# Patent

## Title
All-lag spread-spectrum correlators with rotating references

## Abstract

An all-lag rotating-reference correlator correlates a received spread-spectrum signal with a rotating reference code, and produces in each sampling instance N correlation lags corresponding to the correlation of the received signal with 0, 1, . . . , N−1 lags (or delays) of the rotating reference code, wherein N is the length of the rotating reference code. The rotating reference code is time-variant and is generated by a rotation of a basic reference code. The received signal, possibly embedded in noise and interference, consists of periodic replicas of the basic reference code with or without data modulation. The first embodiment of the present invention describes a method and apparatus of an all-lag rotating-reference correlator which is applicable to situations where data modulation is not present in the received signal. The second embodiment of the present invention describes a method and apparatus of an all-lag rotating-reference correlator which is applicable for situations where data modulation is present in the received signal. Corresponding methods and apparatus are also described when only a number of selected correlation lags are required to be generated. Each apparatus comprises storage means for storing spread-spectrum signal samples, subtraction means, a plurality of multiplication means each of which computes the multiplication result for the output of subtraction means and an element of rotating reference code, storage means for storing correlation lags, and a plurality of addition means.

## Background
This application claims the benefit of Provisional Application No. 60/141,732, filed Jun. 30, 1999.


BACKGROUND
1. Field of the Invention
The present invention generally relates to spread-spectrum (SS) systems. In particular, the present invention relates to methods systems, and apparatus for correlating a received SS signal with all lags of a rotating reference code sequence and producing all correlation lags at a sampling instant.
2. Description of the Related Art
SS techniques have many applications such as multiple-access communications, secure communications, channel sounding, distance measurement and target identification using radars and sonars, and navigation using GPS and GLONASS. One of the essential elements in the implementation of SS systems is a correlator. A correlator is required at a SS receiver to initially acquire the incoming SS signal, as well as to perform other tasks such as code tracking, symbol and carrier clock recovery, demodulation of information systems, and channel estimation.
Commonly used forms of correlators include serial correlators, parallel correlators, banks of serial correlators, and all-lag correlators. An all-lag correlator correlates a stream of incoming data samples with 0, 1, . . . , N−1 lags of an N-length reference code sequence and produces a stream of all-lag even- or odd-correlation at a rate equal to the rate of incoming data samples. Since more correlation information is provided by all-lag correlators than other commonly used forms of correlators, some applications can take advantage of this additional correlation information.
Let dn denote the stream of incoming data samples and {c0, c1, , CN−1} be the reference code sequence. An all-lag correlator generates a stream of all-lag even-correlation vectors, r′n, or a stream of all-lag odd-correlation vectors, {overscore (r)}′n, every sampling instant, where r′n=[r′0,n,r′1,n, . . . ,r′N−1,n]T and {overscore (r)}′n=[{overscore (r)}′0,n,{overscore (r)}′1,n, . . . ,{overscore (r)}′N−1,n]T are given by

r′n=Adn  (1) 

and

{overscore (r)}′n=Ādn  (2) 

In the expressions, r′m,n and {overscore (r)}′m,n denote respectively the mth even- and odd-correlation lags obtained at time n, 



  
    
      
        A
        =
        
          [
          
            
              
                
                  c
                  0
                
              
              
                
                  c
                  1
                
              
              
                
                  c
                  2
                
              
              
                ...
              
              
                
                  c
                  
                    N
                    -
                    2
                  
                
              
              
                
                  c
                  
                    N
                    -
                    1
                  
                
              
            
            
              
                
                  c
                  
                    N
                    -
                    1
                  
                
              
              
                
                  c
                  0
                
              
              
                
                  c
                  1
                
              
              
                ...
              
              
                
                  c
                  
                    N
                    -
                    3
                  
                
              
              
                
                  c
                  
                    N
                    -
                    2
                  
                
              
            
            
              
                
                  c
                  
                    N
                    -
                    2
                  
                
              
              
                
                  c
                  
                    N
                    -
                    1
                  
                
              
              
                
                  c
                  0
                
              
              
                ...
              
              
                
                  c
                  
                    N
                    -
                    4
                  
                
              
              
                
                  c
                  
                    N
                    -
                    4
                  
                
              
            
            
              
                ⋮
              
              
                ⋮
              
              
                ⋮
              
              
                ⋰
              
              
                ⋮
              
              
                ⋮
              
            
            
              
                
                  c
                  2
                
              
              
                
                  c
                  3
                
              
              
                
                  c
                  4
                
              
              
                ...
              
              
                
                  c
                  0
                
              
              
                
                  c
                  1
                
              
            
            
              
                
                  c
                  1
                
              
              
                
                  c
                  2
                
              
              
                
                  c
                  3
                
              
              
                ...
              
              
                
                  c
                  
                    N
                    -
                    1
                  
                
              
              
                
                  c
                  0
                
              
            
          
          ]
        
      
    
    
      
        (
        3
        )
      
    
  
  
    
      and
    
    
      
         
      
    
  
  
    
      
        
          A
          _
        
        =
        
          [
          
            
              
                
                  c
                  0
                
              
              
                
                  c
                  1
                
              
              
                
                  c
                  2
                
              
              
                ...
              
              
                
                  c
                  
                    N
                    -
                    2
                  
                
              
              
                
                  c
                  
                    N
                    -
                    1
                  
                
              
            
            
              
                
                  -
                  
                    c
                    
                      N
                      -
                      1
                    
                  
                
              
              
                
                  c
                  0
                
              
              
                
                  c
                  1
                
              
              
                ...
              
              
                
                  c
                  
                    N
                    -
                    3
                  
                
              
              
                
                  c
                  
                    N
                    -
                    2
                  
                
              
            
            
              
                
                  -
                  
                    c
                    
                      N
                      -
                      2
                    
                  
                
              
              
                
                  -
                  
                    c
                    
                      N
                      -
                      1
                    
                  
                
              
              
                
                  c
                  0
                
              
              
                ...
              
              
                
                  c
                  
                    N
                    -
                    4
                  
                
              
              
                
                  c
                  
                    N
                    -
                    4
                  
                
              
            
            
              
                ⋮
              
              
                ⋮
              
              
                ⋮
              
              
                ⋰
              
              
                ⋮
              
              
                ⋮
              
            
            
              
                
                  -
                  
                    c
                    2
                  
                
              
              
                
                  -
                  
                    c
                    3
                  
                
              
              
                
                  -
                  
                    c
                    4
                  
                
              
              
                ...
              
              
                
                  c
                  0
                
              
              
                
                  c
                  1
                
              
            
            
              
                
                  -
                  
                    c
                    1
                  
                
              
              
                
                  -
                  
                    c
                    2
                  
                
              
              
                
                  -
                  
                    c
                    3
                  
                
              
              
                ...
              
              
                
                  -
                  
                    c
                    
                      N
                      -
                      1
                    
                  
                
              
              
                
                  c
                  0
                
              
            
          
          ]
        
      
    
    
      
        (
        4
        )
      
    
  




