BLIND ESTIMATION OF THE PSEUDO-RANDOM SEQUENCE OF A DIRECT SEQUENCE SPREAD SPECTRUM SIGNAL

BLIND ESTIMATION OF THE PSEUDO-RANDOM SEQUENCE OF A DIRECT SEQUENCE SPREAD SPECTRUM SIGNAL

Gilles BUREL and Céline BOUDER

L.E.S.T. – UMR CNRS 6616

Université de Bretagne Occidentale

6 avenue Le Gorgeu, 29285 Brest cedex, France

Email: Gilles.Burel@univ-brest.fr

ABSTRACT

Direct sequence spread spectrum transmissions (DS-SS) are now widely used for secure communications, as well as for multiple access. They have many interesting properties, including low probability of interception. Indeed, DS-SS transmitters use a periodical pseudo-random sequence to modulate the baseband signal before transmission. A receiver which does not know the sequence cannot demodulate the signal.

In this paper, we propose a method which can estimate the spreading sequence in a non-cooperative context. The method is based on eigenanalysis techniques. The received signal is divided into windows, from which a covariance matrix is computed. We show that the sequence can be reconstructed from the two first eigenvectors of this matrix, and that useful information, such as the desynchronization time, can be extracted from the eigenvalues.

Experimental results show that the method can provide a good estimation, even when the received signal is far below the noise level.

1.INTRODUCTION

Spread spectrum signals have been used for secure communications for several decades [3]. Nowadays, they are also widely used outside the military domain, especially in Code Division Multiple Access (CDMA) systems [2]. Due to their low probability of interception, these signals increase the difficulty of spectrum surveillance.

Direct-Sequence Spread Spectrum transmitters (DS-SS) use a periodical pseudo-random sequence [5] to modulate the baseband signal before transmission. In the context of spectrum surveillance,the pseudo-random sequence used by the transmitter is unknown (as well as other transmitter parameters such as duration of the sequence, symbol frequency and carrier frequency). Hence, in this context, a DS-SS transmission is very difficult to detect and demodulate, because it is often below the noise level. In this paper, we propose a method for estimating the pseudo-random sequence without prior knowledge about the transmitter. Only the duration of the pseudo-random sequence is assumed to have been estimated (this can be done by the method proposed in [1]).

The method is based on eigenanalysis techniques. The received signal is sampled and divided into temporal windows, the size of which is the pseudo-random sequence period. Each window provides a vector which feed the eigenanalysis module. We prove that the spreading sequence can be recovered from the first and the second eigenvectors. This property provides a way to estimate the pseudo-random sequence. Experimental results are given to illustrate the performances of the method and show that a good estimation can be obtained even when the signal is far below the noise level.

The paper is organized as follows. In Section 2, we give the notations and hypotheses. Then, the proposed approach is described in Section 3. Finally, experimental results are provided to illustrate the approach (Section 4) and a conclusion is drawn (Section 5).

2.NOTATIONS AND HYPOTHESES

In a DS-SS transmission, the symbols a k are multiplied by a pseudo-random sequence which spreads the bandwidth [4]. In the sequel, we will use the notations below:

p(t): the convolution of the transmission filter, the channel filter (which represents the channel echoes)and the receiver filter.

{c k , k=0,...,P-1 }: the pseudo-random sequence.P : the length (number of bits) of the pseudo-random sequence.

T s : the symbol period.T e : the sampling period

T c : the chip period (T c = T s / P )h(t): the convolution of the pseudo-random sequence with all the filters of the transmission chain (transmitter filter, channel echoes, and receiver filter):

)

()(1

|

P k c k kT t p c t h h &

: the vector containing the samples of h(t)

s(t): the DS-SS baseband signal at the output of the receiver filter:

)

