Reed-Solomon Codes

Chapter 8 Reed-Solomon codes In the previous chapter we discussed the properties of finite fields, and showed that there exists an essentially unique finite field F_q with q = p^m elements for any prime p and integer m ≥ 1.   We now consider (n, k, d) linear codes over a finite field F_q. The most useful such codes are the Reed-Solomon (RS) codes (1960), whose length is limited to n ≤ q, but which have arbitrary dimension k, 1 ≤ k ≤ n, and which have a minimum distance of d = n - k + 1. This meets a certain fundamental bound called the Singleton bound. RS codes are easily decoded, and have a wide range of uses. We also briefly mention binary Bose-Chaudhuri-Hocquenghem (BCH) codes (1959), which are binary derivatives of RS codes. The parameters (n, k, d) of BCH codes are sometimes slightly better than those of Reed-Muller (RM) codes.   8.1 Linear codes over finite fields An (n, k) linear code C over a finite field F_q is a k-dimensional subspace of the vector space F_qⁿ. A subset C ⊆ F_qⁿ is a subspace if it is closed under componentwise addition (has the group property) as well as under multiplication by scalars (elements of F_q). A linear code C thus necessarily contains the all-zero n-tuple 0.   Any k linearly independent codewords (g₁, ..., g_k) generate C in the sense that C = {∑_j=1^k a_jg_j, a_j ∈ F_q, 1 ≤ j ≤ k}. Thus C has q^k distinct codewords. Example 1. The following nine 4-tuples over F₃ form a (4, 2, 3) linear code over the ternary field F₃ = {0, 1, 2}, with generators g₁ = (1110) and g₂ = (0121): C = {0000, 1110, 2220, 0121, 1201, 2011, 0212, 1022, 2102}. By the group property, c ∈ C and c - c' for any codewords c, c' ∈ C, so the set of Hamming distances between any codeword c ∈ C and all other codewords is independent of c. The minimum Hamming distance d between codewords in a linear code C is thus equal to the minimum Hamming   weight of any nonzero codeword (the minimum distance between 0 and any other codeword). w = min_c∈C,c≠0wt(c) More generally, the group property shows that the number of codewords at Hamming distance w from any codeword c ∈ C is the number N_w of codewords of Hamming weight w in C.   Much of classical algebraic coding theory has been devoted to optimizing the parameters (n, k, d); i.e., maximizing the size q^k of the code for a given length n, minimum distance d and field F_q, or maximizing the guaranteed error-correction power of the code. Because Hamming distance d is a metric satisfying the triangle inequality, a code with Hamming distance d is guaranteed to correct t ≤ d/2 symbol errors whenever 2t ≤ d, or in fact to correct t errors and s erasures whenever 2t + s ≤ d. This elementary metric is not the whole story with regard to performance on an AWGN channel, nor does it take into account decoding complexity; however, it is a good first measure of code power.   8.2 The Singleton bound and MDS codes The Singleton bound is the most fundamental bound on the parameters (n, k, d) over any field: k + d ≤ n + 1.   A code that meets this bound with equality is called "maximum distance separable" (MDS). The only binary codes that are MDS are the trivial (n, n, 1) universe codes, the (n, n-1, 2) single-parity-check (SPC) codes, and the (n, 1, n) repetition codes. However, over nonbinary fields, there exist much less trivial MDS codes, notably the Reed-Solomon codes and their close relations. Let C ⊆ Aⁿ be any set of C n-tuples over any symbol alphabet A of size q = |A|, and let the minimum Hamming distance between codewords in C be d. Then C should be able to correct any set of s = d - 1 erasures; i.e., after puncturing any symbol in d - 1 of the coordinates, the codewords must still all differ in the remaining n - s = n - d + 1 coordinates. Therefore there can be at most q^n-d+1 codewords in C:   Theorem 8.1 (Singleton bound) A code C of length n with minimum Hamming distance d over an alphabet of size q = |A| can have at most |C| ≤ q^n-d+1 codewords. Equality holds if and only if every set of k = n - d + 1 coordinates run through all q possible k-tuples in every set of k = n - d + 1 coordinates. Note that the Singleton bound holds also for nonlinear codes. Any code that meets the Singleton bound with equality is called an MDS code. Given a (possibly nonlinear) code C with q^k codewords over an alphabet of size q, a set of k coordinates is called an information set of C if the codewords run through all possible k-tuples in these coordinates; that is, if there is a unique codeword associated with every possible set of symbol values in that set of coordinates. In other words, we may freely specify the symbols in these coordinates, and then the remainder of the codeword is uniquely specified. The case of equality may therefore be restated as follows:   Corollary 8.2 (Information sets of MDS codes) C is an MDS code if and only if every subset of k = n - d + 1 coordinates is an information set of C.   If C is a linear (n, k, d) code over a finite field F_q, then its size is |C| = q^k. Therefore: 8.5 Applications of RS codes RS codes are useful for a variety of applications: (a) For channels that naturally transmit packets or binary m-tuples, RS codes over F_2^m are used for m-tuple (byte) error correction.   (b) Over memoryless channels such as the AWGN channel, powerful codes may be constructed by concatenation of an "inner code" consisting of q = 2^m codewords or signal points together with an "outer code" over F_2^m, where F_2^m is identified with the inner codewords. Such a concatenated code may be efficiently decoded by maximum-likelihood detection of the inner code followed by algebraic decoding of the RS outer code, preferably using reliability information from the inner decoder in the RS decoder.   (c) RS codes are also useful for burst error correction; for this purpose they are often combined with m-tuple (byte) interleavers.   8.5.1 Concatenation using RS Codes A basic concatenated code involves two codes, called the inner code and outer code, as shown in Figure 1. We see immediately that a concatenation scheme is another example of a layered architecture.   diagram showing a block diagram of a concatenated coding system Figure 1. Concatenation of an inner code and an outer code. The inner code is typically a binary code, such as a block or convolutional, used over a binary channel, such as a discrete-time AWGN channel, with a 2-PAM signal set. The inner decoder is typically a maximum-likelihood decoder, such as a Viterbi decoder, which uses soft (reliability-weighted) outputs from the channel.   The outer code is typically a RS code over a finite field F_2^m. The field of characteristic 2. Each field element may thus be represented by a binary m-tuple. The field F₂₅₆ is commonly used, in which case field elements are represented by 8-bit bytes. An RS codeword of length n symbols may therefore be converted into an RS-coded sequence of nm bits, which is the input sequence to the inner encoder.   The input sequence to the inner encoder is often permuted by an interleaver to ensure that symbols in a given RS codeword are transmitted and decoded independently. A simple row-column interleaver can be used.