Efficient Bank of Correlators for Sets of GCL Sequences

Field of the Technology

The present invention relates to a method for correlation of an input signal a receiver with Generalized Chirp-Like (GCL) sequences being derived from a single Zadoff-Chu sequence modulated with at least two modulation sequences.

The present invention also relates to a receiver arranged for correlation of an input signal with Generalized Chirp-Like (GCL) sequences being derived from a single Zadoff-Chu sequence modulated with at least two modulation sequences.

The present invention also relates to a communication system between a first transceiver and a second transceiver, at least one of said first and second transceivers including a receiver arranged for correlation of an input signal with Generalized

Chirp-Like (GCL) sequences being derived from a single Zadoff-Chu sequence modulated with at least two modulation sequences.

Background of the Invention

In most mobile communication systems of today, there are specific requirements regarding cell search and synchronization of a radio base station and a mobile terminal in order to secure a correct data transmission. One example of such a system is the Universal Terrestrial Radio Access Network (UTRAN). There are also a number of other such mobile communication systems that have corresponding needs regarding cell search and synchronization.

In such mobile communication systems, synchronization is often performed both in uplink and downlink. In one step of the synchronization, downlink synchronization, the mobile terminal synchronizes to the carrier frequency and the frame timing of the radio base station. This synchronization, however, is not sufficient to ensure that the radio base station can properly receive the signals from the mobile terminal, since mobile terminals may be located at various distances relative to the radio base station.

Consequently, further synchronization, uplink synchronization, is needed since the distance between a radio base station and a mobile terminal, and hence the round trip time, is in general unknown.

For uplink synchronization of the mobile terminals, a random access channel

(RACH) can be used. RACH is in some systems contention-based, which means any mobile terminal within the cell may transmit on the resource allocated to RACH.

Consequently, several mobile terminals may attempt to transmit synchronization signals simultaneously. In order to reduce the risk that the radio base station fails to distinguish signals from different mobile terminals, a set of random access preamble sequences is provided, a set being two or more preamble sequences, wherein each mobile terminal randomly selects one such random access preamble sequence. The random access preamble sequences selected by each mobile terminal can then be uniquely distinguished by the radio base station.

In a cell search situation, it could also be possible for a mobile terminal to choose one of a number of different preambles to send to a radio base station. The choice of one of these preambles, made by the mobile terminal, could in this case then also convey some information to the radio base station, e.g. telling the radio base station which services the mobile terminal requests.

Successful detection of the random access preamble sequence is necessary for the mobile terminal to access the network. It is therefore important that the transmitted random access preamble sequence requires a low power amplifier backoff to allow for high average transmit power and hence good coverage. The random access preamble sequences in uplink should preferably have the following properties:

- Good autocorrelation properties to allow for accurate timing estimation,

- good cross-correlation properties to allow for accurate timing estimation of different simultaneous and partially synchronized (i.e. downlink synchronized) preamble sequences, wherein the phase difference is limited by the maximum round- trip time in the cell, and

- zero cross-correlation for synchronous and simultaneous preamble sequences.

These properties are satisfied by the use of Zero-Correlation Zone (ZCZ) sequences. ZCZ sequences should thus preferably be used for the preamble sequences used in cell search and synchronisation. ZCZ sequences can be derived from Generalized Chirp-Like (GCL) sequences, which is described in the following.

Generalized chirp-like (GCL) sequences belong to the family of Constant Amplitude Zero Autocorrelation (CAZAC) sequences. The CAZAC sequences have ideal periodic autocorrelation and close to ideal aperiodic autocorrelation. Zero periodic autocorrelation in at least a zone around zero delay is an important property of a transmitted sequence to enable accurate time-of-arrival estimation. Furthermore, the CAZAC sequences have constant amplitude. A band-limited signal obtained by pulse-shaping of a CAZAC sequence will have small power variations, thus allowing for low-cost power amplifiers and high efficiency.

GCL sequences are modulated Zadoff-Chu sequences, see further reference document [I]. (There is a list of reference documents at the end of this specification.)

