Ferkans — Interactive Telecom Tutor

From Theory to Practice: Distribution Matching

The point is that Maxwell-Boltzmann shaping (§1) tells us what distribution to target, and Probabilistic Amplitude Shaping (§2) tells us how to compose shaping with FEC — but neither tells us how to TRANSFORM a uniform bit stream into a stream of MB-shaped amplitudes. That is the job of a distribution matcher. The CCDM (constant-composition distribution matcher) is the dominant practical choice, achieving the MB rate asymptotically.

Definition:
Distribution Matcher (DM)

A distribution matcher is an invertible mapping from a uniform binary stream $\{0, 1\}^k$ to an amplitude sequence $\mathbf{a} \in \mathcal{A}^n$ such that the empirical distribution of $\mathbf{a}$ approximates a target distribution $P_A$ . The DM is INVERTIBLE — the inverse is computed at the receiver after FEC decoding to recover the original bits.

Definition:
Constant-Composition Distribution Matcher (CCDM)

A constant-composition DM (CCDM) selects output sequences of length $n$ with the same empirical histogram — the "composition". Given a target distribution $P_A$ on an $|\mathcal{A}|$ -ary alphabet, the CCDM chooses counts $(n_{a_1}, \ldots, n_{a_{|\mathcal{A}|}})$ with $n_{a_i} = \lfloor n \cdot P_A(a_i) \rfloor$ and assigns arithmetic-coding rank to each of the $\binom{n}{n_{a_1}, \ldots}$ legal sequences.

Theorem: CCDM Rate Approaches MB Rate

For a target distribution $P_A$ with entropy $H(P_A)$ , the CCDM of length $n$ achieves rate $R_{\rm CCDM}(n) = \frac{\lfloor \log_2 \binom{n}{n_{a_1}, \ldots, n_{a_{|\mathcal{A}|}}} \rfloor}{n} = H(P_A) - O\!\left(\frac{\log n}{n}\right).$ The rate loss is $O(\log n / n)$ , vanishing as $n \to \infty$ .

Proof

Count of legal sequences

The multinomial coefficient $\binom{n}{n_{a_1}, \ldots, n_{a_{|\mathcal{A}|}}}$ counts sequences with the target composition. By Stirling's approximation, $\log_2 \binom{n}{n_{a_1}, \ldots, n_{a_{|\mathcal{A}|}}} = n \cdot H(P_A) - \frac{|\mathcal{A}|-1}{2}\log_2 n + O(1)$ .

Rate extraction

Dividing by $n$ and taking the floor: $R_{\rm CCDM} = H(P_A) - \frac{|\mathcal{A}|-1}{2n}\log_2 n + O(1/n)$ .

Convergence

$R_{\rm CCDM}(n) \to H(P_A)$ as $n \to \infty$ . The rate loss decays as $\log n / n$ — a small fraction of a bit per symbol at $n = 1000$ ( $\approx 0.02$ bits/symbol for 16-PAM). $\blacksquare$

CCDM Output vs Target MB Distribution

Compare the target Maxwell-Boltzmann distribution (green bars) with the actual CCDM output distribution at a chosen block length (blue bars). As $n$ grows, the two match more closely — the KL divergence decays as $\log n / n$ .

Parameters

QAM size

M

Block length

n

200

CCDM Arithmetic Encoding

Complexity:

O(n |\mathcal{A}|)

time,

O(n)

memory.

Input: Target counts

(n_{a_1}, \ldots, n_{a_{|\mathcal{A}|}})

summing to

n

; uniform

k

-bit message

\mathbf{m}

.

Output:

n

-symbol amplitude sequence

\mathbf{a}

.

1. Compute index

I(\mathbf{m}) \in \{0, 1, \ldots, M_{\max} - 1\}

where

M_{\max} = \binom{n}{n_{a_1}, \ldots, n_{a_{|\mathcal{A}|}}}

.

2. for

j = 1, \ldots, n

do

3.

\quad

For each candidate symbol

a_i

, compute the number

N_i

of sequences starting with

a_i

in the remaining position.

4.

\quad

Find the smallest

i^*

such that

\sum_{i \le i^*} N_i > I

.

5.

\quad

Emit

a_j = a_{i^*}

; update

I \gets I - \sum_{i < i^*} N_i

.

6.

\quad

Decrement

n_{a_{i^*}}

.

7. end for

The inverse at the receiver reconstructs $I$ from $\mathbf{a}$ by accumulating $\sum_{i < a_j} N_i$ at each step. Then $\mathbf{m} = I$ in binary.

Example: CCDM for 16-QAM at $n = 200$

For 16-QAM per-axis amplitudes $\{-3, -1, +1, +3\}$ (i.e., $| \mathcal{A}| = 4$ ), and target $P_A = (0.35, 0.15, 0.15, 0.35)$ with $H(P_A) = 1.88$ bits/symbol, find the CCDM rate for $n = 200$ . Compare with the entropy.

Solution

Target counts

$n_{a_i} = (70, 30, 30, 70)$ , summing to 200.

Multinomial count

$\binom{200}{70, 30, 30, 70} \approx 10^{104}$ sequences.

Rate

$R_{\rm CCDM} = \lfloor \log_2 10^{104} \rfloor / 200 \approx 345.4 / 200 = 1.727$ bits/symbol.

Rate loss

Entropy - rate = $1.88 - 1.73 = 0.15$ bits/symbol — about 8% loss. At $n = 10{,}000$ , the loss drops to ~1%.

Common Mistake: CCDM Short-Block Rate Loss Is Real

Mistake:

"CCDM achieves the entropy $H(P_A)$ exactly for any block length."

Correction:

The rate loss is $O(\log n / n)$ . At $n = 100$ the loss can be 5-10% of the target entropy — a meaningful slice of the shaping gain. For URLLC or short-packet applications, this loss limits the achievable shaping gain. Alternatives: shell mapping (Imai-Hirasawa) and hierarchical DM (Amjad-Böcherer 2013) that reduce the short- block loss at increased complexity.

Historical Note: A Line of Distribution-Matching Algorithms

1977–2016

Distribution matching has a 40-year history:

Imai-Hirasawa 1977: shell mapping (sphere-packing lower bound).
Laroia-Farvardin-Tretter 1994: trellis shaping (convolutional approach).
Böcherer 2013 (thesis): CCDM as the practical modern algorithm.
Amjad-Böcherer 2013: hierarchical DM for short blocks.
Schulte-Böcherer 2016: formal CCDM rate-loss analysis. Today, CCDM is the dominant choice in production optical and 5G research. Hierarchical DMs are used for very short blocks.

Key Takeaway

CCDM is the practical algorithm that realises MB shaping. It converts a uniform bit stream into an amplitude sequence of target composition with rate $H(P_A) - O(\log n/n)$ . The short-block rate loss limits the achievable shaping gain for URLLC; hierarchical DM offers a more complex but tighter alternative.

CCDM and Distribution Matching