Orthogonal Sequences

Orthogonal codes are sets of sequences extensively used in wireless communication.


August 01, 2001
URL:http://www.drdobbs.com/orthogonal-sequences/184404738

Aug01: Algorithm Alley

William is a consultant, lecturer, and author of over a dozen books on data communications and computer networking. His most recent book is Wireless Communication and Networks (Prentice-Hall, 2001). He can be contacted at http:// www.williamstallings.com/ or [email protected].


A key element in spread spectrum communication is the use of a spreading sequence. The spreading sequence, c(t), is a sequence of binary digits shared by the transmitter and receiver. In the common scheme known as direct-sequence spread spectrum (DSSS), spreading consists of multiplying (XOR) the input data by the spreading sequence, where the bit rate of the spreading sequence is higher than that of the input data. When the signal is received, the spreading is removed by multiplying with the same spreading code, exactly synchronized with the received signal.

The resulting data rate is consequently that of the spreading sequence. This increases the transmitted data rate and therefore increases the required bandwidth. The redundancy of the system is also increased. The spreading codes are chosen so that the resulting signal is noise-like; therefore, there should be an approximately equal number of ones and zeros in the spreading code and few or no repeated patterns.

Several things can be gained from this apparent waste of bandwidth:

When spreading codes are used in a CDMA application, there is the further requirement of lack of correlation. When multiple signals are received, each spread with a different spreading code, the receiver should be able to pick out any individual signal using that signal's spreading code. The spread signals should behave as if they were uncorrelated with each other, so that other signals will appear as noise and not interfere with the despreading of a particular signal. Because of the high degree of redundancy provided by the spreading operation, the despreading operation is able to cope with the interference of other signals in the same bandwidth.

For example, Figure 1 illustrates a simplified scheme for CDMA encoding and decoding. There are seven logical channels, all using DSSS with a spreading code of 8 bits. Assume that all sources are synchronized. If all seven sources transmit a data bit, in the form of an 8-bit sequence, the signals from all sources combine at the receiver so that two positive or two negative values reinforce and a positive and negative value cancel. To decode a given channel, the receiver multiplies the incoming composite signal by the spreading code for that channel, sums the result, and assigns binary 1 for a positive value and binary 0 for a negative value. In this example, the codes are C0=00000000; C1=01010101; C2=00110011; C3=01100110; C4=00001111; C5=01011010; C6=00111100. It is more convenient here to use +1 and -1 to represent the two binary digits 1 and 0, as in Figure 1.

Two general categories of spreading sequences have been used: PN (pseudonoise or pseudorandom number) sequences and orthogonal codes. PN sequences are the most common ones used in FHSS systems and DSSS systems not employing CDMA. In DSSS CDMA systems, both PN and orthogonal codes have been used. In this article, I'll examine orthogonal sequences.

Orthogonal Codes

Unlike PN sequences, an orthogonal code is a set of sequences in which all pairwise cross correlations are zero. An orthogonal set of sequences is characterized by the equality in Example 1(a), where M is the length of each of the sequences in the set, fi and fj are the ith and jth members of the set, and t is the bit duration.

Both fixed- and variable-length orthogonal codes have been used in CDMA systems. For the CDMA application, each mobile user uses one of the sequences in the set as a spreading code, providing zero cross correlation among all users.

Walsh Codes

Walsh codes are the most common orthogonal codes used in CDMA applications. A set of Walsh codes of length n consists of the n rows of an n×n Walsh matrix. The matrix is defined recursively as in Example 1(b), where n is the dimension of the matrix and the overscore denotes the logical NOT of the bits in the matrix. The Walsh matrix has the property that every row is orthogonal to every other row and to the logical NOT of every other row.

Figure 2 shows the Walsh matrices of dimensions 2, 4, and 8. It is easily seen that a bitwise multiplication of any two rows produces 0. For example, in the 8×8 matrix, row 3 multiplied by row 4 equals 1+(-1)+1+(-1)+1+(-1)+1+(-1)=0. The example of Figure 1 uses Walsh codes from the 8×8 matrix.

Orthogonal spreading codes such as the Walsh sequences can only be used if all of the users in the same CDMA channel are synchronized to the accuracy of a small fraction of one chip. Because the cross correlation between different shifts of Walsh sequences is not zero, if tight synchronization is not provided, PN sequences are needed.

Variable-Length Orthogonal Codes

Third-generation mobile CDMA systems are designed to support users at a number of different data rates. Thus, effective support can be provided by using spreading codes at different rates while maintaining orthogonality. Suppose that the minimum data rate to be supported is Rmin and that all other data rates are related by powers of 2. If a spreading sequence of length N is used for the Rmin data rate, such that each bit of data is spread by N=2n bits of the spreading sequence (transmit the sequence for data bit 0; transmit the complement of the sequence for data bit 1), then the transmitted data rate is NRmin. For a data rate of 2Rmin, a spreading sequence of length N/2=2n-1 will produce the same output rate of N×Rmin. In general, a code length of 2n-k is needed for a bit rate of 2kRmin.

A set of variable-length orthogonal sequences is readily generated from Walsh matrices of different dimensions. Define the N×N matrix CN as consisting of N rows, each of length N, labeled CN(1), CN(2), ..., CN(N). With the limitation that N is a power of 2, the matrix CN can be recursively generated from the matrix CN/2 as in Example 1(c).

Starting with the 1×1 Walsh matrix {-1}, Figure 3 shows the results through C8. Note that each matrix in Figure 3 contains all of the rows of the corresponding Walsh matrix, but in a different order. This ordering is significant for the following reason. Each row CN(i) of CN has the following properties:

For example, C8(4) is not orthogonal to C4(2), C2(1), C16(7), C16(8), or any other row that appears on the same tree path as itself. If a channel requires a mixture of spreading codes to accommodate different data rates, the selection must be made to avoid rows that are on the same tree path.

Multiple Spreading

When sufficient bandwidth is available, a multiple spreading technique can prove highly effective. A typical approach is to spread the data rate by an orthogonal code to provide mutual orthogonality among all users in the same cell and to further spread the result by a PN sequence to provide mutual randomness (low cross correlation) between users in different cells. In such a two-stage spreading, the orthogonal codes are referred to as "channelization codes," and the PN codes are referred to as "scrambling codes." For example, this technique is used in the IS-95 Standard. IS-95 is the most widely used second-generation CDMA scheme, primarily deployed in North America.

DDJ

Aug01: Algorithm Alley

Example 1: (a) An orthogonal set of sequences; (b) Walsh codes; (c) variable-length orthogonal codes.

Aug01: Algorithm Alley

Figure 1: Seven-channel CDMA encoding and decoding.

Aug01: Algorithm Alley

Figure 2: Walsh matrices.

Aug01: Algorithm Alley

Figure 3: Generation of variable-length orthogonal codes.

Terms of Service | Privacy Statement | Copyright © 2024 UBM Tech, All rights reserved.