Exercises

The four 4-PAM Gray codes are $(-3, -1, +1, +3) \to (00, 01, 11, 10)$. A 16-QAM point at $(x, y)$ has 4-bit label $(\text{Gray}(x), \text{Gray}(y))$, concatenation giving $(b_0^I, b_1^I, b_0^Q, b_1^Q)$.

Horizontal neighbours differ only in their 2-bit $I$ sublabel. The PAM Gray transitions are $(00 \leftrightarrow 01)$, $(01 \leftrightarrow 11)$, $(11 \leftrightarrow 10)$ — each differing in exactly one of $b_0^I, b_1^I$. The $Q$ sublabel is the same on both ends. So each pair differs in exactly one bit. With 4 rows and 3 horizontal pairs per row, there are $4 \cdot 3 = 12$ horizontal pairs.

By symmetry, $12$ vertical pairs, each also at Hamming distance $1$.

$24$ nearest-neighbour pairs, all at Hamming distance exactly one. This is the Gray property. $\blacksquare$

$C_{\rm BICM}(\mu) = \sum_{\ell = 0}^{L-1} I(Y; B_\ell)$.

Any product-form decoding metric is mismatched relative to the true joint symbol likelihood, and the generalised mutual information (GMI) under such a metric equals the sum of marginals — a standard result from Merhav-Kaplan-Lapidoth- Shamai on mismatched decoding.

With exact marginal likelihoods $p_{W_\ell}(y \mid b)$, the decoder operates on a memoryless binary mixture channel with capacity $\tfrac{1}{L} \sum_\ell I(Y; B_\ell)$; Shannon's theorem delivers reliable coded-bit rate up to this capacity, and coded-bit rate $\times L$ is the information rate.

$I(Y; X) = I(Y; B_0, \ldots, B_{L-1}) = \sum_{\ell} I(Y; B_\ell \mid B_0, \ldots, B_{\ell-1})$.

Difference $= \sum_{\ell \ge 1} [I(Y; B_\ell \mid B_{<\ell}) - I(Y; B_\ell)]$. (The $\ell = 0$ term cancels.)

Using the identity $I(Y; B_\ell \mid B_{<\ell}) - I(Y; B_\ell) = I(B_\ell; B_{<\ell} \mid Y) - I(B_\ell; B_{<\ell})$ and the prior-independence $I(B_\ell; B_{<\ell}) = 0$, we get $\sum_\ell I(B_\ell; B_{<\ell} \mid Y) \ge 0$.

Each term $I(B_\ell; B_{<\ell} \mid Y) = 0$ iff $B_\ell$ and $B_{<\ell}$ are conditionally independent given $Y$; all terms vanish iff $B_0, \ldots, B_{L-1}$ are jointly conditionally independent given $Y$. $\blacksquare$

$\mathcal{X}_0^{(0)} = \{-3, -1\}$ (labels $00, 01$) and $\mathcal{X}_0^{(1)} = \{+1, +3\}$ (labels $11, 10$). Therefore $$p_{W_0}(y \mid 0) = \tfrac12 [\phi(y+3) + \phi(y+1)],\qquad p_{W_0}(y \mid 1) = \tfrac12 [\phi(y-1) + \phi(y-3)].$$ Each half corresponds to "two points on one side of zero." This is an approximately symmetric binary-input channel with the decision boundary at $y = 0$.

$\mathcal{X}_1^{(0)} = \{-3, +3\}$ (labels $00, 10$) and $\mathcal{X}_1^{(1)} = \{-1, +1\}$ (labels $01, 11$). Therefore $$p_{W_1}(y \mid 0) = \tfrac12 [\phi(y+3) + \phi(y-3)],\qquad p_{W_1}(y \mid 1) = \tfrac12 [\phi(y+1) + \phi(y-1)].$$ Each half is a two-component Gaussian mixture. The decision boundaries are at $y = \pm 2$.

The first bit is the easier bit: points that carry $b_0 = 0$ are all on one side of $y = 0$, so the posterior resembles a binary-input antipodal channel. The second bit is harder: points carrying $b_1 = 0$ (the outer pair) and $b_1 = 1$ (the inner pair) are interleaved, and the channel has two decision regions. This mirrors the numerical table of Thm. TThe BICM Capacity Decomposition.

