AG Kommunikationstheorie


Capacity-Achieving Probabilistic Shaping for Noisy and Noiseless Channels


In this talk, memoryless channels with discrete input are considered. For many channels, the capacity-achieving probability mass functions (pmfs) of the channel input symbols is non-uniform. A device that approximates this optimal pmf is called a channel matcher. In a digital communication system, a channel matcher maps a sequence of equiprobable bits to a sequence of channel input symbols. The main theme of this talk is to show existence and construction of channel matchers that achieve capacity as the complexity of the matcher increases.

First, the decrease of mutual information that results from using a pmf different from the capacity-achieving one is analyzed. It is shown that the relative entropy D(d||p) of the employed pmf d and the optimal pmf p upper bounds this decrease. Then, the class of channel matchers that consist in parsing an equiprobable bit sequence by a prefix-free code are considered. A new algorithm called geometric Huffman coding (ghc) is introduced. It is shown that ghc constructs the optimal prefix-free matcher and that prefix-free matchers are asymptotically capacity-achieving.

The developed techniques for capacity-achieving shaping can be applied to a large class of problems. This is exemplified in the last part of the talk. By assuming error-correction based on systematic block-codes, the highest rate for reliable communication is given by the sparse-dense capacity. It is shown that prefix-free channel matchers asymptotically achieve sparse-dense capacity.

zurück zur Terminübersicht