Reed–Solomon and Related Codes

Generalized Reed–Solomon (in short, GRS) codes and their derivative codes are probably the most extensively-used codes in practice. This may be attributed to several advantages that these codes have. First, GRS codes are maximum distance separable, namely, they attain the Singleton bound. Secondly, being linear codes, they can be encoded efficiently; furthermore, as we see in this chapter, encoders for the sub-class of conventional Reed–Solomon (in short, RS) codes can be implemented by particularly simple hardware circuits. Thirdly, we will show in Chapters 6 and 9 that GRS codes can also be decoded efficiently. As their names suggest, RS codes pre-dated their GRS counterparts. Nevertheless, we find it more convenient herein to define GRS codes first and prove several properties thereof; we then present RS codes as a special class of GRS codes. One seeming limitation of GRS codes is the fact that their length is bounded from above by the size of the field over which they are defined. This could imply that these codes might be useful only when the application calls for a field size that is relatively large, e.g., when the field is GF(2 8 ) and the symbols are bytes. Still, we show that GRS codes can serve as building blocks to derive new codes over small alphabets as well. We present two methods for doing so. The first technique is called concatenation and is based on two stages of encoding, the first of which is a GRS encoder.