Ferkans — Interactive Telecom Tutor

From a Single PEP to the Bit Error Probability

Theorems 1 and 3 bounded the pairwise error probability $P(d)$ for two BICM codewords at Hamming distance $d$ . A real receiver, however, faces ALL competing codewords at once. The passage from "one PEP" to "codeword error probability" is the union bound, and from "codeword error probability" to "bit error probability" is a weight-enumerator weighted sum. In this section we assemble those two bounds into the standard BICM union-bound BER formula, discuss where it is tight (error floor) and where it is loose (waterfall), and flag tighter alternatives (Poltyrev, sphere packing) that will be developed in Ch. 7.

Definition:
Weight Enumerator and Input-Weight Multiplicities

For a binary linear code $\mathcal{C}$ of block length $n$ and dimension $k$ , the weight enumerator is $W(z) = \sum_{d = 0}^n W_d z^d, \qquad W_d = |\{\mathbf{c} \in \mathcal{C} : \text{wt}(\mathbf{c}) = d\}|.$ For a convolutional code, the relevant quantity for BER analysis is the input-weight enumerator $T(z, I) = \sum_{d} c_d(I) z^d,$ where $c_d$ is the number of information bits in error per weight- $d$ error event. We write $c_d$ for $\sum_I I \cdot c_d(I)$ — the total input-weight contribution of weight- $d$ error events.

For a rate- $1/2$ , constraint-length- $5$ convolutional code (generators $(23, 35)_{\rm oct}$ ), the transfer-function analysis of Viterbi (1971) gives $d_{\rm free} = 7$ and $c_7 = 4$ . For LDPC codes, $W_d$ can be estimated by saddlepoint methods or density evolution — see [?mackay-2003].

,

Theorem: Union-Bound Bit Error Probability for BICM

Consider a BICM system with binary code $\mathcal{C}$ of rate $R = k/n$ and weight enumerator $W_d$ (or input-weight multiplicities $c_d$ for convolutional codes). Under maximum-likelihood decoding on fully-interleaved Rayleigh fading with Gray labelling, the bit error probability is bounded by $\boxed{\; P_b \le \frac{1}{k} \sum_{d = d_H}^{n} W_d \cdot c_d \cdot P(d), \;}$ where $P(d)$ is the diversity- $d$ PEP given by Thm. 3 of s03. At high SNR this simplifies to $P_b \approx \frac{W_{d_H} \cdot c_{d_H}}{k} \cdot P(d_H) \propto \text{SNR}^{-d_H \cdot L_{\min}(\mu)}.$

Each pair at Hamming distance $d$ contributes $P(d)$ , weighted by the number of such pairs ( $W_d$ ) and the expected number of information-bit errors they cause ( $c_d / k$ per source bit on average). Summing over $d$ gives the union bound. At high SNR only the smallest- $d$ term matters; at low SNR every term contributes comparably and the bound becomes loose.

Show Hint

Start from the codeword error probability bound $P_e \le \sum_{\mathbf{c}, \hat{\mathbf{c}}} P(\mathbf{c} \to \hat{\mathbf{c}})$ and convert the double sum into a sum over pairs at each Hamming distance.

A pair at Hamming distance $d$ contributes $c_d$ information-bit errors on average (by the assumption that the all-zero codeword is transmitted, valid for linear codes).

Group terms: $\sum_{\text{pairs at dist } d} 1 = W_d$ in the block-code case, or $c_d \cdot k$ in the convolutional-code case.

Divide by $k$ to convert from codeword-error bits to information-bit error rate.

Proof

Step 1: From pairwise to codeword error

For a linear code, the all-zero assumption is WLOG. The union bound over nonzero codewords gives $P_e \le \sum_{\mathbf{c} \in \mathcal{C} \setminus \{0\}} P(\mathbf{0} \to \mathbf{c}).$ Group by Hamming weight: $P_e \le \sum_{d = d_H}^n W_d \cdot P(d).$

Step 2: From codeword error to bit error

