Abstract. Im vorliegenden Beitrag wird eine universelle Decoderarchitektur für einen Low-Density Parity-Check (LDPC) Code Decoder vorgestellt. Anders als bei den in der Literatur häufig beschriebenen Architekturen für strukturierte Codes ist die hier vorgestellte Architektur frei programmierbar, so dass jeder beliebige LDPC Code durch eine Änderung der Initialisierung des Speichers für die Prüfmatrix mit derselben Hardware decodiert werden kann. Die größte Herausforderung beim Entwurf von teilparallelen LDPC Decoder Architekturen liegt im konfliktfreien Datenaustausch zwischen mehreren parallelen Speichern und Berechnungseinheiten, wozu ein Mapping und Scheduling Algorithmus benötigt wird. Der hier vorgestellte Algorithmus stützt sich auf Graphentheorie und findet für jeden beliebigen LDPC Code eine für die Architektur optimale Lösung. Damit sind keine Wartezyklen notwendig und die Parallelität der Architektur wird zu jedem Zeitpunkt voll ausgenutzt.
Abstract. Im vorliegenden Beitrag wird eine universelle Decoderarchitektur für einen Low-Density Parity-Check (LDPC) Code Decoder vorgestellt. Anders als bei den in der Literatur häufig beschriebenen Architekturen für strukturierte Codes ist die hier vorgestellte Architektur frei programmierbar, so dass jeder beliebige LDPC Code durch eine Änderung der Initialisierung des Speichers für die Prüfmatrix mit derselben Hardware decodiert werden kann. Die größte Herausforderung beim Entwurf von teilparallelen LDPC Decoder Architekturen liegt im konfliktfreien Datenaustausch zwischen mehreren parallelen Speichern und Berechnungseinheiten, wozu ein Mapping und Scheduling Algorithmus benötigt wird. Der hier vorgestellte Algorithmus stützt sich auf Graphentheorie und findet für jeden beliebigen LDPC Code eine für die Architektur optimale Lösung. Damit sind keine Wartezyklen notwendig und die Parallelität der Architektur wird zu jedem Zeitpunkt voll ausgenutzt.
In dieser Arbeit werden Codes betrachtet, die allein durch rekursive Anwendung der |u|u+v|-Konstruktion, auch als PLOTKIN-Konstruktion bezeichnet, generiert werden. Der Schwerpunkt liegt hier sowohl auf der Konstruktion als auch auf der Decodierung von Codes dieser Klasse, die die Klasse der REED-MULLER (RM) Codes enthält. Bezüglich der auftretenden Störungen werden nur die beiden Sonderfälle des binären symmetrischen Kanals (BSC) und des additiven weißen gaußschen Rauschkanals (AWGN) betrachtet. Alle hier vorgestellten Codes sind Untercodes von RM-Codes und lassen sich als verallgemeinert verkettete Codes beschreiben. Für die zur Decodierung notwendige Zuverlässigkeitsübergabe an die Decoder der äußeren Codes wird neben der optimalen auch eine suboptimale Methode beschrieben und bewertet. Aufbauend auf diesen Methoden wird sowohl ein neues sequentielles als auch ein listengestütztes Decodierverfahren vorgeschlagen, die für alle Codes dieser Klasse geeignet sind. Es können damit beim AWGN-Kanal mit geringem Aufwand alle RM-Codes bis zu einer Länge von N = 128 Codesymbolen annähernd optimal decodiert werden. Speziell für RM-Codes wird darüber hinaus auch eine kombinierte Listen- und Permutationsdecodierung vorgeschlagen, womit beim AWGN-Kanal auch für alle Codes der Länge N = 256 und beim BSC bis zur Länge N = 512 nahezu optimale Wortfehlerwahrscheinlichkeiten erzielt werden. Um auch bei größeren Codelängen ebenfalls gute Decodierergebnisse zu erzielen, werden zwei verschiedene Methoden zur Anpassung des Codes an die verwendeten Decoder vorgestellt. Beide Methoden ermöglichen für Codelängen N = 2m die Konstruktion von Codes beliebiger Raten K/N, K ∈ {1, 2, ... , N}. Unter anderem die Berücksichtigung der bei Multilevel-Codes bekannten Ergebnisse führt so zu Codes, die zusammen mit dem hier vorgestellten Listendecodierverfahren auch bei deutlich über der Cutoff-Rate liegenden Coderaten kleine Fehlerwahrscheinlichkeiten ermöglichen.
Eine leistungsfähige Vorwärtsfehlerkorrektur ist für jedes moderne Kommunikationssystem essentiell. Um die gesamte Fehlerkorrekturfähigkeit von Kanalcodes wie Low Density Parity Check (LDPC)-Codes nutzen zu können, muss jedoch eine rechnerisch anspruchsvolle Decodierung am Empfänger erfolgen. Insbesondere in Szenarien, in denen die Leistung der Endgeräte oder Latenz der Übertragung begrenzt sind, sind effiziente Decodieralgorithmen von entscheidender Bedeutung. In dieser Arbeit wurde ein neuartiger Dekodierungsansatz entwickelt, der Ideen aus der Informationstheorie und dem maschinellen Lernen kombiniert und zu einem so genannten informationsoptimalen LDPC-Decoder führt. Insbesondere wurde die Information Bottleneck Methode verwendet, um sehr kompakte Darstellungen der in belief-propagation decoding ausgetauschten Nachrichten zu erhalten. Der Dekodierungsansatz wurde zudem verallgemeinert, um diesen auch für praktisch relevante irreguläre LDPC-Codes anwendbar zu machen. Dazu wurde eine weitere Technik entwickelt, das sogenannte „message alingment“. Als Ergebnis konnten LDPC-Dekodierer konstruiert werden, die eine nahezu optimale Leistung (0,2 dB Leistungsverschlechterung) bei sehr geringer Komplexität erreichen. Computersimulationen für irreguläre LDPC-Codes aus dem IEEE 802.11 (WLAN) und DVB-S2 Standard belegen die Anwendbarkeit der entwickelten Decoder auch in standardisierten Kommunikationssystemen.
Recently, low-density parity-check (LDPC) codes have attracted much attention because of their excellent error correcting performance and highly parallelizable decoding scheme. However, the effective VLSI implementation of and LDPC decoder remains a big challenge and is a crucial issue in determining how well we can exploit the benefits of the LDPC codes in the real applications. In this master thesis report, following a error coding background, we describe Low-Density Parity-Check codes and their decoding algorithm, and also requirements and architectures of LPDC decoder implementations.
Das universelle Verhalten von Störstellen mit stark korrelierten Elektronen in einem Metall wird bewiesen. In solchen Systemen wechselwirken die lokalen, stark korrelierten Elektronen der Störstelle mit den niederenergetischen Teilchen-Loch-Anregungen des Metalls und bilden einen komplizierten Vielteilchen-Grundzustand. Alle Versuche, diesen Grundzustand, die elementaren Anregungen und die Energieskalen des universellen Verhaltens mit den sonst üblichen störungstheoretischen Methoden zu berechnen, sind gescheitert. In einigen Spezialfällen gelingt mit Hilfe des Bethe-Ansatzes oder der numerischen Renormierungsgruppe eine Bestimmung der Thermodynamik eines Modellsystems, das aber nicht direkt mit dem ursprünglichen System in Verbindung gebracht werden kann. Daher stellt sich die Frage, wie man das universelle Verhalten von solchen Systemen systematisch beschreiben kann. Die zentralen Aussagen dieser Dissertation lauten: 1. Die Energieskalen eines Systems mit Störstellen lassen sich mit Hilfe einer Diagrammtechnik exakt berechnen. 2. Der Störstellen-Anteil jeder Observablen skaliert im universellen Limes mit der gleichen Energie. 3. Allein die Diagrammstruktur liefert ein Kriterium dafür, wann eine Näherung das universelle Verhalten bewahrt. Die hier benutzte Diagrammtechnik für Störstellen in Metallen wird neu und vereinfacht hergeleitet. Die Zusammenfassung der Diagramme in Klassen von Skelettdiagrammen führt auf ein Variationsprinzip für ein erzeugendes Funktional. Der Störstellen-Anteil der jeweiligen Observablen ergibt sich am Sattelpunkt des Funktionals bezüglich der Variation nach den ionischen Propagatoren. Diese Methode stammt von Luttinger und Ward. In dieser Dissertation wird die Information benutzt, wie die Skelettdiagramme strukturiert sind. Der entscheidende Punkt ist, dass man die Parameter-Abhängigkeit der Propagatoren im erzeugenden Funktional am Sattelpunkt ignorieren kann: Sie wird nur durch die Struktur der Skelettdiagramme bestimmt. Die Skelettdiagramme können so allein aufgrund ihrer Struktur nach der inversen Bandbreite klassifiziert werden. Nur eine als relevant bezeichnete Mindestmenge der Skelettdiagramme bestimmt die exakten Energieskalen des Systems, ohne das Modell vorher gelöst zu haben. Dies ergibt die erste Aussage. Eine Observable ergibt sich stets als Antwort des Systems auf ein entsprechendes äusseres Feld. Es wurde gezeigt, dass es nicht von der Observablen abhängt, welche Skelettdiagramme relevant sind. So kann man zeigen, dass der Störstellen-Anteil jeder Observablen mit der gleichen Energieskala skaliert. Dies ergibt die zweite Aussage. Die relevanten Skelettdiagramme beschreiben damit das universelle Verhalten der Störstelle und garantieren eine systematische Näherung für die Thermodynamik und die Dynamik der Störstelle. Berücksichtigt man noch weitere Skelettdiagramme, so verhalten sich die damit berechneten Störstellen-Anteile von Observablen genau dann universell, wenn ganze Familien von Skelettdiagrammen mitgenommen werden. Diese Skelettdiagramme ändern nichts an der Energieskala. Dies ergibt die dritte Aussage. Für das Anderson-Modell Störstelle in einem Metall ergeben die relevanten Skelettdiagramme gerade die sogenannte non-crossing-approximation (NCA). Daher beschreibt die NCA das universelle Verhalten des Anderson-Modells qualitativ richtig. Skelettdiagramme höherer Ordnung ändern das Bild nicht qualitativ. Bisher war es unerklärlich, warum die NCA mit den Resultaten der numerischen Renormierungsgruppe so gut übereinstimmt. Die Erklärung findet sich im exakten Skalierungsverhalten der NCA, das hier gezeigt wurde. Um das Verfahren zu testen, haben wir für das Anderson-Modell im magnetischen Limes das crossover untersucht. Für hohe Temperaturen oder Magnetfelder verhält sich das magnetische Moment der Störstelle asymptotisch frei, während es für tiefe Temperaturen durch niederenergetische Teilchen-Loch-Anregungen des Fermi-Sees abgeschirmt wird. Dieses crossover vom perturbativen Hochtemperatur- zum nichtperturbativen Niedertemperaturbereich wird durch die Wilson-Zahl charakterisiert. Hier wird die Wilson-Zahl zum ersten Mal mit einer Diagrammtechnik (NCA) berechnet. Das Ergebnis stimmt im Rahmen der Näherung mit dem als exakt postulierten Resultat überein. Um das universelle Verhalten anderer Observablen zu demonstrieren, wurde sodann für das Anderson-Modell zum ersten Mal explizit gezeigt, dass das Einteilchen-Anregungsspektrum - und damit die Abrikosov-Suhl-Resonanz - richtig skaliert, wenn man es mit Hilfe der NCA berechnet. Die vorgestellte Methode ermöglicht es auch, für ein System mit Störstellen die Qualität von Näherungen zu beurteilen, ohne sie zuvor explizit lösen zu müssen.
Inhalt der vorliegenden Arbeit ist die Untersuchung von Bose-Einstein-Kondensaten (BEC) in einschließenden optischen Dipolpotentialstrukturen, mit dem Ziel, die Interferometrie von geführten BECs und die Entwicklung von komplexen Leiterstrukturen für BECs zu untersuchen. Die Basis der vorgestellten Experimente bilden 87-Rubidiumatome, die in einer gekreuzten Dipolfalle gefangen werden und dort mittels evaporativer Kühlung in die Kondensatphase überführt werden. Dieses Kondensat aus 20000 Atomen wird anschließend in lineare oder ringförmige Dipolpotentialstrukturen umgeladen. Im ersten Teil der Arbeit wird ein System vorgestellt, welches, durch gezieltes Programmieren von phasenstabilen Referenzoszillatoren, die Kontrolle der Phaseninformation eines Atominterferometers in einem linearen Wellenleiter erlaubt. Mit Hilfe einer neuartigen Fourieranalyse der dabei gewonnenen Messdaten ist es möglich, eine robuste Definition des Interferometerkontrastes zu liefern, was wiederum Grundlage zur Bestimmung der Kohärenzzeit von 3.3 ms der Wellenfunktion in diesem System ist. Ebenso lässt sich mit der Methode erstmals ein Streifenabstand der Interferenzmuster im Dichteprofil ermitteln, welcher größer als die Ausdehnung der Dichteverteilung selbst ist. Dies ermöglicht es, den Zusammenhang von räumlicher Interferenzfrequenz, Phasengradient des Kondensats, relativer Position und Relativgeschwindigkeit der Interferometerarme sehr genau zu untersuchen. Damit wird der zeitliche Verlauf der Atom-Atom-Wechselwirkung im Wellenleiter unter Einfluss der Delta-Kick Kollimation qualitativ wiedergegeben. Im zweiten Teil der Arbeit wird der Effekt der konischen Refraktion ausgenutzt, um neuartige Potentialgeometrien für Bose-Einstein-Kondensate zu etablieren. Dabei wird eine theoretische Beschreibung der konischen Refraktion vorgestellt, die den Einfluss der räumlichen Strukturierung des Eingangslasersstrahls in einen biaxialen Kristall auf die Lichtverteilung beschreibt. In Form einer Mikrospiegeleinheit zur Strahlmanipulation wird ein System vorgestellt, welches die zuvor beschriebenen Lichtfelder experimentell erzeugen kann. Die dabei gewonnenen Messdaten werden vorgestellt und es wird gezeigt, dass sie in sehr guter Übereinstimmung mit dem theoretischen Modell stehen. Die so erzeugten Lichtfelder werden für das Speichern und Führen von Bose-Einstein-Kondensaten eingesetzt. Durch zeitliche Änderung der Blendenbilder auf der Mikrospiegeleinheit kann die Potentialgeometrie dynamisch verändert werden, wobei die Kohärenz der eingeschlossenen Kondensate erhalten bleibt. Ausgehend von einem harmonischen Potentialeinschluss wird durch eine solche Potentialtransformation eine ringförmige Kondensatverteilung erzeugt. Außerdem wird demonstriert, dass es mit dem System möglich ist, Rotationsbewegung auf ein Bose-Einstein-Kondensat zu übertragen.
The Low-Density Parity-Check codes are among the most powerful forward error correcting codes, since they enable to get as close as a fraction of a dB from the Shannon limit.This astonishing performance combined with their relatively simple decoding algorithmmake these codes very attractive for the next digital transmission system generations. Itis already the case for the next digital satellite broadcasting standard (DVB-S2), where an irregular LDPC code has been chosen to protect the downlink information. In this thesis, we focused our research on the iterative decoding algorithms and their hardware implementations. We proposed first a suboptimal algorithm named the λ-min algorithm. It reduces significantly the complexity of the decoder without any significant performance loss, as compared to the belief propagation (BP) algorithm. Then we studied and designed a generic architecture of an LDPC decoder, which has been implemented on a FPGA based platform. This hardware decoder enables to accelerate the simulations more than 500 times as compared to software simulations. Moreover, based on an all-tunable design, our decoder features many facilities: It is possible to configure it for a very wide code family, so that the research for good codes is processed faster ; thanks to the genericity of the processing components, it is also possible to optimize the internal coding format, and even to compare various decoding algorithms and various processing schedules. Finally, our experience in the area of LDPC decoders led us to propose a formal framework for analysing the architectures of LDPC decoders. This framework encompassesboth the datapath (parallelism, node processors architectures) and the control mode associated to the several decoding schedules. Thus within this framework, a classification of the different state-of-the-art LDPC decoders is proposed. Moreover, some synthesis of efficient and unpublished architectures have been also proposed.