Error Correction — Forward Error Correction and Hamming Codes

How a code can recover the original bits after an error, not just notice one, and the distance property that decides what a code can and cannot fix.

The idea

Error detection, from the previous topic, has a hard limit: it can only tell you something is wrong. Once a CRC check fails, the only move is to ask for the frame again — which costs a round trip, and on a link with real delay that round trip is expensive.

Forward error correction (FEC) does something stronger. It packs in enough redundancy that the receiver can work out what the original bits must have been and fix them itself, without asking for anything again.

The same shape from before still applies: k bits of message, n − k bits of redundancy, codeword of n bits. The code rate R = k/n is the same trade as always — more redundancy protects more, at the cost of throughput. What is different is what the redundancy buys: not just a flag that says “something broke,” but enough structure to say exactly what broke and undo it.

Detection vs correction

	What it needs from the receiver	What it delivers
Error detection (CRC, parity, LRC)	Nothing extra	A yes/no: is this codeword legal? A retransmission request follows if not.
Forward error correction	Extra redundancy, sized for the number of errors to fix	The original k bits, recovered directly — no retransmission needed.

Lecture 3's own comparison. Both spend redundancy bits; they spend them on different jobs.

FEC is what real systems reach for when a retransmission round trip is too costly to wait on. Lecture 3 names two live examples: Ethernet and 802.11 WiFi both use FEC in practice, and 5G NR uses LDPC codes for data transmissions and Polar codes for control channels — Polar codes suit the control channel specifically because it is very short, which is exactly the length regime Polar codes are strong at.

How much a code can detect, and how much it can correct

The slides do not develop Hamming distance, Hamming code construction or the syndrome beyond the general FEC idea above and the code rate. What follows is a standard, well-established piece of coding theory — not something Lecture 3 states directly — included here because a gap in the slides does not mean a gap in the exam.

How it works

Hamming distance

For two codewords of the same length, the Hamming distance between them is simply the number of bit positions where they differ. 1011 and 1001 differ in one position, so their distance is 1.

A code is a set of valid codewords. Looking at every pair of valid codewords and taking the smallest distance among them gives the code’s minimum Hamming distance, d_min. That single number decides what the code can guarantee:

To detect up to s errors, the code needs d_min ≥ s + 1.
To correct up to t errors, the code needs d_min ≥ 2t + 1.

The intuition for the correction bound: if two valid codewords sit 2t + 1 apart, an error pattern of up to t flips can move a codeword at most t steps — not far enough to reach a different valid codeword, so the receiver can still tell which one it started from and correct back to it.

Aside

This relationship is not specific to Hamming codes — it applies to any block code. Hamming codes are simply one well-known, simple example of a code built to hit d_min = 3.

A d_min = 3 code is a useful case to check the arithmetic on directly:

Correcting: 2t + 1 = 3 gives t = 1 — correct 1 error.
Detecting: s + 1 = 3 gives s = 2 — detect 2 errors.

Both are true of the same code, but not on the same error pattern at the same time. Spend the distance on detecting 2 errors and you are not also correcting them; spend it on correcting 1 error and a 2-bit error can slip past uncorrected.

Where marks get lost

Distance 3 does not mean 'correct 2 errors'

The most common way to lose marks here is reading d_min = 3 as “handles up to 2 errors” without asking whether that means detecting them or correcting them. Plug the number into both formulas separately: 2t+1 ≤ 3 caps correction at t = 1; s+1 ≤ 3 caps detection at s = 2. A code that actually corrected 2 errors would need d_min ≥ 5, not 3.

What the syndrome is doing

A Hamming code adds its redundancy as extra parity bits woven through the codeword, each one checking a different, overlapping group of positions. At the receiver, each parity check either passes or fails. The pattern of which checks fail — read together — is the syndrome, and for this construction it points straight at the position of a single flipped bit, with no lookup table required.

The exact rule for how many parity bits a given message needs, and precisely which positions each one covers, is not given in the slides and was not independently verified for this page, so it is not stated here as a formula. The mechanism is best built by experiment rather than by memorising an unverified rule:

Flip a bit, and watch which checks fail and what the syndrome becomes. Flip two, and see the syndrome point at the wrong position entirely — which is the concrete version of the distance-3 pitfall above: this code was built to correct one error, and two errors are enough to fool it.

Check yourself

Two checks:

A code has d_min = 7. What is the largest number of errors it is guaranteed to correct?
Why can a single code not both correct 2 errors and detect 2 errors using the same d_min?

Answers: 2t+1 ≤ 7 gives t ≤ 3, so it corrects up to 3 errors. And: because correcting t errors needs d_min ≥ 2t+1 while detecting the same count only needs d_min ≥ t+1 — correction is the more expensive guarantee for the same error count, so a distance that is only just enough to detect s errors is not automatically enough to correct that many.

In the exam

Detection vs FEC. FEC recovers the original k bits directly; detection only signals that something is wrong.
Code rate carries over. Same R = k/n trade as error detection — more redundancy, better protection, lower throughput.
5G NR codes. LDPC for data, Polar for control — because the control channel is short and Polar codes excel there.
The distance formulas. d_min ≥ s+1 to detect s errors; d_min ≥ 2t+1 to correct t errors. Not lecture content — standard coding theory, safe to use.
The classic trap. d_min = 3 corrects 1 error or detects 2 — never both on the same error pattern. Show the arithmetic, not just the conclusion.
The syndrome, conceptually. Which parity checks fail points directly at the bad bit position. The exact construction rule is not given here — this page will not hand you a number that was not checked.