Ferkans — Interactive Telecom Tutor

Below the Cutoff, Decoders Have Work Exponential in Rate

The Gallager random-coding exponent of §4 treats the decoder as a maximum-metric decoder — the receiver computes the metric for every codeword in the codebook and picks the largest. That is conceptually clean but operationally expensive: the decoder's work is exponential in the blocklength times the rate. Real BICM decoders — LDPC belief propagation, sequential decoders, list decoders — are not of this type.

For sequential decoders on tree codes, Massey-Fano-Jelinek-Zigangirov showed in the 1960s that the practical rate limit is not the capacity but the cutoff rate $R_0 = E_0(1)$ : at rates $R < R_0$ , the expected decoder work per decoded bit is finite; at rates $R > R_0$ , the expected work diverges. For list decoders with list size growing polynomially in $N$ , the same threshold separates "polynomial work" from "exponential work". The cutoff rate is therefore the practical rate limit of any non-ML decoder on a binary-input channel, and its BICM specialisation $R_0^{\rm BICM}$ is the quantity every receiver designer cares about.

Beyond the cutoff rate, §5 also revisits the pairwise error probability (PEP) of a BICM codeword pair on a fading channel from Ch. 6. The classical Caire-Taricco-Biglieri 1998 union bound uses a Bhattacharyya-factor product over distinct bit positions; the improved bound of Martinez, Guillén i Fàbregas, and Caire 2006 replaces this with the GMI-tuned saddle-point at each distance, tightening the bound by 1–2 dB at moderate SNR. Both bounds share the same exponential order (same diversity, same coding gain), but the prefactor in the Martinez-Fàbregas-Caire bound is sharper — a direct benefit of the mismatched-decoding framework.

This section defines $R_0$ precisely, develops its BICM specialisation, compares it to the CM cutoff rate, and derives the saddle-point PEP bound. We close with engineering and pitfall remarks on what the cutoff rate does and does not mean for practical decoders.

,

Definition:
Gallager Cutoff Rate $R_0$

The cutoff rate of a memoryless channel $p(y\mid x)$ with input distribution $q$ is the value of Gallager's $E_0$ at $\rho = 1$ : $R_0(q) \;=\; E_0(\rho = 1, q) \;=\; -\log \!\int_y \!\Big( \sum_x q(x) \sqrt{p(y\mid x)} \Big)^{2}\, dy.$ Equivalently, for binary-input channels with uniform input, $R_0 \;=\; 1 - \log_2(1 + \beta), \quad \beta = \sum_y \sqrt{p(y\mid 0) p(y\mid 1)},$ where $\beta$ is the Bhattacharyya parameter of the channel. $R_0$ has units of bits per channel use under $\log_2$ , nats under $\ln$ .

For BICM with the product bit metric, the cutoff rate per symbol is $R_0^{\rm BICM} \;=\; \sum_{\ell = 0}^{L-1} [\, 1 - \log_2(1 + \beta_\ell)\, ], \qquad \beta_\ell = \sum_y \sqrt{p_{W_\ell}(y\mid 0) p_{W_\ell}(y\mid 1)}.$ This is just the parallel-channel cutoff-rate sum over the $L$ bit channels — a direct consequence of the parallel-channel decomposition of §1.

Operational meaning. For any decoder with polynomial complexity in the blocklength $N$ (sequential, list, threshold), the rate $R_0$ is the threshold above which the expected complexity grows exponentially in $R - R_0$ . Below $R_0$ , complexity is polynomial — or even linear for a well-tuned sequential decoder. This makes $R_0$ the practical rate limit of non-ML decoders.

Three comments on $R_0$ :

