Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2000-05-09
2003-12-16
Ngo, Chuong Dinh (Department: 2124)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S252000
Reexamination Certificate
active
06665692
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to methods for updating a Linear Feedback Shift Register of a code generator, and to code generators using the methods. The term ‘code’ refers to, for example, a pseudo-noise sequence used in a radio system, such as a spreading code or scrambling code of a radio system employing code division multiple access (CDMA), or another code (used for example in an encryption system).
BACKGROUND OF THE INVENTION
In radio systems employing code division multiple access radio resources are divided between a plural number of different users on a code-division basis. The payload of each user is spread on a wide frequency band (of five megaherz, for example) by multiplying the payload by a spreading code. The receiver can separate the signal it wants to receive by multiplying the received signal by the spreading code used. Portions of the spreading code are called chips, and in fact they are bits. A chip value can be expressed with zeros and ones, or as real numbers with ones and minus ones. Chip rate is typically significantly faster, over hundred times, for example, than payload rate.
In addition to spreading codes, codes known as scrambling codes can be used. They are not necessarily used for spreading the signal any more, but for scrambling the bits of the spread signal by multiplying each bit in the signal by the corresponding scrambling code bit. Scrambling codes can be extremely long, 2
41
−1 chips, for example.
The spreading codes used are normally as orthogonal as possible with respect to each other. Spreading codes can be obtained for example from a Hadamard matrix. A Hadamard matrix M
n
is an n×n matrix (where n is an even integer) composed of zeros and ones in such a way that any matrix line differs from any other matrix line exactly at an n/2 position. Consequently, one matrix line comprises only zeros, whereas the rest of the lines are composed of an equal number of zeros and ones. When n=2, the following Hadamard matrix is obtained:
M
2
=
[
0
0
0
1
]
(
1
)
A Hadamard matrix M
2n
is generated from the Hadamard matrix M
n
by the following relation:
M
2
n
=
[
M
n
M
n
M
n
M
_
n
]
(
2
)
where the matrix {overscore (M)}
n
is a complement of the matrix M
n
, i.e. the zeros are replaced by ones and ones by zeros. The matrix 1 thus provides the following:
M
4
=
[
0
0
0
0
0
1
0
1
0
0
1
1
0
1
1
0
]
(
3
)
Further, the matrix 3 provides the following:
M
8
=
[
0
0
0
0
0
0
0
0
0
1
0
1
0
1
0
1
0
0
1
1
0
0
1
1
0
1
1
0
0
1
1
0
0
0
0
0
1
1
1
1
0
1
0
1
1
0
1
0
0
0
1
1
1
1
0
0
0
1
1
0
1
0
0
1
]
(
4
)
If elements of the above described Hadamard matrices, i.e. zeros and ones, are represented by ones and minus ones, then the lines in the Hadamard matrices are orthogonal with respect to each other. If desired, the values could also be inverted, i.e. zeros could be replaced by ones and ones by zeros, but that would not change the properties of the matrix. Hence, the matrix 1 could also be presented in formats such as
M
2
[
1
1
1
0
]
,
M
2
=
[
1
1
1
-
1
]
Each matrix line forms one spreading code. The length of the spreading code varies according to the desired spreading factor. The spreading codes can be numbered for example by indicating the code class of the spreading code and its ordinal number in the code class concerned. The code class can be obtained by the following equation: two to the power of code class equals the length of the spreading code, in other words, the code class is a binary logarithm of the spreading code. The matrix 4, for example, thus includes the following spreading codes (the subindex denotes the code class and the number in parenthesis is the ordinal number):
SPREADINGCODE
3
(0)={0,0,0,0,0,0,0,0}
SPREADINGCODE
3
(1)={0,1,0,1,0,1,0,1}
SPREADINGCODE
3
(2)={0,0,1,1,0,0,1,1}
SPREADINGCODE
3
(3)={0,1,1,0,0,1,1,0}
SPREADINGCODE
3
(4)={0,0,0,0,1,1,1,1}
SPREADINGCODE
3
(5)={0,1,0,1,1,0,1,0}
SPREADINGCODE
3
(6)={0,0,1,1,1,1,0,0}
SPREADINGCODE
3
(7)={0,1,1,0,1,0,0,1}
According to prior art, all short spreading codes are stored into a transceiver memory. For a code of a class 8, for example, this means that 256 different codes of 256 chips are stored into the memory, the memory space needed being 256×256 bits, i.e. a total of 65536 bits. Shorter spreading codes can be generated from the stored long codes, therefore spreading codes of lower code classes need not be separately stored.
Spreading codes can be remarkably long, 2
41
−1 chips for example. A technical problem that arises is how to generate the code in real time, because one and the same sequence is typically used, only different transceivers use the sequence at different stages. Ideally, the code sequence to be generated would be fully random; this is, however, not practical because both the transmitter and the receiver have to be able to generate the code sequence to be used, applying even the same timing, i.e. phase.
The code is generated by means of a code generator, for example a generator using a linear feedback shift register. WO Publication 96/36137 describes a linear feedback shift register that is used for generating what is known as an m sequence (maximal length sequence) to provide a pseudo noise sequence to be used as a code, the sequence being iterated after a sequence of 2
N
−1, where N represents the number of elements in the linear feedback shift register. The initial state is always known in linear feedback shift registers, but a problem arises from how to shift from the known initial state to a new, unknown target state which is at a known offset. In the solution described in the above publication a conversion matrix corresponding to each shift, or at least to each shift corresponding to a power of two, is stored, the conversion matrix indicating how each initial state element needs to be converted to provide target state elements. Consequently, the amount of bits stored for a spreading code of 2
41
−1 chips, for example, is 41×41×41 bits (the number of different powers of two × the number of linear feedback shift register elements × the length of the linear feedback shift register), i.e. 68921 bits in total.
U.S. Pat. No. 5,835,528 discloses how a feedback shift register is updated from a known current state to a new state which is at a known offset. The solution involves storing pre-calculated states that are used for updating. The solution requires memory for storing the states calculated in advance, and only states that are at an offset determined by these states can be updated.
BRIEF DESCRIPTION OF THE INVENTION
An object of the invention is to provide a method for updating a linear feedback shift register, wherein the method employs memory only a little and provides efficient calculation. This is achieved with a method for updating a Galois-type linear feedback shift register of a code generator to a target state which is at a known offset from a unit state. The method comprises the following: 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 the unit state; iterating as long as the counter value 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 a 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, setting the temporary state as the target state.
The invention also relates to 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. The method comprises the following: generating a binary offset number illustrating the offset; generating a counter showing the number
Ngo Chuong Dinh
Nokia Mobile Phones Ltd.
Perman & Green LLP
LandOfFree
Method for updating a linear feedback shift register of code... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for updating a linear feedback shift register of code..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for updating a linear feedback shift register of code... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3159898