High-speed parallel architectures for linear feedback shift registers

Manohar Ayinala, Keshab K. Parhi

Research output: Contribution to journalArticlepeer-review

44 Scopus citations

Abstract

Linear feedback shift register (LFSR) is an important component of the cyclic redundancy check (CRC) operations and BCH encoders. The contribution of this paper is two fold. First, this paper 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 generator polynomials used in CRC operations and BCH encoders. Second, a new formulation is proposed to modify the LFSR into the form of an infinite impulse response (IIR) filter. We propose a novel high speed parallel LFSR architecture based on parallel IIR filter design, pipelining and retiming algorithms. The advantage of the 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 effect in long generator polynomials. The proposed scheme can be applied to any generator polynomial, i.e., any LFSR in general. The proposed parallel architecture achieves better area-time product compared to the previous designs.

Original languageEnglish (US)
Article number5875903
Pages (from-to)4459-4469
Number of pages11
JournalIEEE Transactions on Signal Processing
Volume59
Issue number9
DOIs
StatePublished - Sep 2011

Keywords

  • BCH
  • cyclic redundancy check (CRC)
  • linear feedback shift register (LFSR)
  • look-ahead computation
  • parallel processing
  • pipelining
  • state space
  • transformation

Fingerprint Dive into the research topics of 'High-speed parallel architectures for linear feedback shift registers'. Together they form a unique fingerprint.

Cite this