$R_0$ is always $\le$ capacity: $R_0 = E_0(1) \le E_0'(0) \cdot 1 = C$ by convexity of $E_0(\rho)$ with $E_0(0) = 0$ . At low SNR $R_0 \approx C$ ; at high SNR the gap grows but remains $O(C)$ .
Gallager thought $R_0$ was the "true" practical capacity until the invention of LDPC decoding in the late 1990s. LDPC+BP is an exception: it can operate above the cutoff rate with polynomial complexity, because its complexity depends on the graph sparsity, not on a search over codeword candidates. This is part of why LDPC
- BICM became standard.
Even so, $R_0^{\rm BICM}$ remains a useful sanity check: when a 5G NR LDPC decoder is reported to operate within 0.3–0.5 dB of Shannon, one can verify that the corresponding rate is above $R_0$ — confirming that the decoder is extracting information beyond the Gallager threshold.

,

Theorem: $R_0^{\mathrm{BICM}} \le R_0^{\mathrm{CM}}$ and $R_0 \le I$

For any memoryless channel and constellation $\mathcal{X}$ with labelling $\mu$ :

(i) Cutoff rate is $\le$ capacity: $R_0^{\rm BICM}(\mu) \;\le\; C_{\rm BICM}(\mu), \qquad R_0^{\rm CM} \;\le\; C_{\rm CM}.$ Both with equality only at zero SNR (trivial channel), and the gap grows as a fraction of capacity with SNR — reaching $\sim 30$ – $50\%$ of capacity at moderate SNR for QAM.

(ii) BICM cutoff rate $\le$ CM cutoff rate: $R_0^{\rm BICM}(\mu) \;\le\; R_0^{\rm CM},$ with equality at zero SNR and strict inequality for $M \ge 16$ at positive SNR. The ordering mirrors the capacity ordering of Ch. 5.

