Orthogonality

We met orthogonality in Vectors and spaces: two vectors are orthogonal when their inner product is zero. There it was a geometric fact about arrows in space, and a tool for building error-correcting codes. Here we put it to a different use.

The question this section answers is the one the frequency domain kept raising: if everyone in a city transmits at once, on the same air, why does anyone hear anything? The answer is that the signals are arranged to be orthogonal to each other, and that orthogonality lets a receiver pull out the one signal it wants and cancel all the rest exactly. Three quite different-looking schemes — separating users in time, in frequency, or by code — turn out to be three ways of achieving the same condition.

Signals are vectors

Nothing new is needed to talk about orthogonal signals, because a signal already is a vector.

A discrete signal of length $N$, say $x = (x_1, x_2, \dotsc, x_N)$, is literally an element of $\mathbb{R}^N$, and its inner product with another such signal is the familiar sum

\[\langle x, y\rangle = \sum_{n=1}^{N} x_n y_n.\]

For a signal defined on a continuous time interval $[0,T]$ the sum becomes an integral. Chop $[0,T]$ into $N$ small pieces of width $\Delta t = T/N$, sample each signal once per piece, and form the sum $\sum_n x(t_n) y(t_n) \Delta t$; as the pieces shrink this tends to

\[\langle x, y\rangle = \int_0^{T} x(t)\, y^{*}(t)\, dt,\]

where the complex conjugate on $y$ is there so that $\langle x, x\rangle$ is a non-negative real number even when the signals are complex, exactly as it is for complex vectors.

Two signals are orthogonal when $\langle x, y\rangle = 0$.

Everything proved about inner products in Vectors and spaces carries over unchanged, because nothing in those proofs used the fact that the vectors had finitely many entries. In particular $|x|^2 = \langle x,x\rangle$ measures the energy of the signal, and the inner product is additive in each argument, $\langle x, y + z\rangle = \langle x,y\rangle + \langle x,z\rangle$. One small caution about scalars: because of the conjugate, a scalar comes out of the first argument as itself and out of the second argument conjugated, $\langle \alpha x, y\rangle = \alpha \langle x,y\rangle$ but $\langle x, \beta y\rangle = \beta^{*} \langle x,y\rangle$. For real signals the conjugate does nothing and this is the familiar rule.

Complex exponentials at different frequencies are orthogonal

The first and most important example is one we have been relying on since Frequency and spectrum without naming it.

Take two complex exponentials on the interval $[0,T]$ and compute their inner product. With $\Delta f = f_1 - f_2$,

\[\big\langle e^{i2\pi f_1 t},\, e^{i2\pi f_2 t}\big\rangle = \int_0^T e^{i2\pi f_1 t}\, e^{-i2\pi f_2 t}\, dt = \int_0^T e^{i2\pi \Delta f\, t}\, dt.\]

If $\Delta f = 0$ the integrand is $1$ and the integral is $T$. Otherwise we can integrate directly:

\[\int_0^T e^{i2\pi \Delta f\, t}\, dt = \left[\frac{e^{i2\pi \Delta f\, t}}{i2\pi \Delta f}\right]_0^T = \frac{e^{i2\pi \Delta f\, T} - 1}{i2\pi \Delta f},\]

which is zero exactly when $e^{i2\pi \Delta f T} = 1$, that is, when $\Delta f\, T$ is a nonzero integer.

On an interval of length $T$, the complex exponentials at the frequencies
$$f_k = \frac{k}{T}, \qquad k = 0, \pm 1, \pm 2, \dotsc$$
are mutually orthogonal: any two distinct ones differ in frequency by a nonzero
multiple of $1/T$.

This is the reason the frequency domain works at all. Writing a signal as a combination of these exponentials is writing a vector in terms of an orthogonal set, and finding the amount of frequency $f_k$ present is taking an inner product with $e^{i2\pi f_k t}$ — every other component contributes exactly zero and drops out. It is the same computation you would use to find the coordinates of a vector along a set of perpendicular axes.

Two musicians play steady tones for exactly one second, one at $440$ Hz and one at $441$ Hz. Are the two signals orthogonal over that second? What if the second musician plays $440.5$ Hz?

Three ways to be orthogonal

Two users sharing a channel send $x(t)$ and $y(t)$ at the same time, and the channel carries the sum. There are three natural ways to arrange for $\langle x,y\rangle = 0$.

Take turns (separate in time). If the two signals are never nonzero at the same instant — user A transmits only during her slots and is silent otherwise, and user B does the opposite — then the product $x(t)y^{*}(t)$ is zero at every $t$, so the integral is zero. This is the idea behind Time Division Multiple Access.

Use different bands (separate in frequency). Suppose A’s signal has all its frequency content in one band and B’s in another band that does not overlap. Each signal is a combination of the exponentials in its own band,

\[x(t) = \sum_{k \in \mathcal{A}} \alpha_k\, e^{i2\pi f_k t}, \qquad y(t) = \sum_{l \in \mathcal{B}} \beta_l\, e^{i2\pi f_l t},\]

with $\mathcal{A}$ and $\mathcal{B}$ disjoint. Expanding by the rules above, $\langle x,y\rangle$ is a sum of terms $\alpha_k \beta_l^{*} \langle e^{i2\pi f_k t}, e^{i2\pi f_l t}\rangle$, and every one of those is zero because $f_k \neq f_l$. So $\langle x,y\rangle = 0$: the two users are orthogonal. This is Frequency Division Multiple Access, and it is the orthogonality of complex exponentials wearing a different hat.

