Core CS · Computer Networks

Six bits of data, three bits of proof

Q: Compute the even parity bit for 110101 and tell me exactly what that bit can and cannot catch.

There are four 1 s, which is already even, so the even parity bit is 0 and the codeword is 1101010 . It catches any odd number of bit flips, because each flip toggles the parity of the count. It is blind to every even number of flips, not only two: four flips and six flips sail through as well. That is the fatal weakness, and it is why nothing serious ships a single parity bit on its own.

A wire flips bits and never apologises. Parity catches an odd number of flips and is blind to every even number. Two dimensional parity finds the exact bit that changed. CRC divides your data by a fixed pattern and sends the remainder, and it is the one Ethernet actually uses. The same six bits go through all three.

Divide 110101000 by 1011, one XOR at a time →

One dataword carries the whole lesson. 110101 picks up a parity bit of 0, then a 2 by 3 grid of six check bits, then a CRC of 111. By the end you can say for each of them which errors it is guaranteed to catch and which ones walk straight past it.

01 The idea

Add bits that only agree with the data if nothing changed

A copper pair picks up interference from a motor down the corridor. A fibre run has a splice that scatters light. A radio link meets a microwave oven. In every case the receiver samples the medium and reads a 1 where the sender put a 0. Nothing about the received bits looks wrong. They are perfectly valid bits; they are not the ones that were sent.

So the receiver needs a way to ask a question the data cannot answer on its own. That is what redundancy is: the sender computes some extra bits from the data and sends them alongside, and the receiver recomputes them from what arrived and compares. If the two disagree, something changed in flight. The extra bits carry no information the receiver wanted. They exist purely so that a corruption has two things to break instead of one.

Be precise about what that buys you, because interviewers push on exactly this word. Detection tells you the bits changed. It does not tell you which bits, and it does not give you the original back. Correction rebuilds the original without asking the sender for anything. Correction is strictly more expensive: you need enough redundancy that every single corruption lands nearer to one valid message than to any other, and that costs many more bits than merely noticing that something is off.

Almost every link layer you will meet chooses detection. An Ethernet card that finds a bad frame discards it and tells nobody at all. Recovery happens further up, when TCP notices a gap in its sequence numbers and asks for the missing bytes again. That trade is deliberate: on a link where asking again is cheap, detect-and-retransmit costs far fewer bits than correct-in-place. Correction is reserved for links where asking again is impossible or ruinously slow, which is why it turns up in deep space probes and on optical trunks and not in your laptop’s network card.

Three schemes cover the whole syllabus, and they sit on a clean ladder of cost and strength: a single parity bit, a grid of parity bits, and a polynomial division called CRC. The Internet checksum sits alongside them as a fourth, cheaper option that the software layers use. This lesson runs one six-bit dataword, 110101, through all of them.

Send extra bits computed from the data. The receiver recomputes them from what it received. If the two do not match, the bits changed on the way, and the whole art is choosing a computation that a random corruption almost never satisfies by luck.

RedundancyBits sent that carry no new information, computed from the data so the receiver can recompute them and compare. All the cost of error control is here, and it is measured as check bits per data bit.

Dataword and codewordThe dataword is the k bits you actually want to send. The codeword is the k + r bits that go on the wire, where r is the number of check bits. Only some of the possible k + r bit strings are valid codewords, and that is what makes an error visible.

Detection and correctionDetection says the codeword that arrived is not a valid one. Correction says which valid codeword it must have been. Detection needs less redundancy, so link layers detect and discard and let a higher layer ask again.

02 Worked example

One dataword, three schemes, one remainder of 111

The dataword for this whole lesson is six bits: 1 1 0 1 0 1. It has four 1s in it, and that count is the only thing simple parity ever looks at. Every number below is small enough to check on paper in under a minute, and the CRC numbers reappear in the console in section 04 and in the cheat sheet.

Simple parity, and the hole in the middle of it

