Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Birkhäuser Basel eBooks

Decodierung und Fehlerkorrektur

Frank J. Furrer

Published Jan 1, 1981• 0 citations
Publisher

Abstract

Die Codierung eines Block-Codes kann verstanden werden als die Zuordnung der Elemente einer Menge (nämlich der 2k möglichen Kombinationen von k Informationsbit) zu ausgewählten Elementen einer grösseren Menge (nämlich der 2n möglichen Kombinationen von n Bit). Die ausgewählten n-stelligen Kombinationen werden die Codewörter des Codes genannt. Die Zuordnung der Codewörter zur Information lässt sich durch eine Tabelle (z.Bsp. Tabelle 2.1) oder durch ein Rechenverfahren (Abschnitte 4.6–4.10) definieren und wird Codiervorschrift genannt (Bild 2.5). Dadurch, dass wesentlich mehr Kombinationen von n Bit zur Auswahl zur Verfügung stehen als Informationsblöcke übertragen werden sollen, kann dem Satz von ausgewählten Codewörtern eine Fehlererkennungs- oder Fehlerkorrekturfahigkeit gegeben werden.

DOI
10.1007/978-3-0348-5818-2_5

Related papers

Soft-Decision Decodierung langer Blockcodes mit Informationsmengen

Dulte José de Barros

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.

•Jul 26, 2000•2 citations

Rekursive Codes mit der Plotkin-Konstruktion und ihre Decodierung

N. Stolte

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.

•Jan 1, 2008•59 citations

Charakterisierung von Quantenlogiken durch numerische Ereignisse

Alexandra Bergmayr

Der Begriff Quantenlogik geht auf Von Neumann und Birkhoff zurück, welche darunter den Verband der abgeschlossenen Unterräume eines separablen Hilbertraumes verstanden haben. In Verallgemeinerung davon werden verschiedene Klassen von Halbordnungen als Quantenlogiken bezeichnet.Ist eine Quantenlogik nicht von vornherein bekannt, so kann man versuchen, mit Hilfe von Messungen, welche zu sog. numerischen Ereignissen führen, diese zu charakterisieren. Insbesondere ist von Interesse, ob man es dann mit einem klassischen oder quantenmechanischen Phänomen zu tun hat.Sei S eine Menge von Zuständen eines physikalischen Systems und p(s) die Wahrscheinlichkeit des Eintretens eines Ereignisses, wenn sich das System im Zustand sausS befindet. Dann definiert p(s) eine Funktion von S nach [0, 1], welche als numerisches Ereignis, genauer, als S-Wahrscheinlichkeit, bezeichnet wird. Ordnet man eine Menge P von S-Wahrscheinlichkeiten bezüglich der Ordnung von reellen Funktionen, schließt die konstanten Funktionen 0 und 1 mit ein und verlangt, dass mit jedem pausP auch 1-p zu P gehört, so erhält man eine halbgeordnete Menge, welche als Quantenlogik interpretiert werden kann. Nach einer Einführung in benötigte physikalische Grundlagen werden verschiedene Klassen von solchen Quantenlogiken hinsichtlich ihrer Struktur untersucht, wobei insbesondere der Frage nachgegangen wird, wann diese Boolesche Algebren bilden, was charakteristisch für das Vorliegen eines klassischen physikalischen Systems ist. Ferner werden Zusammenhänge zwischen verschiedenen Klassen von numerischen Ereignissen studiert, algebraische Repräsentationen angegeben und auf verschiedene Weisen die für die Erkennung eines klassischen Systems so wesentliche Eigenschaft charakterisiert, dass zwei S-Wahrscheinlichkeiten miteinander kommutieren. Darüber hinaus werden Familien von aus Korrelationswahrscheinlichkeiten zusammengesetzten Ungleichungen behandelt, welche die aus der Physik bekannten Bellschen-Ungleichungen verallgemeinern.

•Nov 1, 2021•0 citations

Weniger ist mehr. Über die Theorie und Anwendung von schwachen und unscharfen Messungen in der Quantenmechanik

Thomas Konrad

