WO2003030425A2

WO2003030425A2 - Method for generating pseudo-orthogonal sequences

Info

Publication number: WO2003030425A2
Application number: PCT/IB2002/004017
Authority: WO
Inventors: Maria-Gabriella Di Benedetto; Maria Stella Iacobucci
Original assignee: Universita' Degli Studi Di Roma 'la Sapienza'
Priority date: 2001-09-28
Filing date: 2002-09-27
Publication date: 2003-04-10
Also published as: ITRM20010592A0; ITRM20010592A1; AU2002338187A1; WO2003030425A3

Abstract

A method for generating pseudo-orthogonal codes for transmission using the DDMA technique in which: a) the value Ls is defined, corresponding to the length of the string from which to start; b) an integer k, with 1≤k≤Ls, is extracted; c) starting from the K-th bit of the string a number Nb of bits set in the string in a position subsequent to the k-th bit is considered, with Nb set equal to log2(Nh), and the value of all the Nb considered one after another read in the decimal system constitutes the first element of the code word; the elements of the code word are integers between 0 and (Nh-1); and d) all the other elements of the code word are obtained by translating one bit to the right and repeating step c).

Description

A COMPUTER METHOD FOR GENERATING PSEUDO-ORTHOGONAL CODES FOR DATA TRANSMISSION Filed of the invention

The present invention relates to a computer method for generating pseudo- orthogonal codes, in particular for data transmission. State of the art

The technique of data transmission through code-division multiple-access (CDMA) communication channels is characterized in that the separation between the different user signals is based upon the use of appropriate "orthogonal" codes generated via appropriate algorithms. CDMA is an access technique that is increasingly used in modern systems of transmission via radio or via cable. For example, it is has been adopted for third-generation mobile-radio systems. There are three variants of the CDMA technique that are currently widely used. The first, defined as direct-sequence (DS), envisages the direct modulation of the numerical flow to be transmitted via an appropriate code sequence.

The second, defined as frequency-hopping (FH), envisages that the carrier frequency will perform hops on a set of pre-defined values according to an appropriate sequence. The third, time-hopping (TH) is a variant of pulse-code modulation (PCM), in which the position of a pulse within an assigned window is regulated by a code sequence.

Broadly speaking, the principle that underlies the CDMA technique is that the user information, which is typically a narrow-band information, is spread over a much wider band. Consequently, techniques are called for that enable maximum exploitation of the capacities of the communication channels, and this is rendered possible by the CDMA techniques. These guarantee a high quality of transmission, minimizing the interference between the information produced by different users via the use of appropriate codes. Summary of the invention The primary purpose of the present invention is to provide a computer method for generating pseudo-orthogonal codes for use with techniques of transmission of information of the CDMA type so as to minimize the signalling that the users have to exchange for setting up a communication.

Another purpose of the invention is to provide a computer program that will implement the computer method of the invention and that will be versatile and usable with general-purpose computers or else with main frame computers. The above purposes, and others that will become apparent in the light of the ensuing description, are achieved by means of a computerised method for generating pseudo-orthogonal codes that has the characteristics specified in Claim 1 and by means of a computer program as specified in Claim 4. Thanks to the characteristics of the computer method and the computer program which implements it by means of computers, which employs both known algorithms and new algorithms, there is enabled a more efficient exploitation of both radio and cable communication channels. Brief description of the figures Further characteristics and advantages of the invention will emerge more clearly in the light of the ensuing detailed description of a preferred, but not exclusive, embodiment of the computer method for generating pseudo-orthogonal codes, hereinafter illustrated, by way of non-limiting example, with the aid of the annexed tables of drawings, in which: Figure 1 illustrates a graph representing information transmitted according to a first variant of the CDMA technique, in which the computer method for generation of the pseudo-orthogonal codes according to the invention is used; Figure 2 illustrates a graph representing information transmitted by just one user according to a second variant of the CDMA technique, in which the computer method for generation of the pseudo-orthogonal codes according to the invention is used;

