ITMI992747A1

ITMI992747A1 - METHOD AND DEVICE FOR THE GENERATION OF ORTHOGONAL VARIABLE SPREADING FACTOR CODES OR HADAMARD DIE LINES FOR COM SYSTEMS

Info

Publication number: ITMI992747A1
Application number: IT1999MI002747A
Authority: IT
Inventors: Fulvio Piccinonno
Original assignee: Telit Mobile Terminals Spa
Priority date: 1999-12-30
Filing date: 1999-12-30
Publication date: 2001-06-30
Also published as: AU2395701A; WO2001050659A1; IT1314346B1; ITMI992747A0

Description

La presente invenzione si riferisce ad un innovativo metodo per la generazione di codici ortogonali a fattore di spreading variabile (OVSF) o di righe di matrici di Hadamand per sistemi di comunicazione. L’invenzione si riferisce inoltre ad un dispositivo di generazione applicante il metodo. The present invention refers to an innovative method for the generation of orthogonal codes with variable spreading factor (OVSF) or rows of Hadamand matrices for communication systems. The invention also refers to a generation device applying the method.

Nei sistemi di comunicazione a divisione di spettro, quali i sistemi CDMA impiegati per la comunicazione telefonica cellulare, le comunicazioni fra stazione base e stazioni mobili sono stabilite impiegando i cosiddetti codici di “spread”. Nella sostanza, la stazione base assegna un certo numero di canali a ciascuna stazione mobile. La distinzione fra i vari canali è fatta in base a un codice di spread che identifica lo specifico canale. E’ nota la necessità di impiegare codici ortogonali a fattore di spreading variabile allo scopo di migliorare l’efficienza nell’utilizzo della banda disponibile. Poiché diversi servizi richiedono diversi fattori di spreading, nei canali fisici è necessario potere generare sequenze di spreading ortogonali a lunghezza variabile. Poiché i generatori di codici devono essere presenti non solo nelle stazioni fisse ma anche nelle stazioni mobili, è importante che i generatori di codici siano semplici e poco ingombranti. In spectrum division communication systems, such as CDMA systems used for cellular telephone communication, communications between base station and mobile stations are established using so-called “spread” codes. In essence, the base station assigns a certain number of channels to each mobile station. The distinction between the various channels is made on the basis of a spread code that identifies the specific channel. There is a known need to use orthogonal codes with variable spreading factor in order to improve efficiency in the use of the available bandwidth. Since different services require different spreading factors, in physical channels it is necessary to be able to generate orthogonal spreading sequences of variable length. Since code generators must be present not only in fixed stations but also in mobile stations, it is important that code generators are simple and space-saving.

Scopo generale della presente invenzione è fornire un metodo e un dispositivo secondo il metodo, per la generazione semplice ed affidabile di sequenze di codici ortogonali a fattore di spreading variabile o di righe di matrici di Hadamand. The general purpose of the present invention is to provide a method and a device according to the method, for the simple and reliable generation of sequences of orthogonal codes with variable spreading factor or rows of Hadamand matrices.

In vista di tale scopo si è pensato di realizzare, secondo l'invenzione, un metodo per la generazione di sequenze di spreading ortogonali a lunghezza variabile con lunghezza massima 2<k >e fattore di spreading SF o di righe di matrici di Hadamard di dimensione SF, individuate da un indice binario n’ di k=log2SF bit, nel quale la sequenza finale o riga è generata partendo da un primo valore di sequenza predefinito e ripetendo sequenze parziali, uguali o cambiate di segno a seconda del valore, rispettivamente 0 o 1, di ciascun bit di n’. In view of this purpose, according to the invention, it was decided to provide a method for generating orthogonal variable-length spreading sequences with maximum length 2 <k> and spreading factor SF or rows of Hadamard matrices of size SF, identified by a binary index n 'of k = log2SF bit, in which the final sequence or row is generated starting from a first predefined sequence value and repeating partial sequences, equal or changed in sign depending on the value, respectively 0 or 1, of each bit of n '.

