Was It Damaged?

You send Mira meet at 7, and she turns up at three. She is not early. She read your message, and it said meet at 3. You look at what you sent, and it said 7. Somewhere between your keyboard and her screen the seven became a three, and neither of you had any way of knowing.

This is the wire’s second defect, and it is subtler than the first. Take the character 7.

7 = 00110111

Now flip one bit, the third from the right.

3 = 00110011

One bit, a fraction of a microsecond of interference from a motor in the next building, and a seven is a three. There is nothing about 00110011 that looks damaged. It is a perfectly good character. It is only not the character you sent.

The wire does not do this often. On a decent wire in a quiet building you might send a hundred million bits between mistakes. But a hundred million bits is a few seconds of a video call, and rare is not never. Sooner or later a bit will flip, and when it does it will look the same as a bit you meant to send. You need Mira’s machine to be able to tell.

The first idea is the one everyone has. Send everything twice. If the two copies match, trust them; if they do not, something went wrong. This works, in the sense that it catches the flipped seven. It also doubles the cost of everything you send, forever, to guard against something that happens once in a hundred million bits. And when the two copies do not match, what then? You know that one of them is wrong, but you do not know which, so you had better send three copies and take the majority, and now you are spending three bits for every one you actually want to send.

There is a principle hiding in that objection, and it will govern every design choice in this chapter. The wire is almost always right. Whatever you add to catch its rare mistakes should be cheap, because you are paying for it on every frame, and most of those frames were fine. A scheme that triples your cost to catch a one-in-a-hundred-million event has the arithmetic backwards. What you want is something that costs a little on every frame and tells you, most of the time, when a frame is bad.

A much cheaper idea is this. For each byte, count the ones in it, and add a ninth bit chosen so that the total number of ones, including the new bit, is even.

7 = 00110111   five ones   → add a 1 → 001101111   six ones, even

Mira’s machine receives nine bits, counts the ones, and checks that the count is even. If a single bit has flipped, any bit, including the extra one, the count will be odd, and she knows.

received 001100111   five ones, odd   → damaged

This is called a parity bit. It costs one bit in nine, which is about eleven percent, cheaper than doubling, and it catches every single-bit error. It does not catch a two-bit error. Flip two bits and the count of ones goes up by two, or down by two, or one of each, and in all three cases it stays even.

sent     001101111
received 001111011   flipped two bits   six ones, even   → looks fine

Two flips in the same byte is a good deal rarer than one, but it is not rare enough. Interference on a wire does not come as isolated single-bit events. It comes in bursts, a spike that lasts long enough to corrupt several adjacent bits at once. Parity, which counts, is blind to any even number of flips, and bursts produce even numbers about half the time.

Still, you have learned something. You add a small amount of redundancy, information Mira could have computed herself from the content, and she uses it to check the content. The only question is what redundancy, and how much.

The per-byte parity bit has a second problem: it spends eleven percent on every byte, when you would rather spend a fixed small amount on the whole frame. So let us try that instead. Add up all the bytes of the content as numbers, keep the low byte of the total, and send that one byte at the end. Mira adds up the bytes she receives and compares.

m    e    e    t   ␣    a    t   ␣    7
6D + 65 + 65 + 74 + 20 + 61 + 74 + 20 + 37 = 2F7   → low byte F7

Flip the seven to a three and the sum drops by four. Mira gets F3, compares it to the F7 you sent, and knows. This is a checksum, literally a sum used to check, and for a frame of a few hundred bytes it costs one or two bytes. The overhead is now well under one percent, which is much better arithmetic.

But look for the hole. A sum does not care about position, and it does not care about balance. If one byte goes up by four and another goes down by four, the sum is unchanged.

sent     meet at 7
received meet et 3     a → e is +4,  7 → 3 is −4    same sum

That is a burst that happened to hit two bytes in complementary ways, and the checksum waves it through. It is uncommon, but you can see the shape of the weakness. The check is a single number that summarises the content, and there are a great many different contents that summarise to the same number. Some of them are one burst away from the content you actually sent.

Step back from the particular schemes and ask what property you are after. You want a function that takes the content and produces a short check value, such that any small change to the content, one bit, two bits, a burst of a dozen, produces a different check value. Not probably different, but different, for every change up to some size, and overwhelmingly likely to be different for anything bigger. You also want it to be sensitive to where a change is and not only to how big it is, so that complementary flips in two places do not cancel.