Each codeword at distance $d$ contains some number $I(\mathbf{c})$ of information-bit errors out of the $k$ information bits. By the linearity of the code, $I$ depends only on the weight and the code's structure, and its expectation over weight- $d$ codewords is $c_d / W_d$ . Therefore $P_b = \frac{\mathbb{E}[\text{number of info-bit errors}]}{k} \le \frac{1}{k} \sum_d W_d \cdot \frac{c_d}{W_d} \cdot P(d) \cdot W_d = \frac{1}{k} \sum_d W_d c_d P(d),$ which is the theorem. (In the convolutional-code literature $W_d$ is absorbed into $c_d$ ; the formula there is $P_b \le \frac{1}{k} \sum_d c_d P(d)$ directly.)

Step 3: High-SNR leading term

By Thm. 3 of s03, $P(d) \sim \text{SNR}^{-d \cdot L_{\min}(\mu)}$ at high SNR. The smallest $d = d_H$ dominates, and $P_b \approx \frac{W_{d_H} c_{d_H}}{k} \text{SNR}^{-d_H L_{\min}(\mu)}.$ The coefficient $W_{d_H} c_{d_H} / k$ is the bit-error multiplicity at the error floor; its inverse (in dB) is the coding gain relative to an uncoded reference with the same diversity order. $\blacksquare$

,

Example: Union Bound for a Rate-1/2, $d_{H,{\rm free}} = 7$ Convolutional BICM

The rate- $1/2$ , constraint-length- $5$ convolutional code has input-weight multiplicities (from the transfer function): $c_7 = 4, \; c_8 = 12, \; c_9 = 20, \; c_{10} = 72, \; c_{11} = 225, \ldots$ Compute the union-bound BER for this code with Gray-16-QAM BICM on fully-interleaved Rayleigh fading at $E_s/N_0 = 15 \text{ dB}$ and compare with the leading-term approximation.

Solution

Per-$d$ PEP on Rayleigh

Under the MGF-based PEP, the Rayleigh PEP at diversity order $d$ with per-channel SNR $\gamma = E_s/N_0$ is $P(d) \approx \binom{2d - 1}{d} \left(\frac{1}{4 \gamma}\right)^d$ (the standard high-SNR Rayleigh result for diversity $d$ , [?proakis-2008] §14.4). At $\gamma = 15 \text{ dB} = 31.6$ (linear), $4 \gamma = 126.4$ .

Evaluate first few terms

$d = 7$ : $P(7) \approx \binom{13}{7}(1/126.4)^7 \approx 1716 \cdot 2.0 \times 10^{-15} \approx 3.4 \times 10^{-12}$ .
$d = 8$ : $P(8) \approx \binom{15}{8}(1/126.4)^8 \approx 6435 \cdot 1.6 \times 10^{-17} \approx 1.0 \times 10^{-13}$ .
$d = 9$ : $P(9) \approx 48620 \cdot 1.3 \times 10^{-19} \approx 6.3 \times 10^{-15}$ .
$d = 10, 11$ : contribute proportionally smaller amounts.

Union-bound sum (convolutional form, $k = 1$)

$P_b \le c_7 P(7) + c_8 P(8) + c_9 P(9) + c_{10} P(10) + \ldots \approx 4 \cdot 3.4 \times 10^{-12} + 12 \cdot 1.0 \times 10^{-13} + 20 \cdot 6.3 \times 10^{-15} + \ldots$ \approx 1.4 \times 10^{-11} $— dominated by the$ d = 7$ term.

Leading-term approximation

The leading-term approximation is $P_b \approx c_7 P(7) \approx 1.4 \times 10^{-11}.$ Within 5% of the full union bound at this SNR. The leading term becomes increasingly accurate as SNR grows, because each higher- $d$ contribution decays a full extra power of $\text{SNR}$ faster.

Example: Where the Union Bound Goes Loose

A binary code has $W_{d_H} = 10^6$ codewords at minimum distance $d_H = 20$ . On Rayleigh fading with diversity order $d_{\rm BICM} = 20$ , compute the union-bound PEP at the SNR where the true codeword error probability is $0.5$ . What does this tell us about the union bound?

Solution

Leading-term union bound

Under $P(d_H) \approx (1/(4 \gamma))^{d_H}$ at high SNR, and ignoring the binomial prefactor for simplicity, $\text{UB} \approx W_{d_H} \cdot (1/(4 \gamma))^{d_H}.$ At the true $P_e = 0.5$ operating point, the union bound is not operating in the "high-SNR" regime — numerical evaluation easily gives $\text{UB} \gtrsim 1$ , which is trivially true but completely uninformative.

Interpretation: waterfall is not where the UB lives

