CS 5

2

7 / ECE 599 Error Correcting Codes Assignment #5 Due
Friday February 28, 2020.

1. (q-ary codes for limited magnitude errors)

(a) For this problem assume that the symbols are over Z8 = {0, 1, 2, 3, 4, 5, 6, 7}.
Find the maximum number of non-systematic codewords with length
n = 2 that can correct any number of limited magnitude l = 3 er-
rors.

(b) (Systematic codes). Assume that the number of information digits
is k = 4 and the digits are over Z8. Find the number of check digits
required to correct all limited magnitude l = 3 errors.

(c) For the above systematic code, suppose the given information word
is (7246). Find the corresponding check digits.

(d) Assume the above codeword was transmitted and the received in-
formation word is (5134) and the received check digitds have −1
errors in all positions. Explain how the decoding is done.

2. A parity check matrix H contains r rows and n columns. The columns
of H have odd weight vectors of weight 1, 3, 5, etc. Note that n and r
correspond to the length of the code and the number of check bits. For
a given n the smallest r is chosen such that the total number of such
column vectors is equal to n.

(a) For n = 16 find the value of r and show the H matrix.

(b) Show that this code is capable of correcting single errors and de-
tecting double errors.

(c) Find the corresponding G matrix.

3. For the binary group code whose generator matrix is: 1 0 1 0 1 10 1 1 1 1 0
0 0 0 1 1 1

 ,
(a) Find the generator matrix G in the systematic form for an equiva-

lent code.

(b) Find the parity-check matrix H for the code in (a).

(c) Find the codeword that has 110 as information symbols. Show that
it is in the row space of G and in the null space of H.

4. (a) Find the parity check matrix in systematic form for a code over
Z5 capable of correcting single errors. Assume that the number of
information bits, k = 8.

(b) Find the generator matrix for this code.

(c) Suppose the given information word is (12041123). Find the corre-
sponding codeword.

(d) Suppose there is a single error in the fourth information digit which
changed from 4 to 2. Explain how error correction is done.

5. (Sphere Packing Bound for asymmetric errors) Show that any one asym-
metric error correcting code of length n can have a maximum of 2n/(1 +
n/2) codewords.

2