WO-2026096040-A1 - LOW-COMPLEXITY LINEAR FEEDBACK SHIFT REGISTER FOR CYCLIC REDUNDANCY CHECK ENCODING AND DECODING

Abstract

Cyclic redundancy check (CRC) algorithms are utilized in digital communication and storage systems for error detection. CRC encoding and decoding may be implemented using linear feedback shift registers (LFSRs). To achieve high throughput, a parallel LFSR may be implemented by registers using feedback matrix and pre-processing matrix multiplication. In conventional architectures, a feedback matrix may be decided by look-ahead computations of an FSR, and the corresponding matrix multiplication may contribute to a significant portion of the overall complexity of the LFSR. The methods described herein are provide for searching over a wide range of powers of a companion matrix describing the parallel LFSR in order to minimize the logic gate count required for the feedback matrix multiplication.

Inventors

• ZHANG, XINMIAO
• TANG, Yok Jye
• CAI, Jiaxuan

Assignees

• OHIO STATE INNOVATION FOUNDATION

Dates

Publication Date

20260507

Application Date

20250808

Priority Date

20241028

Claims (20)

1. CLAIMS
2. What is claimed is:
3. 1. A method comprising:
4. determining a pre-processing matrix,
5. determining an alternative feedback matrix A 1
6. generating, based in part on the pre-processing matrix and the alternative feedback matrix, a low-complexity P -parallel linear feedback shift register, and
7. configuring cyclic redundancy check (CRC) encoding-decoding circuitry based on the low-complexity P-parallel linear feedback shift register.
8. 2. The method of claim 1, wherein P represents a number of input data bits to be processed during a given clock cycle, and wherein determining the alternative feedback matrix
9. A comprises determining a value of an alternative feedback matrix power L wherein the value of the alternative feedback matrix power I is not limited to P.
10. 3. The method of claim 2, wherein determining the value of the alternative feedback matrix power I compri ses searching over a predetermined range of integers.
11. 4. The method of any one of claims 2 or 3, wherein the value of the alternative feedback matrix power I is a value for which a fewest amount of exciusive-or (XOR) gates are required for matrix multiplication computations related to the alternative feedback matrix /.
12. 5. The method of any one of claims 2-4, wherein the value of the alternative feedback matrix power I is a value which reduces a critical path associated with a CRC algorithm.
13. 6. The method of claim 1, wherein the CRC encoding-decoding circuitry is configured to:
14. generate, based on a data polynomial associated with an input data string, a parity polynomial; and
15. cause transmission of the data polynomial and the parity polynomial to a user device 7. The method of claim 1, wherein the CRC encoding-decoding circuitry is configured to: receive a data polynomial and a parity polynomial, wherein the parity polynomial is generated based on the data polynomial, and
16. determine whether the parity polynomial matches a remainder polynomial, wherein the remainder polynomial is determined based on a polynomial division of the data polynomial and the parity polynomial.
17. 8. A non-transitory computer-readable storage medium storing software instructions that, when executed by a processor of an apparatus, causes the apparatus to:
18. determine a pre-processing matrix;
19. determine an alternative feedback matrix A l ,
20. generate, based in part on the pre-processing matrix and the alternative feedback matrix, a low-complexity P-parallel linear feedback shift register; and

Description

LOW-COMPLEXITY LINEAR FEEDBACK SHIFT REGISTER FOR CYCLIC REDUNDANCY CHECK ENCODING AND DECODING CROSS REFERENCE TO RELATED APPLICATIONS [0001] The present application is a continuation application of U. S. Patent. Application No. 63/712,874, filed on October 28, 2024, which is hereby incorporated by reference in its entirety. GO VERNMENT LICENSE RIGHTS [0002] This invention was made with government support under Award No. 2011785 awarded by the National Science Foundation. The government has certain rights in the invention. BACKGROUND [0003] Cyclic redundancy check (CRC) algorithms are widely used in many digital communication and storage systems for detecting data corruption, ensuring the reliable transfer of data. BRIEF SUM ARY [0004] Cyclic redundancy check (CRC) algorithms are widely used in many digital communication and storage systems for detecting data corruption, ensuring the reliable transfer of data. In general, a CRC encoder-decoder of a sender (e.g., an originating computing device) may utilize a CRC algorithm to encode data to be transmitted to a receiver (e.g., a receiving computing device), where a CRC encoder-decoder of the receiver may use the CRC algorithm to decode the data in order to determine if the data has been transmitted with errors or corruption (e.g., errors caused by transmission interference). On the sender’s side, the CRC encoderdecoder may perform polynomial division using the data to be transmitted (e.g., binary data) and a divisor (e.g., a binary string decided by a generator polynomial) to compute parity bits, which are remainder values derived from the binary- division. The CRC encoder-decoder may append the parity bits to the data to be transmitted. On the receiver’s side, the CRC encoder-decoder may perform a similar binary division using the data with the appended parity bits and the same divisor (e.g., the same generator polynomial). If the CRC encoder-decoder determines that a remainder value of the binary division is zero, the receiver determines that no errors or data corruption has occurred. In the event that a remainder value is a non-zero value, the receiver determines that an error or data corruption has occurred. [0005] Linear feedback shift registers (LFSRs) may be used to implement CRC encoding and decoding and may be configured to compute remainders (e.g., CRC code) of polynomial divisions. In the encoding (e g., generation) and decoding of CRC codes, parities are generated as a remainder of dividing a data polynomial (e.g., a binary polynomial representation of data to be transferred, aka. a message polynomial) by a generator polynomial. Such computations can be carried out by using LFSRs, and LFSRs with a high level of parallelism are needed to meet the high-speed requirements of many practical systems. A conventional parallel LFSR may be understood as a shift register that comprises registers whose state is a linear function (e.g., an exclusive-or (XOR) function) of a previous state of the registers. In some examples, a P -parallel LFSR may be developed by applying look-ahead computations to derive the states of data registers after P clock cycles. Such designs may advantageously lead to a shorter critical path (e.g., the longest sequence of computations between any pair of registers) and a lower complexity compared to those derived by other parallel process algorithms (e.g., unfolding algorithms), especially for larger P. In some such examples, the value of P of a P-parallel LFSR may indicate a degree of parallelism of the P -parallel LFSR. Additionally or alternatively, in some examples, a P-parallel LFSR may process P input data bits during each clock cycle of a corresponding processor of a respective computing device utilizing the P-parallel LFSR. [0006] In some conventional systems, a parallel LFSR based on register state look-ahead utilizes binary matrix multiplications for pre-processing the input of data and updating register states in a feedback loop. For example, in some conventional systems, a register state transformation is used to modify both feedback and pre-processing matrices at the cost of additional post-processing matrix multiplication. In such a system, the data path of multiplying the feedback matrix may be reduced to one XOR gate by using companion-like transformation matrices. However, such transformations may lead to the use of more logic gates in the preprocessing and post-processing matrix multiplications. To mitigate these technical challenges, some conventional systems may endeavor to reduce the overall number of XOR gates by searching for transformation matrices in a triangular form or by searching for inverse transformation matrices to achieve a lower logic gate count and/or reduce the power consumption of a device employing such parallel LFSRs. [0007] For conventional LFSRs, data input may be added to a most significant tap bit of the LFSR. For a CRC with a generator polynomial of degree w, shifting the input to th