error correcting
CS 527 / 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