Cycle-efficient lineary feedback shift register implementation on word-based micro-architecture

A novel algorithm transformation method, called term-preserving look-ahead transformation (TePLAT) is proposed to transform the bit-serial linear feedback shift register (LFSR) algorithm into a bit-parallel formulation which promises order of magnitudes improvement of execution speed compared to the traditional look-ahead algorithm transformation approach. TePLAT is applied to 26 commonly used LFSRs and tested on two popular word-based micro-processor development platforms: a Texas Instrument C6416 Code Composition Simulator and an ARM-9 Simulator. In all 26 cases, TePLAT transformed implementations consistently deliver much higher throughput than those implementations based on traditional look-ahead algorithm transformation.