1999-2000
ACM North Central Regional Programming Contest
Problem 6
— Hamming It Up
If we wish to devise an information encoding scheme that permits us to detect errors, we need to add redundant information. Consider, for example, that we want to send one of four possible messages over a communication channel. Digitally, the most obvious way to do this is to associate the four binary codewords 00, 01, 10, and 11 with the four messages, and then send the appropriate codeword over the channel.
But what happens if noise or electrical problems during transmission cause one of the bits in a codeword to be changed? For example, suppose we sent the codeword 00 but it was received as 01. Is there any way the receiver of the codeword 01 can detect that it was really supposed to be 00?
R. W. Hamming, almost half a century ago, studied this problem. One measure of the ability of a set of codewords to support reliable communication is the Hamming distance of the set. The Hamming distance between any two codewords is the number of bit positions in which the codewords differ. For example, the codewords 10010 and 11000 differ in two bit positions (the second and fourth bits from the left), so the Hamming distance between them is 2. The Hamming distance of a set of codewords is just the minimum Hamming distance between any two codewords in the set. The Hamming distance for the set of codewords including 10010, 11000, and 11111 set would be 2 (since the Hamming distance between 10010 and 11111 is 3, and the Hamming distance between 11000 and 11111 is also 3). The Hamming distance of our original set of two-bit codewords 00, 01, 10, and 11 is 1, insufficient to even detect a 1-bit error.
In this problem you are to determine the Hamming distance for each of several sets of codewords. Each codeword in a set will be assumed to be 32 bits long, but will be represented in the input data as a signed decimal integer. For example, the set of codewords 00, 01, 10, and 11 (assuming a suitable number of leading zero bits) would be specified as 0, 1, 2 and 3 respectively. Likewise, the codewords 10010, 11000, and 11111 would be specified as 18, 24, and 31 respectively. If an input decimal integer is negative, then the corresponding codeword is the binary two’s complement representation of the number. There will be no more than 20 codewords in any set.
There will be multiple test cases in the input. Each test case begins with an integer n (2 £ n £ 20) specifying the number of codewords in the set. This is followed by n signed decimal integers giving the value of the codewords. A single 0 will follow the last test case.
For each input case, display the case number (these are sequential, starting with 1) and the Hamming distance for the set of codewords in that test case. Display the results in a format similar to that shown below.
4 0
1 2 3
3 18
24 31
2 1
–1
2 0
-1
0
Case 1. Hamming distance =
1.
Case 2. Hamming distance =
2.
Case 3. Hamming distance =
31.
Case 4. Hamming distance =
32.