Digital Communications and Information Theory

Systematic Hamming code

A systematic linear block code keeps the k message bits in fixed positions of every codeword and appends n−k parity bits that are linear functions of the message. For a (7,4) Hamming code the parity bits are computed as p = mP over GF(2), so the code is completely specified by the 4×3 matrix P. Because the code is linear, the parity vector of the modulo-2 sum of two messages equals the XOR of their individual parity vectors, so the parities of the four unit messages 1000, 0100, 0010 and 0001 determine all 16 codewords. For minimum distance 3, the columns of the parity-check matrix H = [P^T \mid I_3] must be nonzero and pairwise distinct, so each row of P must have weight at least 2 and no two rows may be equal. The only admissible parity vectors are therefore 011, 101, 110 and 111, and once three of them are fixed the fourth is forced. For example, if the parities of 1000 and 0100 are 011 and 110, then message 1100 has parity 011 \oplus 110 = 101.

A (7,4,3) Hamming code corrects any single bit error, so the decoder fails only when two or more of the 7 bits are in error. On a binary symmetric channel with bit error probability p, the probability of at most one error in 7 bits is (1-p)^7 + 7p(1-p)^6, and this is the probability of correct decoding. The failure probability is one minus this value, so for p = 0.1 the correct-decoding probability is about 0.85 and the failure probability is about 0.15.

Entropy bounds of discrete random variable

The entropy of a discrete random variable X with probabilities p_i is H(X) = -\sum_i p_i \log_2 p_i bits, and it measures the average uncertainty of the outcome. For a variable taking K distinct values, 0 \le H(X) \le \log_2 K bits, with the upper bound reached only when all K values are equally likely. Hence the maximum achievable entropy of a 16-symbol alphabet is \log_2 16 = 4 bits per symbol, and any non-uniform distribution gives a smaller value.

If Y = g(X) is a function of X, then H(Y) \le H(X), with equality when g is one-to-one on the values taken by X, because such a map only relabels the outcomes. Injective maps such as 2X or 2^X therefore leave the entropy unchanged, whereas a map that merges distinct values, such as X^2, can lower it. For X uniform on \{-1, 0, 1\} we have H(X) = \log_2 3 \approx 1.585 bits but H(X^2) \approx 0.918 bits.

For a symmetric three-valued variable with probabilities \alpha, 1-2\alpha and \alpha, the entropy is a function of \alpha that peaks at \alpha = 1/3, where the distribution is uniform. Values of \alpha on the same side of 1/3 are therefore ordered by monotonicity, while values on opposite sides must be compared by direct computation of -\sum p\log_2 p.

PCM quantization and sampling rate

In pulse code modulation a band-limited message is sampled at a rate f_s \ge 2f_m, where f_m is the highest frequency present, and each sample is quantized to one of L = 2^n levels coded with n bits. Sampling above the Nyquist rate, for instance at 1.25 times it, raises the bit rate in proportion, and the resulting bit rate R_b = n f_s must still fit within the channel.

If the channel supports at most R_{max} bits per second, the largest usable resolution is n \le R_{max}/f_s, and the number of levels follows from it. A higher sampling rate therefore forces a coarser quantizer, which is a trade-off between time resolution and amplitude resolution.

For a uniform quantizer covering [-V_{max}, V_{max}] with L levels, the step is \Delta = 2V_{max}/L and the quantization noise power is \Delta^2/12 when the error is uniformly distributed. The signal-to-quantization-noise ratio is then \mathrm{SQNR} = 3L^2 (V_{rms}/V_{max})^2. For example, with V_{rms}/V_{max} = 0.1 and L = 32, the ratio is about 30.7.

Finally, a channel of bandwidth B and signal-to-noise ratio S/N carries at most C = B\log_2(1 + S/N) bits per second, so the minimum bandwidth for a given bit rate satisfies B\log_2(1+S/N) \ge R_b. For a 48 kb/s stream over a channel with linear SNR of 15, the bandwidth must be at least 48/\log_2 16 = 12 kHz.