$p_{W_1}^{\rm SP}(y \mid 0) = \tfrac12 [\phi(y+3) + \phi(y-1)]$ and $p_{W_1}^{\rm SP}(y \mid 1) = \tfrac12 [\phi(y+1) + \phi(y-3)]$.

Under SP, each $b_1$-subset consists of two points at distance $4$ — both mixtures are bimodal with widely separated modes. The two conditional distributions are in fact identical up to a shift by 4, so the total variation between $p(y \mid 0)$ and $p(y \mid 1)$ is small, and the mutual information $I(Y; B_1^{\rm SP})$ is significantly less than $I(Y; B_1^{\rm Gray})$.

SP labelling encodes bit $b_1$ in a long-range structure (points separated by $4$), which makes each unconditional bit-channel distribution bimodal and hard to distinguish. Gray encodes bit $b_1$ in short-range structure (inner pair vs outer pair), giving a cleaner unconditional binary channel. The MLC decoder (which conditions on $b_0$) turns the SP bimodal channel into a unimodal one and reaps the hierarchy benefit — but BICM, being unconditional, pays the bimodal price.

The simulation reports $C_{\rm CM} \approx 3.218$ and $C_{\rm BICM, Gray} \approx 3.176$ bits/symbol, giving a gap of $0.042$ bits, well below the 0.05-bit ceiling.

Sweeping the plot from $\text{SNR} = -5$ to $+25$ dB, the gap $C_{\rm CM} - C_{\rm BICM, Gray}$ peaks at approximately $\text{SNR} = 4$ dB with a value of $\approx 0.047$ bits/symbol. At higher SNR the gap decays exponentially (Thm. TGray Labelling Near-Optimality on AWGN); at lower SNR both capacities go to zero and the gap shrinks.

The uniform bound in Thm. TGray Labelling Near-Optimality on AWGN(b) ($\le 0.05$ bits for $M \le 256$) is essentially tight for 16-QAM; the achievable numerical gap is within a hair of the theoretical upper bound and is negligible at the operating point of any real 16-QAM system.

$\eta = 0.75 \cdot 8 = 6$ bits/symbol.

From the plot, for $M = 256$ the BICM-Gray curve reaches $6$ bits/symbol at approximately $\text{SNR} \approx 19$ dB. (Compare the Shannon limit $\log_2(1 + \text{SNR}) = 6 \Rightarrow \text{SNR} = 63 \approx 18$ dB — the gap is the 256-QAM modulation-capacity penalty of $\approx 1$ dB.)

A capacity-approaching LDPC on BICM-Gray-256-QAM cannot achieve vanishing error below $19$ dB of SNR. Adding the standard finite-length penalty of $1$–$1.5$ dB puts a typical rate-$3/4$ 256-QAM waterfall at $\approx 20$–$20.5$ dB for BER $10^{-5}$.

Under Gray labelling, the dominant error event for each bit is a single nearest-neighbour flip, occurring with probability $P_\ell \approx Q(d_{\min}/(2\sigma)) = Q(\sqrt{\text{SNR}/5})$ (using $d_{\min}^2 = 4E_s/5$ for unit-energy 16-QAM and $\sigma^2 = 1/(2 \text{SNR})$ per real dim).

Each bit channel has conditional entropy $H(B_\ell \mid Y) \approx h_2(P_\ell)$, so $I(Y; B_\ell) = 1 - h_2(P_\ell) \approx 1 + P_\ell \log_2 P_\ell + (1 - P_\ell) \log_2 (1 - P_\ell)$. For small $P_\ell$, the leading correction is $-P_\ell \log_2 P_\ell + O(P_\ell) \to 0$ as $\text{SNR} \to \infty$.

$C_{\rm BICM, Gray} = \sum_{\ell=0}^{3} I(Y; B_\ell) = 4 - \sum_\ell h_2(P_\ell) \approx 4 - \Theta(Q(\sqrt{\text{SNR}/5}))$. The exponential decay of $Q(\cdot)$ makes the gap to the full capacity $L = 4$ vanish super-exponentially in $\text{SNR}$.

