Stardate 20020410.2115

(Captain's log): Someone just found my CDMA FAQ (which happens quite often) and wrote to me and asked, "But how does CDMA actually work so that several people can simultaneously use the same frequency and actually have their transmitters on at once without anyone getting confused?"

I wrote a shorter answer to him, but it got me inspired and I decided to write up a longer explanation. So if you're not curious you may as well not read further. Otherwise, here we go:

It's kind of tricky. Let's break it down a bit and simplify things some; we'll start by ignoring the short and long codes entirely and just talk about the Walsh codes, and we'll shorten those to 8 chips. And we'll talk about the forward link (from cell to phone) and we'll assume temporarily that the speed of light is infinite (so there's no phase delay).

All the Walsh codes are orthogonal which means that if you XOR different ones, the result will be half ones and half zeros. But if you XOR one with itself, you get all 0's. This is critical and it's what makes the whole system work.

So there's users Alice and Betty and Charlie. Alice's Walsh code is 11110000. Betty's is 11001100. Charlie's is 10101010. 11110000 xor 11110000 is all zeros, a match. But 11110000 xor 11001100 is 00111100, and 11110000 xor 10101010 is 01011010. In each case, half ones and half zeros. (The pattern of 1's and 0's doesn't matter, as you'll see. What's important is how many of each there are.)

Alice's receiver runs an accumulator, and it adds for each match (each 0) and subtracts for each non-match (each 1). This requires us to differentiate between chips and bits. A chip is part of a bit. The cell system sends chips at a rate of 1.2288 MHz, but it takes a lot of chips to transmit one bit. Each chip contains a little piece of the information about each bit (hence the name). Right now in most CDMA systems the bit rate per phone is only 9600 per second in voice calls; the rest run 14400 per second. So there are a huge number of chips per bit.

What happens is that all the chips are checked and each one votes on what the bits should be. The majority rule. So if the cell wants to send a bit of 1 to Alice, it transmits a chip pattern of 11110000. Alice sees eight matches to her spreading code, which adds eight votes for "1", and interprets it as a bit of 1. Betty, on the other hand, sees four matches and four non-matches and doesn't interpret it as anything.

When the cell wants to send a "0" to Alice, it transmits 00001111. Alice sees eight non-matches, which adds eight votes for "0". Again, Betty sees four matches and four non-matches and doesn't see anything.

But what if the cell wants to send to both at the same time? The reason that works is that what the cell is sending is actually analog, not digital. It's the sum of all the digital chipstreams. So suppose that it wants to send bits of 1 to both Alice and to Betty. At this point it's better to think of them as being 1's and -1's instead of 1's and 0's. Here's how it works:

That sum is what the cell actually transmits. Alice receives the signal and interprets it as follows:

You get a multiply down and an add across. So the total energy is 8, which Alice interprets as a strongly positive signal as a bit value of "1".

Betty receives the signal and interprets it this way:

The sum is still 8 (though in a sense it's a different 8) and Betty also interprets that as a "1".

Now suppose that the system wants to send a "1" to Alice but a "0" to Betty. To do that, it sends Alice's code normally but Betty's code inverted. Here's how it comes out:

Alice interprets it as follows:

The sum is still eight, which is still interpreted as a "1". But Betty interprets it entirely differently:

And the sum is minus eight which is interpreted as a bit of "0". So Alice sees a "1" and Betty sees a "0", which is what the cell wanted to say to each of them.

Now let's add Charlie. We'll send a 1 to Alice, a 1 to Betty, and a 0 to Charlie:

Alice sees:

The sum is 8, which is interpreted as a "1". The reason this works is that all the values which were added in representing Alice's signal added together, but all the signals for Betty and Charlie cancelled because of half-match-half-nonmatch to Alice's spreading code. Betty sees:

Again, the sum is 8 so Betty also interprets it as "1". But note that though Betty got the same answer, she got it by an entirely different set of patterns. On the other hand, Charlie sees:

And the sum is minus 8 which Charlie interprets as a "0". Each of the three got a couple of chips which voted the wrong way (and it was different chips in each case), but more chips did vote the right way and some of those voted more strongly. It is the consensus which matters, not the pattern or the value interpreted from each individual chip.

So the exact same chipstream can be manipulated so that it will be interpreted correctly by each receiver, and what each receiver gets is completely independent of what any other receives. And the reason is that every receiver has a different spreading code, and every spreading code is orthogonal to every other spreading code.

That is a simplified version of how CDMA works. The actual system is massively more complicated because it has to deal with such things as phase delay (the chips being sent to different guys won't be synchronized with each other because the speed of light is not infinite and they may be different distances from the tower) and power control (the summing process on transmit doesn't actually weight each guy evenly) and a number of other things. In actual execution, to make it work is fantastically complicated. The actual Walsh codes are 64 chips long and there are actually 64 different ones (all of which are mutually orthogonal), and to make it all work there is also the Short Code (which is used to differentiate neighboring cells so that they can use the same frequency at the same time) and the Long Code (which is needed among other reasons to make phase delays due to distance work correctly without confusing anyone). And just to make things even more complicated, the data bits are actually passed through a forward-error-correction encoder before being transmitted, so that in actual practice each data bit is being represented in part by tens of thousands of chips each of which contains information about many data bits simultaneously. And there are also multiple fingers on the rake receiver (what was described above was how a single "finger" works) which permits the phone to receive multipath from the same cell or receive signals simultaneously from more than one cell (which is known as "soft handoff"). And the cell can actually be sending to as many as 30 phones at once. Then you toss in variable-rate codecs and realize that it isn't always sending the same number of bits to each phone. But all those things are just enhancements on this basic principle. What I just described is the basic principle that makes the whole thing work.

I might mention that the process of going the other way, with many phones transmitting and the cell trying to figure it out, is similar but not identical.

What's important is that it is indeed possible for many people to use the same frequency at once and to be transmitting at once without anyone getting confused. It's the orthogonal spreading patterns that make it work.

Update 20040402: Two years on, it is clear that readers were more bewildered by the above explanation than enlightened by it. Rather than giving them an "Aha!" moment as I hped, it seems to have convinced most that it was beyond them. I finally came up with a different way to explain what is going on, using a visual example as an analogy. You can see it here.

My new blog: Chizumatic