Multiple access communication

How can so many people use their phones at the same time, in the same place, on the same air, and still hear each other? This section answers that question, using the orthogonality developed in the previous section.

Early multiuser communication went to great lengths to give every pair of users a dedicated link. Cities were blanketed with webs of wire, one pair per conversation. Wireless communication removed the wires, but it did not remove the underlying problem: the air is one shared medium, and everybody is using it at once.

Wireless communication uses the radio spectrum, the electromagnetic waves from about $3$ kHz to $300$ GHz. By modulating signals at different frequencies and separating them again with the filters of the previous section, several users can transmit simultaneously. To keep users from interfering, the Federal Communications Commission sells licences that grant a buyer exclusive use of a band. In the United States the spectrum is auctioned, and the sums involved are large: in the 2019 auctions for the $24$ GHz and $28$ GHz bands, AT&T bid over $982 million, T-Mobile over $803 million, Verizon $506 million, and US Cellular $127 million. (Sources: the FCC auction results and Ars Technica. If you want to see how crowded the spectrum is, the NTIA publishes a wall chart of every allocation from $3$ kHz to $300$ GHz.)

Which raises the obvious question: if spectrum is that expensive, giving every individual user a private band of their own is enormously wasteful. Most users are silent most of the time, and a band sitting idle earns nothing. The rest of this section is about the alternatives.

Before reading on: a licensed band is exclusive, so nobody else may transmit in it even when its owner is idle. Roughly what fraction of the time do you think your own phone is actually transmitting?

Cellular networks

Before modern cellular networks, mobile radio was largely uncoordinated: as users moved, their transmissions could collide with others using the same channel. Cellular networking fixed this by dividing a region into cells, each with a base station responsible for the users inside it. Depending on how dense the users are, a cell may be many kilometres across or only a few hundred metres. Base stations hand users off from one cell to the next as they move, which means a frequency range can be reused in another cell far enough away not to interfere.

1G. The analog Advanced Mobile Phone System was deployed in the US in 1983. It gave each user in a cell a dedicated frequency band, a scheme called Frequency Division Multiple Access (FDMA). The FCC allocated about $25$ MHz each way, which at roughly $30$ kHz per channel allowed up to $832$ channels. The approach does not scale: more users means more channels means more bandwidth, and there is no more bandwidth.

2G. Analog transmission was bandwidth hungry, largely limited to speech, and unencrypted. Digital transmission brought two new ways to share: Time Division Multiple Access (TDMA), which gives each user brief time slots, and Code Division Multiple Access (CDMA), which gives each user a code. 2G made digital media over a cellular network possible — text messages, ringtones, and data — and with it the smartphone.

3G. Speed came from using bandwidth more efficiently. Where 2G used circuit-switching, in which all the information in a signal travels together along one path, 3G introduced packet-switching for data, in which the information is cut into packets that travel separately and possibly by different routes. Minimum speeds rose to $2$ Mbps for stationary users and $384$ kbps in a moving vehicle. Packet switching was used only for data at this stage, so that voice calls stayed compatible with 2G.

4G. Moving everything, voice included, to packet-switching made 4G networks look like the internet: users have addresses, the network routes, and data rates improved roughly tenfold. The Long-Term Evolution (LTE) standard coordinated this development through the 3rd Generation Partnership Project.

5G. The current generation pushes into higher frequencies, $24$ to $100$ GHz, which are less crowded and offer more bandwidth but travel shorter distances. Shorter range means smaller cells, which is a cost in rural areas and an advantage in dense ones. Higher frequencies also need smaller antennas, so more of them fit, which raises data rates further.

Time Division Multiple Access

The idea is to let several users share one channel by giving each a slice of time during which only that user may transmit.

Each base station tracks requests for transmit and receive time and prioritises them by type, voice calls before data, balancing the allocation so that one user’s heavy usage does not make everyone else wait. (This is why networks throttle excessive usage.) The base station does not physically control when handsets transmit; users are responsible for honouring the slots they are given.

Frequency Division Multiple Access

Instead of slicing time, a base station can assign users non-overlapping ranges of frequency, and let them all transmit continuously within their own range.

