Dual code:-

Referring to exercise 8, find the dual code of the code with words 0000, 0110, 1001, 1111.

(The famous hat problem*) Recently there has been wide fascination among coding theorists with the hat problem: Suppose there are n people in a room, and each is given either a red or blue hat. The hat colors are determined by n separate coin flips. People can see everyone's hat except their own. Next, each person in turn must either guess the color of his or her hat or must pass. The group of n people will win $1 million if at least one person guesses correctly and no one guesses incorrectly. The group is able to agree on a strategy before the hats are assigned. What is the probability that the group wins, and how is that probability achieved? (The usual first reaction is that this probability is one-half-which is incorrect.)

(a) First consider n = 3. Suppose each person responds as follows: if the other two hats are the same color, then the person guesses the opposite color. If the other two hats are different, the person passes. Everyone passes after one person guesses. What is the probability of the team winning? Hint: Consider the number of possible hat color configurations, and the number of these for which the team will lose.

(b) What is the ratio the number of code words in a Hamming code of length 3 to the total number of possible words of length 3?

(c) Suppose n = 7. Consider the strategy whereby each person determines whether there is a choice of his or her hat color that in conjunction with the others would form a code word in an (n, M, d)-(7, 16, 3) Hamming code (using 0 for red and 1 for blue). If there is such a choice, the person guesses the opposite color; if not, he or she passes. What is the probability of winning in this case?