Expanderkod

Expanderkoder
tvådelad expandergraf
Klassificering
Typ	Linjär blockkod
Blocklängd	$n$
Meddelandets längd	$nm$
Betygsätta	$1-m/n$
Distans	$2(1-\epsilon )\gamma \cdot n$
Alfabetets storlek	$2$
Notation	$[n,nm,2(1-\epsilon )\gamma \cdot n]_{2}$ -kod

I kodningsteorin bildar expanderkoder en klass av felkorrigerande koder som är konstruerade från tvådelade expandergrafer . Tillsammans med Justesen-koder är expanderkoder av särskilt intresse eftersom de har en konstant positiv hastighet , ett konstant positivt relativt avstånd och en konstant alfabetisk storlek . Faktum är att alfabetet bara innehåller två element, så expanderkoder tillhör klassen binära koder . Vidare kan expanderkoder både kodas och avkodas i tid proportionell mot kodens blocklängd.

Expanderkoder

I kodningsteorin är en expanderkod en linjär blockkod för $[n,nm]_{2}\,$ vars paritetskontrollmatris är närliggande matris för en tvådelad expandergraf . Dessa koder har bra relativa avstånd ${\displaystyle 2(1-\varepsilon )\gamma \,} ,$ där $\varepsilon \,$ och $\gamma \,$ är egenskaper för expandergrafen som definieras senare), hastighet $\left(1-{\tfrac {m}{n}}\right)\,$ och avkodbarhet (algoritmer för körtid $O(n)\,$ existerar).

Definition

Låt $B$ vara en $(c,d)$ - biregelbunden graf mellan en uppsättning av $n$ noder $\ {v_{1},\cdots ,v_{n}\}$ , kallade variabler och en uppsättning $cn/d$ -noder ${\ displaystyle \{C_{1},\cdots ,C_{cn/d}\}}$ , kallad constraints .

Låt $b(i,j)$ vara en funktion utformad så att, för varje begränsning ${\displaystyle C_{i}},$ variablerna som gränsar till $C_{i}$ är $v_{b(i,1)},\cdots ,v_{b(i,d)}$ .

Låt ${\mathcal {S}}$ vara en felkorrigerande kod med blocklängden $d$ . Expanderkoden ${\mathcal {C}}(B,{\mathcal {S}})$ är koden för blocklängden $n$ vars kodord är orden $(x_{1},\cdots ,x_{n})$ så att för $1\leq i\leq cn/d$ , $(x_{b(i,1)},\cdots ,x_{b(i,d)})$ är en kodord för ${\mathcal {S}}$ .

Det har visat sig att det finns icke-triviala förlustfria expandergrafer. Dessutom kan vi uttryckligen konstruera dem.

Betygsätta

Hastigheten för $C\,$ är dess dimension dividerat med dess blocklängd. I det här fallet har paritetskontrollmatrisen storleken $m\times n\,$ , och därför har $C\,$ hastigheten minst $(nm)/n=1-m/n\,$ .

Distans

Antag att $\varepsilon <{\tfrac {1}{2}}\,$ . Då är avståndet för a $(n,m,d,\gamma ,1-\varepsilon )\,$ expanderkod $C\,$ minst $2(1-\varepsilon )\gamma n\,$ .

Bevis

Observera att vi kan betrakta varje kodord $c\,$ i $C\,$ som en delmängd av hörn $S\subset L\,$ , genom att säga att vertex $v_{i}\in S\,$ om och endast om det ${\displaystyle i\,}:$ e indexet för kodordet är en 1. Då är $​​{\displaystyle c\,}$ ett kodord om varje vertex $v\in R\,$ ligger intill ett jämnt antal hörn i $S\,$ . (För att vara ett kodord, $cP=0\,$ , där $P\,$ är paritetskontrollmatrisen. Sedan motsvarar varje vertex i $R\,$ till varje kolumn i $P\,$ . Matrismultiplikation över ${\text{GF}}(2)=\{0,1\}\,$ sedan ger det önskade resultatet.) Så, om en vertex $v\in R\,$ ligger intill en enda vertex i $S\,$ , vet vi omedelbart att $c\ ,$ är inte ett kodord. Låt $N(S)\,$ beteckna grannarna i $R\,$ av $S\,$ och $U(S)\ ,$ betecknar de grannar till $S\,$ som är unika, dvs intill en enda vertex av $S\,$ .

Lemma 1

För varje $S\subset L\,$ av storlek $|S|\leq \gamma n\,$ , $d|S|\geq |N(S)|\geq |U(S)|\geq d(1-2\varepsilon )|S|\,$ .

Bevis

