Dr. Dobb's is part of the Informa Tech Division of Informa PLC

This site is operated by a business or businesses owned by Informa PLC and all copyright resides with them. Informa PLC's registered office is 5 Howick Place, London SW1P 1WG. Registered in England and Wales. Number 8860726.


Channels ▼
RSS

Orthogonal Sequences


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:

  • You can gain immunity from various kinds of noise and multipath distortion. The earliest applications of spread spectrum were military, where it was used for its immunity to jamming.
  • It can also be used for hiding and encrypting signals. Only a recipient who knows the spreading code can recover the encoded information.

  • Several users can independently use the same higher bandwidth with very little interference. This property is used in cellular telephony applications, with a technique known as code division multiplexing (CDM) or code division multiple access (CDMA).

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:

  • CN(i) is orthogonal to all other rows of CN.
  • CN(i) is not orthogonal to a row on the same path of the tree as itself.

  • CN(i) is orthogonal to all other rows.

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


Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.