are N×N matrices, and

dn=[dn−(N−1), dn−(N−2), . . . , dn−1, dn]T  (5) 

is a data vector containing the N most recent data samples. Correlation information in r′n and {overscore (r)}′n, when processed, can be extracted for various purposes. The information provided by r′n is useful when the SS signal is composed of periodic repetition of the reference code sequence without data modulation. The information contained in r′n and {overscore (r)}′n is applicable when the SS signal is a data signal modulated with the entirety of the reference code.

Despite various advantages, the correlation peak of an all-lag correlator that generates r′n or {overscore (r)}′n shifts from output to output as the correlation vector is updated by newly received data samples. Shifting of the peak position increases the subsequent signal processing requirement for extracting useful information provided by the all-lag correlation. It is desirable to keep the peak position fixed in order to reduce the posterior signal processing requirement. Furthermore, keeping the peak position fixed enables more convenient manipulation of the correlation information in certain applications, such as estimation of the multipath channel profile in wireless communications and ranging in radar systems.
It is possible to overcome the peak-shifting problem by using all-lag correlators that employ rotating reference code sequences. Herein the correlators are referred to as all-lag rotating-reference correlators, and are different from the ones for generating r′n and {overscore (r)}′n, in which fixed reference codes are used. An all-lag rotating-reference correlator that generates at time n an all-lag even-correlation vector rn=[r0,n,r1,n, . . . ,rN−1,n]T, wherein rm,n is the mth even-correlation lag, is constructed as follows.

Define an N×N shift matrix S, where 



  
    
      
        S
        =
        
          
            [
            
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  ...
                
                
                  0
                
                
                  1
                
              
              
                
                  1
                
                
                  0
                
                
                  0
                
                
                  ...
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  1
                
                
                  0
                
                
                  ...
                
                
                  0
                
                
                  0
                
              
              
                
                  ⋮
                
                
                  ⋮
                
                
                  ⋮
                
                
                  ⋰
                
                
                  ⋮
                
                
                  ⋮
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  ...
                
                
                  0
                
                
                  0
                
              
              
                
                  0
                
                
                  0
                
                
                  0
                
                
                  ...
                
                
                  1
                
                
                  0
                
              
            
            ]
          
          .
        
      
    
    
      
        (
        6
        )
      
    
  




Then rn is computed by

rn=Cndn  (7) 

where dn is a data vector given by equation. (5), and Cn is an N×N matrix constructed by

C0=A 

Cn+1=SCn, n≧0  (8) 

It follows that

Cn=S′′A, n≧0  (9) 

An all-lag rotating-reference correlator that generates at time n an all-lag odd-correlation vector {overscore (r)}n=[{overscore (r)}0,n, {overscore (r)}1,n, . . . , {overscore (r)}N−1,n]T, wherein {overscore (r)}m,n, is the mth odd-correlation lag, is constructed as follows.

Define an N×N shift matrix 



  
    
      
        
          S
          _
        
        =
        
          [
          
            
              
                0
              
              
                0
              
              
                0
              
              
                ...
              
              
                0
              
              
                
                  -
                  1
                
              
            
            
              
                1
              
              
                0
              
              
                0
              
              
                ...
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                1
              
              
                0
              
              
                ...
              
              
                0
              
              
                0
              
            
            
              
                ⋮
              
              
                ⋮
              
              
                ⋮
              
              
                ⋰
              
              
                ⋮
              
              
                ⋮
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                ...
              
              
                0
              
              
                0
              
            
            
              
                0
              
              
                0
              
              
                0
              
              
                ...
              
              
                1
              
              
                0
              
            
          
          ]
        
      
    
    
      
        (
        10
        )
      
    
  




