A method and an arrangement for despreading a coded sequence in a communication system

The invention relates to a method and an arrangement for implementing a bank of correlators, corresponding to a set of Orthogonal Gold codes, in a receiver used in a Direct Sequence Code Division Multiple Access system (DS-CDMA). The bank of correlators generates N correlation values (CVo,...,CVn-i) from N received symbols (so,si,...,sn-i) in a sequence. The received symbol sequence (so,si,...,sn-i), where each symbol has been spread by an Orthogonal Gold code respectively, is buffered (401). The buffered symbol sequence is multiplied (402) element-by-element with an arbitrary sequence (ao.ai.....sn-i), in order to obtain a set of products (so*ao,si*ai,...,SN-i*aN-i)· Said arbitrary sequence is the same sequence used when generating the Orthogonal Gold Codes. The set of products (so*ao,si*ai,...,SN-i*aN-i) is then permuted (403) in order to obtain a sequence, which is equal to a sum of a number of sequences from a set of Walsh sequences. The sequence is then transformed (404) with Fast Hadamard Transform as to obtain said correlation values (CVq.....CVn-i).

J

CODED SEQUENCE IN A COMMUNICATION

<img file="AU738415B2_D0001.tif" />

WO 98/33290

PCT/SE97/02183

A METHOD AND AN ARRANGEMENT FOR DESPREADING A CODED SEQUENCE IN A COMMUNICATION SYSTEM

TECHNICAL FIELD

The present invention relates generally to a method and an arrangement for despreading of a received signal in a multicode.

DS-CDMA system and more particularly it relates to a method and an arrangement for implementing a bank of correlators, corresponding to a set of Orthogonal Gold codes or alike, in a receiver used in a Direct Sequence Code Division Multiple Access system (DS-CDMA).

DESCRIPTION OF THE BACKGROUND ART

A spread spectrum communication system employing a direct sequence method, as for example DS-CDMA (Direct Sequence Code Division Multiple Access) system, utilises a method of generating from an information signal, a transmission signal, 15 where the transmission signal have a significantly wide bandwidth with respect to the original information signal. This is a result of spreading the information signal by a high rate spreading sequence such as for example a high bit rate pseudo noise (PN) sequence. The digitised informational signal and the 20 high rate spreading sequence are typically multiplied together.

This combination is called coding or spreading the informational signal. A plurality of coded information signals are transmitted on a same radio frequency carrier wave and jointly received as a composite signal at a receiver. Each of the coded signals 25 overlaps all of the other coded signals, as well as noiserelated signals, in both frequency and time. By correlating the composite signal with one of the unique spreading sequences, the corresponding information signal can be isolated and decoded. Each information signal is thus allocated a unique spreading f

WO98Z33290

PCT/SE97/02183 code and a receiver uses the same spreading code as that used in the transmitter to perform a despread operation.

Multicode transmission scheme is a method to provide high-rate and variable-rate data services in DS-CDMA systems without, decreasing the processing gain or increasing the spreading bandwidth. In such a scheme several code channels are assigned to a single user. High-rate data stream is split into a number of parallel low-rate streams. These low-rate streams are spread by different sequences and added together before power amplification.

To avoid interference between different code channels of a single user, all spreading sequences (codes) should be orthogonal within data symbol duration. To make the other-user interference as a noise-like interference, each single users code channels are further multiplied by a user specific pseudorandom spreading sequence. The number of used orthogonal codes depends on the current data rate. The receiver will have an easier task if it knows which spreading codes are currently used, or at least knows the number of code channels.

