Exercises

$q_{\rm BICM}(y, x) = \prod_{\ell=0}^{L-1} p_{W_\ell}(y\mid b_\ell)$ where $b_\ell = \mu^{-1}(x)_\ell$ is the $\ell$-th label bit of $x$.

$\log q_{\rm BICM}(y, x) = \sum_{\ell: b_\ell = 0} \log p_{W_\ell}(y\mid 0) + \sum_{\ell: b_\ell = 1} \log p_{W_\ell}(y\mid 1) = -\sum_{\ell: b_\ell = 1} \lambda_\ell(y) + \text{const}(y).$ The decoder maximises the sum of log $q_{\rm BICM}$ across all $N$ received symbols over the codebook — equivalently, minimises $\sum_n \sum_{\ell: b_{n,\ell} = 1} \lambda_\ell(y_n)$.

The true likelihood is $p(y\mid x)$, which encodes the joint Euclidean geometry of $x$ relative to $y$. The product metric only uses the marginal per-position laws $p_{W_\ell}$, which average over the other $L-1$ bits. For $M \ge 16$ this averaging destroys information; the metrics differ on a set of positive probability.

$I^{\mathrm{GMI}}(s) = \mathbb{E}_{P_{X,Y}}[\log \frac{q(Y,X)^s} {\mathbb{E}_{\bar X}[q(Y, \bar X)^s]}]$.

At $q = p$, $s = 1$: the numerator is $p(y\mid x)$ and the denominator is $\mathbb{E}_{\bar X}[p(y\mid \bar X)] = \sum_{\bar x} P_X(\bar x) p(y\mid \bar x) = p(y)$. So $I^{\mathrm{GMI}}(1) = \mathbb{E}_{P_{X,Y}}[\log p(Y\mid X)/p(Y)] = I(X; Y)$, the classical mutual information. $\blacksquare$

$I^{\mathrm{GMI}}(s) = \sum_{\ell=0}^{L-1}\left[ s\, \mathbb{E}_{Y, B_\ell}[\log p_{W_\ell}(Y\mid B_\ell)] - \mathbb{E}_Y \log \tfrac{1}{2}\sum_{b\in\{0,1\}} p_{W_\ell}(Y\mid b)^s\right].$$The first term is linear in$s$; the second is$-\mathbb{E}Y \log \mathbb{E}B[p{W\ell}(Y\mid B)^s]$, i.e., negative log-MGF of$\log p_{W_\ell}(Y\mid B)$with respect to$B$.

For any random variable $Z$, $\log \mathbb{E}[e^{sZ}]$ is convex in $s$ (cumulant-generating function). So $\mathbb{E}_Y \log \tfrac{1}{2}\sum_b p_{W_\ell}(y\mid b)^s$ is convex in $s$, and its negative is concave in $s$. The linear first term preserves concavity, and summing over $\ell$ preserves it.

$I^{\mathrm{GMI}}_{\rm BICM}(s)$ is the sum of concave-in-$s$ terms, hence concave in $s > 0$. Its supremum is attained at an interior saddle-point $s^\star > 0$ satisfying $\partial I^{\mathrm{GMI}}/\partial s = 0$. $\blacksquare$

$\text{SNR} = 0$ dB $= 1$ linear, so $\beta = e^{-1} \approx 0.368$.

$R_0 = 1 - \log_2(1 + 0.368) = 1 - \log_2(1.368) \approx 1 - 0.452 = 0.548$ bits per code bit. For comparison, BI-AWGN capacity at 0 dB is $C(0\text{dB}) \approx 0.486$ bits — wait, this is below $R_0$, which seems wrong.

Let me recompute: actually at $\text{SNR} = 0$ dB linear, the BI-AWGN capacity is about $C(1) \approx 0.72$ bits (not $0.486$; I conflated with a different SNR). So $R_0 \approx 0.548 < 0.72$, consistent with $R_0 \le C$. $\blacksquare$

Correction note: the original reasoning's numerical hiccup shows why sanity checks ($R_0 \le C$) are important. The correct numerical values at 0 dB SNR for BI-AWGN are $\beta \approx 0.368$, $R_0 \approx 0.548$ bits, $C \approx 0.72$ bits.

