Expander code - Expander code

Expander codes
bipartiete expander-grafiek
Classificatie
Type	Lineaire blokcode
Blok lengte	${\ displaystyle n}$
Bericht lengte	${\ displaystyle nm}$
Beoordeel	${\ displaystyle 1-m / n}$
Afstand	${\ displaystyle 2 (1- \ epsilon) \ gamma \ cdot n}$
Alfabet grootte	${\ displaystyle 2}$
Notatie	${\ displaystyle [n, nm, 2 (1- \ epsilon) \ gamma \ cdot n] _ {2}}$ -code
v t e

In coderingstheorie , expander codes vormen een klasse van foutcorrigerende codes die zijn opgebouwd uit bipartiete expander grafieken . Samen met Justesen-codes zijn uitbreidingscodes van bijzonder belang omdat ze een constante positieve snelheid , een constante positieve relatieve afstand en een constante alfabetgrootte hebben . In feite bevat het alfabet slechts twee elementen, dus expandercodes behoren tot de klasse van binaire codes . Verder kunnen uitbreidingscodes zowel gecodeerd als gedecodeerd worden in de tijd evenredig met de bloklengte van de code.

Expander codes

In de coderingstheorie is een expandercode een lineaire blokcode waarvan de pariteitscontrolematrix de aangrenzende matrix is ​​van een bipartiete expander-grafiek . Deze codes hebben een goede relatieve afstand , waar en zijn eigenschappen van de uitbreidingsgrafiek zoals later gedefinieerd), snelheid en decodeerbaarheid (algoritmen van looptijd bestaan). ${\ displaystyle [n, nm] _ {2} \,}$ ${\ displaystyle 2 (1- \ varepsilon) \ gamma \,}$${\ displaystyle \ varepsilon \,}$${\ displaystyle \ gamma \,}$ ${\ displaystyle \ left (1 - {\ tfrac {m} {n}} \ right) \,}$${\ displaystyle O (n) \,}$

Definitie

Beschouw een bipartiete grafiek , waar en zijn de vertex sets en is de set randen die hoekpunten verbinden met hoekpunten van . Stel dat elk hoekpunt in heeft graad (de grafiek is -left- regelmatig ), en , . Dan is een expander grafiek als elk klein genoeg deelverzameling , heeft de eigenschap dat ten minste heeft verschillende buren in . Merk op dat dit triviaal geldt voor . Wanneer en voor een constante , zeggen we dat dit een verliesloze expander is. ${\ 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 \,}$

Omdat het een bipartiete grafiek is, kunnen we de aangrenzende matrix beschouwen. De lineaire code die wordt gegenereerd door de transpositie van deze matrix te bekijken als een matrix voor pariteitscontrole, is een uitbreidingscode. ${\ displaystyle G \,}$${\ displaystyle n \ maal m \,}$${\ displaystyle C \,}$

Het is aangetoond dat er niet-triviale verliesloze expander-grafieken bestaan. Bovendien kunnen we ze expliciet construeren.

Beoordeel

De snelheid van is de afmeting gedeeld door de bloklengte. In dit geval heeft de pariteitscontrolematrix een afmeting , en dus tenminste een afmeting . ${\ displaystyle C \,}$${\ displaystyle m \ maal n \,}$${\ displaystyle C \,}$${\ displaystyle (nm) / n = 1 - {\ tfrac {m} {n}} \,}$

Afstand

Stel dat . Dan is de afstand van een uitbreidingscode minimaal . ${\ displaystyle \ varepsilon <{\ tfrac {1} {2}} \,}$${\ displaystyle (n, m, d, \ gamma, 1- \ varepsilon) \,}$${\ displaystyle C \,}$${\ displaystyle 2 (1- \ varepsilon) \ gamma n \,}$

Bewijs