Under even parity the sender appends one bit chosen to make the total number of 1s even. Our dataword already has four, which is even, so the parity bit is 0 and the seven-bit codeword is 1101010. Under odd parity the rule is the mirror image and the bit would be 1. One check bit on six data bits is 14.3% overhead, which is as cheap as error control gets.

Flip one bit anywhere in that codeword and the count of 1s becomes odd, the check fails, and the error is caught. Now flip two. Take 110101, flip the third bit and the fifth bit, and you get 111111. That is six 1s, still even, so the parity bit 0 still agrees and the receiver accepts a dataword that shares only four of its six bits with what was sent. This is not an unlucky case. A single parity bit is blind to every even number of bit errors, all of them, because each flip toggles the parity and an even number of toggles returns it to where it started.

Two dimensional parity, and the intersection that names the culprit

Now arrange the same six bits as two rows of three, and compute an even parity bit for every row and every column, plus one corner bit that is the parity of the parity bits. Six data bits, six check bits, 50% overhead. The two blocks below are the same block, before and after a single flip.

sent row 11100two 1s, even, so the row parity bit is 0

sent row 21010two 1s, even, so the row parity bit is 0

col parity0110column 2 and column 3 each hold a single 1, so their parity bits are 1. The last box is the corner

got row 11100two 1s, matches the stored 0

got row 21110three 1s, odd, but the stored bit says even — row 2 fails

col parity0110column 2 now holds two 1s, even, but the stored bit says odd — column 2 fails

Exactly one row failed and exactly one column failed. There is exactly one bit that sits in both of them, and that bit is the one that changed. Flip row 2, column 2 back from 1 to 0 and the block is repaired. That intersection is the whole reason two dimensional parity can correct and simple parity cannot: one parity bit gives you a yes or no, while a row bit and a column bit together give you coordinates.

It has a limit, and it is a pretty one. Flip all four bits at the corners of a rectangle, here row 1 and row 2 crossed with column 1 and column 2, and every row still has an even count and every column still has an even count. Four flips, nothing detected. So the honest claim is: two dimensional parity detects any one, two or three bit errors, corrects any single one, and misses some four bit patterns.

CRC, which is division and nothing more

CRC treats the bit string as the coefficients of a polynomial and divides it by a fixed generator. The arithmetic is modulo 2, which means no carries and no borrows, so addition and subtraction collapse into one operation, XOR. Our generator is 1011, four bits, which is the polynomial x³ + x + 1. Its degree is r = 3, so the CRC will be three bits and never any other number of bits. Read the pipeline left to right.

DatawordThe six bits we want to send. 110101

→

Append r zerosr = 3, the generator’s degree. This shifts the data left to make room. 110101000

→

Divide by 1011Modulo 2 long division, XOR at every step. Six steps, five of them an actual XOR. Remainder 111

→

Send the codewordReplace the three zeros with the remainder. 110101111

→

Receiver dividesDivide all nine received bits by the same 1011. Clean means remainder 000

Three check bits on six data bits is 33.3% overhead, worse than parity and better than the grid, and it buys far more than either. Notice why appending the zeros works: shifting the dataword left by three positions and then subtracting the remainder produces a number that the generator divides exactly, and in modulo 2 arithmetic subtracting the remainder and appending it are the same operation. That is the trick in one sentence, and the console in section 04 does the division one XOR at a time so you can watch it.

The highlighted node is where every mark in an exam is won or lost, and it is also where students reach for arithmetic they already know and get it wrong. The next section says exactly what that division is and is not.

03 Mechanics

What each scheme costs and what it actually catches

Four schemes, the same six-bit dataword where it applies, and the claims stated as guarantees rather than as impressions. Read the last two columns together: a scheme is only as good as the specific error class it is guaranteed to catch, because a real link produces bursts and not tidy single flips.

