Low-Complexity Linear Feedback Shift Register Architecture For CRC En/Decoding

Cyclic redundancy check (CRC) is utilized in digital communication and storage systems for error detection. CRC en/decoding is implemented using linear feedback shift registers (LFSRs). To achieve high throughput, a parallel LFSR can be implemented by registers with a feedback matrix and a pre-processing matrix multiplication. In previous designs, the feedback matrix is decided by look-ahead computations of the LFSR, and its multiplication contributes to a significant portion of the overall complexity. This paper proposes to search over a wide range of powers of the companion matrix describing the LFSR to minimize the gate count of the feedback matrix multiplication. This is enabled by an alternative interpretation of data inputs. Although the achievable data length protected by CRC is reduced by the proposed scheme, it still meets the requirement of IEEE standards. Besides, our scheme does not affect the pre-processing matrix and the input tap of the LFSR can still be shifted to reduce the complexity. For an example case that the parallelism equals the generator polynomial degree, the proposed design can reduce the gate count by 18%-53% and achieve shorter critical path for various CRCs.