The CM capacity behaves exactly the same way at high SNR (same nearest-neighbour analysis, just on the $M$-ary symbol channel), so the gap $C_{\rm CM} - C_{\rm BICM, Gray}$ also decays as $\Theta(Q(\sqrt{\text{SNR}/5}))$ — the exponential-convergence result of Thm. TGray Labelling Near-Optimality on AWGN(a). $\blacksquare$

$\text{GMI}(q) = \sup_{s \ge 0} \mathbb{E}\bigl[\log \tfrac{q(Y, B)^s}{\mathbb{E}_{B'}[q(Y, B')^s]}\bigr]$. Under i.i.d.\ uniform labels, $\mathbb{E}_{B'}[q(Y, B')^s] = \prod_\ell \mathbb{E}_{B'_\ell}[q_\ell(Y, B'_\ell)^s]$, and $\log q(Y, B) = \sum_\ell \log q_\ell(Y, B_\ell)$. The GMI factorises.

For each $\ell$, with $q_\ell$ being the exact marginal likelihood, the per-bit GMI reduces to $I(Y; B_\ell)$ at $s = 1$. (The supremum over $s$ is achieved at $s = 1$ because the metric is matched — the per-bit channel law.)

$\text{GMI}(q) = \sum_\ell I(Y; B_\ell) = C_{\rm BICM}(\mu)$. This matches the BICM capacity formula and confirms that the BICM capacity is the correct operational quantity under product-metric decoding. $\blacksquare$

Max-log: $\log \sum_i e^{-d_i/\sigma^2} \approx -\min_i d_i/\sigma^2$. This is exact only when one $d_i$ is much smaller than the others; otherwise, the true log-sum is strictly greater by a positive offset.

The max-log metric $q^{\rm ML}_\ell$ is strictly mismatched (not the true marginal likelihood) for $\sigma^2 > 0$. The GMI formula is then suprema over $s \ne 1$ in general, and yields a value strictly less than $I(Y; B_\ell)$.

As $\sigma^2 \to 0$, the nearest-neighbour $x^*$ dominates the likelihood, so the max-log approximation becomes exact. In this regime $\text{GMI}^{\rm ML} \to \sum_\ell I(Y; B_\ell) = C_{\rm BICM}(\mu)$. The loss is therefore a low-to-moderate-SNR effect; at the high SNRs where modern MCS schemes actually operate, max-log is essentially lossless.

For 4-PAM, both Gray ($00, 01, 11, 10$) and SP ($00, 10, 01, 11$ — or whatever SP tree is used) produce the same top- level partition $\{-3, -1\}$ vs $\{+1, +3\}$. Hence $I(Y; B_0^{\rm Gray}) = I(Y; B_0^{\rm SP})$ — around $0.92$ bits at $\text{SNR} = 10$ dB.

The bit-1 partitioning differs: Gray gives $\{-3, +3\}$ vs $\{-1, +1\}$ (inner/outer), while SP gives $\{-3, +1\}$ vs $\{-1, +3\}$ (cosets of distance $2$). The SP unconditional bit channel is symmetric (each $b_1$-set has points at distances $-3$ and $+1$, a distance-4 pair), which makes the marginal posterior $P(B_1^{\rm SP} = 0 \mid y)$ flatter in $y$ than $P(B_1^{\rm Gray} = 0 \mid y)$. Numerically, $I(Y; B_1^{\rm Gray}) \approx 0.66$ while $I(Y; B_1^{\rm SP}) \approx 0.35$.

$C_{\rm BICM, Gray, 4-PAM} \approx 0.92 + 0.66 = 1.58$ bits vs $C_{\rm BICM, SP, 4-PAM} \approx 0.92 + 0.35 = 1.27$ bits. The SP capacity is $\approx 0.3$ bits lower. This is exactly the MLC-style hierarchy that SP creates — information is concentrated in bit $0$ under SP, but bit $1$ is useless without conditioning.

$\eta = 0.75 \cdot 2 = 1.5$ bits/symbol. BICM-Gray-4-QAM reaches $1.5$ bits at $\text{SNR} \approx 3.8$ dB (the QPSK channel is essentially BI-AWGN per component, so the BICM gap to CM is trivial).

