Block Codes: Hamming, Extended Hamming & Bounds

A block code accepts exactly $k$ information symbols, emits exactly $n$ channel symbols, and then starts again with no coding memory carried into the next block. The useful question is not merely how many parity bits it adds. It is which $2^k$ words are legal, how far apart those words are, and how a receiver turns a corrupted word into either a correction or an explicit failure.

This entry develops that mechanism for binary linear codes. It assumes the distance and rate concepts introduced in channel-coding basics, then makes them executable with matrices, syndromes, cosets, and a complete Hamming-code decode. Polynomial generators and the algebraic machinery of CRC, BCH, and Reed–Solomon codes belong to cyclic and BCH codes.

The fixed-block contract #

Linearity gives three practical simplifications:

• encoding is a matrix multiplication rather than a table of $2^k$ arbitrary words;
• checking is another matrix multiplication whose zero result characterizes every legal codeword;
• the distance between two codewords equals the weight of their difference, so $d$ is the smallest weight of any nonzero codeword.

The last point matters operationally. To establish $d$, a linear-code test examines $2^k-1$ nonzero codewords, not every pair of codewords. For large $k$ that exhaustive search is still impossible, so a real code family needs a proof, a structured distance algorithm, or a conservative bound rather than an unverified claim.

Generator and parity-check matrices #

Let the information row vector be $\mathbf u\in\mathrm{GF}(2)^k$. A full-rank $k\times n$ generator matrix $G$ encodes it as

$$\mathbf c=\mathbf uG.$$

A full-rank $(n-k)\times n$ parity-check matrix $H$ describes the same code as a null space:

$$C=\{\mathbf c:H\mathbf c^T=\mathbf 0\}, \qquad GH^T=0.$$

When the coordinate order is systematic, one convenient form is

$$G=\begin{bmatrix}I_k&P\end{bmatrix}, \qquad H=\begin{bmatrix}P^T&I_{n-k}\end{bmatrix}.$$

Over $\mathrm{GF}(2)$, subtraction and addition are both XOR, so the minus sign seen in the general-field formula disappears. The first $k$ codeword positions then reproduce $\mathbf u$ and the last $n-k$ positions contain parity.

A syndrome identifies an error coset #

Suppose the channel adds an error vector $\mathbf e$ and the receiver gets

$$\mathbf r=\mathbf c+\mathbf e.$$

The syndrome is

$$\mathbf s=H\mathbf r^T =H(\mathbf c+\mathbf e)^T =H\mathbf e^T.$$

The transmitted codeword vanishes from the calculation. The syndrome depends only on the error's equivalence class: two received words have the same syndrome exactly when their difference is a codeword.

flowchart LR
  U["message u"] --> E["encode c = uG"]
  E --> C["channel adds error e"]
  C --> S["syndrome s = Hrᵀ"]
  S --> L["choose coset leader ê"]
  L --> X["correct ĉ = r + ê"]

The $2^n$ possible received words split into $2^{n-k}$ disjoint cosets, one for each syndrome. A standard array writes the code itself as the first row, then one row for each translated set $\mathbf e+C$. A syndrome decoder stores one chosen coset leader $\hat{\mathbf e}$ per row and subtracts it—which is the same as adding it in binary.

Why choose the smallest-weight leader? On a binary symmetric channel where independent bit flips are less likely than correct bits, lower-weight error patterns are more probable. That is a maximum-likelihood rule for this channel model, not a theorem that the lowest-weight explanation is always physically right. Bursts, unequal bit reliabilities, and correlated memory faults require a channel-aware metric or an explicit interleaver/error model.

What minimum distance guarantees #

If a code has minimum distance $d$, then it can guarantee

$$\text{detection of up to }d-1\text{ errors}, \qquad \text{correction of up to } t=\left\lfloor\frac{d-1}{2}\right\rfloor\text{ errors}.$$

An erasure says which coordinate is unreliable; an error hides both its location and value. Mixed errors and erasures are uniquely correctable when

$$2t+e\le d-1,$$

where $t$ is the number of unknown-location errors and $e$ is the number of known erasures.

These are worst-case guarantees. A decoder may successfully correct some patterns beyond them, but it must not advertise that luck as code capability. Beyond the guaranteed radius, the same syndrome can have multiple plausible leaders, and a decoder can silently move the received word toward the wrong codeword.

