CS 527 / ECE 599 Error Correcting Codes Assignment
Error Correcting Codes Assignment
CS 527 / ECE 599 Error Correcting Codes Assignment
1. (q-ary codes for limited magnitude errors, non-wrap error model)
(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 digits 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. This problem is related to single limited magnitude l error, where l can
be +1 or −1. Assume the digits are over Z7.
(a) If the number of information digits, k, is 8 then what is the mini-
mum number of check digits, r, required to do the error correction?
(b) Find the parity check matrix H in systematic form.
(c) If the given information word is 4222 1321, find the codeword.
(d) If the first digit of the information word is changed from 4 to 3 (i.e.,
-1 error) show how error correction is done.