Apparatus and methods for obtaining a correlation function in the frequency domain

0Associated
Cases 
0Associated
Defendants 
0Accused
Products 
0Forward
Citations 
0
Petitions 
0
Assignments
First Claim
1. Apparatus for calculating a correlation function between a Direct Sequence Spread Spectrum DSSS signal and a spreading code, the apparatus comprising:
 memory arranged to store a plurality of code replica samples, the code replica samples comprising samples of a complex conjugate of a timetofrequency domain transformed replica of the spreading code obtained at a first sampling rate;
a timetofrequency domain transformation unit configured to receive a block of samples of the DSSS signal at a second sampling rate higher than the first sampling rate, and transform the samples from the time domain to the frequency domain to obtain a plurality of frequencydomain signal samples;
a multiplication unit configured to obtain a correlation operator by reproducing the stored replica samples, and multiply the frequencydomain signal samples by the reproduced stored replica samples to obtain a plurality of multiplied samples; and
an integrating unit configured to receive the multiplied samples and perform integration over a plurality of blocks of samples of the DSSS signal to calculate the correlation function.
0 Assignments
0 Petitions
Accused Products
Abstract
Apparatus and methods are disclosed for obtaining a correlation function between a Direct Sequence Spread Spectrum (DSSS) signal and a spreading code. A plurality of code replica samples are stored in memory at a relatively low sampling rate compared to the sampling rate at which the input DSSS signal is sampled. A correlation operator is obtained by reproducing the stored code replica samples, in order to obtain a correlation operator with the same number of samples as the block of DSSS signal samples currently being processed. For example, when the sampling rate of the DSSS signal is equal to an integer N multiple of the sampling rate used for the code replica samples, the stored replica samples are reproduced N times to obtain the correlation operator. The correlation operator is then multiplied by the block of DSSS signal samples and integrated to obtain a correlation function.
4 Citations
No References
FFTbased CDMA RAKE receiver system and method  
Patent #
US 6,154,443 A
Filed 08/11/1998

Current Assignee
Industrial Technology Research Institute

Sponsoring Entity
Industrial Technology Research Institute

Signal folding coherent acquisition for weak global positioning system (GPS) C/A coded signal  
Patent #
US 6,975,690 B1
Filed 08/15/2001

Current Assignee
The Government Of The United States Of America As Represented By The Secretary Of The Air Force

Sponsoring Entity
The Government Of The United States Of America As Represented By The Secretary Of The Air Force

RECEIVER AND METHOD FOR DIRECT SEQUENCE SPREAD SPECTRUM SIGNALS  
Patent #
US 20160116599A1
Filed 06/05/2014

Current Assignee
Airbus Defence and Space Limited

Sponsoring Entity
Airbus Defence and Space Limited

Processing of signals to provide a delay Doppler map  
Patent #
US 9,465,115 B2
Filed 06/14/2013

Current Assignee
Airbus Defence and Space Limited

Sponsoring Entity
Airbus Defence and Space Limited

17 Claims
 1. Apparatus for calculating a correlation function between a Direct Sequence Spread Spectrum DSSS signal and a spreading code, the apparatus comprising:
memory arranged to store a plurality of code replica samples, the code replica samples comprising samples of a complex conjugate of a timetofrequency domain transformed replica of the spreading code obtained at a first sampling rate; a timetofrequency domain transformation unit configured to receive a block of samples of the DSSS signal at a second sampling rate higher than the first sampling rate, and transform the samples from the time domain to the frequency domain to obtain a plurality of frequencydomain signal samples; a multiplication unit configured to obtain a correlation operator by reproducing the stored replica samples, and multiply the frequencydomain signal samples by the reproduced stored replica samples to obtain a plurality of multiplied samples; and an integrating unit configured to receive the multiplied samples and perform integration over a plurality of blocks of samples of the DSSS signal to calculate the correlation function.  View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9)
 10. A method of calculating a correlation function between a Direct Sequence Spread Spectrum DSSS signal and a spreading code using a plurality of code replica samples, the code replica samples comprising samples of a complex conjugate of a timetofrequency domain transformed replica of the spreading code obtained at a first sampling rate, the method comprising:
