Algorithms and Parallel Computing

18.1 INTRODUCTION

Finite field polynomial division is an operation that is widely used to detect errors and encode data in digital communication systems [113], as well as detect errors in integrated circuits [114, 115]. In digital communications, detecting errors is called cyclic redundancy check (CRC), which appends bits to the message stream before transmission. These redundant bits are obtained from the message bits using finite field polynomial division. In digital integrated circuits, detecting errors is known as built-in self-test (BIST) where a generator produces a pseudorandom vector to be applied to a circuit under test. A compactor reduces the response of the circuit to a signature having a small number of bits. Both the generator and the compactor employ finite field polynomial division. The generation of pseudorandom numbers and polynomial division is usually done using a linear feedback shift register (LSFR). The operations performed by the LFSR can be done in software or hardware. We shall explore the different LFSR structures in this chapter.

Assume the information bits to be processed are represented by a dividend polynomial A. A divisor polynomial B is used to effect the finite field polynomial division. In the following section, we study polynomial division algorithm in more detail.