Method for updating a linear feedback shift register of code generator

• US 6,665,692 B1
• Filed: 05/09/2000
• Issued: 12/16/2003
• Est. Priority Date: 05/10/1999
• Status: Expired due to Term

• Current Assignee: Nokia Technologies Oy (Nokia Corporation)
• Original Assignee: Nokia Mobile Phones UK Limited (Nokia Corporation)
• Inventors: Nieminen, Esko
• Primary Examiner(s): NGO, CHUONG D
• Application Number:
  US09/567,830
• Time in Patent Office: 1,316 Days
• Field of Search: 708/250, 708/251, 708/252, 708/253, 708/254, 708/255, 708/256
• US Class Current: 708/250
• CPC Class Codes: G06F 7/584 using finite field arithmetic, e.g. using a linear feedback shift register
• CPC Class Codes: H04B 1/70756 Jumping within the code, i.e. masking or slewing H04B1/70758 takes precedence
• CPC Class Codes: H04J 13/10 Code generation

Abstract

The invention relates to three different methods for updating a linear feedback shift register of a code generator, and code generators applying the methods. In the basic method a Galois-type linear feedback shift register of a code generator is updated to a target state which is at a known offset from a unit state. The basic method comprises the following: (302) generating a binary offset number illustrating the offset; (304) generating a counter showing the number of bits in the binary offset number; (306) initializing a temporary state with the unit state; (308) iterating as long as the counter value is higher than zero: (310) multiplying the temporary state by itself by applying a Galois Field multiplication; (312) shifting the temporary state one state forward from the current temporary state if the value of the bit shown by the counter is one; and (314) decrementing the counter value by one; (316) in the end, when the counter has reached the value zero, setting the temporary state as the target state. The described basic method is also employed in methods for updating a Galois-type/Fibonacci-type linear feedback shift register of a code generator to a new state which is at a known offset from a current state.

Claims

1. A method for updating a Galois-type linear feedback shift register of a code generator to a new state which is at a known offset from a known current state, comprising:

generating a binary offset number illustrating the offset;

generating a counter showing the number of bits in the binary offset number;

initializing a temporary state with a unit state;

iterating as long as the value of the counter is higher than zero;

applying a Galois Field multiplication to multiply the temporary state by itself;

shifting the temporary state one state forward from the current temporary state if the value of the binary offset number bit shown by the counter is one; and

decrementing the counter value by one;

in the end, when the counter has reached the value zero, performing a Galois Field multiplication between the temporary state and the current state, and setting the state obtained as a result of the multiplication as the new state.

2. A method according to claim 1, wherein the Galois Field multiplication between a first state and a second state is performed as follows:

if the value of the element corresponding to the least significant bit in the first state is one, the second state is placed in the result state, otherwise zero is placed in the result state;

iterating for each first state element in turn, starting from the element following the element corresponding to the least significant bit;

shifting the feedback shift register of the second state one state forward; and

if the value of the first state element to be processed is one, performing a Galois Field summation between the result state and the second state, and placing the state obtained as a result of the summation as the result state.

3. A method according to claim 2, wherein the Galois Field summation is carried out by applying an XOR operation.

4. A method according to claim 2 wherein the first state is the temporary state and the second state is the current state.

5. A method according to claim 2 wherein the first state is the temporary state and the second state is the temporary state.

6. A method according to claim 1, wherein a code generated by means of the linear feedback shift register is a code of a radio system applying code division multiple access.

7. A method for updating a Fibonacci-type linear feedback shift register of a code generator to a new state which is at a known offset from a known current state, comprising:

generating a binary offset number illustrating the offset;

generating a counter showning the number of bits in the binary offset number;

initializing a Galois-type temporary state with a unit state;

iterating as long as the value of the counter is higher than zero;

applying a Galois Field multiplication to multiply the temporary state by itself;

