February 1, 2008
1 min read
Add Us On GoogleAdd SciAmFebruary 2008 Puzzle Solution
By Dennis E. Shasha
On supporting science journalism
If you're enjoying this article, consider supporting our award-winning journalism by subscribing. By purchasing a subscription you are helping to ensure the future of impactful stories about the discoveries and ideas shaping our world today.
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.
It’s Time to Stand Up for Science
If you enjoyed this article, I’d like to ask for your support. Scientific American has served as an advocate for science and industry for 180 years, and right now may be the most critical moment in that two-century history.
I’ve been a Scientific American subscriber since I was 12 years old, and it helped shape the way I look at the world. SciAm always educates and delights me, and inspires a sense of awe for our vast, beautiful universe. I hope it does that for you, too.
If you subscribe to Scientific American, you help ensure that our coverage is centered on meaningful research and discovery; that we have the resources to report on the decisions that threaten labs across the U.S.; and that we support both budding and working scientists at a time when the value of science itself too often goes unrecognized.
In return, you get essential news, captivating podcasts, brilliant infographics, can't-miss newsletters, must-watch videos, challenging games, and the science world's best writing and reporting. You can even gift someone a subscription.
There has never been a more important time for us to stand up and show why science matters. I hope you’ll support us in that mission.