$\eta = 0.75 \cdot 4 = 3$ bits/symbol. BICM-Gray-16-QAM reaches $3$ bits at $\text{SNR} \approx 9.3$ dB.

$\eta = 0.75 \cdot 6 = 4.5$ bits/symbol. BICM-Gray-64-QAM reaches $4.5$ bits at $\text{SNR} \approx 14.5$ dB.

The three MCS thresholds are approximately $4$ dB / $9.5$ dB / $15$ dB. A scheduler should switch from QPSK to 16-QAM around $\text{SNR} \approx 9$ dB and from 16-QAM to 64-QAM around $\text{SNR} \approx 15$ dB, with appropriate implementation margin (1–1.5 dB above each Shannon limit). The same LDPC code at rate $3/4$ drives all three — that is the engineering point of BICM.

By construction of the BICM encoder (uniformly distributed coded bits + ideal interleaver), the prior on $(B_0, \ldots, B_{L-1})$ is i.i.d.\ uniform on $\{0, 1\}^L$. Hence any subset of label bits is mutually independent, so $I(B_\ell; B_{<\ell}) = 0$.

$I(Y; B_\ell, B_{<\ell}) = I(Y; B_{<\ell}) + I(Y; B_\ell \mid B_{<\ell})$ (decompose the joint via chain rule with $B_{<\ell}$ first). Equally, $I(Y; B_\ell, B_{<\ell}) = I(Y; B_\ell) + I(Y; B_{<\ell} \mid B_\ell)$ (decompose with $B_\ell$ first). Equating gives $$I(Y; B_\ell \mid B_{<\ell}) - I(Y; B_\ell) = I(Y; B_{<\ell} \mid B_\ell) - I(Y; B_{<\ell}).$$

Using the symmetric form $I(A; B \mid C) + I(A; C) = I(A; B, C) = I(A; B) + I(A; C \mid B)$ with $A = B_{<\ell}$, $B = Y$, $C = B_\ell$: $I(B_{<\ell}; Y \mid B_\ell) - I(B_{<\ell}; Y) = I(B_{<\ell}; B_\ell \mid Y) - I(B_{<\ell}; B_\ell)$. Using $I(B_{<\ell}; B_\ell) = 0$ (prior independence), $$I(Y; B_\ell \mid B_{<\ell}) - I(Y; B_\ell) = I(B_{<\ell}; B_\ell \mid Y) \ge 0. \quad \blacksquare$$

A single binary code + rate matching drives every modulation in the MCS table; MLC would require $L$ codes per modulation and a dedicated rate-allocation step for each. This reduces encoder/decoder hardware complexity by a factor of $\ge L$.

The BICM decoder is a single run of a binary decoder over the full LLR stream. MLC/MSD is sequential: an error at stage 0 propagates to stage 1 and causes catastrophic error-floor behaviour requiring iterative workarounds.

Changing the labelling (e.g., from Gray to quasi-Gray for APSK) affects only the demapper's look-up; the LDPC decoder and the encoder are unchanged. In MLC, changing the partitioning changes every per-level code's design.

From the plot, BICM-Gray-64-QAM reaches $\eta = 3.6$ bits at approximately $\text{SNR} = 11$ dB.

Adding $1.2$ dB for a realistic LDPC: $11 + 1.2 = 12.2$ dB is the effective waterfall for BER $\approx 10^{-2}$ (the NR BLER target for initial transmission).

We are at $12$ dB — $0.2$ dB below the effective waterfall. HARQ retransmissions will almost certainly be needed. A more prudent MCS at this SNR is $I_{\rm MCS} = 15$ (rate $\approx 0.5$, 64-QAM), which has its waterfall at $\approx 10$ dB and gives a margin of $2$ dB.

In 5G NR, the outer-loop link adaptation algorithm continually adjusts MCS based on the moving-average block error rate; over time it will back off from $I_{\rm MCS} = 17$ to $15$ at this SNR.

One valid anti-Gray 16-QAM labelling maps $(b_0^I, b_1^I, b_0^Q, b_1^Q)$ to point $(I, Q)$ where $I = 2 b_0^Q + b_1^Q - 3$ (rows become Gray-flipped $Q$) and $Q = 2 b_0^I + b_1^I - 3$ (columns become Gray-flipped $I$). Neighbours now differ in 2 bits instead of 1.

