Problem sheet 1 Jan 14th 2004

MT361 Error correcting codes

Ex. 1 (Exam question 1999) Define the term “binary symmetric channel with cross-over probability p”. Such a channel is used to send a message using one of two possible schemes as follows:- A. in single bits using a 3-repetition code, correcting any detected errors; B. in two bit words encoded with the addition of a check-sum bit, and requiring retransmission with any detected errors. For each of these schemes,

1. write down the complete code;

2. find the overall probability of accepting an error;

3. find the expected number of bits that have to be transmitted per message bit.

Calculate the above quantities for p = 0.01 and p = 0.1. Explain the relative merits of these methods under various circumstances.

Ex. 2 (Exam question 2000) Define the term “binary symmetric channel with cross-over probability p”. Such a channel is used to send a message using one of two possible schemes as follows:- A. using a 4-repetition code, and requiring retransmission as often as necessary when any errors are detected; B. using a 5-repetition code, correcting one received error but requiring retransmission as often as necessary when two errors are detected; For each of these schemes,

1. find the overall probability of accepting an error;

2. find the expected number of bits that have to be transmitted per message bit.

Calculate the above quantities for p = 0.01 and p = 0.1. Explain the relative merits of these methods under various circumstances. Suggest a possible scheme if retransmission is not possible.

Ex. 3 (Exam question 2001) Define the term “binary symmetric channel with cross-over probability p”. Such a channel is used to send a message using one of two possible schemes as follows:- A. in single bits using a 3-repetition code, correcting any detected errors; B. in three bit words encoded with the addition of a check-sum bit, and requiring retransmission with any detected errors. For each of these schemes,

1. write down the complete code;

2. find the overall probability of accepting an error;

3. find the expected number of bits that have to be transmitted per message bit.

Calculate the above quantities for p = 0.01 and p = 0.1. Explain the relative merits of these methods under various circumstances.

Ex. 4 (Exam question 2002) Explain precisely the statement “Σ is a ternary symmetric channel with probability of error p”. Such a channel is used to send a single bit message using a 3-repetition code. Write down the number of codewords and the total number of possible received words and determine the numbers of ways in which, for a given message, the received message may contain any number (from zero to three) of errors. Show that the above scheme can be used to correct one error but that two errors may result either (i) in incorrect correction, or (ii) in correction being entirely impossible. Show that each of these occurs with probability P = \frac{3}{2}(1 − p)p^{2}. If the code is used in this way, using retransmission as often as necessary when there are detected errors which cannot be corrected, find

1. the probability of correctly decoding the message the first time;

2. the expected number of bits that have to be transmitted per message bit;

3. the overall probability of accepting an error.

Ex. 5 (Exam question 2003) Define the term “binary symmetric channel with error probability p”. Such a channel is used to send a single bit message using one of three possible schemes as follows:- a. Using a 4-repetition code, correcting one received error but requiring retransmission as often as necessary when two errors are detected. b. Using a 5-repetition code, correcting one or two errors. c. Using a 5-repetition code, with no correction but requiring retransmission when any errors are detected.

For each scheme,

(i) Find the eventual probability of accepting an error

(ii) Find the expected number of bits that have to be transmitted per message bit. Calculate the above quantities for p = 0.1.

Compare the relative merits of these schemes, taking into consideration whether or not retransmission is possible on the channel.

Ex. 6 Suppose Bob wants to transmit single bit messages over a binary symmetric channel. He uses a repetition code of lenth 10. List the possibilities to use the redundant bits for schemes that detect and/or correct errors. (Up to how many errors can be detected? Corrected? Mixed forms of corrections and detections?)

Notes: (Not to be handed in.) Use induction to forecast the exam problem for 2004.

Hand in solutions to problems 1,4,5,6 (you do not need to repeat definitions or explanations) at the beginning of the lecture on Thursday 22nd January. I’ve put some books in the restricted loan section of the library (The ”cage” behind the loan desk.) Recommended reading is R. Hill: A First course in coding theory. (001.539 Hil) An electronic version of the problem sheets is available: http://www.ma.rhul.ac.uk/∼elsholtz/04mt361/lecture.html