Overlap in both, and use codes. The two schemes above buy orthogonality by keeping the users apart. The third does not: both users transmit over the whole band, all of the time, and orthogonality comes from the pattern each one multiplies its data by. Because that pattern is a vector of $\pm 1$s, we are back to the finite- dimensional inner product, and the condition is simply that the two patterns have inner product zero. This is Code Division Multiple Access, and it is the subject of the next section.

Take the length-4 patterns $a = (+1,+1,+1,+1)$ and $b = (-1,+1,+1,-1)$. Are they orthogonal? What about $a$ and $c = (+1,-1,+1,-1)$, and $b$ and $c$?

Orthogonality is what makes the users separable, so it is natural to ask how many mutually orthogonal signals we can find. For patterns of length $N$ the answer is sharp, and it comes straight from linear algebra.

A set of nonzero, mutually orthogonal vectors is linearly independent. Consequently
there are at most $N$ mutually orthogonal nonzero vectors in an $N$-dimensional
space.

To see the first claim, suppose $c_1, \dotsc, c_k$ are nonzero and mutually orthogonal, and that some combination of them vanishes: $\alpha_1 c_1 + \dotsb + \alpha_k c_k = 0$. Take the inner product of both sides with $c_j$. Every term with $i \neq j$ contributes $\alpha_i \langle c_j, c_i\rangle = 0$, leaving

\[\alpha_j \langle c_j, c_j\rangle = 0.\]

Since $c_j \neq 0$ we have $\langle c_j,c_j\rangle = |c_j|^2 > 0$, so $\alpha_j = 0$. This holds for every $j$, so the only combination that vanishes is the trivial one, which is what linear independence means. The second claim then follows from the fact, established in Vectors and spaces, that an $N$-dimensional space contains at most $N$ linearly independent vectors.

So a code of length $N$ supports at most $N$ simultaneous users. Doubling the number of users means doubling the length of the codes, which means transmitting twice as fast — the bandwidth has to come from somewhere either way.

Can you find five mutually orthogonal nonzero vectors of length $4$? Try, and then explain what goes wrong.

Building an orthogonal set: Hadamard codes

Knowing that at most $N$ orthogonal patterns exist does not tell us how to find them. For lengths that are powers of two there is a simple recursive construction that produces the full $N$ of them at once.

Start with the $1 \times 1$ array $H_1 = \begin{pmatrix} +1 \end{pmatrix}$, and double the size at each step by placing four copies of the current array in a square, negating the last one:

\[H_{2m} = \begin{pmatrix} H_m & H_m \\ H_m & -H_m\end{pmatrix}.\]

The first two steps give

\[H_2 = \begin{pmatrix} +1 & +1 \\ +1 & -1\end{pmatrix}, \qquad H_4 = \begin{pmatrix} +1 & +1 & +1 & +1\\ +1 & -1 & +1 & -1\\ +1 & +1 & -1 & -1\\ +1 & -1 & -1 & +1 \end{pmatrix}.\]

The four rows of $H_4$ are the four patterns $(+1,+1,+1,+1)$, $(+1,-1,+1,-1)$, $(+1,+1,-1,-1)$, $(+1,-1,-1,+1)$, and you can check by hand that all six pairs have inner product zero.

That is not a coincidence, and the reason is worth seeing, because it is the whole construction in one line. Every row of $H_{2m}$ has the form $(r, r)$ or $(r, -r)$ for some row $r$ of $H_m$. Take two different rows of $H_{2m}$ and compute:

$\langle (r,r), (s,s)\rangle = \langle r,s\rangle + \langle r,s\rangle = 2\langle r,s\rangle$, which is $0$ when $r \neq s$;
$\langle (r,-r), (s,-s)\rangle = \langle r,s\rangle + \langle r,s\rangle = 2\langle r,s\rangle$, likewise $0$ when $r \neq s$;
$\langle (r,r), (s,-s)\rangle = \langle r,s\rangle - \langle r,s\rangle = 0$, and this one holds for every $r$ and $s$, including $r = s$.

So if the rows of $H_m$ are mutually orthogonal, so are the rows of $H_{2m}$. Since the single row of $H_1$ is trivially “mutually orthogonal”, the construction gives $N$ mutually orthogonal patterns of length $N$ for every $N$ that is a power of two — the largest set possible.

These are called Hadamard or Walsh codes, and they are what real CDMA systems use to keep users apart.

Write out the eight rows of $H_8$ from $H_4$, and verify that the second and fifth rows are orthogonal.

Recovering one signal from the sum

Finally, here is the calculation that all of this exists to make possible. Suppose $k$ users have mutually orthogonal patterns $c_1, \dotsc, c_k$, each of length $N$ with entries $\pm 1$, so that $|c_j|^2 = N$. User $j$ wants to send a single bit, encoded as $m_j = +1$ or $m_j = -1$, and transmits $m_j c_j$. What arrives at the receiver is the sum of everything in the air:

\[s = m_1 c_1 + m_2 c_2 + \dotsb + m_k c_k.\]

To recover user $j$’s bit, take the inner product of the received signal with user $j$’s own pattern:

\[\langle c_j, s\rangle = \sum_{i=1}^{k} m_i \langle c_j, c_i\rangle = m_j \langle c_j, c_j \rangle = m_j N,\]

because every term with $i \neq j$ is zero. So

\[m_j = \frac{\langle c_j, s\rangle}{N}.\]

Every other user’s transmission cancels exactly, no matter how many of them there are or what they sent. This is the same projection formula used to find a vector’s coordinates along perpendicular axes; here the “axes” are the users, and reading off a coordinate is reading one user’s message out of the noise of everybody else’s.

Three users use $c_1 = (+1,+1,+1,+1)$, $c_2 = (+1,-1,+1,-1)$ and $c_3 = (+1,+1,-1,-1)$, and the receiver sees $s = (+1,+3,-1,+1)$. What did each user send?