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.
p_err is 1 when an odd number of stored bits flipped. sbe and dbe flag a single-bit and a double-bit error.- Cycle 1
One data bit flipped. The syndrome is 5, the position of the flip. The decoder corrects it: 3c is right.
- 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.
| Position | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Holds | P | p1 | p2 | d0 | p4 | d1 | d2 | d3 | p8 | d4 | d5 | d6 | d7 |
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 parity | Syndrome | Meaning | Action |
|---|---|---|---|
| good | 0 | no error | pass the data |
| wrong | p | one flip, at position p (p = 0: the parity bit) | flip bit p, report a corrected error |
| good | not 0 | two flips | flag: the data cannot be trusted |
An odd number of flips makes the overall parity wrong. An even number leaves it good.
- Cycle 1
Parity wrong, syndrome 5: one flip at position 5. Corrected to 3c.
- 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.
- Cycle 3
Parity good, syndrome 9: two flips.
dbeis 1, and nothing is corrected.
Measured on Icarus Verilog: the example with its line fixed.
| Decoder | Single flips (3,328) | Double flips (19,968) |
|---|---|---|
| Correct when syndrome is not 0 | 3,328 right | 16,896 wrong but reported as corrected, 3,072 right by luck |
| SECDED: check the overall parity | 3,328 right | 19,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.
- Storage
- Step
- Data
- Control
- Read
Read the next word and check it, as a normal read does.
- Repair
If one bit was wrong, write the corrected word back. The array is clean again.
- 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.
- I/O
- Storage
- Control / FSM
- Data
- Control
- Test
A March test finds a row with dead cells. Fuses record its number and turn the repair on.
- Compare
Every access compares its row bits with the fused row.
- 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
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.
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.
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.
Synthesize the design to measure its cells and inspect the mapped gates.
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=0Original 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
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.
assign {sbe, dbe} = (syn != 4'd0) ? 2'b10 : 2'b00;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.