s than or equal to n - k + 1. Linear (n, k) codes indexed by the syndrome. Therefore, syndrome decoding whose minimum distance is equal to n - k + 1 are called may be viewed as indexing a row of the standard array and maximum-distance separable (MDS) codes. then adding the first element of the row to the received Linear codes can be simply modified to obtain new vector. linear codes. Puncturing a linear code consists of removing a number of coordinate positions from each Example 5. Consider a (3,1) binary repetition code. This codeword. If an (n, k) linear MDS code is punctured, block code consists of two codewords, {000,111}. A then the resulting code is an (n - 1, k) linear MDS code. generator matrix for the code is Shortening a linear code consists of keeping only G = [111]. (3.4.7) codewords with the same symbol in a given position and then deleting this position. If an (n, k) linear MDS code is shortened by keeping only codewords with the zero The corresponding parity check matrix is symbol in a given position, then the resulting code is an (n - 1,k - 1) linear MDS code. (3.4.8) The encoding scheme for an (n, k) linear code can be implemented in O(n2) time. However, there is no efficient way to decode a general linear code with And we can tabulate the standard array as follows: maximum-likelihood decoding [8]. Usually one uses syndrome decoding. To explain syndrome decoding, we must introduce the parity check matrix. The parity check Table 3.4-1 Standard array of a binary code. The first row contains matrix H of an (n, k) linear code with generator matrix G all codewords of the code. Each following row is formed by taking is an (n k) X n matrix whose rows are orthogonal to the a minimum weight vector, adding it to the first row, and then rows of the generator matrix, that is, checking if the resulting addition is already part of the standard array. If the resulting addition is not part of the standard array, then GHT = 0. (3.4.4) it is added as a new row to the standard array. This process is The parity chec