Expander-Code - Expander code

Expander-Codes
zweiteiliger Expander-Graph
Einstufung
Art	Linearer Blockcode
Blocklänge	${\ displaystyle n}$
Nachrichtenlänge	${\ displaystyle nm}$
Bewertung	${\ displaystyle 1-m / n}$
Entfernung	${\ displaystyle 2 (1- \ epsilon) \ gamma \ cdot n}$
Alphabet Größe	${\ displaystyle 2}$
Notation	${\ displaystyle [n, nm, 2 (1- \ epsilon) \ gamma \ cdot n] _ {2}}$-Code
v t e

In der Codierungstheorie bilden Expander-Codes eine Klasse von Fehlerkorrekturcodes , die aus zweigeteilten Expander-Graphen aufgebaut sind . Neben Justesen-Codes sind Expander-Codes von besonderem Interesse, da sie eine konstante positive Rate , einen konstanten positiven relativen Abstand und eine konstante Alphabetgröße aufweisen . Tatsächlich enthält das Alphabet nur zwei Elemente, sodass Expander-Codes zur Klasse der Binärcodes gehören . Darüber hinaus können Expander-Codes zeitlich proportional zur Blocklänge des Codes sowohl codiert als auch decodiert werden.

Expander-Codes

In der Codierungstheorie ist ein Expander-Code ein linearer Blockcode, dessen Paritätsprüfmatrix die Adjazenzmatrix eines zweigeteilten Expander-Graphen ist . Diese Codes haben einen guten relativen Abstand , wobei und sind Eigenschaften des Expander-Graphen (wie später definiert), Rate und Decodierbarkeit (Algorithmen der Laufzeit existieren). ${\ displaystyle [n, nm] _ {2} \,}$ ${\ displaystyle 2 (1- \ varepsilon) \ gamma \,}$${\ displaystyle \ varepsilon \,}$${\ displaystyle \ gamma \,}$ ${\ displaystyle \ left (1 - {\ tfrac {m} {n}} \ right) \,}$${\ displaystyle O (n) \,}$

Definition

Betrachten wir einen zweiteiligen Graphen , wo und sind die Knotenmengen und ist der Satz von Kanten verbindenden Vertices in an Eckpunkten . Angenommen, jeder Scheitelpunkt in hat einen Grad (der Graph ist -left- regulär ) , und , . Dann ist ein Expander Graph wenn jede klein genug , um Teilmenge , hat die Eigenschaft , dass zumindest hat in verschiedene Nachbarn . Beachten Sie, dass dies trivial für gilt . Wann und für eine Konstante sagen wir, dass dies ein verlustfreier Expander ist. ${\ displaystyle G (L, R, E) \,}$${\ displaystyle L \,}$${\ displaystyle R \,}$${\ displaystyle E \,}$${\ displaystyle L \,}$${\ displaystyle R \,}$${\ displaystyle L \,}$ ${\ displaystyle d \,}$${\ displaystyle d \,}$${\ displaystyle | L | = n \,}$${\ displaystyle | R | = m \,}$${\ displaystyle m <n \,}$${\ displaystyle G \,}$${\ displaystyle (n, m, d, \ gamma, \ alpha) \,}$${\ displaystyle S \ subset L \,}$${\ displaystyle | S | \ leq \ gamma n \,}$${\ displaystyle S \,}$${\ displaystyle d \ alpha | S | \,}$${\ displaystyle R \,}$${\ displaystyle \ gamma \ leq {\ tfrac {1} {n}} \,}$${\ displaystyle {\ tfrac {1} {n}} <\ gamma \ leq 1 \,}$${\ displaystyle \ alpha = 1- \ varepsilon \,}$${\ displaystyle \ varepsilon \,}$${\ displaystyle G \,}$

Da es sich um einen zweigeteilten Graphen handelt, können wir seine Adjazenzmatrix betrachten. Dann ist der lineare Code , der durch Betrachten der Transponierten dieser Matrix als Paritätsprüfungsmatrix erzeugt wird, ein Expander-Code. ${\ displaystyle G \,}$${\ displaystyle n \ times m \,}$${\ displaystyle C \,}$

