Code Division Multiple Access (CDMA) is a method for multiplexing signals that assigns each communication channel a unique code created by a pseudorandom generator. Here's a simple example showing how it works:
Say we have 3 channels as shown in the table below (zeros encoded as negative voltage, ones as positive voltage):
Channel Channel Code Data to be sent ------------------------------------------ 1 (-1,-1,-1,-1) 110 = (+1,+1,-1) 2 (-1,+1,-1,+1) 010 = (-1,+1,-1) 3 (-1,-1,+1,+1) 001 = (-1,-1,+1)
Each bit of data is multiplied by its corresponding channel code:
Channel 1 (110): (+1)(-1,-1,-1,-1), (+1)(-1,-1,-1,-1), (-1)(-1,-1,-1,-1) = (-1,-1,-1,-1), (-1,-1,-1,-1), (+1,+1,+1,+1) Channel 2 (010): (-1)(-1,+1,-1,+1), (+1)(-1,+1,-1,+1), (-1)(-1,+1,-1,+1) = (+1,-1,+1,-1), (-1,+1,-1,+1), (+1,-1,+1,-1) Channel 3 (001): (-1)(-1,-1,+1,+1), (-1)(-1,-1,+1,+1), (+1)(-1,-1,+1,+1) = (+1,+1,-1,-1), (+1,+1,-1,-1), (-1,-1,+1,+1)
Then the coded signals are summed together (multiplexing stage):
| | | | | | | | | | ------------- | | |+1|+1|+1|+1| Channel 1 ------------------------------------------- |-1|-1|-1|-1|-1|-1|-1|-1| | ------------------------- | | | | | | | | | ---- ---- | ---- ------- ---- | |+1| |+1| | |+1| |+1|+1| |+1| | Channel 2 ------------------------------------------- | |-1| |-1|-1| |-1| | |-1| |-1| | ---- ------- ---- | ---- ---- | | | | | | | | ------- ------- ------- | |+1|+1| |+1|+1| |+1|+1| | Channel 3 ------------------------------------------- | |-1|-1| |-1|-1| |-1|-1| | ------- ------- ------- | | | | | | | | | | | ---- | | | | | | | ---- | ---- ---- | |--- |+1| | |+1| |+1| |+3|+1| Sum signal ------------------------------------------- | |-1|-1|-3|-1| |-3|-1| |-1| | | ------| |--- | |--- ---- | | | | | | | | | ---- ---- | |
The sum signal is what is transmitted to the receiver. On the receiving end, say we want to extract the data from Channel 2 (demultiplexing stage). The receiver multiplies the sum signal by the Channel 2 code signal to obtain a signal correlated to the data sent on Channel 2, and then the final result is integrated to obtain the actual data bits:
| | | ---- | | | | | | | ---- | ---- ---- | |--- |+1| | |+1| |+1| |+3|+1| Sum signal ------------------------------------------- | |-1|-1|-3|-1| |-3|-1| |-1| | | ------| |--- | |--- ---- | | | | | | | | | ---- ---- | | | | | | | | | | | ---- ---- ---- ---- ---- ---- | |+1| |+1| |+1| |+1| |+1| |+1| Channel 2 ------------------------------------------- sequence |-1| |-1| |-1| |-1| |-1| |-1| | ---- ---- ---- ---- ---- ---- | | | | | | | | | | | ---- | | | | | | | | | ---- ------| | | ---- | |+1| |+1|+1|+3| | |+1| Correlator ------------------------------------------- output |-1|-1| |-3| |-1|-1|-1|-3| | ------- | | ---------| | | | | | | | | | | ---- | ---- | | | *** | | | | ** *|+4 | | | *** | | | |** | | Integrator ---*-----------*-----------*--------------- output |* ** | |** | | *** ** | | *** | | ** | | ** | | *|-4 | ****|-4 | | | |
So, (-4,+4,-4) = 010, which was the data sent on Channel 2!
In CDMA, when a device wants to transmit a packet of data it does so immediately, rather than first checking to see if the network is busy (i.e. there is another transmission in progress).
Device "a" transmits a packet of data. As it transmits, it "listens" to the network to ensure that what it hears is its own data packet. If another device "b" is transmitting data at the same time as device "a", as device "a" listens to the network it will here device "b"'s transmission interfering with its own. In this manner, a simultaneous use of the network, or a "collision", can be detected.
Because device "a" must detect the collision while it is still transmitting its packet, the signal from device "b" must be received before device "a" has finished its transmission. Therefore, the size of a packet that can be sent is restricted such that the time it takes to transmit the packet is less than or equal to the time it will take the signal from device "b" to reach device "a". Thus, even as device "a" sends the end of its packet it will detect the interference from the beginning of device "b"'s packet while the transmission is still in progress.
As such, in a CDMA network, the maximum size of a data packet is the transmission rate (bits per second) times the signal propogation delay (roughly the speed of light (C) times the length of the cable) when the distance on the network between any two devices is the maximum distance allowed.
When a collision occurs, all of the colliding packets must be re-sent. However, if both device "a" and "b" attempted to retransmit their packets in the same instant, the collision would simply repeat. In order to avoid this problem, each device randomly selects a time slice from a window of time that is two time slices long (the length of the time slice is the transmission time for a packet). Hopefuly, the collision will not reoccur, however because both devices may randomly choose the same time slice for retransmission, each device will continue to retry the transmission, doubling the number of time slices in the window each time, until there are 32768 time slices in the window. If the packets are still colliding, the transmission is abandoned.
------------ editor's note:CDMA is referenced here as the generic term for Collision-Detect Multi-Access busses, not in the specific communications usage. Reference:http://classes.engr.oregonstate.edu/eecs/fall2003/ece441/groups/g11/JoshWhitePaper.htmliceowl: 2/11/03
CDMA stands for Code Division Multiple Access. Multiple Access schemes are used to allow multiple senders to use one medium, such as one network cable/ring or a band of frequencies.
CDMA is also used as a name for IS-95 and IS-2000 cell phone networks.
TDMA (Time Division Multiple Access) works very simply by allowing each sender a time slot to send its information. A simple implementation would allow each sender in turn to send for one second and then wait n-1 seconds, where n is the total number of senders competing for access to the medium.
FDMA (Frequency Division Multiple Access) is how radio stations share the FM band; each station has its own frequency.
CDMA is different from these two, as all senders broadcast on the same frequency, all at the same time!
The trick is that in stead of sending a 0 or 1 each sender is assigned a special code, known as its spreading code or chip sequence. Unlike a previous write-up stated, these are not truly pseudo random, there is a method to this madness, known as the Walsh Matrix.
In a Walsh Matrix the dot product of each two rows is zero. Using the example from the previous writeup;
channel code ----------------------- 1 (-1,-1,-1,-1) 2 (-1,+1,-1,+1) 3 (-1,-1,+1,+1)
Let's calculate the dot product of code 1 and 2
-1*-1 = +1 -1*+1 = -1 -1*-1 = +1 -1*+1 = -1 ---+ 0
The same holds for the dot products of every combination of different codes. But when you generate the dot product of a single code the answer is one! Generating Walsh codes is left as an exercise for the user.
If sender 1 wants to transmit a 1, (-1,-1,-1,-1) is broadcast, is sender 1 wants to transmit a 0 (+1,+1,+1,+1) is broadcast. In the ether, these amplitude modulations simply add up.
If sender 1 now sends a 1 and everyone else sends a 0 the following happens in the ether:
1 (-1,-1,-1,-1) 2 (+1,-1,+1,-1) 3 (+1,+1,-1,-1) -------------+ (+1,-1,-1,-3)
We know there are 3 stations sending, and we want to know what the first station is sending. So we calculate the dot product of the first station's code (-1,-1,-1,-1) and the received signales (+1,-1,-1,-3) the answer is.. 1 !
Had (+1,+1,+1,+1) been sent, the received value would have been (+3,+1,+1,-1); the dot product of that value with (-1,-1,-1,-1) is -1, which stands for a digital zero.
If station one didn't transmit at all, the received value would have been (+2,0,0,-2), with a dot product with (-1,-1,-1,-1) of zero (which signifies silence).
How to calculate the dot products of these simple matrices; simply multiply the nth element in one matrix with the nth element in the other matrix, sum these all up, and divide by the number of elements. e.g. (-1,-1,-1,-1) . (+3,+1,+1,-1) = ((-1*+3) + (-1*+1) + (-1*+1) + (-1*-1))/4 = -4/4 = -1.
The dot product is all you need to know to understand the basics of CDMA!!
The devil is in the details in implementing CDMA. To work succesfully, each station must start transmitting its code/chip sequence at the exact same time as all other broadcasting stations.
Furthermore, each sender's signal MUST be the same strength (i.e. +1 and -1 and not +0.5 and -0.5 whilst a neighbor transmits +0.8 and -0.8) at the RECEIVER. In cell phone networks this is done by having a tight control loop between the CDMA handsets and the base station, to calibrate the signal continually.
To join the network, a handset must also request a chip sequence from the network to use. In cellular mobile phone networks logging on to the network is often done by having a special set of 'bootstrapping' frequencies, where stations can announce their presence; these frequencies usually operate using some sort of slotted Aloha.
The number of simultanious users on a CDMA network is not infinite, just like the number of users on a TDMA network is not infinite, even though we can split up time in infinitely small pieces, there will always be a limiting factor. Still CDMA seems to be very succesful, and lies at the heart of the new UMTS standard that will be used in Europe for 3G networks. (The US 3G standard is of course slightly different from the European one).
Ci·Cj = 0 for i ≠ j
It isn't very difficult to come up with codes that satisfy this property. For example, let m = n = 3. At this point we are just looking for a basis for R3; an obvious choice is
T1 = i = (1, 0, 0) T2 = j = (0, 1, 0) T3 = k = (0, 0, 1)
So what kind of code is this? We see that only T1 has a non-zero first component, only T2 has a non-zero second component, and so on. In physical terms, that means that only the user assigned to Ti gets to transmit in the ith `time slot'. But that is just TDMA; TDMA is therefore a special case of CDMA.
Alternately, we might remember from a class on Fourier transforms that
1 / | cos(2πit) cos(2πjt) dt = 0 , i ≠ j / 0
n-1 --- \ cos(2πi (k/n)) cos(2πj (k/n)) ≈ 0 , i ≠ j /-- k=0
cos(2πa ((k-1)/n))
In practice we can come up with much better codes than these. Otherwise there wouldn't be much point to the way that CDMA is typically implemented, which involves huge amounts of digital signal processing. However, the math behind CDMA holds for any multiple-access system in which the receivers correlate the received signal against the `reference waveforms', and that is almost any practical multiple-access scheme.
Actually it should be obvious that everyone is glossing over a lot of details here. We are dealing entirely with vectors of real numbers, and it is not possible to connect n real numbers to an antenna. Electromagnetic fields are described as functions of time, not vectors in Rn. It turns out that it is possible to define a vector space of functions. Then we can map our vectors in Rn into signals that can be sent over the air, and everything in this node becomes useful and rigorous.
Further confusing things, Qualcomm has a set of standards with CDMA in the name (like CDMA2000, also known as 1x). These don't just specify the modulation scheme; they specify everything, including stuff like how long a phone number can be. They do, of course, use CDMA for the modulation.
printable version chaos
Everything2 Help