A GCL sequence {c(k)} is defined as c(k) = a(k)b(kmodm), k = 0,1,...,N-I, (1) where N=sm ² , s and m are positive integers, {b(k) } is any sequence of m complex numbers of unit magnitude, and {#(£)} is the Zadoff-Chu sequence

, is any integer, (2) where and r is relatively prime to N. W _n ^p is a shorthand notation for Qxp(-j2πrp/ή).

If two GCL sequences c _x (k) and c _y (k) are defined by using the same Zadoff-Chu sequence {a(k)} but different arbitrary orthogonal modulation sequences {b _x (k)} and {b _y (k)}, they are so-called zero-correlation zone (ZCZ) sequences, i.e. the periodic cross-correlations are zero for all shifts p such that 0<p|<r, where T=sm-\ is the length of the zero correlation zone. The aperiodic cross-correlations are in general low for shifts within the zero-correlation zone. The low cross-correlation property allows for detection of several quasi-simultaneous transmissions of different GCL sequences based on the same Zadoff-Chu sequence, even when the received signal powers are very different.

From the autocorrelation and cross-correlation properties as well as the limited power variations, a set of orthogonal GCL sequences using the same Zadoff-Chu sequence is therefore useful for non-synchronized random access preambles.

A detector, in for instance a radio base station transceiver, for non-synchronized random access preambles based on such a set of GCL sequences needs to correlate the received signal with all sequences in the set of GCL sequences for a range of delays. Such correlations are computationally complex. A background art implementation of an efficient matched filter for a single GCL sequence has been presented in reference document [2], This solution thus only relates to reception of one GCL sequence.

The implementation in reference document [2] is based on an appropriate decomposition of the Zadoff-Chu sequence. Let

k = smi + d, A = O ₅ I, , ..., N - I, N = sm ² ,

/ = 0, 1, , ..., w - l, . (3) d = 0, 1, , ..., sm -l

Then

_a

where we have used (-I) ^* '' = {-\) ^s> . The filter matched to c(k) is equivalent to a correlator that acts on an input signal u(k).

The output z is given by

<n) = ∑ _k ^N : _Q ^l c(kyu(n- N + l + k) _ ₍₅₎

Using equations (2), (3), and (4) in equation (5) gives

*(") = σ^/CO∑^ ¹ u(n-N + l + smi + d)g(d)b(d mod nifW? , (6)

where

and

Another change of variables

d = mx + y, d = 0, l, , ..., sm - l x = Q, l, , ..., s - l, (9)

^ = 0, 1, , ..., w - l

in equation (6) and setting ri = n - N + 1 gives

* ⁽ O = σ«/ ⁽ 0∑2, ∑£ « ^(« ' + ^s mi + ^» *+ ^y)g( >>* + y)Ky ⁾ X7 • ⁽ io ⁾

The last summation in equation (10) represents the /th frequency of the w-point discrete Fourier transform (DFT) of the (si+x)ih block of m windowed input samples. Denote the /th frequency of the /M-point DFT of the windowed (_r/-hc)th block by S _ilX (i). Then equation (10) can be expressed as

Hence, z(n) is a weighted sum of DFT outputs where the DFTs are performed on sm different windowed blocks of the input signal. In equation (11) the/ ^' th frequency of the DFT of the windowed (s/)th block is multiplied byβj). In the expression for a later output z(η+smf) the Oth frequency of the DFT of the same windowed block is multiplied by/(0). This property suggests that one can calculate all m frequencies of a single windowed block, multiply the 7th frequency output byβj) and delay it by sm(j- 1) samples. Calculating all m frequencies of the DFT simultaneously can be done efficiently using a Fast Fourier transform (FFT).

The efficient correlator implementing the matched filter from reference document [2] is shown in fig. 1, with the notation g _x (y)=g(mx+y).

The hardware complexity of a correlator can be defined as the number of required complex multiplications and additions per input sample. For a conventional correlator there are N multiplications and JV-1 additions per input sample, giving a hardware complexity O of O=2N-l.

The number of multiplications M required for the correlator in Fig. 1 is given by M = sm + m - 1 + sM _DFT and the number of additions A is A ~ sm - 1 + sA _DFT , given that the factors g(mx+y) are pre-multiplied by b(y). The term "-1" in the number of multiplications is here due to the fact that/fφ is always equal to 1. The hardware complexity of this correlator depends mainly on the DFT algorithms. FFTs can be devised for all sizes of DFTs. If m is a power of 2, the DFT can be very efficiently implemented by a radix-2 FFT with M _DFT = — log ₂ m

and A _DFT = m log ₂ m . This instead gives a hardware complexity of

O = \.5smlog ₂ m + (2s + V)m - 2. (12) The hardware complexity can thus be lowered for a single GCL sequence correlator by the use of FFTs instead of DFTs when implementing the correlator.

However, the complexity of the correlation dramatically grows when more than one GCL sequence is used. A detector, in for instance a radio base station transceiver, then needs to correlate the received signal with all sequences in the used set of GCL sequences. More computations must then be made in the matched filters of the receivers in systems in which, for example, a number of different preamble sequences are used. In receivers receiving such signals, complexity is a problem and complexity reduction is thus especially important.

Lower complexity is wanted since lower complexity results in less circuitry, less processor computations and less power consumption in the receiver. Since receivers in communication systems generally have limited circuitry space, processing abilities and power resources, these properties are highly desirable.

Summary of the Invention

It is an object of the present invention to provide a method and a receiver that solves the above stated problem, i.e. to reduce the complexity of correlation of an input signal when a set of GCL sequences are used for preambles or the like.

The complexity of the correlation dramatically grows when more than one GCL sequence is used. The present invention therefore aims to provide a correlation

method and a receiver implementing the method having less complexity than the correlation methods and receivers known in the background art.

The object is achieved by an above mentioned method for correlation of an input signal according to the characterizing portion of claim 1, i.e. by performing, in a step after said processing in said first delay line, a multiplication of samples of said input signal with elements of modulation sequences corresponding to the at least two modulation sequences being used for deriving said GCL sequences, and performing said DFT processing using a single DFT circuit.

The object is also achieved by an above mentioned receiver arranged for correlation of an input signal according to the characterizing portion of claim 20, i.e. the receiver further includes means for performing, in a stage after said stage for first delay line processing, a multiplication of samples of said input signal with elements of modulation sequences corresponding to the at least two modulation sequences being used for deriving said GCL sequences, and means for performing said DFT processing in a single DFT circuit.

The object is also achieved by an above mentioned communication system arranged for correlation of an input signal according to the characterizing portion of claim 27.

The method for correlation of an input signal according to the present invention and the receiver and communication system implementing the method make it possible to reduce the complexity involved in receiving and correlating an input signal when a set of GCL sequences based on a single Zadoff-Chu sequence are used in the system.

In an embodiment of the invention, complexity reduction is achieved, for receivers receiving signals possibly including any of a set of arbitrary modulation sequences, by separating calculations related to the set of modulation sequences from the rest of the calculations. Calculations not related to the set of modulation sequences can thereby be calculated once for all modulation sequences, instead of duplicating them for every modulation sequence. When implementing the invention in a receiver structure, this separation corresponds to performing the multiplication of received signal samples with modulation sequence elements in the last stage of the receiver.

There is further only one DFT or one FFT used in the receiver according to this

embodiment of the invention. These features effectively reduce the complexity of the correlation.

In an embodiment of the invention, complexity reduction is achieved, for receivers receiving signals possibly including any of a set of modulation sequences defined as DFT sequences, b,(k) = W^, I = 0,1,... ,m-\ , by incorporating the multiplication of received samples with modulation sequence elements into the DFT or FFT processing. Also in this embodiment of the invention, only one DFT or one FFT is used in the receiver. These features further reduce the complexity of the correlation. Also, the use of DFT sequences as modulation sequences has the advantage of improving Peak-to- Average Ratio (PAR) for the transmitted signal. A good PAR value lowers the demands of amplifiers in the transmitters.

Detailed exemplary embodiments and advantages of the method, receiver and communication system according to the invention will now be described with reference to the appended drawings illustrating some preferred embodiments.

Brief Description of the Drawings

Fig. 1 shows a background art correlator, used for a single GCL sequence.

Fig. 2 shows a correlator according to the present invention, used for an arbitrary set of modulating sequences.

Fig. 3 shows a correlator according to the present invention, used for a set of modulating sequences being DFT sequences.

Detailed Description of the Invention

When expanding the background art matched filtering shown in reference document [2] from receiving one single GCL sequence to being able to receive a set of sequences containing more than one GCL sequence, a straightforward solution based on the background art could be to apply the efficient correlator for a single GCL sequence to each sequence in the set separately.

However, the complexity grows linearly with the number of sequences in the set. For m sequences the complexity is

O = 1.5sm ² log, m + (2s + \)m ² - 2m

(13) = (3 + l.5log ₂ m)N + m ² - 2m.

This solution has a high level of complexity.

Another possible solution could be to, for each delay, multiply the received signal element-wise with the complex conjugate of the Zadoff-Chu sequence a(k) to create a vector of length N. Then for k=0, 1, ..., m-l, every mth element (k+jm, y-0,1,..., sm- 1) of the resulting vector is summed. The result is a vector of length m.

Finally, if the modulating sequences are DFT sequences, an /w-point DFT gives the receiver output for all preambles derived from the same Zadoff-Chu sequence. The

resulting number of multiplications for m being a power of 2 is M = N λ — log ₂ m

and A = N - 1 + m log ₂ m , which gives a hardware complexity of

O = 2N + 1.5mlog ₂ m - l . (14)

This solution has less complexity than the complexity of the separate efficient correlators shown in equation (13).

Equations (13) and (14) show complexity of two straightforward solutions for reception of more than one GCL sequence when having methods known from background art as a starting point and expanding them to sets of GCL sequences.

However, the level of complexity in these solutions is still fairly high and there is a need for further complexity reduction.

In Fig. 2, a receiver implementing an embodiment of the present invention, being applicable to any set of modulating sequences, is shown. An incoming signal can possibly include at least one GCL sequence out of a set of GCL sequences generated by modulating a single Zadoff-Chu sequence with different modulating sequences bι(k). According to the present invention, the receiver therefore receives the incoming signal by correlating it with the GCL sequences in that set of GCL sequences. A receiver according to this embodiment of the invention separates the correlation into four stages. A first stage includes a first delay line, generating m samples for each delay of the correlation. A second stage includes, regardless the number of modulating sequences, a single DFT-circuit, into which the m samples generated by the first stage are fed. The second stage may also be implemented using a single m-

point FFT circuit for more effective processing. A third stage includes second delay lines further processing the output of the DFT or FFT and feeds a fourth multiplication stage with samples. The fourth stage performs multiplication of samples of the received signal with elements of the modulation sequences used for creating the GCL sequences at the transmitter end, thereby generating one output sample for each GCL sequence correlator.

In the receiver in fig. 2, every smth. sample of the input signal is in the first delay line stage multiplied by one of the coefficients /to generate the inputs to the DFT. The m samples outputted from the DFT are, in the second delay line stage, further fed to m filters, each filter having coefficients from the sequence g, to produce a vector v of length m with elements v(y), y=0,l, ...,m-l. The vector v is independent of the modulating sequences and can therefore be calculated once for all GCL sequences. Finally, the column vector v is, in the multiplication stage subject to a matrix multiplication, Bv, where each row of the matrix B is the complex conjugate of a modulating sequence, i.e. (B>)i _k =bι{K) ^* .

Mathematically described, the inventors of the present invention have realized that a new bank of correlators can be obtained from background art equation (10) by changing the order of summation in the following way: ^z ' O ^{) b} ι ^(y ϊ σIIo s ^(mx + + ^{smi +mx+ y)} f ⁽ Mm ^iy > C ¹⁵⁾

where / is the label of the modulating sequence.

Compared to equation (10), the complex conjugate of the elements b,(y) from the modulation sequence appears in equation (15) in the leftmost summation instead of in the rightmost summation.

Vector elements v(y) are the result of the two inner summations (the two rightmost summations) and are independent of the modulating sequences. The vector v can thus be calculated once for all GCL sequences derived from a single Zadoff- Chu sequence. Hence, equation (15) can be expressed as

and the vector of correlator outputs z with elements zι(n), this equals in matrix notation

z=Bv.

According to this embodiment of the present invention, only one DFT is used, regardless of the number of modulation sequences used. Further, calculations in equation (10) related to the set of modulation sequences are in equations (15) and (16) separated from the rest of the calculations. This separation makes the calculations not related to the set of modulation sequences more effective, since they can be calculated once for all modulation sequences. A complexity reduction is thereby achieved for receivers receiving signals including any of a set of different modulation sequences, i.e. receiving signals including any of a set of GCL sequences.

The complexity reduction of the present invention can also be understood from studying figs. 1 and 2. As can be seen in the background art solution for a single GCL sequence in fig.l, multiplication of input signal samples with modulation sequence elements is performed in the first stage of the receiver. That is, all processing in the correlator after this multiplication is dependent of the modulation sequence b. From this follows that, if this structure was used for a set of GCL sequences, the whole correlator shown in fig. 1 would have to be duplicated once for each GCL sequence. It is easy to realize that this would result in an enormous complexity when the number of GCL sequences increases.

As can be seen in fig. 2, on the other hand, multiplication of input signal samples with modulation sequence elements is, according to the present invention, performed in the last stage of the receiver. The preceding stages of the receiver is thus independent of the set of modulation sequences b and can be calculated once for all modulation sequences, regardless of the number of modulation sequences. Thus, the solution to perform the modulation multiplication in a stage later than the first stage of the receiver reduces the complexity of the receiver when dealing with sets of GCL sequences.

The complexity of the embodiment of the present invention shown in fig. 2 can also be calculated by estimating the number of complex multiplications and additions.

The number of complex multiplications is M = sm + m - 1 + M _DFT + M _B and the

number of additions is A = (s - \)m + A _DFT + A _B , where M _B and A _B are the number of multiplications and additions of the matrix multiplication, respectively.

One interesting case is when B is the DFT matrix, i.e. when a set of modulating sequences are defined as DFT sequences, b, (k) = W* , I = 0,1, ...,m ~\ . Then

M = sm + m - l + 2M _DFT , and

A = (s - ϊ)m + 2A _DFT

If m is a power of 2 the resulting hardware complexity using radix-2 FFTs is O = lm\o% ₂ m + 2sm -\ . (17)

The complexities of background art given by equation (14) and of this embodiment of the invention, defined in equation (17), are given in Table 1. The invention is less complex than background art solutions for all values of m and s. (Variables N, m and s are here the variables used in equations (1) and (2).) The reduction in complexity further increases dramatically with increasing 5.

Table 1. Hardware complexity of background art and invention for sets of sequences

The invention is also less complex than background art solutions for correlation with a single GCL sequence. For a single sequence the g factors can be pre-multiplied with the modulating sequence b so that

A _B = M _B = 0.

Then

M = sm + m -l + M _DFT , and

A = sm - m + λ DFT '

and for m power of 2 the hardware complexity O equals

0 = 1.51og ₂ ffz + 2 _> srø - l . (18)

The complexity of prior art equation (12) is compared to that of the invention equation (18) for a single sequence in Table 2. The invention reduces the complexity for all values ofs and m, in particular as s increases.

Table 2. Hardware complexity of background art and invention for single sequence

In fig. 3, another embodiment of the present invention, applicable in case where a set of modulating sequences are defined as DFT sequences, b, (k) = W*, I = 0,1,...,rø - l , is shown.

A correlator according to this embodiment of the invention has three stages, a first delay line stage, a DFT stage and a second delay line stage. The first delay line stage includes a delay line including sm delays, sm means for multiplication of samples of said input signal with first delay line coefficients g and means for adding sm first delay line outputs together forming m output samples. The DFT stage includes a single DFT circuit. The DFT stage may also be implemented using an m- point FFT circuit for more effective processing. The DFT stage receives m samples from the first delay line stage and performs multiplication of samples of the received signal with elements of the set of modulation sequences.

The multiplication of the received signal samples with the modulation signal elements can here be performed in the DFT stage since the set of modulation sequences are DFT sequences. The DFT stage outputs m parallel samples of the processed signal. The second delay line stage includes m parallel delay lines each including delays and means for multiplication of said input signal with second delay line coefficients / The second delay line stage essentially delays and multiplies each output sample from the DFT circuit with second delay line coefficients /in a way that all parallel DFT output samples are multiplied with different coefficients / and that these coefficients /are shifted in each delay step of each delay line. The second delay line further adds results of these multiplications in each delay line together and outputs / samples in parallel as an output signal.

Mathematically, the correlation output of the /th sequence, zι(ri), in the correlator shown in fig. 3 is given by

⁹⁾

i.e., the output i+l from the DFT is multiplied by Xz).

According to this embodiment of the present invention, only one DFT is used, regardless of the number of modulation sequences used. Further, calculations in equation (10) related to the set of modulation sequences, here being DFT sequences b _t (k) = W^ , I = 0,l,...,m -l , have in equation (19) been moved from the rightmost summation in equation (10) to the DFT summation. This makes calculations related to multiplication of modulation sequences more effective, since they can be made within the already present DFT processing. A complexity reduction is thereby achieved for receivers according to this embodiment, receiving signals including any of a set of different DFT modulation sequences, i.e. receiving signals including any of a set of DFT GCL sequences.

The number of complex multiplications for this embodiment is M = sm + M _DFT + m(m - ϊ) , since T(O)=I, and the number of additions is A = (s - \)m + A _DFT + m{m - 1) . If /w is a power of 2 the resulting hardware complexity using radix-2 FFTs is

O = 1.5mlog ₂ m + 2^« + 2w ² -37« . (20)

The complexities of background art given by equation (14) and of this embodiment of the invention, defined in equation (20), are presented in Table 3. This embodiment is less complex than background art solutions for most values of N, m and s, especially for large values of s. (Variables N, m and s are the variables used in equations (1) and (2).)

Table 3. Hardware complexity of background art and invention for sets of sequences

Thus, the solution to perform the modulation multiplication in a stage later than the first stage of the receiver reduces the complexity of the receiver when dealing with sets of DFT GCL sequences.

Further, the use of DFT sequences as modulation sequences has the advantage that these sequences result in transmission signals having very good PAR characteristics. This allows use of simple and cheap amplifiers in the transmitter of the signals as well as lower complexity in the transmitter.

Correlation methods, receivers and communication systems according to the invention may be modified by those skilled in the art, as compared to the exemplary embodiments described above. It is, for instance, understood by a skilled person that a receiver according to the invention also may receive other types of signals than the GCL sequences described in this specification. Correlation of the input signal with a set of GCL sequences results in a reception of possible GCL sequences, whereas correlation with sequences corresponding to the other types of signals results in reception of the other type of signals.

Reference documents

[1] B. M. Popovic, "Generalized Chirp-Like Polyphase Sequences with Optimum Correlation Properties," IEEE Trans, on Information Theory, Vol. 38, no. 4, pp 1406-1409, July 1992. [2] B. M. Popovic, "Efficient matched filter for the Generalized Chirp-Like polyphase sequences," IEEE Trans, on Aerospace and Electronic Systems, Vol. 30, no. 3, pp 769-777, July 1994.