Trivialt, $|N(S)|\geq |U(S)|\,$ , eftersom $v\in U(S)\,$ antyder ${\ displaystyle v\in N(S)\,}$ . $|N(S)|\leq d|S|\,$ följer eftersom graden av varje vertex i $S\,$ är $d\,$ . Genom expansionsegenskapen för grafen måste det finnas en uppsättning $d(1-\varepsilon )|S|\,$ kanter som går till distinkta hörn. De återstående $d\varepsilon |S|\,$ kanter gör som mest $d\varepsilon |S|\,$ grannar inte unika, så $U(S)\geq d(1-\varepsilon )|S|-d\varepsilon |S|=d(1-2\varepsilon )|S|\,$ .

Naturlig följd

Varje tillräckligt litet $S\,$ har en unik granne. Detta följer eftersom $\varepsilon <{\tfrac {1}{2}}\,$ .

Lemma 2

Varje delmängd $T\subset L\,$ med $|T|<2(1-\varepsilon )\gamma n\,$ har en unik granne.

Bevis

Lemma 1 bevisar fallet $|T|\leq \gamma n\,$ , så anta att $2(1-\varepsilon )\gamma n>|T|>\gamma n\,$ . Låt $S\subset T\,$ så att $|S|=\gamma n\,$ . Av Lemma 1 vet vi att $|U(S)|\geq d(1-2\varepsilon )|S|\,$ . Då är en vertex $v\in U(S)\,$ i $U(T)\,$ iff $v\notin N(T\setminus S)\,$ , och vi vet att $|T\setminus S|\leq 2(1-\varepsilon )\gamma n-\gamma n=(1- 2\varepsilon )\gamma n\,$ , så vid första delen av Lemma 1 vet vi $|N(T\setminus S)|\leq d(1-2\varepsilon )\gamma n\,$ . Eftersom $\varepsilon <{\tfrac {1}{2}}\,$ , $|U(T)|\geq |U(S)\setminus N(T\setminus S)|\geq |U(S)|-|N(T\setminus S)|>0\,$ , och därför är $U(T)\,$ inte tom.

Naturlig följd

Observera att om en $T\subset L\,$ har minst 1 unik granne, dvs $|U(T)|>0\,$ , då kan motsvarande ord $c\,$ som motsvarar $T\,$ inte vara ett kodord, eftersom det inte multipliceras till vektor med alla nollor av paritetskontrollmatrisen. Med föregående argument, $c\in C\implicerar wt(c)\geq 2(1-\varepsilon )\gamma n\,$ . Eftersom $C\,$ är linjär drar vi slutsatsen att $C\,$ har ett avstånd på minst $2(1-\varepsilon )\gamma n\,$ .

Kodning

Kodningstiden för en expanderkod är övre gränsad av den för en allmän linjär kod - $O(n^{2})\,$ genom matrismultiplikation. Ett resultat på grund av Spielman visar att kodning är möjlig i $O(n)\,$ tid.

Avkodning

Avkodning av expanderkoder är möjlig i $O(n)\,$ tid när $\varepsilon <{\tfrac {1}{4}}\,$ med hjälp av följande algoritm .

Låt $v_{i}\,$ vara spetsen på $L\,$ som motsvarar det $i\,$ :e indexet i kodorden för $C\,$ . Låt $y\in \{0,1\}^{n}\,$ vara ett mottaget ord, och $V(y)=\{v_{i}\mid {\text{}}i^{\text{th}}{\text{ positionen för }}y{\text{ är en }}1\}\,$ . Låt $e(i)\,$ vara $|\{v\in R\mid v_{i}\in N(v){\text{ och }}N(v)\cap V(y){\text{ är jämn}}\}| \,$ och $o(i)\,$ vara $|\{v\in R\mid v_{i}\in N(v){\text{ och }}N(v)\cap V(y){\text{ är udda}}\}| \,$ . Tänk sedan på den giriga algoritmen:

---

Inmatning: mottaget ord $y\,$ .

initiera y' till y medan det finns av i R intill ett udda antal hörn i V(y') om det finns ett i så att o(i) > e(i) vänd posten i i y' annars misslyckas

Utdata: misslyckas, eller modifierat kodord $y'\,$ .

---

Bevis

Vi visar först algoritmens korrekthet och undersöker sedan dess körtid.

Rätthet

Vi måste visa att algoritmen avslutas med rätt kodord när det mottagna kodordet ligger inom halva kodens avstånd från det ursprungliga kodordet. Låt uppsättningen av korrupta variabler vara $S\,$ , $s=|S|\,$ , och uppsättningen av otillfredsställda (intill ett udda antal hörn) hörn i $R\,$ vara $c\,$ . Följande lemma kommer att visa sig användbart.

