Multiset-partition distribution matching

Tobias Fehenberger, David S. Millar (Corresponding author), Toshiaki Koike-Akino, Keisuke Kojima, Kieran Parsons

Research output: Contribution to journalArticleAcademicpeer-review

96 Citations (SciVal)


Distribution matching is a fixed-length invertible mapping from a uniformly distributed bit sequence to shaped amplitudes and plays an important role in the probabilistic amplitude shaping framework. With conventional constant-composition distribution matching (CCDM), all output sequences have identical composition. In this paper, we propose multiset-partition distribution matching (MPDM), where the composition is constant over all output sequences. When considering the desired distribution as a multiset, MPDM corresponds to partitioning this multiset into equal-sized subsets. We show that MPDM allows addressing more output sequences and, thus, has a lower rate loss than CCDM in all nontrivial cases. By imposing some constraints on the partitioning, a constructive MPDM algorithm is proposed which comprises two parts. A variable-length prefix of the binary data word determines the composition to be used, and the remainder of the input word is mapped with a conventional CCDM algorithm, such as arithmetic coding, according to the chosen composition. Simulations of 64-ary quadrature amplitude modulation over the additive white Gaussian noise channel demonstrate that the block-length saving of MPDM over CCDM for a fixed gap to capacity is approximately a factor of 2.5-5 at medium to high signal-to-noise ratios.

Original languageEnglish
Article number8533438
Pages (from-to)1885 - 1893
Number of pages9
JournalIEEE Transactions on Communications
Issue number3
Publication statusPublished - Mar 2019


  • Coded Modulation
  • Distributed databases
  • Distribution Matching
  • Encoding
  • Forward error correction
  • Modulation
  • Partitioning algorithms
  • Probabilistic Amplitude Shaping
  • Probabilistic logic
  • Signal to noise ratio
  • Distribution matching
  • coded modulation
  • probabilistic amplitude shaping


Dive into the research topics of 'Multiset-partition distribution matching'. Together they form a unique fingerprint.

Cite this