Arithmetic in large GF(2(exp n))

Abstract

The decoding of Reed Solomon (BCH) codes usually requires large numbers of calculations using GF(2(exp n)) arithmetic. Though efficient algorithms and corresponding circuits for performing basic Galois field arithmetic are known, many of these techniques either become very slow or else require an inordinate amount of circuitry to implement when the size of the Galois field becomes much larger than GF(2(exp 8)). Consequently, most currently available Reed-Solomon decoders are built using small fields, such as GF(2(exp 8)) or GF(2(exp 10)), even though significant coding efficiencies could often be obtained if larger symbol sizes, such as GF(2(exp 16)) or GF(2(exp 32)), were used. Algorithms for performing the basic arithmetic required to decode Reed-Solomon codes have been developed explicitly for use in these large fields. They are discussed in detail.