ESE 570
Coding Theory and Applications
Fall 2006

Problem Set 1

Due: Monday, September 18, 2006

Required Problems:

1. Blahut's book, Problem 1.8.

2. Blahut's book, Problem 1.9; the last line should have plus or minus the square root of n.

3. Blahut's book, Problem 1.10.

4. In this problem, you will write computer code to compute bit error rate capacity bounds. Assume binary inputs to the encoder.
Let C(x) be the capacity of a family of channels that function of the variable x, where x determines the reliability or quality of the channel. Thus, reliable communication (communication with probability of error tending to zero as the codeword length grows) is possible for all rates less than C(x). If a fraction of errors is allowed, then communication at higher rates is possible. Let p denote the fraction of errors allowed. This bit error rate can be achieved by first using a source encoder on the information bits to optimally compress them (using rate-distortion theory). This can be achieved with rate 1-h(p), where h(p) is the binary entropy function. The resulting bits can then be sent through the channel with no errors as long as R(1-h(p)) < C(x) where R is the rate of the code.
There are two equivalent representations of this. The first is R is less than C(x)/(1-h(p)). If C(x) is monotonically increasing with x, then the quality of the channel required is x is greater than C-1(R(1-h(p))).
a. Write a program to plot the achievable region for a binary input additive white Gaussian noise channel using a code of rate R. Generate two plots, one for each version of the bound. That is, one plot should have the BER versus the achievable rates for a fixed Eb/N0, and one plot should have BER versus Eb/N0 for fixed rate R. Use the CBIAWGN expression from our class notes.
b. Write a program to plot these same quantities for a binary symmetric channel (BSC). Assume that the crossover probability is q. Recall that C(q)=1-h(q).

5. For a (7,4) Hamming code, determine the BER as a function of the channel for both the BIAWGN channel and the BSC. For the BIAWN channel, obtain the curve by simulation at a variety of noise levels, using maximum likelihood decoding. The BSC curve can be found via simulation also. The word error rate can be found found analytically using the fact that the Hamming code only corrects one error. Compare the curves to the achievable bounds determined in the last problem.