The union bound is exponentially tight at the error floor where the leading-PEP-term dominates. In the waterfall region (where $P_e$ is in the range $10^{-1}$ to $10^{-3}$ ), many codewords contribute comparably and the union-bound addition over-counts by several orders of magnitude. The reader should not trust the union bound to within an order of magnitude until the true BER is below ~ $10^{-5}$ .

What to use instead for the waterfall

Tighter bounds — Poltyrev (1994), Divsalar (1999), tangential-sphere bound, or exact density-evolution for LDPC codes — become necessary in the waterfall region. These are developed for BICM in Ch. 7 (error exponents and cutoff rate). For engineering BER targets at $10^{-5}$ and below, the leading-term union bound is adequate.

Common Mistake: The Union Bound Is NOT a BER Estimate at the Waterfall

Mistake:

A very common mistake in BICM performance studies is to plot the leading- PEP-term union bound and read it as an accurate prediction of simulated BER, especially in the waterfall region around $10^{-2}$ to $10^{-4}$ . At these BERs the union bound can exceed $1$ (i.e., be trivial) even when the true BER is $10^{-2}$ .

Correction:

Reserve the union bound for the error floor region, typically below $10^{-5}$ BER, where the leading PEP term dominates and the bound becomes exponentially tight. For the waterfall region, use either (a) Monte Carlo simulation, (b) the tighter bounds of Ch. 7, or (c) density evolution / EXIT analysis for specific code families. Never report the union bound as a BER at $10^{-2}$ — it is not a predictor there, only an upper bound (and often a laughably loose one).

Common Mistake: Upper Bound vs Actual: PEP Is $P_{\rm pairwise}$ , Not BER

Mistake:

When computing the PEP $P(d)$ for a specific $d$ , students sometimes read this directly as "the BER at that diversity order."

Correction:

$P(d)$ is the probability of confusing ONE specific pair of codewords at distance $d$ . The BER aggregates over ALL competing codewords (the $W_d c_d / k$ weighting in Thm. 4) and over information-bit counts. The BER is strictly smaller than a single PEP times the number of codewords only because the union over disjoint events can over-count; it is strictly larger than a single PEP because many pairs contribute. The union bound gives a valid UPPER bound on BER in terms of the PEP.

Union Bound vs Tighter BER Bounds

Compare the leading-term union bound $P_b \approx \frac{c_{d_H}}{k} (4\text{SNR})^{-d_H}$ against (a) the full union bound summing $c_d$ for $d = d_H, d_H + 1, \ldots$ , and (b) a tighter Poltyrev-style bound that is valid in the waterfall region. Adjust $d_H$ and the multiplicity $c_d$ to see how the gap evolves. Key observation: the bounds converge below ~ $10^{-5}$ BER but diverge sharply in the waterfall — which is exactly the regime where simulation is essential.

Parameters

d_H

10

Multiplicity

c_d

1

Union-Bound BER Computation for Convolutional BICM

Complexity:

O(|\gamma| \cdot D)

— essentially free after the transfer function is computed

Input: Convolutional code transfer function

T(z, I) = \sum c_d(I) z^d

,

diversity order

d_{\rm div} = d_H L_{\min}(\mu)

, SNR grid

\{\gamma_i\}

,

labelling

\mu

, truncation order

D

.

Output: Union-bound BER curve

P_b(\gamma)

.

1. For each

\gamma

in the grid:

2.

\quad P_b \leftarrow 0

3.

\quad

for

d = d_H, d_H + 1, \ldots, D

do

4.

\qquad

Compute diversity-

d

PEP:

P(d) \leftarrow \binom{2d-1}{d} (4\gamma)^{-d L_{\min}(\mu)}

5.

\qquad

Lookup

c_d

from transfer function

6.

\qquad P_b \leftarrow P_b + c_d \cdot P(d) / k

7.

\quad

end for

8.

\quad

Record

(\gamma, P_b)

9. Return: curve

\{(\gamma_i, P_{b,i})\}

The truncation order $D$ is chosen so that the tail $\sum_{d > D} c_d P(d)$ is a negligible fraction of the dominant term $c_{d_H} P(d_H)$ . For Rayleigh fading at moderate SNR ( $> 10 \text{ dB}$ ), $D = d_H + 10$ is safely more than enough. At low SNR (waterfall), one may need $D = n$ (the entire block length), at which point the bound is anyway loose by orders of magnitude and simulation is preferred.