An example of orthogonal sequences is a so-called Orthogonal Gold sequences. A set (G ) of Orthogonal Gold codes (OG₀,OG_lt . . . , OGn.J with elements belonging to an alphabet of 0 and 1, is defined as a matrix obtained from a modulo-two summation (XOR) between each row of an orthogonal matrix (M) and a sequence (a ) , i . e.

<td></td><td> ’ OGo ' OGi</td><td colspan="2"> a xi ® a</td>

<td> G =</td><td></td><td> =</td><td></td>

<td></td><td> . . .</td><td></td><td> . . .</td>

<td></td><td> ΟθΝ-Χ.</td><td></td><td></td>

Μ Φ a

WO 98/33290

PCT/SE97/02183 where

<td></td><td> 0</td><td> 0</td><td></td><td> 0 0</td><td> 0</td>

<td></td><td>^X1</td><td>^X2</td><td>^X3</td><td> • · · ^XN-!</td><td> 0</td>

<td> =</td><td> x₂</td><td>^X3</td><td>^X4</td><td> ... x_x</td><td> 0</td>

<td></td><td> _^XN-1</td><td>^X1</td><td>^X2</td><td> • · · ^XN-2</td><td> 0</td>

and a = [a_x a₂ ... a.., o] .

The orthogonal matrix (M) is obtained from another matrix (M) consisting of all cyclic shifts of a first maximum length PN sequence (m-sequence) {x_k}, where k=l,2,...,N-1, by bordering the matrix (M) on the top with a row of zeros and on the right side by a column of zeros.

The sequence (a) is another m-sequence {a_k}, where k=l,2,...,N1, with a zero added on the right end. The sequences (x_k) and (a_k) should form a so-called preferred pair of m-sequences to obtain optimum periodic cross-correlation function. Optimum cross-correlation function is one which has minimum maximum value for a given sequence length and a given number of sequences .

However, the actual definition of the Orthogonal Gold sequences is more general, in the sense that the sequence (a) can be an arbitrary sequence with zero at the right end. In that case the set of sequences (G) would still be orthogonal but the periodic cross-correlation functions between the sequences from the set will not be optimum.

WO 98/33290

PCT/SE97/02183

An equivalent definition of the set. (G) of Orthogonal Gold sequences with elements belonging to a alphabet of -1 and +1 can be obtained by mapping 0-»l and l-> -1, while the modulo two summation should be replaced by multiplication between row elements of the matrix M and elements of the sequence a .

The usual receiver method for CDMA systems is so-called RAKE combining, which assumes weighted summation of separately despread multipath signal components, with appropriate compensation of corresponding components' delays.

In the multicode CDMA systems, the number of RAKE receivers needed for a single mobile-base station connection is equal to the maximum number of parallel code channels. As all RAKEs work in parallel, the baseband receiver consists of multiple despreaders, each corresponding to a different receiving path, and each consisting of a number of correlators corresponding to the different code channels.

The despreader implementation depends on the actual spreading method, i.e. which spreading sequence is used. If the spreading sequence is binary, with +1 and -1 elements, it is called Binary Phase Shift Keying (BPSK) spreading, while when the spreading method is complex, consisting of real and imaginary binary sequences it is called QuadraPhase Shift Keying (QPSK) spreading. Usually QPSK spreading is performed with different real and imaginary binary sequences.

The efficiency of the despreader for the multicode CDMA systems directly depends on a bank of correlators corresponding to the binary spreading sequences .

The maximum number of sequences in any orthogonal set is equal to the sequence length. Therefore, if the length of sequences is N, it is necessary to perform N² operations for each sample at the output of the bank of correlators.

An implementation of the bank of correlators which provides less N²5 operations per output sample is an efficient implementation.

Two kinds of orthogonal sets of sequences are proposed for a Multicode DS-CDMA scheme; sets of Walsh sequences and sets of Orthogonal Gold sequences. A bank of correlators corresponding to a set of Walsh sequences can be efficiently implemented by using a Fast Hadamard Transform (FHT). In 10 that, case the number of operations required for each output sample is N x log₂ N.

An implementation of a bank of correlators corresponding to orthogonal Gold sequences that requires less than N² operations is also desirable.

SUMMARY OF THE INVENTION

The object of present invention is to solve the problem how to reduce the 15 complexity of a bank of correlators matched to a set of Orthogonal Gold sequences.

Another problem which the invention is intended to solve is to reduce the power consumption in a receiver when despreading received radio signals.

According to a first aspect of the invention there is provided a method of despreading a symbol sequence (S^S,.....S^,) to obtain a number of correlation values (0^,...,07^), where said symbol sequence has been spread by a set of Orthogonal Gold sequence (G), which have been generated by means of an arbitrary sequence (a₀,a₁₍..., a^), including the following steps:

a) multiplying element-by-element of said symbol sequence (Sq.S,.....S_N.,) with said arbitrary sequence (a₀,a,,...,8^.,), in order to obtain a set of products (®o ®o> ®1 .....>S_N., 3n-i)>

b) permuting said set of products (s₀*a₀, s/a,......in order to obtain a sequence (w) equal to a sum of a number of sequences from a set of Walsh sequences;

<img file="AU738415B2_D0002.tif" />

c) transforming said sequence (w) with a Fast Hadamard Transform so as to obtain said correlation values (CV^..·.^^,).

According to a second aspect of the invention there is provided a method of despreading a symbol sequence (80,81,...,8^) to obtain a number of correlation values (Ονο,.,.,Ον^), where said symbol sequence has been spread by a set of Orthogonal Gold sequences (G), which have been generated by means of an arbitrary sequence (a^a!,...^.,), including the following steps:

a) permuting said symbol sequence (S_o, Sp.-.S^j.,), according to a certain rule in order to obtain a permuted version of said sequence (S_p0, 8^,...,8^):