receiving a block of samples of the DSSS signal at a second sampling rate higher than the first sampling rate; transforming the samples from the time domain to the frequency domain to obtain a plurality of frequencydomain signal samples; obtaining a correlation operator by reproducing the code replica samples; multiplying the frequencydomain signal samples by the reproduced code replica samples to obtain a plurality of multiplied samples; and integrating the multiplied samples over a plurality of blocks of samples of the DSSS signal to calculate the correlation function.  View Dependent Claims (11, 12, 13, 14, 15, 16, 17)
1 Specification
The present application is a U.S. national phase application under 35 U.S.C. § 371 of International Application No. PCT/EP2017/072649, filed on Sep. 8, 2017 and published as WO 2018/046694 A1 on Mar. 15, 2018, which claims priority to EP Application No. 16275130.9, filed on Sep. 8, 2016. The content of each of these related applications is incorporated herein by reference in its entirety.
The present invention relates to calculating a correlation function in the frequency domain. More particularly, the present invention relates to obtaining a correlation function between a Direct Sequence Spread Spectrum (DSSS) signal and a replica of a spreading code.
DSSS modulation is used in a wide variety of applications, including Global Navigation Satellite Systems (GNSS), radio frequency ranging systems, radio frequency time transfer systems, antijamming receivers and channel sounding. An example of a DSSS signal is illustrated in
Many Digital Signal Processing (DSP) algorithms require a DSSS signal to be correlated with a replica of a spreading code at the receiver. In a GNSS receiver, the correlation process can be considered to be the most important DSP process, since without this it would not be possible for the receiver to lock onto and track the downlink signals and make timeofarrival measurements from satellites in a GNSS constellation. In general, a DSSS correlation process involves correlating incoming samples against a replica of a candidate spreading code, which can be referred to as a filter kernel, and detecting a peak in the correlation function. To make a precise timeofarrival estimate, many GNSS implementations use a sample rate of the signal which is significantly larger than the native sample rate of the filter kernel, which in a GNSS receiver is one sample per chip.
A Fourierbased tracking algorithm for obtaining a correlation function in a GNSS receiver is disclosed in “A Realtime FFT Based Block Processing Method with Near Linear Scaling”, M. Turner, A. R. (2015), ION ITM. The algorithm transforms blocks of 50% zero padded time domain samples into blocks of frequency domain samples, applies the Doppler and phase corrections that were obtained during acquisition, multiplies the frequencydomain samples by the relevant Fourier transformed spreading code, and accumulates data over one data symbol period to integrate the underlying correlation function over many Fast Fourier Transform (FFT) blocks. An Inverse FFT (IFFT) operation is then performed to transform the correlation function back to the time domain for further processing.
One drawback with this method is that the instantaneous memory bandwidth and capacity required can very quickly become unacceptably large. For example, when oversampling the Galileo Open service PRN signal, which has 4092 chips per PRN cycle, at an oversampling rate of 50×, the Fourier domain storage requirement per satellite tracking chain is: 4092×50(upsample)×13(bit)×2(zero pad)×2(complex)=10639200(bits)=10.6 Mbits. The memory bandwidth per tracking chain is: 50(oversample rate)×1023000(chip rate)×2(zero pad)×13(bit width)×2(complex)=2659800000 (bits/sec)=2.66 (Gbit/sec). Therefore to track downlink signals from one hundred satellites in a GNSS constellation, a total bandwidth of 266 Gb/s and 1 Gb of storage capacity would be required for a high performance receiver with a sample rate 50 MS/s. Currently, the most memoryrich commercially available Field Programmable Gate Array (FPGA) contains 24.2 Mbits of block random access memory (BRAM), and could therefore only accommodate up to two tracking channels in the abovedescribed example. This limitation renders the Fourierbased tracking algorithm impractical for FPGA implementations, without using offFPGA chip fast volatile memory.
The invention is made in this context.
According to a first aspect of the present invention, there is provided apparatus for calculating a correlation function between a Direct Sequence Spread Spectrum DSSS signal and a spreading code, the apparatus comprising: memory arranged to store a plurality of code replica samples, the code replica samples comprising samples of a complex conjugate of a timetofrequency domain transformed replica of the spreading code obtained at a first sampling rate; a timetofrequency domain transformation unit configured to receive a block of samples of the DSSS signal at a second sampling rate higher than the first sampling rate, and transform the samples from the time domain to the frequency domain to obtain a plurality of frequencydomain signal samples; a multiplication unit configured to obtain a correlation operator by reproducing the stored replica samples, and multiply the frequencydomain signal samples by the reproduced stored replica samples to obtain a plurality of multiplied samples; and an integrating unit configured to receive the multiplied samples and perform integration over a plurality of blocks of samples of the DSSS signal to calculate the correlation function.
In some embodiments according to the first aspect, the second sampling rate is equal to the first sampling rate multiplied by an integer N, and the multiplication unit is configured to obtain the correlation operator by reproducing the stored replica samples N times.
In some embodiments according to the first aspect, the second sampling rate is equal to the first sampling rate multiplied by a noninteger multiplier X, and the multiplication unit is configured to obtain the correlation operator by reproducing the stored replica samples an integer number N times, and to apply a frequencydomain interpolation or decimation to the frequencydomain signal samples such that a sampling rate of the interpolated or decimated signal samples matches a sampling rate of the correlation operator, before multiplying the frequencydomain signal samples by the reproduced stored replica samples.
In some embodiments according to the first aspect, the apparatus further comprises a moving average filter unit configured to multiply the correlation function by a moving average filter correlation matrix.
In some embodiments according to the first aspect, the apparatus further comprises a modulation unit configured to multiply the correlation function by a modulation matrix to account for a modulation scheme used in the DSSS signal.
In some embodiments according to the first aspect, the apparatus further comprises a plurality of signal processing branches each configured to calculate a correlation function between the block of samples of the DSSS signal and a different spreading code, wherein the moving average filter unit and/or the modulation unit are shared between the plurality of signal processing branches such that the moving average filter unit and/or the modulation unit is configured to receive a plurality of correlation functions from the plurality of signal processing branches.
In some embodiments according to the first aspect, the integrating unit is configured to perform the integration across a transition between consecutive data symbol periods in the DSSS signal, and to determine a polarity of a data symbol in each of the data symbol periods based on a polarity of the obtained correlation function.
In some embodiments according to the first aspect, the apparatus further comprises a frequencytotime domain transformation unit configured to transform the obtained correlation function from the frequency domain into the time domain.
In some embodiments according to the first aspect, the apparatus is embodied in a Field Programmable Gate Array chip.
According to a second aspect of the present invention, there is provided a method of calculating a correlation function between a Direct Sequence Spread Spectrum DSSS signal and a spreading code using a plurality of code replica samples, the code replica samples comprising samples of a complex conjugate of a timetofrequency domain transformed replica of the spreading code obtained at a first sampling rate, the method comprising: receiving a block of samples of the DSSS signal at a second sampling rate higher than the first sampling rate; transforming the samples from the time domain to the frequency domain to obtain a plurality of frequencydomain signal samples; obtaining a correlation operator by reproducing the stored replica samples; multiplying the frequencydomain signal samples by the reproduced stored replica samples to obtain a plurality of multiplied samples; and integrating the multiplied samples over a plurality of blocks of samples of the DSSS signal to calculate the correlation function.
In some embodiments according to the second aspect, the second sampling rate is equal to the first sampling rate multiplied by an integer N, and the correlation operator is obtained by reproducing the stored replica samples N times.
In some embodiments according to the second aspect, the second sampling rate is equal to the first sampling rate multiplied by a noninteger multiplier X, and the correlation operator is obtained by reproducing the stored replica samples an integer number N times, and applying a frequencydomain interpolation or decimation to the frequencydomain signal samples such that a sampling rate of the interpolated or decimated signal samples matches a sampling rate of the correlation operator, before multiplying the frequencydomain signal samples by the reproduced stored replica samples.
In some embodiments according to the second aspect, the method further comprises multiplying the correlation function by a moving average filter correlation matrix.
In some embodiments according to the second aspect, the method further comprises multiplying the correlation function by a modulation matrix to account for a modulation scheme used in the DSSS signal.
In some embodiments according to the second aspect, the method further comprises calculating a correlation function between the block of samples of the DSSS signal and a different spreading code using a plurality of signal processing branches, wherein the moving average filter correlation matrix and/or the modulation matrix are applied by a shared unit configured to receive the plurality of correlation functions from the plurality of signal processing branches.
In some embodiments according to the second aspect, the integration is performed across a transition between consecutive data symbol periods in the DSSS signal, and the method further comprises determining a polarity of a data symbol in each of the data symbol periods based on a polarity of the obtained correlation function.
In some embodiments according to the second aspect, the method further comprises a step of transforming the obtained correlation function from the frequency domain into the time domain.
According to a third aspect of the present invention, there is provided a computerreadable storage medium arranged to store computer program instructions which when executed perform a method according to the second aspect.
Embodiments of the present invention will now be described, by way of example only, with reference to the accompanying drawings, in which:
In the following detailed description, only certain exemplary embodiments of the present invention have been shown and described, simply by way of illustration. As those skilled in the art would realize, the described embodiments may be modified in various different ways, all without departing from the scope of the present invention. In particular, embodiments of the invention are described below in relation to tracking GNSS signals, but it will be understood that the principles disclosed herein can also be applied to other types of DSSS signal. Accordingly, the drawings and description are to be regarded as illustrative in nature and not restrictive. Like reference numerals designate like elements throughout the specification.
Referring now to
The acquisition correlator 210 and the tracking correlator 220 both receive I and Q samples of a received DSSS signal. For example, a receiver which includes the apparatus of
Also, as shown in
As shown in
The apparatus further comprises a multiplication unit 322 which is configured to multiple the frequencydomain signal samples by a correlation operator, to obtain a plurality of multiplied samples. The multiplication unit 322 is configured to generate the correlation operator from replica samples stored in memory 323. A method of obtaining the correlation operator is described in more detail below. The apparatus further comprises an integrating unit 324 configured to receive the multiplied samples and perform integration over a plurality of blocks of samples of the DSSS signal, in order to obtain the correlation function.
In the present embodiment, the apparatus further comprises a moving average filter 325 configured to receive the correlation function from the integrating unit 324 and apply a moving average filter function, and a Binary Offset Carrier (BOC) unit 326 configured to apply BOC modulation after the moving average filter has been applied. As will become apparent from the following description, in some embodiments the moving average filter function and/or BOC modulation may be applied at different stages in the processing chain, for example when generating the correlation operator before multiplication takes place, or after multiplication but before integrating. Furthermore, in some embodiments the BOC unit 326 may be omitted if BOC modulation is not used in the received DSSS signal, or another type of modulation may be applied as required.
Finally, in the present embodiment the apparatus comprises an IFFT unit 327 configured to transform the samples from the frequency domain back to the time domain for further processing in the receiver. In some embodiments, the IFFT unit 327 may be omitted and further processing can be performed in the frequency domain. For example, an integral from one data symbol to the next can be calculated in the frequency domain to determine the polarity of the data symbols, without having to perform a frequencytotime domain transformation.
In the present embodiment the memory 323 is arranged to store the plurality of code replica samples having a first sampling rate. In the present embodiment, the sampling rate at which the code replica samples are stored is equal to the native “baseband” sample rate of the spreading code. The code replica samples comprise samples of a complex conjugate of a timetofrequency domain transformed replica of the spreading code, at the first sampling rate. The FFT unit 321 receives the I,Q signal samples of the DSSS signal at a second sampling rate which is higher than the first sampling rate, and in the present embodiment is equal to an integer N multiple of the first sampling rate. In order to generate a correlation operator with the same number of samples as the block of DSSS signal samples that is currently being processed, the multiplication unit 322 is configured to reproduce the stored replica samples N times. A method of obtaining the correlation operator from the stored replica samples will now be described.
The basic definition of time domain complex correlation over a time duration t, using linear algebra notation, is:
C_{t}·s_{t}=ƒ_{t} (1)
where C_{t }is a correlation operator matrix derived from the replica spreading code over the time duration t, s is the signal vector sampled over the same duration, and ƒ is the correlation function output. In general, the correlation operator replica must be sampled at the same rate as the signal and can be defined for cyclic or zeropadded correlation. Hence in the present embodiment, the stored replica code samples are reproduced N times to generate a correlation operator with the correct sample rate. The reason that the stored replica code samples can simply be replicated N times, as opposed to storing the replica code samples at the same sampling rate at which the DSSS signal samples are received, will become apparent from the following explanation.
The correlation matrix C_{t }is a circulant matrix filled with the replica at single sample shifts over each row, or over each column. The replica may also contain additional modulation such as BOC, in which case the additional modulation will be represented in the correlation operator matrix C_{t}. The symmetry of this correlation matrix is shown below:
As explained above, the sample rate of the replica should be increased to match that of the DSSS signal being processed. To understand the process by which the Fourier domain correlation operator is obtained in embodiments of the present invention, it can be helpful to consider the time domain correlation matrix, which can be defined using a specific series of linear operators from which the corresponding Fourier domain equation can be derived.
First the replica of duration t is sampled at a lower rate than the sampling rate that will be used for the DSSS signal samples. In the present embodiment, the replica of duration t is sampled at its native sample rate, equal to the bit rate of the replica code.
In some embodiments the replica may include any additional modulation such as BOC(1,1) modulation, but in the embodiment of
For a PRN which takes values of 0 or 1, the baseband sample rate corresponds to one sample per chip. For continuous filter kernels, this sample rate is arbitrary. In any case, the sampling rate at which the replica code samples are stored should be selected so as to be sufficient to encompass the bandwidth of the filter kernel. In the present embodiment, the sampling rate selected for the replica code samples is an integer multiple of the native rate of the spreading code. The code replica sampled at the native rate is denoted by c_{t }(also referred to as the “baseband” filter kernel), and the Fourier version of this vector which has been interpolated to the DSSS signal sample rate is denoted by c_{t}^{ƒ}. The ratio between the DSSS signal sample rate and the native filter sample rate is defined as l.
The correlation operator matrix C_{t}, which contains N rows and columns, can be derived from the Fourier interpolated baseband replica using linear operators, by 1) puncturing the Fourier interpolated base band replica to produce the zerostuffed upsampled base band filter kernel, 2) applying BOC modulation to the resulting zero stuffed replica, 3) applying a moving average filter to produce a zero order sampleandhold replica, used as the correlation filter kernel, and 4) applying a left and right multiplied permutation matrix. This process enables the circulant correlation operator matrix C_{t }to be synthesized from the filter, which can be written in matrix form as:
where P_{i }is the ith cyclic permutation matrix of order N,
where M is the moving average filter correlation matrix,
B=I−P_{M}I (5)
where B is a BOC(1,1) modulation matrix,
where δ_{ij }is the konica delta and δ(x−d) is the Dirac delta function, Z is a samplezeroing matrix to transform the Fourier interpolated replica to the zeropadded baseband filter kernel,
and R_{t }is a matrix with the replica c_{t}^{ƒ }in the first column and zero everywhere else.
The MBZC_{t }term in equation (3) prepares the replica in column 1 of R_{t }such that it is transformed into the sampleandhold upsampled base band replica c_{t}, at the required signal sample rate and with BOC(1,1) modulation applied. The cyclic permutation matrices P_{i }applied to the left and right and the final summation ensure that a correlation matrix is constructed by progressively shifting the vector into an adjacent column, barrel shifting the rows. Under the Fourier similarity transform, equation (3) can be rewritten as:
Furthermore, since the discrete Fourier transformation matrix is unitary, to within a scaling constant, then:
FF*=I (9)
and equation (8) can be expanded to:
It can be noted that the grouped terms are similarity transforms of the enclosed operators from the discrete time basis set to the Fourier basis set. Rewriting the operators to indicate a new basis set representation of each, equation (10) can be simplified as follows:
In the Fourier domain, C_{t}^{ƒ}, P_{t}^{ƒ}, M^{ƒ }and B^{ƒ }are all diagonal since they are all circulant matrices in the time domain. This allows refactoring of equation (11) as follows:
Furthermore, since M^{ƒ}, B^{ƒ }and C_{t}^{ƒ }are all diagonal, then:
must also be diagonal. The summation term in (13) is a frequency domain correlation matrix which is constructed in the time domain from the base band filter kernel, c_{t }and zerostuffed upsampled to the DSSS signal sample rate. In the Fourier domain this operator is the Fourier transformation of the zerostuffed replica c_{t }across the diagonal of the matrix.
As described above, in the present embodiment the multiplication unit 322 is configured to reproduce the stored replica samples N times in order to generate a correlation operator with the same number of samples as the block of DSSS signal samples that is currently being processed. This is based on the realisation that the Fourier transform of a zerostuffed upsampled vector can be constructed from the nonzero stuffed vector in the Fourier domain by simply replicating it multiple times to fill the whole vector. This occurs because the periodic zerostuffing acts to subsample the Fourier basis set, which in turn results in aliasing of the Fourier integrals and the repeating Fourier domain filter kernel. Hence in embodiments of the present invention, the full zeroorder sampleandhold correlation operator in the Fourier domain can be constructed by storing only the Fourier transformed baseband code replica samples at the baseband sample rate, reproducing the stored code replica samples N times, and applying diagonal operators to the synthesized replica.
Therefore if the ratio of the baseband sample rate and the signal sample rate is M, then there is a M fold reduction in storage requirement for the replica in the frequency domain, where M may take an integer value as in the example above or may take a noninteger value.
Furthermore, in embodiments of the invention in which a plurality of spreading codes need to be tracked, such as a GNSS receiver, a similar property can be exploited to achieve further efficiency gains.
In the embodiments shown in
An example of a correlation peak is illustrated in
The magnitude of the PRN autocorrelation function of the GPS CA code is approximately 30 decibels (dB).
Referring now to
As shown in
As explained above with reference to
Embodiments of the present invention have been described which can achieve a significant reduction in the number of code replica samples which must be stored, when using a Fourierbased correlation algorithm. Specifically, the number of code replica samples that must be stored is reduced by a factor equal to the replica upsample rate. This is made possible by exploiting the fact that the Fourier transform of the baseband replica has an approximately constant envelope, and can therefore be homogeneously quantized across all samples in the frequency domain. Hence, fewer bits are needed to store the baseband replica.
Furthermore, this decreased bit width has additional advantages as well as a reduction in the storage capacity required to store the code replica samples. The numerical operations implemented within the multiplication units 322, 422 can be implemented with fewer silicon gates, and the resulting accumulation registers used to store the frequency domain correlation function can also be made smaller. When implemented in a FPGA, signal routing is also simplified by the corresponding decrease in the accumulation bit width. For example, an embodiment such as the one shown in
In the abovedescribed embodiments of the invention, the native sampling rate of the DSSS signal is an integer multiple of the sampling rate at which the code replica samples are stored. Accordingly, the stored replica samples are upsampled to match the native sampling rate of the DSSS signal by reproducing the stored replica samples an integer number of times. This results in a correlation operator which has the same number of samples as the block of DSSS signal samples currently being processed, allowing a frequencydomain multiplication to be performed. However, in other embodiments the native sampling rate of the DSSS signal may be a noninteger multiple of the sampling rate of the code replica samples.
In such noninteger upsampling embodiments, the multiplication unit can be configured to obtain the correlation operator by reproducing the stored replica samples an integer number of times, and the DSSS signal is sampled at some other rate close to the integer rate at which the stored replica samples are reproduced. These samples of the DSSS signal are Fourier transformed in an identical manner to that described above. Then, if the signal sample rate is slower than the integer upsample rate applied to the stored replica samples, zeros are padded in the centre of the DSSS signal'"'"'s Fourier transform, effectively performing a Fourier interpolation. Alternatively, if the signal sample rate is faster than the integer upsample rate applied to the stored replica samples, then excess samples are deleted from the centre of the DSSS signal'"'"'s Fourier transform, effectively performing a Fourier decimation. This process ensures that the replica and signal are sample rate matched. That is, the sampling rate of the interpolated or decimated DSSS signal samples matches a sampling rate of the correlation operator, allowing the interpolated or decimated frequencydomain DSSS signal samples to be multiplied by the correlation operator. This method allows a sufficiently close approximation to the integer upsample method to provide an acceptable level of accuracy.
Whilst certain embodiments of the invention have been described herein with reference to the drawings, it will be understood that many variations and modifications will be possible without departing from the scope of the invention as defined in the accompanying claims.