Capacity achieving probabilistic shaping for noisy and noiseless channels

Böcherer, Georg; Mathar, Rudolf

doi:4097

Capacity achieving probabilistic shaping for noisy and noiseless channels = Kapazitätserreichende probabilistische Kanalanpassung für verrauschte und rauschfreie Kanäle

Böcherer, Georg (Author)

2012

VerantwortlichkeitsangabeGeorg Böcherer

ImpressumAachen : Publikationsserver der RWTH Aachen University 2012

Umfang145 S. : graph. Darst.

Aachen, Techn. Hochsch., Diss., 2012

Genehmigende Fakultät
Fak06

Hauptberichter/Gutachter
Mathar, Rudolf (Thesis advisor)

Tag der mündlichen Prüfung/Habilitation
2012-02-13

Online
URN: urn:nbn:de:hbz:82-opus-40977
URL: https://publications.rwth-aachen.de/record/82812/files/4097.pdf

Einrichtungen

Lehrstuhl und Institut für Theoretische Informationstechnik (613410)

Inhaltliche Beschreibung (Schlagwörter)
Kanalkapazität (Genormte SW) ; Wahrscheinlichkeitsverteilung (Genormte SW) ; Codierung (Genormte SW) ; Endlicher Automat (Genormte SW) ; Low-Density-Parity-Check-Code (Genormte SW) ; Huffman-Code (Genormte SW) ; Konvexe Optimierung (Genormte SW) ; Ingenieurwissenschaften (frei) ; kapazitätserreichende Verteilung (frei) ; geometrischer Huffman-Code (frei) ; channel capacity (frei) ; capacity-achieving distribution (frei) ; probabilistic shaping (frei) ; geometric Huffman coding (frei) ; constrained coding (frei)

Thematische Einordnung (Klassifikation)
DDC: 620
msc: 94A05 * 94A17 * 94A45 * 94A15

Kurzfassung
Bei der Berechnung der Kapazität eines Kommunikationskanales nach Shannon muss die Kanaleingangsverteilung bestimmt werden, welche die Transinformation zwischen Kanaleingang und Kanalausgang maximiert. Bei vielen Kanälen ist diese sogenannte kapazitätserreichende Verteilung nicht gleichverteilt. Digitale Kommunikationssysteme werden durch eine binäre Schnittstelle aufgeteilt in einen Teil für die Datenquelle und einen Teil für den Übertragungskanal. Dies wirft die Frage auf wie man die binären Sequenzen an der Schnittstelle so auf Sequenzen von Kanaleingangssymbolen abbilden kann, dass die resultierende Verteilung am Kanaleingang in der Nähe der kapazitätserreichenden Verteilung liegt. Die Beantwortung dieser Frage ist das Thema dieser Arbeit. Es werden dyadische Verteilungen betrachtet, welche erzeugt werden, wenn die binäre Sequenz an der Schnittstelle von einem Präfix-freien Kode geparst wird. Dieses Verfahren wird im Folgenden Präfix-freie Kanalanpassung genannt. Im ersten Teil dieser Arbeit werden drei Arten von diskreten gedächtnislosen Kanälen betrachtet. Erstens Kanäle ohne Nebenbedingungen, zweitens Kanäle mit Eingangssymbolen unterschiedlicher Länge und drittens Kanäle mit eingeschränkten Durchschnittskosten der Kanaleinganssymbole. Sowohl rauschfreie als auch verrauschte Kanäle werden betrachtet. Ein neuer Algorithmus, der Geometrische Huffman-Kode, wird vorgestellt. Es wird gezeigt, dass dieser Algorithmus im rauschfreien Fall die optimale Präfix-freie Kanalanpassung findet. Sowohl für rauschfreie als auch für verrauschte Kanäle wird gezeigt, dass die geometrische Huffman-Kodierung kapazitätserreichend ist, wenn Blöcke von Kanalsymbolen gemeinsam erzeugt werden und die Blocklänge gegen unendlich geht. Im zweiten Teil der Arbeit werden rauschfreie Kanäle mit Gedächtnis betrachtet. Für den allgemeinen Fall wird eine fundamentale Beziehung zwischen kombinatorischer und probabilistischer Kapazität hergeleitet. Für rauschfreie Kanäle, welche von Graphen mit endlich vielen Zuständen erzeugt werden, wird gezeigt, dass unter der Verwendung von Präfix-freier Kanalanpassung jede Rate unterhalb der Kapazität erreicht werden kann. Für verschiedene Beispiele wird gezeigt, dass Präfix-freie Kanalanpassung höhere Raten erreicht als bisher bekannte Verfahren. Der letzte Teil der Arbeit widmet sich der Kombination von Präfix-freier Kanalanpassung und Fehlerkorrektur. Für die allgemeine Klasse (nicht-)binärer Blockkodes werden analytische Ausdrücke für den Anpassungsgewinn und den Kodierungsgewinn hergeleitet. Der Anpassungsgewinn beschreibt den Verlust an Rate, der daher resultiert, dass eine nicht-kapazitätserreichende Verteilung am Kanaleingang verwendet wird. Der Kodierungsgewinn beschreibt den Ratenverlust, welcher von der Verwendung nicht-optimaler fehlerkorrigierender Kodes herrührt. Die Gewinne werden untersucht für drei Konfigurationen, nämlich für nicht-angepasste (gleichverteilte) Kanaleingangsverteilungen, für teilweise angepasste Verteilungen und für vollständig angepasste Verteilungen. Es wird gezeigt, dass im letzteren Fall der optimale Anpassungsgewinn asymptotisch erreicht wird. Simulationsresultate für einen binären symmetrischen Kanal mit Eingangssymbolen unterschiedlicher Länge bestätigen die theoretischen Resultate und zeigen, dass Präfix-freie Kanalanpassung die Verwendung von ldpc-Kodes erlaubt mit einem optimalen Anpassungsgewinn, welcher die Kanalkapazität nicht verringert.

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.

Fulltext:
PDF