Bits flip on real links, so the sender adds extra bits that let the receiver notice — sometimes locate, and occasionally repair — the damage.
Words you will meet
-
Parity bit parity bit Simple One extra bit that makes the number of ones even, or odd. Precise In an even parity scheme the sender adds one bit so the total number of 1s in the d+1 bits is even. The receiver counts the 1s; an odd count means an odd number of bit errors occurred. An even number of errors goes undetected, and under burst conditions that probability can approach 50 per cent. introduced in ch. 6 — open in glossary — one extra bit that makes the number of 1s even, or odd.
-
Two-dimensional parity two-dimensional parity Simple Parity on every row and every column, so you can find the flipped bit. Precise The d data bits are laid out in i rows and j columns and a parity value is computed for each row and each column. A single bit error makes both its row and its column fail, so the receiver can locate and correct it. It can also detect, but not correct, any two errors. introduced in ch. 6 — open in glossary — parity on every row and every column, which locates a flipped bit.
-
Forward error correction forward error correction Simple Fix the error where it lands, without asking again. Precise The ability of a receiver both to detect and to correct errors. It reduces the number of sender retransmissions and, more importantly, allows immediate correction — avoiding a round-trip wait, which matters for real-time applications and for long-delay links such as deep-space links. introduced in ch. 6 — open in glossary — written FEC (Forward Error Correction) Forward Error Correction A receiver both detecting and correcting errors, without asking for a retransmission. Two-dimensional parity is the book's example. introduced in ch. 6 : repairing the error where it lands, without asking for a retransmission.
-
Cyclic redundancy check cyclic redundancy check Simple Divide the bits by an agreed number; the remainder is the check. Precise Sender and receiver agree on an r+1 bit generator G. The sender chooses r bits R such that the d+r bit pattern D·2^r XOR R is exactly divisible by G in modulo-2 arithmetic. The receiver divides by G and a non-zero remainder means an error. CRC codes are also called polynomial codes. introduced in ch. 6 — open in glossary — written CRC (Cyclic Redundancy Check) Cyclic Redundancy Check The error-detection code used in link-layer adapters. Sender and receiver agree on a generator G; the sender appends bits so the whole pattern divides by G with no remainder under modulo-2 arithmetic. introduced in ch. 6 : what link-layer adapters actually use.
-
Generator generator Simple The agreed bit pattern a CRC divides by. Precise An r+1 bit pattern G, whose leftmost bit must be 1, agreed by sender and receiver for a CRC. International standards define 8-, 12-, 16- and 32-bit generators; CRC-32 is used in several IEEE link-level protocols. introduced in ch. 6 — open in glossary — written
G: the agreed bit pattern a CRC divides by.
Why this matters
Section 3.3 built the Internet checksum and section 4.3.1 put one in the IP (Internet Protocol) Internet Protocol The network-layer protocol that defines the datagram format and addressing every Internet device must use. introduced in ch. 1 header. Both are weak, and the book said so at the time without saying what a strong one looks like.
This section says. It also answers a question the book planted two chapters ago. Why does the transport layer use a checksum and the link layer a CRC, when both detect the same kind of damage?
The answer is not about mathematics. It is about where each one runs, which is what section 6.1 established.
What the receiver can actually know
D is the data to be protected. It typically includes not only the datagram passed down from the network layer, but also link-level addressing information, sequence numbers and other header fields. EDC is the error-detection and -correction bits.
The book’s wording of the receiver’s decision is deliberate, and step 4 is why.
Read all steps as text
- The sender protects D with EDC — D is the data to be protected. It typically includes not only the datagram passed down from the network layer, but also link-level addressing information, sequence numbers and other header fields. EDC is the error-detection and -correction bits.
- Both cross a link that flips bits — Bit errors are introduced by signal attenuation and electromagnetic noise. Nothing in the link promises they will not happen.
- The receiver gets D′ and EDC′ — Both may differ from what was sent. Note that the error-detection bits themselves can be damaged — they cross the same link.
- And the question it can answer is narrower than you want — The receiver must decide whether D′ is the same as D, knowing only D′ and EDC′. The book asks whether an error is DETECTED, not whether an error has OCCURRED — and says the wording is important. These techniques let a receiver sometimes, but not always, notice that bit errors happened.
”Detected”, not “occurred”
The book flags its own wording, and it is worth slowing down for.
The receiver’s question is “is an error detected?” — not “did an error occur?” Error-detection techniques let a receiver sometimes, but not always, detect that bit errors have happened.
So a receiver may be entirely unaware that what it holds is corrupt. It might deliver a damaged datagram upward, or act on a damaged header field, believing both are fine.
The whole design goal is to make that probability small, not zero. And the usual price is overhead: a scheme with a smaller chance of missing an error needs more computation and more bits.
Parity: the smallest possible scheme
In an even parity scheme the sender adds one bit, chosen so the total number of 1s in the d + 1 bits is even. Odd parity chooses the other value.
The receiver simply counts the 1s. An odd count under even parity means at least one bit flipped — more precisely, it means an odd number of bits flipped.
The receiver counts the 1s in all 17 bits and finds 10, which is even. No error detected.
Click any data bit to flip it. Then flip a second one.
The book’s own bits. Click one to flip it, then click a second. The second flip is the lesson.
In plain words
Flip one bit and the count changes from even to odd, and the receiver knows.
Flip a second and the count is even again. The receiver sees nothing wrong.
If bit errors were rare and independent, two errors in one frame would be very unlikely and one parity bit might do. But measurements show errors are not independent: they cluster in bursts. Under burst conditions the probability that a single parity bit misses the damage can approach 50 per cent.
A coin flip is not error detection.
Two dimensions, and something new
Lay the d bits out in i rows and j columns, and compute a parity value for each row and each column. The i + j + 1 parity bits are the frame’s error-detection bits.
Now flip a single bit. Its row fails and its column fails, and no other row or column does. The receiver can use those two indices to find the corrupted bit and put it back.
Every row and every column agrees with its parity bit. Click any bit to flip it.
Row parity down the right, column parity along the bottom. Flip exactly one bit and the receiver can repair it. Flip two and it can only complain.
That ability — to detect and correct — is forward error correction forward error correction Simple Fix the error where it lands, without asking again. Precise The ability of a receiver both to detect and to correct errors. It reduces the number of sender retransmissions and, more importantly, allows immediate correction — avoiding a round-trip wait, which matters for real-time applications and for long-delay links such as deep-space links. introduced in ch. 6 — open in glossary . Two-dimensional parity can also detect any combination of two errors, though it cannot correct them.
Everyday picture
A spreadsheet where every row has a total in the right-hand column and every column has a total along the bottom.
Change one number by mistake and exactly one row total and one column total stop matching. You do not need to hunt: the two wrong totals cross at the cell you broke, and you can work out what the value should have been.
Change two numbers and several totals disagree, and they no longer cross at one place. You know something is wrong. You cannot say what.
Where the picture stops. A spreadsheet’s totals are much bigger than one digit, so they carry far more information than a parity bit, which is a single 0 or 1. Parity tells you only whether a count was odd — which is exactly why an even number of errors slips through.
Why forward error correction is worth its bits
FEC (Forward Error Correction) Forward Error Correction A receiver both detecting and correcting errors, without asking for a retransmission. Two-dimensional parity is the book's example. introduced in ch. 6 is used in audio storage and playback, and the book names audio compact discs. In networks it is used either alone or alongside link-layer ARQ (Automatic Repeat reQuest) Automatic Repeat reQuest The family of reliable protocols that recover from errors by retransmitting. Needs error detection, receiver feedback and retransmission (§3.4.1). introduced in ch. 3 techniques like the ones in section 3.4.
It has two benefits, and the second is the bigger one.
It reduces the number of retransmissions the sender must make.
It corrects the error immediately, at the receiver. No waiting a round-trip for a NAK (negative acknowledgement) negative acknowledgement A message saying that data arrived damaged and must be resent. Used by rdt2.1; removed in rdt2.2; TCP has none, and uses three duplicate ACKs instead. introduced in ch. 3 to travel back and a retransmission to travel forward. That matters for real-time applications. It matters enormously on links with long propagation delays — the book’s example is a deep-space link, where one round trip is measured in hours.
Checksums, and the question the book has been saving
In a checksumming method the d data bits are treated as a sequence of k-bit integers, which are summed. The Internet checksum does exactly this with 16-bit integers, and section 3.3 took it apart bit by bit.
| Internet checksumtransport layer | Cyclic redundancy checklink layer | |
|---|---|---|
| Runs where | ||
| And therefore must be | ||
| The arithmetic | ||
| Bits of overhead | ||
| Protection |
Cells marked ⓘ have a reason behind them — click to read it.
The book plants this question and answers it in one sentence. Everything else in the table follows. Click any cell.
In plain words
The answer is one sentence long, and it is not about which scheme is better.
The transport layer is software, so it needs something fast. The link layer is a chip, so it can afford something strong.
That is why the same job is done two different ways at two layers, and why neither choice is a mistake. Section 6.1 is what makes the argument work: without knowing the link layer is a network adapter, this looks arbitrary.
Cyclic redundancy check
CRC (Cyclic Redundancy Check) Cyclic Redundancy Check The error-detection code used in link-layer adapters. Sender and receiver agree on a generator G; the sender appends bits so the whole pattern divides by G with no remainder under modulo-2 arithmetic. introduced in ch. 6 codes are also known as polynomial codes, because the bit string can be viewed as a polynomial whose coefficients are its 0s and 1s.
The sender and receiver first agree on an r + 1 bit
generator generator Simple The agreed bit pattern a CRC divides by. Precise An r+1 bit pattern G, whose leftmost bit must be 1, agreed by sender and receiver for a CRC. International standards define 8-, 12-, 16- and 32-bit generators; CRC-32 is used in several IEEE link-level protocols.
introduced in ch. 6 — open in glossary
, G, whose leftmost bit must be 1. For a
piece of data D, the sender then chooses r additional bits R and appends
them. It chooses them so that the resulting d + r bit pattern is exactly
divisible by the generator, with no remainder, using modulo-2 arithmetic.
Error checking is then trivial: the receiver divides the d + r received bits by the generator. A non-zero remainder means an error; zero means the data is accepted.
R means something different here from anywhere else in this chapter
In this section R is the r CRC check bits — a bit pattern.
From section 6.3 onwards, R is the link rate of a shared channel, in bits
per second, and it turns up in expressions like R/N. That is five book pages
away.
The tell is the unit. If R is being divided or measured in bits per second, it
is a rate. If it is being appended to data, it is the CRC bits.
The arithmetic is exclusive-or
All CRC calculations are done in modulo-2 arithmetic, without carries in addition or borrows in subtraction. So addition and subtraction are identical, and both are the bitwise exclusive-or:
and equally 1011 − 0101 = 1110. Multiplication by 2^k left-shifts a pattern
by k places, exactly as in ordinary binary.
Where R comes from
The sender wants R such that D · 2^r ⊕ R = nG for some n. Exclusive-or R
onto both sides and that becomes
which says: divide D · 2^r by G, and the remainder is exactly R.
Step 6: the working bit at position 6 is 1, so G is XORed in there and the quotient gets a 1. Modulo-2 subtraction is exclusive-or, with no borrows.
The last 3 bits of the working value are 011 — that is R, the CRC bits. What goes on the wire is D followed by R:
101110011click a bit to damage it in flight
The receiver divides by G and gets remainder 000 — zero, so the data is accepted.
The book’s own D = 101110 and G = 1001, so d = 6 and r = 3. Step to the end and the nine transmitted bits are 101 110 011, exactly as the book prints them. Then click a bit to damage the frame in flight.
Check the book’s own numbers
The widget above runs the book’s Figure 6.7: D = 101110, so d = 6, and
G = 1001, so r = 3.
Step to the end and you should have quotient 101011 and remainder 011 — both printed in the book’s figure. The nine transmitted bits are then 101 110 011, which is exactly what page 460 says.
Then click any transmitted bit. The receiver’s division stops coming out at zero,
and it does so for every single-bit flip. tools/check-bitstream-ch06.mjs
tries all nine positions and all 49 possible bursts of up to 3 bits, and the
check catches every one.
What a CRC actually guarantees
International standards define 8-, 12-, 16- and 32-bit generators. CRC-32, adopted in a number of IEEE (Institute of Electrical and Electronics Engineers) Institute of Electrical and Electronics Engineers The body whose 802 committee standardises Ethernet and WiFi. introduced in ch. 1 link-level protocols, uses
G_CRC-32 = 100000100110000010001110110110111Thirty-three bits, so r = 32. Each CRC standard gives three guarantees.
- Every burst error of fewer than r + 1 bits is detected. All consecutive bit errors of r bits or fewer are caught, with certainty.
- A longer burst is detected with probability 1 − 0.5^r. For CRC-32 that is a chance of about one in four billion of missing one.
- Any odd number of bit errors is detected, however far apart they are.
Check yourself
Check yourself
0 of 7 answered1.The book asks whether an error is "detected", not whether an error has "occurred", and says the wording is important. Why?
2.predictA frame is protected by a single even parity bit. Two of its bits flip in transit. What does the receiver conclude?
3.With two-dimensional parity, one bit flips. What can the receiver do?
4.Why does the transport layer use a checksum while the link layer uses a CRC, when both detect the same kind of damage?
5.In CRC, how does the sender choose the r bits R?
6.In CRC arithmetic, what is 1011 − 0101?
7.CRC-32 uses a 33-bit generator, so r = 32. What does that guarantee?
What to remember
- The receiver asks whether an error is detected, not whether one occurred. These schemes can always be fooled; the goal is to make that rare.
- Two-dimensional parity locates a single error — its row and its column both fail — so it can correct it. That is forward error correction, and its real value is repairing the error immediately rather than waiting a round trip.
- A checksum sums integers; a CRC divides. The transport layer uses the first because it is software; the link layer uses the second because it is a chip.