shifting the temporary state one state forward from the current temporary state if the value of the binary offset number bit shown by the counter is one; and

decrementing the counter value by one;

in the end, when the counter has reached the value zero, performing a Galois Field multiplication between the Galois-type temporary state and the Fibonacci-type current state, and setting the state obtained as a result of the multiplication as the new state of the Fibonacci-type.

8. A method according to claim 7, wherein the Galois Field multiplication between the Galois-type state and the Fibonacci-type state is performed as follows:

initializing the temporary state with the Galois-type state;

performing an AND operation between the temporary state and the Fibonacci state, and performing an XOR operation between all the bits obtained as a result of the AND operation, and placing the bit obtained as a result of the XOR operation into the result state as the rightmost, not yet calculated element;

if all the elements in the result state have been calculated, completing the multiplication process, otherwise shifting the temporary state to the next Galois-type state and continuing the multiplication from the second process step.

9. A code generator in a radio system comprising:

means for generating a binary offset number illustrating a known offset from a known current state of a Galois-type linear feedback shift register to a new state;

means for generating a counter showing the number of bits in the binary offset number;

means for initializing a temporary state with a unit state;

means for iterating the operation of subsequent means as long as the counter value is higher than zero;

means for applying a Galois Field multiplication to multiply the temporary state by itself;

means for shifting the temporary state one state forward from the current temporary state if the value of the binary offset number bit shown by the counter is one; and

means for decrementing the counter value by one;

means for multiplying the temporary state and the current state by applying the Galois Field multiplication, and for setting the state obtained as a result of the multiplication as the new state when the counter has reached the value zero.

10. A code generator according to claim 9, wherein the means for performing the Galois Field multiplication between a first state and a second state comprises:

means for placing the second state in the result state if the value of the element corresponding to the least significant bit in the first state is one, otherwise for placing zero into the result state;

means for iterating the operation of the subsequent means for each first state element, starting from the element following the element corresponding to the least significant bit;

means for shifting the feedback shift register of the second state one state forward; and

means for performing a Galois Field summation between the result state and the second state if the value of the first state element to be processed is one, and for placing the state obtained as a result of the summation to the result state.

11. A code generator according to claim 10 wherein the first state is the temporary state and the second state is the current state.

12. A code generator according to claim 10 wherein the first state is the temporary state and the second state is the temporary state.

13. A code generator according to claim 10, wherein the means for performing a Galois Field summation use an XOR operation.

14. A code generator according to claim 9, wherein the radio system is a radio system applying code divisional multiple access.

15. A code generator in a radio system comprising:

means for generating a binary offset number illustrating a known offset from a known current state of a Fibonacci-type linear feedback shift register to a new state;

means for generating a counter showing the number of bits in the binary offset number;

means for initializing a Galois-type temporary state with a unit state;

means for iterating the operation of subsequent means as long as the counter value is higher than zero;

means for applying a Galois Field multiplication to multiply the temporary state by itself;

means for shifting the temporary state one state forward from the current temporary state if the value of the binary offset number bit shown by the counter is one; and

means for decrementing the counter value by one;

means for multiplying the Galois-type temporary state and the Fibonacci-type current state by applying the Galois Field multiplication, and for setting the state obtained as a result of the multiplication as the new state of the Fibonacci-type when the counter has reached the value zero.

16. A code generator according to claim 15, wherein the means for performing a Galois Field multiplication between a Galois-type state and a Fibonacci-type state comprise:

means for initializing a temporary state with a Galois-type state;

calculation means for performing an AND operation between the temporary state and the Fibonacci-type state, and to perform an XOR operation between all the bits obtained as a result of the AND operation, and to place the bit obtained as a result of the XOR operation into the result state as the rightmost, not yet calculated element;

means for completing the multiplication process if all result state elements have been calculated;

means for shifting the temporary state to the next Galois-type state and to continue the multiplication process by applying the calculation means if all the result state elements have not been calculated.