Computer Networks Advanced

Parity Bits and Internet Checksum

A bit sent across a wire can arrive flipped. A voltage spike, a loose connector, or a burst of radio noise can turn a 0 into a 1 without any warning. The receiver sees a string of bits that looks perfectly valid, and it has no way to know that one of them is wrong. Error detection exists to close that gap. The sender adds a few extra bits that are computed from the data, and the receiver recomputes them. If the two results disagree, something went wrong in transit.

This chapter covers the simplest tools for that job. Parity bits are the oldest and lightest: one bit per chunk of data. Two-dimensional parity arranges the data in a grid and adds parity along both directions, so errors can be located as well as detected. The Internet checksum is the method IP, TCP, and UDP use to protect headers, and it trades strength for speed in software. Each method is cheap, and each has blind spots you can predict once you know how it works.

Single Parity Bit

A parity bit is one extra bit appended to a group of data bits. The rule is simple. With even parity, the sender chooses the parity bit so that the total number of 1s, data plus parity, is even. With odd parity, the total must be odd. Either rule works as long as both ends agree.

Take the byte 0110 1011. It contains five 1s, which is odd. For even parity, the sender appends a 1, giving 0110 1011 1, which has six 1s. The receiver counts the 1s in the nine bits it gets. An even count means the word is accepted. An odd count means at least one bit flipped.

Mathematically, the parity bit $p$ for data bits $d_1$ through $d_n$ is the sum of the bits modulo 2:

$$p = (d_1 + d_2 + \cdots + d_n) \bmod 2$$

This works because each flipped bit changes the count of 1s by one, and that always flips the parity from even to odd or back. The cost is one bit per group, which is cheap, but the method only tells you that something is wrong. It cannot say which bit to fix.

spec: static diagram of one byte with even parity. Top row shows eight data cells labelled 0,1,1,0,1,0,1,1 with the bit positions 7 down to 0 above them, and a ninth cell labelled P=1 at the right end, set apart in a different shade to mark it as the parity bit. Beneath, a caption line reads "Data 0110 1011 has five 1s; parity bit 1 makes the total six, which is even." Below that, a second row shows the same nine bits with the fourth data bit flipped to 1 and marked with an X, and a caption reading "One flipped bit leaves an odd count of seven, so the receiver detects the error."

Two-Dimensional Parity

Single parity has a weakness you can fix by adding structure. Put the data into rows, then compute a parity bit for each row. Then compute a parity bit for each column, including the row parity column, and add that as a final parity row. The result is a grid where every row and every column has even parity.

Suppose a single bit flips somewhere in the grid. Its row parity fails and its column parity fails. The receiver sees exactly one bad row and exactly one bad column, and the intersection of those two points to the flipped bit. The receiver can flip it back without asking for a retransmission. This is error correction, and it is the step beyond detection that single parity cannot take.

Here is a small grid of three data rows, four bits each. The rightmost column and bottom row are the parity bits.

Each row and each column has an even number of 1s. Now flip the bit in Row 2, Column 2. The row now has an odd count, and so does Column 2. The bad row and bad column pin the error to that one cell.

spec: static chart of a 4 by 5 grid of cells, with the three data rows and the parity column and row from the table: Row 1 = 1 0 1 1 | 1, Row 2 = 0 1 1 0 | 0, Row 3 = 1 1 0 0 | 0, and column parity row = 0 0 0 1 | 1. Highlight the cell at Row 2, Column 2 in red and label it "flipped bit", and mark the entire Row 2 and the entire Column 2 with a colored outline labelled "parity check fails here". Include a small caption: "One flipped bit fails exactly one row check and one column check, which identifies its position."

The Internet Checksum

Parity works bit by bit, which is slow when you have to run it over many bytes in software. The Internet checksum works on 16-bit words instead. The sender adds up all the words in the message using ones' complement addition, a form of binary addition in which any carry out of the top bit wraps around and is added back in at the bottom. The sender then flips every bit of the sum, which is the one's complement, and places the result in the header as the checksum.

The receiver repeats the addition over every word, including the checksum field. If nothing changed, the sum of the data plus the checksum comes out to all 1s, the largest possible value. Any other result signals an error. This is why the checksum is cheap: it uses ordinary addition, which processors do quickly, and it needs no lookup table.

Why wrap the carry? Plain addition would throw away a carry out of the top bit, and that lost bit is information. Wrapping keeps it. The same idea appears in IP, TCP, and UDP headers, and it is the reason the checksum can catch errors that cancel out in simple sums. The result is fast, but not as strong as the more careful methods used at the link layer, such as cyclic redundancy check (CRC).

spec: static diagram of an 8-bit ones' complement checksum example, shown as a vertical column sum. Line 1: word A = 0x4F = 0100 1111. Line 2: word B = 0xA2 = 1010 0010. Line 3: the raw sum 0x4F + 0xA2 = 0x111, with the leftmost bit marked as a carry out labelled "carry 1, wrap around". Line 4: the wrapped sum 0x11 + 1 = 0x12. Line 5: the checksum, the one's complement of 0x12, equal to 1110 1101 = 0xED. Then a receiver row: 0x4F + 0xA2 + 0xED with the intermediate sum 0x12 + 0xED = 0xFF, labelled "all 1s, accept". Use boxes for the values and arrows between steps. Caption: "Sender computes 0xED; receiver's total of all three values is 0xFF."

What Each Method Misses

Every detection method has a set of errors it cannot see, and knowing those sets matters more than memorizing the methods. An error goes undetected when the damaged bits still satisfy the rule the receiver checks.

Single parity misses any error that flips an even number of bits. Flip two bits in the same group and the count of 1s stays even, so the receiver accepts the corrupted data. It also cannot tell you which bit is wrong. It catches only the odd-count errors, which covers most single-bit noise but very little else.

Two-dimensional parity catches far more, but it has its own blind spot. Flip four bits that sit at the corners of a rectangle, say Row 1 and Row 3 by Column 1 and Column 3. Each affected row now has two errors, and each affected column has two errors, so every parity check still passes. The grid looks clean even though four bits are wrong. Any even-sized pattern that forms rectangles can slip through this way.

The Internet checksum is more forgiving about patterns but blind to different things. Because it is a plain sum, it cannot see the order of words. Swapping two 16-bit words leaves the total unchanged, so a reordering error goes unnoticed. Two errors that cancel in the sum are also invisible: one bit flipping from 0 to 1 at position 3 in one word and another bit flipping from 1 to 0 at position 3 in a different word can net to zero. The checksum is therefore a fast guard against random noise, not a guarantee of integrity. Where stronger protection is needed, CRC is designed to catch bursts and the cancellation patterns that these simpler methods miss.

AI-generated study article from SophistAI. Sign up free to study it with an AI tutor.