Method and Apparatus for Increasing the Data Rate for a Given Symbol Rate in a Spread Spectrum System

The present invention relates to a spread spectrum communications technique. More particularly, the present invention relates to an encoding technique for use in spread spectrum communications wherein an N-fold increase in data rate for a given symbol rate is achieved by encoding N data bits for each spreading sequence.

Spread spectrum techniques permit data signals to be extracted from noise with a relatively small error rate. In a spread spectrum system, a binary 1 data bit is represented by a first sequence of binary states or elements called chips, and a binary 0 data bit is represented by a second sequence of binary chips. Each sequence of binary chips is known as a spreading sequence. Typically, the second sequence of chips is the complement of the first sequence chips. Thus, in a spread spectrum coding technique, the basic unit of data, i.e. the data bit, is encoded by forming a sequence of chips. The chip rate is much higher than the data rate and each chip has a much broader frequency spectrum than a data bit. Since each chip has a frequency spectrum that is spread much wider than the frequency spectrum of the original data bit, the technique is known as spread spectrum.

At a receiver, a stream of data bits, which has been transmitted using the spread spectrum format, is recovered using a process known as despreading. Despreading involves correlating the received signal which comprises chips, with a local reference chip sequence. The local reference utilizes the same chip sequence that was used to encode the data bits at the transmitting end. More particularly, at the receiver, the reference chip sequence is stored in a register. The signal comprising the received chips is entered into a shift register, and for each chip time period, the received chips are advanced one position in the shift register. At each chip time period, the number of matches between the prestored reference sequence and the received chips in the shift register is obtained. Consider the case where the reference sequence corresponds to a binary 1 data bit and the binary 0 data bit is represented by the complement of the reference sequence. In this case, when the number of matches exceeds a predetermined upper threshold, a data decision is made indicating the presence of a binary 1 data bit. When the number of matches falls below a predetermined lower threshold, a data decision is made indicating the presence of a binary 0 data bit. In between the data decisions times, when there are portions of two consecutive spreading sequences in the shift register (i.e. the end portion of one sequence and the beginning of the next sequence), the number of matches falls in between the high and low thresholds, thus preventing erroneous data decisions.

In a noise free system, the presence of a binary 1 will be indicated by a total match between the received chips in the shift register and the reference sequence. Similarly, the presence of a binary 0 will be indicated by no matches between the received chips in the shift register and the reference sequence. However, in real systems, noise prevents all the chips in a spreading sequence from being correctly received so that binary 1 and binary 0 data decisions are based on whether the number of matches is above or below upper and lower predetermined thresholds, respectively. This process has the effect of averaging out random noise. Thus, the despread signal component is enhanced and the noise component is reduced. This is known in the spread spectrum art as process gain and is defined as the number of chips per data bit.

In short, in a spread spectrum communication system, at an encoder or spreader, each data bit in a data bit stream is coded by transmitting a sequence of binary chips. Typically, one such spreading sequence is used to represent a binary "1" and its complement is used to represent a binary "0". The chips representing the data bit stream are modulated onto a carrier using a conventional two-level modulation technique such as binary phase shift keying (BPSK) or frequency shift keying (FSK), and transmitted to a decoder or despreader. At the decoder or despreader, the chips are demodulated and correlated with a reference sequence to reconstruct the original data bit stream.

In a spread spectrum system, the symbol rate is the rate at which sequences of chips are transmitted and the data rate is the rate at which data is transmitted. For a given symbol rate, it is desirable for the data rate to be as high as possible.

Outside of the spread spectrum art, it is well known that encoding multiple bits per symbol increases the data transmission rate for a given symbol transmission rate, provided that the symbols can be received with a sufficiently low error rate. In the prior art, the encoding of multiple bits per symbol is typically accomplished by various multiple level modulation schemes such as quadriphase shift keying (QPSK) or quadrature amplitude modulation (e.g. 64QAM). These multilevel modulation techniques utilize combinations of changes in phase and/or amplitude to provide multiple (i.e. more than two) modulation levels. Thus, each transmitted modulated symbol can represent more than one bit. The disadvantage of these multilevel modulation schemes is that there is an increase in symbol error rate for a given signal-to-noise ratio as the modulation scheme contains more levels.

In view of the foregoing it is an object of the present invention to improve the spread spectrum communication technique by increasing the data rate for a given symbol rate.

It is a further object of the present invention to improve the spread spectrum communication technique by increasing the data rate for a given symbol rate by encoding multiple bits with each spreading sequence.

It is also an object of the present invention to improve the spread spectrum communication technique by increasing the data rate for a given symbol rate without the use of a multilevel modulation technique.

The present invention is an improvement in the spread spectrum communication technique which increases the data rate N-fold for a given symbol rate. This is accomplished by encoding N (N.gtoreq.2) bits for each transmitted spreading sequence.

More particularly, to encode a stream of data bits, 2.sup.N predetermined spreading sequences are provided. The data bit stream is divided into groups of N bits, and for each N bit group, a corresponding one of the 2.sup.N predetermined spreading sequence is selected and transmitted.

