Source-linked AI summary
Constant Composition Distribution Matching
Patrick Schulte, Georg Böcherer
TL;DR
Distribution matching must convert independent Bernoulli(1/2) bits into symbols following a desired distribution while retaining invertibility. The paper develops fixed-to-fixed-length matchers using constant composition codes and arithmetic coding, achieving the desired distribution entropy asymptotically while normalized divergence vanishes.
Problem
Distribution matching seeks an invertible mapping from Bernoulli(1/2) input bits to length-n output strings that imitate a desired distribution.
Method
The paper uses constant composition codes with arithmetic coding to implement practical fixed-to-fixed-length distribution matchers and dematchers.
Results
The matcher asymptotically achieves the entropy H(A) of the desired distribution, while normalized informational divergence approaches zero as n→∞.
Takeaways & Limitations
The resulting fixed-to-fixed-length matcher is practical and invertible, with error propagation limited by the blocklength.
Abstract
from arXiv · showhide
Distribution matching transforms independent and Bernoulli(1/2) distributed input bits into a sequence of output symbols with a desired distribution. Fixed-to-fixed length, invertible, and low complexity encoders and decoders based on constant composition and arithmetic coding are presented. Asymptotically in the blocklength, the encoder achieves the maximum rate, namely the entropy of the desired distribution. Furthermore, the normalized divergence of the encoder output and the desired distribution goes to zero in the blocklength.
I. INTRODUCTION
Distribution matching converts independent Bernoulli(1/2) input bits into output symbols approximating a desired distribution, while enabling inverse recovery. This work proposes practical fixed-to-fixed-length matchers based on constant composition and arithmetic coding.
- Distribution matchers transform independent Bernoulli(1/2) input bits into output symbols with a desired distribution.
- A dematcher performs the inverse operation and recovers the input bits from the output symbols.
- Earlier matcher codebooks require offline generation and storage, which becomes infeasible at the large lengths needed for maximum rate.
- The proposed fixed-to-fixed-length matchers are practical, invertible, asymptotically optimal, and based on constant composition codes indexed by arithmetic coding.
II. PROBLEM STATEMENT
The paper formalizes invertible distribution matching from Bernoulli input bits to fixed-length output sequences that imitate a desired distribution. It defines achievable rate and relates rate limits to entropy and normalized informational divergence.
- Performance measures: The section introduces entropy, informational divergence, normalized informational divergence, and iid notation as measures for analyzing distribution matching.These definitions provide the quantities used to characterize the desired distribution and output approximation.
- Problem formulation: A one-to-one distribution matcher maps m Bernoulli-distributed input bits to length-n output strings while providing an inverse mapping.The output distribution is intended to imitate the desired distribution P_A.
- Problem formulation: The matching rate R = m/n is achievable when an invertible mapping satisfies the required distribution-matching condition for sufficiently large n.The definition quantifies this requirement for every α > 0.
- Rate limits: Proposition 1 bounds the maximum achievable rate under the stated matching condition.The proposition is presented as a converse relating achievable rate to the distribution-matching criterion.
III. CONSTANT COMPOSITION DISTRIBUTION MATCHING
The paper uses empirical distributions, or types, to define constant composition codes whose codewords share the same symbol counts. This structure supports matching a target distribution through a common composition.
- Constant composition: The empirical distribution of a length-n vector records each symbol’s relative frequency, and is called its type.The count n_a(c) specifies how often symbol a occurs in c.
- Constant composition: A constant composition code has codewords with identical symbol counts, so every codeword shares the same type.The count n_a does not depend on the codeword within the codebook.
A. Approach
The approach selects an n-type close to the desired distribution, uses its type class as the available codeword set, and chooses the input length from the type-class size. Arithmetic coding implements the mapping efficiently.
- A. Approach: The target composition is chosen by selecting integer symbol counts n_a approximately proportional to P_A while satisfying the n-type constraint.The allocation solves the stated optimization problem and can be found efficiently using Algorithm 2 from [18].
- A. Approach: For fixed output length n, the type class T_n^{P̄_A} contains all vectors having the selected empirical distribution.The code construction uses this set of constant-composition sequences.
- A. Approach: Invertibility requires the input blocklength to satisfy m ≤ log2 |T_n^{P̄_A}|, so the construction sets m = floor(log2 |T_n^{P̄_A}|).This choice ensures enough codewords for all input blocks.
- A. Approach: The encoding function f_ccdm maps input blocks into the selected type class, and its image forms the constant composition codebook.The mapping is defined after fixing the input length from the type-class cardinality.
- A. Approach: Arithmetic coding implements the constant-composition mapping efficiently, while invertibility gives the codebook size |C_ccdm| = 2^m.The codebook is the image of the encoding function.
B. Analysis
The analysis establishes that the fixed-to-fixed constant-composition distribution matcher asymptotically achieves the desired entropy rate while its normalized divergence vanishes. A finite-blocklength example shows a trade-off between blocklength efficiency and codebook storage requirements.
- The fccdm asymptotically achieves all rates satisfying (8).
- The analysis bounds the contribution involving the alphabet size k = |A| and shows that this term vanishes as blocklength increases.
- The rate analysis relates input and output lengths to characterize the matcher’s asymptotic behavior.
- The normalized divergence approaches zero as n →∞.
- In the example with PA = (0.0722, 0.1654, 0.3209, 0.4415), ccdm needs about 4 times the optimal scheme’s blocklength to reach 0.06 bits per symbol divergence.
- The optimal codebook requires about 10240 bits = 1.25 kB for n = 10 and 1.441 × 1019 TB for n = 100.
IV. ARITHMETIC CODING
The arithmetic encoder indexes constant-composition output sequences by associating intervals with input and output sequences, refining them sequentially under a without-replacement model. Sure output prefixes are identified during refinement, while rescaling addresses numerical representation limits.
- Interval construction: Arithmetic coding associates intervals with each m-bit input sequence and each output sequence in the constant-composition type class.Input and output intervals are ordered lexicographically and both span [0,1).
- Interval construction: For n = 4 and P¯A(0) = P¯A(1) = 0.5, four input sequences and six equally probable output sequences receive intervals.The example uses output length n = 4 and equal target symbol probabilities.
- Interval construction: The encoder links an output sequence to an input sequence when the output interval’s lower border lies inside the input interval, selecting the lowest-border output when multiple choices exist.There are at most two choices because the input interval is less than twice the output interval size.
- Online algorithm: Sequential input refinement splits the interval equally for Bernoulli(1/2) bits and checks after each step whether a sure output prefix has been determined.After m bits, the input interval has size 2^-m; identified prefixes are emitted with probability one.
- Online algorithm: Conditioned output probabilities are computed by drawing without replacement from a bag containing n symbols with fixed counts, decrementing the relevant count after each draw.If a symbol count is n′_a among n remaining symbols, its conditional probability is n′_a/n.
- Online algorithm: After n output refinements, the procedure produces equally spaced intervals labeled by all sequences in the constant-composition type class.The construction ensures that every generated sequence has the desired type.
- Numerical implementation: Rescaling is introduced whenever numerical representation problems arise, with the input and output intervals remapped after each newly known output symbol.The output interval is scaled to [0,1) once a prefix has been identified.
A. Scaling input and output intervals
The encoder rescales both intervals after identifying an output prefix, mapping the relevant output interval to [0,1) before continuing refinement.
- A. Scaling input and output intervals: After identifying a prefix, the encoder discards sequences without that prefix and rescales the input and output intervals.The output interval is mapped to [0,1), and subsequent input bits determine further sure prefixes.
V. CONCLUSION
The paper presents a practical, invertible fixed-to-fixed length distribution matcher that achieves the maximum rate asymptotically. It also addresses synchronization and variable-rate concerns, while limiting error propagation by the blocklength.
- V. CONCLUSION: The proposed practical and invertible fixed-to-fixed length matcher achieves the maximum rate asymptotically in the blocklength.The conclusion identifies this as the principal result.
- V. CONCLUSION: The fixed-to-fixed length matcher is robust to synchronization and variable rate problems compared with earlier matchers.The conclusion contrasts this property with matchers proposed in the cited literature.
- V. CONCLUSION: Error propagation is limited by the blocklength.
- V. CONCLUSION: Future work will investigate fixed-to-fixed length codes that perform well in the finite-blocklength regime.