In dieser Arbeit wird eine spezielle Klasse verallgemeinerter Messungen in der Quantenmechanik untersucht. Es handelt sich um sogenannte unscharfe Messungen. Mathematisch sind sie durch vertauschende Effekte und reine Operationen (d.h. reine Zustände werden durch den Messprozess auf reine Zustände abgebildet) gekennzeichnet. Physikalisch bedeutet das, man kann sie als Messungen herkömmlicher Messgrößen wie z.B. Energie, Ort oder Spin auffassen, und sie produzieren kein klassisches Rauschen. In der Praxis treten sie u.a. auf, wenn die Kopplung zwischen Messgerät und zu vermessendem System sehr schwach ist. Daher sind sie verwandt mit den schwachen Messungen von Aharonov und Vaidman, die über eine solche schwache Kopplung definiert sind. Die Streuung der Messwerte einer unscharfen Messung ist größer als die einer vergleichbaren Projektionsmessung, daher die Bezeichnung "unscharf". Damit verbunden ist aber häufig auch eine geringere Störung des zu vermessenden Systems. Falls die Störung gering ist, wird die Messung auch "schwach" genannt. Das Verhältnis zwischen Informationsgewinn und Störung (Zustandsänderung) durch die Messung nimmt für minimale, unscharfe Messungen eine einfache Form an: die Zustandsänderung entspricht der Änderung der Wahrscheinlichkeitverteilung der Messergebnisse. Da letztere wiederum dem Informationsgewinn durch die Messung entspricht (der Informationsgewinn kann durch die negative Änderung der Shannon-Entropie gemessen werden), sind Informationsgewinn und Störung äquivalent. Die Messung von Dynamik an einem einzelnen Quantensystem in Echtzeit ist ein Anwendungsgebiet für unscharfe Messungen. Ein Folge von unscharfen Messungen wird in dieser Arbeit vorgestellt, die die Rabioszillationen eines einzelnen Zwei-Niveau-Systems in Echtzeit gewährleisten soll. Als Maß für die Auflösung einer kurzen Sequenz von Messungen (N-Serie) wurde die sogenannte Niveau-Auflösungszeit aus der Streuung der Messresultate einer N-Serie gewonnen. Es stellte sich heraus, dass diese proportional zur Dekohärenzzeit ist, die ein Maß für die Störung des Zwei-Niveau-Systems darstellt. Monte-Carlo-Simulationen der sequentiellen Messung zeigen, dass eine Visualisierung der Rabioszillationen möglich ist. Bedingung dafür ist, dass die Niveau-Auflösungszeit ungefähr gleich der Rabi-Periode ist. Eine Realisierung einer Folge von unscharfen Messungen wird anhand eines quantenoptischen Systems aus der Hohlraumresonator-QED beschrieben. Schliesslich wird die Entwicklung eines Qubits mit Hamiltonischer Dynamik unter dem Einfluss einer Folge von unscharfen Messungen beschrieben. Differenzengleichungen werden hergeleitet um die zeitliche Entwicklung des Zwei-Niveau-Systems darzustellen. Verschiedene Effekte treten auf: u.a. eine zusätzliche unitäre Dynamik, verursacht durch den unitären Anteil der Back-action'' des Messapparates und Dekohärenz aufgrund dieses unitären Anteils sowie aufgrund des Informationsgewinnes. Es kommt auch zu einer Art Reibung (Dissipation). Im Grenzwert kontinuierlicher Messungen verschwinden die meisten dieser Effekte. Für diesen Grenzwert wird eine Mastergleichung angegeben, die die Zustandsdynamik bei einer sequentiellen Messung näherungsweise beschreibt. Das erste Kapitel dieser Arbeit enthält eine Diskussion der Auswirkungen der Stochastik auf die Struktur der Quantenmechanik. Ausgehend von der Zufälligkeit des Ausganges von Quantenmessungen und der nicht-eindeutigen Zerlegbarkeit von gemischten Zuständen in reine Zustände ergibt sich eine Motivation für drei der vier Axiome der Quantenmechanik.

•Jan 1, 2003•0 citations

Cryptographic Protocols from Physical Assumptions

