Coding Theory

First Assignment: due Fri. Feb. 9

  1. In this problem we compare the performance of several codes of length 30 assuming the same channel we used in class for codes of length 14. We have q = 10^(-7) and a transmission rate of 10^7 bits /sec.

    a. Find the code rate, word error rate and number of word errors per year for the following codes (use 32 * 10^6 secs/year). Comment also on the need for retransmission.

    b. How does the added length (30 vs. 14-15 in class) seem to have affected performance?

  2. This is a study of incomplete maximum likelihood decoding (IMLD) for a non-linear code: Consider the code of length 5 with codewords 00000, 11100, 01110, 00111.

    a. Construct an IMLD table showing for each possible received vector the codeword to which it is decoded (if there is a unique closest codeword).

    b. Find L(00000), the list of codewords decoded to 00000. Find L(11100) and L(01110) also.

    c. Assume codeword 00000 is sent, for each error vector of weight 0, 1, 2 identify whether the error is c) corrected, d) detected, or f) falsely corrected (miscorrected). Do the same for codewords 11100 and 01110.
    Which error vectors can be corrected by the code (independently of which codeword is sent)?

    d. Suppose that the codeword 00000 is sent over a reasonably good channel (q < 10^(-3)). The probabability of more than 2 errors occurring is then very small, so we can approximate the performance of the code using the data in the table from part c. Compute, as a function of p, for 00000 the probability of c) correction, d) detection, and f) false correction. Do the same for 11100 and 01110.

    e. Suppose q=1-p = 10^(-4). Evaluate and tabulate your results in d.

    f. Comment on the results in d. and e.

    g. Suppose we use a less aggresive correction procedure, correcting only if the received vector is a distance 0 or 1 from a codeword. How would this change the performance? That is, what would be the probabilities for correction, detection, and false correction? Evaluate for arbitrary p, and then for q = 1-p=10^(-4).