ABSTRACT
Reed-Solomon or RS(n, k) codes are nonbinary cyclic codes composed of sequences of symbols of m-bits, where m > 2 is an integer, which exist for all n and k, 0 < k < n < 2m + 2. In this notation, n is the total number of code symbols in an encoded block (usually called length), and k is the number of data symbols to be encoded. Generally, (n, k) = (2m − 1, 2m− 1− 2t), where t is the (symbol) error correcting capability of the code. An extended RS code can have n = 2m or n = 2m + 1. Among all linear codes with the same encoding input and output block lengths, RS codes have the largest possible minimum distance. Similar to the Hamming distance, the distance between two codewords in a nonbinary code is defined as the number of symbols in which the sequences differ. For RS codes, the minimum distance is given by dmin = n − k + 1. This code can correct any combination of t or fewer er-
rors, where t = ⌊dmin − 1
⌋ = b(n − k)/2c. This definition of t implies that
correction of t symbols using an RS code requires at most 2t parity symbols. In fact, the RS decoder has (n − k) redundant symbols, which is equal to 2t, i.e., twice the number of correctable errors. In the case of erasures, the correction capability of the code is γ = dmin − 1 = n− k. Since RS codes are used as both error correcting and erasure codes (see §13.6), the simultaneous error-correction and erasure-correction capability of the code is expressed as 2α + γ < dmin < n − k, where α is the number of correctable symbol-error patterns and γ the correctable number of symbol erasure patterns (see §13.6 on erasures).