Maximum likelihood detection decision boundary

A maximum likelihood detector chooses the hypothesis x_i that maximizes the likelihood f(y \mid x_i) of the received value y, and with equal priors this coincides with the MAP rule. The decision boundary between two hypotheses is the set of y where their likelihoods are equal, so it is found by solving f(y \mid x_1) = f(y \mid x_2) and noting which hypothesis is larger on each side.

For additive zero-mean Gaussian noise of equal variance, the likelihoods cross at the midpoint of the two signal levels. For an equally spaced constellation such as \{-2, 0, 2\} with symmetric noise, the ML boundaries are therefore the midpoints \pm 1.

Non-Gaussian densities, including those with finite support, can produce intervals where one hypothesis has zero likelihood, so the boundary need not be a midpoint. The symbol error probability is the probability that the received value falls in another symbol's decision region, which is the integral of the correct symbol's density over that region. An outer symbol is in error through one tail of the noise, while an interior symbol is in error through both tails.

Delta modulation slope overload

In delta modulation the one-bit staircase output moves up or down by a fixed step \Delta at every sampling instant T_s = 1/f_s, so its maximum slope is \Delta f_s. Slope overload occurs when the input changes faster than this, and the staircase cannot follow it. To avoid overload the step must satisfy \Delta f_s \ge \max|dx/dt|. For a sinusoid A\sin(2\pi f_m t) the maximum slope is 2\pi f_m A, which gives \Delta_{min} = 2\pi f_m A/f_s.

For example, a 1 V amplitude sinusoid at 1 kHz sampled at 64 kHz requires \Delta \ge 2\pi \times 1000 \times 1/64000 \approx 0.098 V. A larger step avoids overload but increases granular noise where the input is nearly flat, so the choice of step is a design trade-off between the two kinds of noise.

Polar NRZ bit error probability

Polar NRZ signaling sends one level +A for a binary 1 and the opposite level -A for a binary 0, so the two levels are 2A apart. With zero-mean Gaussian noise of variance \sigma^2 and decision threshold v, an error for a transmitted 0 occurs when the sample exceeds v, with probability Q((v+A)/\sigma). For a transmitted 1 the error probability is Q((A-v)/\sigma), so the average bit error probability is P_e = P_0\,Q\!\left(\frac{v+A}{\sigma}\right) + P_1\,Q\!\left(\frac{A-v}{\sigma}\right).

The MAP threshold, obtained by equating P_0 f(y\mid 0) and P_1 f(y\mid 1), is v_{th} = \dfrac{\sigma^2}{s_1 - s_0}\ln\dfrac{P_0}{P_1}, where s_1 and s_0 are the two levels. For equal priors it reduces to the midpoint 0. When the symbols are unequally likely, the threshold moves toward the less probable level, so the decision region of the rarer symbol shrinks. For example, with A = 1, \sigma^2 = 0.25 and P_1 = 0.2, the threshold is 0.125\ln 4 \approx 0.17.

Bits per symbol for M-ary modulation

An M-ary modulation scheme maps \log_2 M bits onto each symbol, so M is a power of 2 for an integer bit count, and the raw bit rate is R_b = R_s\log_2 M. Standard examples are QPSK with 2 bits per symbol, 8-PSK with 3, 16-QAM with 4 and 64-QAM with 6.

When the modulation changes from symbol to symbol, the raw bit rate equals the symbol rate times the average of \log_2 M over the constellations used. An alternating pattern of 8-PSK and 64-QAM symbols therefore carries (3+6)/2 = 4.5 bits per symbol on average.

Channel capacity of discrete memoryless channel

The capacity of a discrete memoryless channel is C = \max_{p(x)} I(X;Y) bits per channel use, where the maximum is taken over input distributions. For a channel whose rows are permutations of the same probability vector, the uniform input gives a uniform output and maximizes the mutual information, so C = \log_2|\mathcal{Y}| - H(\text{row}). The binary symmetric channel is the simplest case, with C = 1 - h(p), where h is the binary entropy function.