Es wurde gezeigt, dass nichttriviale verlustfreie Expander-Graphen existieren. Darüber hinaus können wir sie explizit konstruieren.

Bewertung

Die Rate von ist seine Dimension geteilt durch seine Blocklänge. In diesem Fall hat die Paritätsprüfmatrix eine Größe und daher mindestens eine Dimension . ${\ displaystyle C \,}$${\ displaystyle m \ times n \,}$${\ displaystyle C \,}$${\ displaystyle (nm) / n = 1 - {\ tfrac {m} {n}} \,}$

Entfernung

Angenommen, wir nehmen an . Dann beträgt der Abstand eines Expander-Codes mindestens . ${\ displaystyle \ varepsilon <{\ tfrac {1} {2}} \,}$${\ displaystyle (n, m, d, \ gamma, 1- \ varepsilon) \,}$${\ displaystyle C \,}$${\ displaystyle 2 (1- \ varepsilon) \ gamma n \,}$

Beweis

Beachten Sie, dass wir jedes Codewort in als eine Teilmenge von Scheitelpunkten betrachten können , indem wir diesen Scheitelpunkt genau dann sagen, wenn der th-Index des Codeworts eine 1 ist. Dann ist ein Codewort, wenn jeder Scheitelpunkt neben einer geraden Anzahl von Scheitelpunkten in liegt . (Um ein Codewort zu sein, wo ist die Paritätsprüfungsmatrix? Dann entspricht jeder Scheitelpunkt in jeder Spalte von . Die Matrixmultiplikation über ergibt dann das gewünschte Ergebnis.) Wenn also ein Scheitelpunkt neben einem einzelnen Scheitelpunkt in liegt , Wir wissen sofort, dass dies kein Codewort ist. Lassen Sie bezeichnen die Nachbarn in der , und jene Nachbarn bezeichnen die sind einzigartig, dh neben einem einzelnen Scheitelpunkt . ${\ displaystyle c \,}$${\ displaystyle C \,}$${\ displaystyle S \ subset L \,}$${\ displaystyle v_ {i} \ in S \,}$${\ displaystyle i \,}$${\ displaystyle c \,}$${\ displaystyle v \ in R \,}$${\ displaystyle S \,}$${\ displaystyle cP = 0 \,}$${\ displaystyle P \,}$${\ displaystyle R \,}$${\ displaystyle P \,}$${\ displaystyle {\ text {GF}} (2) = \ {0,1 \} \,}$${\ displaystyle v \ in R \,}$${\ displaystyle S \,}$${\ displaystyle c \,}$${\ displaystyle N (S) \,}$${\ displaystyle R \,}$${\ displaystyle S \,}$${\ displaystyle U (S) \,}$${\ displaystyle S \,}$${\ displaystyle S \,}$

Lemma 1

Für jede Größe , . ${\ displaystyle S \ subset L \,}$${\ displaystyle | S | \ leq \ gamma n \,}$${\ displaystyle d | S | \ geq | N (S) | \ geq | U (S) | \ geq d (1-2 \ varepsilon) | S | \,}$

Beweis

Trivial , da impliziert . folgt, da der Grad jedes Scheitelpunkts in ist . Aufgrund der Erweiterungseigenschaft des Diagramms muss eine Reihe von Kanten vorhanden sein, die zu unterschiedlichen Scheitelpunkten führen. Die restlichen Kanten machen also höchstens Nachbarn nicht eindeutig, also . ${\ displaystyle | N (S) | \ geq | U (S) | \,}$${\ displaystyle v \ in U (S) \,}$${\ displaystyle v \ in N (S) \,}$${\ displaystyle | N (S) | \ leq d | S | \,}$${\ displaystyle S \,}$${\ displaystyle d \,}$${\ displaystyle d (1- \ varepsilon) | S | \,}$${\ displaystyle d \ varepsilon | S | \,}$${\ displaystyle d \ varepsilon | S | \,}$${\ displaystyle U (S) \ geq d (1- \ varepsilon) | S | -d \ varepsilon | S | = d (1-2 \ varepsilon) | S | \,}$