Illustratively, the chips comprising a selected spreading sequence serve as a source for a simple two-level modulation scheme such as frequency shift keying (FSK) or binary phase shift keying (BPSK).

To receive a signal transmitted in the multiple bit per spreading sequence format, the spreading sequences are demodulated and correlated with the 2.sup.N predetermined spreading sequences to identify which of the 2.sup.N predetermined spreading sequences have been received. The identified spreading sequences are then decoded to regenerate the original groups of N data bits.

FIGS. 1A and 1B illustrate the conventional spread spectrum technique.

FIG. 2 illustrates a spreader for encoding N bits per spreading sequence, in accordance with an illustrative embodiment of the present invention, and a despreader for decoding N bits per spreading sequence, in accordance with an illustrative embodiment of the present invention.

Before describing the N-bit spread spectrum encoding technique of the present invention, it may be helpful to briefly review the conventional single bit spread spectrum technique.

In accordance with the conventional spread spectrum encoding technique, each data bit in a data bit stream is mapped into a sequence of chips known as a spreading sequence. Consider the following example:

wherein the spreading sequence for binary 0 is the complement of the spreading sequence for binary 1 and wherein (first) and (last) indicate the order in which the chips are transmitted. Each chip has a much wider frequency spectrum than a data bit. The spreading sequence corresponding to each bit in the data bit stream is modulated onto a carrier, preferably using a simple two-level modulation scheme such as BPSK or FSK and transmitted to a remote receiver. At a receiver, the received spreading sequences are correlated with a reference sequence to convert the spreading sequences back into data bits.

FIG. 1A shows a reference sequence which is the same as the spreading sequence for binary 1 identified above. Illustratively, the reference sequence is stored in a register 10 which is schematically illustrated in FIG. 1A. FIG. 1A also shows the incoming chips. The incoming chips are entered into a shift register 20 schematically illustrated in FIG. 1A. The incoming chips are shifted one position in the shift register (i.e. in the direction of arrow 21) at the end of each chip time period.

The incoming chips are correlated with the reference sequence. More particularly, at each chip time period, the chip values stored in the shift register are compared with the reference sequence and the number of matches is counted. The number of matches is plotted as a function of time in FIG. 1B. Note that the plot of FIG. 1B has a high threshold and a low threshold. In any chip time period, when the number of matches exceeds the high threshold, a data decision is made indicating the presence of a binary 1 data bit. Similarly, when the number of matches falls below the low threshold, a data decision is made indicating the presence of a binary 0 bit. In the absence of noise, a binary 1 bit would be indicated by a complete match between the reference sequence and the received chips in the shift register. Similarly, binary 0 would be indicated by a complete mismatch between the reference sequence and the received chips in the shift register because a binary 0 is encoded with the complement of the reference sequence. However, because in a noisy environment there is a certain chip error rate, a detection decision indicating a binary 1 or binary 0 is made when the number of matches exceeds or falls below high and low thresholds, respectively. As indicated previously, this correlation process has the effect of averaging out random noise so that the signal component is enhanced and the noise reduced.

In connection with FIG. 1B, it should be noted that at times when a complete received spreading sequence is not being compared with the reference sequence (i.e. between data decision times), the number of matches falls in between the high and low threshold. Only at decision times do the number of matches fall outside the thresholds. Another way of saying this is that the spreading sequences utilized to code the binary 1 and binary 0 data bits have a single autocorrelation peak, low autocorrelation sidelobes and low cross and partial correlations. Since the binary 1 and binary 0 spreading sequences are complements of each other, the cross-correlation function is small.

While the above-described spread spectrum technique serves to reduce the error rate for a transmitted bit stream, it would be desirable to increase the data rate for a given symbol rate. As indicated above, the present invention achieves an N-fold increase in data bit rate for a given symbol rate by coding N bits for each spreading sequence. Consider an example wherein the data rate is doubled for a given symbol rate. This is accomplished by coding two data bits per spreading sequence. This requires four different chip sequences denoted by A, B, A, B, where Aand Bdenote the complements of A and B, respectively.

Preferably, in order to be distinguishable at the despreader, the sequences A, B, A, Bhave the following properties.

1. single autocorrelation peak

2. low autocorrelation sidelobes

3. low cross and partial correlations (By a partial correlation, it is meant that when a portion of one sequence and a portion of another sequence is compared with one of the sequences, the number of matches falls in between a high and a low threshold.)

For practical purposes, the sequences A, B, A, B, should be nearly balanced, i.e., they should have almost as many binary 1's as binary 0's, to avoid D.C. offsets.

These sequences can be found by a search of all possible combinations of sequences of a given length L and selecting the sequence combinations that satisfy the above requirements. If the sequence of length 2L obtained by concatenating the sequences A and B of length L is denoted by AB and "*" denotes correlation, then the requirements identified above become, for the sequences A, B, A, B, the following:

1. AA*A, BB*B, AA* A, BB*B have a single autocorrelation peak.

2. AA*B, BB*A, AA*B, BB*A have low cross-correlations.

