In der vorliegenden Arbeit wird ein effizienter Soft-Decision Algorithmus vorgeschlagen, der fur die Decodierung langer linearen Blockcodes angewendet werden kann. Im Gegensatz zu Faltungscodes kann normalerweise die zusatzliche Zuverlassigkeitsinformation in die Decodierung von Blockcodes nicht auf einfache und effiziente Weise integrierte werden. Diese Arbeit ist ein Versuch, diese Lucke zu schliesen. Eine Moglichkeit der Hard-Decision Decodierung besteht in der Verwendung von sogenannten Informationsmengen. Eine Informationsmenge gestattet es, durch Kenntnis einiger Komponenten eines Codewortes die unbekannten Stellen exakt zu berechnen. In dieser Arbeit wird ein Decodieralgorithmus vorgestellt, der auf Informationsmengen basiert. Die Zuverlassigkeitsinformationen werden derart zur Auswahl der Informationsmengen verwendet, das fur sehr lange Blockcodes eine minimale Anzahl von Operationen notwendig ist. Zur weiteren Begrenzung der durchschnittlichen Komplexitat werden einige Kriterien hergeleitet, die einen Abbruch der Iteration gestatten, wenn der Algorithmus bereits eine Maximum-Likelihood Schatzung erreicht hat. Weiterhin werden ausfuhrliche Simulationen mit dem beschriebenen Algorithmus durchgefuhrt. Um auch sehr lange Blockcodes zu simulieren, wird zunachst eine Simulationsmethode vorgeschlagen, die die wahrscheinlichsten Fehlerereignisse stark berucksichtigt. Dadurch wird es moglich, sehr lange Codes auch fur grose Signal zu Rauschverhaltnis zu simulieren. Es wird eingehend untersucht, wie sich verschiedene Abbruchkriterien auf die Komplexitat des Decodieralgorithmus auswirken. Ferner wird dieser Algorithmus fur die BCH-Codes (128,64) und (255,123) angewendet. Es zeigt sich, das selbst mit wenigen Iterationen eine deutliche Steigerung gegenuber einer BMD-Decodierung erreicht werden kann. Durch Erhohung der Anzahl der Iterationen gestattet es der vorschlagene Algorithmus beliebig dicht an die Leistungsfahigkeit eines Maximum-Likelihood-Decodierers heranzukommen.
Mit dieser Arbeit wird bewiesen, dass die Entwicklung von niedrig skalierenden Algo- rithmen zur Berechnung von austauschartigen Vielteilchen-Termen sowohl möglich als auch praktisch ist. Die Vorhersage von Materialeigenschaften mittels ab initio Metho- den erfordert effiziente Computerprogramme. Nach wie vor ist die computergestützte Materialphysik eine der rechenintensivsten Wissenschaftszweige. Das zentrale Problem, auch bekannt als Problem der elektronischen Struktur, besteht in der Berechnung hinre- ichend genauer Näherungen zur Vielteilchen-Schrödingergleichung. Die Korrelation von Elektronen ist dabei von besonderer Bedeutung, bestimmt sie doch maßgeblich Eigen- schaften wie die Kristallstruktur, Oberflächenenergien oder thermodynamische Phasen- grenzen. In dieser Arbeit stellen wir neue Algorithmen vor, welche die Effizienz von Berechnungen der Korrelationsenergie großer Systeme erheblich verbessern. Wir setzen dabei auf Orbital-basierte Vielteilchen-Störungstheorie und gehen damit über Hartree- Fock oder Dichtefunktionaltheorie hinaus. Orbitale sind einfache und anschauliche mathematische Zutaten um Näherungen zur Grundzustandsenergie von Vielteilchensys- temen zu konstruieren. Allerdings ist die Assoziation eines Orbitals mit einem Elektron falsch, da Elektronen ununterscheidbar sind, Orbitale dagegen unterscheidbar. Alle ord- nungsgemäßen Theorien berücksichtigen daher sogenannte austauschartige Terme, die genau diesen Fehler korrigieren. Diese austauschartigen Terme werden von Methoden wie zweiter-Ordnung-Møller-Plesset-Störungstheorie (engl. second-order Møller-Plesset perturbation theory, MP2) oder näherungsweise durch zweiter-Ordnung-abgeschirmter- Austausch (engl. second-order screened exchange, SOSEX) berücksichtigt. Allerdings weisen diese austauschartigen Terme eine hohe algorithmische Komplexität auf, was sich wiederum oft in einem steilem Skalierungsverhalten der Rechenzeit gegenüber der Systemgröße äußert. Das Hauptziel dieser Arbeit besteht in dem Beweis, dass niedrig- skalierende Algorithmen zur Berechnung der Austauschterme jedoch sehr wohl möglich sind. Wir präsentieren drei Algorithmen, welche die Skalierung von MP2- und SOSEX- Rechnungen von einer quintischen auf eine quartische oder gar kubische Skalierung re- duzieren. Dabei werden ausschließlich analytische Umformungen vorgenommen, sodass keinerlei Genauigkeit geopfert wird. Durch diese niedrigere Skalierung ist es möglich, die Korrelationsenergie mitsamt Austauschtermen für Systeme einiger hundert Valen- zelektronen mit hoher Genauigkeit zu berechnen. Wir stellen ebenfalls drei grundlegend verschiedene stochastische Algorithmen vor, welche die Rechenkosten zum Preis von statistischen Ungenauigkeiten reduzieren. Diese Implementierungen erlauben es, Berech- nungen an noch größeren Systemen vorzunehmen, wenn nur der relative Fehler pro Elek- 5tron entscheident ist. Des weiteren sind alle implementierten Algorithmen hochgradig parallelisiert und damit Hochleistungssoftware. Jegliche Betrachtungen verwenden ebe- nen Wellen, welche eine probate Basis für periodische Systeme darstelle.
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.