Error Detection — Parity, LRC and CRC

Three ways to notice that a frame arrived damaged, and why only one of them is trusted in real hardware.

The idea

Signals get attenuated and picked up by noise. Bits arrive wrong. The data link layer’s job is to notice, so it can either ask for the frame again or throw it away — but either way not hand corruption upwards as though it were data.

The general shape of every scheme here is the same. Take k bits of message, add n − k redundancy bits, transmit n bits total. The redundancy is chosen so that most corruptions produce something the receiver can tell is not a legal codeword.

That gives the trade directly. The code rate R = k/n measures how much of what you send is real payload. More redundancy means better protection and less throughput. There is no scheme that gives you both.

The lecture is also careful about a point worth internalising: error detection is not 100% reliable. A protocol may miss some errors, though rarely. A larger redundancy field detects more. You are buying probability, not certainty.

Two kinds of error

Single-bit error — exactly one bit has changed.
Burst error — two or more bits have changed.

Bursts are what actually happens. A noise spike lasts longer than one bit interval, so it corrupts a run of them. Any scheme that only handles single-bit errors is solving the rare case.

The three methods

How it works

VRC, LRC and CRC

Parity, or Vertical Redundancy Check (VRC). One of the oldest and simplest. Add one bit per byte, chosen so the total number of 1s is even (even parity) or odd (odd parity).

The lecture’s example: the letter V in 7-bit ASCII is 0110101. That contains four 1s — already even — so with even parity the added bit is 0 and the transmitted codeword is 01101010.

The limitation is fatal and the lecture says so directly: if two bits are erroneous, parity checking will fail, giving about 50% reliability. Since real errors come in bursts, that is close to a coin toss.

Longitudinal Redundancy Check (LRC). Arrange the block of bits into rows and add a redundant row across the whole block. Now each bit position is covered by a parity bit computed down the column, as well as each row having its own. A burst that corrupts several bits in one row is caught by the column parity even when the row parity is fooled.

Better than VRC at exactly the case VRC fails on.

Cyclic Redundancy Check (CRC). Based on binary division. The data unit is divided by a predetermined divisor and the remainder becomes the CRC.

This is what real hardware uses — Ethernet and 802.11 WiFi both — and the rest of this page is about why.

Method	Redundancy added	Catches	Verdict
VRC (parity)	1 bit per byte	Any odd number of bit errors	Simplest, lowest reliability — about 50%
LRC	One extra row per block	Much more burst damage than VRC	Better than VRC, good for burst errors
CRC	(n − k) bits	All bursts shorter than (n − k) + 1 bits	Most powerful; detects most error patterns

This is the lecture's own three-way comparison, and it is a likely exam question in exactly this form.

How CRC works

How it works

Polynomial division, modulo 2

Any bit sequence can be written as a polynomial — 1011 is x³ + x + 1. CRC codes are cyclic, meaning any circular shift of a codeword is also a valid codeword, and every codeword is a multiple of one generator polynomial g(x).

That last property is the entire trick. If every legal codeword is a multiple of g(x), then dividing a received codeword by g(x) gives zero remainder when it is legal, and something non-zero when it is not.

To encode a message u(x):

Multiply u(x) by x^(n−k) — in bits, append n−k zeros
Divide by g(x) and take the remainder b(x)
The codeword is b(x) + u(x) — the message with the remainder appended

To decode a received v(x):

Divide v(x) by g(x)
Zero remainder means the message is correct
Anything else means there are errors

The generator has length (n−k)+1 and is known to both sender and receiver in advance. It is not transmitted.

Aside

The arithmetic is modulo 2: addition and subtraction are both XOR, with no carries and no borrows. That is not a simplification for teaching — it is why CRC is viable. XOR is a single gate, so the whole division runs in hardware at line rate, which parity-style schemes with real arithmetic could not do.

The lecture’s example

Worked example

u = 11001, divisor 11011

Append n−k zeros. The divisor 11011 is 5 bits, so n−k = 4. The dividend becomes 11001 followed by four zeros: 110010000.
Divide modulo 2. At each position, if the leading bit is 1, XOR with the divisor; if it is 0, shift and bring down the next bit. Step through it in the tool below rather than reading it here.
Remainder is 1101.
Codeword is message plus remainder: 11001 + 1101 = 110011101.
Check it. Divide 110011101 by 11011 and the remainder is 0000 — which is what the receiver will find if nothing was corrupted.

AnswerRemainder 1101, codeword 110011101

Where marks get lost

The lecture's k and n do not match its own example

The slide says “u = 11001, k = 4, and n = 7”, and both the encoder and decoder slides print Divisor 11011.

Those cannot all be true at once. A 5-bit divisor means n − k = 4, and with a 5-bit message that gives k = 5 and n = 9, not k = 4 and n = 7. Working it the other way — forcing k = 4, n = 7 — needs a 4-bit divisor and produces remainder 101, which is not the 1101 the slide shows.

So the arithmetic on the slide is right and the labels are stale. This page uses the divisor and remainder the lecture actually prints. If you tried to reconcile k = 4, n = 7 with the example and could not, you were not making a mistake.

Step through it

CRC divider

Try it

Data bits

Generator


Step	Position	Window	Operation	Result

Modulo-2 division: addition and subtraction are both XOR, no carries and no borrows. Step through one bit position at a time to see why.

Change the generator and watch the remainder length change with it — always one bit shorter than the divisor. Then take a finished codeword, flip one bit, and divide again: the remainder stops being zero, which is exactly what the receiver detects.

What CRC guarantees

Beyond “it usually works”, there is a real guarantee. With n − k redundancy bits, CRC detects all burst errors shorter than (n − k) + 1 bits.

So a 32-bit CRC — what Ethernet uses — catches every burst up to 32 bits long, with certainty. Longer bursts are caught with very high probability but not guaranteed.

That is the number to quote when a question asks why CRC is preferred: it is not just better on average, it has a hard guarantee that parity and LRC do not.

Check yourself

Three checks:

A CRC uses a 9-bit generator. How many bits is the remainder, and what burst length is guaranteed to be caught?
Why does the receiver not need to be told the generator polynomial in the frame?
Even parity, data 1011011. What is the parity bit?

Answers: 8-bit remainder, all bursts under 9 bits. The generator is agreed in advance by the standard — sending it would waste bandwidth and an attacker or a corruption could alter it. And 1011011 has five 1s, so the parity bit is 1 to make six.

In the exam

Compare VRC, LRC and CRC. The lecture’s own three-line summary — simplest and 50% reliable, better for bursts, most powerful — is the expected answer.
Perform a CRC division. Given data and a generator, produce the remainder and the codeword. Show the XOR steps; method marks live there.
Decode. Given a received codeword, divide and state whether it is accepted. Say “no error detected”, not “no error” — the lecture is explicit that detection is not 100%.
Encoding steps in order. Multiply by x^(n−k), divide by g(x), append the remainder. Worth memorising as three steps.
The burst guarantee. All bursts shorter than (n−k)+1 bits.
Code rate R = k/n, and the trade it describes.
Parity’s failure mode. Two flipped bits go undetected. Be able to construct an example.