()(s

k k

kT t h a t s

| f

f

n(t): the noise at the output of the receiver filter.2n V : the noise variance

)()()(t n t s t y : the signal at the output of the

receiver filter

The following hypotheses are assumed:

x The symbols are centered and uncorrelated.

x The noise is white, gaussian, centered, and

uncorrelated with the signal.

x The signal to noise ratio (in dB ) at the output of

the receiver filter is negative (the signal is hidden in the noise).

x In the paper, we assume that the symbol period T s

has been estimated [1]. All other parameters are unknown.

x When the SNR is not too low, methods based on

cyclostationarity analysis can estimate the chip period T c . If an estimation of T c is available, the sampling period can be set to T e =T c , and the interpretation of the results is easier. But this is not a requirement.

3. BLIND ESTIMATION OF THE SPREADING SEQUENCE

The received signal is sampled and divided into non-overlapping temporal windows, the duration of which is T s . Let us note the content of a window.We can estimate the correlation matrix:

^`

H y y E R &&. The eigenanalysis of this matrix shows that there are two large eigenvalues. The reason is explained below.

Since the window duration is equal to the symbol period, a window always contains the end of a symbol (for a duration T s – t 0 ), followed by the beginning of the next symbol (for a duration t 0),where t 0 is unknown. Hence, we can write:n

h a h a m m &&& 110where n &

stands for the noise.

0h &

is a vector containing the end (duration T s – t 0 )

of the spreading waveform h(t), followed by zeroes (duration t 0).1 h &

is a vector containing zeroes (duration T s – t 0 )followed by the beginning (duration t 0) of the spreading waveform h(t).

t 0 is the desynchronization between windows and symbols (s T t d 00).

Using the equations above, we obtain:

^`

^

`I h h a E h h a E R n

H

m H

m

2112

1002....V &&&&From this equation, it is clear that two eigenvalues

will be larger than the others. The corresponding

eigenvectors will be equal to 0h & and 1 h &

, up to

multiplicative factors. Let us note:

2a V the variance of the symbols

2

2

2)(h

T dt t h e h

&|

3

f

f

H 2000h h v &&& and 2

1

11 h h v &&&

Then, we have:

I v v T t v v T

t T R n H s H s e

h a 211000022...1V H V ?

??ˉ?- ??1·¨¨?§

&&&&The DS-SS signal variance is the signal energy on

a period s T , divided by s T :

s

h

a s

T 222H V V

Let us note U the signal to noise ratio:

2

2n

s V V U Then, we can write:

???ˉ?- I v v T t v v T t T R H e H

e s n 1

100002...&&&&U U V Hence, when 2

0s T

t d , the eigenvalues are:

2011n

e s T t T V U O ??1·¨¨?§ 2021n e T t V U O ??1·¨¨?§ 2

n i V O (for 3t i )

These equations are useful. For instance, we can estimate the signal to noise ratio:

s

e n T

T ??1·¨¨?§ 2?221V O O U and the desynchronization:

??1·¨¨?§ 1?220n e

T t V O U

When 20s T

t !, the order of the two first eigenvalues

is changed.

4. EXPERIMENTAL RESULTS

To illustrate the approach, a DS-SS signal is generated using a random-sequence of length P=31(it is one of the Gold Sequences [4] which are traditionally used in CDMA systems). The symbols belong to a QPSK constellation (Quadrature Phase Shift Keying). The SNR is dB 9 (hence, the noise

power in the signal passband is considerably larger than the signal power: 12.0 U ). 211 windows are used for estimating the correlation matrix. To simplify the interpretation of illustrations, the sampling period is chosen equal to T c =T s /31, and there is no echo on the channel. Here, the desynchronization is approximately

39.00

s

T t Figure 1 shows the eigenvalues: we can clearly distinguish the first and second eigenvalues. We can estimate the noise variance by:

| |P

i i

n

P 3

221O V we obtain:

5

21042.3u n V We have also:

611012.1u O 6

21082.0u O Then, using the equations, we obtain:

12.0? U

38.0?0 s

T t

These values are close to the true values.

Figure 1: Estimated eigenvalues

Figure 2 shows the normalized first and second eigenvectors. These vectors are then concatenated,and we obtain the estimated sequence shown on figure 3. For comparison, the true sequence is also shown.

This result shows that a good estimation is obtained, even with very low SNR. The cosine of the

angle between the vectors shown on figure 3 is close to 1: its value is 0.972

Figure 2: Normalized eigenvectors

Figure 3: Estimated and true spreading sequences

5.CONCLUSION

A method for estimating the spreading sequence of a DS-SS signal in a non-cooperative context has been proposed. The method provides good results even for very low signal to noise ratio (negative SNR). No hypothesis was done on the nature of the spreading sequence: it can be a sequence generated by pseudo-random shift-registers, such as Gold sequences, but this is not a requirement.

Once estimated by this method, the sequence can be used by a traditional spread spectrum receiver, in order to retrieve the symbols.

REFERENCES

[1]G. Burel, ? Detection of Spread Spectrum

Transmissions using Fluctuations of Correlation Estimators”, IEEE Int. Symp. on Intelligent Signal Processing and Communication Systems (ISPACS’2000), November 5-8, 2000, Honolulu, Hawaii, USA, accepted

[2]K.S. Kim et al., “Analysis of quasi-ML multiuser

detection of DS/CDMA systems in asynchronous channels”, IEEE Trans. on Communications, vol 47, No. 12, December 1999

Raymond. L. Picholtz, Donald L. Schilling, Laurence B. Milstein, “Theory of Spread-Spectrum Communications - A Tutorial”, IEEE Trans. on Communications, V ol. COM- 30, No. 5, May 1982, pp. 855- 884.

John G. Proakis, “Digital communications”, Third Edition, Mac Graw Hill International Editions, 1995.

Dilip V. Sarwate, Michael B. Pursley,“Crosscorrelation Properties of Pseudorandom and Related Sequences”, Proceedings of the IEEE, V ol. 68, No. 5, May 1980, pp. 593- 619.