k matrix may be viewed as a generator continued until the standard array is filled. matrix for a code that lies in the null space of G. It is clear that for any codeword C that is generated by G, cHT 0. e1+C2... e1+C2 (3.4.5) e2+C2... e2 C2 Now, if we add an error vector e to c, then e3+C2... e3 + C2 (3.4.6) where we call S the syndrome of (c + e). If we let each syndrome correspond to an error vector, then the e2n-k-1 e2n-k_1+C2 e2n-k_1+C2 CHAPTER 3.4 Channel protection fundamentals 000 111 code of minimum distance r + 1. Thus, the Reed-Solo- 001 110 mon codes are MDS codes. Therefore, an (n, k) Reed- 010 101 (3.4.9) Solomon code can correct eo symbol erasures and e1 100 011 symbol errors simultaneously if eo + 2e1 < n - k. In particular, in a channel where only erasures can occur, all Notice that the minimum weight codeword is (1,1,1) codeword symbols of an (n, k) Reed-Solomon codeword and therefore the minimum distance of the code is 3. can be correctly recovered if at least k symbols are This implies that one error may be corrected if received. a minimum distance decoder is used for decoding. Reed-Solomon codes are suitable for the correction Alternatively, up to two errors may be detected. of burst errors. An (n, k) Reed-Solomon code can be Since the decoding of general linear block codes is not decoded in O(n2) time with Berlekamp's iterative efficient, special classes of linear codes with fast decoding algorithm [7]. Guruswami and Sudan [23] developed algorithms were developed. The most popular of these is a polynomial-time algorithm for Reed-Solomon codes the class of cyclic codes. An (n, k) linear code is a cyclic that finds a list of all codewords within a distance code if for each codeword (c1, ,Cn-1, cn), the right shift In - Vn(k-1) from a received word. Thus, the (Cn,C1,...,Cn-1) is also a codeword. algorithm is guaranteed to determine the list of all po- tentially sent codewords if at most [n - Vnkk - 3.4.3.1.1 CRC codes errors occurred during transmission. The complexity of CRC codes are shortened