WO2003013037A1

WO2003013037A1 - Code generation

Info

Publication number: WO2003013037A1
Application number: PCT/GB2002/003580
Authority: WO
Inventors: Jonathan Lucas
Original assignee: Ubinetics Limited
Priority date: 2001-08-02
Filing date: 2002-08-02
Publication date: 2003-02-13
Also published as: GB2378362A; EP1415422A1; GB0118899D0; CN1555623A

Abstract

An OVSF code is generated using a parity generator (18) operating on the output of a masked counter (12), the counter and the mask word having opposing bit significance conventions. As the counter (12) advances, the parity generator spells out the OVSF code. The overlap of the counter and the mask can be adjusted to cause the generation of other OVSF codes. By giving the mask word and the counter the same bit significance conventions, Hadamard codes can be generated (Figure 4).

Description

CODE GENERATION

The invention relates to the generation of spreading codes and to the use of spreading codes in communications techniques. A spreading code is a code that is capable of being used to spread another signal in CDMA (code division multiple access) communications. In certain embodiments, the invention deals with Orthogonal Variable Spreading Factor (OVSF) codes and Hadamard codes, both of which can be used for spreading signals.

h 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 ONSF 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 C_n,_x may be described as the x^th (where x is numbered from 0) row of the OVSF matrix C_n. C_n is described recursively below:

Ci = [0]

00 c₂ 0 1

0000

00 1 1 c₄

0 1 01

0 1 1 0

00000000

00001 1 1 1

001 1001 1 c₈ = 001 1 1 100

010101 01

0101 101 0

01 1001 10

01 101001

C n+1 = C₂«+l 3 ,n>0

C₂n+12"+!-!

(Note that C₂, C₄, and C₈ are shown for information. Technically, only the definition for d is required along with the recursive definition of C₂»+ι ). 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 C_n>x, the whole matrix C_n is generated, and then the X^th row is taken from this matrix to provide the code. This implies that Ci to C_n-i need to be generated along the way.

For example, to generate C512.1 , one starts with the matrix Ci. From that, one generates C₂, then C , Cs, C₁₆, C₃₂, C₆ , Cι₂₈, C₂₅₆ and finally C512. The desired code (C512.1) is the 2^nd 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 H_n,_x may be described as the x^th row (where x is numbered from 0) of the Hadamard matrix H_n. H_n is described recursively below:

Ho = [0]

0 0 Hι = 0 1

(Note that Hi, Η₂, and H₃ are shown for information. Technically, only the definition for H₀ is required along with the recursive definition of H_n+ι.)

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 H_n,_x, the whole matrix H_n is generated, and then the X^th row is taken from this matrix to provide the code. This implies that H₂to Hn-i need to be generated along the way. For example, to generate Hg,2, one starts with the matrix H₀. From that, one generates Hi_, then H₂. H3. H₄ .H5, H₆, H₇ and finally H₈. The desired code (H_8>2) is the 3^rd 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 C₂» 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 C_n>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 C„,_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 log₂(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 C₈,5 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=2³) as follows:

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 C_n,_x. If the longest OVSF code required belongs to matrix C_q, then the counter must be capable of counting through at least q values, i.e. the counter must have at least log₂(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 C_s,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 C₈,3, n=8, x=3, and log2(n)=3.

As can be seen, the parity generator 28 is generating a continuous stream which is C ^•8,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 nonnal 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.

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 C_n>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_n>x. If the longest OVSF code required belongs to matrix C_q, 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 log₂(q) bits long.

For example, let us say we are trying to generate C₈,3, 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 C₈,3 where n=8, x=3, and log₂(n)=3.

The output of the parity generator 28 is C₈,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.

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 H„_,x. 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 H_n,_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 2ⁿ successive cycles, the parity bits spell out H_n,x. If the longest Hadamard codes required belong to Hadamard matrix H_p, then the counter 12 must be capable of counting through at least 2^P 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 H_3>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.

As can be seen, the parity generator 18 is generating a continuous stream which is H_3j3 repeated over and over.

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

Claims

1. 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.

2. Apparatus according to claim 1, wherein the masking means is arranged to overlap a selectable number n of the least significant bits of the co-ordinate words for the masking operation so that the spreading code being generated belongs to OVSF matrix

C₂".

3. Apparatus according to claim 1 or 2, wherein the apparatus has an additional mode of operation in which the masking means performs the masking operation with the co-ordinate words having the same bit significance convention such that the spreading code is a Hadamard code.

4. Apparatus according to claim 1, 2 or 3, wherein the second co-ordinate word identifies the position of the spreading code containing the specified bit within a matrix containing the spreading code and the second co-ordinate word is bit-reversed to achieve the opposing bit significance conventions.

5. Apparatus according to claim 1, 2 or 3, further comprising reversing means for bit-reversing the first co-ordinate word to achieve the opposing bit significance conventions.

6. Apparatus according to claim 1, 2 or 3, further comprising a reverse carry adder for producing the first co-ordinate word in order to achieve the opposing bit significance conventions.

7. Apparatus according to any preceding claim, further comprising counter means issuing a counter value, wherein the first co-ordinate word is the counter value and the counter value is advanced to cause the parity generating means to issue the spreading code.

8. Apparatus according to claim 7 when dependent on claim 3, wherein m successive parity values in the additional mode are designated to form the spreading code so that the code is a Hadamard code from Hadamard matrix H_m.

9. Apparatus according to claim 8, wherein m is adjustable to select the Hadamard code issued by the parity generating means.

10. Apparatus according to any preceding claim, wherein the second co-ordinate word is adjustable to control which spreading code provides the specified bit.

11. Apparatus according to any preceding claim, wherein the first co-ordinate word is adjustable to control which bit of the spreading code is provided by the parity generating means.

12. Apparatus for manipulating a communications signal, comprising the apparatus of any preceding claim for producing spreading code bits, and means for applying the spreading code bits to the communications signal.

13. 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.

14. A method according to claim 13, wherein there is an overlap of a selectable number n of the least significant bits of the co-ordinate words for the masking operation and the method further comprises selecting n to determine that the spreading code arises from OVSF matrix C₂».

15. A method according to claim 13 or 14, wherein the second co-ordinate word identifies the position of the spreading code containing the specified bit within a matrix containing the spreading code and the second co-ordinate word is bit-reversed to obtain the opposing bit significance conventions.

16. A method according to any one of claim 13, 14 or 15, wherein the first co-ordinate value is a counter value and the counter value is advanced to cause successive parity determinations to form a spreading code.

17. A method according to any one of claims 13 to 16, wherein the second co-ordinate word is adjustable to control which spreading code provides the specified bit.

18. A method according to any one of claims 13 to 17, wherein the first co-ordinate word is adjustable to control which bit of the spreading code is provided by the parity determination.

19. A method of manipulating a signal, comprising at least one of spreading and despreading the signal with spreading code bits generated by the method of any one of claims 13 to 18.

20. A program for carrying out the method of any one of claims 13 to 19.