**
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
*E*_{b}/N_{0}, and one plot should have BER versus
*E*_{b}/N_{0} for fixed rate *R*. Use the
*C*_{BIAWGN} 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.