b) permuting said arbitrary sequence (a₀, ai,...,a_N_i), according to the same rule in order to obtain a permuted version of said sequence (a_p0,a_p1,...,a_pN.i);

c) multiplying element-by-element of said permuted version of the symbol sequence (S_p0,S_p1.....S^.,) with said permuted version of said arbitrary sequence (a_p0,a_p1.....apN.J, as to obtain a sequence (w) equal to a sum of a number of sequences from a set of Walsh sequences;

d) transforming said sequences (w) with Fast Hadamard Transform as to obtain said correlation values (CV^..·.^^).

According to a third aspect of the invention there is provided a method of despreading a symbol sequence (Sq.St.....S^) as to obtain a number of code channels (ΟΗο,ΟΗ,,.,.,ΟΗμ) from an incoming code spread radio signal, which is quadrature, detected as to obtain an inphase signal and a quadrature signal, including the following steps:

correlating said inphase signal according to steps in claim 1, therewith to 25 obtain N inphase correlation values;

correlating said quadrature signal according to steps in claim 1, therewith to obtain N quadrature correlation values;

arrange said inphase correlation values and said quadrature correlation values according to a corresponding spreading method, therewith, to obtain said

<img file="AU738415B2_D0003.tif" />

6a

According to a forth aspect of the invention there is provided A method of despreading a symbol sequence (S_o,8,,...8_Ν.,) as to obtain a number of code channels (CH₀,CH,,...,CH_M) from an incoming code spread radio signal, which is quadrature detected as to obtain an inphase signal and a quadrature signal, characterised in the following steps:

correlating said inphase signal according to steps in claim 2, therewith to obtain N inphase correlation values;

correlating said quadrature signal according to steps in claim 2, therewith to obtain N quadrature correlation values;

arrange said inphase correlation values and said quadrature correlation values according to a corresponding spreading method, therewith to obtain said code channels (ΟΗ₀₎ΟΗ,.....CH_M).

According to a fifth aspect of the invention there is provided an arrangement of a bank of correlators for despreading a symbol sequence (S₀,S„...S_N.,) to obtain 15 a number of code channels (CH₀, CH,.....CH_N.,), where the code channels have been spread by a set of Orthogonal Gold sequences (G), which have been generated by means of an arbitrary sequence (a₀,a„...,a_N.,), characterised in that said arrangement includes:

means for permuting the symbol sequence (S_o,S„...,S_N.,) according to a 20 certain rule, in order to obtain a permuted version of sequence (S^.Sp,.....S_pN.,);

means for permuting the arbitrary sequence (a₀,a„...,a_N.,), according to the same rule, in order to obtain a permuted version of said sequence (®ρθ,3ρΐ, · · · >θ·ρΝ-1) >

means for multiplying element-by-element of said permuted version of said symbol sequence Spo.Sp,.....S_pN.,) with said permuted version of said arbitrary sequence (a_p0,a_p1.....a_pN.,) as to obtain a sequence (w) which is a sum of a number of sequences from a set of Walsh sequences;

at least one bank of Walsh correlations, implemented as Fast Hadamard

Transformer, operable to transforming said sequence (w) to obtain correlation values (CV₀.....CV_N.,).

<img file="AU738415B2_D0004.tif" />

6b

