Three different finite-field multipliers are presented: (1) a dual-basis multiplier due to E.R. Berlekamp (1982); the Massey-Omura normal basis multiplier; and (3) the Scott-Tavares-Peppard standard basis multiplier. These algorithms are chosen because each has its own distinct features that apply most suitably in particular areas. They are implemented on silicon chips with NMOS technology so that the multiplier most desirable for VLSI implementation can readily be ascertained.>

A conventional prime factor discrete Fourier transform (DFT) algorithm of the Winograd type is used to realize a discrete Fourier-like transform on the finite field GF(q/sup /n). A pipeline structure is used to implement this prime-factor DFT over GF(q/sup /n). This algorithm is developed to compute cyclic convolutions of complex numbers and to aid in decoding the Reed-Solomon codes. Such a pipeline fast prime-factor DFT algorithm over GF(q/sup /n) is regular, simple, expandable, and naturally suitable for most implementation technologies. An example illustrating the pipeline aspect of a 30-point transform over GF(q/sup /n) is presented.>

A new VLSI design of a pipeline Reed-Solomon decoder is presented. The transform decoding technique used in a previous design is replaced by a simple time domain algorithm. A new architecture which realizes such algorithm permits efficient pipeline processing with a minimum of circuits. A systolic array is also developed to perform erasure corrections in the new design. A modified form of Euclid's algorithm is developed with a new architecture which maintains a real-time throughput rate with less transistors. Such improvements results in both an enhanced capability and significant reduction in silicon area, thereby making it possible to build a pipeline (255,223) RS decoder on a single VLSI chip.

In this paper a recursive algorithm using the error-trellis decoding technique is developed to decode certain convolutional codes (CC's). An example, illustrating the VLSI architecture of such a decoder, is given for a dual-k CC. It is demonstrated that such a decoder can be realized readily on a single chip with NMOS technology.

In this correspondence, the complex integer multiplier and adder over the direct sum of two copies of finite field developed in [1] is specialized to the direct sum of the rings of integers modulo Fermat numbers. Such multiplication over the rings of integers modulo Fermat numbers can be performed by means of two integer multiplications, whereas the complex integer multiplication requires three integer multiplications. Such multiplications and additions can be used in the implementation of a discrete Fourier transform (DFT) of a sequence of complex numbers. The advantage of the present approach is that the number of multiplications needed to compute a systolic array of the DFT can be reduced substantially. The architectural designs using this approach are regular, simple, expandable and, therefore, naturally suitable for VLSI implementation.

Multiplication is central in the implementation of Fermat number transforms (FNT) and other residue number algorithms. There is need for a good multiplication algorithm which can be realized easily on a VLSI chip. In this paper, the Leibowitz multiplier [1] is modified to realize multiplication in the ring of integers modulo a Fermat number. The advantage of this new algorithm over Leibowitz's algorithm is that Leibowitz's algorithm takes modulo after the product of multiplication is obtained. Hence time is wasted. In this new algorithm, modulo is taken in every bit operation when performing multiplication. Therefore no time is wasted in this respect. Furthermore, this algorithm requires only a sequence of cyclic shifts and additions. The design for this new multiplier are regular, simple, expandable and therefore, suitable for VLSI implementation.

Multiplication is central in the implementation of Fermat Number Transforms (FNT) and other residue number algorithms. There is need for a good multiplication algorithm which can be realized easily on a VLSI chip. In this paper, the Leibowitz multiplier [1] is modified to realize multiplication in the ring of integers modulo a Fermat number. The advantage of this new algorithm over Leibowitz's algorithm is that Leibowitz's algorithm takes modulo after the product of multiplication is obtained. Hence time is wasted. In this new algorithm, modulo is taken in every bit operation when performing multiplication. Therefore no time is wasted in this respect. Furthermore, this algorithm requires only a sequence of cyclic shifts and additions. The design for this new multiplier are regular, simple, expandable and therefore, suitable for VLSI implementation.

Berlekamp has developed for the California Institute of Technology Jet Propulsion Laboratory (JPL) a bit-serial multiplication algorithm for the encoding of Reed-Solomon (RS) codes, using a dual basis over a Galois field. The conventional RS encoder for long codes often requires lookup tables to perform multiplication of two field elements. Berlekamp's algorithm requires only shifting and EXCLUSIVE OR operations. It is shown in this paper that the new dual-basis (255,223) RS encoder can be realized readily on a single VLSI chip with NMOS technology.