February 2008 Puzzle Solution

1. As in the warm-up, you would need only one for a total of 101 bits. You could add an odd parity of bits 1, 21, 41, ...101. That is, arrange it so bits at those positions have an odd number of 1s. Any burst of 20 errors would have to overlap one of those bits, but no more than that. The burst would flip that bit, revealing an error.

2. You would need 111 bits. Add a bit that is the odd parity of all 100 message bits. This will detect bursts of consecutive length 1, 3, 5, 7, 9, 11, 13, 15, 17 and 19. Then add a bit that is the odd parity of 1, 3, 5, 7, ...101 (for bursts of length two). Now add a bit that is the odd parity of 1, 5, 9, 13, ...97, 101 (for bursts of length four). Keep going up to an odd parity on 1, 21, 41, ...101.

One can do even better, because the odd parity on 1, 3, 5, 7, ... will also catch errors of longer lengths. This solution is due to John A. Trono of Saint Michael's College.

Share this Article:


You must sign in or register as a member to submit a comment.

Email this Article