Gray: $C_{\rm BICM, Gray} \approx 0.512$ bits/symbol. Anti-Gray: $C_{\rm BICM, AG} \approx 0.528$ bits/symbol. Anti-Gray is ahead by $\approx 0.016$ bits.

At very low SNR the per-bit channels are nearly useless in isolation (conditional entropy near 1); spreading bit-related information across more label transitions (anti-Gray) extracts slightly more unconditional mutual information than concentrating it on single-bit transitions (Gray). The advantage is small and reverses at higher SNR where Gray's one-bit-flip structure becomes more valuable.

At $\text{SNR} = -3$ dB, operating a BICM system at $\eta = 0.5$ bits means using 16-QAM at rate $R_c = 1/8$, which is far below anything a practical system would consider. The anti-Gray advantage exists but is operationally irrelevant.

If consecutive $L$ coded bits share the same symbol, then their LLRs are deterministic functions of the same $y$ — highly correlated. The binary decoder, which assumes i.i.d.
bit-channel outputs, encounters a memory-full binary channel.

A binary decoder that treats a memory-full channel as memoryless operates at a smaller generalised mutual information. For small $L$ this loss is significant; it is exactly what the interleaver recovers.

On a fading channel, the interleaver is even more critical: without it, a symbol fade takes down all $L$ consecutive coded bits at once, destroying the diversity order of the binary code. The interleaver spreads the fade across different codeword positions, restoring full diversity (Ch. 6).

The interleaver is what converts the $M$-ary symbol channel into $L$ marginally-independent binary channels. Take it out and the BICM paradigm collapses.

Numerical integration gives $C_{\rm CM}^{\rm 8-PSK} \approx 1.81$ bits/symbol at $\text{SNR} = 6$ dB. (For reference: Shannon limit is $\log_2(5) = 2.32$; QPSK CM is $\approx 1.60$.)

Under Gray labelling (bit 0 splits upper/lower half-circle, bit 1 splits right/left, bit 2 splits alternating), the three bit-channel capacities are roughly $(0.78, 0.46, 0.46)$ for a sum of $C_{\rm BICM, Gray}^{\rm 8-PSK} \approx 1.70$ bits/symbol.

$C_{\rm CM} - C_{\rm BICM, Gray} \approx 0.11$ bits — an order of magnitude larger than the 16-QAM gap. In SNR terms, the rate $1.70$ bits is reached by CM at about $5.3$ dB, so the BICM penalty is $\approx 0.7$ dB of SNR.

8-PSK does not decompose into independent PAM Gray components; its three bit channels are more strongly correlated at the symbol level than the four bit channels of 16-QAM (which split into two independent 4-PAM systems). The BICM formula's product-decoding assumption loses more information on 8-PSK than on square QAM. This is a DVB-S2- relevant observation: 8-PSK + rate-5/6 LDPC is used at medium SNR, and the $\approx 0.7$ dB BICM penalty is a known design cost.

For square $M$-QAM, the label decomposes as $(b_0^I, \ldots, b_{L/2 - 1}^I, b_0^Q, \ldots, b_{L/2 - 1}^Q)$, and the likelihood factorises: $p(y \mid x) = p(y_I \mid x_I) \cdot p(y_Q \mid x_Q)$. So each LLR depends only on one of $y_I, y_Q$ and the corresponding $\sqrt{M}$-PAM subset — an $O(\sqrt{M})$ search per LLR.

$L$ LLRs $\times O(\sqrt{M})$ per LLR = $O(L \sqrt{M})$ total. For 256-QAM, $L = 8$, $\sqrt{M} = 16$, giving $128$ distance computations — compared to $M \cdot L = 2048$ for the naive algorithm. A $16\times$ speedup.

5G NR demappers use further refinements (e.g., the "decision- region" trick that directly computes max-log LLRs from truncated projections of $y$), bringing the cost to $O(L + \text{const})$ per symbol for modulations up to 256-QAM. This is the cost floor.

The BICM pairwise error probability on a Rayleigh block- fading channel decays as $\text{SNR}^{-d}$, where the diversity order $d$ is at most the minimum number of distinct fading realisations affecting the dominant codeword pair at Hamming distance $d_f$.

