In a conventional FDMA (frequency division multiple access) scheme, different channels are transmitted on different frequency bands. In a TDMA (time division multiple access) scheme, different channels are transmitted in different timeslots in an agreed timeslot pattern.

A central part of any CDMA (code division multiple access) system is the use of spreading codes. In such a system, a continuous transmission on a single frequency contains multiple concurrent channels. Each symbol in each channel is modulated with a high speed 'spreading code'. The mathematical properties of these codes are such that it is possible to transmit many different symbol streams (or channels) with different spreading codes simultaneously in the same radio frequency band and still be able to successfully receive and separate these channels if the spreading code is known.

In IS-95 (currently the most widely used commercial CDMA system), these codes are known as Walsh Codes. Walsh Codes are all the same length (64 elements), and so are 'fixed spreading factor codes'.

In UMTS, the type of code used is slightly different-these are of variable length, and have very desirable properties in that careful allocation of these codes allows a system to transmit multiple channels of different speeds on the same frequency band without co-interference. Specifically, any length of a power of 2 is supported as a valid length.

These codes are called Orthogonal Variable Spreading Factor (OVSF) codes. The definition of these OVSF codes is given in the UMTS specification and is repeated below for information. This definition can easily be implemented in software, but requires significant amounts of memory and processing power to run, as it involves possibly large (up to 512x512 element) matrix calculations.

OVSF code Cn, x may be described as the xth (where x is numbered from 0) row of the OVSF matrix Cn. Cn is described recursively below: (Note that C2, C4, and C8 are shown for information. Technically, only the definition for Ci is required along with the recursive definition of C2n+1). For a given OVSF matrix, a spreading code bit can be specified by a pair of co-ordinates, one identifying the code which provides the bit (i. e. x) and the other identifying the position of the specified bit within its code.

The algorithm above requires that, for any given code Cn, x, the whole matrix Cn is generated, and then the x'row is taken from this matrix to provide the code. This implies that Cl to Con l need to be generated along the way.

For example, to generate 512, 1, one starts with the matrix Cl. From that, one generates 2, then C4, C8, C16, C32, C64, C128, C256 and finally 512. The desired code (Cs, l) is the 2nd row of this matrix (the rows are numbered from 0 to n-1).

As can be seen, this is a computationally intensive operation. In addition, a large amount of memory is required to store all the intermediate matrices required to get to the desired OVSF code.

Once generated, any OVSF codes required are passed to a hardware block where they are stored and used to provide the real spreading signals used to generate the full rate sequence to be transmitted on the air.

In UMTS, a synchronisation channel is broadcast by a base station in order to provide timing, frequency and identification information for a mobile station (MS) to easily detect and decode. It consists of two separate channels, code multiplexed together. The primary synchronisation channel (PSCH) is used to provide slot timing and phase information for automatic frequency correction. The secondary synchronisation channel (SSCH) is orthogonal to (i. e. it does not interfere with) the PSCH and gives frame timing and cell identification information.

Although Hadamard codes are capable of being used for spreading other signals, in UMTS Hadamard codes are used in the SSCH to provide the cell identification information mentioned in the preceding paragraph. The definition of these codes is given in the UMTS specifications, and is repeated below for information. This definition can easily be implemented in software, but requires significant amounts of memory and processing power to run, as it involves possibly large (up to 256x256 element) matrix calculations.

Hadamard code Hn, x may be described as the xt"row (where x is numbered from 0) of the Hadamard matrix Hn. Hn is described recursively below: (Note that H1, H2, and H3 are shown for information. Technically, only the definition for Ho is required along with the recursive definition of Hn+l) For a given Hadamard matrix, a spreading code bit can be specified by a pair of co-ordinates, one identifying the code which provides the bit (i. e. x) and the other identifying the position of the specified bit within its code.

The algorithm above requires that, for any given code Hn,x, the whole matrix Hn is generated, and then the xtl'row is taken from this matrix to provide the code. This implies that H2 to Hn l need to be generated along the way.

For example, to generate Hs, 2, one starts with the matrix Ho. From that, one generates Hi, then H2, H3, H4, Hs, H6, H7 and finally H8. The desired code (H8, 2) is the 3rd row of this matrix (the rows are numbered from 0 to n-1).