Then {overscore (r)}n is given by

{overscore (r)}n={overscore (C)}ndn  (11) 

where {overscore (C)}n is recursively generated by

{overscore (C)}0=Ā

{overscore (C)}n+1={overscore (SC)}n, n≧0  (12) 

Therefore,

{overscore (C)}n={overscore (S)}nĀ, n≧0  (13) 

It can be shown that the reference code used to compute rn and {overscore (r)}n is time-variant and is a rotation of a basic reference code c0, c1, , cN−1. The information provided by rn is useful when the SS signal is composed of periodic repetition of the basic reference code sequence without data modulation. The information altogether contained in rn and {overscore (r)}n is applicable when the SS signal is a data signal modulated with the entirety of the basic reference code.

The sequence of sets of all even-correlation lags, rn, is generated at a rate equal to the rate of incoming SS signal samples dn. It is obvious that a means for generating an all-lag even-correlation sequence can be implemented by means of N parallel correlators each of which, at time n, correlates SS signal samples with the rotating reference code given by a row of Cn. However, none of the prior art teaches or suggests a method or apparatus for correlating a received SS signal with a rotating reference code using one correlator (a) which has the number of outputs equal to N and (b) whose outputs at one sampling instant are all even-correlation lags for the incoming SS signal samples and are produced at a rate equal to the rate of the incoming SS signal samples.
In some applications, it is desirable to generate only part of N even-correlation lags every sampling instant. For example, consider the situation aabove. M (M<N) selected even-correlation lags are generated. It is obvious that a means for generating an M-even-correlation sequence can be implemented by means of M parallel correlators each of which, at time n, correlates SS signal samples with the rotating reference code given by a specified row of Cn. However, none of the prior art teaches or suggests a method or apparatus for correlating a received SS signal with a rotating reference code using one correlator (a) which has the number of outputs equal to M and (b) whose outputs at one sampling instant are M even-correlation lags for the incoming SS signal samples and are produced at a rate equal to the rate of the incoming SS signal samples.
The sequence of sets of all even-correlation lags, rn, and the sequence of sets of all odd-correlation lags, {overscore (r)}n, are generated at a rate equal to the rate of incoming SS signal samples dn. It is obvious that a means for generating an all-lag even-correlation sequence can be implemented by means of N parallel correlators each of which, at time n, correlates SS signal samples with the rotating reference code given by a row of Cn. It is also obvious that a means for generating an all-lag odd-correlation sequence can be implemented by means of N parallel correlators each of which, at time n, correlates SS signal samples with a sequence specified by a row of {overscore (C)}n. However, none of the prior art teaches or suggests a method or apparatus for correlating a received SS signal with a rotating reference code using one correlator (a) which has the number of outputs equal to N and (b) whose outputs at one sampling instant are all even-correlation lags for the incoming SS signal samples and are produced at a rate equal to the rate of the incoming SS signal samples. In addition, none of the prior art teaches or suggests a method or apparatus for correlating a received SS signal with a rotating reference code using one correlator (a) which has the number of outputs equal to N and (b) whose outputs at one sampling instant are all odd-correlation lags for the incoming SS signal samples and are produced at a rate equal to the rate of the incoming SS signal samples.
In some applications, it is desirable to generate only part of N even- and N odd-correlation lags every sampling instant. For example, consider the situation where M selected even- and M selected odd-correlation lags (M<N) are generated. It is obvious that a means for generating an M-even-correlation sequence can be implemented by means of M parallel correlators each of which, at time n, correlates SS signal samples with the rotating reference code given by a specified row of Cn. It is also obvious that a means for generating an M-odd-correlation sequence can be implemented by means of M parallel correlators each of which, at time n, correlates SS signal samples with a sequence specified by a specified row of {overscore (C)}n. However, none of the prior art teaches or suggests a method or apparatus for correlating a received SS signal with a rotating reference code using one correlator (a) which has the number of outputs equal to M and (b) whose outputs at one sampling instant are M even-correlation lags for the incoming SS signal samples and are produced at a rate equal to the rate of the incoming SS signal samples. In addition, none of the prior art teaches or suggests a method or apparatus for correlating a received SS signal with a rotating reference code using one correlator (a) which has the number of outputs equal to M and (b) whose outputs at one sampling instant are M odd-correlation lags for the incoming SS signal samples and are produced at a rate equal to the rate of the incoming SS signal samples.
SUMMARY OF THE INVENTION
A first object of the invention is to provide a method and apparatus including a simple correlator for computing or generating all N even-correlation lags between a rotating reference code and a received SS signal, wherein (a) the rotating reference code is time-variant and is generated by a rotation of a basic reference code, (b) the SS signal is a signal, possibly corrupted by noise and interference, composed by means of periodic repetition of a pseudo-noise (PN) sequence, and (c) the correlator has N outputs and generates all N even-correlation lags once every sampling instant. Such an apparatus can be used for SS systems employing, for example, binary-phase-shift-keying (BPSK) signals, or code-phase-shift-keying (CPSK) signals, each without data modulation.,
A second object of the invention is to provide an apparatus including a plurality of correlators, for correlating a plurality of streams of SS signal samples with a rotating reference code, wherein (a) the rotating reference code is time-variant and is generated by a rotation of a basic reference code, (b) the plurality of streams of SS signal samples are generated from a received SS signal, which is a signal, possibly corrupted by noise and interference, composed by means of periodic repetition of a PN sequence, and (c) each of the correlators has N outputs and generates all N even-correlation lags once every sampling instant. Such an apparatus can be used for SS systems employing, for example, BPSK signals, or quadrature-phase-shift-keyed (QPSK) signals, multicarrier BPSK signals, multicarrier QPSK signals, or CPSK signals, each without data modulation embedded therein.
A third object of the invention is to provide a method and an apparatus including a combination of an even-correlation-lag generator and an odd-correlation-lag generator, for computing or generating all N even- and N odd-correlation lags between a rotating reference code and a received SS signal, wherein (a) the rotating reference code is time-variant and is generated by a rotation of a basic reference code, (b) the received SS signal is a signal composed by modulating data with the entirety of a PN sequence, (c) the even-correlation-lag generator has N outputs and generates N even-correlation lags once every sampling instant, and (d) the odd-correlation-lag generator has N outputs and generates N odd-correlation lags once every sampling instant. Such an apparatus can be used for SS systems employing, for example, BPSK signals, or CPSK signals, each with data modulation embedded therein.
A fourth object of the invention is to provide an apparatus including a plurality of sub-apparatuses, each of which is a combination of an even-correlation-lag generator and an odd-correlation-lag generator, for correlating a plurality of streams of SS signal samples with a rotating reference code and producing for each of the plurality of streams of SS signal samples all N even- and N odd-correlation lags once every sampling instant, wherein (a) the rotating reference code is time-variant and is generated by a rotation of a basic reference code, (b) the plurality of streams of SS signal samples are generated from a received SS signal, which is a signal, possibly corrupted by noise and interference, composed by means of modulating data with the entirety of a PN sequence, (c) each of the even-correlation-lag generators has N outputs and generates N even-correlation lags once every sampling instant, and (d) each of the odd-correlation-lag generators has N outputs and generates N odd-correlation lags once every sampling instant. Such an apparatus is useful for SS systems employing, for example, BPSK signals, QPSK signals, multicarrier BPSK signals, multicarrier QPSK signals, or CPSK signals, each having data modulation embedded therein.
A fifth object of the invention is to provide a method and an apparatus including one correlator for computing or generating M selected even-correlation lags (M<N) between a rotating reference code and a received SS signal, wherein (a) the rotating reference code is time-variant and is generated by a rotation of a basic reference code, (b) the SS signal is a signal, possibly corrupted by noise and interference, composed by means of periodic repetition of a PN sequence, and (c) the correlator has M outputs and generates M selected even-correlation lags once every sampling instant. Such an apparatus can be used for SS systems employing for example, BPSK signals, or CPSK signals, each without data modulation.
A sixth object of the invention is to provide an apparatus including a plurality of correlators, for correlating a plurality of streams of SS signal samples with a rotating reference code, wherein (a) the rotating reference code is time-variant and is generated by a rotation of a basic reference code, (b) the plurality of streams of SS signal samples are generated from a received SS signal, which is a signal, possibly corrupted by noise and interference, composed by means of periodic repetition of a PN sequence, and (c) each of the correlators has M outputs and generates M selected even-correlation lags once every sampling instant. Such an apparatus can be used for SS systems employing, for example, BPSK signals, QPSK signals, multicarrier BPSK signals, multicarrier QPSK signals, or CPSK signals, each without data modulation embedded therein.
A seventh object of the invention is to provide a method and an apparatus, including a combination of an even-correlation-lag generator and an odd-correlation-lag generator, for computing or generating M selected even- and M selected odd-correlation lags (M<N) between a rotating reference code and a received SS signal, wherein (a) the rotating reference code is time-variant and is generated by a rotation of a basic reference code, (b) the received SS signal is a signal composed by modulating data with the entirety of a PN sequence, (c) the even-correlation-lag generator has M outputs and generates M selected even-correlation lags once every sampling instant, and (d) the odd-correlation-lag generator has M outputs and generates M selected odd-correlation lags once every sampling instant. Such an apparatus can be used for SS systems employing, for example, BPSK signals, or CPSK signals, each with data modulation embedded therein.
An eighth object of the invention is to provide an apparatus including a plurality of sub apparatuses each of which is a combination of an even-correlation-lag generator and an odd-correlation-lag generator, for correlating a plurality of streams of SS signal samples with a rotating reference code and producing for each of the plurality of streams of SS signal samples M selected even- and M selected odd-correlation lags once every sampling instant, wherein (a) the rotating reference code is time-variant and is generated by a rotation of a basic reference code, (b) the plurality of streams of SS signal samples are generated from a received SS signal, which is a signal, possibly corrupted by noise and interference, composed by means of modulating data with the entirety of a PN sequence, (c) each of the even-correlation-lag generators has M outputs and generates M selected even-correlation lags once every sampling instant, and (d) each of the odd-correlation-lag generators has M outputs and generates M selected odd-correlation lags once every sampling instant. Such an apparatus is useful for SS systems employing, for example, BPSK signals, QPSK signals, multicarrier BPSK signals, multicarrier QPSK signals, or CPSK signals, each having data modulation embedded therein.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a diagram of an all-lag even-correlation generator, which generates rn;
FIG. 2 is a diagram of a rotating-reference-code generator for generating the time-variant reference code at time n;
FIG. 3 is a diagram of an all-lag odd-correlation generator, which generates {overscore (r)}n;
FIG. 4 is a diagram of a rotating-reference-code generator for generating the time-variant reference code at time n;
FIG. 5 is a diagram of an all-lag rotating-reference correlator for correlating a stream of SS signal samples with a rotating reference code;
FIG. 6 is a diagram of an all-lag rotating-reference correlator for correlating a plurality of streams of SS signal samples with a rotating reference code;
FIG. 7 is a diagram of an all-lag rotating-reference correlator for correlating a stream of SS signal samples with a rotating reference code;
FIG. 8 is a diagram of an all-lag rotating-reference correlator for correlating a plurality of streams of SS signal samples with a rotating reference code;
FIG. 9 is a diagram of a rotating-reference correlator for correlating a stream of SS signal samples with a rotating reference code and producing selected even-correlation lags;
FIG. 10 is a diagram of a rotating-reference correlator for correlating a plurality of streams of SS signal samples with a rotating reference code;
FIG. 11 is a diagram of a rotating-reference correlator for correlating a stream of SS signal samples with a rotating reference code and producing selected even- and selected odd-correlation lags; and
FIG. 12 is a diagram of a rotating-reference correlator for correlating a plurality of streams of SS signal samples with a rotating reference code.



