Designing programmable parallel LFSR using parallel prefix trees

Abstract EN

The throughput of an LFSR (Linear Feedback Shift Register) is affected by the sampling rate as well as the clock rate.

On the other hand, the system-level characteristics of an LFSR such as its error detection capabilities are determined by the generating polynomial.

Parallel LFSRS aim at improving the sampling rate in order to meet high throughput demands in parallel transmission or computation environments.

Moreover, programmable LFSRS provide more system level flexibility by allowing different generating polynomials to be used.

Thus, using programmable parallel LFSRs looks an attractive solution to improve both throughput and system-level parameters.

Programmable parallel LFSRs can be useful in stream ciphers, microprocessors, and many other environments.

But parallelism and programmability can reduce the clock rate by increasing the logical depth and increase power and area by increasing the number of gates.

Thus, we will need an efficient solution to manage the tradeoffs.

This paper proposes an approach based on Parallel Prefix Trees (PPTs) to design programmable parallel LFSRs.

PPTs are a family of topologies previously used in the design of parallel arithmetic circuits in order to manage the tradeoff between different circuit level parameters.

Our approach allows designers to use different PPTs in order to improve different circuit level parameters.

A sample PPT-based programmable parallel LFR is designed and evaluated.

Empirical results show more than 23% improvement in throughput and more than 27% improvement in area compared to state-of-the-art programmable parallel LFSR architectures.