EC-23.2 Block Codes: Hamming, Cyclic and Reed–Solomon

What this is and why it exists

A block code takes a fixed number of information symbols and produces a fixed number of transmitted ones.

The whole family is linear algebra over a finite field. That sounds forbidding, and it is what makes everything computable. Encoding is a matrix product. Decoding is looking up which error pattern produces the pattern you observed.

Cyclic codes then add one structural property, and that property turns the matrix operations into a shift register. This is why these codes are everywhere in hardware.

The vocabulary

• Linear code — one in which the sum of two codewords is another codeword.
• Generator matrix — the matrix that maps information into codewords.
• Parity check matrix — the matrix that gives zero for every valid codeword.
• Syndrome — the result of applying the parity check to a received word.
• Cyclic code — one where any rotation of a codeword is also a codeword.
• Generator polynomial — the polynomial whose multiples are the codewords.
• Symbol — a group of bits treated as one unit by the code.
• Shortening — omitting information positions to reduce the block length.
• Puncturing — not transmitting some parity positions to raise the rate.

The mental model

Three objects contain everything about a linear block code. The generator matrix turns information into a codeword. The parity check matrix gives zero for every valid codeword and something non-zero otherwise. And the minimum distance between codewords says how many errors can be handled.

Syndrome decoding is the key trick. Multiply a received word by the parity check matrix. Because the code is linear, the result depends only on the error pattern and not at all on what was sent. So one lookup table, from syndrome to most likely error, decodes everything.

The Hamming code is the smallest complete example. Place the parity bits so that the syndrome, read as a binary number, is the position of the single error. Add the parity, get the syndrome, flip that bit. It is still used inside memory chips, for exactly that economy.

Cyclic codes impose one extra rule: rotating a codeword gives another codeword. That turns the algebra into polynomial arithmetic, and a short shift register performs polynomial division directly. This is why cyclic codes dominate hardware implementations and why the same structure appears in every checksum you have met.

Reed-Solomon codes work with symbols of several bits rather than single bits. A run of consecutive bit errors then damages only one or two symbols, which is precisely what a burst channel produces. That is why this family appears in storage, in broadcast and on every optical disc.

Finally, practical fitting. Standard codes come in fixed sizes, and real systems rarely want exactly those. Shortening omits information positions; puncturing declines to transmit some parity. Both change the distance of the code, and by how much has to be checked rather than assumed.

What you should now be able to explain or do

• Encode a message using a generator matrix, by hand, for a small code.
• Compute a syndrome and explain why it depends only on the error.
• Explain how a Hamming code's syndrome locates a single error.
• Say what cyclic structure buys, and why shift registers implement it.
• Explain why symbol-based codes suit burst channels.
• Say what shortening and puncturing do, and what they cost.

Check yourself