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.
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.
High Throughput VLSI Architectures for CRC/BCH Encoders and FFT computations.
Retrieved from the University of Minnesota Digital Conservancy,
Content distributed via the University of Minnesota's Digital Conservancy may be subject to additional license and use restrictions applied by the depositor.