One word through the 39-bit code

Store 32'hDEAD_BEEF with SECDED and flip Hamming position 13: the syndrome reads 001101, which is 13, and the decoder repairs it. Flip position 22 as well and the syndrome reads 27, a position nobody touched. A decoder that trusts the syndrome alone flips position 27 and returns DE8CBFEF as good data; the overall parity bit is what stops it.

This lesson follows the layout frozen in SECDED Encode and Syndrome, which derives the (8,4) code. Hamming positions 1 to 38 hold six check bits at 1, 2, 4, 8, 16 and 32 and the 32 data bits in the other positions, in ascending order. Overall parity P sits at position 39. Every number below is printed by the bench at the end of the page.

Read each cell top to bottom: Hamming position, name, stored value. The position number, not the vector index, is what the syndrome reports.

• Check bits sit at the powers of two: 1, 2, 4, 8, 16 and 32. P at 39 is outside the Hamming part.

• Data bits fill the gaps in order: d0 at 3, d1 to d3 at 5 to 7, d4 to d10 at 9 to 15, d11 to d25 at 17 to 31, d26 to d31 at 33 to 38.

• Storage: position k is vector bit cw[k-1], so P is cw[38] and d0 is cw[2].

Computing the six check bits and P

Check bit 2^b covers every position whose number has bit b set. It is chosen so that its group, itself included, holds an even number of ones. Take p32: it covers positions 33 to 38, which hold d26 to d31. The top six bits of DEAD_BEEF are 1, 1, 1, 0, 1, 1 at positions 33 to 38: five ones, an odd count, so p32 = 1.

P is the XOR of positions 1 to 38. Those 38 bits hold 27 ones, so P = 1 and the full 39-bit word holds an even 28. The stored codeword, MSB first, is:

codeword cw[38:0] = 39'h77d5b76e77
positions 1..13: 1 1 1 0 1 1 1 0 0 1 1 1 0
positions 14..26: 1 1 0 1 1 1 0 1 1 0 1 1 0
positions 27..39: 1 0 1 0 1 1 1 1 1 0 1 1 1

The hex value reads from cw[38] down to cw[0]; the rows read position 1 upwards. They are the same 39 bits, which is worth checking once by hand: the hex starts with 111, and positions 39, 38 and 37 are 1, 1, 1.

Four faults, decoded

The decoder recomputes the six checks over the received positions 1 to 38. The result is the syndrome. It also XORs all 39 bits: an odd result means an odd number of bits flipped.

clean                      syndrome=000000 (0) overall_bad=0 ce=0 ue=0 data=deadbeef
flip position 13 (d8)      syndrome=001101 (13) overall_bad=1 ce=1 ue=0 data=deadbeef
flip positions 13 and 22   syndrome=011011 (27) overall_bad=0 ce=0 ue=1 data=deacbfef
  a decoder without P would flip position 27 (d21) and return de8cbfef
flip position 39 (P)       syndrome=000000 (0) overall_bad=1 ce=1 ue=0 data=deadbeef
flip positions 1, 6, 32    syndrome=100111 (39) overall_bad=1 ce=0 ue=1 data=deadbeeb

Read each line as syndrome, then overall parity, then the decision. The data column is the decoder output; on a UE line it is the raw, uncorrected word, which the read response must poison.

• Single flip: position 13 is in checks 1, 4 and 8, because 13 = 1 + 4 + 8. Those three checks fail, and their weights add back to 13.

• Double flip: the syndrome is 13 XOR 22 = 27. Position 27 holds d21, which is good. Even overall parity is the only sign that 27 is a lie.

• Parity-only flip: P is in no check, so the syndrome stays 0 while the overall XOR is odd. The data needs no repair; rewrite the word to clear the bad P.

• Syndrome 39: the Hamming part ends at 38, so no single flip can produce it. Three flips can (1 XOR 6 XOR 32 = 39). Treat it as UE and never use it as an index.

