please help me out
14:332:548, Error Control Coding Homework 4 Rutgers University 1. Let F be the ternary field GF (3) and let C be a linear code over F that is generated by G = ( 2 1 2 1 1 1 1 0 ) (a) List all the codewords of C. (b) Find a systematic generator matrix and a parity check matrix of C. (c) Compute the minimum distance of C. (d) A codeword of C is transmitted through noisy channel and the word y = (1, 1, 1, 1) is received. Find all the codewords of C that can be produced as an output by a nearest-codeword decoder for C when applied to y. (e) Suppose that the encoding is carried out by the mapping u −→ uG. A nearest-codeword decoder for C is applied to the word y in part (d) to produce a codeword ĉ. Denote by û the information word and that is associated with ĉ. Can any of the entries of û be uniquely determined – regardless of which nearest-codeword decoder is used? (f) Repeat part (e) for the case where a systematic generator matrix replaces G in the encoding. 2. Let C be a linear code over F = GF (2) with a parity check matrix H = 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 1 (a) What is the parameters n, k, and d of C? (b) Write a generator matrix of C. (c) Find the largest integer t such that every pattern of up to t errors will be decoded correctly by a nearest-codeword decoder for C. (d) A codeword of C is transmitted through an additive channel (F, F, Prob) and the word y = (1, 0, 1, 0, 1, 0, 1, 0, 1) is received. What will be the respective output of a nearest-codeword decoder for C when applied to y? (e) Given that the answer to part (d) is the correct codeword, how many errors does a nearest- codeword decoder correct in this case? And how is this number consistent with the value t in part (c)? 1 3. Show that the number of distinct generator matrices of a linear [n, k, d] code over F = GF (q) is∏k−1 i=0 (q k − qi). Hint: First show that the sought number equals to the number of k× k nonsingular matrices over F . Next, count the latter matrices 4. Let G be a k × k generator matrix of a linear code C ≠ {0} over a field F . Show that the minimum distance of C is the largest integer d such that every k × (n− d+ 1) sub matrix of G has rank k. 5. Let (a1, a2, ..., ak) be a nonzero vector over F = GF (q) and consider the mapping f : F k −→ F defined by f(x1, x2, ..., xk) = ∑k i=1 aixi. Show that each element of F is the image under f of exactly qk−1 vectors in F k. 6. (a) Let C be a linear (n, k, d) code over F = GF (q) and let T be a qk×n array whose rows are the codewords of C. Show that each element of F appears in every nonzero column in T exactly qk−1 times. Hint: Use Problem 5. (b) (The Plotkin bound for linear codes) Show that every linear (n, k, d) code over F = GF (q) satisfies the inequality d ≤ n(q − 1)q k−1 qk − 1 Hint: Using Part (a), start by showing that the average Hamming weight of the qk − 1 nonzero codewords in the code is at most n(q − 1)qk−1/(qk − 1). 7. (First-order Reed-Muller codes) Let F = GF (q) and for a positive integer m let n = qm. The first- order Reed-Muller code over F is defined as the linear (n,m+1) code C over F with an (m+1)×n generator matrix whose columns range over all the vectors in Fm+1 with a first entry equaling 1. (Observe that for q = 2, the first-order Reed-Muller code is the dual code of the extended Hamming code) (a) Show that the minimum distance of C equals q(qm−1) and this number is the Hamming weight of q(qm− 1) codewords in C. What are the Hamming weights of the remaining q codewords in C? Hint: Use problem 5 (b) Show that no linear (n,m+1) code over F can have minimum distance greater than qm−1(q− 1). Hint: Use the Plotkin bound. (c) The shortened first-order Reed-Muller code over F is defined as the linear (n − 1,m) code C′ over F with an m× (n−1) generator matrix whose columns range over all the nonzero vectors in Fm. Show that C′ can be obtained from C by a shortening operation that deletes the same single coordinate in all the codewords in C. (d) Show that every nonzero codeword in the shortened code C′ has Hamming weight qm−1(q− 1) and verify that the shortened code C′ attains the Plotkin bound. 2