The parity trick that answers “exactly where?” and not just “something is wrong”
Why should you care?
Every frame crossing a cable or the air faces noise from interference, loose connectors or even a microwave oven. One flipped bit can turn a transfer of 100 into 900. The link layer’s first duty is to notice damage, and the receiver usually discards the frame and asks for a resend. On satellite or noisy wireless links, resending is slow and may fail again, so it would be better if the receiver could repair the damage itself. Two-dimensional parity shows that idea in its simplest form.
Step 0: the one-bit recap
In simple parity, the sender appends one extra bit so that the total number of 1s is even. If the receiver counts an odd number, it knows a bit has flipped. The scheme has two weaknesses that our course slides point out: two flipped bits cancel each other and slip through unnoticed, and even when a flip is caught, the receiver has no idea which bit went bad. Detection without location means no repair.
A quick illustration: the data 101010 has three 1s, so the sender appends a 1 and transmits 1010101. If noise flips two bits and the receiver sees 1111101, it counts six 1s, an even number, and wrongly accepts the frame.
The big idea: arrange the bits in a grid
Instead of guarding one long row of bits, write the data as a small table. Then protect it twice, once along every row and once along every column. It works like naming a cell in a spreadsheet: a row number and a column number together point to exactly one cell, so two failing checks reveal the damaged bit.
Why does this work? A single flipped bit changes the count in exactly one row and exactly one column, and in no other. Every bit sits at a unique row-and-column crossing, so the pair of failing checks narrows the error down to a single bit.
- Sender: arrange the data in rows, add an even-parity bit at the end of each row, add an even-parity bit under each column, and send the whole block.
- Receiver: recount every row and every column of the block that arrived.
- Decision: if every count is even, accept. If exactly one row and one column are odd, the bit where they cross is the culprit, so flip it back.
Figure 1. Row and column parity on a 4×4 block; the failing row 3 and column 2 expose the flipped bit.
Worked example, step by step
Take the four data rows 1011, 0110, 1100, 0001. Their row-parity bits are 1, 0, 0, 1(row one has three 1s, so we add a 1 to make four; row four has one 1, so we add another). The column-parity bits all come out as 0, and so does the corner bit. Now suppose noise flips the second bit of the third row from 1 to 0. At the receiver, row 3 now holds a single 1, which is odd, and column 2 also holds a single 1, which is odd. Every other row and column still has an even count. The receiver points at row 3, column 2, flips that bit back to 1, and the original block is restored without asking for a retransmission.
Notice what the receiver never needed: a second copy of the data. It only checked the rule “every row and every column must hold an even number of 1s”. That makes correction cheap to compute, just a few additions and one bit flip, which is why the idea is so easy to build into hardware.
What it can and cannot do
| Error pattern | Outcome |
|---|---|
| 1 bit flipped | Detected and corrected (row + column cross at the bad bit) |
| 2 or 3 bits flipped | Detected, but not correctable. Two errors at (1,1) and (2,2) leave the same failing rows and columns as two errors at (1,2) and (2,1), so the receiver cannot tell which pair is real |
| 4 bits at the corners of a rectangle | Slips through. Every affected row and column sees an even number of changes, so all parities still look fine |
| Burst of consecutive bits in one row | Usually detected (each column sees one change) but not repairable |
There is also a price. A grid with r rows and c columns needs r + c + 1 extra bits. For our 4×4 block that is 9 extra bits on top of 16, which is heavy. For an 8×8 block it is 17 on top of 64, about 27 percent. This overhead is why modern links such as Ethernet rely on a CRC to detect trouble and on retransmission to repair it, and keep heavier correcting codes for places where resending is painful.
Burst errors deserve a mention. Real noise often damages several neighboring bits at once. If a burst lands inside one row, the row parity may miss it (an even number of flips cancels), but each affected column sees one change, so the damage is still detected. Correction is impossible, however, which is why long bursts are the natural job of CRC.
Real-world case study: rebuilding a dead disk
The same “parity lets you recover missing data” principle runs inside the storage servers behind everyday cloud services. In RAID 5 (and its simpler cousin RAID 4), the system stores data blocks on several disks plus a parity block, calculated using XOR, which is just even parity applied bit by bit. If one disk dies, the controller already knows which disk is missing, so it XORs the surviving blocks to reconstruct the lost one. Figure 2 shows the idea with two data disks. Real RAID 5 rotates the parity block across all disks so that no single disk becomes a bottleneck.
Figure 2. Parity-based recovery, simplified.
One subtle point: this rebuild works because the failed disk is known. Recovering a known missing piece is easier than finding an unknown flipped bit, which is what the crossing in Figure 1 solves.
Two more places where the idea reappears: ECC memory in servers uses Hamming-style codes that locate and fix a flipped bit, much like our row-and-column crossing, and wireless or satellite systems use forward error correction so that receivers can repair small damage without waiting for a retry.
Try it yourself
Flip the **last data bit of row 1** in the example. Which row and column fail? Answer: row 1 and column 4.
Key takeaways
- Simple parity detects errors but cannot locate them.
- Two-dimensional parity corrects one flipped bit, detects up to three, and misses a four-bit rectangle.
- Correction costs extra bits, so real links combine CRC, retransmission and error-correcting codes.
- It also protects RAID storage and ECC memory.
References and further reading
- Course slides, Unit 5: The Link Layer, Computer Networks, SIT Pune. https://1drv.ms/p/c/70201b25f03037d4/IQA-NAtD0wsvTL8TOua3pPOdAaMoqMv5jX14hMvdmPymtTY?e=juVfWO
- Kurose, J. and Ross, K., Computer Networking: A Top-Down Approach, Pearson (link-layer chapter).
Top comments (0)