Scheme	Check bits	On our 110101	Guaranteed to detect	Corrects	Cost to compute
Even parity	`1`	`1101010`, 14.3% overhead	`any odd number of flips only`	Nothing	One XOR of every bit. A single gate.
Two dimensional parity	`6` for a 2 by 3 block	12 bits sent for 6, 50% overhead	`1, 2 and 3 bit errors`	One bit, at the failing row crossed with the failing column	One parity per row and per column.
Internet checksum	`16`	Not applicable; it works on 16-bit words	`single-bit errors within a word`	Nothing	One add per 16-bit word plus a carry fold. Software.
CRC, generator 1011	`3`, always the generator’s degree	`110101111`, 33.3% overhead	`all single-bit errors, all bursts up to 3 bits`	Nothing	One shift and one conditional XOR per bit. Hardware.
CRC-32, Ethernet’s FCS	`32`, four bytes	4 of 1518 bytes on a maximum frame = 0.26%	`all bursts up to 32 bits`	Nothing	A 32-stage shift register in the network card.

Modulo 2 is XOR, and doing anything else is the classic wrong answer. In a CRC division there is no carry, no borrow and no notion of one number being larger than another. 1 − 0 = 1, and so does 0 − 1, because both are XOR. Two consequences follow and both are marked. First, you never ask “does 1011 go into this?” the way you would in decimal; you only look at the leading bit of the current window. If it is a 1 you XOR with the generator, and if it is a 0 you XOR with all zeros, which is a shift and nothing else. Second, the remainder always has exactly one fewer bit than the divisor, so a four-bit generator gives a three-bit CRC no matter what the data was. If your remainder came out four bits wide, you stopped one XOR early.

The Internet checksum, worked all the way through. RFC 1071 defines it as the 16-bit one’s complement of the one’s complement sum of the data taken as 16-bit words. Take two words, 0xE3AF and 0x4B29. Add them as ordinary integers: 58287 + 19241 = 77528 = 0x12ED8, which needs 17 bits. That 17th bit is the end around carry, and you add it back into the low 16: 0x2ED8 + 1 = 0x2ED9. Now take the one’s complement, which is flipping every bit: 0010 1110 1101 1001 becomes 1101 0001 0010 0110, or 0xD126. That is the checksum you transmit. The receiver adds everything including the checksum field, 0x2ED9 + 0xD126, and gets 0xFFFF — all ones. Complement that and you get zero, which is why you will hear the test stated both ways. Skipping the carry fold is the single most common error, and it changes the answer by exactly one.

Why the checksum is weak, and why it survives anyway. It is a plain sum, so any corruption whose effects cancel is invisible: two flips in different words that offset each other, or a word of all zeros inserted, or the words arriving in a different order, since addition does not care about order. Sixteen bits of state is also not much to hide a corruption in. It survives because it is a couple of adds per word in ordinary software, and because it can be updated incrementally: a router that decrements the TTL can adjust the IPv4 header checksum by patching in the difference rather than re-summing the header. IPv4 checksums its own header only and never the payload, TCP and UDP checksum their header plus the payload plus a pseudo-header built from the IP addresses, and IPv6 dropped the network-layer checksum entirely on the grounds that the link layer below and the transport layer above both check already.

What a CRC is guaranteed to catch, and the test you can do in your head. Four guarantees, each conditional on the generator. All single-bit errors, provided the generator has more than one term. All double-bit errors, provided the generator does not divide x^k + 1 for any k up to the frame length, which is exactly the condition that forces real generators up to degree 16 or 32. All odd numbers of bit errors, provided x + 1 is a factor of the generator — and you test that by substituting x = 1 and seeing whether the terms sum to zero modulo 2, which is the same as asking whether the generator has an even number of 1 bits. Our teaching generator 1011 has three, so x + 1 is not a factor and it does not carry that guarantee; the CRC-8 used by ATM, x⁸ + x² + x + 1, has four terms and does. And all burst errors of length r or less, where a burst means the run from the first flipped bit to the last. That last one is why CRC is the link layer’s choice: interference does not flip one tidy bit, it wipes a run of them, and a 32-bit CRC covers every burst up to 32 bits absolutely.