Why This Matters: LDPC Codes and the Union Bound: When It Breaks

For LDPC codes (used in LTE, 5G NR, DVB-S2, Wi-Fi 6), the weight enumerator $W_d$ is effectively random over the ensemble and $d_H$ is typically small (5–15 for practical block lengths). The union bound predicts an error floor at BER $\sim 10^{-4}$ , but modern short-block LDPC codes achieve $10^{-5}$ BER at SNRs where the union bound is loose by $3$ – $5$ dB. The gap between union-bound prediction and simulated BER in the waterfall is closed by density-evolution analysis, which tracks the message distribution iteratively through the Tanner graph. This is the right analytical tool for modern coded systems; the union bound of this section is the foundational framework but not the final tool.

Quick Check

At very high SNR on fully-interleaved Rayleigh fading, the BICM union bound $P_b \le \frac{1}{k} \sum_d W_d c_d P(d)$ is dominated by which term?

The term at the BLOCK LENGTH $d = n$

The term at $d = d_H$ (minimum Hamming distance)

The term at $d = k$ (information dimension)

The term at $d = L_{\min}(\mu)$

Correction:

The term at

d = d_H

(minimum Hamming distance)

$P(d) \sim \text{SNR}^{-d L_{\min}(\mu)}$ , so the smallest $d$ gives the slowest decay. At high SNR, $P_b \approx \frac{W_{d_H} c_{d_H}}{k} (4\text{SNR})^{-d_H L_{\min}(\mu)}$ .

⚠️Engineering Note

5G NR: Does the Union Bound Match Simulation?

5G NR uses a base-graph-2 LDPC code of effective rate between $0.3$ and $0.95$ after rate matching. For a representative 1024-bit code block at rate $1/2$ , the simulated BER at $E_s/N_0 = 3$ dB on Rayleigh fading is $\sim 10^{-2}$ , while the union-bound prediction (leading term, $d_H \approx 10$ for this ensemble) is $\sim 10^{-1}$ — off by an order of magnitude. At $6 \text{ dB}$ , simulated BER is $\sim 10^{-5}$ and the union bound predicts $\sim 2 \times 10^{-5}$ — within a factor of 2. 3GPP system-level simulators use the union bound for SNR targets in the error floor and Monte Carlo (plus extrapolation from short-block BER tables) in the waterfall. The practical lesson is: use the bound where it is tight, simulate where it is loose.

Practical Constraints

•
Base graph: BG2 for $k \le 3840$ bits, BG1 for larger blocks.
•
Rate matching via repetition and puncturing; effective rates $0.33$ to $0.92$ .
•
Block length: 40 to 8448 information bits after rate matching.

📋 Ref: 3GPP TS 38.212, §5.3.2

Union-Bound Analysis of Coded BICM

From a Single PEP to the Bit Error Probability

Definition: Weight Enumerator and Input-Weight Multiplicities

Theorem: Union-Bound Bit Error Probability for BICM

Step 1: From pairwise to codeword error

Step 2: From codeword error to bit error

Step 3: High-SNR leading term

Example: Union Bound for a Rate-1/2, dH,free=7d_{H,{\rm free}} = 7dH,free​=7 Convolutional BICM

Per-$d$ PEP on Rayleigh

Evaluate first few terms

Union-bound sum (convolutional form, $k = 1$)

Leading-term approximation

Example: Where the Union Bound Goes Loose

Leading-term union bound

Interpretation: waterfall is not where the UB lives

What to use instead for the waterfall

Common Mistake: The Union Bound Is NOT a BER Estimate at the Waterfall

Common Mistake: Upper Bound vs Actual: PEP Is PpairwiseP_{\rm pairwise}Ppairwise​, Not BER

Union Bound vs Tighter BER Bounds

Parameters

Union-Bound BER Computation for Convolutional BICM

Why This Matters: LDPC Codes and the Union Bound: When It Breaks

Quick Check

5G NR: Does the Union Bound Match Simulation?

Definition:
Weight Enumerator and Input-Weight Multiplicities

Example: Union Bound for a Rate-1/2, $d_{H,{\rm free}} = 7$ Convolutional BICM

Common Mistake: Upper Bound vs Actual: PEP Is $P_{\rm pairwise}$ , Not BER