The basis-change algorithm for fast finite field transforms

A computational algorithm is developed which involves the change of basis of field elements during the nontrivial evaluation of coset elements. This finite field arithmetic is equipped with cyclic shifting for scaling, simple table lookups for polynomial reduction, and a series of component-wise modular adders. Application of these concepts to the existing fast transform not only serves to simplify the transform, but also leads to the development of a very compact signal processing device which can be implemented as a building block and seamlessly integrated with a discrete Fourier transform (DFT) system. Once the butterfly operation module of a cyclotronic coset based on the algorithm is developed, the integration of the modules leads to an efficient VLSI implementation of the pipeline stages of the fast transform