As can be seen, this is a computationally intensive operation. In addition, a large amount of memory is required to store all the intermediate matrices required to get to the desired Hadamard code.

Once generated, any Hadamard codes required are passed to a hardware block where they are stored and used to provide the real spreading signals used to generate the full rate sequence to be transmitted on the air, or against which an input sequence should be correlated.

The invention seeks to provide an improved technique for spreading code bit generation.

According to one aspect, the invention provides apparatus for spreading code bit generation, comprising masking means arranged to mask a first co-ordinate word with a second co-ordinate word having the opposite bit significance convention to the first co-ordinate word, the first and second co-ordinate words specifying a bit of a spreading code, and parity generating means for determining the parity of the masked first co-ordinate word to obtain the specified bit.

The invention also consists in a method of spreading code bit generation, comprising providing two co-ordinate words specifying a bit of a spreading code and having opposing bit significance conventions, masking a first one of the co-ordinate words with the second and determining the parity of the masked first co-ordinate word to obtain the specified bit.

By generating spreading code bits in this fashion, it is not necessary to perform the intermediate step of generating one or more spreading code matrices from which the spreading code bits are taken. This may provide savings in terms of memory space, processing time and power consumption. In one embodiment, the second co-ordinate word identifies the position of the spreading code containing the specified bit within the matrix containing the code and the first co-ordinate word identifies the position of the specified bit within the code.

Advantageously, the second co-ordinate word is bit reversed since the bit reversed value does not need to be updated during the issue of the code.

In one embodiment, the co-ordinate words are overlapped by a selectable number n of their least significant bits for the masking process and advantageously n can be selected to determine in a simple manner the OVSF matrix C2 » providing the code.

In one embodiment, there is an additional mode of operation in which the masking operation is carried out with the co-ordinate words having the same bit significance convention so that the generated bit belongs to a Hadamard code.

According to a second aspect, the invention provides apparatus for spreading code bit generation, comprising masking means for masking a first co-ordinate word with a second co-ordinate word, the first and second co-ordinate words specifying a bit of a spreading code, and parity generating means for determining the parity of the masked first co-ordinate word to obtain the specified bit.

The invention also consists in a method of spreading code bit generation, comprising providing two co-ordinate words specifying a bit of a spreading code, masking a first one of the co-ordinate words with the second and determining the parity of the masked first co-ordinate word to obtain the specified bit.

By generating spreading code bits in this fashion, it is not necessary to perform the intermediate step of generating one or more spreading code matrices from which the spreading code bits are taken. This may provide savings in terms of memory space, processing time and power consumption.

The invention also extends to methods and apparatus for manipulating a signal, involving at least one of spreading and despreading the signal with spreading code bits generated by a method or apparatus according to the invention.

The invention can also be implemented as a computer program which, if necessary, can be provided on a data carrier.

By way of example only, some embodiments of the invention will now be described with reference to the accompanying figures, in which: Figures 1 to 3 each show a block diagram of a OVSF code generator; and Figure 4 is a block diagram of an OVSF code generator in a Hadamard code generating mode.

Figure 1 shows a block diagram of a code generator 20 for generation of an OVSF code Cn, X. The code generator 20 comprises a binary counter 22 and a mask register 24, both of which provide inputs to a masking unit 26. The output of the masking unit 26 is supplied to a parity generator 28. For each increment of the counter 22, the parity generator 28 outputs one OVSF code bit.

To generate OVSF code Cn, x, the mask register 24 is loaded with x written in the opposite endianism (bit significance convention) to the counter value. With respect to the endianism of the counter, register 24 is effectively loaded with a bit reversed version of x.

For example, the decimal number 3 is the 4 bit binary number 0011 in the bit significance convention where the rightmost bit is the least significant bit and the leftmost bit is the most significant bit, whereas decimal 3 is 1100 in the opposite bit significance convention.

The masking unit 26 receives the value x from the mask register 24 and the counter value from counter 22. It will be recalled that these values have opposite bit significance conventions and the masking unit 26 needs to align these values before performing the masking operation. The masking unit 26 aligns these values so that their log2 (n) (always an integer value because n is always a power of 2) least significant bits overlap. The masking is then performed by doing a bitwise AND on the aligned values. The following example illustrates the operation of the masking unit where Cs, s is being generated and the counter value is presently 7.