The method to generate {overscore (r)}n is based on the recursive relationship

{overscore (r)}n={overscore (r)}n−1+(dn+dn−N)ān  (17) 

where an=[αN−1,n, αN−2,n, . . . , α0,n]T is the reference code for time n, given by

ān={overscore (S)}ān−1, n>0  (18) 

with

ā0=[cN−1,cN−2, . . . , c0]T  (19) 

Based on knowing {overscore (r)}n−1, this recursive relationship can be applied to generate {overscore (r)}n. Initial conditions are set such that {overscore (r)}0=0 and d0=d−1= . . . =d−(N−1)=0.

An all-lag odd-correlation generator is shown in FIG. 3. The apparatus consists of an addition means 202, a plurality of multipliers 210-1, 210-2, . . . , 210-N, a plurality of storage means 220-1, 220-2, . . . , 220-N (collectively referred to as 220), and a plurality of adders 230-1, 230-2, . . . , 230-N. The input SS signal samples are d1, d2, d3, . . . and the output vectors are {overscore (r)}N, {overscore (r)}N+1, {overscore (r)}N+2, . . . .
The incoming SS signal sample is fed from the port 200 to the input of addition means 202. The signal sample obtained at the nth previous sampling instant is available at the output of shift register 101-N. The outputs {overscore (r)}0,n, {overscore (r)}1,n, . . . , {overscore (r)}N−1,n computed or generated at the nth sampling instance are obtained at the outputs of adders 230-1, 230-2, . . . , 230-N, respectively. The outputs {overscore (r)}0,n−1, {overscore (r)}1,n−1, {overscore (r)}2,n−1, . . . , {overscore (r)}N−1,n−1 computed or generated at the (n−1)th sampling instant are stored in storage means 220-1, 220-2, . . . , 220-N, respectively, and are available at the outputs of respective storage means 220 at the nth sampling instant. Before d1 is received, the values stored in 220 are reset to zero when the reset operation sets d0=d−1= . . . =d−(N−1)=0 and {overscore (r)}0,0={overscore (r)}1,0= . . . ={overscore (r)}N−1,0=0. Suppose that dn is fed into the apparatus. This signal sample is presented to the input of addition means 202. Another input of addition means 202 is connected to the output of shift register 101-N. The output of addition means 202 is connected to one of two inputs of multiplier 210-1, and is similarly connected to a plurality of multipliers 210-2, 210-3, . . . , 210-N. Other inputs of multipliers 210-1, 210-2, . . . , 210-N are connected to input ports 215-1, 215-2, . . . , 215-N, which provide values of
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
A method to generate rn is based on the recursive relationship

