Error Correction in Memory

Store each word with SECDED check bits. Correct a single flipped bit on read, and flag a double one.

You Will Be Able To

  • Lay out a (13,8) SECDED word: four Hamming check bits, the data and an overall parity bit.
  • Compute the syndrome on read and use it to correct one flipped bit.
  • Use the overall parity to tell a single error from a double one.
  • Explain scrubbing and spare rows.
Lesson
G8.9
Time
35 min
Runs on
Your browser
Check
4 questions

A server logged only corrected errors, yet one table held a wrong value. Two bits of one word had flipped. The decoder "fixed" the word with the wrong bit and called it a single error.

A Double Error "corrected" as a SingleEach column is one read. p_err is 1 when an odd number of stored bits flipped. sbe and dbe flag a single-bit and a double-bit error.
0123word0123syndrome0509p_errsbedberdataa53c7ea8two flips, sbe=1
Scroll horizontally ↔
  1. Cycle 1

    One data bit flipped. The syndrome is 5, the position of the flip. The decoder corrects it: 3c is right.

  2. Cycle 3

    Two bits flipped, at positions 3 and 10. The syndrome is 3 XOR 10 = 9. The decoder flips bit 9 as well, returns a8 and reports a corrected single error. The right word was 99.

Measured on Icarus Verilog: the example of this lesson as it ships.

A Word That Checks Itself

A memory cell can flip on its own: a particle strike or a weak cell. ECC memory stores extra check bits with each word. SECDED means single error correct, double error detect.

Position0123456789101112
HoldsPp1p2d0p4d1d2d3p8d4d5d6d7

The (13,8) word of this lesson. Check bit pk covers every position p for which p AND k is not 0 (k = 1, 2, 4, 8). P is the parity of all the others.

The positions are numbered so that each check bit has a power of two as its place. On a read, the decoder recomputes the four checks. The four results form the syndrome.

If exactly one bit at position p flipped, every check that covers p fails. So the syndrome is p in binary: it points at the wrong bit.

Correct One, Detect Two

The syndrome alone cannot tell one flip from two. Two flips at positions i and j give the syndrome i XOR j, which looks like a single error somewhere else. The overall parity bit breaks the tie.

Overall paritySyndromeMeaningAction
good0no errorpass the data
wrongpone flip, at position p (p = 0: the parity bit)flip bit p, report a corrected error
goodnot 0two flipsflag: the data cannot be trusted

An odd number of flips makes the overall parity wrong. An even number leaves it good.

The Same Four Reads with the Overall Parity CheckedEach column is one read. Word 1 has one data bit flipped, word 2 its parity bit, word 3 two bits.
0123word0123syndrome0509p_errsbedberdataa53c7eb8
Scroll horizontally ↔
  1. Cycle 1

    Parity wrong, syndrome 5: one flip at position 5. Corrected to 3c.

  2. Cycle 2

    Parity wrong, syndrome 0: the flip is in the parity bit itself. The data 7e is right, and the error is still reported.

  3. Cycle 3

    Parity good, syndrome 9: two flips. dbe is 1, and nothing is corrected.

Measured on Icarus Verilog: the example with its line fixed.

DecoderSingle flips (3,328)Double flips (19,968)
Correct when syndrome is not 03,328 right16,896 wrong but reported as corrected, 3,072 right by luck
SECDED: check the overall parity3,328 right19,968 flagged

Measured on Icarus Verilog: every 8-bit word, with every single flip and every pair of flips of its 13 stored bits.

Scrubbing and Spare Rows

Correcting the read data does not repair the array. If the word stays wrong, a second flip later turns one correctable error into two. A scrubber prevents that.

A Scrub PassArrows show one step of the scrubber. It visits every address in turn while the memory is idle.
  • Storage
  • Step
  • Data
  • Control
A scrub passArrows show one step of the scrubber. It visits every address in turn while the memory is idle. storage Scrub counter the next address step Read and check syndrome and parity step Write back the corrected word storage Error log counts and addresses addresssingle errorany error
  1. storage Scrub counterthe next address
    • address → Read and check
  2. step Read and checksyndrome and parity
    • single error → Write back
    • any error → Error log
  3. step Write backthe corrected word
  4. storage Error logcounts and addresses
  1. Read

    Read the next word and check it, as a normal read does.

  2. Repair

    If one bit was wrong, write the corrected word back. The array is clean again.

  3. Report

    Count every error. Many errors at one address point to a weak cell.