Under Gray, the two BICM bit channels $W_0, W_1$ are both BI-AWGN with per-bit SNR equal to the symbol SNR (as in Example EQPSK with Gray Labelling: Two Identical Parallel BI-AWGN Channels).

From Thm. $s = 1$ Equals the CTB Capacity" data-ref-type="theorem">TBICM GMI at $s = 1$ Equals the CTB Capacity, $I^{\mathrm{GMI}}(1) = \sum_\ell I(Y; B_\ell) = 2 \times C_{\rm BI-AWGN}(\text{SNR})$. The GMI reduces exactly to twice the BI-AWGN capacity.

Since the per-position channels are identical symmetric BI-AWGN, the GMI$(s)$ curve is maximised at $s = 1$ (the matched-decoder scaling for BPSK). So $\sup_s I^{\mathrm{GMI}}(s) = I^{\mathrm{GMI}}(1) = 2 C_{\rm BI-AWGN}$. Gray-QPSK has zero BICM-to-CM gap: the mismatched decoder is matched for this constellation. $\blacksquare$

For $L$ independent parallel channels with Gallager functions $E_0^{(\ell)}(\rho)$, the joint Gallager function of the product channel is $E_0^{\rm parallel}(\rho) = \sum_\ell E_0^{(\ell)}(\rho)$ — a direct consequence of the factorisation of the product channel's transition law into the product of per-subchannel laws, and the multiplicativity of the integral over the product output space.

$R_0^{\rm parallel} = E_0^{\rm parallel}(1) = \sum_\ell E_0^{(\ell)}(1) = \sum_\ell R_0^{(\ell)}$, i.e., the sum of per-subchannel cutoff rates.

The BICM parallel-channel model has per-subchannel Bhattacharyya parameters $\beta_\ell = \sum_y \sqrt{p_{W_\ell}(y\mid 0) p_{W_\ell} (y\mid 1)}$. Each $W_\ell$ is binary-input, so $R_0^{(\ell)} = 1 - \log_2(1 + \beta_\ell)$. Summing gives $R_0^{\rm BICM} = \sum_\ell [1 - \log_2(1 + \beta_\ell)] = L - \sum_\ell \log_2(1 + \beta_\ell)$. $\blacksquare$

$\mathbb{E}[e^{\Lambda_n/2}] = \mathbb{E}_{Y, B}[\sqrt{p_{W_\ell}(Y\mid \bar B) / p_{W_\ell}(Y\mid B)}]$, where $\ell$ is the position of bit $n$. Using uniform $B$: $= \sum_y \tfrac{1}{2}[\sqrt{p_{W_\ell}(y\mid 0) p_{W_\ell}(y\mid 1) / p_{W_\ell}(y\mid 0)} + \sqrt{p_{W_\ell}(y\mid 0) p_{W_\ell}(y\mid 1) / p_{W_\ell}(y\mid 1)}]$ $= \sum_y \sqrt{p_{W_\ell}(y\mid 0) p_{W_\ell}(y\mid 1)} = \beta_\ell$.

