Pulse or digital communications – Spread spectrum – Direct sequence
Reexamination Certificate
2001-07-13
2003-10-07
Ghayour, Mohammad H. (Department: 2631)
Pulse or digital communications
Spread spectrum
Direct sequence
C375S130000, C375S152000, C370S335000
Reexamination Certificate
active
06631158
ABSTRACT:
FIELD OF INVENTION
The invention relates to a method for updating a linear feedback shift register of a code generator from a known state to a new state, and to a code generator using the method. ‘Code’ refers to a pseudo-noise sequence used in a radio system, for instance to a long spreading code or scrambling code in a radio system employing code division multiple access (CDMA).
BACKGROUND
In radio systems employing code division multiple access, the radio resource is divided on a code-division basis between the various users. The payload of each user is spread onto a wide frequency band, of five megahertz, for instance, by multiplying the payload with a spreading code. A receiver distinguishes the signal it wants by multiplying the received signal by the spreading code used to spread it. Parts of a spreading code are called chips which are, in fact, bits. The value of a chip can be marked by a zero and a one, or in real numbers by a one and a minus one. The chip rate is typically significantly faster, over a hundred times faster, for instance, than the payload rate.
In addition to spreading codes, codes known as scrambling codes can also be used. The scrambling codes do not necessarily spread the signal any more, but scramble the bits of a spread signal by multiplying each bit in the signal with the corresponding scrambling code bit. Scrambling codes can be extremely long, 2
41
−1 chips long, for instance.
The spreading codes used are usually as orthogonal as possible with respect to each other. Spreading codes are obtained from a Hadamard matrix, for instance. A Hadamard matrix M
n
is an n×n matrix (n is an even integer) made of zeros and ones so that any matrix line differs from any other matrix line exactly at an n/2 position. One matrix line thus contains only zeros, whereas the rest of the lines contain an equal number of zeros and ones. When n=2, the following Hadamard matrix is obtained:
M
2
=
[
0
0
0
1
]
(
1
)
From the Hadamard matrix M
n
, the Hadamard matrix M
2n
is generated by the following relation:
M
2
n
=
[
M
n
M
n
M
n
M
_
n
]
(
2
)
where matrix {overscore (M)}
n
is a complement of matrix M
n
, i.e. the zeros have been replaced with ones and the ones with zeros. Thus, matrix 1 provides:
M
4
=
[
0
0
0
0
0
1
0
1
0
0
1
1
0
1
1
0
]
(
3
)
Further, maxtrix 3 provides:
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 the elements, that is, zeros and ones, of the above Hadamard matrices are represented by ones and minus ones, then the lines in the Hadamard matrix are orthogonal with respect to each other. If desired, the values could also be inverted, i.e. the zeros changed to ones and the ones to zeros, but this does not change the properties of the matrix. For instance, matrix 1 could also be presented as:
M
2
=
[
1
1
1
0
]
,
M
2
=
[
1
1
1
-
1
]
Each matrix line forms one spreading code. The length of a spreading code varies according to the desired spreading factor. Spreading codes can be numbered, for instance, by indicating the code class of the spreading code and its ordinal number in said code class. The code class can be obtained by the following equation: two to the power of the code class equals the length of the spreading code, i.e. the code class is a binary logarithm of the spreading code. Thus, matrix 4, for instance, has the following spreading codes (subindex denotes the code class and the ordinal number is in brackets):
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 the memory of a transceiver. This means that for a code class 8 code, for instance, 256 different 256-chip-long codes are stored into the memory, i.e. the memory requirement is 256×256 bits, which totals 65536 bits. Shorter spreading codes can be generated from the stored long codes, which means that the spreading codes of lower code classes need not be separately stored.
Spreading codes can be extremely long, 2
21
−1 chips long, for instance. This creates the technical problem of being able to generate said code in real-time, since the same sequence is typically used, but different transmitters use it at different stages. Ideally, the generated code sequence would be completely random, but this is not practical, because both the transmitter and the receiver must be able to generate the code sequence used and with the same timing, i.e. phase, too.
Code is generated with a code generator, with a code generator using a linear feedback shift register, for instance. Publication WO 96/36137 discloses a linear feedback shift register that is used for generating an m-sequence (maximal length sequence) to provide a pseudo-noise sequence to be used as a code, the sequence being iterated after 2
N
−1 cycles, where N represents the number of elements in the feedback shift register. The initial state is always known in linear feedback shift registers, but a problem arises from how to jump from the initial state to an unknown new state. In the solution disclosed in said publication, a transformation matrix corresponding to each jump, or at least to each jump corresponding to a power of two, is stored, which transformation matrix indicates how each element of the initial state should be transformed to obtain the elements of the new state. Thus, for instance, for a spreading code of 2
41
−1 chips, 41×41×41 (the number of the powers of two×the number of the elements in the feedback shift register×the length of the feedback shift register) bits are stored, i.e. a total of 68921 bits.
BRIEF DESCRIPTION
It is an object of the invention to develop a method for generating a spreading code when necessary, whereby memory is not needed for storing each spreading code, and saving memory space in comparison with known methods. This object is achieved by the method disclosed in the following. The method in question is a method for updating the linear feedback shift register of a code generator from a known state to a new state, comprising defining the jumps corresponding to the different powers of two for shifting from a known state to a new state. The method also comprises generating in each jump the feedback shift register obtained as a result of said jump as follows: generating the value of one element of the obtained feedback shift register from the previous state and the pre-stored mask register corresponding to said element, while the mask register determines the elements of the feedback shift register of the previous state, using which elements said element value is generated, and repeating the generation of the value of one feedback shift register element for each remaining obtained feedback shift register element by shifting the mask register to the position of said remaining element and by generating the value of said remaining element of the obtained feedback shift register from the previous state and the shifted mask register.
The invention also relates to a code generator of a radio system, comprising means for defining the jumps corresponding to the different powers of two for updating the linear feedback shift register of a code generator from a known state to a new state. The code generator also comprising: means for generating in each jump the feedback shift register obtained as a result of said jump, comprising means for generating the value of one element of the obtained feedback shift register from the previous state and the pre-stored mask register corresponding to said obtained element, while the mask register determines the elements of the feedback shift
Lipponen Veli
Moilanen Pentti
Al-Beshrawi Tony
Ghayour Mohammad H.
Nokia Networks Oy
LandOfFree
Method for updating 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 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 linear feedback shift register of code... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3131871