Cycle-Efficient LFSR Implementation on Word-Based Microarchitecture

Cycle-efficient implementation of the linear feedback shift register (LFSR) algorithm on a word-based microarchitecture is investigated. This work examines an algorithm transformation method, called term-preserving look-ahead transformation (TePLAT), that transforms the bit-serial LFSR algorithm into a bit parallel format while maintaining the overhead of the original LFSR algorithm. Detailed implementation methodologies as well as extensive simulation results are presented. We apply TePLAT to 25 commonly used LFSRs and test the resulting parallel formulations on two popular word-based microprocessor development platforms: a Texas Instrument C6416 Code Composition Simulator and an ARM-9 Simulator. In all 25 cases, TePLAT transformed LFSR formulations consistently achieve much higher throughput than those of a naïve implementation and a traditional look-ahead transformation-based implementation.