In the convention where the leftmost bit is the least significant, 7 as a 4 bit word is 1110.

In the convention where the rightmost bit is the least significant, 5 as a 4 bit word is 0101.

The masking unit 26 aligns the 3 least significant bits of these words (since n=8=23) as follows: 1110 1 1 1 1 0 1 Performing the bitwise AND operation on the aligned values yields the word 101.

Thus, for each value of the counter 22, the parity generator 28 receives a word from the masking unit 26. For each word that it receives, the parity generator 28 outputs a single bit which indicates the parity of the word received from the masking unit 26. It will be seen that, over each group of n successive cycles, the parity bits spell out Cnx. If the longest OVSF code required belongs to matrix, then the counter must be capable of counting through at least q values, i. e. the counter must have at least log2 (q) bits. Typically, the counter runs continuously and generates the bits of the OVSF code at the rate required to provide a constant stream of data to the modulation or demodulation system of a CDMA transceiver.

For example, let us say we are trying to generate C8 3. From the OVSF matrices above, we know that this sequence is 0,0, 1,1, 1, 1, 0,0. The table below shows how the various blocks in the generator 20 behave for the first few steps of the counter. Note that for C8 3, n=8, x=3, and log2 (n) =3. Log2 (n) Log2 (n) Output of #ls Output of Parity Lowest Bits of Lowest Bits of Masking Unit 26 Generator 28 Counter 22 (x) 000 110 0000 0 0 001 110 0000 0 0 010 110 0010 1 1 Oil 110 0010 1 1 100 110 0100 1 1 101 110 0101 1 1 110 110 0100 2 0 100 110 0110 2 0 000 110 0000 0 0 001 110 0000 0 0 010 110 0010 1 1 Oil 110 solo il 100 110 0100 1 1 101 110 0100 1 1 110 110 0100 2 0 111 110 0110 2 0 As can be seen, the parity generator 28 is generating a continuous stream which is C8,3 repeated over and over.

Figure 2 shows a block diagram of a modified OVSF code generator 30. The generator 30 is similar to generator 20 in that it also comprises a mask register 24, a masking unit 26 and a parity generator 28. However, in Figure 2, the counter 22 of Figure 1 has been replaced by a reverse carry adder 32 and a further register 34. In this embodiment, the mask register 24 contains the binary version of x written such that its rightmost bit is the least significant and the reverse carry adder 32 and register 34 are used to create what is essentially a counter having the opposite bit significance convention. Register 34 is loaded with a binary version of decimal 1 written in the opposite endianism to x. For example, where n is 64, register 34 is loaded with the value 100000.

The reverse carry adder is a common hardware block often used in implementations of fast Fourier transforms (FFTs). It operates in the same way as a normal binary adder, except that the carry bit of the add moves in the opposite way to a conventional adder. The table below gives some examples. X Y X+Y (reverse carry) 1000 1000 0100 1000 1100 0010 0001 0001 0000 In generator 30, the inputs to the reverse carry adder are its output (which is fed back) and the content of register 34.

The outputs of the reverse carry adder 32 and the mask register 24 are used by the masking unit 26 and the parity generator 28 to produce the OVSF code Cn, x in the same manner as in generator 20. It will be seen that, over each group of n successive cycles, the parity bits spell out C", X. If the longest OVSF code required belongs to matrix, then the adder must be capable of counting through at least q values, i. e. the adder must be capable of outputting a result at least log2 (q) bits long.

For example, let us say we are trying to generate C83, which is (0,0, 1,1, 1,1, 0,0). The table below shows how the various blocks in the generator 30 behave for the first few steps of the counter for C83 where n=8, x=3, and log2 (n) =3. Content of Log2 (n) Log2 (n) Output of # of 1s Output of Parity Register 34 lowest bits of lowest bits of Masking Unit Generator 28 Output of x 26 Adder 32 100 000 Oil 000 0 0 100 100 Oil 000 0 0 100 010 011 010 1 1 100 110 011 010 1 1 100 001 Oil 001 1 1 100 101 011 001 1 1 100 Oil Oil Oil 2 0 100 111 Oil Oil 2 0 100 000 011 000 0 0 100 100 011 000 0 0 100 010 011 010 1 1 100 110 011 010 1 1 100 001 011 001 1 1 100 101 011 001 1 1 100 Oil Oil Oil 2 0 100 111 Oil Oil 2 0 The output of the parity generator 28 is C8, 3- Figure 3 shows a block diagram of another OVSF code generator 40. The generator 40 is similar to generators 20 and 30 in that it also comprises a mask register 24, a masking unit 26 and a parity generator 28. The code generator 40 also comprises a counter 44, whose output has the same bit significance convention as the value in the mask register.