The decision itself is four lines of RTL. ce includes the P-only case, where the syndrome is 0 and nothing in positions 1 to 38 is flipped.

1
2
3
4
5

// snippet: the classification in secded32_dec (full listing below)
assign ce   = overall_bad && (syndrome <= 6'd38);     // syndrome 0 here means P itself
assign ue   = (!overall_bad && syndrome != 0) || (overall_bad && syndrome > 6'd38);
assign fix  = (ce && syndrome != 0) ? (39'd1 << (syndrome - 6'd1)) : '0;  // position k is bit k-1
assign data = extract(cw ^ fix);

Common mistakes

The bench catches it at once. Here is the decoder with 39'd1 << syndrome, the only change:

flip position 13 (d8)      syndrome=001101 (13) overall_bad=1 ce=1 ue=0 data=deadbdef
...
FAIL single flip at position 2: data=00000001 expected 00000000
FAIL single flip at position 3: data=00000001 expected 00000000
FATAL: bad.sv:169: FAIL: 37002 errors

The decoder still says ce=1. It left d8 wrong and also flipped position 14 (d9), so DEADBEEF came back as DEADBDEF. A bench that checks only the ce flag would pass this.

Testbench

The encoder, the decoder and a bench that prints every number on this page, then checks all 39 single flips on 1000 words and all 741 pairs on 100 of them. The bench also re-encodes each word with its own position table, so the encoder is not checked against itself.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

// secded32: extended Hamming (39,32). Hamming position k (1..39) is stored in cw[k-1].
// Check bits sit at positions 1, 2, 4, 8, 16, 32; data d0..d31 fill the other positions
// 3..38 in ascending order; overall parity P sits at position 39.
module secded32_enc (
  input  logic [31:0] data,
  output logic [38:0] cw
);
  function automatic logic [38:0] encode(input logic [31:0] d);
    logic [38:0] c;
    int j;
    c = '0;
    j = 0;
    for (int k = 1; k <= 38; k++)
      if ((k & (k - 1)) != 0) begin        // not a power of two: next data bit
        c[k-1] = d[j];
        j++;
      end
    for (int b = 0; b < 6; b++)            // check 2^b: XOR of the other positions with bit b set
      for (int k = 1; k <= 38; k++)
        if (k[b] && k != (1 << b)) c[(1 << b) - 1] ^= c[k-1];
    c[38] = ^c[37:0];                      // overall parity over positions 1..38
    return c;
  endfunction
  assign cw = encode(data);
endmodule

module secded32_dec (
  input  logic [38:0] cw,
  output logic [31:0] data,
  output logic [5:0]  syndrome,
  output logic        overall_bad,
  output logic        ce,                  // one bit was wrong and is corrected
  output logic        ue                   // uncorrectable: data must not be used
);
  function automatic logic [5:0] syn(input logic [38:0] c);
    logic [5:0] s;
    s = '0;
    for (int b = 0; b < 6; b++)
      for (int k = 1; k <= 38; k++)
        if (k[b]) s[b] ^= c[k-1];          // position k lives at index k-1
    return s;
  endfunction
  function automatic logic [31:0] extract(input logic [38:0] c);
    logic [31:0] d;
    int j;
    d = '0;
    j = 0;
    for (int k = 1; k <= 38; k++)
      if ((k & (k - 1)) != 0) begin
        d[j] = c[k-1];
        j++;
      end
    return d;
  endfunction
  logic [38:0] fix;                        // one-hot mask of the bit to flip back
  assign syndrome    = syn(cw);
  assign overall_bad = ^cw;
  assign ce   = overall_bad && (syndrome <= 6'd38);  // syndrome 0 here means P itself
  assign ue   = (!overall_bad && syndrome != 0) || (overall_bad && syndrome > 6'd38);
  assign fix  = (ce && syndrome != 0) ? (39'd1 << (syndrome - 6'd1)) : '0;
  assign data = extract(cw ^ fix);
endmodule

Related topics

• SECDED encode and syndrome

• Correction and reporting