Alexander Koch

Moderne Kryptographie erlaubt nicht nur, personenbezogene Daten im Internet zu schützen oder sich für bestimmte Dienste zu authentifizieren, sondern ermöglicht auch das Auswerten einer Funktion auf geheimen Eingaben mehrerer Parteien, ohne dass dabei etwas über diese Eingaben gelernt werden kann (mit der Ausnahme von Informationen, die aus der Ausgabe und eigenen Eingaben effizient abgeleitet werden können). Kryptographische Protokolle dieser Art werden sichere Mehrparteienberechnung genannt und eignen sich für ein breites Anwendungsspektrum, wie z.B. geheime Abstimmungen und Auktionen. Um die Sicherheit solcher Protokolle zu beweisen, werden Annahmen benötigt, die oft komplexitätstheoretischer Natur sind, beispielsweise, dass es schwierig ist, hinreichend große Zahlen zu faktorisieren. Sicherheitsannahmen, die auf physikalischen Prinzipien basieren, bieten im Gegensatz zu komplexitätstheoretischen Annahmen jedoch einige Vorteile: die Protokolle sind meist konzeptionell einfacher, die Sicherheit ist unabhängig von den Berechnungskapazitäten des Angreifers, und die Funktionsweise und Sicherheit ist oft für den Menschen leichter nachvollziehbar. (Zum Beispiel forderte das Bundesverfassungsgericht: „Beim Einsatz elektronischer Wahlgeräte müssen die wesentlichen Schritte der Wahlhandlung und der Ergebnisermittlung vom Bürger zuverlässig und ohne besondere Sachkenntnis überprüft werden können.“ (BVerfG, Urteil des Zweiten Senats vom 03. März 2009)). Beispiele für solche Annahmen sind physikalisch getrennte oder unkorrumpierbare Hardware-Komponenten (vgl. Broadnax et al., 2018), Write-Only-Geräte für Logging, oder frei zu rubbelnde Felder, wie man sie von PIN-Briefen kennt. Auch die aus der Quantentheorie folgende Nicht-Duplizierbarkeit von Quantenzuständen ist eine physikalische Sicherheitsannahme, die z.B. verwendet wird, um nicht-klonbares „Quantengeld“ zu realisieren. In der vorliegenden Dissertation geht es neben Protokollen, die die Sicherheit und Isolation bestimmter einfacher Hardware-Komponenten als Vertrauensanker verwenden, im Besonderen um kryptographischen Protokolle für die sichere Mehrparteienberechnung, die mit Hilfe physikalischer Spielkarten durchgeführt werden. Die Sicherheitsannahme besteht darin, dass die Karten ununterscheidbare Rückseiten haben und, dass bestimmte Mischoperationen sicher durchgeführt werden können. Eine Anwendung dieser Protokolle liegt also in der Veranschaulichung von Kryptographie und in der Ermöglichung sicherer Mehrparteienberechnungen, die gänzlich ohne Computer ausgeführt werden können. Ein Ziel in diesem Bereich der Kryptographie ist es, Protokolle anzugeben, die möglichst wenige Karten benötigen – und sie als optimal in diesem Sinne zu beweisen. Abhängig von Anforderungen an das Laufzeitverhalten (endliche vs. lediglich im Erwartungswert endliche Laufzeit) und an die Praktikabilität der eingesetzten Mischoperationen, ergeben sich unterschiedliche untere Schranken für die mindestens benötigte Kartenanzahl. Im Rahmen der Arbeit wird für jede Kombination dieser Anforderungen ein UND-Protokoll – ein logisches UND zweier in Karten codierter Bits; dieses ist zusammen mit der Negation und dem Kopieren von Bits hinreichend für die Realisierung allgemeiner Schaltkreise – konstruiert oder in der Literatur identifiziert, das mit der minimalen Anzahl an Karten auskommt, und dies auch als Karten-minimal bewiesen. Insgesamt ist UND mit vier (für erwartet endliche Laufzeit (Koch, Walzer und Härtel, 2015; Koch, 2018)), fünf (für praktikable Mischoperationen oder endliche Laufzeit (Koch, Walzer und Härtel, 2015; Koch, 2018)) oder sechs Karten (für endliche Laufzeit und gleichzeitig praktikable Mischoperationen (Kastner et al., 2017)) möglich und optimal. Für die notwendigen Struktureinsichten wurden so-genannte „Zustandsdiagramme“ mit zugehörigen Kalkülregeln entwickelt, die eine graphenbasierte Darstellung aller möglichen Protokolldurchläufe darstellen und an denen Korrektheit und Sicherheit der Protokolle direkt ablesbar sind (Koch, Walzer und Härtel, 2015; Kastner et al., 2017). Dieser Kalkül hat seitdem eine breite Verwendung in der bereichsrelevanten Literatur gefunden. (Beweise für untere Schranken bzgl. der Kartenanzahl werden durch den Kalkül zu Beweisen, die zeigen, dass bestimmte Protokollzustände in einer bestimmten kombinatorischen Graphenstruktur nicht erreichbar sind.) Mit Hilfe des Kalküls wurden Begriffe der Spielkartenkryptographie als C-Programm formalisiert und (unter bestimmten Einschränkungen) mit einem „Software Bounded Model Checking“-Ansatz die Längenminimalität eines kartenminimalen UND-Protokolls bewiesen (Koch, Schrempp und Kirsten, 2019). Darüber hinaus werden konzeptionell einfache Protokolle für den Fall einer sicheren Mehrparteienberechnung angegeben, bei der sogar zusätzlich die zu berechnende Funktion geheim bleiben soll (Koch und Walzer, 2018), und zwar für jedes der folgenden Berechnungsmodelle: (universelle) Schaltkreise, binäre Entscheidungsdiagramme, Turingmaschinen und RAM-Maschinen. Es wird zudem untersucht, wie Karten-basierte Protokolle so ausgeführt werden können, dass die einzige Interaktion darin besteht, dass andere Parteien die korrekte Ausführung überwachen. Dies ermöglicht eine (schwach interaktive) Programm-Obfuszierung, bei der eine Partei ein durch Karten codiertes Programm auf eigenen Eingaben ausführen kann, ohne etwas über dessen interne Funktionsweise zu lernen, das über das Ein-/Ausgabeverhalten hinaus geht. Dies ist ohne derartige physikalische Annahmen i.A. nicht möglich. Zusätzlich wird eine Sicherheit gegen Angreifer, die auch vom Protokoll abweichen dürfen, formalisiert und es wird eine Methode angegeben um unter möglichst schwachen Sicherheitsannahmen ein passiv sicheres Protokoll mechanisch in ein aktiv sicheres zu transformieren (Koch und Walzer, 2017). Eine weitere, in der Dissertation untersuchte physikalische Sicherheitsannahme, ist die Annahme primitiver, unkorrumpierbarer Hardware-Bausteine, wie z.B. einen TAN-Generator. Dies ermöglicht z.B. eine sichere Authentifikation des menschlichen Nutzers über ein korrumpiertes Terminal, ohne dass der Nutzer selbst kryptographische Berechnungen durchführen muss (z.B. große Primzahlen zu multiplizieren). Dies wird am Beispiel des Geldabhebens an einem korrumpierten Geldautomaten mit Hilfe eines als sicher angenommenen zweiten Geräts (Achenbach et al., 2019) und mit möglichst schwachen Anforderungen an die vorhandenen Kommunikationskanäle gelöst. Da das angegebene Protokoll auch sicher ist, wenn es beliebig mit anderen gleichzeitig laufenden Protokollen ausgeführt wird (also sogenannte Universelle Komponierbarkeit aufweist), es modular entworfen wurde, und die Sicherheitsannahme glaubwürdig ist, ist die Funktionsweise für den Menschen transparent und nachvollziehbar. Insgesamt bildet die Arbeit durch die verschiedenen Karten-basierten Protokolle, Kalküle und systematisierten Beweise für untere Schranken bzgl. der Kartenanzahl, sowie durch Ergebnisse zur sicheren Verwendung eines nicht-vertrauenswürdigen Terminals, und einer Einordnung dieser in eine systematische Darstellung der verschiedenen, in der Kryptographie verwendeten physikalischen Annahmen, einen wesentlichen Beitrag zur physikalisch-basierten Kryptographie.

