Configurable multi-step linear feedback shift register
View Patent ↗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.
1. A method for accomplishing state transitions in a configurable linear feedback shift register (LFSR) controlled by a clock, the length of the LFSR being represented by N, wherein a state vector represents the state of the LFSR, an output of the LFSR comprising W output symbols, W being at least two, and the output symbols being generated during one clock cycle, a state transition of the LFSR being accomplished during one clock cycle via multiplication of the state vector by a state transition matrix to the power of W (multiple state transition matrix), characterized in that said multiple state transition matrix is decomposed in a first matrix and a second matrix, the first matrix comprising at most N+W+1 different expressions and the second matrix comprising at most N+W+1 different expressions, wherein the elements of the second matrix are defined by:
G
i
,
j
=
{
1
,
if
i
-
j
=
W
g
i
+
j
-
N
+
1
,
if
(
i
+
j
≥
N
-
1
)
⋀
(
j
≥
N
-
W
)
0
,
otherwise
and the elements of the first matrix are defined by:
P
i
,
j
=
{
1
,
if
i
=
j
⋀
i
<
N
-
W
p
i
+
j
-
2
N
+
W
+
1
,
if
i
+
j
≥
2
N
-
W
-
1
0
,
otherwise
wherein
p
0
=
1
,
p
1
=
∑
j
=
0
i
-
1
g
N
-
i
+
j
p
j
for
0
<
i
<
N
,
and g 0 , g 1 up to and including g N-1 represent the configuration symbols which are comprised in the state transition matrix.
2. A method according to claim 1 , wherein the expressions of the first matrix are evaluated during a configuration stage of the operation of the LFSR.
3. A configurable linear feedback shift register (LFSR) controlled by a clock, the length of the LFSR being represented by N, a state vector representing the state of the LFSR, the LFSR being arranged to generate an output comprising W output symbols, W being at least two, to generate the output symbols during one clock cycle, the LFSR comprising multiplication means for accomplishing a state transition of the LFSR during one clock cycle via multiplication of the state vector by a state transition matrix to the power of W (multiple state transition matrix), characterized in that said multiple state transition matrix is decomposed in a first matrix and a second matrix, the first matrix comprising at most N+W+1 different expressions and the second matrix comprising at most N+W+1 different expressions, wherein the elements of the second matrix are defined by:
G
i
,
j
=
{
1
,
if
i
-
j
=
W
g
i
+
j
-
N
+
1
,
if
(
i
+
j
≥
N
-
1
)
⋀
(
j
≥
N
-
W
)
0
,
otherwise
and the elements of the first matrix are defined by:
P
i
,
j
=
{
1
,
if
i
=
j
⋀
i
<
N
-
W
p
i
+
j
-
2
N
+
W
+
1
,
if
i
+
j
≥
2
N
-
W
-
1
0
,
otherwise
wherein
p
0
=
1
,
p
i
=
∑
j
=
0
i
-
1
g
N
-
i
+
j
p
j
for
0
<
i
<
N
,
and g 0 , g 1 up to and including g N-1 represent the configuration symbols which are comprised in the state transition matrix.
4. A configurable linear feedback shift register (LFSR) according to claim 3 , characterized in that the multiplication means comprises a first set of logical units for performing the multiplication of the state vector by the second matrix and a second set of logical units for performing the multiplication of the state vector by the first matrix.
5. A configurable linear feedback shift register (LFSR) according to claim 4 , characterized in that the LFSR comprises a third set of logical units for computing the first matrix.
6. A configurable linear feedback shift register (LFSR) according to claim 5 , characterized in that the third set of logical units is arranged to perform the computation of the first matrix during a configuration stage of the operation of the LFSR.
7. A configurable linear feedback shift register (LFSR) according to claim 6 , characterized in that the second set of logical units is coupled to the first set of logical units via an intermediate data register.