Such functions exist. The family the wire uses treats the entire frame as one enormous binary number and divides it by a carefully chosen constant, keeping the remainder. The remainder is the check value. The constant is picked so that the arithmetic has the properties you asked for: every single-bit and two-bit error changes the remainder, every burst shorter than the check value changes the remainder, and for a random large corruption the chance of the remainder happening to match is about one in four billion for a 32-bit check. The scheme was worked out by W. Wesley Peterson in 1961, and it has been on the end of frames ever since.

We are not going to derive that arithmetic here. It is a page in a textbook, a pleasing page, and it is also done entirely by the network card without your involvement; it belongs on the far side of the boundary we drew in Chapter 1. What matters is that you now know what to ask for, and that the thing you asked for is available at the cost of four bytes on the end of a frame. Its name is a cyclic redundancy check, and you will see it written as CRC.

The check goes at the end of the frame, after the content, for a practical reason. The sender can compute it as the bytes go out and append it when they are done, and the receiver can compute it as the bytes come in and compare when they are done. Neither side has to hold the whole frame before starting.

┌──────────────┬────────┬──────────────────────┬───────┐
│ start marker │ length │ content              │ check │
│  3 bytes     │ 2 bytes│ as many as length says│ 4 bytes│
└──────────────┴────────┴──────────────────────┴───────┘

loading…

The part after the content is called the trailer, to distinguish it from the header. Your frame now has a header, a payload, and a trailer, and that shape, bookkeeping, content, and more bookkeeping, will hold all the way up the tower.

What does Mira do with a bad frame? She throws it away. That sounds abrupt, so let us think about the alternatives. She could keep it and hope it is mostly right, but a frame with one flipped bit is as dangerous as a frame that is mostly wrong, because she cannot tell which bit, and the flipped bit might be the seven. She could try to guess what it should have been, but the check tells her that something changed and not what, so guessing is making up data. There is no honest option except to discard the frame and act as if it never arrived.

This raises a question worth sitting with. If Mira’s card discards a bad frame, Mira does not know she was sent anything. And you do not know it was discarded. From your side the frame went out; from hers nothing came in; and nothing in the tower so far has any way of noticing the gap. The seven-became-three problem is solved, in that Mira will never again act on a corrupted message, but it has been replaced by a quieter one. Sometimes a message vanishes, and neither of you finds out. We are going to leave that open. It is not a defect in what you built today; discarding is the correct behaviour, and the fix for the silence belongs several floors higher, once there is enough tower to build it on.

Coming up · I·11 — Putting It Back Together

A discarded frame is a message nobody knows went missing. Chapter 11 is about how the sender finds out, and what it does once it has.

→

There is a road we did not take, and it is worth walking a little way down it. Everything above detects damage and throws the frame away. But there is a stronger thing you could do. If you add enough redundancy, considerably more than four bytes, Mira’s machine can not only tell that a bit flipped but work out which bit, and flip it back. There is no discard, no gap, and no need to ask again.

The intuition is simple enough. Imagine writing your bytes out in a grid and computing a parity bit for every row and for every column. A single flipped bit will make one row and one column report odd, and the bit at their intersection is the culprit. You have located it. Flip it back and the frame is repaired. Schemes that do this properly, for more than one error at a time, are called error-correcting codes. Richard Hamming worked out the first of them at Bell Laboratories in 1947, after a relay computer that he could only use at weekends kept detecting an error, abandoning his job, and leaving him nothing to show for it on Monday. He wanted a machine that could fix the error and carry on, and a deep and lovely subject grew out of that irritation.

loading…

Your frames now know where they start, how long they are, and whether they arrived intact. Between Chapter 2 and this one the wire’s two defects have both been answered. They have not been eliminated, because the wire still does not know where anything begins and still flips the occasional bit, but they have been answered with agreements, so that neither defect can corrupt a message without being found out.

You have also begun to develop a sense of taste about agreements. They should be cheap on the common case, sensitive to the rare one, and placed where the machinery can handle them without bothering anyone above. That taste will serve you for the rest of the book. For now you have two machines and one wire, and upstairs a third neighbour is asking to join.