Figure 3 illustrates a graph representing information transmitted according to a second variant of the CDMA technique by multiple users, in which the computer method for generation of the pseudo-orthogonal codes according to the invention is used; Figure 4 illustrates a graph representing information transmitted by just one user according to a third variant of the CDMA technique, in which the computer method for generation of the pseudo-orthogonal codes according to the invention is used; Figure 5 illustrates a graph representing information transmitted by three users according to a third variant of the CDMA technique, in which the computer method for generation of the pseudo-orthogonal codes according to the invention is used; Figure 6 represents the structure of a packet according to version 4 of the Internet protocol (IPv4); the pseudo-orthogonal code according to the invention is suitable for being generated starting from such packets; and

Figure 7 represents the structure of the header of a packet according to version 6 of the Internet protocol (IPv6); the pseudo-orthogonal code according to the invention is suitable for being generated starting from such packets. Description of a preferred embodiment of the invention

In the first variant, the DS-CDMA, each bit of information b(t) is multiplied by a binary sequence c(t), referred to as band-spreading code, which characterizes the user in question and is orthogonal to the codes used by the other users. Figure 1 illustrates said multiplication. As may be noted, the rate of the sequence transmitted x(t)=b(t)-c(t), referred to as chip rate f_c=1/Tc, is much higher than the bit rate of the information signal =MTb. Quantitatively, said band increase is defined via a factor referred to as process gain, which is equal to the ratio between the rate f_c of the signal transmitted and the rate f_b of the information signal and is, in general, designated by "G":

*^b

On the receiver end, thanks to the properties of the band-spreading codes used, it is possible to extract user information via a simple correlation of the entire signal received with the code that had been used during transmission. Recovery of the information starting from the signal received is obtained as described in what follows. Let be q(t) and C_j(t) be two code words. These are orthogonal if:

E[c,(t) -c_t(t)]_Tt =l;E[_Cl(t)-c₂(t)]_Tb = 0

The encoded words are: x₁(t) = b_l(t) - c_l(t) x₂(t) = b₂(t) -c₂(t)) In the case of multiple access, the signal transmitted is: z{t) = x_x{t) + x₂(t)

Assuming that there is absence of noise, the signals decoded by the individual users are:

E[z{f)

= E[x₁(t) - c_l(t) - c_l(t)+x₂(ή-c₂(t)

=

= x_l(t)-E[c_l(t) -

+x₂(t) -E[c₂(t)-c_l(t)]_Tb = ,(

E[z(t)-c₂(t)]_Tb = E[x₁(t) -c_l(t) -c₂(t)+x₂(t)-c₂(t) - c₂(t)]_Tb =

x₂(t) In this first case, the band-spreading code can be formed by the product, bit by bit, of the Walsh-Hadamard codes with pseudo-random sequences. The second access technique, the TH-CDMA, is also promising for future generations of mobile-radio systems. This technique, also referred to as (IR) impulse radio, is a spread-spectrum technique that uses pulses of extremely short duration of a pulse-position-modulation (PPM) type.

Multiple access is obtained via use of TH codes, i.e., the signal transmitted is:

where g(t) represents the pulse, N_s is the number of pulses per bit, and

T_b =N_S -T_f is the bit duration. The sequence ^represents the bits of information. An additional delay of c_}T_c is given by the TH code, with Q ≤C_j ≤ N_h and

N_h -T_c <T_f . Figure 2 illustrates the concept of the TH-CDMA in the case of just one user who transmits one bit. Figure 3 illustrates multiple access, in which the user 1 uses the sequence C⁽¹⁾=[1 0 0 2], the user 2 uses C⁽²⁾=[0 1 2 0], and the user 3 uses C⁽³⁾=[2 2 1 0]. The TH codes used are a string of integers between 0 and (N_h-1 ) of length N_p.

The third access technique of a CDMA type is the FH-CDMA. In this case the total band is divided into a number of sub-bands, and each user transmits in one sub- band, which changes at pre-set time intervals according to a frequency-hopping (FH) sequence. Figure 4 illustrates the FH-CDMA with just one user. In this example, the frequency-hopping sequence used [f2 f1 f1 f3] is illustrated. Figure 5 illustrates multiple access with three users, in which user number 1 uses the sequence [f2 f1 f1 f3], user number 2 uses [f1 f2 f3 f1], and user number 3 uses [f3 f3 f2 f2]. If an integer is associated to each frequency, the FH codes are strings of integers.

Underlying the invention is the definition of an algorithm that enables a pseudo- random code to be obtained starting from a binary string. The pseudo-random code is used for spread-spectrum access to a shared resource, typically the radio channel or cable channel. In particular, in multiple-access networks said code distinguishes the communication between two users of the network. The protocol currently used in the majority of telecommunication networks is the Internet Protocol (IP), in the version IPv4. An increasingly wide diffusion of this protocol is forecast for the next few years, together with a gradual migration to version 6 of the IP protocol, IPv6, on account of the limited number of Internet addresses that can be handled with IPv4. The algorithm according to the invention is designed to be applied to any binary string. A possible advantageous application is the one where the binary string is the concatenation of the IP addresses of the source machine and of the addressee. In fact, communication between two network nodes via IP is based upon the exchange of packets, referred to as IP packets, consisting of a header and a body. The structure of the header of the IPv4 packets is the one represented in Figure 6, and the structure of the header of the IPv6 packets is the one represented in Figure 7. As may be seen, in the header of the IP packets there is always present the pair made up of the source address and the destination address. The length of said addresses is 32 bits for IPv4 and 128 bits for IPv6. In this case, the length of the string for the generation of the code is 64 bits for IPv4 and 256 bits for IPv6. The algorithm for generating the code, which is designed to be used for the generation of the sequences in the three CDMA variants described above, is obtained with the following process. a) The string from which to start, of length L_s, is defined. b) An integer k, with l≤k≤L_s , \s extracted. c) Starting from the k-th bit of the string of length L_s, a number N_b of bits is considered, which are set in the string in a position subsequent to the k-th bit, where N is derived by calculation of log₂(N_h), and the value of all the N_b bits, considered one after another, read in decimal base, constitutes the first element of the code word. d) All the other N_p elements of the code word are obtained by translating one bit to the right and repeating step c). Note that the numbers making up the output code are integers that may range from 0 to (Nh -1).

