Modality A: Midterm
The midterm of Modality A has twelve true/false statements drawn from the 25 theory statements of this collection, possibly paraphrased. The sample examination shows the format.
Sample examination
Weekly samples
A new sample midterm is posted every Tuesday until the exam, with its solutions.
Sample 1
Sample 2
Collection
This collection contains twenty-five fundamental statements of digital data transmission, the theory that the Modality A midterm exam assesses. The exam presents short statements, each of them on one part of a statement of this list.
We use the following conventions. The function \sinc(x) is \tfrac{\sin(\pi x)}{\pi x}. A probability is denoted by \Pr(\cdot) and an expectation by \EE(\cdot). Logarithms are in base 2, written \log_2, and entropies and rates are measured in bits. A channel with input x and output y has law W(y|x), a probability for discrete outputs and a density for continuous ones.
The inner product of two finite-energy waveforms \phi_i(t) and \phi_k(t) is \begin{equation*} \langle\phi_i,\phi_k\rangle=\int_{-\infty}^{\infty}\phi_i(t)\phi_k^*(t)\drm t, \end{equation*} where ^* denotes the complex conjugate, which falls on the second waveform, and the energy of a waveform is its inner product with itself, E=\langle\phi,\phi\rangle, that is, \begin{equation*} E=\int_{-\infty}^{\infty}|\phi(t)|^2\drm t, \end{equation*} a nonnegative real number. A set \{\phi_i(t)\} of waveforms is orthonormal if \langle\phi_i,\phi_k\rangle=\delta_{ik}, where \delta_{ik} equals 1 for i=k and 0 otherwise: every waveform has unit energy and any two distinct waveforms are orthogonal, that is, have zero inner product.
Two waveforms with disjoint supports are orthogonal, but orthogonal waveforms need not have disjoint supports, and linearly independent waveforms need not be orthogonal. Two waveforms are linearly dependent when one is a constant multiple of the other, and if \phi(t) has energy E then \alpha\phi(t) has energy |\alpha|^2E and \langle\phi,\alpha\phi\rangle=\alpha^*E for any complex \alpha, while the time-scaled waveform \phi(at) has energy E/|a| for any real a\neq0. A unit-modulus factor e^{j\theta} or a time shift leaves the energy unchanged.
Given an orthonormal set \{\phi_i(t)\}\smash{_{i=1}^{N}}, a signal x(t) is represented in the signal space they span as \begin{equation*} \bar x(t)=\sum_{i=1}^{N}x_i\phi_i(t), \end{equation*} with coefficients x_i=\langle x,\phi_i\rangle. The representation \bar x(t) is the orthogonal projection of x(t) onto the signal space, the signal of the space closest to x(t), and it equals x(t) exactly when x(t) belongs to the space. A signal band-limited to |f|\leq W belongs to the space spanned by the orthonormal sampling waveforms \begin{equation*} \phi_i(t)=\sqrt{2W}\,\sinc\Bigl(2W\Bigl(t-\frac{i}{2W}\Bigr)\Bigr), \end{equation*} i\in\mathbb Z, with coefficients x_i=\tfrac{1}{\sqrt{2W}}\,x\bigl(\tfrac{i}{2W}\bigr): its samples taken 2W times per second, scaled by \tfrac{1}{\sqrt{2W}}.
Parseval’s identity states that an inner product can be computed in the time or in the frequency domain, \begin{equation*} \langle x,y\rangle=\int_{-\infty}^{\infty}\hat x(f)\hat y^*(f)\drm f, \end{equation*} where \begin{equation*} \hat x(f)=\int_{-\infty}^{\infty}x(t)e^{-j2\pi ft}\drm t \end{equation*} is the Fourier transform, so a signal has the same energy in both domains. The waveform B\sinc(Bt), with B>0, has a rectangular transform equal to 1 for |f|\leq\tfrac B2 and 0 elsewhere. Hence \sinc(t) has unit energy and occupies the band |f|\leq\tfrac12, and, conversely, a rectangle of amplitude A and width T centered at the origin has transform AT\sinc(Tf). Inner products of \sinc waveforms are computed in the frequency domain as overlaps of rectangles.
The bandwidth of a baseband waveform is the extent of the positive frequencies where its Fourier transform is nonzero: a baseband waveform of bandwidth W occupies |f|\leq W. A passband transmission of bandwidth W and duration T provides WT orthonormal complex waveforms, that is, WT channel uses, or W channel uses per second. It is built from a baseband waveform of bandwidth \tfrac W2, which carries W complex symbols per second. Consequently, a rate or a capacity in bits per channel use is converted to bits per second by multiplying by the passband bandwidth W, and to bits per second and per hertz, the spectral efficiency, by dividing the latter by W again.
Symbols sent as \sum_{i=-\infty}^{\infty}X_i\phi(t-iT), with symbol period T, are free of inter-symbol interference when the shifted waveforms \phi(t-iT) are orthogonal, which holds if and only if the similarity function \begin{equation*} R_{\phi\phi}(\tau)=\int_{-\infty}^{\infty}\phi(t)\phi^*(t-\tau)\drm t \end{equation*} vanishes at every nonzero multiple of T. For the pulse \sinc(t/T_0), whose similarity function T_0\sinc(\tau/T_0) vanishes at \tau=\pm T_0,\pm2T_0,\dots, this holds when T is a multiple of T_0. Nyquist’s criterion: with a baseband waveform of bandwidth W, which occupies |f|\leq W, the maximum symbol rate without inter-symbol interference is R_{\mathrm s}=2W symbols per second, that is, the minimum symbol period is T=\tfrac{1}{2W}. The amplitude of the waveform fixes its energy, not the rate.
A constellation with M points carries \log_2M bits per symbol, and the bit rate is R_{\mathrm b}=R_{\mathrm s}\log_2M bits per second when the symbols are sent at R_{\mathrm s} symbols per second. For instance, 256-QAM carries 8 bits per symbol and 8-PSK carries 3, so a baseband waveform of bandwidth 50 MHz allows at most 100 Msymbol/s and 800 Mbit/s with 256-QAM. When the waveforms of consecutive messages must not overlap in time, the maximum rate is the number of bits per waveform divided by the duration of the longest waveform.
The energy of a signal is \begin{equation*} E=\int_{-\infty}^{\infty}|x(t)|^2\drm t, \end{equation*} where for a complex signal |x(t)|^2=x(t)x^*(t) is the squared modulus, not the square. The energy of a sum is \begin{equation*} E_{x+y}=E_x+E_y+2\,\mathrm{Re}\langle x,y\rangle, \end{equation*} which reduces to the sum of the energies when \mathrm{Re}\langle x,y\rangle=0, in particular when the two signals are orthogonal.
If x(t)=\smash{\sum_{i=1}^{N}}x_i\phi_i(t) with \{\phi_i\}\smash{_{i=1}^{N}} orthonormal, its energy is the sum of the squared moduli of its coefficients, \begin{equation*} E=\sum_{i=1}^{N}|x_i|^2, \end{equation*} and the energy of a constellation point x is |x|^2. The average symbol energy of a constellation \mathcal X used with probabilities \Pr(x) is the expectation \Es=\EE(|X|^2), \begin{equation*} \Es=\sum_{x\in\mathcal X}\Pr(x)|x|^2. \end{equation*} For equiprobable symbols it is the arithmetic mean of the squared moduli of the points, including any point at the origin, which costs no energy but counts in the average.
The average energy per bit is the average symbol energy divided by the number of information bits carried by a symbol, \Eb=\Es/\log_2M for a one-to-one mapping of \log_2M bits onto M symbols, and more generally the average energy of a signal divided by the number of bits it carries. The average energy depends on the input distribution: a bit D with \Pr(D=1)=p has \EE(D^2)=p. If x(t)=\smash{\sum_{i=1}^{N}}a_i\phi_i(t) with unit-energy waveforms and independent zero-mean random coefficients, the average energy is \EE(E)=\smash{\sum_{i=1}^{N}}\EE(|a_i|^2) whatever the inner products of the waveforms, because the cross terms \EE(a_ia_k^*)=\EE(a_i)\EE(a_k)^* vanish, although they do affect the energy of each realization.
Law of large numbers: the average of n independent realizations of a random variable X approaches its expectation as n grows, \begin{equation*} \frac1n\sum_{i=1}^{n}x_i\to\EE(X), \end{equation*} so a Monte Carlo simulation estimates \EE(g(X)) by averaging g(x_i) over many independent samples. In particular, the relative frequency of an event approaches its probability, because the indicator of the event, equal to 1 when it occurs and 0 otherwise, has expectation equal to the probability. In MATLAB, a comparison such as
(s > a)is that indicator. Thus the average of the squared moduli of many symbols estimates the average symbol energy \EE(|X|^2), and the average of -\log_2\Pr(x_i) over many symbols estimates the entropy H(X).In MATLAB,
randreturns a uniform random number in (0,1), with \Pr(\texttt{rand}<p)=p for 0\leq p\leq1, so(rand < p)is a bit equal to 1 with probability p and, for a>0, a\,\texttt{rand}+b is uniform on (b,a+b) with density \tfrac1a. The functionrandnreturns a real Gaussian sample of zero mean and unit variance, so \sigma\,\texttt{randn}+\mu is Gaussian with mean \mu and variance \sigma^2, and a circularly symmetric complex Gaussian sample of variance \sigma^2 is generated as \tfrac{\sigma}{\sqrt2}\,(randn + 1j*randn).The entropy of a discrete random variable X with values in a finite set \mathcal X and probabilities \Pr(x) is \begin{equation*} H(X)=-\sum_{x\in\mathcal X}\Pr(x)\log_2\Pr(x)\ \text{bits}, \end{equation*} nonnegative, at most \log_2|\mathcal X|, the logarithm of the number of values, with equality for the uniform distribution, and additive for independent variables. The binary entropy function \begin{equation*} h_2(p)=-p\log_2p-(1-p)\log_2(1-p) \end{equation*} is the entropy of a bit equal to 1 with probability p. It vanishes for p=0 and p=1, it is symmetric around p=\tfrac12, and it attains its maximum, 1 bit, at p=\tfrac12.
The differential entropy of a continuous random variable with density f(x) is \begin{equation*} h(X)=-\int_{-\infty}^{\infty}f(x)\log_2f(x)\drm x\ \text{bits}. \end{equation*} It can be negative, it does not change when the variable is shifted by a constant, and scaling the variable by a adds \log_2|a|. A uniform variable on an interval of length a has h(X)=\log_2a, and an exponential variable with mean \mu, with density \tfrac1\mu e^{-x/\mu} for x\geq0, has h(X)=\log_2(e\mu).
A real Gaussian random variable with variance \sigma^2 has differential entropy \tfrac12\log_2(2\pi e\sigma^2), whatever its mean, and it has the largest differential entropy among all real random variables with that variance. The differential entropy of a complex random variable whose real and imaginary parts are independent is the sum of the entropies of the two parts. A circularly symmetric complex Gaussian variable of variance \sigma^2, with independent real and imaginary parts of variance \tfrac{\sigma^2}{2} each, has differential entropy \log_2(\pi e\sigma^2).
The mutual information between the input X and the output Y of a channel with input alphabet \mathcal X is \begin{equation*} I(X;Y)=H(Y)-H(Y|X), \end{equation*} where H(Y|X)=\sum_{x\in\mathcal X}\Pr(x)H(Y|X=x) and the output distribution is \Pr(y)=\sum_{x\in\mathcal X}\Pr(x)W(y|x). It is measured in bits per channel use, it is nonnegative and symmetric, and it vanishes when the output is independent of the input. The capacity of the channel is the largest mutual information over all input distributions, C=\max I(X;Y), and reliable communication, with error probability as small as desired for long enough codes, is possible at a rate R bits per channel use if and only if R<C. A coded-modulation system with a constellation of M points cannot transmit reliably above \log_2M bits per channel use, even without noise, so its rate is bounded by the smaller of \log_2M and C.
For the binary symmetric channel (BSC), or bit-flipping channel, with crossover probability p, which flips the input bit with probability p, the mutual information with equiprobable inputs is 1-h_2(p) bits per channel use. For the binary erasure channel (BEC), or bit-erasing channel, with erasure probability \varepsilon, which replaces the input by an erasure symbol with probability \varepsilon and never flips it, the mutual information with equiprobable inputs is 1-\varepsilon. In both cases the equiprobable input is the capacity achieving one: the BSC capacity equals 1 bit for p=0 or p=1 and vanishes at p=\tfrac12, where the output is independent of the input, and the BEC capacity counts the fraction 1-\varepsilon of bits that arrive intact.
In the discrete-time model of a complex AWGN channel with noise spectral density \No, each channel use is Y=X+Z, where Z is a circularly symmetric complex Gaussian noise sample of variance \sigma^2=\No, that is, \tfrac{\No}{2} per real component, independent from use to use. The channel law is \begin{equation*} W(y|x)=\frac{1}{\pi\sigma^2}e^{-|y-x|^2/\sigma^2}, \end{equation*} the noise density centered at the transmitted symbol. It depends on y only through the distance |y-x|, so all outputs at the same distance from x are equally likely. The channel is memoryless: the law of a sequence is the product of the laws of its symbols, W^n(\y|\x)=\prod_{i=1}^nW(y_i|x_i).
The capacity of the complex AWGN channel with average symbol energy \Es and noise variance \sigma^2 is \begin{equation*} C=\log_2\Bigl(1+\frac{\Es}{\sigma^2}\Bigr)\ \text{bits per channel use}, \end{equation*} achieved by a Gaussian input, where \Es/\sigma^2 is the signal-to-noise ratio per channel use. For the real AWGN channel it is \tfrac12\log_2\bigl(1+\tfrac{\Es}{\sigma^2}\bigr). With passband bandwidth W, power P and noise spectral density \No, the capacity in bits per second is \begin{equation*} C=W\log_2\Bigl(1+\frac{P}{\No W}\Bigr), \end{equation*} the capacity per channel use with \Es=\tfrac PW and \sigma^2=\No, multiplied by the W channel uses per second, and C/W is the spectral efficiency in bits per second and per hertz.
Reliable communication at a rate R bits per second over the AWGN channel with passband bandwidth W, power P and noise spectral density \No is possible if and only if R<W\log_2\bigl(1+\tfrac{P}{\No W}\bigr). For a given bandwidth the condition involves the power and the noise only through the ratio \tfrac{P}{\No}. As the bandwidth grows without bound with P and \No fixed, the capacity approaches the finite limit \tfrac{P}{\No}\log_2e bits per second, that is, \tfrac{P}{\No} nats per second: at low signal-to-noise ratio the capacity is proportional to the power, and at high signal-to-noise ratio it grows only logarithmically with it.
The maximum a posteriori (MAP) detector chooses, for the observed y, the symbol x that maximizes the joint probability, \begin{equation*} \hat x_{\mathrm{MAP}}(y)=\argmax_{x\in\mathcal X}\Pr(x)W(y|x), \end{equation*} where \Pr(x) is the probability with which the symbol is sent and W(y|x) the channel law. By Bayes’ rule this is the symbol with the largest posterior probability \Pr(x|y), and no detector has a smaller average error probability. The maximum likelihood (ML) detector chooses the symbol that maximizes the channel law, ignoring the prior, \begin{equation*} \hat x_{\mathrm{ML}}(y)=\argmax_{x\in\mathcal X}W(y|x). \end{equation*} It coincides with the MAP detector when the symbols are equiprobable, and where two likelihoods tie the MAP detector decides by the prior whereas the ML detector may decide arbitrarily.
On the real or complex Gaussian channel, the ML detector, which is optimal for equiprobable symbols, chooses the constellation point nearest to the observation, and the boundary between two points is the perpendicular bisector of the segment joining them, the midpoint for real symbols. This nearest-point rule is a property of Gaussian noise: with other noises, such as uniform, exponential or multiplicative, the detector must compare the channel laws directly. For sequences over a memoryless channel the ML decoder chooses the codeword with the largest product of symbol likelihoods, on the Gaussian channel the codeword nearest to the received sequence in Euclidean distance. For a repetition code of odd length on a bit-flipping channel with flip probability p<\tfrac12 it is the majority vote, whose error probability is the probability that more than half of the bits are flipped. An even length, with ties broken at random, has the same error probability as the odd length below it.
The conditional error probability of a detector given the symbol x, P_{\mathrm e}(x), is the probability that the observation falls outside the decision region of x when x is sent, and the average error probability over the constellation \mathcal X is \begin{equation*} P_{\mathrm e}=\sum_{x\in\mathcal X}\Pr(x)P_{\mathrm e}(x). \end{equation*} For two equiprobable real symbols \pm A in real Gaussian noise of variance \sigma^2, the ML detector is a threshold at 0 and P_{\mathrm e}=Q\bigl(\tfrac A\sigma\bigr), where the Gaussian tail function is \begin{equation*} Q(u)=\int_u^\infty\frac{e^{-t^2/2}}{\sqrt{2\pi}}\drm t, \end{equation*} equal to \tfrac12\erfc\bigl(\tfrac{u}{\sqrt2}\bigr) with \erfc(u)=\tfrac{2}{\sqrt\pi}\smash{\int_u^\infty}e^{-t^2}\drm t. In complex noise of variance \sigma^2, only the real component, of variance \tfrac{\sigma^2}{2}, matters for real symbols.
Groups of k bits can be mapped reversibly onto sequences of n symbols of an M-point constellation, so that the bits can be recovered from the symbols, if and only if M^n\geq2^k. The shortest reversible mapping has n=\lceil k/\log_2M\rceil symbols, and it carries \tfrac kn\leq\log_2M bits per symbol, with equality only when 2^k is a power of M. For instance, 10 bits need 7 symbols of 3-PSK, since 3^6=729<1024\leq3^7.
The rate of a coded-modulation system is the number of information bits per channel use, R=\tfrac kn when k information bits are sent in n symbols. A repetition code of length r followed by an M-point constellation has rate \tfrac{\log_2M}{r}. When a transmission chain has several stages, the information rate is the product of the rates of the stages, and each stage that adds redundancy reduces the rate. A rate can also be measured in source symbols per channel symbol, such as die throws per constellation symbol. It is converted to bits by multiplying by the information of a source symbol, \log_2 of the number of equiprobable outcomes, and repeating each source symbol r times divides it by r.