According to a sixth aspect of the invention there is provided an arrangement of a bank of correlations for despreading a symbol a symbol sequence (Sq.Sj S^,) to obtain a number of code channels (CH₀, CH!, ...,CHnJ, where the code channels have been spread by a set of

Orthogonal Gold sequences (G), which have been generated by means of an arbitrary sequence (80,3,,...,3^), characterised in that arrangement includes:

means for multiplying element-by-element of said symbol sequence (S₀,S,.....S_N.,) with said arbitrary sequence (a_0>a,,...,a_N.,), as to obtain a set of products (s₀*a₀, s,*a,......S_N.,*a_N.,);

means for permuting said set of products (s₀*a₀, s,*a,......S_N.,*a_N.,) according to a certain rule, in order to obtain a sequence (w) which is the sum of sequences from a set of Walsh sequences;

at least one bank of Walsh correlations, implemented as Fast Hadamard 15 Transformer, operable to transforming said sequences (w) to obtain said correlations values (CV₀,...,CV_N.,).

In accordance with embodiment of the present invention, the aforesaid problems are overcome and resolved by implementing the bank of correlators in a more efficient way compared to a straightforward implementation which used a 20 correlator for each Orthogonal Gold sequence.

The implementation of the bank of correlators is performed in the following way. Multiplying a received sequence element-by-element with an arbitrary sequence, that is used for generation of the Orthogonal Gold sequences, as to obtain a set of products. The elements in the set of products are permuted 25 according to a certain rule in order to obtain a permuted sequence which is equal to a sum of a number of sequences from a set of Walsh sequences. A Fast Hadamard Transform is then performed on said permuted sequence as to obtain correlation values between the received sequence and each possible Walsh sequence.

<img file="AU738415B2_D0005.tif" />

6c

An advantage afforded by embodiments of the present invention is that the number of operations used when despreading a received sequence are essentially decreased.

A further advantage afforded by embodiments of the present invention is that due to the smaller number of operations during the despreading of received radio signals a reduction of power consumption is obtained.

Another advantage afforded by embodiments of the present invention smaller area needed for integrated circuit implementation of the aforementioned bank of correlates.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention will now be described in more detail with reference to exemplifying embodiments thereof and also with reference to the accompanying drawings, in which

Figure 1 is a block diagram illustrating a part of a receiver operable to 15 receive a BPSK-spread signal used in a DS-CDMA system.

<img file="AU738415B2_D0006.tif" />

WO 98/33290

PCT/SE97/02183

Figure 2 is block diagram illustrating part of a receiver operable to receive a QPSK-spread signal used in a DS-CDMA system.

Figure 3 is a block diagram is illustrating background art of a. bank of correlators.

Figure 4 is a flowchart of an embodiment of an inventive method for implementing the bank of correlators.

Figure 5 is flowchart of another embodiment of the inventive method for implementing the bank of correlators.

Figure 6 is a block diagram illustrating an embodiment of an inventive arrangement of the bank of correlators.

Figure 7 is a block diagram illustrating another embodiment of the inventive arrangement of the bank of correlators.

DETAILED DESCRIPTION

Figure 1 illustrates a part of a receiver 100 used in a multicode DS-CDMA system. In a corresponding transmitter, all N transmitted code channels have been spread with a set of Orthogonal Gold sequences G_O,G_1Z . . . respectively, and utilising method called Binary Phase Shift Keying (BPSK). The part of a receiver 100 comprises a quadrature detector 101 which generates an inphase signal on an output 102 and a quadrature signal on an output 103 for radio frequency signals which appear on an input 104. Each output 102,103 is connected to a branch, an inphase signal branch 112 and a quadrature signal branch 113, that comprises the following entities connected to each other: a lowpass filter 105 with a bandwidth proportional to a chip frequency used in the CDMA system; an A/D-converter 106, a pulse

WO 98/33290

PCT/SE97/02183 matched filter 107 which is the same used in the transmitter for spectrum shaping; a downsampling unit 108 for downsampling to one sample per chip and a bank of correlators 109. Each bank of correlators generates N correlation values.

On a first output 110 of the bank of correlators 109 in the inphase signal branch 112 a first code channel inphase signal is generated and on a first output 111 of the bank of correlators 109 in the quadrature signal branch 113 a first code channel quadrature signal is generated. The two said outputs 110,111 are combined into a pair of outputs for a first code channel CH·^ All other outputs of each bank of correlators are combined in the same way to form N pairs of output which correspond to N code channels. Each code channel can be combined with the same code channel obtained from another reception path.

Figure 2 illustrates part of another receiver 200 used in a multicode CDMA system. In a corresponding transmitter, the N transmitted code channels have been spread with a set of Orthogonal Gold sequences G_o,G_x, . . . ,G_N._X respectively, and utilising method called QuadraPhase Shift Keying (QPSK). This method produce N/2 code channels such that each code channel is spread with two sequences in the corresponding transmitter. For example, a first code channel CH! is spread with a first Orthogonal Gold sequence OG₀ and a second Orthogonal Gold sequence OGi .

The part of a receiver 200 comprises the same units as the part of a receiver 100 described in conjunction with figure 1. Due to the fact that the used utilising method is QPSK the number of the received code channels are N/2 and the arrangement of the N outputs of the banks of correlators is different than in the part of receiver 100.

WO 98/33290

PCT/SE97/02183

A first output 201 of the bank of correlators 109 in the inphase signal branch 112 and a second output 204 of the bank of correlators in the quadrature signal branch 113 are connected to an adder 205, which is operable to adding the output signals on the outputs 201,204. A sum is obtained as an output signal on an output 207 of the adder 205. The output signal on the output 207 is the inphase signal of the first code channel 0¾.

A second output 202 of the bank of correlators in the inphase signal branch 112 and a first output 203 of the bank of correlators in the quadrature signal branch 113 are connected to an adder 206, which is operable to adding the output signal on the output 202 to the output signals on the output 203. A sum is obtained as an output signal on an output 208 of the adder 206. The output signal on the output 208 is the quadrature signal of the first code channel CHj. All N outputs from the two banks of correlators are arranged in the same way. This means that the N/2:th code channel is obtained with two last output of the two banks of correlators. That is, a N-l:th output of the bank of correlators in the inphase signal branch 112 and a N:th output of the bank of correlators in the quadrature signal branch 113 are connected in the same way as the output 201 and output 204 and that a N:th output of the bank of correlators in the inphase signal branch 112 and a N-l:th output of the bank of correlators in the quadrature signal branch 113 are connected in the same way as the output 211 and output 212.

The explanation for the above arrangements of the outputs of the banks of correlators can be obtained from the following simple relation, wherein the inphase signal to the bank of correlators is denoted d_T and the quadrature signal is denoted d_Q. The first code channel has been spread with OG₀ and OG!. Hence the

WO 98/33290

PCT/SE97/02183 following multiplication has to be performed to obtain the first code channel CH_X:

(di + j do)(OGo — j OGi) = (diOGo + doOGi) + j(doOGo + diOGi) .

The real part (diOGo + daOGi) is what is obtained on the output 207 and the imaginary part (doOGo + diOGi) what is obtained on the output 208. The real part and the imaginary part correspond to the inphase signal and the quadrature signal of the first code channel respectively.

The implementation of the bank of correlators does not depend on which spreading method that is used in the transmitter. The code channels are obtained by arranging the outputs of the banks of correlators in a way specific for the applied spreading method.

Figure 3 illustrates the background art for the bank of correlators (109, figure 1 and figure 2) used for despreading multicode channels. A bank of correlators 300 comprises N correlators Corr_x, . . ., Corr_N, where each correlator generates a correlation signal on output out_lz . . . , out_N. Each Orthogonal Gold sequence OG₀, . . . ,0G_N._lz used for spreading the code channels in

<td> the transmitter, is</td><td colspan="2"> stored</td><td> in</td><td> registers</td><td> ref_lz .</td><td> ..., ref_N. For</td>

<td> example, in register</td><td> ref _x</td><td> is</td><td> the</td><td> Orthogonal</td><td> Gold</td><td> sequence OG₀</td>

<td> stored and in register</td><td> ref_N</td><td> is</td><td> the</td><td> Orthogonal</td><td> Gold</td><td> sequence ΟΟ_Ν__Χ</td>

stored. A sampled signal received from the downsampling unit 108 is connected to an input 201 of the bank of correlators 109. Each sample is shifted into all registers reg_x, . . . , reg_N and a multiplication is performed continuously bit-by-bit after every shift with the stored Orthogonal Gold sequence. Results of each bit multiplication are summed in summarizer S and the sum is output on the output out_lz ...,out_N respectively as a correlation

WO 98/33290

PCT/SE97/02183 value between the Orthogonal Gold sequence and the received signal. For example, if the Orthogonal Gold sequence OG₀ is stored in the register ref_lz the bank of correlators is connected to the downsampling unit in the inphase signal branch 112, and the BPSK spreading method is used, the correlation signal on the output out_x corresponds to the inphase signal of the code channel CH_X. With the same conditions stated above, except that the bank of correlators is connected to the quadrature signal branch 113, the quadrature signal for code channel CH! is obtained.

This implementation of the bank of correlators is inefficient. To despread all code channels it takes N² operations, which is time- and powerconsuming.

A flowchart, figure 4, illustrates an embodiment of an inventive method concerning how to implement an efficient bank of correlators used in a receiver in a multicode CDMA system. In a first step 401 N input samples SS = s₀, s_x, . . ., s_N__x are buffered. In a second step 402 the input samples s₀, s_x, . . . , s_N__x are multiplied element-by-element with a arbitrary sequence a = a₀, a_x, . . . ,a_N._x, therewith a sequence p = p₀,p_x, · . ,p_N__xs₀*a₀, s_x*a_x, . . ., s_N._x*a_N._x is obtained. The sequence a is the same used when the Orthogonal Gold sequences G are generated in the transmitter. The obtained sequence p is then, in a third step 403, permuted in a certain way, which will be described in more detail below, in order to obtain a sequences w , which is equal to a sum of a number of sequences from a set of so-called Walsh sequences. The sequence w is, in a step 404, transformed with a Fast Hadamard Transform as to obtain a set of correlation values

C = CV₀, . . . ,CV_N._X between said sequence w and each of N Walsh

WO 98/33290

PCT/SE97/02183 sequences. By using this inventive method for an inphase signal and for a quadrature signal it will be possible as earlier described to efficiently despread code channels used in a multicode channel system.

A flowchart, figure 5, illustrates another embodiment of the inventive method. In a first step 501, the N input samples SS = s₀, s_x, . . ., s_N._x are buffered. A permutation is carried out in a certain way, described in detail below, on the buffered input samples SS in a second step 501, in order to obtain a permuted version SS_p = s_p0, s_pl, . . . , s_pN._x of the input sequence SS. In a third step 503 the permuted version of all N input samples s_po/θρίζ · · · / θρΝ-ι are multiplied element-by-element with a permuted version a_p = a_p0,a_pX, . . . ,a_pN._x of the sequence a a₀, a_x, . . . , a_N._x, therewith sequence w = w₀, w_x, . . . , w_N__x^spo*^apo/^spi*^api/ · · · / ^spN-i*^apN-i is obtained. The sequence a is permuted in a certain way, described below, before it is used. The sequence w is then, in a fourth step 504, transformed with the Fast Hadamard Transform as to obtain correlation values

CV₀, . . . , CV_N._X between said sequence w and each of N Walsh sequences .

The permutation rule used in present invention is one which maps Orthogonal Gold codes into Walsh sequences. For each matrix M there are many column permutations which produce the same set of Walsh sequences, but with different ordering of Walsh sequences. All these permutations are related to the natural state sequence of the appropriate linear-feedback shift register sequence generator, or equivalently, to the sequence of Galois Field GF(2ⁿ) elements 1, a, a², ..., aⁿ~² , where a is a primitive element

WO 98/33290

PCT/SE97/02183 of GF(2ⁿ) . The determination of the column permutation of matrix M will be illustrated by the following example.

If N=2ⁿ=8, the m-sequence {xk} = [1 1 1 0 0 1 o] , can be used to generate the matrix M given by:

The m-sequence

Xk+3 =Xk+i+Xk (mod 2 ) {*k} is generated which is obtained by from polynomial: f(x)=x³+x+l over GF(2). The initial the recursion, feedback shift the three or equivalently, the initial state register sequence generator, are of recursion:

primitive values for the 1ineartaken to be:

[^xi x₂ x₃] = [1

The primitive polynomial defines the extended

Galois Field elements ordered into the sequence of the successive powers of a primitive element a are given in the following table 1.

table 1.

<td> Field</td><td> Decimal</td><td> Position</td><td> Basic Permutation</td><td> Permuted</td>

<td> elements</td><td> value</td><td></td><td> (of position)</td><td> Decimal</td>

<td></td><td></td><td></td><td></td><td> Values</td>

WO 98/33290

PCT/SE97/02183

<td> [o 0 1]= a⁰</td><td> 1</td><td> 1</td><td> 8</td><td> 0</td>

<td> [o 1 o]= a¹</td><td> 2</td><td> 2</td><td> 1</td><td> 1</td>

<td> [1 0 o]= a²</td><td> 4</td><td> 3</td><td> 2</td><td> 2</td>

<td> [0 1 1]= a³</td><td> 3</td><td> 4</td><td> 4</td><td> 3</td>

<td> [1 1 o]= a⁴</td><td> 6</td><td> 5</td><td> 3</td><td> 4</td>

<td> [1 1 1]= a⁵</td><td> 7</td><td> 6</td><td> 7</td><td> 5</td>

<td> [1 0 1]= a⁶</td><td> 5</td><td> 7</td><td> 5</td><td> 6</td>

<td> [o o o]</td><td> 0</td><td> 8</td><td> 6</td><td> 7</td>

The basic column permutation which maps M-transform matrix into the matrix whose rows are different Walsh functions is obtained by reordering the sequence of Galois field elements so that their decimal values are linearly ranging from 0 to 7.

Reordering the positions of columns of matrix M according to the basic permutation ρ=[β 1 2 4 3 7 5 6] produces the new matrix given in table 2. The rows of this matrix are Walsh functions, so by suitable permutation of rows this matrix can be transformed onto Sylvester-type Hadamard matrix. The Sylvester10 type Hadamard matrix H of order 8 is given in table 3. The rows of H are Walsh sequences designated as WO to W7.

table 2.

<td> Permuted Matrix M</td><td> Walsh Function</td>

WO 98/33290

PCT/SE97/02183

<td> 00000000</td><td> =wo</td>

<td> 01101001</td><td> =W7</td>

<td> 01100110</td><td> =W3</td>

<td> 01010101</td><td> =W1</td>

<td> 00001111</td><td> =W4</td>

<td> 00110011</td><td> =W2</td>

<td> 01011010</td><td> =W5</td>

<td> 00111100</td><td> =W6</td>

table 3.

<td> Sylvester-type Hadamard Matrix</td><td> Walsh Function</td>

<td> 0 0 0 0 0 0 0 0</td><td> =W0</td>

<td> 01010101</td><td> =W1</td>

<td> 00110011</td><td> =W2</td>

<td> 01100110</td><td> =W3</td>

<td> 00001111</td><td> =W4</td>

<td> 01011010</td><td> =W5</td>

<td> 00111100</td><td> =W6</td>

WO 98/33290

PCT/SE97/02183

<td> 01101001</td><td> =W7</td>

Besides the basic permutation, there are many other permutations which will produce the same set of Walsh functions. They can be obtained by applying the same principle from the previous example to the transformed matrix of GF(2ⁿ) elements, obtained by any combination of the following operations: columns permutation of field elements, and cyclic shift of 1, a, a², . . . , aⁿ² sequence. The total number of permutations which can be obtained in this way, for the Orthogonal Gold sequences of length N=2ⁿ, is M = n! x (N - 1) .

However, the total number of permutations is even larger, what can be seen if the transformed matrix of GF(2ⁿ) elements is defined most generally. Namely, the rotation of any column corresponding to the nonzero GF(2ⁿ) elements in the field elements matrix, that produces all different decimal values, will result in a additional permutation for matrix M . In that way, for example, it can be obtained 168 permutations for n=3, which is 4 times larger than 3! x (θ - 1) . For n=4 , it can be found 56 x 4’ x (16 - 1) permutations .

The following example illustrates permutation construction using transformed matrix of Galois Field elements. If the first and second column of the field elements in table 1 have exchanged the position, another permutation can be obtained as shown in table 4.

table 4.

<td> Field</td><td> Decimal</td><td> Position</td><td> Basic Permutation</td><td> Permuted</td>

WO 98/33290

PCT/SE97/02183

<td> elements</td><td> value</td><td></td><td> (of position)</td><td> Decimal Values</td>

<td> [o 0 1]= a⁰</td><td> 1</td><td> 1</td><td> 8</td><td> 0</td>

<td> [1 0 o]= a²</td><td> 4</td><td> 2</td><td> 1</td><td> 1</td>

<td> [o 1 o]= a¹</td><td> 2</td><td> 3</td><td> 3</td><td> 2</td>

<td> [1 0 1]= a⁶</td><td> 5</td><td> 4</td><td> 7</td><td> 3</td>

<td> [1 1 o]= a⁴</td><td> 6</td><td> 5</td><td> 2</td><td> 4</td>

<td> [1 1 1]= a⁵</td><td> 7</td><td> 6</td><td> 4</td><td> 5</td>

<td> [o 1 1]= a³</td><td> 3</td><td> 7</td><td> 5</td><td> 6</td>

<td> [o o o]</td><td> 0</td><td> 8</td><td> 6</td><td> 7</td>

The permutation when applied to the matrix M will produce another matrix containing the set of Walsh functions, as shown in table 5.

table 5.

<td> Permuted Matrix M</td><td> Walsh Function</td>

<td> 00000000</td><td> =W0</td>

<td> 01101001</td><td> =W7</td>

<td> 01011010</td><td> =W5</td>

WO 98/33290

PCT/SE97/02183

<td> 01010101</td><td> =W1</td>

<td> 00110011</td><td> =W2</td>

<td> 00001111</td><td> =W4</td>

<td> 01100110</td><td> =W3</td>

<td> 00111100</td><td> =W6</td>

Figure 6 illustrates an embodiment of an inventive arrangement of the efficient bank of correlators 600 used in a receiver in a multicode CDMA system. A first register 602 converts serially received, on an input 601, input samples SS - s₀, s_x, . . ., s_N.! to parallel. N serially received input samples SS are output on N parallel output 0,,,...,0^ to a multiplier 603. The arbitrary sequence a = a₀,a_x, . . .,a_N__x is stored in a memory 605 which has connections to the multiplier 603. Each element a₀,a_x, . . . , a_N._x is output on a corresponding connection c₀, . . . , ο_Ν._χand multiplied in the multiplier 603 with a corresponding input sample s₀, s_x, . . ., s_N._x, therewith the product p = p₀,p_lf . . . ,p_N._x = s₀*a₀, s₁*a₁, . . . , s_N.₁*a_N_₁ is obtained. Output u = u^u-^ . . . ,u_N._x of the multiplier are connected to a second register 604 in which the permutation is performed. The obtained permuted version of the product p is the sequence w , which is equal to the sum of a number of sequences of the so-called Walsh sequences. The elements w₀,w_x, . . .,w_N._x of the sequence w are, via a corresponding connection v₀,v_x, . . .,v_N__lz connected to a bank of Walsh correlators 606, implemented as Fast Hadamard Transformer,

WO 98/33290

PCT/SE97/02183 which generates on output k₀, k_lz . . . , k_N._x the correlation values CV₀, . . . /CVjj.j corresponding to each Walsh sequence w_0/w₁, . . . , w^.

Figure 7 illustrates another embodiment of the inventive arrangement 700. A first register 702 converts serially, received, on an input 701, input samples SS = s₀, s_1# . . . , s_N.i to parallel. The register 702 is also arranged so that N serially received input samples SS are permuted and output on N parallel output Οο,.,.,Ον.χ to a multiplier 703. The permuted arbitrary sequence a_p = ^aPo»^aPi/· · · /^a_PN-i is stored in a memory 605 which for each N elements has a connection c₀,...,c_N.·,^ to the multiplier 703. Each element a_p0,a_pl, . . .,a^.j is output on the corresponding connection 0,,,...,0^ and multiplied in the multiplier 703 with a corresponding input sample s_p0, s_pl, . . ., s_pN.

therewith the products s_p0*a_p0, s_pl*a_pl, . . . , s_pN.₁*a_pN.₁ are obtained, which form a sequence, which is the sum of a number of sequences, from the set of Walsh sequences. Outputs u₀,u_lz . . . ,u_N. _x of the multiplier 703 are connected to a bank of Walsh correlators 704, implemented as Fast Hadamard Transformer. The bank of Walsh correlators 704 comprises a buffer for buffering said products s_pO*^aPo, ^sPi*^aPi, · · · , ^sPN-i*^a_PN-i before the Fast Hadamard Transformation is performed on said products. For the sequence s_p0*a_p0, s_pl*a_pl, . . . , s_pN.₁*a_pN.₁ the bank of Walsh correlators 704 generates N correlation values CV₀, . . . , CV^ corresponding to each of N Walsh sequences.

The mentioned Fast Hadamard Transform, which is known by a person skilled in the art, is a method to increase the efficiency of Hadamard transform. The Hadamard transform is characterised by a Hadamard matrix, in which each row of the Hadamard matrix is orthogonal to every other row of the matrix.

WO 98/33290

PCT/SE97/02183

Each row of the Hadamard matrix can be referred to as a Walsh sequence.

A Hadamard matrix of order n can be defined recursively as follows:

Han

Hn

Hn

Hn

-Hn

The Fast Hadamard transform exploit the fact that Hadamard matrices are real, symmetric and row-wise orthogonal. Since the Hadamard matrices contain only ±1 values, no multiplications are required in the transform calculation. Moreover the number of additions and subtractions required can be reduced from n² to n x log2 n, due to the fact that a Hadamard matrix of order n (H_n) can be written as a product of n sparse matrices, that is,

Hn r-logi (n) Hn . where

<td> '1</td><td> 1</td><td> 0</td><td> 0 . .</td><td></td>

<td> 0</td><td> 0</td><td> 1</td><td> 1 . .</td><td></td>

<td> 0</td><td> 0</td><td></td><td></td><td> ..1 1</td>

<td> 1</td><td> -1</td><td> 0</td><td> 0 . .</td><td></td>

<td> 0</td><td> 0</td><td> 1</td><td> -1 . .</td><td></td>

<td></td><td></td><td></td><td></td><td> - . 1 -1</td>

Noting that the top n/2 rows and the bottom n/2 rows contain only two nonzero terms per row, the transformation g£°9²⁽ⁿ⁾ X u = Hn X Hn. . . Hn X u can be accomplished by operating

WO 98/33290

PCT/SE97/O2183

Hn x log2 n times on u, where u is a column vector of the input sample.

Due to the structure of Hn only n additions or subtractions are required each time Hn operates on a vector, giving a total of n x login additions and subtractions.

The inventive method and arrangement described in conjunction with the figures require 2 x N + N x log2 N operations when despreading N samples. It is assumed that multiplication as well as permutation are performed in N operations.

The mapping between the ordinal numbers of despreader outputs and ordinal numbers of code channels requires in principle an additional permutation of Fast Hadamard Transform outputs. However, the amount of corresponding additional processing power depends of the actual implementation. For example, if despread code channels are further processed in parallel, the hard-wired connection between despreader outputs and the rest of the receiver can be permuted, so no additional processing power is required.

As an example, if N=64, then 512 (0(64)=512) operations are required. Compared with 4 096 (64 x 64) operations required by a straightforward implementation, 8 times reduction of the complexity is obtained.

The earlier described inventive method and arrangement do not have to operate in parallel. They can of course operate serially but they are then less efficient.

The embodiments described above serve merely as illustration and not as limitation. It will be apparent to one ordinary skill in

WO 98/33290 2 2 PCT/SE97/02183 the art that departures may be made from the embodiments described above without departing from the spirit and scope of the invention. Therefore, the invention should not be regarded as being limited to the examples described, but should instead 5 be regarded as being equal in scope to the following claims.