A fixed assignment is wasteful for the same reason a licensed band is: users move and their needs change. So modern FDMA is really a hybrid, assigning users blocks in both time and frequency at once. This is the norm in 2G TDMA/FDMA networks such as GSM.

Both schemes are orthogonality

TDMA and FDMA look like different engineering ideas, but mathematically they are the same idea, and it is the one from the previous section. In TDMA no two users are transmitting a nonzero signal at the same instant, so their signals are orthogonal because they never overlap in time. In FDMA no two users occupy the same frequency, so their signals are orthogonal because they are built from disjoint sets of complex exponentials. A hybrid time-frequency assignment is orthogonal for both reasons at once.

Is separating the users the only way to get orthogonality? No — and the alternative is what the rest of this section is about.

Code Division Multiple Access

Code Division Multiple Access separates users by giving each an orthogonal code, without slicing time or frequency at all. Every user has access to all frequencies, all of the time.

Each user multiplies their data by their own code, and the receiver, knowing which code it is looking for, extracts that user’s data and cancels everything else. This is what requires the codes to be mutually orthogonal: multiplying the received signal by one user’s code zeroes out the contribution of every other user exactly.

Concretely, a user starts with a low-bandwidth data signal and multiplies it by a much faster spreading code. The result occupies a wide band — hence the name spread spectrum — but that same band can be reused simultaneously by every other user with a different code. The number of concurrent users is therefore not limited directly by the bandwidth, but by the number of orthogonal codes available, which we saw is the code length $N$.

Because each user transmits continuously and uses the whole channel, CDMA does not make anyone wait for a slot, which lowers latency, and it degrades gracefully when channel conditions vary.

Sending and receiving

Suppose the code length is $N$. User A has a codeword $a$, a vector of $N$ entries each $\pm 1$, and user B has codeword $b$, chosen so that $\langle a,b\rangle = 0$.

To send a $1$, user A transmits $a$; to send a $0$, she transmits $-a$. User B does the same with $b$. Writing $m_A, m_B \in {+1,-1}$ for the two bits, the receiver sees the sum

\[s = m_A a + m_B b.\]

Decoding for A is a single inner product:

\[\langle a, s\rangle = \langle a, m_A a\rangle + \langle a, m_B b\rangle = m_A \langle a,a\rangle + m_B \langle a,b\rangle = m_A N,\]

since $\langle a,b\rangle = 0$ and $\langle a,a\rangle = N$ for a $\pm 1$ vector of length $N$. Dividing by $N$ recovers $m_A$. Decoding for B works the same way with $b$. If there are three or more users whose codewords are pairwise orthogonal, the computation is unchanged: every term but one vanishes.

Four users transmit simultaneously with the codewords $$a = (+1,+1,+1,+1),\quad b = (-1,+1,+1,-1),\quad c = (+1,-1,+1,-1),\quad d = (+1,+1,-1,-1).$$ The received signal is $s = (+2,+2,-2,+2)$. What did each user send?

With the same four codewords, the receiver instead sees $s' = (+2,0,-2,0)$. Decoding now gives $\langle a,s'\rangle = 0$ and $\langle c,s'\rangle = 0$, which is neither $+N$ nor $-N$. What has happened?

CDMA and noise

Real channels add noise, so the receiver does not see a clean combination of codewords. With a noise vector $n$,

\[s = m_A a + m_B b + n,\]

and decoding for A now gives

\[\langle a, s\rangle = m_A N + m_B \langle a,b\rangle + \langle a, n\rangle = m_A N + \langle a, n\rangle.\]

The other users still cancel exactly. What is left is the true signal $m_A N$ plus one unwanted term, $\langle a,n\rangle$. CDMA works whenever that term is small compared with $N$.

The key point is that noise is random and unrelated to the code, so the inner product $\langle a, n\rangle$ tends to be small: the positive and negative contributions cancel. Let us make that precise using expectation and variance.

Assume the noise in each interval has mean zero and that the intervals are independent. Then, using linearity of expectation and the fact that the $a_i$ are constants,

