BCH, Reed–Solomon, and related codes
Robert J. McEliece · Cambridge University Press eBooks · 2004
Introduction In Chapter 7 we gave one useful generalization of the (7, 4) Hamming code of the Introduction: the family of (2 m − 1, 2 m − m − 1) single-error-correcting Hamming codes. In Chapter 8 we gave a further generalization, to a class of codes capable of correcting a single burst of errors. In this chapter, however, we will give a far more important and extensive generalization, the multipleerror-correcting BCH 2 and Reed–Solomon codes. To motivate the general definition, recall that the parity-check matrix of a Hamming code of length n = 2 m − 1 is given by (see Section 7.4) where ( v 0 , v 1 , …, v n −1 ) is some ordering of the 2 m − 1 nonzero (column) vectors from V m = GF (2) m . The matrix H has dimensions m × n , which means that it takes m parity-check bits to correct one error. If we wish to correct two errors, it stands to reason that m more parity checks will be required. Thus we might guess that a matrix of the general form where w 0 , w 1 , …, w n −1 ∈ V m , will serve as the parity-check matrix for a two-error-correcting code of length n . Since however, the v i 's are distinct, we may view the correspondence v i → w i as a function from V m into itself, and write H 2 as But how should the function f be chosen? According to the results of Section 7.3, H 2 will define a two-error-correcting code iff the syndromes of the error pattern of weights 0, 1 and 2 are all distinct.