•Jan 1, 2019•16 citations

Einfache Codes

Kurt-Ulrich Witt

ZusammenfassungIn diesem Kapitel beschäftigen wir uns einführend mit sehr einfachen Codes: Block-Codes und linearen Codes. Dabei lernen wir weitere Begriffe kennen, die benötigt werden, um später bestimmte Qualitäten von Codes, wie Fehelererkennung und -korrektur, zu beschreiben.

Vieweg+Teubner eBooks•Jan 1, 2001•0 citations
Die Codierung eines Block-Codes kann verstanden werden als die Zuordnung der Elemente einer Menge (nämlich der 2k möglichen Kombinationen von k Informationsbit) zu ausgewählten Elementen einer grösseren Menge (nämlich der 2n möglichen Kombinationen von n Bit). Die ausgewählten n-stelligen Kombinationen werden die Codewörter des Codes genannt. Die Zuordnung der Codewörter zur Information lässt sich durch eine Tabelle (z.Bsp. Tabelle 2.1) oder durch ein Rechenverfahren (Abschnitte 4.6–4.10) definieren und wird Codiervorschrift genannt (Bild 2.5). Dadurch, dass wesentlich mehr Kombinationen von n Bit zur Auswahl zur Verfügung stehen als Informationsblöcke übertragen werden sollen, kann dem Satz von ausgewählten Codewörtern eine Fehlererkennungs- oder Fehlerkorrekturfahigkeit gegeben werden.
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.
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.
Der Begriff Quantenlogik geht auf Von Neumann und Birkhoff zurück, welche darunter den Verband der abgeschlossenen Unterräume eines separablen Hilbertraumes verstanden haben. In Verallgemeinerung davon werden verschiedene Klassen von Halbordnungen als Quantenlogiken bezeichnet.Ist eine Quantenlogik nicht von vornherein bekannt, so kann man versuchen, mit Hilfe von Messungen, welche zu sog. numerischen Ereignissen führen, diese zu charakterisieren. Insbesondere ist von Interesse, ob man es dann mit einem klassischen oder quantenmechanischen Phänomen zu tun hat.Sei S eine Menge von Zuständen eines physikalischen Systems und p(s) die Wahrscheinlichkeit des Eintretens eines Ereignisses, wenn sich das System im Zustand sausS befindet. Dann definiert p(s) eine Funktion von S nach [0, 1], welche als numerisches Ereignis, genauer, als S-Wahrscheinlichkeit, bezeichnet wird. Ordnet man eine Menge P von S-Wahrscheinlichkeiten bezüglich der Ordnung von reellen Funktionen, schließt die konstanten Funktionen 0 und 1 mit ein und verlangt, dass mit jedem pausP auch 1-p zu P gehört, so erhält man eine halbgeordnete Menge, welche als Quantenlogik interpretiert werden kann. Nach einer Einführung in benötigte physikalische Grundlagen werden verschiedene Klassen von solchen Quantenlogiken hinsichtlich ihrer Struktur untersucht, wobei insbesondere der Frage nachgegangen wird, wann diese Boolesche Algebren bilden, was charakteristisch für das Vorliegen eines klassischen physikalischen Systems ist. Ferner werden Zusammenhänge zwischen verschiedenen Klassen von numerischen Ereignissen studiert, algebraische Repräsentationen angegeben und auf verschiedene Weisen die für die Erkennung eines klassischen Systems so wesentliche Eigenschaft charakterisiert, dass zwei S-Wahrscheinlichkeiten miteinander kommutieren. Darüber hinaus werden Familien von aus Korrelationswahrscheinlichkeiten zusammengesetzten Ungleichungen behandelt, welche die aus der Physik bekannten Bellschen-Ungleichungen verallgemeinern.
In dieser Arbeit wird eine spezielle Klasse verallgemeinerter Messungen in der Quantenmechanik untersucht. Es handelt sich um sogenannte unscharfe Messungen. Mathematisch sind sie durch vertauschende Effekte und reine Operationen (d.h. reine Zustände werden durch den Messprozess auf reine Zustände abgebildet) gekennzeichnet. Physikalisch bedeutet das, man kann sie als Messungen herkömmlicher Messgrößen wie z.B. Energie, Ort oder Spin auffassen, und sie produzieren kein klassisches Rauschen. In der Praxis treten sie u.a. auf, wenn die Kopplung zwischen Messgerät und zu vermessendem System sehr schwach ist. Daher sind sie verwandt mit den schwachen Messungen von Aharonov und Vaidman, die über eine solche schwache Kopplung definiert sind. Die Streuung der Messwerte einer unscharfen Messung ist größer als die einer vergleichbaren Projektionsmessung, daher die Bezeichnung "unscharf". Damit verbunden ist aber häufig auch eine geringere Störung des zu vermessenden Systems. Falls die Störung gering ist, wird die Messung auch "schwach" genannt. Das Verhältnis zwischen Informationsgewinn und Störung (Zustandsänderung) durch die Messung nimmt für minimale, unscharfe Messungen eine einfache Form an: die Zustandsänderung entspricht der Änderung der Wahrscheinlichkeitverteilung der Messergebnisse. Da letztere wiederum dem Informationsgewinn durch die Messung entspricht (der Informationsgewinn kann durch die negative Änderung der Shannon-Entropie gemessen werden), sind Informationsgewinn und Störung äquivalent. Die Messung von Dynamik an einem einzelnen Quantensystem in Echtzeit ist ein Anwendungsgebiet für unscharfe Messungen. Ein Folge von unscharfen Messungen wird in dieser Arbeit vorgestellt, die die Rabioszillationen eines einzelnen Zwei-Niveau-Systems in Echtzeit gewährleisten soll. Als Maß für die Auflösung einer kurzen Sequenz von Messungen (N-Serie) wurde die sogenannte Niveau-Auflösungszeit aus der Streuung der Messresultate einer N-Serie gewonnen. Es stellte sich heraus, dass diese proportional zur Dekohärenzzeit ist, die ein Maß für die Störung des Zwei-Niveau-Systems darstellt. Monte-Carlo-Simulationen der sequentiellen Messung zeigen, dass eine Visualisierung der Rabioszillationen möglich ist. Bedingung dafür ist, dass die Niveau-Auflösungszeit ungefähr gleich der Rabi-Periode ist. Eine Realisierung einer Folge von unscharfen Messungen wird anhand eines quantenoptischen Systems aus der Hohlraumresonator-QED beschrieben. Schliesslich wird die Entwicklung eines Qubits mit Hamiltonischer Dynamik unter dem Einfluss einer Folge von unscharfen Messungen beschrieben. Differenzengleichungen werden hergeleitet um die zeitliche Entwicklung des Zwei-Niveau-Systems darzustellen. Verschiedene Effekte treten auf: u.a. eine zusätzliche unitäre Dynamik, verursacht durch den unitären Anteil der Back-action'' des Messapparates und Dekohärenz aufgrund dieses unitären Anteils sowie aufgrund des Informationsgewinnes. Es kommt auch zu einer Art Reibung (Dissipation). Im Grenzwert kontinuierlicher Messungen verschwinden die meisten dieser Effekte. Für diesen Grenzwert wird eine Mastergleichung angegeben, die die Zustandsdynamik bei einer sequentiellen Messung näherungsweise beschreibt. Das erste Kapitel dieser Arbeit enthält eine Diskussion der Auswirkungen der Stochastik auf die Struktur der Quantenmechanik. Ausgehend von der Zufälligkeit des Ausganges von Quantenmessungen und der nicht-eindeutigen Zerlegbarkeit von gemischten Zuständen in reine Zustände ergibt sich eine Motivation für drei der vier Axiome der Quantenmechanik.
Moderne Kryptographie erlaubt nicht nur, personenbezogene Daten im Internet zu schützen oder sich für bestimmte Dienste zu authentifizieren, sondern ermöglicht auch das Auswerten einer Funktion auf geheimen Eingaben mehrerer Parteien, ohne dass dabei etwas über diese Eingaben gelernt werden kann (mit der Ausnahme von Informationen, die aus der Ausgabe und eigenen Eingaben effizient abgeleitet werden können). Kryptographische Protokolle dieser Art werden sichere Mehrparteienberechnung genannt und eignen sich für ein breites Anwendungsspektrum, wie z.B. geheime Abstimmungen und Auktionen. Um die Sicherheit solcher Protokolle zu beweisen, werden Annahmen benötigt, die oft komplexitätstheoretischer Natur sind, beispielsweise, dass es schwierig ist, hinreichend große Zahlen zu faktorisieren. Sicherheitsannahmen, die auf physikalischen Prinzipien basieren, bieten im Gegensatz zu komplexitätstheoretischen Annahmen jedoch einige Vorteile: die Protokolle sind meist konzeptionell einfacher, die Sicherheit ist unabhängig von den Berechnungskapazitäten des Angreifers, und die Funktionsweise und Sicherheit ist oft für den Menschen leichter nachvollziehbar. (Zum Beispiel forderte das Bundesverfassungsgericht: „Beim Einsatz elektronischer Wahlgeräte müssen die wesentlichen Schritte der Wahlhandlung und der Ergebnisermittlung vom Bürger zuverlässig und ohne besondere Sachkenntnis überprüft werden können.“ (BVerfG, Urteil des Zweiten Senats vom 03. März 2009)). Beispiele für solche Annahmen sind physikalisch getrennte oder unkorrumpierbare Hardware-Komponenten (vgl. Broadnax et al., 2018), Write-Only-Geräte für Logging, oder frei zu rubbelnde Felder, wie man sie von PIN-Briefen kennt. Auch die aus der Quantentheorie folgende Nicht-Duplizierbarkeit von Quantenzuständen ist eine physikalische Sicherheitsannahme, die z.B. verwendet wird, um nicht-klonbares „Quantengeld“ zu realisieren. In der vorliegenden Dissertation geht es neben Protokollen, die die Sicherheit und Isolation bestimmter einfacher Hardware-Komponenten als Vertrauensanker verwenden, im Besonderen um kryptographischen Protokolle für die sichere Mehrparteienberechnung, die mit Hilfe physikalischer Spielkarten durchgeführt werden. Die Sicherheitsannahme besteht darin, dass die Karten ununterscheidbare Rückseiten haben und, dass bestimmte Mischoperationen sicher durchgeführt werden können. Eine Anwendung dieser Protokolle liegt also in der Veranschaulichung von Kryptographie und in der Ermöglichung sicherer Mehrparteienberechnungen, die gänzlich ohne Computer ausgeführt werden können. Ein Ziel in diesem Bereich der Kryptographie ist es, Protokolle anzugeben, die möglichst wenige Karten benötigen – und sie als optimal in diesem Sinne zu beweisen. Abhängig von Anforderungen an das Laufzeitverhalten (endliche vs. lediglich im Erwartungswert endliche Laufzeit) und an die Praktikabilität der eingesetzten Mischoperationen, ergeben sich unterschiedliche untere Schranken für die mindestens benötigte Kartenanzahl. Im Rahmen der Arbeit wird für jede Kombination dieser Anforderungen ein UND-Protokoll – ein logisches UND zweier in Karten codierter Bits; dieses ist zusammen mit der Negation und dem Kopieren von Bits hinreichend für die Realisierung allgemeiner Schaltkreise – konstruiert oder in der Literatur identifiziert, das mit der minimalen Anzahl an Karten auskommt, und dies auch als Karten-minimal bewiesen. Insgesamt ist UND mit vier (für erwartet endliche Laufzeit (Koch, Walzer und Härtel, 2015; Koch, 2018)), fünf (für praktikable Mischoperationen oder endliche Laufzeit (Koch, Walzer und Härtel, 2015; Koch, 2018)) oder sechs Karten (für endliche Laufzeit und gleichzeitig praktikable Mischoperationen (Kastner et al., 2017)) möglich und optimal. Für die notwendigen Struktureinsichten wurden so-genannte „Zustandsdiagramme“ mit zugehörigen Kalkülregeln entwickelt, die eine graphenbasierte Darstellung aller möglichen Protokolldurchläufe darstellen und an denen Korrektheit und Sicherheit der Protokolle direkt ablesbar sind (Koch, Walzer und Härtel, 2015; Kastner et al., 2017). Dieser Kalkül hat seitdem eine breite Verwendung in der bereichsrelevanten Literatur gefunden. (Beweise für untere Schranken bzgl. der Kartenanzahl werden durch den Kalkül zu Beweisen, die zeigen, dass bestimmte Protokollzustände in einer bestimmten kombinatorischen Graphenstruktur nicht erreichbar sind.) Mit Hilfe des Kalküls wurden Begriffe der Spielkartenkryptographie als C-Programm formalisiert und (unter bestimmten Einschränkungen) mit einem „Software Bounded Model Checking“-Ansatz die Längenminimalität eines kartenminimalen UND-Protokolls bewiesen (Koch, Schrempp und Kirsten, 2019). Darüber hinaus werden konzeptionell einfache Protokolle für den Fall einer sicheren Mehrparteienberechnung angegeben, bei der sogar zusätzlich die zu berechnende Funktion geheim bleiben soll (Koch und Walzer, 2018), und zwar für jedes der folgenden Berechnungsmodelle: (universelle) Schaltkreise, binäre Entscheidungsdiagramme, Turingmaschinen und RAM-Maschinen. Es wird zudem untersucht, wie Karten-basierte Protokolle so ausgeführt werden können, dass die einzige Interaktion darin besteht, dass andere Parteien die korrekte Ausführung überwachen. Dies ermöglicht eine (schwach interaktive) Programm-Obfuszierung, bei der eine Partei ein durch Karten codiertes Programm auf eigenen Eingaben ausführen kann, ohne etwas über dessen interne Funktionsweise zu lernen, das über das Ein-/Ausgabeverhalten hinaus geht. Dies ist ohne derartige physikalische Annahmen i.A. nicht möglich. Zusätzlich wird eine Sicherheit gegen Angreifer, die auch vom Protokoll abweichen dürfen, formalisiert und es wird eine Methode angegeben um unter möglichst schwachen Sicherheitsannahmen ein passiv sicheres Protokoll mechanisch in ein aktiv sicheres zu transformieren (Koch und Walzer, 2017). Eine weitere, in der Dissertation untersuchte physikalische Sicherheitsannahme, ist die Annahme primitiver, unkorrumpierbarer Hardware-Bausteine, wie z.B. einen TAN-Generator. Dies ermöglicht z.B. eine sichere Authentifikation des menschlichen Nutzers über ein korrumpiertes Terminal, ohne dass der Nutzer selbst kryptographische Berechnungen durchführen muss (z.B. große Primzahlen zu multiplizieren). Dies wird am Beispiel des Geldabhebens an einem korrumpierten Geldautomaten mit Hilfe eines als sicher angenommenen zweiten Geräts (Achenbach et al., 2019) und mit möglichst schwachen Anforderungen an die vorhandenen Kommunikationskanäle gelöst. Da das angegebene Protokoll auch sicher ist, wenn es beliebig mit anderen gleichzeitig laufenden Protokollen ausgeführt wird (also sogenannte Universelle Komponierbarkeit aufweist), es modular entworfen wurde, und die Sicherheitsannahme glaubwürdig ist, ist die Funktionsweise für den Menschen transparent und nachvollziehbar. Insgesamt bildet die Arbeit durch die verschiedenen Karten-basierten Protokolle, Kalküle und systematisierten Beweise für untere Schranken bzgl. der Kartenanzahl, sowie durch Ergebnisse zur sicheren Verwendung eines nicht-vertrauenswürdigen Terminals, und einer Einordnung dieser in eine systematische Darstellung der verschiedenen, in der Kryptographie verwendeten physikalischen Annahmen, einen wesentlichen Beitrag zur physikalisch-basierten Kryptographie.