\[E\big[\langle a,n\rangle\big] = E\left[\sum_{i=1}^{N} a_i n_i\right] = \sum_{i=1}^{N} a_i\, E[n_i] = 0.\]

So on average the noise term contributes nothing. How far from zero does it stray? For that we need the variance. Suppose each $n_i$ takes the values $-M$, $0$ and $+M$ with probabilities $p/2$, $1-p$ and $p/2$:

\[n_{i} = \begin{cases} -M & \text{with probability } p/2, \\ 0 & \text{with probability } 1 - p, \\ +M & \text{with probability } p/2. \end{cases}\]

Its mean is zero, so its variance is $\operatorname{Var}(n_i) = E[n_i^2] = \frac{p}{2}M^2 + \frac{p}{2}M^2 = pM^2$. Since the $n_i$ are independent and each $a_i^2 = 1$,

\[\operatorname{Var}\big(\langle a,n\rangle\big) = \operatorname{Var}\left(\sum_{i=1}^{N} a_i n_i\right) = \sum_{i=1}^{N} a_i^{2}\operatorname{Var}(n_i) = N p M^{2},\]

so the standard deviation of the noise term is $M\sqrt{Np}$.

Now compare the two quantities. The signal we are trying to detect has size $N$. The noise term has standard deviation proportional to $\sqrt{N}$. A random quantity is rarely many standard deviations away from its mean — at least $99\%$ of the probability lies within ten of them — so with high probability the noise term is at most about $10M\sqrt{Np}$, while the signal is $N$. The ratio

\[\frac{10M\sqrt{Np}}{N} = \frac{10M\sqrt{p}}{\sqrt{N}}\]

shrinks as $N$ grows, no matter how large $M$ is.

The signal grows like $N$ and the noise like $\sqrt{N}$. By making the code long
enough, CDMA can recover a message even when the noise in every single interval is
far larger than the signal in that interval.

This is why a CDMA transmission can sit below the noise floor and still be decoded: a receiver that does not know the code sees nothing but noise, and one that does know it recovers the message.

The statement that at least $99\%$ of the probability lies within ten standard deviations of the mean is Chebyshev's inequality: for any random variable $X$ with mean $\mu$ and standard deviation $\sigma$, and any $k > 0$, $P(\vert X - \mu\vert \geq k\sigma) \leq 1/k^{2}$. It says nothing about the shape of the distribution, which is what makes it usable here: we assumed very little about the noise.

Two users have the length-$10$ codewords $$a = (+1,+1,+1,+1,+1,+1,+1,+1,+1,+1), \qquad b = (-1,-1,-1,-1,-1,+1,+1,+1,+1,+1),$$ and the received signal is $s = (1,3,3,0,0,0,2,-1,0,-1)$. What did each user send, and what was the noise?

In the exercise above, what is the largest the noise term $\langle a,n\rangle$ could have been before user A's bit was decoded incorrectly?

Spreading a signal in practice

The examples above send one bit per codeword. In a real system the message is a stream of bits, and each bit is multiplied by a whole period of the spreading code. Because the code changes much faster than the data, the product occupies a far wider band than the data alone.

To recover the message, the receiver multiplies the incoming wideband signal by the same spreading code again. Where the code matches, each chip is multiplied by $(\pm 1)^2 = +1$, so the code cancels itself and the original slow data signal reappears; averaging over one period of the code gives back the bit.

If instead the receiver multiplies by a different code, orthogonal to the one that was used, the products no longer agree. Over one period the decoded chips are as often $+1$ as $-1$, and averaging them gives zero — which is exactly the statement $\langle a,b\rangle = 0$ seen one interval at a time.

Two groups agree on the codes $c_A = (-1,-1,+1,+1)$ and $c_B = (-1,+1,-1,+1)$ and transmit at the same time; noise is added on the way. Over seven code periods the receiver sees $$0,1,-1,4 \mid 3,1,-1,-4 \mid 2,1,1,-1 \mid -3,-1,-3,1 \mid 2,0,-2,3 \mid -1,-4,2,1 \mid 0,1,-1,1.$$ Decode group B's seven bits by multiplying each block by $c_B$ and averaging.