Method of mask calculation for generation of shifted...

Details Method of mask calculation for generation of shifted... Method of mask calculation for generation of shifted...

1999-12-06

2003-02-25

Malzahn, David H. (Department: 2121)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06526427

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to spread-spectrum communications, in general, and to calculations of masks for generation of shifted pseudo-noise (PN) sequences, in particular.
BACKGROUND OF THE INVENTION
In direct sequence spread-spectrum communications, a pseudo-noise (PN) sequence is used for spreading an information signal. The PN sequence, is typically a long binary sequence. In the IS-95 standard, for example, the length of the PN sequence is 2
15
. In the wideband code division multiple access (W-CDMA) standard, the lengths are 2
18
and 2
42
.
One technique for generating PN sequences is through the use of a maximum length shift register, as shown in
FIG. 1
, to which reference is now made. A linear feedback shift register
100
having R bits is connected in a feedback loop to a XOR unit
102
. Initially, shift register
100
contains an R-bit integer. A single bit B is output from shift register
100
with every tick of a clock (not shown), The output bit B may be, for example, the least significant bit of shift register
100
, or may be a more complex combination of the bits of shift register
100
. XOR unit
102
is connected to particular bits of shift register
100
in a feedback loop.
In the example shown in
FIG. 1
, for each tick of the clock: a) XOR unit
102
performs a XOR operation an the contents of bit
2
, bit
3
and bit (R−1) of shift register
100
, b) shift register
100
is shifted to the right by one bit, outputting as output bit B the contents of bit
1
, and c) the result of the XOR operation is stared in bit R of shift register
100
. The procedure is repeated for each tick of the clock, thereby producing a sequence X of output bits B.
The R-bit integer stored in shift register
100
at any given time is known as the “state” of shift register
100
. Clearly there are 2
R
possible states of shift register
100
. As the clock marks 2
R
−1 ticks, shift register
100
cycles through 2
R
−1 possible states (excluding the zero state). The resultant sequence X of output bits B , with a zero added, has a periodicity of 2
R
, is said to have a length of 2
R
, and is known as a maximal length linear binary sequence. For some feedback arrangements, however, the sequence is not a maximal length sequence. Rather, for these arrangements, shift register
100
cycles through only some of the 2
R
−1 possible states, resulting in a sequence X of output bits B having a periodicity of less than 2
R
.
The sequence X satisfies a polynomial, for example h(X)=X
18
+X
7
+1=0, where X
0
≡1 is the unshifted sequence X, X
7
is the sequence X shifted by a delay of 7, X
18
is the sequence X shifted by a delay of 18, and the summation is a XOR-operation. What the polynomial represents is the fact that if the sequence X and its shifted versions for delays of 7 and 18 are XOR added, the result is a sequence of all zero bits. The polynomial h(X) is chosen so that the sequence X is noisy. However, since the sequence X is periodic and not truly noisy, the sequence is called a pseudo-noise (PN) sequence.
In direct sequence spread-spectrum communications, it is frequently necessary to calculate in real-time a shifted version of the PN sequence, where the shift, also known as the “delay”, is unknown prior to real-time and may be of the order of the size of 2
R
. As is known in the art, calculation of a shifted version of a PN sequence is accomplished in hardware using a mask.
FIG. 2
, to which reference is now made, is a schematic illustration of a prior art hardware system for calculating an arbitrary shifted version of a PN sequence. As in
FIG. 7
, shift register
200
has R bits and is connected to a XOR unit
202
in a feedback loop. The R bits of shift register
200
are connected via R switches
204
to a XOR unit
206
. A mask M(d) for a delay d indicates which of the switches
204
are closed and which are open. XOR unit
206
sums the contents of the bits whose switches
204
are closed and produces an output bit B′. For each tick of the clock, the contents of shift register
900
change according to the feedback loop, and the resulting output bit B′ produced by XOR unit
206
reflects this change. If the PN sequence comprising the output bits B is denoted S[n], the shifted PN sequence comprising the output bits B′ is denoted S[n−d].
Mask M(d) can be represented as a binary vector of length R, [c
R-1
(d) c
R-2
(d). . . c
i
(d) c
0
(d)], where c
1
(d) has a value of 1 when the ith switch should be closed and a value of 0 when the ith switch should be open.
Mask M(d) can also be represented as a polynomial. For example, the polynomial X
12
+X
5
+X
0
indicates that the switches for bits
12
,
5
and
0
of shift register
100
are closed, and all the other switches are open. In general, for an arbitrary delay d ,the mask M(d) that determines which of the switches to close and which to open in order to calculate the PN sequence that is shifted by the delay d is given by:
M
⁢
(
d
)
=
∑
i
=
0
R
-
1
⁢
c
i
⁢
(
d
)
⁢
X
′
,
where i is an index for the R switches and the R bits of the shift register, and c, (d) is as defined hereinabove, and X′ denotes the sequence X ,shifted by a delay of i.
The task of calculating an arbitrary shifted version of a PN sequence is therefore equivalent to the task of mask calculation. The goal is to find a method for calculating the mask for an arbitrary delay, even a large delay, quickly and with minimum use of valuable memory and power resources.
The most trivial solution would be to calculate in advance the mask for every one of the possible 2
R
delays, and to store the resulting 2
R
R-bit integers in memory. Then during online operation, when the arbitrary delay becomes known, the appropriate R-bit mask is read from the memory. Since R typically has a value of 15 or 18, this solution is impractical due to its requirement of a huge dedicated memory.
The articles “Generation of delayed replicas of maximal-length linear binary sequences”, S. H. Tsao,
Proc. Inst. Elec. Engrs
. (London) 111, No. 11, November 1964, pp. 1803-1807, and “Discussion on generation of delayed replicas of maximal length binary sequences”, P. D. Roberts, A. C. Davies and S. H. Tsao.
Proc. Inst. Elec. Engrs
. (London) 112, No. 4, April 1965, pp. 702-704, are among the earliest to deal with delays in shift registers. However, the methods described therein are not appropriate for handling large delays.
Algorithms that are capable of handling large delays are either matrix fast multiplication methods or polynomial fast division methods. For sparse matrices or sparse polynomials other methods based on this sparseness may be used in particular, the article “A simple technique for the determination of delayed maximal length binary sequences”, A. Miller, A. Brown and P. Mars,
IEEE Trans. Computers C
-26, No. 8, August 1977, pp. 808-811, describes a tree-like structure representation for trinomials, but this algorithm does not outperform fast polynomial division.
Matrix multiplication algorithms are based on the state machine representation of the shift register, as described in R. L. Peterson, R. E. Ziemer and D. E. Borth,
Introduction to Spread Spectrum Communications
, Prentice Hall, New Jersey (1995) and in “M-sequences: what they are and how they can be implemented”,
The April Spread Spectrum Sourcebook
, Appendix A, Publication No. 121 of the Radio Amateur's Library, The American Radio Relay League, USA. The multiplication process may be optimized by the so-called logarithmic (usually loge) route corresponding to the binary representation of the delay d , This is described in “Matrix method to determine shift-register connections for delayed pseudo-random binary sequences”, B. Ireland and J. Marshall,
Electron. Letters
, 4, No. 21, 1968, pp. 467-468 and in “M-sequences: what they are and how they can be implemented”,
The April Spread Spectrum Sourcebook
, Appendix A. Such algorithms have a num

Affiliated with

Also associated with

Rating

Method of mask calculation for generation of shifted... 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 of mask calculation for generation of shifted..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of mask calculation for generation of shifted... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3175065