Solution to Last Month's Dr. Ecco
Solution to "Jam Session," DDJ, April 2005.
1. We represent the 6 data bits followed by 4 check bits as follows:
b1 b2 b3 b4 b5 b6 c1 c2 c3 c4
Here is one possibility of what the check bits could do:
c1 is odd parity on b1, b2, b3, b4, b5, b6, c1, c4
c2 is odd parity on b1, b2, b3, b4, c3, c2
c3 is odd parity on b1, b2, c1, c3, c4
c4 is odd parity on b1, b5, b4, c4
The trick is to locate the parity tests that don't work if any bit has been flipped and to make sure these are all different. If all the parities are correct, then no single bit has been flipped. If there is an error in b1, then the parities corresponding to c1, c2, c3, and c4 will all be bad.
Error in b2, then c1, c2, and c3 will be bad.
b3: c1, c2.
b4: c1, c2, c4.
b5: c1, c4.
b6: c1
c1: c1, c3
c2: c2
c3: c2, c3
c4: c3, c4.
2. If you know the offset between the bit flip to the first receiver and to the second is an odd number, then you can use:
b1, b2, b3, b4, b5, b6, b7, b8, Podd, Peven
where Podd ensures that there are an odd number of 1s among b1, b3, b5, b7, Podd and Peven ensures that there are an odd number of 1s among b2, b4, b6, b8, and Peven. Here is why this works: If no error is detected, then the data bits are correct. If the first receiver detects an error, say for Podd, then the second can detect an error only for Peven because of the odd offset. Therefore, one of the two receivers will receive an error-free Podd group and and an error-free Peven group.
3. If you know the offset is 4 bits, then Ivan Rezanka showed how 3 check bits are enough. First note that with an offset of 4, the bits that could flip are bit 1 for the first receiver and bit 5 for the second—denoted (1,5)—or (2,6), (3,7), (4,8), (5,9), (6, 10), (7,1), (8,2), (9,3), or (10,4).
Here is a three check bit solution:
b1 b2 b3 b4 b5 b6 b7 c1 c2 c3
c1 is odd parity on b1, b4, b6, b7
c2 is odd parity on b2, b4, b5, b7
c3 is odd parity on b3, b4, b5, b6
If all parity bits check out for either receiver, we are done. If some pair changes, we detect as follows: If bit 1 to the first receiver and bit 5 to the second is flipped then c1 for the first receiver and c2 for the second will be incorrect. We denote this by (c1, c2). Note that when merging these two signals, the reconstructor must recognize this ordering. So, we abbreviate this first situation as follows:
(1,5) -- (c1, c2, and c3)
and continue as follows:
(2,6) -- (c2, c1 and c3)
(3,7) -- (c3, c1 and c2)
(4,8) -- (c1 and c2 and c3, c1)
(5,9) -- (c2 and c3, c2)
(6,10) -- (c3, c3)
(7,1) -- (c1 and c2, c1)
(8,2) -- (c1, c2)
(9,3) -- (c2, c3)
(10,4) -- (c3, c1 and c2 and c3)
Note that each diagnostic is different.
