Math 342 Homework 1.1 15 January 2015 This is an updated version of Homework 1, with clarifying material added to questions 1 & 3. 1 For each of the following codes, explain: • How many errors it can detect, if it is used to detect errors. • How many errors it can correct (assume maximum likelihood decoding). 1. {(1, 1, 0), (0, 0, 1), (2, 2, 2)}, q = 3 2. {(1, 0, 1, 0), (1, 1, 0, 1), (0, 1, 1, 0), (0, 0, 0, 1)}, q = 2 3. {(0, 4, 1, 3, 2), (4, 1, 3, 2, 0), (1, 3, 2, 0, 4), (3, 2, 0, 4, 1), (2, 0, 4, 1, 3)}, q = 5 2 Construct codes having the following parameters, or show that no such codes exist. 1. (3, 7, 1)2 2. (4, 5, 4)5 3. (4, 28, 2)3 3 Consider the binary symmetric channel with crossover probability p. Let C be the binary repetition code with word length 4, that is C = {(1, 1, 1, 1), (0, 0, 0, 0)}. What is the probability (in terms of p) 1. that a word will be miscorrected? Assume that we use Maximum Likelihood Decoding, so that for example (1, 1, 1, 0) will be corrected to (1, 1, 1, 1), whereas (1, 1, 0, 0) will be corrected to (1, 1, 1, 1) half the time and to (0, 0, 0, 0) the other half. 2. that an error will not be detected, that is, that a transmitted (1, 1, 1, 1) is received as (0, 0, 0, 0) or vice versa. 1 4 One kind of ‘hat problem’ is the following: n players are each wearing a hat which is one of c colours. The possible colours are known beforehand. The hat colours are assigned randomly so that each configuration of hat colours is equally likely. E.g. with 2 players, and two colours ‘black’ and ‘white’, the configurations (b, w), (b, b), (w, w) and (w, b) can each occur with probability 1/4. The players know what colour hat each other player is wearing, but do not know the colours of the hats they themselves are wearing. The players secretly and simultaneously write down a guess for the colour of their own hat: the allowed guesses are either a named colour or ‘abstain’. If all players write down ‘abstain’, or if any player writes down a wrong colour guess, then the game is lost. Otherwise, the game is won. The players may agree on a strategy before the game, but may not communicate during the game. 1. Show that with three players and two colours, there is a strategy that allows the players to win 3/4 of all games. 2. Suppose there are two players and three colours, {r , g , b}. Explain a strategy that allows the players to win more than 1/3 of all games. 2