Sempre secondo l’invenzione, si è pensato di realizzare un dispositivo per la generazione di sequenze di spreading ortogonali a lunghezza variabile con lunghezza massima 2 e fattore di spreading SF o di righe di matrici di Hadamard di dimensione SF, individuate da un indice n’ di k=log2SF bit, caratterizzato dal fatto di comprendere uno shift-register di indice nel quale viene caricato l’indice n’ e uno shift-register di sequenza o riga nel quale viene formata la sequenza finale o riga, un circuito trasferitore invertitore comandato essendo connesso per il prelievo della sequenza parziale memorizzata nello shift-register di sequenza, un circuito di comando del trasferitore invertitore e degli shift-register di indice e di sequenza comandando il circuito trasferitore per prelevare dallo shift-register di sequenza la sequenza parziale in esso memorizzata, invertirla o meno a comando dell’uscita dello shift-register di indice, e memorizzare il risultato nello shift-register di sequenza accodato alla sequenza parziale già in esso, il circuito di comando ripetendo il prelievo, l’eventuale inversione e la memorizzazione accodata per ogni bit dell’indice nello shift-register di indice, facendo scorrere ogni volta di uno il contenuto dello shift-register di indice, fino ad avere utilizzato tutti i bit costituenti n’. Always according to the invention, it was thought to realize a device for the generation of orthogonal spreading sequences of variable length with maximum length 2 and spreading factor SF or rows of Hadamard matrices of size SF, identified by an index n ' of k = log2SF bit, characterized by the fact of comprising an index shift-register in which the index n 'is loaded and a sequence or row shift-register in which the final sequence or row is formed, a controlled inverter transfer circuit being connected for the withdrawal of the partial sequence stored in the sequence shift register, a control circuit of the inverter transfer and of the index and sequence shift registers controlling the transfer circuit to take the partial sequence in it from the sequence shift register stored, invert it or not at the command of the output of the index shift-register, and store the result in the shift-register of sequence ac coded to the partial sequence already in it, the control circuit repeating the withdrawal, the eventual inversion and the storage queued for each bit of the index in the index shift-register, each time scrolling by one the contents of the shift-register of index, until all the constituent bits n 'have been used.

Per rendere più chiara la spiegazione dei principi innovativi della presente invenzione ed i suoi vantaggi rispetto alla tecnica nota si descriverà di seguito, con l'aiuto dei disegni allegati, una possibile realizzazione esemplificativa applicante tali principi. To clarify the explanation of the innovative principles of the present invention and its advantages with respect to the known art, a possible exemplary embodiment applying these principles will be described below, with the help of the attached drawings.

-figura 1 rappresenta una parte iniziale di un albero per la generazione di sequenze di spreading; -figure 1 represents an initial part of a tree for the generation of spreading sequences;

-figura 2 rappresenta un diagramma di flusso descrivente il metodo secondo l’invenzione; -figure 2 represents a flow chart describing the method according to the invention;

-figura 3 rappresenta uno schema a blocchi di un circuito di generazione applicante il metodo dell’invenzione. - figure 3 represents a block diagram of a generation circuit applying the method of the invention.

Con riferimento alle figure, in figura 1 è mostrato un albero di generazione, nel quale ad ogni livello sono presenti codici (o rami) in numero pari al fattore di spreading SF associato a quel livello. Ad ogni codice è associato un indice dato dal fattore di spreading SF del livello, a ciascun livello i codici sono inoltre numerati da 1 al valore SF del livello. Ad esempio, al livello SF=2 avremo due rami il primo con codice indicato con c2,i e il secondo con codice indicato C2.2. La definizione dei codici è data nel modo seguente: With reference to the figures, Figure 1 shows a generation tree, in which at each level there are codes (or branches) in a number equal to the spreading factor SF associated with that level. Each code is associated with an index given by the spreading factor SF of the level, at each level the codes are also numbered from 1 to the SF value of the level. For example, at level SF = 2 we will have two branches, the first with code indicated with c2, i and the second with code indicated as C2.2. The definition of the codes is given as follows:

<C>U=(1) <C> U = (1)

csF.2k-i=(csF/2,k, cSF/2,k) per indice 2k-l = dispari csF.2k-i = (csF / 2, k, cSF / 2, k) for index 2k-l = odd

CsF^k=(csF/2.k, cSF/2,k) per indice 2k = pari CsF ^ k = (csF / 2.k, cSF / 2, k) by index 2k = even

I codici, a parte una diversa numerazione, corrispondono a righe di una matrice di Hadamard di dimensione SF. Apart from a different numbering, the codes correspond to rows of a Hadamard matrix of size SF.

La trasformazione dell’indice del codice viene effettuata decrementando di una unità il valore n del numero di codice, in modo che assuma valori compresi fra 0 e SF-1 ed esprimendolo in binario con una quantità di cifre pari a log2SF. La trasformazione così ottenuta viene qui indicata con n\ The transformation of the code index is carried out by decreasing the n value of the code number by one unit, so that it assumes values between 0 and SF-1 and expressing it in binary with a quantity of digits equal to log2SF. The transformation thus obtained is indicated here with n \

Ad esempio, la trasformazione dell’indice del sesto codice con fattore di spreading pari a 16, vale a dire ci6i6, sarà 0101, in quanto il decremento del numero di codice restituisce il valore 5, la cui rappresentazione binaria 101 deve essere espressa con Iog216=4 cifre. Ovviamente, nel caso i codici venissero numerati da 0 a SF-1 non sarebbe più necessaria l’operazione iniziale di decremento nella trasformazione sopra descritta. For example, the transformation of the index of the sixth code with a spreading factor of 16, i.e. ci6i6, will be 0101, as decrementing the code number returns the value 5, whose binary representation 101 must be expressed with Iog216 = 4 digits. Obviously, if the codes were numbered from 0 to SF-1, the initial decrement operation in the transformation described above would no longer be necessary.

Volendo generare una riga di una matrice di Hadamard di dimensione SF, sarà sufficiente numerare le righe dall’alto in basso da 0 (prima riga) a SF-1 (ultima riga) e prendere la sua rappresentazione binaria con un numero di cifre pari a log2SF. In generale, per qualsiasi permutazione (le righe di una matrice di Hadamard di dimensione SF sono identiche, a parte una permutazione, all’insieme di OVSF con fattore di spreading SF) sarà sufficiente una modifica alla trasformazione del numero di codice che tenga conto della permutazione. Wanting to generate a row of a Hadamard matrix of size SF, it will be sufficient to number the rows from top to bottom from 0 (first row) to SF-1 (last row) and take its binary representation with a number of digits equal to log2SF. In general, for any permutation (the rows of a Hadamard matrix of dimension SF are identical, apart from a permutation, to the set of OVSF with spreading factor SF) a modification to the code number transformation will suffice, taking into account the permutation.

In figura 2 è mostrato, per mezzo di un diagramma di flusso, il metodo di generazione della presente invenzione. Figure 2 shows, by means of a flow chart, the generation method of the present invention.

