Simulating Die Tossing and Coding for Binary Erasure Channels using MATLAB

Part 1 - Tossing Fair and Unfair Dice

1. (25 pts) Tossing a fair and unfair die. Suppose you have a 5-sided die, with sides numbered 1, 2, 3, 4, and 5.

(a) Write a MATLAB program to simulate the tossing of a 5-sided fair die (i.e., all sides are equally likely), for t =10, 50, 100, 500 and 1000 tosses. Based on the simulation, what is the estimated probability of obtaining an odd number?

(b) Suppose X is a random variable denoting the outcome of a die toss. Based on the mathematical analysis, what is the probability that X has odd value?

(c) Refer back to part (a). Does it agree with the theoretical result in (b)?

(d) Repeat parts (a), (b), and (c) with a 5-sided die that has the following properties:

• The probability of the die outcome being 1 is equal to the probability of the die outcome being 2.
• The probabilities of the die outcome being a 3, 4, or 5 are all equal.
• The probability of the die outcome being a 1 is twice the probability of the die outcome being 5.

You may find useful the MATLAB function rand that generates a uniform random value in the (0, 1) interval.

2. (25 pts) Coding for BEC In this problem, we consider the problem of transmitting bits over a binary erasure channel (BEC). The input bit X to the BEC channel is “0” or “1” with equal probability. The output of the channel Y is given where pe is called the erasure probability and the bits that become are said to be erased. Note that an observer of Y will know when a bit has been erased. We can summarize the communication channel as follows:
1
0
1
0

Input:X Output:Y
1 ? pe
pe
1 ? pe
pe

Clearly, if we send just one bit of information, the probability that the Output gets the Input is 1?pe. To improve the probability of successfully sending information through the BEC channel, we employ the ideas of redundancy and coding which turn out to be very powerful tools in solving such problems. Consider the following strategy of using the N-repetition code described in Lecture 5.

The N-repetition code takes a single bit that we want to transmit and repeats it N times (known as encoding). Now, each bit of the encoded N-bit sequence is transmitted through the BEC channel. Upon receiving this sequence, the receiver declares that the encoded bit is i) 1 if the received bit sequence has at least one 1, ii) 0 if the received bit sequence has at least one 0. If the received sequence has all erasures, the receiver declares that the encoded bit is undecodable. This process is known as decoding.

Consider the following example. Let N = 5 and suppose we want to transmit the bit

1. We first encode it into the sequence 11111, using the 5-repetition code. Suppose some bits got erased during transmission over the BEC channel, so that the receiver observes the sequence ????1. In this example, using the decoding method, the receiver would determine that the encoded bit for transmission was a 1. If the receiver observes the sequence, the receiver declares the encoded bit as undecodable.

(a) Write a program to simulate the BEC channel. Also, write programs for encoding and decoding the N-repetition code. We choose N = 3, 4 and 5 for this problem. For a given N, simulate 100000 instances of sending a bit through the BEC using the repetition code for pe = {0.125, 0.15, 0.175, · · · , 0.4}. Record the fraction of times (of the 100000) the receiver declares the encoded bit as undecodable for each pe. Denote the fraction by P
Rep
sim . Plot P
Rep
sim against pe for each N. You may want to use a semi-log for the y axis