Why the Hamming construction works #

Choose $m$ parity checks and form $H$ from every distinct nonzero $m$-bit column. There are $2^m-1$ such columns, giving the binary Hamming family

$$n=2^m-1, \qquad k=2^m-m-1, \qquad d=3.$$

A one-bit error in position $j$ has error vector $\mathbf e_j$, so

$$H\mathbf e_j^T=\text{column }j\text{ of }H.$$

Every column is nonzero, so no one-bit error has the zero syndrome. Every column is different, so no two positions produce the same syndrome. Equivalently, $H$ has no zero column and no pair of dependent columns, which excludes codewords of weight one or two and gives $d\ge3$. Some three columns do sum to zero, so $d=3$.

Hamming's familiar coordinate convention labels positions $1,2,\ldots,2^m-1$ by their binary numbers and uses those labels as the columns of $H$. Positions $1,2,4,8,\ldots$ hold parity; the remaining positions hold information. Reading the failed parity checks as a binary integer then returns the location of a single error directly.

The construction is perfect for one-error correction. Each codeword owns one no-error word plus $n$ possible one-error words, and

$$2^k(1+n)=2^{2^m-m-1}\,2^m=2^n.$$

The radius-one decoding balls fill the entire binary space without gaps or overlaps. This efficiency also creates the plain Hamming decoder's sharp edge: every nonzero syndrome already names a bit, so there is no unused syndrome left to say “this was a double error.”

Complete Hamming $[7,4,3]$ encode and correction #

Use positions $1,2,4$ for even-parity checks and positions $3,5,6,7$ for information. Let syndrome components $(s_1,s_2,s_4)$ correspond to parity-check weights $1,2,4$:

$$H= \begin{bmatrix} 1&0&1&0&1&0&1\\ 0&1&1&0&0&1&1\\ 0&0&0&1&1&1&1 \end{bmatrix}.$$

For message order $(c_3,c_5,c_6,c_7)$, a compatible generator is

$$G= \begin{bmatrix} 1&1&1&0&0&0&0\\ 1&0&0&1&1&0&0\\ 0&1&0&1&0&1&0\\ 1&1&0&1&0&0&1 \end{bmatrix}, \qquad GH^T=0.$$

Take

$$\mathbf u=(1,0,1,1).$$

The information positions are therefore $c_3=1$, $c_5=0$, $c_6=1$, and $c_7=1$. The even-parity equations give

$$\begin{aligned} c_1+c_3+c_5+c_7&=0 &&\Rightarrow c_1=0,\\ c_2+c_3+c_6+c_7&=0 &&\Rightarrow c_2=1,\\ c_4+c_5+c_6+c_7&=0 &&\Rightarrow c_4=0. \end{aligned}$$

Thus

$$\mathbf c=\mathbf uG=(0,1,1,0,0,1,1).$$

Now flip position 5 in transit:

$$\mathbf r=(0,1,1,0,1,1,1).$$

The receiver computes

$$\mathbf s=H\mathbf r^T=(1,0,1)^T.$$

Interpreting the components with weights $1,2,4$ gives $1+0+4=5$. The decoder flips received position 5, recovers $0110011$, verifies that its new syndrome is zero, and reads the information positions as $1011$.

Extended Hamming and SECDED #

Append one bit that makes the parity of the entire Hamming codeword even. Because all weight-three codewords had odd weight, their extensions gain one more nonzero coordinate; the result is

$$[2^m,\ 2^m-m-1,\ 4].$$

For $m=3$, Hamming $[7,4,3]$ becomes extended Hamming $[8,4,4]$: single-error correction, double-error detection (SECDED). Let $\mathbf s$ be the original $m$-bit Hamming syndrome over the first seven positions and let $q$ be the parity of all eight received bits.

The last row is the feature the unextended code lacked. Two errors preserve even overall parity but disturb at least one original parity equation, so the decoder detects rather than “corrects” them.

Puncturing the added overall-parity coordinate returns the original $[7,4,3]$ Hamming code. This is a useful sanity check: removing one coordinate can reduce distance by at most one, and here it reduces four to three.

