You have come into possession of 8 bottles of “poison,” except, you’ve learned, 7 are fake poison and only 1 is really poisonous. Your master plan to take over the world requires you to identify the poison by tomorrow. Luckily, as an evil genius, you have a small collection of very expensive rats, which you can use for testing. You can give samples from bottles to multiple rats simultaneously (a rat can receive a mixture of samples from more than one bottle), and then wait for a day to see which ones die. Obviously you can identify the real poison with 8 rats (one bottle each), or even with 7 (one bottle each, one unused bottle; if all rats survive then the leftover bottle is the poison). But how many rats do you need to identify the poison? (Make the number as small as possible.)
Let c ∈ {0, 1} 23.
A handy fact (which you’ll show in Exercise 9.132, after we’ve developed the necessary tools for counting to figure out this quantity): the number of 23-bit strings c′ with ∆(c, c ′ ) ≤ 3 is exactly 2048 = 211 = 223−12. This fact means that (according to a generalization of Lemma 4.9) it might be possible to achieve the following code parameters:
• 12-bit messages;
• 23-bit codewords; and
• minimum distance 7.
In fact, these parameters are achievable—and a code that achieves these parameters is surprisingly simple to construct. The Golay code is an error-correcting code that can be constructed by the following so-called “greedy” algorithm in Figure 4.16. (The loop should consider the strings x in lexicographic order: first 00 00, then 00 01, then 00 10, going all the way up to 11 11. Notice that therefore the all-zero vector will be added to S in the first iteration of the while loop; a hundred and twenty-seven iterations later, 00000000000000001111111 will be the second element added to S, and so forth.)