Logische Folge

Jeder ausreichend kleine hat einen einzigartigen Nachbarn. Dies folgt seitdem . ${\ displaystyle S \,}$${\ displaystyle \ varepsilon <{\ tfrac {1} {2}} \,}$

Lemma 2

Jede Teilmenge mit hat einen eindeutigen Nachbarn. ${\ displaystyle T \ subset L \,}$${\ displaystyle | T | <2 (1- \ varepsilon) \ gamma n \,}$

Beweis

Lemma 1 beweist den Fall , nehmen wir also an . Lass so das . Durch Lemma 1 wissen wir das . Dann ist ein Scheitelpunkt in iff , und das wissen wir. Durch den ersten Teil von Lemma 1 wissen wir es . Da , und ist daher nicht leer. ${\ displaystyle | T | \ leq \ gamma n \,}$${\ displaystyle 2 (1- \ varepsilon) \ gamma n> | T |> \ gamma n \,}$${\ displaystyle S \ subset T \,}$${\ displaystyle | S | = \ gamma n \,}$${\ displaystyle | U (S) | \ geq d (1-2 \ varepsilon) | S | \,}$${\ displaystyle v \ in U (S) \,}$${\ displaystyle U (T) \,}$${\ displaystyle v \ notin N (T \ setminus S) \,}$${\ displaystyle | T \ setminus S | \ leq 2 (1- \ varepsilon) \ gamma n- \ gamma n = (1-2 \ varepsilon) \ gamma n \,}$${\ displaystyle | N (T \ setminus S) | \ leq d (1-2 \ varepsilon) \ gamma n \,}$${\ displaystyle \ varepsilon <{\ tfrac {1} {2}} \,}$${\ displaystyle | U (T) | \ geq | U (S) \ setminus N (T \ setminus S) | \ geq | U (S) | - | N (T \ setminus S) |> 0 \,}$${\ displaystyle U (T) \,}$

Logische Folge

Es ist zu beachten, dass, wenn a mindestens 1 eindeutigen Nachbarn hat, dh das entsprechende Wort, das entspricht, kein Codewort sein kann, da es sich nicht mit dem Vektor für alle Nullen mit der Paritätsprüfungsmatrix multipliziert. Durch das vorherige Argument , . Da linear ist, schließen wir, dass mindestens Abstand hat . ${\ displaystyle T \ subset L \,}$${\ displaystyle | U (T) |> 0 \,}$${\ displaystyle c \,}$${\ displaystyle T \,}$${\ displaystyle c \ in C \ impliziert wt (c) \ geq 2 (1- \ varepsilon) \ gamma n \,}$${\ displaystyle C \,}$${\ displaystyle C \,}$${\ displaystyle 2 (1- \ varepsilon) \ gamma n \,}$

Codierung

Die Codierungszeit für einen Expander-Code ist durch die eines allgemeinen linearen Codes begrenzt - durch Matrixmultiplikation. Ein Ergebnis von Spielman zeigt, dass eine Codierung rechtzeitig möglich ist. ${\ displaystyle O (n ^ {2}) \,}$${\ displaystyle O (n) \,}$

Dekodierung

Die Dekodierung von Expander-Codes ist bei Verwendung des folgenden Algorithmus zeitlich möglich . ${\ displaystyle O (n) \,}$${\ displaystyle \ varepsilon <{\ tfrac {1} {4}} \,}$

