WO2001050659A1

WO2001050659A1 - Method and device for orthogonal variable spreading factor codes and hadamard matrices generation

Info

Publication number: WO2001050659A1
Application number: PCT/IT2000/000530
Authority: WO
Inventors: Fulvio Piccinonno
Original assignee: Telit Mobile Terminals S.P.A.
Priority date: 1999-12-30
Filing date: 2000-12-19
Publication date: 2001-07-12
Also published as: ITMI992747A1; ITMI992747A0; IT1314346B1; AU2395701A

Abstract

A method for the generation of variable length orthogonal spreading sequences with maximal length 2k and spreading factor SF or rows of Hadamard matrices of dimension SF, marked by an index n' of k=log¿2?SF bits. In the method the final sequence or row is generated starting from a predefined initial value and repeating partial sub-sequences, as they are or changed in sign depending on the value, 0 or 1 respectively, of each bit of the binary representation of n'. An apparatus for the generation according to the method is composed by an index shift-register (10) in which the index n' is loaded and a sequence shift-register (11) in which the final sequence or row is composed. A transfer circuit (13) takes the partial sequence stored in the sequence shift register (11) inverts it or not depending on the output of the index shift-register and uploads the result in the sequence shift-register appending it to the partial sequence generated up to now. The circuit repeats the loading, eventually the inversion and the storing for each bit of the index in the index shift-register, shifting of one position each time the index shift-register until all the bits of n' have been used.

Description

Method and device for Orthogonal Variable Spreading Factor codes and Hadamard matrices generation.

The present invention relates to an innovative generator for orthogonal variable spreading factor (OVSF) codes or rows of Hadamard matrices for communication systems. The invention relates to an apparatus that apply the method too. In the spectrum division communication systems, like CDMA systems used in cellular telecommunications, the communications between base stations and mobile stations are established using the so-called "spreading codes". Substantially, the base station assigns a given number of channels to each mobile station. The distinction between the channels is given by a spreading code, which identify the specific channel. It is known to be necessary to use orthogonal variable spreading factor codes to improve the efficiency of the bandwidth usage. Since different services require different spreading factors, it is necessary to generate orthogonal variable spreading factor sequences in the physical channels. Since the code generators must be in the mobile stations too, it is important to have simple and not encumbering generators. The objective of the present invention is to give a method and an apparatus that uses the method for a simple and reliable generation of orthogonal variable spreading factor codes or rows of Hadamard matrices.

With this objective in mind, we have thought to realise, as described in the invention, an orthogonal variable spreading factor sequences generator with maximal length 2^k and spreading factor SF, or a generator for rows of Hadamard matrices of dimension SF, marked by an index n' of k=log₂SF bits. In the method the final sequence or row is generated starting from a predefined initial value and repeating partial sub-sequences, as they are or changed in sign depending on the value, 0 or 1 respectively, of each bit of the binary representation of n'.

An apparatus for the generation according to the method has been realised. It is composed by an index shift-register in which the index n' is loaded and a sequence shift-register in which the final sequence or row is composed; a transfer circuit that takes the partial sequence stored in the sequence shift register and invert it or not depending on the output of the index shift-register and upload the result in the sequence shift-register appending it to the partial sequence generated up to now. The circuit repeats the loading, eventually the inversion and the storing for each bit of the index in the index shift-register, shifting of one position each time the index shift- register until all the bits of n' have been used. To make clear the innovations in this invention and the advantages on the prior art, in the following will be described, with the help of the enclosed pictures, a possible implementation of these principles.

• Figure 1 represents the initial part of a spreading sequence generator tree;

• Figure 2 represents a flowchart that describes the method; • Figure 3 represents a block scheme of a generator circuit that applies the method of the invention.

In figure 1 a generator tree is shown. At each level of the tree there are as much codes or branches as the spreading factor SF associated to the level. To each code an index equal to the spreading factor is associated, and in each level the codes are numbered from 1 to SF. Sometimes they could be numbered from 0 to SF-1. For example, at the level SF=2 there are two branches, the first with the code indicated as c₂ , , the second with a code indicated with c_{2 2}. The code definition is the following:

9_Λ = (1)

* SF,2k-l ~ V^C SF , ' ^CSF ,

— ,k — ,k

2 2

• SF,2k ~ ^CSF_ . ^{, C} F_ )

2 ^' 2 ^'

The codes, except a different enumeration, correspond to the rows of an Hadamard matrix.

The code index is transformed decrementing of one the value n of the code, so that it will assume values in the range 0..SF-1 (this step is not necessary if the codes are numbered starting from 0), and it will be binary represented using log SF bits. The result of the transformation is denoted with n'.

For example, the transformation of the index of the sixth code with spreading factor 16, denoted with c_{16 6} , will be 0101, since decrementing the code number we obtain the value 5, whose binary representation is 101, which has to be expressed with log₂16=4 bits. Obviously if the codes are numbered from 0 to SF-1 it is not necessary to initially decrement the cod.ϊ number.

If we want to generate a row of an Hadamard matrix of dimension SF, it is enough to number the rows from top to bottom, starting from 0 (first row) and ending with SF-1 (last row), take the binary representation of the number of the desired row and express it with log₂SF bits. Generally speaking, for every permutation (the rows of an Hadamard matrix are identical, except a permutation, to the set of OVSF with spreading factor SF) a modification to the transformation of the code number that takes in account the permutation is all of what is required. Figure 2 shows, using a flowchart, the generation method of this invention.

For the generation of the sequence the values of SF and n are received in input. If necessary n is transformed as previously described, obtaining the binary number n'=n- 1 expressed with log₂SF bits: ri= bit_{log2 SF},bit,_h ^^ ,...,bit_x .

We start from the common value c, , = (1) and for each bit of n', starting from the highest significant bit bit_{]ogι SF} with the iteration index z=log SF (the less significant bit bit for an Hadamard matrix) for each step the sequence previously generated is repeated as it is if the -th bit of the code is equal to 0 or changed in sign if the z^'-fh bit is equal to 1. The iteration ends when the index i equals to 0, that means that all the bits of the binary number n ' have been considered. For the -th bit of n' exactly 2^1'1 values are generated, for an overall number of elements, including the initial common value, equal to ∑2'-^l + l = SF ι=l..log₂ SF

It is now clear how the sequence could be loaded in a shift-register adequately dimensioned (great enough to contain all the requested sequence) and repeated with any more computation.

As an example, in what follows the generation of the code c_{16 6} is described.

In the initialisation phase the binary version of n' is calculated, being SF=16 and n=6 it will be n '=0101.

Step 1: the most significant bit of n' is 0, so the initial sequence (1) is repeated with the same sign, obtaining Cseq = l , 1. Step 2: the second most significant bit of n' is 1, so the previously generated sequence is repeated changed in sign, obtaining Cseq = 1 , 1 , -1 , - 1. Step 3: the third most significant bit of n' is equal to 0, so the sequence previously generated is repeated as it is, obtaining

Cseq = l , 1 , - 1 , -1 , 1 , 1 , -1 , -1. Step 4: the fourth and last bit of n' is equal to 1, so the sequence generated in the previous steps is repeated changed in sign, obtaining the final sequence of length 16 Cseq = l , 1 , -1 , -1 , 1 , 1 , -1 , -1 , - 1 , -1 , 1 , 1 , -1 , -1 , 1 , 1.

In figure 3 the block scheme of a circuit that implement the invention method is depicted. The circuit is composed by a first shift-register 10 dimensioned to contain the binary number n' a second shift-register 11 dimensioned to contain the sequence to be generated; a third shift-register 12 dimensioned to contain at least half of the sequence to be generated; a block 13 which parallel transfer the first half of the second shift register 11 in the third shift-register 12; a control and temporisation block 14.

The transfer block 13 will change or not the sign of the bits depending on the value assumed by the input command I. This signal is the output of the shift-register 10. If the output of the shift-register 10 is equal to 1 the transfer block change the sign of the bits, otherwise leave them as they are.