Read the diagram as text
  • Scrub counter: the next address
  • Read and check: syndrome and parity
  • Write back: the corrected word
  • Error log: counts and addresses
  • Scrub counter → Read and check: address
  • Read and check → Write back: single error
  • Read and check → Error log: any error

The scrub rate is chosen so that two flips in one word between visits are very unlikely.

Spare rows handle cells that are bad from the start. Production test finds the bad rows. Fuses then send their addresses to spare rows. ECC handles the rare flips that come later. Lesson G14.5 shows the memory tests that find bad rows.

A Spare Row Replaces a Bad OneArrows show where one access goes. The fuses are set once, after production test.
  • I/O
  • Storage
  • Control / FSM
  • Data
  • Control
A spare row replaces a bad oneArrows show where one access goes. The fuses are set once, after production test. io Address row and column storage Fuses enable and the badrow control Compare row == fused row? storage Main array every other row storage Spare row takes the bad row'splace row bitsbad rowno matchmatch
  1. storage Fusesenable and the bad row
    • bad row → Compare
  2. io Addressrow and column
    • row bits → Compare
  3. control Comparerow == fused row?
    • no match → Main array
    • match → Spare row
  4. storage Main arrayevery other row
  5. storage Spare rowtakes the bad row's place
  1. Test

    A March test finds a row with dead cells. Fuses record its number and turn the repair on.

  2. Compare

    Every access compares its row bits with the fused row.

  3. Steer

    A match goes to the spare row, at the same column. Every other access goes to the main array.

Read the diagram as text
  • Address: row and column
  • Fuses: enable and the bad row
  • Compare: row == fused row?
  • Main array: every other row
  • Spare row: takes the bad row's place
  • Address → Compare: row bits
  • Fuses → Compare: bad row
  • Compare → Main array: no match
  • Compare → Spare row: match

Problem G8.9.2 builds this steering logic. Real memories also have spare columns.

Asked in interviews
  1. How does SECDED work?

    Hamming check bits sit at the power-of-two positions, and each covers the positions with one bit of its number set. On read, the recomputed checks form the syndrome, which names a single flipped bit. An overall parity bit tells one flip from two.

  2. How many check bits for 64 data bits?

    Seven Hamming bits cover up to 127 positions, which is enough for 64 data bits plus the check bits. One more for the overall parity gives 8: the common 72-bit memory word.

  3. What is memory scrubbing?

    A background process that reads every word, corrects single errors and writes the word back. It stops single errors from piling up into double errors that SECDED can only detect.

Try It

The bench writes a5, 3c, 7e and 99. Then it flips one data bit of word 1, the parity bit of word 2, and two bits of word 3.

Word 1 reads syndrome 5 data 3c sbe=1: one flip, corrected. Word 2 reads syndrome 0 and sbe=0: its parity-bit flip goes unreported.

Word 3 is the dangerous one: syndrome 9 data a8 sbe=1 dbe=0. The decoder "corrected" bit 9 and returned a wrong word, reported as a corrected single error.

Fix the line that sets sbe and dbe: correct only when p_err is 1. Run again: word 2 shows sbe=1, and word 3 shows dbe=1.

RTLIcarus Verilog · in your browser · Lint: Verilator service · Synthesize: Yosys service
Edit the design, then Run, Lint or Synthesize
Expected: word 0: stored 1010001001110 syndrome 0 data a5 sbe=0 dbe=0 word 1: stored 0011011100101 syndrome 5 data 3c sbe=1 dbe=0 word 2: stored 0111111110001 syndrome 0 data 7e sbe=0 dbe=0 word 3: stored 1011010000011 syndrome 9 data a8 sbe=1 dbe=0

Original design · 147 cells · 48 flip-flops · 0 latches · 8 logic levels. Synthesis uses Yosys; counts depend on the toolchain.

