Project: A SEC-DED Encoder and Decoder
November 16, 202649 min readbeginner
Building the (72,64) SEC-DED encoder and decoder of a 64-bit memory port in two codes, checking it against a model, proving it with a solver, and counting the gates and levels Yosys really builds.
SECDED and Hsiao Codes compared two (72,64) codes on paper, the extended Hamming code and Hsiao's code, by counting the ones in their check matrices and predicting the gates and gate delays each would cost. This project builds both. It writes the encoder and decoder of a 64-bit memory port, generic over the check matrix, checks them against a software model on 2,802,514 simulated cases per code, proves them correct with a solver for all data words, and synthesizes them to test the predictions. Some predictions hold exactly, one reverses, and the reasons are the most useful part of the chapter.
Every number in the chapter is recomputed by ch30_project_secded_encoder_and_decoder.py in the python/ folder of the companion repository ecc-book-lab, and the charts are drawn by ch30_charts.py in the same folder. The GNU Octave twin ch30_project_secded_encoder_and_decoder.m prints the same lines, as The Octave Route explains. The hardware is in hdl/, the cocotb bench that simulates it is in tb/, and the formal runner is in formal/, each under a secded72 subfolder, while the synthesis script is in synth/. The bench and the formal runner are driven from Python and have no Octave twin.
This chapter does not teach SystemVerilog or cocotb. Every listing arrives finished, and the text explains what the hardware does and proves why it is right. The languages themselves are taught from the beginning in RTL Design and Verification and in the material on hardware description languages in Computer Architecture.
01.Setting Up
Setting Up the Lab Bench installs the tools and a Python virtual environment holding cocotb. The results were measured with the versions it records for 2026-11-14, Verilator 5.054, Yosys 0.71, SymbiYosys 0.71 and Z3 5.4.1, and the Yosys build was git 5628c13. With that environment active, the five commands below, run from the root of the companion repository, reproduce every hardware result in the chapter.
| python tb/secded72/check_secded72.py | |
| python tb/secded72/run_secded72.py | |
| python tb/secded72/run_secded72.py --flag parity | |
| python synth/synth_secded72.py | |
| python formal/secded72/run_formal72.py |
The first ties every matrix to SECDED and Hsiao Codes, the second and third run the bench with each form of the uncorrectable flag, the fourth synthesizes every block and compares the counts with the recorded data, and the fifth runs the nine formal tasks. On the recorded run each bench command took about a minute and a half and the formal tasks about eight minutes. The option --code picks one code, and the exercises use it.
02.A 64-Bit Word Behind a Memory Port
Figure 1 shows where the logic sits. A 64-bit word on its way into memory passes through the encoder, which appends 8 check bits, and the memory stores all 72. On the way out, the decoder returns 64 data bits and two flags. The flag corrected says that one bit was wrong and has been put right, and uncorrectable says that the word holds an error the code cannot repair. Its gates are area, paid again at every port, and its gate delays between the memory and the data output are latency, added to every load.
The decoder must keep a precise promise, which Verifying ECC Hardware calls the guarantee, over a set of error patterns it calls the design envelope. Write for the 64-bit data word, for its 72-bit codeword, for the 72-bit error pattern with a 1 wherever the memory flipped a bit, and for the number of ones in . The decoder sees , where is bitwise XOR, and returns its data output, corrected and uncorrectable.
Here is the 64-bit data part of , so on a double error the decoder passes the received data bits through untouched and raises uncorrectable. The envelope holds patterns, where counts the ways to choose two of the 72 positions. Beyond it the code promises nothing.
03.Architecture Decisions
Four decisions shape the design. The first is the code. SECDED and Hsiao Codes predicted that Hsiao's matrix [1], with 216 ones and no row heavier than 27, needs 208 XOR gates in 5 levels for its syndrome, against 276 gates in 7 levels for the extended Hamming matrix [2], whose 284 ones include a 72-input parity row. Hsiao is the default, and extended Hamming is built beside it so that the prediction is tested rather than assumed.
The second is genericity. Every module takes one parameter, CODE, naming a code in a generated package of constants, and derives its widths N and K from it, so no one can set a width that disagrees with the matrix. The third is that neither block holds a register. A combinational decoder adds gate delays but no clock cycle, and leaves the placement of any register to the design around it.
The fourth is the bit order. The Hsiao codeword puts the data at positions 0 to 63 and the check bits at 64 to 71. The extended Hamming codeword keeps the order of SECDED and Hsiao Codes, with check bits at positions 0, 1, 2, 4, 8, 16, 32 and 64 and data in the other positions in increasing order, so the low seven bits of the column at position spell in binary. The interface of the decoder, from hdl/secded72/secded72_dec.sv, is the contract every check in the chapter tests.
| module secded72_dec #( | |
| parameter int CODE = secded72_pkg::HSIAO, // which code of secded72_pkg.sv | |
| parameter int FLAG = 0, // 0: no-match form, 1: parity form | |
| parameter int N = secded72_pkg::n_of(CODE), // derived from CODE; never set by hand | |
| parameter int K = secded72_pkg::k_of(CODE) // derived from CODE; never set by hand | |
| ) ( | |
| input logic [N-1:0] received, // bit j is codeword position j | |
| output logic [K-1:0] data, // the corrected data bits | |
| output logic corrected, // a single error was corrected | |
| output logic uncorrectable // the word holds an error it cannot correct | |
| ); |
The parameter FLAG picks one of two ways to compute uncorrectable, and a later section proves that they agree everywhere the guarantee speaks.
04.One Source for Every Matrix
Two copies of a matrix, one in the hardware and one in the model that checks it, can drift apart, so the project writes each matrix once, as a list of columns in tb/secded72/secded72_model.py, where each column is an 8-bit number whose bit is the entry in row . The Hsiao list is the 56 weight-3 columns, one for each choice of three of the eight rows, then the eight cyclic rotations of the weight-5 column with ones in rows 0 to 4, then the eight weight-1 check columns. The extended Hamming list puts at position the number in rows 0 to 6 and a 1 in row 7, the overall parity row.
Figure 2 draws both, and the balance of the Hsiao rows follows from the construction. A row lies in weight-3 columns, since the other two rows of such a column can be any two of the remaining seven, in 5 of the 8 rotations, and in one check column, so every row holds ones. The extended Hamming rows run from 8 ones in row 6, which only positions 64 to 71 reach, to 72 in the parity row.
Two scripts guard the list. tb/secded72/gen_secded72_pkg.py writes hdl/secded72/secded72_pkg.sv from the model, with each code's columns, rows, positions and encoder masks, and with --check reports whether the package on disk is current. tb/secded72/check_secded72.py compares every column list with the one the script of SECDED and Hsiao Codes builds, checks that the columns are distinct and nonzero with no three summing to zero, which makes the minimum distance at least four, and runs the package check. The bench runner calls it first, so a drifted matrix stops the run before a single case.
05.The Encoder
An encoder chooses check bits that make every row of the check matrix sum to zero over the codeword. Write for the check matrix over , the arithmetic of single bits in which addition is XOR and multiplication is AND, for its entry in row and column , and for bit of a 72-bit word . The syndrome of has the bits
so is the XOR of the bits row covers, and is a codeword exactly when all eight are zero.
Proof. The column at position has its single 1 in row , so row covers one check bit, the one at position , besides its data bits. Setting in Equation 2 says that this check bit XORed with those data bits is zero, and XORing both sides with the data bits gives the check bit as their XOR. Each row holds its own check bit and no other, so the eight choices do not interfere.
Each Hsiao row holds 27 ones, one of them the check bit, so each check bit is a 26-input XOR. The next lemma says what such a gate costs.
Proof. Each gate of a tree takes two signals and returns one, so it lowers by one the number still to be combined, and going from signals to one takes gates. For depth, an input at level 0 depends on input. A gate at level combines two signals of level at most , each depending on at most inputs, so it depends on at most . An output depending on inputs therefore has , and since is a whole number, . A balanced tree halves the number of signals at each level, rounding up, and leaves one after exactly levels.
The Hsiao encoder is therefore eight trees of 25 gates, 200 in all, each levels deep. Extended Hamming is less obliging, since its parity row covers every check column, so the model solves the eight check equations by Gauss-Jordan elimination, the row reduction that turns the check columns into the identity, and reads off for each check bit a mask of the data bits it XORs. The masks hold 35, 35, 35, 35, 31, 31, 31 and 7 data bits, which makes 232 gates as separate trees, 6 levels deep. The encoder, from hdl/secded72/secded72_enc.sv, is two loops the package fills in.
| for (genvar b = 0; b < K; b++) begin : g_data | |
| localparam int P = int'(DATA_POS[8*b +: 8]); | |
| assign codeword[P] = data[b]; | |
| end | |
| for (genvar t = 0; t < R; t++) begin : g_check | |
| localparam int P = int'(CHECK_POS[8*t +: 8]); | |
| localparam logic [K-1:0] MASK = CHECK_MASKS[MAX_K*t +: K]; | |
| assign codeword[P] = ^(data & MASK); | |
| end |
The first loop copies each data bit to its position, and the second makes each check bit the XOR of the data bits its mask selects, since the unary ^ of SystemVerilog XORs every bit of its operand. One body serves every matrix because the positions and masks are package constants.
06.The Decoder
The decoder works in the three stages of Figure 3. The syndrome stage computes with eight XOR trees over all 72 bits, the column-match stage compares with each column, and the correction stage flips each data bit whose own column matched.
A single error at position has syndrome , because Equation 2 is linear and the codeword contributes zero, so exactly the match line rises, the columns being distinct. Flipping bit back is then one XOR. The stages and flags, from hdl/secded72/secded72_dec.sv, read almost as that sentence does.
| // ---- column-match stage: match[j] is 1 when the syndrome equals column j | |
| logic [N-1:0] match; | |
| for (genvar j = 0; j < N; j++) begin : g_match | |
| localparam logic [R-1:0] COLUMN = COLUMNS[MAX_R*j +: R]; | |
| assign match[j] = (syndrome == COLUMN); | |
| end | |
| // ---- correction stage: flip the data bit whose column matched | |
| for (genvar b = 0; b < K; b++) begin : g_correct | |
| localparam int P = int'(DATA_POS[8*b +: 8]); | |
| assign data[b] = received[P] ^ match[P]; | |
| end | |
| // ---- flags | |
| assign corrected = |match; | |
| if (FLAG == 0) begin : g_nomatch | |
| assign uncorrectable = (|syndrome) & ~corrected; | |
| end else if (PARITY_ROW < 0) begin : g_even | |
| assign uncorrectable = (|syndrome) & ~(^syndrome); | |
| end else begin : g_parity_bit | |
| assign uncorrectable = (|syndrome[PARITY_ROW-1:0]) & ~syndrome[PARITY_ROW]; | |
| end | |
| endmodule |
The output corrected is the OR of all 72 match lines, so it rises for a single error in a check bit too, where no data bit changes. The no-match form of uncorrectable says that the syndrome is nonzero and no column matched. Counting the gates of Figure 3 stage by stage gives the hand count that SECDED and Hsiao Codes began.
Proof. Each term counts one stage. The syndrome costs gates. Each of the match lines is an AND of bits, a tree of gates by the lemma on wide gates, with the inversions free. Each of the data bits passes one XOR. The OR of the match lines takes gates. The no-match flag needs the OR of the syndrome bits, gates, and one AND with corrected inverted. A data bit waits levels for the syndrome, for a balanced AND over inputs and one for its XOR. The output corrected replaces that XOR with a balanced OR over lines, and uncorrectable adds its AND after corrected, which arrives later than the OR of the syndrome bits.
For Hsiao, and , so at depths 9, 15 and 16. For extended Hamming, and , giving 923 gates at depths 11, 17 and 18. The parity forms change only the flag. For Hsiao it is the OR and the XOR of the eight syndrome bits, 7 gates each, joined by one AND, for 862 gates, at depth since it no longer waits for corrected. For extended Hamming it is the OR of the seven low syndrome bits, 6 gates, and an AND with the parity bit inverted, for 922 gates at depth , the low trees being at most 6 deep and the parity row 7.
07.Two Flags That Agree Inside the Envelope
Proof. Take Hsiao first. Every column has odd weight, 1, 3 or 5. If , then is nonzero and of even weight, so it is no column and . If and , then is nonzero, no column, and of odd weight, which is . In the envelope, gives and both forms 0. A single error gives a column, so , and its odd weight gives . A double error at positions and gives , nonzero because the columns are distinct, and of even weight because , so and therefore .
For extended Hamming every column has , and the low bits of the columns are the distinct numbers 0 to 71. If , then , so is no column, and , so . If , then , since a zero low part leaves as zero or as the column of position 0, neither of which flags. If also , then and the low bits match no column, so they are 72 or more. In the envelope, a single error gives a column, so , and gives . A double error at and gives and low bits , so and therefore .
The companion script checks every case. Of the 256 syndromes, 72 match a column, so fires on . fires on 127, so for each code holds syndromes, and never fires alone. On the 2,629 patterns of the envelope the two forms disagree on none.
The parity form is shallower, since it never reads the match lines, so by the hand count the Hsiao flag is ready at depth 9 rather than 16, and the netlist below gives 10. The no-match form catches more beyond the envelope, where a syndrome in raises it and slips past the parity form. For both codes the parity form flags no triple at all, since three odd-weight Hsiao columns XOR to odd weight and three ones in row 7 make , as the second worked example shows.
08.The Reference Model
The model in tb/secded72/secded72_model.py is plain Python with nothing beyond the standard library. A word is an integer whose bit is position , and these functions are the syndrome, the data extraction, the flag and the decoder.
| def syndrome(self, word: int) -> int: | |
| s = 0 | |
| for i, mask in enumerate(self.row_masks): | |
| s |= ((word & mask).bit_count() & 1) << i | |
| return s | |
| def data_bits(self, word: int) -> int: | |
| d = 0 | |
| for b, p in enumerate(self.data_positions): | |
| d |= ((word >> p) & 1) << b | |
| return d | |
| def uncorrectable(self, s: int, matched: bool, flag: str) -> bool: | |
| if flag == "nomatch": | |
| return s != 0 and not matched | |
| if self.parity_row is None: | |
| return s != 0 and s.bit_count() % 2 == 0 | |
| hamming_bits = s & ((1 << self.parity_row) - 1) | |
| return hamming_bits != 0 and not (s >> self.parity_row) & 1 | |
| def decode(self, received: int, flag: str = "nomatch") -> tuple: | |
| """Return (data, corrected, uncorrectable) for one received word.""" | |
| s = self.syndrome(received) | |
| j = self.position_of.get(s) | |
| matched = j is not None | |
| if matched: | |
| received ^= 1 << j | |
| return (self.data_bits(received), int(matched), int(self.uncorrectable(s, matched, flag))) |
The integer row_masks[i] has bit set when position lies in row , so (word & mask).bit_count() & 1 is the XOR of the bits row covers. The dictionary position_of maps each column back to its position, so the model decodes by lookup rather than with 72 comparators.
The model and the hardware still share the column list, and the package's masks come from the model's elimination, so a mistake there would sit in both. The bench therefore checks each case against a second oracle too, the guarantee of Equation 1, which the function spec computes from , and the weight of alone. A wrong mask makes some codeword's syndrome nonzero, so a clean word is misread and the guarantee fails even where the model agrees. A shared mistake that still leaves a valid SEC-DED code passes both oracles, and the column check against SECDED and Hsiao Codes exists for that case.
09.The Bench
The bench hdl/secded72/secded72_bench.sv wires the encoder to the decoder through the channel assign received = codeword ^ error;, so a test drives a data word and an error pattern and reads back the codeword and the decoder's outputs. The channel lives in the bench, which keeps both blocks synthesizable as they stand. The test in tb/secded72/test_secded72.py runs under cocotb [3] and Verilator [4], and its heart is one loop.
| for d in words: | |
| codeword = CODE.encode(d) | |
| dut.data.value = d | |
| for e in patterns: | |
| dut.error.value = e | |
| await Timer(1, unit="ns") | |
| got_codeword = dut.codeword.value.to_unsigned() | |
| got = (dut.data_out.value.to_unsigned(), int(dut.corrected.value), int(dut.uncorrectable.value)) | |
| want = CODE.decode(codeword ^ e, FLAG) | |
| cases += 1 | |
| by_weight[e.bit_count()] += 1 | |
| if got_codeword != codeword or got != want: | |
| model_mismatches += 1 | |
| if first is None: | |
| first = f"model: d={d:#x} e={e:#x} hardware {got} codeword {got_codeword:#x}, model {want}" | |
| if got != model.spec(CODE, d, e): | |
| spec_mismatches += 1 | |
| if first is None: | |
| first = f"guarantee: d={d:#x} e={e:#x} hardware {got}, guarantee {model.spec(CODE, d, e)}" |
For each data word the loop encodes once in the model, then drives each pattern and waits one nanosecond of simulated time for the logic to settle. The codeword is compared with the model's, the outputs with the model's decode and with the guarantee, and each case is counted by its weight. The words are the all-zero word, the all-ones word, the 64 words with a single 1 and 1,000 random words drawn with the fixed seed 30, so the cases number
of which have weight 0, weight 1 and weight 2.
Table 1. The four sweeps of the bench, one for each code and form of the uncorrectable flag, with the time each sweep took inside the simulator on the recorded run
| Code | Flag | Cases | Disagreements | Sweep time |
|---|---|---|---|---|
| Hsiao (72,64) | no-match | 2,802,514 | 0 | 44.1 s |
| extended Hamming (72,64) | no-match | 2,802,514 | 0 | 45.2 s |
| Hsiao (72,64) | parity | 2,802,514 | 0 | 45.4 s |
| extended Hamming (72,64) | parity | 2,802,514 | 0 | 46.7 s |
Source: measured by tb/secded72/run_secded72.py, with the case counts reproduced by ch30_project_secded_encoder_and_decoder.py.
Table 1 records zero disagreements with either oracle in all four sweeps, and a theorem of Verifying ECC Hardware, in its section When One Codeword Stands for All, makes that stronger than it looks. If the encoder is systematic, the syndrome is linear over with on every codeword, and the match logic and flags see the received word only through , then the case of and is wrong exactly when the case of the zero word and is wrong.
Proof. The encoder copies each data bit unchanged to its position, so it is systematic. Each syndrome bit is an XOR of received bits, as in Equation 2, which is linear over . The masks solve the check equations, as the lemma on the Hsiao check bits shows for Hsiao and the model's elimination does for every code, so on every codeword. The match lines compare with constants, both flags read only and the match lines, and the correction XORs each received data bit with a match line, so the match logic and flags see the received word only through .
So for the design as written, the 2,629 patterns on the zero word settle all data words, and the other 1,065 words are there because a bug can break a hypothesis. The zero word encodes to zero under any XOR encoder, so a wrong mask is invisible on it. The 64 words with a single 1 test every mask bit, since an XOR encoder's output is the XOR of the contributions of single data bits, and the all-ones and random words catch a bug that is not linear at all, such as an AND typed where an XOR belongs.
The bench still simulates only the RTL inside the envelope, and its 1,066 words stand for every data word only through a lemma about the design that passed. The formal proof closes that gap.
10.The Formal Proof
A solver checks a statement for every input at once. The wrapper hdl/secded72/secded72_formal.sv builds the bench's chain of encoder, channel and decoder but leaves its inputs free, so SymbiYosys [5] may pick any of them. The data word d ranges over all values, and the error pattern is built from two optional positions, p1 and p2, each used when its bit v1 or v2 is set.
| assign e = (v1 ? (N'(1) << p1) : '0) | (v2 ? (N'(1) << p2) : '0); | |
| assign wt = (v1 && v2 && p1 != p2) ? 2'd2 : (v1 || v2) ? 2'd1 : 2'd0; |
The pattern therefore ranges over exactly the patterns of weight 0, 1 and 2. When both positions are used and equal, the OR makes a pattern of weight 1, and wt agrees. The properties follow.
| always_comb begin | |
| assume (int'(p1) < N); | |
| assume (int'(p2) < N); | |
| if (VACUOUS == 1) assume (!v2); | |
| if (wt == 2'd0) assert (data_out == d && !corrected && !uncorrectable); | |
| if (wt == 2'd1) assert (data_out == d && corrected && !uncorrectable); | |
| if (wt == 2'd2) assert (data_out == received_data && !corrected && uncorrectable); | |
| assert (data_out == d || uncorrectable); | |
| cover (wt == 2'd0); | |
| cover (wt == 2'd1); | |
| cover (wt == 2'd2); | |
| end |
The first three assertions are Equation 1 line by line, with received_data standing for the received data bits. The fourth, at any weight, says the data out is right unless uncorrectable is raised, which rules out wrong data handed over in silence. The three covers ask for an input of each weight on the balanced Hsiao and extended Hamming codes, guarding against a vacuous proof, one whose assumptions exclude the cases that matter, and every proof makes the same assumptions. The SymbiYosys file formal/secded72/secded72.sby [6] names nine tasks and their engines.
| [tasks] | |
| prove_hsiao prove hsiao nomatch | |
| prove_hsiao_parity prove hsiao parity | |
| prove_hamming prove hamming nomatch | |
| prove_hamming_parity prove hamming parity | |
| cover_hsiao cover hsiao nomatch | |
| cover_hamming cover hamming nomatch | |
| narrow_cover_hsiao cover hsiao nomatch narrow | |
| prove_dictionary prove dictionary nomatch | |
| prove_39_32 prove h39 nomatch | |
| [options] | |
| prove: mode prove | |
| cover: mode cover | |
| depth 1 | |
| [engines] | |
| prove: abc pdr | |
| cover: smtbmc z3 |
The proofs run on the pdr command of ABC [7], which its own help describes as property-directed reachability, the method Bradley introduced as IC3 [8], and the covers on yosys-smtbmc with Z3 [9]. The design has no register, so a single time step holds every behavior and a depth of 1 suffices.
Table 2. The nine formal tasks, with the verdict each must give and the time each took on the recorded run
| Task | What it checks | Verdict | Time |
|---|---|---|---|
prove_hsiao | Hsiao, no-match flag | PASS | 18.1 s |
prove_hsiao_parity | Hsiao, parity flag | PASS | 19.7 s |
prove_hamming | extended Hamming, no-match flag | PASS | 189.4 s |
prove_hamming_parity | extended Hamming, parity flag | PASS | 237.7 s |
cover_hsiao | each weight reachable, Hsiao | PASS | 0.5 s |
cover_hamming | each weight reachable, extended Hamming | PASS | 0.4 s |
narrow_cover_hsiao | a narrowed assumption | FAIL, as intended | 0.4 s |
prove_dictionary | Hsiao in dictionary order | PASS | 21.3 s |
prove_39_32 | Hsiao (39,32) | PASS | 2.0 s |
Source: measured by formal/secded72/run_formal72.py, 489.6 s in all.
Table 2 shows every task giving its expected verdict. The four proofs say that both decoders, with both flags, meet the guarantee for every data word and every pattern of the envelope, about cases each by the count of Verifying ECC Hardware. The engine matters. An earlier run of prove_hsiao on yosys-smtbmc with Z3, the engine Verifying ECC Hardware used, took 723 seconds. Solver times vary between runs too, prove_hamming having taken 290.5 seconds on an earlier run, so they measure the proof and not the hardware.
The task narrow_cover_hsiao plants the classic mistake on purpose. With VACUOUS set to 1 the wrapper assumes !v2, which forbids every pattern of weight 2. A proof under that assumption would pass trivially, and only the cover notices. The solver reports the weight-2 cover at line 90 of the wrapper unreached, and the runner counts that FAIL as the verdict it expects.
A failing proof shows one wrinkle of the installation. SymbiYosys writes a counterexample trace with yosys-witness, which needs the Python module click, and without it the task ends DONE (ERROR, rc=16) with engine_0 (abc pdr) returned FAIL in its log. The runner reads that line and reports FAIL, so a broken decoder never passes for a broken tool. The proof covers the RTL inside the envelope, not the gates, timing or heavier patterns, and it inherits the matrix from the package, which is why the column check runs first.
11.Counting Gates in a Real Netlist
The script synth/synth_secded72.py asks Yosys [10] what it really builds. It flattens each block and hands it to ABC [7] with abc -g AND,OR,XOR and the script strash; balance -x; map. As ABC's own help describes them, strash turns the logic into two-input ANDs and inverters, balance -x rebalances it to minimize levels, wide XORs included, and map performs standard-cell mapping with area recovery, onto a library Yosys writes in which AND, OR, XOR and the inverter all have the same delay. The script then counts as the hand count does, with inverters free.
Each block is synthesized two ways. As separate trees, each syndrome bit and check bit is synthesized alone, so no gate can serve two outputs, which is the hand count's model. As a whole block, ABC may share any gate, as it would in a real design.
Table 3. Two-input gates and levels for each block, predicted by hand and measured in the Yosys netlist, for both (72,64) codes. A decoder's levels are given for its data output, corrected and uncorrectable
| Block | Hsiao, predicted | Hsiao, measured | Ext. Hamming, predicted | Ext. Hamming, measured |
|---|---|---|---|---|
| Syndrome, separate trees | 208, 5 levels | 208, 5 levels | 276, 7 levels | 276, 7 levels |
| Encoder, separate trees | 200 | 200 | 232 | 232 |
| Syndrome, whole block | 208, 5 levels | 169, 5 levels | 276, 7 levels | 137, 7 levels |
| Encoder, whole block | 200, 5 levels | 159, 5 levels | 232, 6 levels | 175, 6 levels |
| Decoder, no-match flag | 855, levels 9/15/16 | 550, levels 9/15/16 | 923, levels 11/17/18 | 478, levels 11/17/18 |
| Decoder, parity flag | 862, levels 9/15/9 | 457, levels 9/15/10 | 922, levels 11/17/10 | 385, levels 11/17/10 |
Source: measured by synth/synth_secded72.py into data/ch30/secded72_gates.json, with the predictions and the comparison reproduced by ch30_project_secded_encoder_and_decoder.py.
The separate trees match the hand count exactly, gate for gate and level for level, as the lemma on wide gates says they must. Allowed to share, ABC cuts the Hsiao syndrome from 208 gates to 169 and the extended Hamming syndrome from 276 to 137, so the matrix with more ones ends with fewer gates, as Figure 6 shows. The reason is in the columns. Positions and of the extended Hamming code, for any whole number , differ only in row 0, because the binary numbers and differ only in their last digit. Every other row that covers one covers both, so one gate computing serves all those rows, and the argument repeats for groups of four positions, and on up. The Hsiao matrix avoids such repeats. Two weight-3 columns share at most two rows and a check column lies in one row only, so a gate over a pair of positions serves few rows.
Sharing cost no level in the syndrome or the encoder. The whole-block Hsiao syndrome is 5 levels deep in every bit, and the extended Hamming bits are 6, 6, 6, 5, 5, 5, 3 and 7 deep, exactly for the row weights 36, 36, 36, 32, 32, 32, 8 and 72. The extended Hamming encoder shares far less than its syndrome, from 232 gates to 175, since no encoder mask is a 72-input parity row reusing almost every piece of the others. The Hsiao encoder goes from 200 to 159, so Hsiao keeps a 9.1 percent advantage there.
The decoder shares the most, because its 72 comparators all read the same eight syndrome bits. Each comparator is an AND of eight literals, a literal being a syndrome bit or its inverse. Four bits can be set only 16 ways, so 16 four-input ANDs over rows 0 to 3 and 16 over rows 4 to 7 can serve every comparator, each of which then needs one more AND, the trick a memory's address decoder calls predecoding. The 855 Hsiao gates of the hand count become 550 and the 923 extended Hamming gates become 478, 35.7 and 48.2 percent shared away.
Here the prediction reverses, as Figure 7 shows. By hand the Hsiao decoder is the smaller, 855 gates against 923. In the netlist it is the larger, 550 against 478, which is 15.1 percent more, because the extended Hamming syndrome shares so much more. What Hsiao keeps is depth. Its data output is 9 levels deep against 11, which is 18.2 percent fewer, and its corrected and uncorrectable outputs are 15 and 16 deep against 17 and 18, exactly the hand prediction for both codes. Sharing moves gates and leaves the longest paths where the lemma pins them, and the longest paths are what a read waits for.
One depth does differ. The Hsiao parity flag sits at 10 levels where the hand count says 9, because ABC built some XORs of two syndrome bits and as , two levels deep, to share those AND terms with the comparators. ABC is a heuristic, not a minimizer, so these counts belong to this recipe on this build, and only the separate trees are figures a proof pins down.
12.What the Numbers Mean for a Designer
Read latency is the number to watch, because every level on the path to the data output is added to every load. Hsiao's 9 levels against 11 are the reason to prefer it, and that reason survived synthesis. Whether 9 levels fit beside the memory access in one cycle depends on the process and the clock, which is why the chapter counts levels rather than picoseconds.
The flags are later than the data, at 15 levels for corrected and 16 for the no-match uncorrectable, because each waits for the OR of all 72 match lines. A design that must act on the flag in the cycle of the read can use the parity form, whose flag arrives at 10 levels, and accept that some words beyond the envelope pass unflagged, or it can register the flags and act a cycle later while the data goes ahead.
Area is paid per port. The Hsiao decoder is 550 two-input gates in this netlist and its encoder 159, and a memory with several read ports pays for a decoder at each. Where area matters more than latency, the netlist favors extended Hamming at 478 gates, which the hand count alone would have hidden. If the read path is too long for one cycle, a register after the syndrome stage splits it, and it holds only the 8 syndrome bits and the 64 received data bits the correction still needs.
13.Looking Ahead
Every check in this chapter stayed inside the envelope, and the code promises nothing outside it. The next chapter, Lab: Measuring Miscorrection, drives the same hardware with patterns of weight 3 and 4 and counts what it does. SECDED and Hsiao Codes predicted the answer for triple errors from the matrices alone. Of the 59,640 ways to choose three of the 72 positions, Hsiao miscorrects 33,568 and flags 26,072, and extended Hamming miscorrects 45,304 and flags 14,336. The lab samples triples on the hardware and checks the measured split against those counts, and the theorem of this chapter already says where the two forms of the flag must part, on the triples whose syndrome lands in .
14.Worked Examples
The syndrome of a pattern is the XOR of the columns it flips. Printed with first, position 0 holds and position 1 holds , so the syndrome is . It is nonzero with two ones, and every Hsiao column has odd weight, so no match line rises. Nothing is flipped and corrected is 0. The flag uncorrectable is 1 in the no-match form, since the syndrome is nonzero with no match, and 1 in the parity form, since its weight is even. The data output is with bits 0 and 1 flipped, which is as Equation 1 requires.
Position 70 holds the weight-1 column , so the syndrome is , with five ones. The weight-5 columns are the eight runs of five consecutive rows, counted around the eight rows as a circle, and rows 0, 1, 2, 3 and 5 are no such run, so the syndrome lies in and corrected is 0. The no-match form raises uncorrectable, since the syndrome is nonzero with no match. The parity form leaves it at 0, since the weight is odd, and the decoder hands out data with bits 0 and 49 wrong and no flag, which is silent corruption.
A check bit is the XOR of the data bits in its mask, which for the all-ones word is the parity of the mask's size. Every Hsiao mask holds 26 data bits, an even number, so all eight check bits are 0, printed , and the codeword is 64 ones followed by 8 zeros. The extended Hamming masks hold 35, 35, 35, 35, 31, 31, 31 and 7 data bits, all odd, so all eight check bits are 1, printed , and the codeword is 72 ones. The last exercise uses both facts.
Eight trees over 216 inputs in all lose one gate each, so , and . The comparators add , the correction 64, the OR for corrected 71, the OR of the syndrome bits 7 and the final AND 1, for . The depths are to the data, to corrected and 16 to uncorrectable. The netlist has 550 gates at exactly those depths, so the hand count overstates the gates by the 35.7 percent that sharing removes and gets every depth right.
15.Exercises
References
- [1]Hsiao, M. Y. (1970). “A Class of Optimal Minimum Odd-weight-column SEC-DED Codes.” IBM Journal of Research and Development, 14(4), pp. 395–401. doi:10.1147/rd.144.0395
- [2]Hamming, Richard W. (1950). “Error Detecting and Error Correcting Codes.” Bell System Technical Journal, 29(2), pp. 147–160. doi:10.1002/j.1538-7305.1950.tb00463.x
- [3]cocotb Project “Installation.” cocotb 2.1 documentation. Read 2026-11-14. https://docs.cocotb.org/en/stable/install.html
- [4]Verilator Project “Installation.” Verilator 5.054 documentation. Read 2026-11-14. https://verilator.org/guide/latest/install.html
- [5]YosysHQ “Installation guide.” SymbiYosys documentation. Read 2026-11-15. https://symbiyosys.readthedocs.io/en/latest/install.html
- [6]YosysHQ “Reference for .sby file format.” SymbiYosys documentation. Read 2026-11-15. https://symbiyosys.readthedocs.io/en/latest/reference.html
- [7]Brayton, Robert and Mishchenko, Alan (2010). “ABC: An Academic Industrial-Strength Verification Tool.” In Computer Aided Verification, pp. 24–40. doi:10.1007/978-3-642-14295-6_5
- [8]Bradley, Aaron R. (2011). “SAT-Based Model Checking without Unrolling.” In Verification, Model Checking, and Abstract Interpretation, pp. 70–87. doi:10.1007/978-3-642-18275-4_7
- [9]de Moura, Leonardo and Bjørner, Nikolaj (2008). “Z3: An Efficient SMT Solver.” In Tools and Algorithms for the Construction and Analysis of Systems, pp. 337–340. doi:10.1007/978-3-540-78800-3_24
- [10]YosysHQ “Installation.” Yosys documentation. Read 2026-11-14. https://yosyshq.readthedocs.io/projects/yosys/en/latest/getting_started/installation.html
— Anirban
Hardware–software at the seam where compilers meet microcode.