Sei der Scheitelpunkt , der dem th-Index in den Codewörtern von entspricht . Sei ein empfangenes Wort und . Lassen Sie sein , und sein . Dann betrachten Sie den gierigen Algorithmus: ${\ displaystyle v_ {i} \,}$${\ displaystyle L \,}$${\ displaystyle i \,}$${\ displaystyle C \,}$${\ displaystyle y \ in \ {0,1 \} ^ {n} \,}$${\ displaystyle V (y) = \ {v_ {i} \ mid {\ text {the}} i ^ {\ text {th}} {\ text {position of}} y {\ text {is a}} 1 \} \,}$${\ displaystyle e (i) \,}$${\ displaystyle | \ {v \ in R \ mid v_ {i} \ in N (v) {\ text {und}} N (v) \ cap V (y) {\ text {ist gerade}} \} | \,}$${\ displaystyle o (i) \,}$${\ displaystyle | \ {v \ in R \ mid v_ {i} \ in N (v) {\ text {und}} N (v) \ cap V (y) {\ text {ist ungerade}} \} | \,}$

---

Eingabe: empfangenes Wort . ${\ displaystyle y \,}$

initialize y' to y
while there is a v in R adjacent to an odd number of vertices in V(y')
    if there is an i such that o(i) > e(i)
        flip entry i in y'
    else
        fail

Ausgabe: Fehler oder geändertes Codewort . ${\ displaystyle y '\,}$

---

Beweis

Wir zeigen zuerst die Richtigkeit des Algorithmus und untersuchen dann seine Laufzeit.

Richtigkeit

Wir müssen zeigen, dass der Algorithmus mit dem richtigen Codewort endet, wenn das empfangene Codewort innerhalb der halben Entfernung des Codes vom ursprünglichen Codewort liegt. Die Menge der beschädigten Variablen sei , und die Menge der nicht erfüllten (neben einer ungeraden Anzahl von Eckpunkten) Eckpunkte sei . Das folgende Lemma wird sich als nützlich erweisen. ${\ displaystyle S \,}$${\ displaystyle s = | S | \,}$${\ displaystyle R \,}$${\ displaystyle c \,}$

Lemma 3

Wenn ja , dann gibt es ein mit . ${\ displaystyle 0 <s <\ gamma n \,}$${\ displaystyle v_ {i} \,}$${\ displaystyle o (i)> e (i) \,}$

Beweis

Durch Lemma 1 wissen wir das . Ein durchschnittlicher Scheitelpunkt hat also mindestens eindeutige Nachbarn (erinnern Sie sich, dass eindeutige Nachbarn unzufrieden sind und daher dazu beitragen ), da und somit ein Scheitelpunkt mit . ${\ displaystyle U (S) \ geq d (1-2 \ varepsilon) s \,}$${\ displaystyle d (1-2 \ varepsilon)> d / 2 \,}$${\ displaystyle o (i) \,}$${\ displaystyle \ varepsilon <{\ tfrac {1} {4}} \,}$${\ displaystyle v_ {i} \,}$${\ displaystyle o (i)> e (i) \,}$

Wenn wir also noch kein Codewort erreicht haben, gibt es immer einen Scheitelpunkt zum Umdrehen. Als nächstes zeigen wir, dass die Anzahl der Fehler niemals darüber hinaus zunehmen kann . ${\ displaystyle \ gamma n \,}$

Lemma 4

Wenn wir mit beginnen , erreichen wir zu keinem Zeitpunkt im Algorithmus. ${\ displaystyle s <\ gamma (1-2 \ varepsilon) n \,}$${\ displaystyle s = \ gamma n \,}$

Beweis

Wenn wir einen Vertex - Flip , und untereinander ausgetauscht werden, und da wir hatten , bedeutet dies , die Anzahl von unzufriedenen Vertices auf der rechten Seite verringert sich durch mindestens eine nach jedem flip. Da die anfängliche Anzahl nicht erfüllter Eckpunkte höchstens durch die Regelmäßigkeit des Graphen bestimmt wird . Wenn wir eine Zeichenfolge mit Fehlern erreichen würden, gäbe es nach Lemma 1 mindestens eindeutige Nachbarn, was bedeutet, dass es zumindest unbefriedigte Eckpunkte geben würde, ein Widerspruch. ${\ displaystyle v_ {i} \,}$${\ displaystyle o (i) \,}$${\ displaystyle e (i) \,}$${\ displaystyle o (i)> e (i) \,}$${\ displaystyle s <\ gamma (1-2 \ varepsilon) n \,}$${\ displaystyle d \ gamma (1-2 \ varepsilon) n \,}$${\ displaystyle d \,}$${\ displaystyle \ gamma n \,}$${\ displaystyle d \ gamma (1-2 \ varepsilon) n \,}$${\ displaystyle d \ gamma (1-2 \ varepsilon) n \,}$

Die Lemmas 3 und 4 zeigen uns, dass wir, wenn wir mit (der halben Entfernung von ) beginnen, immer einen Scheitelpunkt finden, den wir umdrehen können. Jeder Flip reduziert die Anzahl der nicht erfüllten Scheitelpunkte um mindestens 1, und daher endet der Algorithmus in den meisten Schritten und endet bei einem Codewort nach Lemma 3. (Wäre es nicht bei einem Codewort, gäbe es einen Scheitelpunkt zum Umdrehen ). Lemma 4 zeigt uns, dass wir niemals weiter als vom richtigen Codewort entfernt sein können. Da der Code eine Entfernung (seit ) hat, muss das Codewort, mit dem er endet, das richtige Codewort sein, da die Anzahl der Bit-Flips weniger als die Hälfte der Entfernung beträgt (wir hätten also nicht weit genug reisen können, um ein anderes Codewort zu erreichen). ${\ displaystyle s <\ gamma (1-2 \ varepsilon) n \,}$${\ displaystyle C \,}$${\ displaystyle v_ {i} \,}$${\ displaystyle R \,}$${\ displaystyle m \,}$${\ displaystyle \ gamma n \,}$${\ displaystyle 2 (1- \ varepsilon) \ gamma n> \ gamma n \,}$${\ displaystyle \ varepsilon <{\ tfrac {1} {2}} \,}$

Komplexität

Wir zeigen nun, dass der Algorithmus eine lineare Zeitdecodierung erreichen kann. Sei konstant und sei der maximale Grad eines Scheitelpunkts in . Beachten Sie, dass dies auch für bekannte Konstruktionen konstant ist. ${\ displaystyle {\ tfrac {n} {m}} \,}$${\ displaystyle r \,}$${\ displaystyle R \,}$${\ displaystyle r \,}$

1. Vorverarbeitung: Es braucht Zeit, um zu berechnen, ob jeder Scheitelpunkt eine ungerade oder gerade Anzahl von Nachbarn hat.${\ displaystyle O (mr) \,}$${\ displaystyle R \,}$
2. Vorverarbeitung 2: Wir nehmen uns Zeit, um eine Liste der Eckpunkte zu berechnen, in denen .${\ displaystyle O (dn) = O (dmr) \,}$${\ displaystyle v_ {i} \,}$${\ displaystyle L \,}$${\ displaystyle o (i)> e (i) \,}$
3. Jede Iteration: Wir entfernen einfach das erste Listenelement. Um die Liste der ungeraden / geraden Eckpunkte in zu aktualisieren , müssen nur Einträge aktualisiert und nach Bedarf eingefügt / entfernt werden. Wir aktualisieren dann Einträge in der Liste der Eckpunkte mit ungeraderen als geraden Nachbarn und fügen sie nach Bedarf ein / aus. Somit braucht jede Iteration Zeit.${\ displaystyle R \,}$${\ displaystyle O (d) \,}$${\ displaystyle O (dr) \,}$${\ displaystyle L \,}$${\ displaystyle O (dr) \,}$
4. Wie oben dargelegt, beträgt die Gesamtzahl der Iterationen höchstens .${\ displaystyle m \,}$

Dies gibt eine Gesamtlaufzeit an , wobei und Konstanten sind. ${\ displaystyle O (mdr) = O (n) \,}$${\ displaystyle d \,}$${\ displaystyle r \,}$

Siehe auch

• Expander-Diagramm
• Paritätsprüfcode mit niedriger Dichte
• Lineare Zeitcodierung und Decodierung von Fehlerkorrekturcodes
• ABNNR- und AEL-Codes

Anmerkungen

Dieser Artikel basiert auf den Kursnotizen von Dr. Venkatesan Guruswami.

Verweise