Methods for efficient state transition matrix based LFSR computations

1. A method for state transition matrix-based linear feedback shift register computations, said method comprising:

computing a transition matrix associated with a linear feedback shift register, said transition matrix comprising a k-step transition matrix based on a single step state transition matrix;

computing an output matrix associated with said linear feedback shift register defined such that an input bit is a linear function of a previous state and external input bits and comprises more than one feedback as input;

combining said transition matrix with said output matrix;

reducing a size of said transition matrix and said output matrix following combining said transition matrix with said output matrix; and

configuring said transition matrix to comprise said single step state transition matrix wherein a size of said k-step transition matrix is increased from L*(L+k) to k*(L+k), but an output generating matrix is reduced from k*(L+k) to zero, thereby providing an improved speedup capability for calculating a next state and/or an output of said linear feedback shift register.

2. The method of claim 1 further comprising:

defining a polynomial associated with said single step state transition matrix, wherein said polynomial corresponds to said linear feedback shift register defined such that an input bit is a linear function of a previous state and external input bits and comprises more than one feedback as input.

3. The method of claim 2 wherein reducing said size of said transition matrix and said output matrix following combining said transition matrix with said output matrix, further comprises:

augmenting said single step transition matrix;

generating said k-step state transition matrix M k of dimension L*k; and

multiplying a final transition matrix by a state input vector.

4. The method of claim 3 wherein augmenting said single step transition matrix further comprises:

adding zeros to a plurality of new matrix elements; and

associating one feedback term with said polynomial.

5. The method of claim 4 further comprising:

performing an XOR operation on said state input vector and resultant vector; and

utilizing said linear feedback shift register in combination with a cyclic redundancy checking device.

6. The method of claim 4 wherein augmenting said single step transition matrix further comprises:

adding a plurality of rows to said single step transition matrix; and

producing an output of said linear feedback shift register wherein said output Is a state bit.

7. The method of claim 6 further comprising: utilizing said linear feedback shift register in combination with a gold sequence scrambler.

8. The method of claim 3 wherein augmenting said single step transition matrix further comprises: adding zeros to a plurality of new matrix elements; and associating more than one feedback term with said polynomial.

9. The method of claim 8 further comprising: performing an XOR operation on said state input vector and a resultant vector; and utilizing said linear feedback shift register in combination with a turbo encoder.

10. The method of claim 3 further comprising: iterating said steps until all input bits are consumed or all state bits are produced wherein said iteration produces a plurality of next state-input vectors.

11. A method for state transition matrix-based linear feedback shift register computations, said method comprising:

defining a linear feedback shift register such that an input bit thereof is a linear function of a previous state and external input bits and comprises more than one feedback as input

defining a polynomial associated with said linear feedback shift register;

computing a transition matrix associated with said linear feedback shift register, said transition matrix comprising a k-step transition matrix based on a single step state transition matrix;

computing an output generating matrix based on said polynomial associated with said linear feedback shift register;

combining said transition matrix and output matrix to form a combined transition matrix;

reducing a size of said combined transition matrix;

removing columns from said transition matrix;

multiplying transition matrix by at least one state input vector; and

computing an XOR operation between the result of multiplying said transition matrix and said at least one state input vectors wherein a size of said k-step transition matrix is increased from L*(L+k) to k*(L+k), but said output generating matrix is reduced from k*(L+k) to zero, thereby providing an improved speedup capability for calculating the next state and/or output of said linear feedback shift register.

12. The method of claim 11 further comprising: utilizing said linear feedback shift register in combination with a cyclic redundancy checking device.

13. The method of claim 11 further comprising associating one feedback term with said polynomial.

14. The method of claim 13 further comprising:

augmenting said transition matrix, by adding extra rows to said transition matrix;

multiplying said transition matrix by said at least one state input vector; and

iterating said steps until a plurality of state bits are produced or all input bits are consumed.

15. The method of claim 14 further comprising: utilizing said linear feedback shift register in combination with a gold sequence scrambler.

16. The method of claim 14 , wherein the output of said linear feedback shift register produces an output comprising said plurality of state bits.

17. The method of claim 13 , wherein there is more than one feedback term associated with said polynomial.

18. The method of claim 17 further comprising: utilizing said linear feedback shift register in combination with a turbo encoder.