Three bounds that answer different questions #

Let

$$V_2(n,r)=\sum_{i=0}^{r}\binom{n}{i}$$

be the number of binary words inside a Hamming ball of radius $r$. Let $A_2(n,d)$ be the largest possible number of length-$n$ binary codewords with minimum distance at least $d$.

For Hamming $[7,4,3]$, the sphere-packing calculation is exact:

$$2^4V_2(7,1)=16(1+7)=128=2^7.$$

That equality says the code is perfect, not that it has the largest possible distance for rate $4/7$. Singleton only gives $d\le7-4+1=4$, so it is looser here. The bounds bracket what parameters are possible; they say nothing by themselves about encoder wiring, decoder complexity, soft-decision performance, burst tolerance, or the probability of patterns beyond the guaranteed radius.

The linear Gilbert–Varshamov form is slightly sharper than the unrestricted greedy count. A sufficient existence condition for a binary linear $[n,k,d]$ code is

$$\sum_{i=0}^{d-2}\binom{n-1}{i}<2^{n-k}.$$

Treat “exists” literally. A randomly chosen matrix may have the promised distance with high probability at large block length while still being useless to an implementation that cannot search exponentially many codewords.

Shortening, puncturing, and extension #

These operations produce related lengths without redesigning everything, but they change different parts of the contract.

Shortening is not puncturing. A shortened encoder removes one degree of freedom and one transmitted coordinate; a punctured encoder normally removes only a transmitted coordinate. A receiver that inserts the omitted shortened bit in the wrong information position can produce valid syndromes and wrong payloads, making this an interoperability failure rather than an obvious decoder failure.

Implementation and interoperability checklist #

Write down the bit-exact code before optimizing XOR trees:

• exact $[n,k,d]$ parameters and whether “Hamming $(n,k)$” includes an overall parity bit;
• the complete $G$ and $H$, or normative parity equations from which both are generated;
• information, check, and overall-parity coordinate numbers, including serialization order and bit endianness;
• even- or odd-parity convention and the syndrome-bit significance order;
• every shortened, punctured, or fixed coordinate and the stage at which it is removed or reinserted;
• decoder policy for no error, corrected data, detected-uncorrectable data, and patterns outside the guarantee;
• whether corrected storage words are written back, merely corrected on the read path, or left for a separate scrubber;
• whether downstream logic receives invalid data alongside an error flag or the transaction fails closed.

A good implementation has one machine-readable source for the matrix and derives hardware, software, reference models, and tests from it. OpenTitan's current SECDED tooling is a concrete example: one configuration generates RTL encoders/decoders, C and SystemVerilog reference functions, testbench material, and formal-verification artifacts. Its OTP integration also distinguishes correctable and uncorrectable outcomes instead of reducing both to a single “ECC error” bit. That separation is part of the system contract, not an optional logging detail.

For extended Hamming $[8,4,4]$, exhaustive tests are small enough to be mandatory:

1. encode all 16 messages and verify $H\mathbf c^T=0$ plus even overall parity;
2. inject each of the 8 single-bit errors into every codeword and require exact payload recovery plus a corrected status;
3. inject all $\binom{8}{2}=28$ double-bit errors into every codeword and require an uncorrectable status with no attempted correction;
4. compare golden wire-order vectors across RTL, firmware, and a simple matrix reference;
5. inject representative three- and four-bit patterns to verify the documented failure policy, never an unsupported correction claim;
6. test shortened or punctured profiles at every frame boundary and reset condition.

The decoder should re-evaluate parity after a correction in verification builds. If that assertion fails on a nominal single-error test, the likely problem is not coding theory; it is a column order, parity convention, or syndrome-bit significance mismatch.

Scope boundary #

Hamming codes expose the core linear-block-code mechanism in its smallest complete form: a null-space definition, a syndrome, a coset leader, and a distance guarantee. Larger useful families add structure so that the same ideas remain decodable without a table that grows as $2^{n-k}$. Generator polynomials, cyclic shifts, finite-field roots, BCH designed distance, Reed–Solomon symbols, and their algebraic decoders are deliberately reserved for cyclic and BCH codes. Trellis memory and sequence decoding are instead covered by convolutional codes and Viterbi decoding.