High Throughput VLSI Architectures for CRC/BCH Encoders and FFT computations

University of Minnesota Master of Science in Electrical Engineering thesis. December 2010. Major: Electrical Engineering. Advisor: Keshab K. Parhi. 1 computer file (PDF); viii, 62 pages.Linear feedback shift register (LFSR) is an important component of the cyclic redun- dancy check (CRC) operations and BCH encoders. This thesis presents a mathematical proof of existence of a linear transformation to transform LFSR circuits into equivalent state space formulations. This transformation achieves a full speed-up compared to the serial architecture at the cost of an increase in hardware overhead. This method applies to all irreducible polynomials used in CRC operations and BCH encoders. A new formu- lation is proposed to modify the LFSR into the form of an IIR ¯lter. We propose a novel high speed parallel LFSR architecture based on parallel In¯nite Impulse Response (IIR) ¯lter design, pipelining and retiming algorithms. The advantage of proposed approach over the previous architectures is that it has both feedforward and feedback paths. We further propose to apply combined parallel and pipelining techniques to eliminate the fanout e®ect in long generator polynomials. The proposed scheme can be applied to any generator polynomial, i.e., any LFSR in general. A comparison between the proposed and previous architectures shows that the proposed parallel architecture achieves the same critical path as that of previous designs with a reduced hardware cost. Further, this thesis presents a novel approach to develop the pipelined architectures for the fast Fourier transform (FFT). A formal procedure for designing FFT architec- tures using folding transformation and register minimization techniques is proposed. Novel parallel-pipelined architectures for the computation of fast Fourier transform are derived. The proposed architecture takes advantage of under utilized hardware in the serial architecture to derive L-parallel architectures without increasing the hardware complexity by a factor of L. The operating frequency of the proposed architecture can be decreased which in turn reduces the power consumption. A comparison is drawn be- tween the proposed designs and the previous architectures. The power consumption can be reduced up to 37% and 50% in 2-parallel FFT architectures. The output samples are obtained in a scrambled order in the proposed architectures. Circuits to reorder these scrambled sequences to desired order are presented