h1

TY  - THES
AU  - Böcherer, Georg
TI  - Capacity achieving probabilistic shaping for noisy and noiseless channels
CY  - Aachen
PB  - Publikationsserver der RWTH Aachen University
M1  - RWTH-CONV-143171
SP  - 145 S. : graph. Darst.
PY  - 2012
N1  - Aachen, Techn. Hochsch., Diss., 2012
AB  - In Shannon theory, the key step in calculating the capacity of a communication channel is to determine the channel input distribution that maximizes the mutual information between transmitted and received symbols. For many channels, this so called capacity-achieving distribution is not uniform. In digital communication systems, there is a binary interface that separates the system into a source-related part and a channel-related part. A natural question is how the bit stream at the binary interface can be mapped to channel input symbols in such a way that the resulting distribution is close to capacity-achieving. The topic of this thesis is to answer this question. In this thesis, dyadic distributions are considered. Dyadic distributions can be generated by parsing the bit stream at the binary interface by a prefix-free code. A device that implements this procedure is called a prefix-free matcher. In the first part of this thesis, three types of discrete memoryless channels are considered. First, unconstrained channels, second, channels with input symbols of unequal duration, and third, channels with a constraint on the average symbol cost. Both the noiseless and the noisy case are considered. A new algorithm called geometric Huffman coding is proposed. It is shown that this algorithm efficiently finds the optimal prefix-free matcher for the noiseless case. For the noiseless and the noisy case, it is shown that the generated dyadic distributions are asymptotically capacity-achieving when blocks of symbols are jointly generated and when the blocklength goes to infinity. In the second part of the thesis, noiseless channels with memory are considered. For the general setting, a fundamental relation between the combinatorial and the probabilistic notion of capacity is derived. For noiseless channels that are generated by graphs with finitely many states, it is shown that prefix-free matchers can be used to transmit a binary stream over the channel at a rate as close to capacity as desired. For various examples prefix-free matchers achieve higher rates than previously known techniques. The topic of the last part is how prefix-free matchers can be combined with error correction. For the general class of not necessarily binary systematic block codes, analytic formulas for shaping gain and coding gain are derived. The shaping gain determines the performance loss that results from using a distribution different from the capacity-achieving one, and the coding gain quantifies the loss due to sub-optimal codes. The gains are assessed for three modes of operation, namely when none, some, or all symbols are matched to the capacity-achieving distribution by a prefix-free matcher. It is proven that in the latter case, the optimal shaping gain is asymptotically achieved. The results are evaluated for a binary symmetric channel where the input symbols zero and one are of unequal duration. The numerical results reveal that prefix-free matchers in practice allow to operate ldpc codes with a shaping gain that does not degrade capacity.
KW  - Kanalkapazität (SWD)
KW  - Wahrscheinlichkeitsverteilung (SWD)
KW  - Codierung (SWD)
KW  - Endlicher Automat (SWD)
KW  - Low-Density-Parity-Check-Code (SWD)
KW  - Huffman-Code (SWD)
KW  - Konvexe Optimierung (SWD)
LB  - PUB:(DE-HGF)11
UR  - https://publications.rwth-aachen.de/record/82812
ER  -