Saltar al contenido ForoHackers

SECDED explained with a 7-bit example (Hamming(7,4))

Arquitectura de computadorasTeoría de la informaciónIngeniería de fiabilidad
#1008 · bitflip_betty · · Denunciar

As promised. ECC memory uses a code called SECDED: Single-Error Correct, Double-Error Detect. To see the idea, shrink it to Hamming(7,4): 4 data bits, 3 parity bits.

Number the positions 1 to 7. Put the parity bits at positions that are powers of two (1, 2, 4) and the data at 3, 5, 6, 7:

position:  1   2   3   4   5   6   7
role:      p1  p2  d1  p4  d2  d3  d4

Each parity bit covers the positions whose binary index has that bit set:

  • p1 covers 1, 3, 5, 7
  • p2 covers 2, 3, 6, 7
  • p4 covers 4, 5, 6, 7

Each parity is chosen so its group has an even number of ones. Example: data 1011 goes in d1 d2 d3 d4, giving _ _ 1 _ 0 1 1. Positions 3, 5, 7 hold 1, 0, 1, which is already even, so p1 = 0. Positions 3, 6, 7 hold 1, 1, 1, odd, so p2 = 1. Positions 5, 6, 7 hold 0, 1, 1, even, so p4 = 0. Codeword: 0 1 1 0 0 1 1.

Now flip one bit, say position 6. Recompute the three checks over the received word. They give a 3-bit syndrome: the failing groups here are p2 and p4, so syndrome = binary 110 = 6. The syndrome is the position of the flipped bit. Flip it back. Magic, and just three XORs.

For the "DED" half, add one more overall parity bit over the entire word. A single error makes the overall parity odd and the syndrome non-zero: correct it. Two errors leave the overall parity even but the syndrome non-zero: you can tell something is wrong and cannot fix it, so you report an uncorrectable error.

Real memory scales this up: 64 data bits plus 8 check bits (72 bits per word), which is why ECC DIMMs have nine chips where non-ECC has eight.

#1416 · hexdump_hermit · · Denunciar

The mnemonic that made it stick for me: position n is covered by exactly those parity bits that appear in the binary expansion of n. Position 6 is 110, so it is covered by p4 and p2. That is why the syndrome reads out the position directly.

#1417 · bitflip_betty · · Denunciar

Exactly, and it is the reason the decoder is so cheap in hardware: three XOR trees and no search. The real overhead of ECC is the extra chip, not the logic.

#1418 · null_terminated_hopes · · Denunciar

I understood it on the second read, which for me counts as a standing ovation. The idea that the syndrome is the address of the error is what I will remember.

#1419 · r3l1c_0f_bbs · · Denunciar

So the parity error that froze my old machine was the "D" in SECDED, the detect-and-give-up half, with no correct. Everything had a purpose. Thank you.

Inicia sesión o únete para responder.