However, a bit reverser operates on the output of the counter 44 to give the counter value the opposite bit significance convention to that of the mask register. The output of the bit reverser is used to provide an input to the masking unit 26. The following table illustrates the operation of the counter 44 and the bit reverser 42 for 4 bit words. Counter 44 Output of Bit Reverser 42 0000 0000 0001 1000 0010 0100 0011 1100 0100 0010 0101 1010 0110 0110 0111 1110 1000 0001 1001 1001 1010 0101 1011 1101 1100 0011 It will be apparent from the table above, the output from bit reverser 32 is the same as the output of the reverse carry adder 32 in Figure 2. Given that the mask register 24, masking unit 26 and parity generator 28 in Figure 3 operate analogously to their counterparts in code generator 30, it will be readily understood by the skilled person how the generator 40 produces OVSF codes.

An OVSF code generator as described in Figure 1, 2 or 3 can be provided with a second mode of operation in which Hadamard codes can be generated by performing the masking operation with the inputs to the masking unit being given the same bit significance convention. In the embodiment of Figure 1, the concordance of the bit significance conventions could be achieved by re-loading the mask register 24 with a version of x that is not bit-reversed relative to the counter 22. In the embodiment of Figure 2, the concordance could be achieved by providing a bit-reverser at point BR. In the embodiment of Figure 3, the concordance could be achieved by providing that the bit-reverser 42 is disabled in the Hadamard code generation mode.

The operation of the Figure 1, 2 and 3 embodiments in the Hadamard code generation mode effectively produces a system operating like the scheme shown in Figure 4.

Figure 4 shows a block diagram of a code generator 10 for generation of a Hadamard code Hnx. The code generator 10 comprises a binary counter 12 and a mask register 14, both of which provide inputs to a masking unit 16. The output of the masking unit 16 is supplied to a parity generator 18. For each increment of the counter 12, the parity generator 18 outputs one Hadamard code bit. The counter 12 wraps back to the start of the code automatically.

To generate Hadamard code Hn, x, the mask register 14 is loaded with the value x and the masking unit 16 performs a bitwise AND operation on the output of the counter 12 and the value x from register 14. Thus, for each value of the counter 12, the parity generator 18 receives a word from the masking unit 16. For each word that it receives, the parity generator 18 outputs a single bit which indicates the parity of the word received from the masking unit 16. Over each group of 2n successive cycles, the parity bits spell out Hnx. If the longest Hadamard codes required belong to Hadamard matrix Hp, then the counter 12 must be capable of counting through at least 2P values before wrapping, i. e. the counter 14 must have at least p bits. Typically, the counter runs continuously and generates the bits of the Hadamard code at the rate required to provide a constant stream of data to the modulation or demodulation system of a CDMA transceiver.

For example, let us say we are trying to generate Ho. 3. From the Hadamard matrices above, we know that this sequence is 0,1, 1,0, 0,1, 1, 0. The table below shows how the various blocks in the generator 10 behave for the first few steps of the counter for n=3, x=3. Counter 12 x Output of Masking # is Output Parity of Unit 16 Generator 18 0000 Oil 000 0 0 0001 Oil 001 1 1 0010 Oil 010 1 1 0011 Oil Oil 2 0 0100 Oil 000 0 0 0101 Oil 001 1 1 0110 011 010 1 1 0111 Oil Oil 2 0 1000 Oil 000 0 0 1001 011 001 1 1 1010 011 010 1 1 1011 Oil Oil 2 0 1100 011 000 0 0 110 011 001 1 1 1110 011 010 1 1 1111 Oil Oil 2 0 As can be seen, the parity generator 18 is generating a continuous stream which is H3,3 repeated over and over.

Although Hadamard codes can be used as spreading codes, in UMTS they are typically used as identifier tags in signals.