Number of parity bit required

Question

I was reading about error detection and stumbled upon a statement which I didn't quite understand. The statement said "for a k bit string we need lg k parity bits to detect 2 bit errors".where lg is log to the base 2

I couldn't quite understand why this is true, is there any formal derivation that confirms this.

The name of the book is Data Networks by Gallahager.

Im not doubting what the book says, but am just curious enough to see a derivation.

Thanks, Chander

Answer 1

Have a look at the wikipedia page for Cyclic Redundancy Check. Strictly speaking a parity bit is a 1 bit check so talking about more than 1 parity bit is probably shorthand for the equivalent CRC. The article "Mathematics of CRC" gives more on the derivation.

Answer 2

terminology

• For "linear" codes (CRC, Hamming codes, etc.), each data bit always affects a fixed set of some (but not all) of the parity bits. For example, if (only) bit 7 of the data is flipped in transit, and that flips parity bits 2 and 4 but not parity bit 5 -- in the recalculated parity bits, compared to the as-received parity bits -- then flipping bit 7 of the data will flip parity bits 2 and 4 but not parity bit 5 for every possible frame of payload data bits.
• All the bits in the payload that affect a particular parity bit (such as parity bit 5), and that parity bit itself, are said to be "covered" or "protected" by that parity bit.

• When the receiver re-calculates the parity bits, and compares the re-calculated parity bits with the received parity bits, the difference is called the syndrome. When there were no errors, the syndrome is zero.

  In other words, syndrome = recalculated_parity XOR recieved_parity.

Proof

A proof that n parity bits are required to detect 2 bit errors in a 2^n bit frame of payload data bits:

When there is only 1 error in the entire frame, when the receiver re-calculates the parity bits, there are two cases:

• Each recalculated parity bit that does not cover the erroneous bit is the same as the corresponding received parity bit. (The corresponding bit in the syndrome is "0").
• Each recalculated parity bit that covers the erroneous bit is different from the corresponding received parity bit, and the error is detected. (The corresponding bit in the syndrome is "1").

When there is exactly 2 errors in the entire frame, the resulting syndrome is the XOR of the syndrome caused by each error in isolation. When the receiver re-calculates the parity bits, there are 3 cases:

• (a) Each recalculated parity bit that does not cover either erroneous bit is the same as the corresponding received parity bit. (The corresponding bit in the syndrome is "0").
• (b) Each recalculated parity bit that covers both erroneous bit is the same as the corresponding received parity bit. (Each error flips such a bit once, and both flips combined return that bit to the original state, so the corresponding bit in the syndrome is "0").
• (c) Each recalculated parity bit that covers one erroneous bit, and does not cover the other erroneous bit, is different from the corresponding received parity bit, and the error is detected. (The corresponding bit in the syndrome is "1").

If, hypothetically, there existed some payload bit such that flipping it produces some syndrome S, and there is any other payload bit that produces exactly the same syndrome S, then a two-bit error that hit both of those bits would be undetectable. In other words, that two-bit error would give syndrome of S xor S == zero. In other words, each parity is either case (a) or case (b), neither of which can detect such an error. That would be bad.

So in order to detect every possible two-bit error in the frame, we must design the error-detection code such that each single-bit error must produce a different syndrome. In other words, there must be at least 1 parity bit of type (c) for every possible case of two erroneous bits in the frame.

Using n parity bits gives n syndrome bits. With n syndrome bits, there are at most 2^n possible different syndromes. So to make sure that each bit in the frame (when it is the only error) gives a different syndrome, we must have at most 2^n bits in the frame.

I bet if you posted this question on https://math.stackexchange.com/ you'd get a much shorter and more elegant proof :-).