rn=rn−1+(dn−dn−N)an  (14) 

where an=[αN−1,n,αN−2,n, . . . , α0,n]T is the reference code for time n, given by

αn=Sαn−1n>0  (15) 

with

α0=[cN−1,cN−2, . . . ,c0]T  (16) 

Based on knowing {overscore (r)}n−1, this recursive relationship can be applied to generate {overscore (r)}n. Initial conditions are set such that {overscore (r)}0=0 and d0=d−1= . . . =d−(N−1)=0.

An all-lag odd-correlation generator is shown in FIG. 1. The apparatus consists of a plurality of storage means 101-1, 101-2, . . . , 101-N acting as a shift register (collectively referred to as 101) for storing SS signal samples, a subtraction means 102, a plurality of multipliers 110-1, 110-2, . . . , 110-N, a plurality of storage means 120-1, 120-2, . . . , 120-N (collectively referred to as 120), and a plurality of adders 130-1, 130-2, . . . , 130-N. The input SS signal samples are d1, d2, d3, . . . and the desired output vectors are rN, rN+1, rN+2, . . . .
The incoming SS signal sample is fed from the port 100 to the input of shift register 101-1 and the input of subtraction means 102. The signal sample obtained at the nth previous sampling instant step available at the output of shift register 101-N. The outputs r0,n, r1,n, . . . , rN−1,n computed or generated at the nth sampling instant are obtained at the outputs of adders 130-1, 130-2, . . . , 130-N, respectively. The outputs r0,n−1, r1,n−1, . . . , rN−1,n−1 computed or generated at the (n−1)th sampling instant are stored in storage means 120-1, 120-2, . . . , 120-N, respectively, and are available at the outputs of respective storage means 120 at the nth sampling instant.
Before d1 is received, the values stored in 101 and 120 are reset to zero when the reset operation sets d0=d−1= . . . =d−(N−1)=0 and r0,0=r1,0= . . . =rN−1,0=0. Suppose now that dn is fed into the apparatus. This signal sample is presented to the input of subtraction means 102. Another input of the subtraction means 102 is connected to the output of 101-N. The output of subtraction means 102 is connected to one of two inputs of multiplier 110-1, and is similarly connected to a plurality of multipliers 110-2, 110-3, . . . , 110-N. Other inputs of multipliers 110-1, 110-2, . . . , 110-N are connected to input ports 115-1, 115-2, . . . , 115-N, which provides values of αN−1,n, αN−2,n, αN−3,n, . . . , α0,n, respectively, at the nth sampling instant. Outputs of multipliers 110-1, 110-2, . . . , 110-N are connected to inputs of adders 130-1, 130-2, . . . , 130-N, respectively. Other inputs of adders 130-1, 130-2, . . . , 130-N are connected to outputs of storage means 120-1, 120-2, . . . , 120-N, respectively. Inputs of storage means 120-1, 120-2, . . . , 120-N are connected to outputs of adders 130-1, 130-2, . . . , 130-N, respectively. Correlator outputs r0,n, r1,n, . . . , rN−1,n obtained at the nth time instant appear at outputs of adders 130-1, 130-2, . . . , 130-N, respectively.
For the case where M selected even-correlation lags are generated every sampling instance, M<N, the recursive relationship given by equation (14) indicates that the M selected even-correlation lags can be generated by a reduced even-correlation generator by deleting unused branches from the all-lag even-correlation generator depicted in FIG. 1. For example, if the mth even-correlation lag is not wanted to be generated, then multiplier 110-m, adder 130-m, and storage means 120-m are deleted. Operation of the reduced even-correlation generator is the same as that of the all-lag even-correlation generator.
A rotating-reference generator that generates an at time n is depicted in FIG. 2. The generator includes N storage elements 160-1, 160-2, 160-3, . . . , 160-N acting as an end-around shift register collectively referred to as 160 for generating the rotating reference. Prior to operation, the storage elements 160-1, 160-2, 160-3, . . . , 160-N are initialized with values c0, c1, c2, . . . , cN−1, respectively.
{overscore (α)}N−1,n, {overscore (α)}N−2,n, {overscore (α)}N−3,n, . . . , {overscore (α)}0,n, respectively, at the nth sampling instant. Outputs of the multipliers 210-1, 210-2, . . . , 210-N are connected to inputs of adders 230-1, 230-2, . . . , 230-N, respectively. Other inputs of the adders 230-1, 230-2, . . . , 230-N are connected to outputs of the storage means 220-1, 220-2, . . . , 220-N, respectively. Inputs of the storage means 220-1, 220-2, . . . , 220-N are connected to the outputs of the adders 230-1230-2, . . . , 230-N, respectively. Correlator outputs {overscore (r)}0,n, {overscore (r)}1,n, . . . , {overscore (r)}N−1,n obtained at the nth time instant are the outputs of the adders 230-1, 230-2, . . . , 230-N, respectively.
In the case where M selected odd-correlation lags are generated every sampling instant, M<N, the recursive relationship given by equation. (17) indicates that the M selected odd-correlation lags can be generated by a reduced odd-correlation generator by deleting unused branches from the all-lag odd-correlation generator depicted in FIG. 3. For example, if the mth odd-correlation lag is not wanted to be generated, then multiplier 210-m, adder 230-m, and storage means 220-m are deleted. Operation of the reduced odd-correlation generator is the same as that of the all-lag odd-correlation generator.
A rotating-reference generator that generates ān at time n is as shown in FIG. 4. The generator includes N storage elements 260-1, 260-2, 260-3, . . . , 260-N acting as an inverting end-around shift register collectively referred to as 260 for generating the rotating reference, and a negator 270. Prior to operation, the storage elements 260-1, 260-2, 260-3, . . . , 260-N are initialized with values c0, c1, C2, . . . , CN−1, respectively.
An exemplary apparatus that accomplishes the first object of the invention is shown in FIG. 5, and includes an all-lag even-correlation generator 350, and a rotating-reference generator 360 for generating an at time n. A stream of SS signal samples is fed into the apparatus from port 300. Even-correlation lags for the stream of SS signal samples are obtained as outputs of the all-lag even-correlation generator 350. The rotating-reference generator 360 provides values of α0,n, α1,n, . . . , αN−1,n at time n to the all-lag even-correlation generator 350. Q streams of SS signal samples are fed into the apparatus through ports 600-1, 600-2, . . . , 600-Q (collectively referred to as 600). Even-correlation lags for all streams are obtained as outputs of all-lag even-correlation generators 650-1, 650-2, . . . , 650-Q. Odd-correlation lags for all streams are obtained as outputs of the all-lag odd-correlation generators 655-1, 655-2, . . . , 655-Q. The rotating-reference generator 660 provides values of α0,n, α1,n, . . . , αN−1,n at time n to the Q all-lag even-correlation generators 650. The rotating-reference generator 665 provides values of {overscore (α)}0,n, {overscore (α)}1,n, . . . , {overscore (α)}N−1,n at time n to the Q all-lag odd-correlation generators 655.
An exemplary apparatus that accomplishes the fifth object of the invention is shown in FIG. 9, and includes a reduced even-correlation generator 750, and a rotating-reference generator 760 for generating an at time n. A stream of SS signal samples is fed into the apparatus from port 700. Selected even-correlation lags for the stream of SS signal samples are obtained as outputs of the reduced even-correlation generator 750. The rotating-reference generator 760 provides values of α0,n, α1,n, . . . , αN−1,n at time n to the reduced even-correlation generator 750.
An exemplary apparatus that accomplishes the sixth object of the invention is shown in FIG. 10, and includes a plurality of reduced even-correlation generators 850-1, 850-2, . . . , 850-Q (collectively called 850), and a rotating-reference generator 860 for generating an at time n, wherein Q is the number of streams of SS signal samples to be correlated with the rotating reference code. The Q streams of SS signal samples are fed into the apparatus through ports 800-1, 800-2, . . . , 800-Q (collectively referred to as 800). Selected even-correlation lags for all streams are obtained as outputs of reduced even-correlation generators 850-1, 850-2, . . . , 850-Q. The rotating-reference generator 860 provides values of α0,n, α1,n, . . . , αN−1,n at time n to the Q all-lag even-correlation generators 850.
An exemplary apparatus that accomplishes the seventh object of the invention is shown in FIG. 11, and includes a reduced even-correlation generator 950, a reduced odd-correlation
An exemplary apparatus that accomplishes the second object of the invention is shown in FIG. 6 and includes a plurality of all-lag even-correlation generators 450-1, 450-2, . . . , 450-Q (collectively referred to as 450), and a rotating-reference generator 460 for generating an at time n, wherein Q is the number of streams of SS signal samples to be correlated with the rotating reference code. The Q streams of SS signal samples are fed into the apparatus through ports 400-1, 400-2, . . . , 400-Q (collectively referred to as 400). Even-correlation lags for all streams are obtained as outputs of the all-lag even-correlation generators 450-1, 450-2, . . . , 450-Q. The rotating-reference generator 460 provides values of α0,n, α1,n, . . . , αN−1,n at time n to the Q all-lag even-correlation generators 450.
An exemplary apparatus that accomplishes the third object of the invention is shown in FIG. 7, and includes an all-lag even-correlation generator 550, an all-lag odd-correlation generator 555, a rotating-reference generator 560 for generating an, and a rotating-reference generator 565 for generating ān. A stream of SS signal samples is fed into the apparatus from port 500, and is directed to the all-lag even- and odd-correlation generators 550 and 555. Even-correlation lags for the stream of SS signal samples are obtained as outputs of the all-lag even-correlation generator 550. Odd-correlation lags for the stream of SS signal samples are obtained as outputs of the all-lag odd-correlation generator 555. The rotating-reference generator 560 provides values of α0,n, α1,n, . . . , αN−1,n at time n to the all-lag even-correlation generator 550. The rotating-reference generator 565 provides values of {overscore (α)}0,n, {overscore (α)}1,n, . . . , {overscore (α)}N−1,n at time n to the all-lag odd-correlation generator 555.
An exemplary apparatus that accomplishes the fourth object of the invention is shown in FIG. 8, and includes a plurality of all-lag even-correlation generators 650-1, 650-2, . . . , 650-Q (collectively referred to as 650), a plurality of all-lag odd-correlation generators 655-1, 655-2, . . . , 655-Q (collectively referred to as 655), a rotating-reference generator 660 for generating an, and a rotating-reference generator 665 for generating ān, wherein Q is the number of streams of SS signal samples to be correlated with the rotating reference code. The generator 955, a rotating Preference generator 960 for generating an, and a rotating-reference generator 965 for generating ān. A stream of SS signal samples is fed into the apparatus from port 900, and is directed to the reduced even- and odd-correlation generators 950 and 955. Selected even-correlation lags for the stream of SS signal samples are obtained as outputs of the reduced even-correlation generator 950. Selected odd-correlation lags for the stream of SS signal samples are obtained as outputs of the reduced odd-correlation generator 955. The rotating-reference generator 960 provides values of α0,n, α1,n, . . . , αN−1,n at time n to the reduced even-correlation generator 950. The rotating-reference generator 965 provides values of {overscore (α)}0,n, {overscore (α)}1,n, . . . , {overscore (α)}N−1,n at time n to the reduced odd-correlation generator 955.
An exemplary apparatus that accomplishes the eighth object of the invention is shown in FIG. 12, and includes a plurality of reduced even-correlation generators 1050-1, 1050-2, . . . , 1050-Q (collectively referred to as 1050), a plurality of reduced odd-correlation generators 1055-1, 1055-2, . . . , 1055-Q (collectively referred to as 1055), a rotating-reference generator 1060 for generating an, and a rotating-reference generator 1065 for generating ān, wherein Q is the number of streams of SS signal samples to be correlated with the rotating reference code. The Q streams of SS signal samples are fed into the apparatus through ports 1000-1, 1000-2, . . . , 1000-Q (collectively referred to as 1000). Selected even-correlation lags for all streams are obtained as outputs of reduced even-correlation generators 1050-1, 1050-2, . . . , 1050-Q. Selected odd-correlation lags for all streams are obtained as outputs of reduced odd-correlation generators 1055-1, 1055-2, . . . , 1055-Q. The rotating-reference generator 1060 provides values of α0,n, α1,n, . . . , αN−1,n at time n to the Q reduced even-correlation generators 1050. The rotating-reference generator 1065 provides values of {overscore (α)}0,n, {overscore (α)}1,n, . . . , {overscore (α)}N−1,n at time n to the Q reduced odd-correlation generators 1055.
It will be apparent to those skilled in the art that various modifications can be made to the apparatus described herein without departing from the scope and spirit of the invention. For example, the exemplary apparatus described herein could be used in a particular application, but may discard some of the outputs produced by the all-lag rotating-reference correlator, or may not use some/all outputs produced at some sampling instants. Furthermore, it will be apparent to those skilled in the art that the apparatus described herein can be implemented not only in the digital domain (i.e., using very large scale integration circuits to process the incoming SS signal that is digitized using an analog-to-digital converter), but also in the analog domain (viz., via using surface-acoustic-wave devices, charge-coupled devices or other equivalents) and also in software for execution in digital signal processor(s) or programmable device(s) or their equivalents.

