Orthogonal Codes in CDMA:

Generation and Simulation

Introduction

CDMA (Code Division Multiple Access) is a communication technique that allows multiple users to communicate simultaneously over one frequency. This is achieved through the use of spreading codes, whereby a single data bit is "spread" over a longer sequence of transmitted bits. These codes, known as chip sequences, must be carefully chosen so that the data may be correctly "despread" at the receiver. Such codes are known as orthogonal codes.

This document introduces some fundamentals of CDMA, necessary for understanding of the subsequent material. It discusses some of the issues involved, then describes the appended C programs as guides to generating orthogonal codes, and simulating the coding/decoding procedure.

CDMA Basics

Each user is assigned a chip sequence. This is simply a sequence of bits (chips). The spreading process is shown below, using an example:

 1  0  1  1  0  0

 1 -1  1  1 -1 -1

 1 -1  1  1 -1 -1

-1  1 -1 -1  1  1

 0  0  0  0  0  0

In its simplest form, decoding involves calculating the dot product of the received bit stream with one user’s spreading sequence. Note that when signals arrive at the receiver from different users, they linearly add. See the example below.

Length of chip sequences = n = 4

-1 +1 -1 +1

+1 -1 +1 -1

+1 +1 -1  0

+1 +1 -1 -1

-1 -1  1  0

 0  0  0  0

 2  0  0 -2

Thus all transmitted data has been recovered.

Investigation

The above method makes two key assumptions: code synchronization and chip synchronization. Code synch indicates that the transmitted sequences from each user begin at the same time. Chip synch implies that all users transmit a chip (bit) at the same time. In a realistic CDMA system, neither assumption is valid.

Definition of Practical Orthogonality

Ultimately, the chip sequences must be orthogonal for correct transmission/reception. What is orthogonality? Mathematically speaking, if we have n users and n-bit chip sequences, then a set of vectors in n-space are orthogonal if any point in n-space may be expressed as only one linear combination of these vectors. In a more practical sense, vectors are orthogonal if they allow correct decoding of transmitted data. This definition may sound contrived at first, and slower to calculate, but its usefulness will become apparent later as we investigate chip synchronization issues.

Here is a C program that tests for practical orthogonality. Near the top of the file, the number of users, code lengths, and actual codes are entered. Then compile the program and run it to see if the codes are orthogonal. When testing, it uses the idea that each user has three transmission possibilities: logic high, logic low, and no transmission. All possible combinations are tried.

Code Synchronization

In this section, we will investigate chip sequences that are orthogonal regardless of code asynchrony. The key idea is to use codes that are longer than n bits (for n users). This "wasted" bandwidth will solve code synchronization problems, thus negating the need for other solutions (such as a high-power synch carrier).

The test for orthogonality despite code synchronization issues is very similar to the basic orthogonality test. However, for every transmission combination, each code must be rotated in all possibilities relative to each other. So for 4-user, 8-bit codes, this program will take 8⁴=4096 times as long as the previous program. However, the run time is still acceptable.

The steps for configuring this program are identical to those above: set the number of users and code length, then the chip sequences.

Finding Suitable Codes

Another program finds a set of chip sequences that solve the code synchronization problem above. To configure, simply choose the desired number of users. Upon initialization, the program begins to try all possible codes, determining orthogonality by the same criteria as above. It begins with codes of length n (the number of users), and if necessary, increments the code length until a solution is found. If one solution is found for a particular code length, all solutions of that code length are generated and output before the program finishes.

Unfortunately, due to the number of possible codes, this program is too slow for actual use. Significant optimization (i.e. identifying and pruning combinations that cannot work, rather than trying all possibilities) would be necessary for this program to be useful. However, it was written, and is presented here should anyone find a use for it. Note that this program is written in C++ (almost pure C, but variables are defined anywhere, not just at the top of functions). This was done to make the program easier to understand.

Chip Synchronization

We will not be developing a program to solve chip synchronization issues. Unlike the code asynchrony problem, which had a discrete (and finite) number of possibilities, the number of ways in which bits may be unsynchronized is infinite. Therefore, this program will be a simulation.

To solve the chip synchronization issue, supersampling is used. That is, rather than sample the received waveform once per bit period, multiple samples are taken during the same period. A supersampling value of 4, for example, should provide enough extra resolution to handle all cases (i.e. sampling on a bit transition). The purpose of the simulation is to determine how accurately the transmitted signals can be decoded.

This program simulates the CDMA transmission and decoding process. It requires an input file that specifies the transmission sequence. Here is a sample input file. See the comments at the top of the program file for more details. This program creates a set of files for every station being simulated. These results are intended to be viewed with gnuplot, a freeware plotting program. If running in a unix environment, with the sample input file given above, use the following command line: simul1 simul1.in app This will produce the following files:

To start gnuplot, simple type gnuplot. To view the results of the first station from within gnuplot, type load "app0.comm" (this command, as well as all that follow, can easily be extended for any particular station). This will graph the results of the simulation, considering the decoded data for the first chip sequence. The following three series are produced:

1. "User X Data" - indicates the correct value that should be received for this user. It stays at this value for the first four samples (i.e. throughout the first chip in the sequence) and drops to -50 elsewhere to indicate where the sequence should NOT be despread correctly at these times. The received value, (-1, 0, or +1), is multiplied by 32 for easy comparison with other series.
2. "User X Dot Prod" - is the dot product with taking one sample during each over-sampling period (this is the method actually used for this project). So the dot product vectors will be as wide as the chip sequences. This result is multiplied but the over-sampling rate (4) for easy comparison.
3. "User X DP Quad Sum" - this is the result of adding four adjacent dot products, each calculated as above for the second series. In effect, this averages the dot product values. This series is just for comparison.

The ideal case shows all three plots having the same value when the data graph is not -50 (this is when the incoming samples should be decoded). In other words, correlation is highest at these points and is lower elsewhere. A sample plot is shown below: Click here for the original Postscript file.

To generate a postscript file for a particular plot, use the following sequence of gnuplot commands:

set terminal postscript
set output "app0.ps"
load "app0.comm"