Merk op dat we elk codewoord in kunnen beschouwen als een subset van hoekpunten , door dat hoekpunt te zeggen als en slechts als de e index van het codewoord een 1 is . Dan is een codewoord als elk hoekpunt grenst aan een even aantal hoekpunten in . (Om een ​​codewoord te zijn , waar is de pariteitscontrolematrix. Dan komt elk hoekpunt binnen overeen met elke kolom van . Matrixvermenigvuldiging over geeft dan het gewenste resultaat.) Dus als een hoekpunt grenst aan een enkel hoekpunt in , we weten meteen dat dit geen codewoord is. Laten we de buren in van aanduiden , en die buren aanduiden waarvan uniek is, dwz grenzend aan een enkel hoekpunt van . ${\ 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

Voor elke grootte , . ${\ displaystyle S \ subset L \,}$${\ displaystyle | S | \ leq \ gamma n \,}$${\ Displaystyle d | S | \ geq | N (S) | \ geq | U (S) | \ geq d (1-2 \ varepsilon) | S | \,}$

Bewijs

Eigenlijk, want impliceert . volgt aangezien de graad van elk hoekpunt in is . Door de expansie-eigenschap van de graaf moet er een set randen zijn die naar verschillende hoekpunten gaan. De overige randen maken bij de meeste buren niet uniek dus . ${\ displaystyle | N (S) | \ geq | U (S) | \,}$${\ displaystyle v \ in U (S) \,}$${\ displaystyle v \ in N (S) \,}$${\ displaystyle | N (S) | \ eq 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 | \,}$

Gevolg

Ieder voldoende klein heeft een unieke buur. Dit volgt sinds . ${\ displaystyle S \,}$${\ displaystyle \ varepsilon <{\ tfrac {1} {2}} \,}$

Lemma 2

Elke subgroep met een unieke buurman. ${\ displaystyle T \ subset L \,}$${\ Displaystyle | T | <2 (1- \ varepsilon) \ gamma n \,}$

Bewijs

Lemma 1 bewijst het geval , dus veronderstel . Laat zo dat . Bij Lemma 1 weten we dat . Dan is er een hoekpunt in iff , en dat weten we , dus door het eerste deel van Lemma 1 weten we dat . Omdat , en dus niet leeg is. ${\ 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 | \ eq 2 (1- \ varepsilon) \ gamma n- \ gamma n = (1-2 \ varepsilon) \ gamma n \,}$${\ Displaystyle | N (T \ setminus S) | \ eq 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) \,}$

Gevolg

Merk op dat als a ten minste 1 unieke buur heeft, dat wil zeggen dat het corresponderende woord dat overeenkomt met geen codewoord kan zijn, aangezien het zich niet vermenigvuldigt met de vector met alle nullen door de pariteitscontrolematrix. Door de vorige argument . Omdat het lineair is, concluderen we dat er tenminste afstand is . ${\ displaystyle T \ subset L \,}$${\ displaystyle | U (T) |> 0 \,}$${\ displaystyle c \,}$${\ displaystyle T \,}$${\ Displaystyle c \ in C \ impliceert wt (c) \ geq 2 (1- \ varepsilon) \ gamma n \,}$${\ displaystyle C \,}$${\ displaystyle C \,}$${\ displaystyle 2 (1- \ varepsilon) \ gamma n \,}$

Codering

De coderingstijd voor een uitbreidingscode wordt bovengrens door die van een algemene lineaire code - door matrixvermenigvuldiging. Een resultaat van Spielman laat zien dat codering in de tijd mogelijk is . ${\ displaystyle O (n ^ {2}) \,}$${\ displaystyle O (n) \,}$

Decodering

Decodering van uitbreidingscodes is tijdig mogelijk bij gebruik van het volgende algoritme. ${\ displaystyle O (n) \,}$${\ displaystyle \ varepsilon <{\ tfrac {1} {4}} \,}$

Laat het hoekpunt daarvan zijn dat overeenkomt met de th index in de codewoorden van . Laat een ontvangen woord zijn, en . Laat zijn en zijn . Overweeg dan het hebzuchtige algoritme: ${\ 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 {positie van}} y {\ text {is a}} 1 \} \,}$${\ displaystyle e (i) \,}$${\ displaystyle | \ {v \ in R \ mid v_ {i} \ in N (v) {\ text {en}} N (v) \ cap V (y) {\ text {is even}} \} | \,}$${\ displaystyle o (i) \,}$${\ displaystyle | \ {v \ in R \ mid v_ {i} \ in N (v) {\ text {en}} N (v) \ cap V (y) {\ text {is oneven}} \} | \,}$

---

