Matching Dyadic Distributions to Channels


G. Böcherer, R. Mathar,


        Many communication channels with discrete input have non-uniform capacity achieving probability mass functions (PMF). By parsing a stream of independent and equiprobable bits according to a full prefix-free code, a modulator can generate dyadic PMFs at the channel input. In this work, we show that for discrete memoryless channels and for memoryless discrete noiseless channels, searching for good dyadic input PMFs is equivalent to minimizing the Kullback-Leibler distance between a dyadic PMF and a weighted version of the capacity achieving PMF. We define a new algorithm called Geometric Huffman Coding (GHC) and prove that GHC finds the optimal dyadic PMF in O(m log m) steps where m is the number of input symbols of the considered channel. Furthermore, we prove that by generating dyadic PMFs of blocks of consecutive input symbols, GHC achieves capacity when the block length goes to infinity.

BibTEX Reference Entry 

	author = {Georg B{\"o}cherer and Rudolf Mathar},
	title = "Matching Dyadic Distributions to Channels",
	pages = "23-32",
	booktitle = "Data Compression Conference (DCC 2011)",
	address = {Snowbird, USA},
	month = Mar,
	year = 2011,
	hsb = hsb999910034704,


 Download paper  Download bibtex-file

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights there in are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.