Designing programmable parallel LFSR using parallel prefix trees

Abstract

Linear Feedback Shift Registers (LFSRs) are simple sequential circuits widely used in different applications and environments. An LFSR is uniquely represented by a binary sequence called the generating sequence which determines the system-level properties of the LFSR such as error detection capability or the length of the pseudo-random number sequence. Since LFSRs cannot sample more than one bit per clock cycle, they can cause throughput bottlenecks in parallel environments. Using parallel LFSRs with higher sampling rates is a common approach to mitigate this problem. But this approach requires managing tradeoffs among sampling rate and circuit-level parameters such as clock period and area. This paper proposes an approach inspired by the notion of Parallel Prefix Trees (PPTs) in arithmetic circuits to design programmable parallel LFSRs which can operate on any generating sequence of a given length. This approach aims at performance as well as system and circuit-level flexibility. 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.