Lemma 3

Om ${\displaystyle 0<s<\gamma n\,} ,$ så finns det en $v_{i}\,$ med $o (i)>e(i)\,$ .

Bevis

Genom Lemma 1 vet vi att $U(S)\geq d(1-2\varepsilon )s\,$ . Så en genomsnittlig vertex har minst $d(1-2\varepsilon )>d/2\,$ unika grannar (återkalla unika grannar är inte nöjda och bidrar därmed till $o(i)\,$ ), eftersom ${\displaystyle \varepsilon <{\tfrac {1}{4}}\,} ,$ och det finns alltså en vertex $v_{i}\,$ med $o(i)>e(i)\,$ .

Så, om vi ännu inte har nått ett kodord, kommer det alltid att finnas någon vertex att vända. Därefter visar vi att antalet fel aldrig kan öka utöver $\gamma n\,$ .

Lemma 4

Om vi ​​börjar med $s<\gamma (1-2\varepsilon )n\,$ så når vi aldrig $s=\gamma n\ ,$ när som helst i algoritmen.

Bevis

När vi vänder en vertex $v_{i}\,$ , $o(i)\,$ och $e(i)\,$ växlas, och eftersom vi hade $o(i)>e(i)\,$ , betyder det att antalet otillfredsställda hörn till höger minskar med minst en efter varje vändning. Eftersom ${\displaystyle s<\gamma (1-2\varepsilon )n\,} ,$ är det initiala antalet otillfredsställda hörn som mest ${\ displaystyle d\gamma (1-2\varepsilon )n\,}$ , av grafens $d\,$ -regelbundenhet. Om vi ​​nådde en sträng med $\gamma n\,$ fel, då vid Lemma 1, skulle det finnas minst $d\gamma (1-2\varepsilon) )n\,$ unika grannar, vilket betyder att det skulle finnas åtminstone $d\gamma (1-2\varepsilon )n\,$ otillfredsställda hörn, en motsägelse.

Lemma 3 och 4 visar oss att om vi börjar med $s<\gamma (1-2\varepsilon )n\,$ (halva avståndet av $C\ ,$ ), så hittar vi alltid en vertex $v_{i}\,$ att vända. Varje vändning minskar antalet otillfredsställda hörn i $R\,$ med minst 1, och följaktligen slutar algoritmen i högst $m\,$ steg, och den slutar vid något kodord, av Lemma 3 (Om det inte var ett kodord, skulle det finnas någon vertex att vända). Lemma 4 visar oss att vi aldrig kan vara längre än $\gamma n\,$ från det korrekta kodordet. Eftersom koden har avstånd ${\displaystyle 2(1-\varepsilon )\gamma n>\gamma n\,} ($ eftersom $\varepsilon <{\ tfrac {1}{2}}\,$ ), måste kodordet det avslutas på vara rätt kodord, eftersom antalet bitflip är mindre än halva avståndet (så vi kunde inte ha rest tillräckligt långt för att nå någon annan kodord).

Komplexitet

Vi visar nu att algoritmen kan uppnå linjär tidsavkodning. Låt ${\tfrac {n}{m}}\,$ vara konstant och $r\,$ vara den maximala graden av någon vertex i $R\,$ . Observera att $r\,$ också är konstant för kända konstruktioner.

1. Förbearbetning: Det tar $O(mr)\,$ tid att beräkna om varje vertex i $R\,$ har ett udda eller jämnt antal grannar.
2. Förbearbetning 2: Vi tar $O(dn)=O(dmr)\,$ tid för att beräkna en lista med hörn $v_{i} \,$ i $L\,$ som har $o(i)>e(i)\,$ .
3. Varje iteration: Vi tar helt enkelt bort det första listelementet. För att uppdatera listan med udda/jämna hörn i $R\,$ behöver vi bara uppdatera $O(d)\,$ poster, infoga/ta bort vid behov. Vi uppdaterar sedan ${\displaystyle O(dr)\,}-$ poster i listan över hörn i $L\,$ med mer udda än jämna grannar, infogar/tar bort vid behov. Således tar varje iteration $O(dr)\,$ tid.
4. Som argumenterats ovan är det totala antalet iterationer högst $m\,$ .

Detta ger en total körtid på $O(mdr)=O(n)\,$ tid, där $d\,$ och $r\ ,$ är konstanter.

Se även

• Expanderdiagram
• Kod för paritetskontroll med låg densitet
• Linjär tidskodning och avkodning av felkorrigerande koder
• ABNNR- och AEL-koder

Anteckningar

Den här artikeln är baserad på Dr Venkatesan Guruswamis kursanteckningar.