Configurable multi-step linear feedback shift register
US7702706B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Mar 30, 2004 |
| Grant date | Apr 20, 2010 |
| Priority date | — |
| Expiry date | Apr 24, 2027 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F7/72
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The state transition of a linear feedback shift register (LFSR) controlled by a clock (310) with length N and step size W, W being at least two, is accomplished via a next-state function (320). The next-state function deploys a state transition matrix (350). The state vector (330), which represents the contents of the LFSR, is either multiplied sequentially by the state transition matrix or multiplied by the state transition matrix to the power of W (multiple state transition matrix). The method and the LFSR according to the invention are characterized in that the multiple state transition matrix is decomposed in a first matrix (360) and a second matrix (370), the first matrix comprising at most N+W+1 different expressions and the second matrix comprising at most N+W+1 different expressions. The LFSR further comprises means to multiply the state vector by the second matrix and the first matrix, and means for computing the first matrix. The invention overcomes the shortcomings of configurable multi-step linear feedback shift registers because the amount of time needed to generate the output can be reduced significantly.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.