## Claims

1. An apparatus for correlating a stream of spread-spectrum signal samples with a rotating reference code, comprising:
spread spectrum signal storage means for storing the spread-spectrum signal samples at a present sampling instance and at a plurality of previous sampling instances; 
subtraction means for calculating the difference between the present sampling instance and the plurality of previous sampling instances thus generating time lagged signal samples; 
a plurality of multiplication means each computing the multiplication result for the output of the subtraction means and an element of the rotating reference code; 
correlation lag storage means for storing correlation lags obtained at the previous sampling instance; and 
a plurality of addition means, coupled to outputs of the plurality of multiplication means and the correlation lag storage means, generating a correlation lag dependent on the previous sampling instance.

2. The apparatus of claim 1, wherein at least one of the spread spectrum signal storage means and the correlation lag storage means includes a surface-acoustic-wave (SAW) device.

3. The apparatus of claim 1, wherein at least one of the spread spectrum signal storage means and the correlation lag storage means includes a charge-coupled device (CCD).

4. The apparatus of claim 1, further comprising a rotating-reference generator including a plurality of storage elements configured as end-around shift registers.

5. The apparatus of claim 4, wherein the stream of spread-spectrum signal samples is generated from a received BPSK signal composed by means of periodic repetition of a PN sequence.

6. The apparatus of claim 4, wherein the stream of spread-spectrum signal samples is generated from a received CPSK signal composed by means of periodic repetition of a PN sequence.