Invoer: ontvangen woord . ${\ 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

Uitvoer: mislukt of gewijzigd codewoord . ${\ displaystyle y '\,}$

---

Bewijs

We laten eerst de juistheid van het algoritme zien en onderzoeken vervolgens de looptijd.

Juistheid

We moeten aantonen dat het algoritme eindigt met het juiste codewoord wanneer het ontvangen codewoord zich binnen de halve codeafstand van het oorspronkelijke codewoord bevindt. Laat de set van corrupte variabelen , en het stel ontevreden (aangrenzend aan een oneven aantal hoekpunten) hoekpunten in be . Het volgende lemma zal nuttig zijn. ${\ displaystyle S \,}$${\ displaystyle s = | S | \,}$${\ displaystyle R \,}$${\ displaystyle c \,}$

Lemma 3

Als , dan is er een met . ${\ displaystyle 0 <s <\ gamma n \,}$${\ displaystyle v_ {i} \,}$${\ displaystyle o (i)> e (i) \,}$

Bewijs

Bij Lemma 1 weten we dat . Dus een gemiddeld hoekpunt heeft op zijn minst unieke buren (herinner me unieke buren zijn ontevreden en dragen dus bij ), aangezien , en dus is er een hoekpunt met . ${\ 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) \,}$

Dus als we nog geen codewoord hebben bereikt, zal er altijd een hoekpunt zijn om om te draaien. Vervolgens laten we zien dat het aantal fouten nooit verder kan stijgen . ${\ displaystyle \ gamma n \,}$

Lemma 4

Als we met beginnen , bereiken we nooit een punt in het algoritme. ${\ Displaystyle s <\ gamma (1-2 \ varepsilon) n \,}$${\ displaystyle s = \ gamma n \,}$

Bewijs

Wanneer we een hoekpunt omdraaien , en worden verwisseld, en sinds we dat hadden gedaan , betekent dit dat het aantal ontevreden hoekpunten aan de rechterkant na elke omslag met ten minste één afneemt. Aangezien het aanvankelijke aantal ontevreden hoekpunten hoogstens gelijk is aan de regelmaat van de grafiek . Als we een string met fouten zouden bereiken, dan zouden er bij Lemma 1 op zijn minst unieke buren zijn, wat betekent dat er op zijn minst ontevreden hoekpunten zouden zijn , een tegenspraak. ${\ 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 \,}$

Lemma's 3 en 4 laten ons zien dat als we beginnen met (de helft van de afstand van ), we altijd een hoekpunt zullen vinden om om te draaien. Elke omkering vermindert het aantal ontevreden hoekpunten met ten minste 1, en daarom eindigt het algoritme in de meeste stappen en eindigt het bij een codewoord, bij Lemma 3. (Als het niet bij een codewoord was, zou er een hoekpunt zijn om om te draaien ). Lemma 4 laat ons zien dat we nooit verder kunnen zijn dan van het juiste codewoord. Omdat de code afstand heeft (sinds ), moet het codewoord waarop het eindigt het juiste codewoord zijn, aangezien het aantal bitflips minder is dan de helft van de afstand (dus we hadden niet ver genoeg kunnen reizen om een ​​ander codewoord te bereiken). ${\ 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}} \,}$

Complexiteit

We laten nu zien dat het algoritme lineaire tijddecodering kan bereiken. Laat constant zijn, en de maximale graad van een hoekpunt in . Merk op dat dit ook constant is voor bekende constructies. ${\ displaystyle {\ tfrac {n} {m}} \,}$${\ displaystyle r \,}$${\ displaystyle R \,}$${\ displaystyle r \,}$

1. Voorverwerking: het kost tijd om te berekenen of elk hoekpunt een oneven of even aantal buren heeft. ${\ displaystyle O (mr) \,}$${\ displaystyle R \,}$
2. Pre-processing 2: We nemen de tijd om een lijst van de hoekpunten te berekenen in welke hebben . ${\ displaystyle O (dn) = O (dmr) \,}$${\ displaystyle v_ {i} \,}$${\ displaystyle L \,}$${\ displaystyle o (i)> e (i) \,}$
3. Elke herhaling: we verwijderen eenvoudig het eerste lijstelement. Om de lijst met oneven / even hoekpunten bij te werken , hoeven we alleen de ingangen bij te werken, en indien nodig invoegen / verwijderen. Vervolgens werken we vermeldingen in de lijst met hoekpunten bij met meer oneven dan even buren, waarbij we waar nodig invoegen / verwijderen. Elke iteratie kost dus tijd. ${\ displaystyle R \,}$${\ displaystyle O (d) \,}$${\ displaystyle O (dr) \,}$${\ displaystyle L \,}$${\ displaystyle O (dr) \,}$
4. Zoals hierboven betoogd, is het totale aantal iteraties maximaal . ${\ displaystyle m \,}$

Dit geeft een totale looptijd van waar en zijn constanten. ${\ displaystyle O (mdr) = O (n) \,}$${\ displaystyle d \,}$${\ displaystyle r \,}$

Zie ook

• Expander grafiek
• Pariteitscontrolecode met lage dichtheid
• Lineaire tijdcodering en decodering van foutcorrectiecodes
• ABNNR- en AEL-codes

Opmerkingen

Dit artikel is gebaseerd op de cursusnotities van Dr. Venkatesan Guruswami.

Referenties