The inventive idea is linked to the possibility of generating a code with pseudorandom characteristics starting from a known binary string and an integer k. This means that two terminals connected together by a communication channel, to which the binary string is already known, corresponding, for example, to the IP addresses of the two terminals that have to communicate with one another (in the case of a communication via the Internet), can independently find the code to be used for communicating with one another, by further exchanging, in the step of setting-up of the call, only one integer k. In the entire process, the computer just has to store the binary string present in the software that implements the particular network protocol, for example the IP protocol in the case of communication via the Internet, and the integer k. This may be extracted from a generator of pseudorandom numbers present in the computer and stored for use in relation to the communication, or else it is possible to define the integer k in some other appropriate way.

The use of the invention is extremely wide because is applicable in all network terminals that use the spread-spectrum access technique to a shared resource, when the code used for the spread spectrum is a pseudo-random code. In addition, the wide use of the IP and the diffusion of mobile-radio networks supporting IP with CDMA access to the radio resource renders the algorithm applicable to an extremely wide range of mobile networks for telecommunications. The implementation of the method according to the invention is advantageously provided via the definition of a computer program, in particular for a general purpose computer, also of a personal-computer type. The program may be written in an appropriate programming language, such as may be "C+" or equivalent. The said program can be stored in data-processing means integrated directly with telecommunications devices and be implemented, according to appropriate modalities known to a person skilled in the branch, for the needs of data transmission.

Claims

1. A method for generating pseudo-orthogonal codes for data transmission, designed for implementation by electronic data-processing means characterized by the following steps: a) determining a pre-defined binary-code string, of length L_s; b) defining a value (N_p), corresponding to the length of the output string; c) defining an integer k, with value greater than or equal to 1 and less than or equal to said length (L_s); d) identificating the k-th bit of the string, and taking into consideration of a given number N_b of bits in the string in a position subsequent to the k-th bit, said number

N_b being obtained from the value of log₂(N_h), where the integers that make up the output code range from 0 to (N_h -1 ); e) reading the value of said number N_b of bits in the decimal system, the said value determining the first element of the word of said pseudo-orthogonal code; and f) identificating the k+1 -th bit and executing the previous steps d), e) to determine a subsequent element of the code word.

2. The method according to Claim 1 , wherein steps d), e), and f) are repeated for the number of bits N_p that make up the output string.

3. The method according to Claim 1, wherein the number k is generated in a random way by a computer program or other appropriate means.

4. A computer program comprising a program code for computers, designed to carry out all the steps of Claim 1.

5. The computer program according to Claim 4 stored on means accessible via computer.