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:
Chip Sequence: 
1 0 1 1 0 0 
Spreading Sequence: 
1 1 1 1 1 1 
Transmitted bits, data = 1: 
1 1 1 1 1 1 
Transmitted bits, data = 0: 
1 1 1 1 1 1 
No transmission: 
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
Station 
Spreading Sequence 
Data 
Transmitted Sequence 
Dot Product 
DP / n 
A 

Low 

4 
1 
B 

High 

+4 
1 
C 

N/T 

0 
0 
Received: 

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 nbit chip sequences, then a set of vectors in nspace are orthogonal if any point in nspace 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 highpower 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 4user, 8bit codes, this program will take 8^{4}=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:
app0.comm  app0.data 
app1.comm  app1.data 
app2.comm  app2.data 
app3.comm  app3.data 
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:
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"