Hamming distance is the single idea underneath all four schemes. The Hamming distance between two bit strings is the number of positions where they differ, and the minimum Hamming distance of a code is the smallest distance between any two of its valid codewords. That one number sets both limits: a code with minimum distance d detects up to d − 1 errors and corrects up to (d − 1) / 2 rounded down. Simple parity has d = 2, so it detects one error and corrects none. Two dimensional parity has d = 4, so it detects three and corrects one, which is exactly what section 02 showed, and the invisible four-bit rectangle is the pair of codewords that are only distance 4 apart. Every scheme in this lesson is a different way of buying distance.

CRC is in the hardware because of the shape of the arithmetic. A CRC is one shift and one conditional XOR per bit, which is precisely a linear feedback shift register: r flip-flops with XOR taps wired at the generator’s set bits. It consumes the bit stream as it arrives at line rate, needs no buffer and no multiplication, and finishes on the same clock as the last bit. That is why Ethernet’s FCS is computed by the network card rather than the driver, and why it can be a trailer at the end of the frame rather than a field in the header. The Internet checksum cannot do that: it needs whole 16-bit words and a carry fold, which is a CPU operation on assembled data, so it lives in software one layer up.

05 Cheat sheet

The numbers and the claims they ask you to defend

Every row is something you can be asked to state or compute in under ten seconds. The right-hand column is the specific wrong answer that gets given, not a general warning.

What they ask	The answer	The trap
Detection versus correction	`detection says the bits changed, correction rebuilds them without asking again`	`saying CRC corrects errors — no CRC in this lesson corrects anything`
Even parity bit for 110101	`four 1s, already even, so the bit is 0 and the codeword is 1101010`	Computing odd parity when the question said even. Read the convention first.
What one parity bit misses	`every even number of flips: 2, 4, 6, all of them`	Answering “two-bit errors”. It is every even count, and that is a much bigger hole.
Two dimensional parity on a 2 by 3 block	`2 row bits + 3 column bits + 1 corner bit = 6 check bits on 6 data bits`	Forgetting the corner bit, or forgetting that it is the parity of the parities.
How it corrects	`one row fails and one column fails; flip the bit where they cross`	`claiming it corrects two errors — it corrects exactly one`
What it still misses	`four flips at the corners of a rectangle leave every row and column even`	Saying it detects everything up to three and stopping, without the counterexample.
Internet checksum recipe	`sum the 16-bit words, fold the end-around carry back in, one’s complement the result`	`skipping the carry fold — it changes the answer by exactly one`
The receiver’s checksum test	`add everything including the checksum field; the total must be 0xFFFF`	Expecting 0x0000. You get zero only after complementing that all-ones total.
CRC arithmetic	`modulo 2: XOR, no carry, no borrow, no comparison of magnitudes`	`doing decimal subtraction, or asking whether the divisor “fits”`
Our division, end to end	`110101 → append 000 → 110101000 ÷ 1011 → remainder 111 → send 110101111`	Sending the dataword and the remainder as ten or more bits. The zeros are replaced, not kept.
Width of the remainder	`always r bits, one fewer than the generator, whatever the data was`	Quoting 4 bits for the 4-bit generator 1011. A four-bit remainder means you stopped early.
Burst guarantee	`every burst of length r or less is detected, always`	Quoting it as r + 1. The burst is measured from the first flipped bit to the last.
Ethernet’s FCS	`CRC-32, 4 bytes, a trailer at the end of the frame`	`calling it a checksum — it is a division remainder, not a sum`
What a card does with a bad FCS	`discards the frame and notifies nobody; a higher layer notices the gap`	Claiming an error is reported back to the sender at layer 2 on Ethernet.

Redundancy is the whole mechanismAll four schemes send bits computed from the data. A corruption is invisible exactly when it leaves the data and the check bits consistent with each other, so the schemes differ only in how hard that is to hit by accident. A single parity bit is fooled by any even number of flips at all; a CRC has to be fooled into producing one exact remainder.

Detection is not correctionTwo dimensional parity is the only scheme here that corrects, and it corrects exactly one bit, using the row and column coordinates of the failure. Everything else detects and discards. The frame is recovered by a retransmission from a layer above, not by the layer that spotted the problem.