Read included file: tb.sv
// tb.sv: the bench (read-only). It writes four words, flips stored bits as a particle strike would,
// then reads every word back.
`timescale 1ns/1ps
module tb;
  logic       clk = 0, we = 0;
  logic [1:0] addr = 0;
  logic [7:0] wdata = 0;
  wire  [7:0] rdata;
  wire        sbe, dbe;
  ecc_ram dut (.*);
  always #5 clk = ~clk;
  task automatic write(input logic [1:0] a, input logic [7:0] d);
    addr = a; wdata = d; we = 1; @(posedge clk); #1 we = 0;
  endtask
  initial begin
    write(0, 8'ha5); write(1, 8'h3c); write(2, 8'h7e); write(3, 8'h99);
    dut.mem[1][5]  = !dut.mem[1][5];                                   // word 1: one data bit
    dut.mem[2][0]  = !dut.mem[2][0];                                   // word 2: the overall parity bit
    dut.mem[3][3]  = !dut.mem[3][3]; dut.mem[3][10] = !dut.mem[3][10]; // word 3: two bits
    for (int a = 0; a < 4; a++) begin
      addr = a; #1;
      $display("word %0d: stored %b syndrome %0d data %h sbe=%b dbe=%b", a, dut.mem[a], dut.syn, rdata, sbe, dbe);
    end
    $finish(0);
  end
endmodule

Check Yourself

Predict the outputTwo words take a particle hit on days 1, 3 and 5. Word a is scrubbed on even days; word b never is. What exact line does the program print?
module tb;
  int flips_a = 0, flips_b = 0;          // wrong bits in word a (scrubbed) and word b (not scrubbed)
  int lost_a = 0, lost_b = 0;
  initial begin
    for (int day = 1; day <= 6; day++) begin
      if (day == 1 || day == 3 || day == 5) begin flips_a++; flips_b++; end   // a particle hits both words
      if (flips_a >= 2) lost_a = 1;      // two wrong bits: SECDED can only flag them
      if (flips_b >= 2) lost_b = 1;
      if (day % 2 == 0) flips_a = 0;     // word a is scrubbed on even days: corrected and written back
    end
    $display("lost_a=%0d lost_b=%0d", lost_a, lost_b);
  end
endmodule
Spot the bugEach option sets sbe and dbe, the single-bit and double-bit error flags. The bench flips every single bit and every pair of bits of one word. A single flip must be corrected and reported; a double flip must be flagged. Which option fails?
ConceptHow many check bits does a SECDED code need for 8 data bits?
ConceptWhy does a memory controller scrub?

Common Mistakes

Wrong Correct whenever the syndrome is not zero.

A double error also gives a non-zero syndrome, so a third bit is flipped. On Icarus, 16,896 of the 19,968 double errors come back as wrong data, reported as corrected.

Fix Correct only when the overall parity is wrong. A non-zero syndrome with good overall parity means two errors: flag them.

Before
assign {sbe, dbe} = (syn != 4'd0) ? 2'b10 : 2'b00;
After
assign {sbe, dbe} = p_err ? 2'b10 : (syn != 4'd0) ? 2'b01 : 2'b00;

Wrong Treat syndrome 0 as "no error".

A flip of the overall parity bit itself gives syndrome 0 with a parity error. The spot item counts such a read as wrong when it is not reported.

Fix Syndrome 0 with a parity error is a single error in bit 0. The data is right, but the event is still a corrected error.

Wrong Leave the overall parity bit out of the stored word.

Without it the code corrects one error but cannot tell two from one. It is plain SEC, not SECDED.

Fix Store the parity of the other 12 bits as bit 0, and check all 13 bits on read.

Wrong Correct the read data but leave the stored word wrong.

The error stays in the array. A second flip in the same word makes it uncorrectable. In the scrub program, the word that is never scrubbed is lost.

Fix Write the corrected word back, on the read or in a background scrub pass.

Remember

  • A (13,8) SECDED word: Hamming check bits at 1, 2, 4, 8, data at the other positions, overall parity at 0.
  • The syndrome is the XOR of the positions that hold a 1. For one flip it names the flipped bit.
  • Parity wrong: one flip, correct it. Parity good and syndrome not 0: two flips, flag them.
  • Correcting without the parity check turns double errors into silent wrong data.
  • Scrubbing writes corrected words back. Spare rows replace cells that were bad at test.

Practice

Report a problem with this page