7. The aparatus of claim 1, wherein the correlation lags are even-correlation lags.

8. The apparatus of claim 1, further including a negator such that the negator is configured to generate odd correlation lags.

9. An apparatus for correlating a plurality of streams of spread-spectrum signal samples with a rotating reference code, comprising:
spread spectrum signal storage means for storing the spread-spectrum signal samples at a current sampling instance and at a plurality of previous sampling instances; 
subtraction means for calculating the difference between time-lagged signal samples; 
a plurality of multiplication means each computing the multiplication result for the output of the subtraction means and an element of the rotating reference code; 
correlation lag storage means for storing correlation lags obtained at the last previous sampling instance; and 
a plurality of addition means, coupled to outputs of the plurality of multiplication means and the even-correlation-lag storage means.

10. An apparatus of claim 9, wherein the plurality of streams of spread-spectrum signal samples are generated from a BPSK signal composed by means of periodic repetition of a PN sequence.

11. An apparatus of claim 9, wherein the plurality of streams of spread-spectrum signal samples are generated from a CPSK signal composed by means of periodic repetition of a PN sequence.

12. An apparatus of claim 9, wherein the plurality of streams of spread-spectrum signal samples are generated from a QPSK signal composed by means of periodic repetition of a PN sequence.

13. An apparatus of claim 9, wherein the plurality of streams of spread-spectrum signal samples are generated from a multicarrier BPSK signal each of subcarrier signals being composed by means of periodic repetition of a PN sequence.

14. An apparatus of claim 9, wherein the plurality of streams of spread-spectrum signal samples are generated from a multicarrier QPSK signal each of subcarrier signals being composed by means of periodic repetition of a PN sequence.