PLEASE HELP ME OUTAQ
14:332:548, Error Control Coding Homework 5 Rutgers University 1. RAID 4 (redundant array of independent disks) uses (4, 2) RS code over GF (5) to store a file re- dundantly on 4 disks. Namely, the file represented by the data vector u = (u1, u2), is encoded into a codeword c = (c1, c2, c3, c4) = uG, where G is the generator matrix of the RS code; and every entry of c is stored on a separate disk. (a) Give the generator matrix G of this code. (b) In practice, a systematic version of the code is used to allow easy access to the data. Find Gs, the generator matrix of the systematic version of this code (by doing row operations on G). (c) Find the parity check matrix Hs of this code corresponding to Gs. (d) Suppose that the disks storing the systematic data fail and we read the remaining disks c3 = c4 = 3. What was the stored file? (e) Suppose we read the following c = (2, 4, 4, 0). Can you detect an error? (f) Describe a way to find and correct the error in part (e). 2. Consider again the setting of the previous problem. (a) Use the polynomial method to describe how to encode C (find the generator polynomial g(x)). (b) Use the polynomial method to show how to encode the file u = (1, 4) in a systematic way. (c) The system stores the following c = (1, 1, 1, 1) and c′ = (3, 1, 4, 0). Use the polynomial method to check whether c or c′ contain errors. 3. Let α = {α1, . . . , αn} be n distinct non-zero elements of Fq and v = (v1, . . . , vn) ∈ Fq \ {0} be a vector with non-necessarily distinct coordinates. We define the generalized RS code GRSα,v as GRSα,v ≜ { (v1p(α1), v2p(α2), . . . , vnp(αn)) ∣∣ p(x) is a polynomial in Fq of degree ≤ k − 1}. (a) Prove that GRSα,v is an (n, k) linear code. (b) Prove that GRSα,v is MDS. (c) Show that the dual of a GRSα,v code is a GRSα,v′ code where v′ ∈ Fnq \ {0}. (d) Consider the (4, 2) RS code over F7 with the following evaluation points α = {0, 1, 2, 6}. Find its dual. 4. Let RSFq(n, k) denote the Reed-Solomon code over Fq where the evaluation points is Fq (i.e., n = q). Prove that ( RSFq(n, k) )⊥ = RSFq(n, n− k), that is, the dual of these Reed-Solomon codes are Reed-Solomon codes themselves. Conclude that Reed-Solomon codes contain self-dual codes. 1 5. Let C be the standard (4,2) RS code over GF (5) . In each of the cases below, a codeword ci ∈ C, i = 1, . . . , 4, is transmitted and a corresponding string yi is received. Use the Berlekamp-Welch algorithm to decode each received string. Describe the details. (a) y1 = (1, 4, 2, 0). (b) y2 = (3, 2, 4, 0). (c) y3 = (1, 2, 1, 1). (d) y4 = (3, 0, 0, 2). 2