CRC is one XOR per bitWhich is why it is a shift register in the network card rather than code in the driver, why it runs at line rate with no buffering, and why the FCS can sit at the end of the frame instead of in the header. The arithmetic decided the hardware, and the hardware decided the frame format.

06 Where & why

Where these checks run on hardware you already use

None of this is exam furniture. Two of the four schemes are running on the machine in front of you right now, and one of them keeps a counter you can print.

Ethernet · IEEE 802.3

The FCS is a CRC-32 and nothing more

Four bytes at the end of every frame, computed by the network card over every byte before them. If the receiving card’s division does not come out to zero it drops the frame and tells nobody — no error frame, no negative acknowledgement, nothing. On the largest standard 1518-byte frame those four bytes are 0.26% overhead; on the smallest legal 64-byte frame the identical check costs 6.25%. The check also protects exactly one hop: a switch verifies the FCS, then computes a fresh one for the frame it sends onward.

Wi-Fi 6 · IEEE 802.11ax

Same CRC-32, completely different recovery

802.11 frames carry a 4-byte FCS with the same polynomial, but the air loses and corrupts far more frames than copper does, so Wi-Fi does not drop and forget. The receiver acknowledges every good unicast frame, and an unacknowledged frame is retransmitted at layer 2 before TCP ever notices. Same detection, retransmission moved down a layer, because the loss rate made end-to-end recovery too slow.

IPv4 and TCP · RFC 1071

The one’s complement sum you worked in section 03

The 16-bit field in an IPv4 header covers the header only, which is 20 bytes when there are no options, and never the payload. Every router recomputes it because the TTL changed on the way through. TCP and UDP use the same arithmetic over their header, their payload and a pseudo-header of the IP addresses. A UDP checksum of zero means “not computed”, so a genuine result of zero is transmitted as 0xFFFF instead — the two are the same value in one’s complement.

Linux · ethtool -S eth0

Your CRC failures are a live integer

ethtool -S eth0 prints per-driver counters including rx_crc_errors, and ip -s -s link show eth0 shows the same figure in its error breakdown. A count that climbs while traffic flows means frames really are being corrupted on that segment: a bad cable, a failing transceiver, or a duplex mismatch. It is the fastest way to prove a physical-layer fault instead of guessing at one.

Two sentences to be able to defend on the spot. Detection is cheap and correction is not, which is why almost every link layer detects, discards, and lets somebody else ask again. And a CRC is a remainder, not a sum, which is why it catches the bursts a sum cannot and why it fits in a shift register.

07 Interview questions

What they actually ask

Error detection is a favourite opener because it can be asked as pure theory or as a two-minute division on a whiteboard, and the same candidate often survives one and not the other. Expect to be handed a dataword and a generator and asked to produce the codeword out loud.

What is the difference between error detection and error correction, and which one does Ethernet do?

Detection tells you the bits changed; correction rebuilds the original without asking the sender for anything. Ethernet detects: the card checks the 4-byte FCS, and a frame that fails is discarded silently with no notification to anyone. Recovery happens further up, when TCP sees a gap in its sequence numbers and asks for the missing bytes again. Correction needs far more redundant bits than detection, so a link where asking again is cheap chooses detection every time.

Compute the even parity bit for 110101 and tell me exactly what that bit can and cannot catch.

There are four 1s, which is already even, so the even parity bit is 0 and the codeword is 1101010. It catches any odd number of bit flips, because each flip toggles the parity of the count. It is blind to every even number of flips, not only two: four flips and six flips sail through as well. That is the fatal weakness, and it is why nothing serious ships a single parity bit on its own.

Two dimensional parity can correct a single bit error. How does it know where the error is?

It gets coordinates instead of a yes or no. One parity bit per row and one per column means a single flipped bit breaks exactly one row check and exactly one column check, and the flipped bit is the only bit that sits in both. Flip the bit at that intersection and the block is repaired. A single parity bit cannot do this because it produces one failing check with no position information in it at all.