Per la generazione si ricevono in ingresso i valori SF e n sui quali basare la sequenza. Ad n si applica la trasformazione sopra detta (se necessaria) così da ottenere il numero binario n’=n-l con log^F bits, cioè: n’=bit|og2SF, bit(iog2sF>i . bittFor the generation, the values SF and n on which to base the sequence are received. The above transformation is applied to n (if necessary) so as to obtain the binary number n '= n-l with log ^ F bits, that is: n' = bit | og2SF, bit (iog2sF> i. Bitt

Si comincia dal valore iniziale ci,i=(l), comune a tutti i codici, e per ogni bit di n’, partendo dal bit più significativo bitiog2sF (dal meno significativo nel caso di una matrice di Hadamard) e per ogni passo si ripete la sequenza generata fino a quel punto, presa con lo stesso segno se il bit i-esimo del codice considerato è uguale a 0 o presa con segno cambiato se il bit i-esimo del codice considerato è uguale a 1. Il ciclo termina quando l’indice i giunge a zero, vale a dire quando sono stati considerati tutti i bit del numero binario n\ We start from the initial value ci, i = (l), common to all codes, and for each bit of n ', starting from the most significant bit bitiog2sF (from the least significant in the case of a Hadamard matrix) and for each step we repeats the sequence generated up to that point, taken with the same sign if the i-th bit of the considered code is equal to 0 or taken with a changed sign if the i-th bit of the considered code is equal to 1. The cycle ends when the index i reaches zero, i.e. when all the bits of the binary number n \ have been considered

Per l’i-esimo bit di n’ vengono generati 2<1'1 >valori della sequenza, per un totale di elementi, comprendendo anche il valore iniziale comune, pari a: For the i-th bit of n ', 2 <1'1> values of the sequence are generated, for a total of elements, also including the common initial value, equal to:

Risulta chiaro come là sequenza possa essere caricata (anche durante la generazione) in uno shift-register di dimensione opportuna (sufficiente a contenere l’intera sequenza richiesta) e ripetuta senza bisogno di ulteriori calcoli. It is clear how the sequence can be loaded (even during generation) in a shift-register of appropriate size (sufficient to contain the entire required sequence) and repeated without the need for further calculations.

A titolo di esempio, si descrive di seguito la generazione del codice Ci6,6· As an example, the generation of the code Ci6,6 is described below

Nella fase di inizializzazione si calcola n’ in binario che, poiché SF=16 e n=6, sarà n’=0101. In the initialization phase, n 'is calculated in binary which, since SF = 16 and n = 6, will be n' = 0101.

Passo 1: il bit più significativo di n’ è pari a 0, perciò la sequenza di inizio, che è costituita dal solo valore 1, viene ripetuta con lo stesso segno, ottenendo Step 1: the most significant bit of n 'is equal to 0, therefore the starting sequence, which consists only of the value 1, is repeated with the same sign, obtaining

Passo2: il secondo bit più significativo di n’ è pari a 1, perciò la sequenza generata al passo precedente viene ripetuta con segno opposto, ottenendo Step2: the second most significant bit of n 'is equal to 1, therefore the sequence generated in the previous step is repeated with the opposite sign, obtaining

q q

Passo 3: il terzo bit più significativo di n’ è pari a 0, perciò la sequenza generata al passo precedente viene ripetuta con lo stesso segno, ottenendo Step 3: the third most significant bit of n 'is equal to 0, therefore the sequence generated in the previous step is repeated with the same sign, obtaining

Passo 3: il quatto e ultimo bit di n’ è pari a 1, perciò la sequenza generata al passo precedente viene ripetuta con segno opposto, ottenendo la sequenza finale di 16 valori Step 3: the fourth and last bit of n 'is equal to 1, therefore the sequence generated in the previous step is repeated with the opposite sign, obtaining the final sequence of 16 values

In figura 3 è mostrato lo schema a blocchi di un circuito realizzante il metodo dell’invenzione. Il circuito comprende: un primo shift-register 10 di dimensione adatta a contenere il numero binario n’; un secondo shift-register 11 di dimensione adatta a contenere la sequenza da generare; un terzo shift-register 12 di dimensione adatta a contenere almeno la metà della sequenza da generare, un blocco 13 di trasferimento in parallelo della prima metà del secondo shift-register 11 nel terzo shift register 12; un blocco di controllo e temporizzazione 14. Figure 3 shows the block diagram of a circuit implementing the method of the invention. The circuit includes: a first shift-register 10 of a size suitable to contain the binary number n '; a second shift register 11 of a size suitable for containing the sequence to be generated; a third shift-register 12 of a size suitable to contain at least half of the sequence to be generated, a block 13 for the parallel transfer of the first half of the second shift-register 11 in the third shift register 12; a control and timing block 14.

Il blocco di trasferimento 13 inverte o meno i bit trasferiti a seconda del valore assunto dal segnale al suo ingresso di comando I. Tale segnale è l’uscita dello shiftregister 10. Se l’uscita dello shift-register 10 è pari a l, il blocco di trasferimento inverte i bit trasferiti, altrimenti li mantiene invariati. The transfer block 13 inverts or not the transferred bits according to the value assumed by the signal at its command input I. This signal is the output of the shiftregister 10. If the output of the shift-register 10 is equal to 1, the block transfer reverses the bits transferred, otherwise it keeps them unchanged.

All’unità di controllo 14 giungono i valori SF ed n di definizione della sequenza da generare (ingressi SF e n). L’unità di controllo calcola il valore n’ e lo carica nello shift-register n’. Inoltre, essa inizializza con la sequenza iniziale lo shift-register 11. Dopodiché, l’unità di controllo invia un primo impulso di clock allo shift-register dell’indice 10 The control unit 14 receives the values SF and n defining the sequence to be generated (inputs SF and n). The control unit calculates the value n 'and loads it into the shift-register n'. In addition, it initializes the shift register 11 with the initial sequence. After that, the control unit sends a first clock pulse to the shift register of index 10

Così che il bit più significativo di n’ viene inviato all’unità di trasferimento 13, che trasferisce dallo shift-register di sequenza 11 allo shift-register temporaneo 12 la sequenza fino a quel momento generata, invertita o meno in base al valore 1 o 0 di tale bit. L’unità di controllo scorre nello shift-register 12 la sequenza trasferita in esso fino a che, bit a bit, essa viene trasferita nello shift-register 11, mentre la sequenza contenuta in quest’ultimo si sposta anch’essa bit a bit, così che la sequenza nello shift-register temporaneo 12 viene accodata alla sequenza nello shift-register 11. Thus the most significant bit of n 'is sent to the transfer unit 13, which transfers the sequence generated up to that moment from the sequence shift register 11 to the temporary shift register 12, inverted or not based on the value 1 or 0 of that bit. The control unit scrolls in the shift-register 12 the sequence transferred in it until, bit by bit, it is transferred in the shift-register 11, while the sequence contained in the latter also moves bit by bit, so that the sequence in the temporary shift register 12 is appended to the sequence in the shift register 11.

Dopodiché, l’unità di controllo comanda lo shift-register di indice 10 per emettere il successivo bit di n’. La procedura di trasferimento, eventuale inversione e accodamento si ripete per ottenere nello shift-register di sequenza 11 la nuova sequenza intermedia e così via fino alla generazione completa della sequenza. La sequenza ottenuta é emessa dall’uscita dello shift-register di sequenza 11 ed è disponibile all’uscita Cseq del dispositivo di generazione. After that, the control unit commands the shift register of index 10 to emit the next bit of n '. The transfer, possible inversion and queuing procedure is repeated to obtain the new intermediate sequence in the shift register of sequence 11 and so on until the complete generation of the sequence. The sequence obtained is emitted from the output of the sequence 11 shift register and is available at the Cseq output of the generation device.

Con lo stesso circuito, risulta evidente come sia possibile ottenere righe di una matrice di Hadamard, cambiando l’ordine dei bit di n’ nello shift-register di indice in modo da considerare sequenzialmente i bit di n’ ad iniziare dal bit meno significativo. With the same circuit, it is clear how it is possible to obtain rows of a Hadamard matrix, changing the order of the bits of n 'in the index shift register in order to sequentially consider the bits of n' starting from the least significant bit.

A questo punto è chiaro come si siano raggiunti gli scopi prefissati. At this point it is clear how the intended purposes have been achieved.

Naturalmente, la descrizione sopra fatta di una realizzazione applicante i principi innovativi della presente invenzione è riportata a titolo esemplificativo di tali principi innovativi e non deve perciò essere presa a limitazione dell'ambito di privativa qui rivendicato. Ad esempio, come sopra accennato, nel caso si scelga di numerare gli indici n da 0 a SF-1, anziché da 1 a SF, il valore n in ingresso sarà utilizzabile direttamente, senza preventivo decremento di una unità. Naturally, the above description of an embodiment applying the innovative principles of the present invention is given by way of example of such innovative principles and must therefore not be taken as a limitation of the patent scope claimed herein. For example, as mentioned above, if you choose to number the indices n from 0 to SF-1, instead of from 1 to SF, the input value n will be usable directly, without decreasing it by one unit.

Inoltre, come facilmente immaginabile al tecnico, il circuito rappresentato in figura 3 può essere realizzato sia con un circuito a logica cablata, sia con un opportuno circuito a microprocessore opportunamente programmato, sia con una soluzione ibrida. Infine, lo shift-register temporaneo 12 può anche mancare se il blocco trasferitore 13 può esso stesso accodare nel registro 11 la nuova sequenza alla sequenza parziale già nello shift-register 11. Moreover, as easily imagined to the skilled person, the circuit shown in Figure 3 can be realized both with a wired logic circuit, with a suitable microprocessor circuit suitably programmed, and with a hybrid solution. Finally, the temporary shift register 12 can also be missing if the transfer block 13 can itself queue the new sequence to the partial sequence already in the shift register 11 in register 11.

Claims

CLAIMS X. Method for the generation of variable-length orthogonal spreading sequences with maximum length 2 <k> and spreading factor SF or rows of Hadamard matrices of size SF, identified by a binary index n 'of k = log2SF bit, in which the final sequence or line is generated starting from a first predefined sequence value and repeating partial sequences, equal or changed in sign depending on the value, respectively 0 or 1, of each bit of n \ 2. Method according to claim 1 in which the spreading sequence is generated by sequentially taking the bits of n 'starting from the most significant bit. 3. Method according to claim 1 in which a row of the matrix is generated by sequentially taking the bits of n 'starting from the least significant bit. 4. Method according to claim 1 in which the initial sequence value is equal to 1. 5. Method according to claim 1, in which the index n ', variable from 0 to SF-1, is obtained starting from an index n variable from 1 to SF, decreased by 1 and, if necessary extended to bring it to the length of k bits. 6. Device for the generation of variable-length orthogonal spreading sequences with maximum length 2 <k> and spreading factor SF or rows of Hadamard matrices of size SF, identified by an index n 'of k = Iog2SF bit, characterized by comprising an index shift-register into which the index n 'is loaded and a sequence or row shift-register in which the final sequence or row is formed, a commanded inverting transfer circuit being connected to pick up the sequence partial sequence stored in the sequence shift register, a control circuit of the inverter transfer and of the index and sequence shift registers controlling the transfer circuit to take the partial sequence stored in it from the sequence shift register, invert it or not at the command of the output of the index shift register, and store the result in the sequence shift register appended to the partial sequence already in it, the circuit command by repeating the withdrawal, possible inversion and storage queued for each bit of the index in the index shiftregister, scrolling the contents of the index shiftregister each time by one, until all the constituent bits n. 7. Device according to claim 6, characterized in that the transfer circuit stores the result in a temporary shift register from which said result is taken to be inserted bit by bit in said sequence shift register. 8. Device according to claim 6, characterized in that the control circuit receives at its input an index value n variable between 1 and SF and calculates the said value n 'to be stored in the index shift register by subtracting 1 from n and possibly extending it up to kbit length. 9. Device according to claim 6, characterized in that the sequence shift register is initialized with a sequence consisting of a single bit at 1.