The control unit 14 receives the values SF and n that define the sequence to be generated. The control unit calculate the value of n' and load it in the first shift- register. It initialises the shift-register 11 too. Finally the control unit send a first clock impulse to the index shift-register 10, so that the most significant bit of n' is sent to the block 13, which transfer the sequence since then generated from the sequence shift-register 11 to the temporary shift-register 12, changed in sign or not depending on the value 0 or 1 of this bit. The control unit shifts bit by bit the sequence in the register 12 until this sequence is transferred in the shift-register 11, while the sequence here contained is shifted bit by bit too, so that the sequence in 12 is appended to the sequence in 11. After that the control unit command the index shift-register to give in output the next bit of n'. The transfer procedure, eventually the inversion and the appending is repeated to obtain in the sequence shift-register 11 the new intermediate sequence and so on until the generation of the sequence is completed. The sequence obtained is sent out from the sequence shift-register 11 and is available at the output Cseq of the generation apparatus.

It is evident how, with the same circuit, it is possible to generate the rows of an Hadamard matrix, changing the order of the bits of n' in the index shift-register so that the bits of n' are used starting from the less significant bit. Now it is clear how we have reached our objectives.

Obviously the preceding description of an instance using the innovative rules of this invention is only an exemplification of these innovative rules and therefore is not a limitation of their applicability. For example if the index k is numbered from 0 to SF- 1 and not from 1 to SF, the input value k will be given directly in input to the AND block 15, without any decrement.

To everyone skilled in the art of realise circuits like the one represented in figure 3 is clear from the above description that the same circuit could be realised with a wired logic, or with a microprocessor circuit opportunely programmed, or with an hybrid solution. It is clear that the method saves memory with respect to the standard generation of the orthogonal codes made recursively using a tree structure and with respect to the standard generation of Hadamard matrices made with a recursive procedure or using the Kronecker product. It is clear too that the desired sequence could be immediately read in output as it is partially generated, without waiting the completion of the generation, which is a great advantage as the length of the sequence increases.

Finally, the shift-register 12 could be not used if the transfer block 13 may append in the register 11 the new sequence to the partial sequence already in the shift-register 11.

Claims

1. A method for the generation of variable length orthogonal spreading sequences with maximal length 2^k and spreading factor SF or rows of Hadamard matrices of dimension SF, marked by an index n' of k=log SF bits. In the method the final sequence or row is generated starting from a predefined initial value and repeating partial sub-sequences, as they are or changed in sign depending on the value, 0 or 1 respectively, of each bit of the binary representation of n'.

2. A method, as set forth in claim 1, wherein the spreading sequence is generated taking sequentially the bits of π' starting from the most significant bit.

3. A method, as set forth in claim 1, wherein the spreading sequence is generated taking sequentially the bits of n' starting from the less significant bit.

4. A method, as set forth in claim 1 , wherein the sequence starting value is equal to 1.

5. A method, as set forth in claim 1, wherein the index n that is in the range from 0 to SF-1, is obtained starting from an index which assume values in the range from

1 to SF decremented by 1 and, if necessary, extended to a length of k bits.

6. An apparatus for the generation of variable length orthogonal spreading sequences with maximal length 2^k and spreading factor SF or rows of Hadamard matrices of dimension SF, marked by an index ri of k=log₂SF bits. The apparatus is composed by an index shift-register in which the binary number n' is loaded; a sequence or row shift-register in which the sequence or row to be generated is constructed; a transfer circuit that takes and eventually change in sign the sequence in the previous shift-register, appending it to the former sequence; a command block that controls the shift-registers and the transfer circuit, repeating the withdrawal, eventually the inversion and the appending for each bit of the index in the index shift-r jgister, so that each time the contents of the index shift- register is shifted of one position until all the bits of n' have been used.

7. An apparatus, as set forth in claims 6, characterised by the fact that the transfer circuit store the result in a temporary shift-register from which the output is taken one bit at the time to be inserted in the sequence shift-register.

8. An apparatus, as set forth in claims 6, characterised by the fact that the control circuit receives in input an index value n in the range 1..SF and calculate n' to be loaded in the index shift-register subtracting 1 from n and eventually extending it to a k bit length.

9. An apparatus, as set forth in claims 6, characterised by the fact that the sequence shift-register is initialised with a sequence constituted by a single bit set to 1.