Algebra and Its Applications to Coding Theory

Abstract

Finite field is one of the most prominent theories applied to cyclic error correcting codes. Construction of Bose-Chaudhuri-Hocquenghem (BCH) codes, a special class of cyclic codes, relies heavily on finite field arithmetics. These arithmetics need to be performed efficiently to meet the execution speed and the design constrains. Such objectives constitute massive challenges and efforts that will render for the best algorithms, architectures, implementations and design. In this thesis, we aim to provide a perspective on the application of finite field arithmetics in encoding and decoding algorithms of cyclic codes. First, the consistent usage of operations and theories in finite field is presented. Further, a novel systematic encoding algorithm for long cyclic codes, n ≥ 214 − 1, shows a satisfactory time saving percentage over traditional algorithms. Finally, in BCH decoding algorithms, “Chien” search process is one of the most time consuming blocks. We relatively decrease the time lost by the decoder in searching for roots of an error locator polynomial which not all of its roots belong to the multiplicative group F 2m.