If $n_\ell$ is the number of distinct bits at level $\ell$, the PEP is bounded by $P(\mathbf{c}\to\mathbf{c}') \le \prod_\ell \beta_\ell^{n_\ell}$. Averaged over the interleaver (which uniformly spreads the $d_H = \sum_\ell n_\ell$ distinct bits across the $L$ levels), this gives the classical Caire-Taricco-Biglieri union bound of Ch. 6.

The same derivation with general $s$ replaces $\beta_\ell$ by the $s$-tilted factor $\tilde\beta_\ell(s) = \mathbb{E}[(p/p)^s]$. Minimising over $s$ gives the MFC saddle-point bound of Thm. TMartinez-Fàbregas-Caire Saddle-Point PEP Bound. $\blacksquare$

Numerical evaluation at 12 dB, 16-QAM Gray:

• $C_{\rm CM} \approx 3.68$ bits/symbol (CM capacity)
• $C_{\rm BICM} \approx 3.64$ bits/symbol (CTB capacity)
• $R_0^{\rm CM} \approx 3.06$ bits/symbol (CM cutoff rate)
• $R_0^{\rm BICM} \approx 2.94$ bits/symbol (BICM cutoff rate)

$2.94 < 3.06 < 3.64 < 3.68$ — satisfies $R_0^{\rm BICM} < R_0^{\rm CM} < C_{\rm BICM} < C_{\rm CM}$, consistent with Thm. $R_0^{\mathrm{BICM}} \le R_0^{\mathrm{CM}}$ and $R_0 \le I$" data-ref-type="theorem">T$R_0^{\mathrm{BICM}} \le R_0^{\mathrm{CM}}$ and $R_0 \le I$.

$C_{\rm CM} - R_0^{\rm BICM} \approx 0.74$ bits/symbol. At this SNR, the capacity slope of 16-QAM is $\sim 0.08$ bits/dB, so the gap is $\sim 9$ dB of SNR-equivalent. This is the "sequential-decoder penalty" — BICM with a sequential decoder would need 9 dB more SNR to reach $C_{\rm CM}$. LDPC+BP eliminates this penalty entirely by operating above $R_0$.

$E_r(R) = \max_{0\le\rho\le 1} [E_0(\rho) - \rho R]$. At $\rho = 0$, the term is $E_0(0) - 0 = 0$. For $\rho > 0$ small, the term is $E_0'(0) \rho - R \rho + O(\rho^2) = (I^{\mathrm{GMI}} - R)\rho + O(\rho^2)$.

If $R = I^{\mathrm{GMI}}(s^\star)$ exactly, the first-order term vanishes and the second-order term ($E_0''(0) < 0$ by concavity of GMI in $s$, but here $\rho$'s second derivative is $E_0''(0)$ which is negative for concave $E_0$ — actually $E_0$ is convex in $\rho$, so $E_0''(0) \ge 0$; the maximum over $\rho$ of $E_0(\rho) - \rho R$ at $R = I^{\rm GMI}$ is attained at $\rho = 0$ with value 0).

$E_r^{\rm BICM}(I^{\mathrm{GMI}}(s^\star)) = 0$. The derivative at this rate is $\partial E_r/\partial R = -\rho^\star(R) = -0 = 0$ from the envelope theorem (but the slope in the limit from below is $-1$ because as $R$ decreases below the GMI, the optimal $\rho^\star \to 0^+$ linearly in $R - I^{\rm GMI}$, giving $dE_r/dR \to -1$). $\blacksquare$

Under Gray labelling, QPSK is exactly two independent BPSK channels (I and Q). The symbol channel $p(y\mid x)$ factors exactly into $p(y_I \mid b_0) p(y_Q \mid b_1)$ because the I and Q noises are independent and each bit controls only one component.

For Gray QPSK, $I(B_1; B_0 \mid Y) = 0$ because $B_0$ and $B_1$ are conditionally independent given $Y$. The chain-rule gap vanishes, so $C_{\rm CM} = C_{\rm BICM}$ and similarly $R_0^{\rm CM} = R_0^{\rm BICM}$.

Both cutoff rates are $2 [1 - \log_2(1 + e^{-\text{SNR}})] = 2 R_0^{\rm BPSK}$. They coincide because the two metrics (joint and product) coincide on this special structure. Gray QPSK is the only non-trivial constellation-labelling pair with this exact-matching property. $\blacksquare$

$\frac{\partial I^{\mathrm{GMI}}}{\partial s} = \mathbb{E}_{Y, B}[\log p_{W_\ell}(Y\mid B)] - \mathbb{E}_Y[\frac{\sum_b p_{W_\ell}(Y\mid b)^s \log p_{W_\ell}(Y\mid b)} {\sum_b p_{W_\ell}(Y\mid b)^s}]$. At $s = 1$, the second term is $\mathbb{E}_Y[\frac{\sum_b p_{W_\ell}(Y\mid b) \log p_{W_\ell}(Y\mid b)} {\sum_b p_{W_\ell}(Y\mid b)}]$ — the conditional entropy under the mixture distribution. For symmetric binary channels (high-SNR Gray QAM limit), this equals $-H(B\mid Y)$ evaluated on the $W_\ell$- channel, and the full first derivative reduces to $I(Y; B_\ell) - I(Y; B_\ell) = 0$.

$\frac{\partial^2 I^{\mathrm{GMI}}}{\partial s^2}\Big|_{s=1} = -\mathrm{Var}_Y[\log p_{W_\ell}(Y\mid \bar B) - \log p_{W_\ell}(Y\mid B)]$ under uniform $B$. This is a negative quantity (strict unless the per-position channel is noiseless or useless), giving $c_2 < 0$.

The curvature $c_2 < 0$ quantifies how sharply the GMI decays away from $s = 1$. At high SNR $|c_2|$ is small (curve nearly flat near the peak) and tuning $s$ gives negligible rate gain. At low SNR $|c_2|$ is larger and the peak is narrower — but also shifted away from $s = 1$, so tuning $s$ gains a bit of rate. This explains why the GMI scaling payoff is largest at low SNR. $\blacksquare$

$R_0^{\rm BICM} = \sum_{\ell=0}^{L-1} [1 - \log_2(1 + \beta_\ell)]$.

For 16-QAM Gray ($L = 4$): two bits with $\beta = 0.1$ give $[1 - \log_2(1.1)] \times 2 = [1 - 0.138] \times 2 = 1.72$. Two bits with $\beta = 0.25$ give $[1 - \log_2(1.25)] \times 2 = [1 - 0.322] \times 2 = 1.36$. Total: $R_0^{\rm BICM} \approx 3.08$ bits/symbol.

At 6 dB the 16-QAM capacity is about $3.3$ bits/symbol, so $R_0^{\rm BICM}/C_{\rm BICM} \approx 0.93$ — i.e., the cutoff rate is 93% of capacity at this SNR. At higher SNR this ratio drops (cutoff rate saturates below $\log_2 M$ while capacity grows). $\blacksquare$

A fundamental result of mismatched decoding (Ganti-Lapidoth-Telatar 1999, Thm. 1) states that $\sup_s I^{\mathrm{GMI}}(s; q) \le \sup_{P_X} I(X; Y)$ for any metric $q$. In our setting $P_X$ is fixed to uniform on $\mathcal{X}$, so the bound becomes $\sup_s I^{\mathrm{GMI}}(s; q_{\rm BICM}) \le I(X; Y) = C_{\rm CM}$.

Alternatively: the product metric is a deterministic function of $(y, x)$, so by the data-processing inequality any functional of the metric (including its log-likelihood ratio used by the decoder) carries at most as much information as $(y, x)$ — hence the achievable rate cannot exceed $I(X; Y) = C_{\rm CM}$.

Equality $\sup_s I^{\mathrm{GMI}}(s) = C_{\rm CM}$ holds iff the product bit metric is proportional to the joint likelihood $q_{\rm BICM}(y, x) \propto p(y\mid x)$ (up to a codeword- independent function of $y$). This is the Gray-QPSK case — and only that case — in our setting. For all other $(\mathcal{X}, \mu)$ the GMI is strictly below $C_{\rm CM}$. $\blacksquare$

$E_r(R)$ is the max over $\rho \in [0, 1]$ of $E_0(\rho) - \rho R$. The optimum $\rho^\star(R)$ decreases from $1$ (at small $R$) to $0$ (at $R = C$). Below the critical rate $R_{\rm crit}$ the optimum is $\rho^\star = 1$, and $E_r(R) = R_0 - R$ — a straight line. Above $R_{\rm crit}$, $\rho^\star < 1$ and $E_r(R)$ is a convex function reaching $0$ at $R = C$.

At $R = 0$, $E_r(0) = E_0(1) = R_0$. So $R_0$ is the value of the exponent at zero rate — the "exponential floor" of the exponent function.

For BI-AWGN at 3 dB: $C \approx 0.88$ bits, $R_0 \approx 0.82$ bits, $R_{\rm crit} \approx 0.55$ bits. The straight-line part goes from $(0, R_0)$ to $(R_{\rm crit}, R_0 - R_{\rm crit})$; the convex part from $(R_{\rm crit}, R_0 - R_{\rm crit})$ down to $(C, 0)$. This is the standard "two-hump" Gallager exponent shape. $\blacksquare$

5G NR QPSK supports code rates up to $\sim 0.95$, yielding $1.9$ bits/symbol at 3 dB. This exceeds $R_0^{\rm BICM}(3\text{dB}) = 1.63$ bits/symbol by $\sim 0.3$ bits/symbol — clearly above the Gallager cutoff.

Gallager's cutoff-rate theorem applies to maximum-metric decoders — those whose work per decoded bit grows with the number of codeword candidates examined. For a rate-$R$ code of blocklength $N$, that number is $2^{NR}$, and the expected work per bit diverges exponentially for $R > R_0$.

LDPC+BP is not in this complexity class. BP iterates over the edges of the factor graph. For a graph of degree-distribution fixed by the LDPC base graph, the number of edges is $O(N)$ independent of the code rate. The complexity per iteration is therefore $O(N)$, and convergence to a valid codeword requires $O(\log N)$ iterations in the threshold-scaling regime. Total work is $O(N \log N)$, polynomial in $N$ at any rate up to the density-evolution threshold — which is above $R_0$ and within $\sim 0.3$ dB of capacity.

The cutoff rate is a historical milestone in BICM analysis — the tight rate limit when sequential / list decoders were the standard. Modern BICM (with LDPC+BP) breaks through this limit; the operational question has become "can we approach the BICM GMI / CTB capacity?" and the answer for standard-compliant BICM is yes, within $\sim 0.3$ dB. The theoretical cleanup of §3–4 (GMI and random-coding exponent) remains the foundation, but the cutoff rate itself is informative rather than binding. $\blacksquare$

The BICM receiver uses $q_{\rm BICM}(y, x) = \prod_\ell p_{W_\ell}(y\mid b_\ell)$ instead of $p(y\mid x)$. This is a mismatched metric in the sense of Merhav-Kaplan-Lapidoth-Shamai 1994. The rate achievable by a random code with this mismatched decoder is the GMI $I^{\mathrm{GMI}}(s)$, not the CM mutual information.

The GMI is parameterised by a scaling $s > 0$; $\sup_s I^{\mathrm{GMI}}(s)$ is the largest achievable rate. For Gray-QAM at high SNR, $s^\star = 1$ and $I^{\mathrm{GMI}}(1)$ equals the CTB capacity — elevating the CTB formula from heuristic to rigorous. At low SNR or non-Gray labellings, $s^\star \ne 1$ and tuning $s$ gives a small rate boost.

Applying Gallager's random-coding machinery to the product metric yields a well-defined BICM exponent $E_r^{\rm BICM}(R)$, pointwise below the CM exponent $E_r^{\rm CM}(R)$. Under Gray the gap is small (exponent ratio $\gtrsim 0.85$); under SP it is large (ratio $\sim 0.5$). The exponent gap quantifies blocklength cost.

The GMI framework extends cleanly to block-fading channels (outage analysis reduces to per-symbol GMI) and to MIMO-BICM (the bit metric becomes a marginalised log-likelihood). Both are developed in subsequent chapters of the monograph (Ch. 6–8) and provide the theoretical toolkit for the MIMO / BICM-ID analyses of Chs. 8, 10 of this book.

All four contributions lean on the same mismatched-decoding scaffold: a product metric, a decoder scaling $s$, a GMI, and a Gallager-exponent refinement. The monograph's coherence is what makes it the canonical reference for BICM. $\blacksquare$

The GMI at $s = 1$ is $E_0'(\rho = 0)$ (the initial slope of $E_0$) while the cutoff rate is $E_0(\rho = 1)$ (the value of $E_0$ at $\rho = 1$). These two are not related by a simple subtraction; they are two different functionals of $E_0$.

By convexity of $E_0$ with $E_0(0) = 0$: $R_0 = E_0(1) \le E_0'(0) \cdot 1 = I^{\mathrm{GMI}}(1)$ (integrating the derivative). Equality holds only if $E_0'(\rho)$ is constant in $\rho$ — the degenerate zero-SNR case. At positive SNR, $R_0 < I^{\mathrm{GMI}}(1)$ strictly.

The gap $I^{\mathrm{GMI}}(1) - R_0$ grows with SNR. At low SNR it is a small fraction of the capacity; at moderate SNR ($\sim 10$ dB) it is roughly 20%; at high SNR ($\sim 20$ dB) it grows to 30–40%. There is no closed-form subtraction identity; the gap depends non-trivially on the channel through $E_0(\rho)$. $\blacksquare$