Codeword length $N$. Interleaver spreads the $N$ coded bits uniformly across $M_b$ fading blocks, so each block gets $N/M_b$ bits. With $d_f = 10$, the $10$ differing bits of the dominant codeword-pair fall into at most $\min(d_f, M_b) = \min(10, M_b)$ distinct blocks — so $d = \min(10, M_b)$.

If $M_b \ge 10$, the code's full free-distance diversity is exploited. If $M_b < 10$, the fading correlation limits the diversity to $M_b$. In 5G NR with OFDM over a frequency- selective channel, the interleaver is chosen to span all available coherence bandwidths, ensuring $M_b$ is as large as possible. Chapter 6 develops the full analysis.

$C_{\rm CM} - C_{\rm BICM}(\mu_G) = \sum_\ell I(B_\ell; B_{<\ell} \mid Y) \le \sum_\ell H(B_\ell \mid Y)$.

Under Gray labelling, each bit channel is approximately a BI-AWGN channel with effective SNR $\text{SNR}_\ell^{\rm eff}$ depending on the PAM level. Its conditional entropy is $h_2(P_\ell)$ where $P_\ell = Q(\sqrt{\text{SNR}_\ell^{\rm eff}})$. Summing gives a closed-form — but loose — upper bound $\sum_\ell h_2(P_\ell)$.

Observe that $I(B_\ell; B_{<\ell} \mid Y)$ is bounded below $H(B_\ell \mid Y) \cdot H(B_{<\ell} \mid Y)$ (Cauchy- Schwarz-like). Refinements in Fàbregas-Martínez-Caire 2008 §3.5 give sharper bounds via the Taylor expansion of mutual information around Gaussian inputs. A fully analytical uniform bound remains an open problem; the result of Caire-Taricco-Biglieri 1998 is a numerical table, and researchers have since produced asymptotic closed-form expressions (Martínez-Fàbregas-Caire 2009) and tight machine-learning-assisted bounds (Alvarado et al. 2015).

A valid partial answer is the high-SNR asymptotic $C_{\rm CM} - C_{\rm BICM, Gray} = \Theta(Q(d_{\min} \sqrt{\text{SNR}/2}))$ from Thm. TBICM Capacity — High-SNR Asymptotics. An uniform-in-SNR closed-form bound is a research-level open question — the state of the art is in Alvarado, Brännström, Agrell (2015) "A note on the capacity of BICM in fading channels" and subsequent papers.

Before Caire-Taricco-Biglieri 1998, coded modulation for wireless channels was dominated by two paradigms: Ungerboeck TCM (optimised for AWGN, monolithic per-channel) and Imai-Hirasawa MLC (multi-code, set-partitioning-based). Both paradigms tightly coupled code design to constellation design, making rate adaptation and multi-modulation MCS tables prohibitive. Zehavi's 1992 paper had shown that a simple bit-interleaver + binary code + 8-PSK combination could outperform TCM on Rayleigh fading — but without any theoretical justification for how well it could do or why.

Caire-Taricco-Biglieri supplied that theory. Their paper's three contributions — (i) formalising BICM as $L$ parallel independent binary channels with capacity $\sum_\ell I(Y; B_\ell)$; (ii) proving Gray labelling makes the BICM capacity within fractions of a bit of CM capacity on square QAM; (iii) deriving the diversity-order analysis on fading channels — together turned BICM from a plausible heuristic into a capacity-theoretic design rule. The paper's single most influential design advice — "use a powerful binary code, a bit interleaver, and Gray labelling" — is the architectural basis of every modern wireless MCS.

The direct industrial consequences were: DVB-S2 (2003) adopted LDPC + BICM as its coded-modulation architecture with quasi-Gray APSK, replacing TCM/convolutional/BICM- hybrid designs considered in the standardisation; LTE (2008) used turbo codes + BICM + Gray QAM; 5G NR (2018) switched back to LDPC + BICM + Gray QAM with a single base graph per code length. Every one of these standards uses exactly the architecture Caire-Taricco-Biglieri 1998 justified theoretically. In the history of wireless standards, few academic papers have had so direct an impact — and this one is the flagship CommIT contribution of the entire Ferkans CM book.