$R_0 = E_0(1)$ is a point evaluation of the Gallager function at $\rho = 1$ ; since $E_0^{\rm BICM}(\rho) \le E_0^{\rm CM}(\rho)$ pointwise (Thm. $\le$ $\leq$ CM Exponent" data-ref-type="theorem">TBICM Random-Coding Exponent $\le$ CM Exponent), the $\rho = 1$ values inherit the ordering. The capacity-vs-cutoff ordering is standard from Gallager's convexity argument.

Show Hint

Specialise Thm. $\le$ $\leq$ CM Exponent" data-ref-type="theorem">TBICM Random-Coding Exponent $\le$ CM Exponent to $\rho = 1$ to get $R_0^{\rm BICM} \le R_0^{\rm CM}$ .

Use convexity of $E_0$ in $\rho$ with $E_0(0) = 0$ and $E_0'(0) = I$ to get $R_0 \le C$ .

Proof

Cutoff $\le$ capacity

$E_0(\rho)$ is convex in $\rho \in [0, 1]$ with $E_0(0) = 0$ and $E_0'(0) = I$ . By convexity, $E_0(1) = E_0(0) + \int_0^1 E_0'(\rho)\, d\rho$ , and since $E_0'(\rho)$ is decreasing (by concavity of the GMI in $s$ ), $\int_0^1 E_0'(\rho)\, d\rho \le E_0'(0) \cdot 1 = I$ . Thus $R_0 = E_0(1) \le I = C$ , with equality only at channels where $E_0$ is linear (zero-SNR limit).

BICM $\le$ CM cutoff

Thm. $\le$ $\leq$ CM Exponent" data-ref-type="theorem">TBICM Random-Coding Exponent $\le$ CM Exponent gave $E_0^{\rm BICM}(\rho, 1) \le E_0^{\rm CM}(\rho)$ for all $\rho \in [0, 1]$ . Setting $\rho = 1$ yields $R_0^{\rm BICM} \le R_0^{\rm CM}$ directly.

Strict inequality

For $M \ge 16$ on AWGN at positive SNR, the chain-rule residual $\sum_{\ell=1}^{L-1} I(B_\ell; B_{<\ell}\mid Y) > 0$ , which propagates to $E_0^{\rm BICM}(1) < E_0^{\rm CM}(1)$ strictly — hence $R_0^{\rm BICM} < R_0^{\rm CM}$ strictly. $\blacksquare$

,

Three PEP Bounds at Fixed Hamming Distance $d_H$

Compare three different bounds on the pairwise error probability $P(\mathbf{c} \to \mathbf{c}')$ where $\mathbf{c}$ and $\mathbf{c}'$ differ in $d_H$ bit positions, for BICM on AWGN with 16-QAM and Gray labelling:

Caire-Taricco-Biglieri 1998 union bound (Ch. 6): a product of Bhattacharyya factors, one per distinct bit position.
Chernoff/union with scaling $s = 1$ : the GMI-style bound at the fixed decoder scaling.
Martinez-Fàbregas-Caire 2006 saddle-point bound: optimise the scaling $s$ at each $d_H$ to tighten the bound.

The saddle-point bound is 1–2 dB tighter than the union bound at moderate SNR for the same $d_H$ — a non-trivial improvement that makes PEP-based union bounds on BICM much more accurate than the classical ones. At high SNR and low SNR all three bounds converge to the same exponential order.

Parameters

Hamming distance

d_H

10

Theorem: Martinez-Fàbregas-Caire Saddle-Point PEP Bound

Let $\mathbf{c}, \mathbf{c}' \in \{0,1\}^{N}$ be two codewords differing in $d_H$ bit positions, transmitted over a BICM system with the product bit metric. The pairwise error probability satisfies $P(\mathbf{c} \to \mathbf{c}') \;\le\; \min_{s > 0}\; \prod_{n: c_n \ne c'_n} \mathbb{E}_{Y, B_\ell}\!\left[\, \Big(\frac{p_{W_\ell}(Y\mid \bar B_\ell)}{p_{W_\ell}(Y\mid B_\ell)}\Big)^{s} \right],$ where $\bar B_\ell = 1 - B_\ell$ is the complementary bit at position $\ell$ , and the product runs over the $d_H$ distinct bit positions. The minimisation over $s > 0$ is the saddle-point optimisation.

At $s = 1/2$ this reduces to the Bhattacharyya-factor product of the Caire-Taricco-Biglieri 1998 bound; optimising over $s$ gives the tighter Martinez-Fàbregas-Caire 2006 bound. The improvement is $\sim 1$ – $2$ dB at moderate $d_H$ and moderate SNR; at large $d_H$ the saddle-point approaches $s = 1/2$ and the improvement vanishes.

The classical union bound uses a Chernoff-type tilt at $s = 1/2$ — the "neutral" choice that symmetrically weights the two codewords. The saddle-point argument optimises the tilt per distance: for short distances (where the decoder's "surprise" is largest) the optimal $s$ is smaller, placing more weight on the transmitted codeword; for long distances, $s$ approaches $1/2$ and the bound reduces to the Bhattacharyya form. The GMI framework naturally provides this tilt optimisation as part of the same machinery used for capacity.

Show Hint

Apply a Chernoff bound to $\Pr\{\sum_n \log \text{metric-ratio}_n \ge 0\}$ with tilt parameter $s$ .

Recognise the per-position expectation as the $s$ -tilted Bhattacharyya-like factor.

Optimise $s$ to tighten the bound, obtaining the saddle-point form.

Proof

Chernoff bound on the PEP

Define the per-position metric-ratio $\Lambda_n = \log \frac{q_{\rm BICM}(y_n, \bar x_n)}{q_{\rm BICM}(y_n, x_n)}$ for bit positions where $c_n \ne c'_n$ (zero elsewhere). The PEP is $P(\mathbf{c} \to \mathbf{c}') = \Pr\!\big\{\sum_n \Lambda_n \ge 0\big\}.$ For any $s > 0$ , Chernoff gives $\Pr\!\big\{\sum_n \Lambda_n \ge 0\big\} \le \mathbb{E}[e^{s\sum_n \Lambda_n}] = \prod_n \mathbb{E}[e^{s \Lambda_n}].$

Evaluate per-position factor

For bit positions $n$ where $c_n = c'_n$ , $\Lambda_n = 0$ and the factor is 1. For the $d_H$ distinct positions, $\mathbb{E}[e^{s \Lambda_n}] = \mathbb{E}_{Y, B_\ell}\!\left[\Big(\frac{p_{W_\ell}(Y\mid \bar B_\ell)} {p_{W_\ell}(Y\mid B_\ell)}\Big)^{s}\right].$ Taking the product over the $d_H$ positions gives the product form in the theorem statement.

Saddle-point optimisation

The bound holds for every $s > 0$ , so the tightest bound is the $s$ -optimised one. Call the optimum $s^\star(d_H)$ . This value depends on $d_H$ , the channel, and the labelling. For fixed SNR and Gray, $s^\star(d_H)$ varies smoothly from $\sim 0.3$ at $d_H = 4$ to $\sim 0.5$ at $d_H = 30$ — approaching the Bhattacharyya tilt at large distances.

Reduction to CTB union bound

At $s = 1/2$ , the per-position factor reduces to the standard Bhattacharyya parameter $\beta_\ell = \mathbb{E}_Y[\sqrt{p_{W_\ell} (Y\mid 0) p_{W_\ell}(Y\mid 1)}]$ . The product over $d_H$ distinct positions is then $\prod_\ell \beta_\ell^{n_\ell}$ where $n_\ell$ is the number of distinct positions at level $\ell$ — the Caire-Taricco-Biglieri union-bound form from Ch. 6 Thm. [?ch06:thm-bicm-union-bound]. The saddle-point bound tightens this by allowing $s \ne 1/2$ . $\blacksquare$

,

Example: Saddle-Point vs Union Bound: 16-QAM Gray at 8 dB, $d_H = 10$

For BICM with 16-QAM Gray labelling on AWGN at $\text{SNR} = 8$ dB and Hamming distance $d_H = 10$ , compute (i) the CTB union-bound PEP, (ii) the MFC saddle-point PEP, and (iii) compare the two in dB of SNR margin.

Solution

Bhattacharyya factor at $s = 1/2$

For 16-QAM Gray at 8 dB linear ( $\text{SNR} \approx 6.3$ ), the per-position Bhattacharyya factors are approximately $\beta_0 = \beta_2 \approx 0.07$ (outer bits, high SNR) and $\beta_1 = \beta_3 \approx 0.18$ (inner bits, effectively lower SNR). Averaging uniformly over bit positions gives $\bar\beta \approx 0.13$ . The CTB union bound for $d_H = 10$ is $P^{\rm CTB}_{\rm pair} \le \bar\beta^{10} = 0.13^{10} \approx 1.4 \times 10^{-9}$ .

Saddle-point at optimised $s$

Numerical saddle-point search gives $s^\star \approx 0.42$ for this distance. The per-position factor at $s^\star = 0.42$ is slightly smaller than at $s = 1/2$ , say $\tilde\beta(s^\star) \approx 0.11$ . The MFC bound is $\tilde\beta^{10}(s^\star) \approx 2.6 \times 10^{-10}$ — about 5 $\times$ tighter than the union bound.

Convert to SNR margin

At this SNR, a factor of 5 in PEP corresponds to about 0.8–1 dB of SNR (via the Q-function slope). So the MFC saddle-point bound tightens the union bound by $\sim 1$ dB. For a union bound over many $d_H$ values in a full codeword error estimate, this $\sim 1$ dB reduction propagates and can mean the difference between being within or outside the standard performance target.

Large-$d_H$ convergence

As $d_H \to \infty$ , $s^\star \to 1/2$ (the symmetric Chernoff tilt) and the MFC bound reduces to the CTB bound. The improvement is therefore distance-dependent: largest at moderate $d_H$ , vanishing at large $d_H$ . This is consistent with the classical Bhattacharyya bound being asymptotically tight at long distances.

,

Common Mistake: Cutoff Rate Is Not Capacity

Mistake:

Quoting $R_0^{\rm BICM}$ as the "BICM capacity" or assuming that LDPC+BP decoders cannot operate at rates above $R_0$ .

Correction:

The cutoff rate $R_0$ is not the capacity. It is a tighter rate threshold for a specific class of decoders — namely those whose decoding complexity grows with the number of candidate codewords examined per information bit (sequential, list, threshold decoders). For these decoders, above $R_0$ the expected complexity diverges exponentially in $R - R_0$ .

LDPC + belief propagation is NOT in this class. BP complexity is proportional to the number of edges in the factor graph, which is $O(N)$ independent of rate (for fixed graph density). BP therefore can operate above the cutoff rate — in fact, at rates within $\sim 0.3$ dB of capacity in 5G NR, well above $R_0^{\rm BICM}$ . The invention of LDPC in the 1990s is what retired the cutoff rate as "the practical capacity"; the practical capacity is now (nearly) the Shannon capacity.

So when you see $R_0$ quoted in a paper, ask:

What decoder architecture is the paper about?
If the answer is "LDPC+BP", then $R_0$ is a historical curiosity — informative but not operational.
If the answer is "sequential" or "list" or "polar-SCL with small list", then $R_0$ is the tight operational limit below which complexity stays polynomial.

🔧Engineering Note

5G NR LDPC Decoders Operate Above the Cutoff Rate

Every 5G NR LDPC decoder operates above the Gallager cutoff rate of the BICM channel. For QPSK at 3 dB, $R_0^{\rm BICM} \approx 1.63$ bits/symbol (Example ECutoff Rate of BICM-QPSK at 3 dB); the typical 5G NR QPSK operating rate is $\sim 1.7$ bits/symbol (code rate 0.85, QPSK spectral efficiency 2, giving 1.7). LDPC's density-evolution capacity is within $\sim 0.3$ dB of Shannon, which is well above $R_0$ .

This is why the cutoff rate is, in the 5G design process, a sanity check, not a design constraint. The design constraint is the density-evolution threshold of the chosen LDPC base graph on the BICM channel, which determines the achievable rate under BP decoding. That threshold is computed on the mixture-channel LLR histogram, and is the quantity a 5G LDPC designer actually optimises.

The cutoff-rate sanity check is useful when diagnosing simulation behaviour: if a decoder is reported to operate at $R \gg R_0$ with low error probability, this confirms the decoder is extracting information beyond the Gallager threshold — a hallmark of modern iterative / message-passing decoders. If instead the decoder is reported to work only at $R \le R_0$ , it is likely a sequential or list-type decoder and the cutoff rate is doing real operational work.

Practical Constraints

•
$R_0^{\rm BICM}$ is below practical 5G NR LDPC operating rates
•
Density-evolution threshold (not cutoff rate) is the design target for LDPC
•
For sequential decoders (polar SCL with small list), the cutoff rate is tight
•
$R_0$ is useful as a diagnostic when comparing decoder architectures

📋 Ref: 3GPP TS 38.212, §5.1

,

Common Mistake: Saddle-Point Is a Provable Upper Bound, Not an Exact PEP

Mistake:

Interpreting the Martinez-Fàbregas-Caire saddle-point bound as an exact PEP expression or as a lower bound on PEP.

Correction:

Both the CTB union bound and the MFC saddle-point bound are upper bounds on the pairwise error probability. The saddle-point tightens the Chernoff exponent but does not achieve equality; at finite blocklength the actual PEP is still below both bounds, often by $1$ – $2$ dB at the SNRs of interest. To match simulation, one typically uses the MFC bound plus a small correction term (or fits directly to the simulated PEP curve).

In particular, the MFC bound is a union bound in spirit: it is tight on the codeword-pair-level event, but a codeword-error event is a union over many pairs, and the union bound can loosen further as the list of pairs grows. For low error rates the MFC bound is tight; near the waterfall region the union bound component dominates and the bound loosens by 1–3 dB.

Historical Note: Martinez-Fàbregas-Caire 2006: Sharpening the BICM PEP

2006

The 2006 IEEE Transactions on Information Theory paper of Alfonso Martinez, Albert Guillén i Fàbregas, and Giuseppe Caire — "Error probability analysis of bit-interleaved coded modulation" — is the companion analysis paper to the 2008 Foundations & Trends monograph. It derives the saddle-point PEP bound of Thm. TMartinez-Fàbregas-Caire Saddle-Point PEP Bound and shows that it tightens the classical Caire-Taricco-Biglieri 1998 union bound by $\sim 1$ – $2$ dB at moderate SNR.

The paper's contribution is twofold. First, it exhibits the exact saddle-point $s^\star(d_H)$ as a function of Hamming distance — a numerical knob that the 1998 paper had not optimised. Second, it demonstrates that the improved bound tracks simulation far more closely than the union bound — to within a few tenths of a dB at $P_e \sim 10^{-5}$ . This makes the MFC bound the practical PEP bound used in modern BICM analyses; the CTB union bound is retained for its simplicity (single evaluation at $s = 1/2$ ) when rough estimates suffice.

Methodologically, the 2006 paper is the first concrete demonstration that the mismatched-decoding GMI framework (then being developed for the 2008 monograph) pays numerical dividends beyond the information-theoretic cleanup. The $s$ -optimisation that gives the exact achievable rate in §3 also gives the sharpest PEP bound in §5 — the framework is internally coherent.

Why This Matters: From Cutoff Rate to BICM-ID: Closing the Gap

Chapter 7's takeaway is that BICM — at one-shot demapping — has a rate gap to CM of $\lesssim 0.3$ dB on Gray-QAM, an exponent ratio of $\sim 0.85$ , and a PEP improvement of $\sim 1$ dB via the MFC saddle-point. All three quantities can be further improved by iterative demapping + decoding, where the binary decoder's extrinsic LLRs are fed back to the demapper for a second pass through the per-symbol likelihood computation.

BICM-ID — the subject of Chapter 8 — closes the product-metric mismatch by making the demapper posterior conditioned on the current LLRs of the other bits. In the limit of perfect extrinsic information, BICM-ID's demapper computes the full joint symbol likelihood; i.e., the iterative system eliminates the mismatched- decoding penalty entirely. The penalty for this gain is complexity (multiple demapper passes) and the need for set-partition labelling rather than Gray (because iterative feedback needs structural separation between bits). Chapter 8 develops the EXIT-chart analysis and the code-design implications.

Forward reference: the GMI saddle-point of this chapter and the EXIT chart of Ch. 8 are two sides of the same coin. The GMI parameterises single-pass BICM rate; the EXIT chart parameterises iterative BICM-ID rate. Both are mismatched-decoding quantities; both reduce to CM capacity as the mismatch vanishes (at high SNR for GMI, at full iteration for EXIT).

Quick Check

The cutoff rate $R_0^{\mathrm{BICM}}$ is

the practical rate limit of sequential / list decoders, above which decoder complexity grows exponentially in $R - R_0$

the BICM capacity minus a fixed gap of 3 dB

the rate above which the error probability is always 1

the rate at which the BICM mismatched decoder achieves the same PEP as the CM matched decoder

Correction:

the practical rate limit of sequential / list decoders, above which decoder complexity grows exponentially in

R - R_0

This is the operational meaning of the cutoff rate. For sequential (Fano, stack) and list (Forney) decoders, $R_0 = E_0(1)$ is the rate threshold that separates polynomial from exponential expected work. LDPC+BP is a notable exception that can operate above $R_0$ .

Quick Check

The Martinez-Fàbregas-Caire saddle-point PEP bound is tighter than the Caire-Taricco-Biglieri union bound because

it optimises the Chernoff tilt $s$ at each Hamming distance rather than fixing $s = 1/2$ (Bhattacharyya)

it uses a different channel model (block fading instead of i.i.d.)

it accounts for BICM-ID iterative feedback

it assumes Gray labelling and a specific constellation

Correction:

it optimises the Chernoff tilt

s

at each Hamming distance rather than fixing

s = 1/2

(Bhattacharyya)

Both bounds are Chernoff-type. The CTB bound fixes $s = 1/2$ , giving a Bhattacharyya-factor product. The MFC bound optimises $s$ per-distance, giving a tighter bound especially at short $d_H$ . This is the content of Thm. TMartinez-Fàbregas-Caire Saddle-Point PEP Bound.

Cutoff Rate $R_0$

The Gallager function evaluated at $\rho = 1$ : $R_0 = E_0(1) = -\log \int_y (\sum_x q(x)\sqrt{p(y\mid x)})^2 dy$ . For binary-input channels with uniform input, $R_0 = 1 - \log_2(1 + \beta)$ where $\beta$ is the Bhattacharyya parameter. Operationally, the rate threshold above which sequential and list decoders have exponential expected complexity.

Bhattacharyya Parameter $\beta$

For a binary-input channel, $\beta = \sum_y \sqrt{p(y\mid 0) p(y\mid 1)}$ — a scalar in $[0, 1]$ characterising the discriminability of the two inputs. $\beta = 0$ : perfectly discriminable (zero-SNR noise limit is $\beta = 1$ , noiseless limit is $\beta = 0$ ). The Bhattacharyya parameter controls the Chernoff PEP bound at $s = 1/2$ and the cutoff rate via $R_0 = 1 - \log_2(1 + \beta)$ .

Saddle-Point PEP Bound (Martinez-Fàbregas-Caire 2006)

The PEP bound $P(\mathbf{c}\to\mathbf{c}') \le \min_s \prod_n \mathbb{E}[ (p_{W_\ell}(y\mid \bar b)/p_{W_\ell}(y\mid b))^s]$ , where the minimum is over the decoder scaling $s$ and the product runs over distinct bit positions. Tightens the classical $s = 1/2$ Bhattacharyya bound by $\sim 1$ – $2$ dB at moderate SNR; reduces to the classical bound at $s^\star = 1/2$ for long distances.

Cutoff Rate and Practical PEP Bounds

Below the Cutoff, Decoders Have Work Exponential in Rate

Definition: Gallager Cutoff Rate R0R_0R0​

Theorem: R0BICM≤R0CMR_0^{\mathrm{BICM}} \le R_0^{\mathrm{CM}}R0BICM​≤R0CM​ and R0≤IR_0 \le IR0​≤I

Cutoff $\le$ capacity

BICM $\le$ CM cutoff

Strict inequality

Three PEP Bounds at Fixed Hamming Distance dHd_HdH​

Parameters

Theorem: Martinez-Fàbregas-Caire Saddle-Point PEP Bound

Chernoff bound on the PEP

Evaluate per-position factor

Saddle-point optimisation

Reduction to CTB union bound

Example: Saddle-Point vs Union Bound: 16-QAM Gray at 8 dB, dH=10d_H = 10dH​=10

Bhattacharyya factor at $s = 1/2$

Saddle-point at optimised $s$

Convert to SNR margin

Large-$d_H$ convergence

Common Mistake: Cutoff Rate Is Not Capacity

5G NR LDPC Decoders Operate Above the Cutoff Rate

Common Mistake: Saddle-Point Is a Provable Upper Bound, Not an Exact PEP

Historical Note: Martinez-Fàbregas-Caire 2006: Sharpening the BICM PEP

Why This Matters: From Cutoff Rate to BICM-ID: Closing the Gap

Quick Check

Quick Check

Cutoff Rate R0R_0R0​

Bhattacharyya Parameter β\betaβ

Saddle-Point PEP Bound (Martinez-Fàbregas-Caire 2006)

Definition:
Gallager Cutoff Rate $R_0$

Theorem: $R_0^{\mathrm{BICM}} \le R_0^{\mathrm{CM}}$ and $R_0 \le I$

Three PEP Bounds at Fixed Hamming Distance $d_H$

Example: Saddle-Point vs Union Bound: 16-QAM Gray at 8 dB, $d_H = 10$

Cutoff Rate $R_0$

Bhattacharyya Parameter $\beta$