What is the Internet checksum, and how does the receiver test it?

Split the data into 16-bit words, add them as integers, fold any carry out of the top back into the low 16 bits, and transmit the one’s complement of that sum. The receiver adds every word including the checksum field with the same end-around carry, and the total must come out to 0xFFFF, all ones. Complementing that gives zero, which is why you will hear the test stated as “expect all ones” and as “expect zero” and both are right.

Why is the Internet checksum considered weak?

Because it is a plain sum, so any corruption whose contributions cancel is invisible: two flips in different words that offset each other, or bytes moving around in ways that do not change the total. It also only ever holds 16 bits of state. It survives because it costs a couple of adds per word in software and can be patched incrementally, which is exactly what a router needs when it decrements the TTL and must fix the IPv4 header checksum without re-summing the header.

Walk me through computing a CRC. Use 110101 with generator 1011.

The generator has degree 3, so append three zeros to get 110101000, then divide that by 1011 in modulo 2 arithmetic. The remainder is 111, and it replaces the three appended zeros, so the codeword transmitted is 110101111. The receiver divides the whole nine-bit received string by the same 1011 and expects a remainder of 000. Anything else means the bits changed and the frame is discarded.

Why is CRC division XOR and not subtraction?

Because the arithmetic is modulo 2, where there is no carry and no borrow, so addition and subtraction collapse into the same operation and that operation is XOR. It also means there is no notion of one number being bigger than another, so you never ask whether the divisor “fits”. You look only at the leading bit of the current window: a 1 means XOR with the generator, a 0 means XOR with all zeros, which is a shift and nothing more. That is what makes the whole thing a shift register.

What errors is a CRC guaranteed to detect?

Four classes, each conditional on the generator. All single-bit errors, if the generator has more than one term. All double-bit errors, if the generator does not divide x^k + 1 for any k up to the frame length. All odd numbers of bit errors, if x + 1 is a factor of the generator, which you test by substituting x = 1 and checking whether the terms sum to zero modulo 2. And all burst errors of length r or less, where r is the generator’s degree. That last one is why link layers use CRC: real interference wipes a run of bits, not one tidy bit.

Checksum versus CRC. Why does the Internet stack use both?

They sit at different layers and are optimised for different things. CRC is a division, catches every burst up to the length of the generator, and reduces to a shift register that runs at line rate on arriving bits, so it lives in the network card at layer 2. The checksum is a sum, misses anything that cancels, but costs a couple of instructions per word and can be updated incrementally, so it lives in software at layers 3 and 4. The other difference worth naming is coverage: the IPv4 checksum protects only the IP header, while the Ethernet FCS is computed over the entire frame including every byte of payload.

Why is CRC implemented in hardware and the checksum in software?

The shape of the arithmetic decides it. A CRC is one shift and one conditional XOR per bit, which is exactly a linear feedback shift register with taps at the generator’s set bits: it consumes the bit stream as it arrives, needs no buffer, and finishes on the same clock as the last bit. The Internet checksum needs whole 16-bit words and a carry fold, so it cannot start until the words are assembled in memory. That is also why the Ethernet FCS can be a trailer at the end of the frame and the IPv4 checksum has to be a field in the header.

Where does Hamming distance come into all of this?

Hard

The FCS is a 32-bit value. Argue from that alone what fraction of randomly corrupted frames pass the check anyway. Then: a store-and-forward switch sits between two hosts, and a memory fault inside it flips a bit after the switch has verified the incoming frame and before it builds the outgoing one. Explain why every FCS check on the whole path still passes, and use that to explain why TCP keeps a checksum of its own even though every single hop already runs a CRC.

Follow-up

Nothing here is a weakness in CRC-32, and widening the polynomial to 64 bits would not help at all. The first half is arithmetic; the second half is geography, and the two answers have nothing to do with each other.

Show the hint

Work out how many distinct FCS values exist, then treat a corrupted frame as producing one of them at random. For the second half, draw the path and mark every point at which an FCS is created and every point at which one is verified.