Coding Theory

Coding theory describes how symbols are represented, transmitted, and recovered. In a software system, “coding” can mean compression, an error code, a wire-level signal, or a framing convention. Those mechanisms interact, but they solve different problems.

Source Coding Versus Channel Coding #

Source coding represents the source with as few bits as its information content permits. A lossless compressor removes statistical redundancy and must reproduce the original bytes exactly; a lossy codec discards information according to an application-specific distortion model.

Channel coding adds structured redundancy before transmission or storage. The receiver uses that redundancy to detect corruption or correct it. A parity bit detects only some error patterns. A repetition code can correct errors by majority vote, but consumes substantial bandwidth. Hamming codes and modern block or convolutional codes provide more useful distance for the same overhead.

Compression and channel coding therefore have opposite bit budgets:

• compression reduces redundancy because the channel is assumed to be reliable;
• channel coding adds redundancy because the channel is assumed to be noisy.

Applying a compressor after an error-correcting code generally finds little redundancy. Applying error correction after compression is effective because the compressed stream still needs protection.

Hamming Distance, Redundancy, and Code Rate #

The Hamming distance between two equal-length bit strings is the number of positions in which they differ. The minimum distance d of a block code is the smallest distance between any two valid codewords. A decoder can always detect up to d - 1 bit errors, and a bounded-distance decoder can correct up to floor((d - 1) / 2) errors.

If a code maps k information bits to n transmitted bits, its code rate is R = k/n. The remaining n - k bits are redundancy. Increasing minimum distance normally lowers R, so an implementation chooses a rate and decoder that match the channel’s error model. A checksum or CRC also adds redundancy, but it is designed for detection rather than correction: a failed check says that the received message is invalid without identifying the original bits.

Line Codes and Transition Behavior #

Line coding maps bits to physical signal levels or transitions. It affects clock recovery, spectrum, and baseline behavior; it does not identify message boundaries and does not repair bit errors.

Nonreturn-to-Zero (NRZ) #

In an NRZ-level convention, one bit value selects one signal level and the other value selects another level for the complete bit interval. A long run of equal bits therefore has no transitions. The receiver must recover timing from a separate clock, a transition-rich encoding, or a rule such as bit stuffing.

“NRZ” can also describe transition conventions rather than one universal mapping, so a protocol specification must state its polarity and timing rules. An implementation must not infer the mapping from the name alone.

Nonreturn-to-Zero Inverted (NRZI) #

NRZI encodes one bit value as a transition and the other as no transition. A common convention, used by USB, is:

Other protocols reverse the bit meanings. NRZI is polarity-independent after the initial level is established, but it does not eliminate long transition-free runs: repeated “hold” bits still require a clocking rule. USB consequently uses bit stuffing. NRZI also does not provide framing, error detection, or error correction.

Keep the Layers Separate #

A robust link can contain all of these layers:

1. Physical signaling turns bits into voltages, optical symbols, or transitions.
2. Framing marks boundaries, addresses, and sometimes length fields.
3. Source coding compresses the payload.
4. Integrity checks such as CRCs detect accidental alteration.
5. Channel coding adds redundancy that permits detection or correction.

The layers have different failure modes. A transition rule cannot tell where a frame ends, a frame delimiter cannot correct a flipped payload bit, and a compressor cannot validate that bytes survived transport. Naming the layer explicitly prevents an NRZI, CRC, and Huffman code from being treated as interchangeable “encodings.”

References #

• C. E. Shannon, “A Mathematical Theory of Communication,” Bell System Technical Journal, 1948.
• R. W. Hamming, “Error Detecting and Error Correcting Codes,” Bell System Technical Journal, 1950.
• Universal Serial Bus Specification, Revision 2.0, sections on NRZI and bit stuffing.