3. AA* A, BB*B have low cross-correlation.

4. AA*B, BB*A have low cross-correlations.

5. AB*A, AB*B, AB*A, AB*B, BA*A, BA*B, BB*A, BA*B have low cross-correlations.

How far the autocorrelation sidelobes and the cross and partial correlations are below the peak autocorrelation values will determine how many chips can be received in error. It is desirable that the autocorrelation sidelobes and the partial and cross correlations be as far away from the high and low thresholds as possible.

An example of a possible chip sequence to be used for encoding 2 bits per chip sequence when L=12 is as follows:

For these sequences, peak correlations are 0 and 12 matches. Autocorrelation sidelobes and cross and partial correlation values are at most 8 and 4 matches, so the high threshold can be set .gtoreq.9 and the low threshold can be set .ltoreq.3, with thresholds at 10 and 2 providing the best performance for a given chip error rate.

The mapping from N-bit groups (e.g. N=2) to sequences should be done such that the bit groups with the largest Hamming distance are mapped into sequences with the largest Hamming distance. For the illustrative sequences A, B, A, Bprovided above, a feasible mapping is as follows:

To illustrate how special the sequences A, B, A, B, are, consider that out of 16,777,216 possible sequence combinations of length L=12 chips, only four combinations satisfy the requirements stated above at the optimum side lobe level of 4 below peak correlation. These other combinations are:

To achieve a 3-fold increase in data rate, four sequences A, B, C, D and their complements A, B, C, D are needed to encode the eight possible combinations of three bits.

For optimal cross-correlations at length L=16, illustrative sequences are:

Autocorrelation sidelobes and cross and partial correlations are at most 5 and 11 matches.

FIG. 2 schematically illustrates a spreader 200 for encoding N bits per spreading sequence and a despreader 400 for receiving the spread spectrum signal produced by the spreader 200. The spreader 200 and despreader 400 are connected by the communications channel 300. In the illustrative spreader and despreader of FIG. 2, N=3 so that three bits are encoded per spreading sequence.

The spreader 200 comprises a sequence generator 202 which can generate 2.sup.N-1 =4 predetermined spreading sequences A, B, C, and D on lines 204. The sequence generator 202 may comprise a memory for storing the 2.sup.N-1 sequences or other circuitry for generating the sequences. The spreader 200 also includes a serial-to-parallel converter 206 for receiving on line 207 the data bit stream to be encoded. The serial-to-parallel converter 206 outputs groups of N=3 bits in parallel on lines 208a, 208b, 208c. Two of the bits on lines 208a, 208b are transmitted to the selector 210 so that the selector 210 can select one of the four sequences A, B, C or D. The selected sequence is then transmitted to an input 211 of an EXCLUSIVE-OR gate 212. The third bit of the N=3 bits produced by the serial-to-parallel converter 206 is transmitted via line 208c to a second input 213 of the EXCLUSIVE-OR gate 212. When the bit on line 208c is a binary 1, the complement of the selected sequence is produced at the output 214 of the gate 212. The sequence at the output of the gate 212 is modulated by the RF modulator 220 and transmitted via the channel 300 to the despreader 400.

At the despreader 400 the received spread spectrum signal is demodulated by the demodulator 402 and transmitted in parallel to the four correlators 410, 411, 412, 413. The correlators 410, 411, 412, 413 have as their reference sequences, the sequences A, B, C, and D respectively. Thus, the correlators 410, 411, 412, 413 determine if the received spreading sequences include the sequences A or A, B or B, C or C, D or D, respectively. Each of the correlators has two output lines 420, for indicating the presence of a particular sequence or its complement or equivalently to indicate if the low or high threshold has been exceeded. The decoder 430 receives an output from any of the 2.sup.N =8 correlator output lines 420 and converts this output into a corresponding N=3 bit group in parallel on lines 432. The parallel N 3 bit group on lines 432 is converted into serial form on line 444 by parallel-to serial converter 440.

If, for example, in a communication system, a correlator output is used to indicate link activity, the presence of 2.sup.N-1 rather than 1 correlator will increase the probability of falsely indicating a valid chip sequence when random noise is input to the despreader. This can be remedied by qualifying a "sequence present" signal from a correlator with another signal indicative of link activity such as received RF level.

In short, a method and apparatus for transmitting a stream of data bits in a spread spectrum format is disclosed. The inventive method comprises providing 2.sup.N predetermined spreading sequences, where N is equal to or larger than two. The predetermined spreading sequences have suitable auto, cross, and partial correlation properties. For each group of N bits in a stream of data bits to be transmitted, a particular one from the 2.sup.N predetermined spreading sequences is selected and transmitted. In this manner, each transmitted spreading sequence corresponds to a particular arrangement of N bits. The invention achieves an N-fold increase in data rate for a particular symbol rate by encoding N bits in a spreading sequence.

Finally, the above-described embodiments of the invention are intended to be illustrative only. Numerous alternative embodiments may be devised by those skilled in the art without departing from the spirit or scope of the following claims.