Module ccdm 

Constant-composition distribution matching (CCDM): uniform bits to sequences of symbols of a prescribed distribution, the shaping stage of probabilistic amplitude shaping (comnum_systems::pas).

Model

A composition $(n_{1}, \dots, n_{A})$, $\sum_{a} n_{a} = n$, defines the set of the $\binom{n}{n_{1}, \dots, n_{A}} = n! / \prod_{a} n_{a}!$ sequences of $n$ symbols in which symbol $a$ appears $n_{a}$ times: their empirical distribution is exactly $n_{a} / n$. The matcher maps $k = \lfloor \log_{2} \binom{n}{n_{1}, \dots, n_{A}} \rfloor$ uniform bits, read as an integer, to the sequence of that rank in the lexicographic order of the set (enumerative coding, Cover 1973), and the dematcher computes the rank back. The rate $k/n$ approaches the entropy of the target distribution as $n$ grows, with a rate loss of the order of $\log n / n$ (Schulte & Böcherer 2016, who implement the same set by arithmetic coding).

The ranks are exact integers of about $n H$ bits (comnum_math::bigint::BigUint); a symbol costs $O(A)$ big-integer products and quotients by machine integers.

Ccdm::from_distribution chooses the composition nearest to a target distribution (largest remainders). Ccdm::dematch accepts any sequence: a symbol that the composition has used up (after a decoding error) is replaced by the nearest available one, so that wrong sequences still give $k$ bits.

Examples

use comnum_fec::ccdm::Ccdm;
// 4 amplitudes with probabilities 0.4, 0.3, 0.2, 0.1, blocks of 100 amplitudes
let dm = Ccdm::from_distribution(&[0.4, 0.3, 0.2, 0.1], 100)?;
assert_eq!(dm.composition(), &[40, 30, 20, 10]);
assert_eq!(dm.k(), 175);   // log2 of 100!/(40! 30! 20! 10!) = 175.03; 100 H = 184.6
let bits: Vec<u8> = (0..dm.k()).map(|i| ((i * 7) % 3 == 0) as u8).collect();
let a = dm.match_bits(&bits)?;
assert_eq!(a.iter().filter(|&&s| s == 0).count(), 40);
assert_eq!(dm.dematch(&a)?, bits);

References

1. P. Schulte and G. Böcherer, “Constant composition distribution matching,” IEEE Trans. Inf. Theory, 62(1), 430–434, 2016.
2. T. M. Cover, “Enumerative source coding,” IEEE Trans. Inf. Theory, 19(1), 73–77, 1973.

Structs

Ccdm

A constant-composition distribution matcher (see the module).