Expander kód - Expander code - Wikipedia

Expander kódy
	bipartitní expandér graf
Klasifikace
Typ	Lineární kód bloku
Délka bloku
Délka zprávy
Hodnotit
Vzdálenost
Velikost abecedy
Zápis	-kód

v teorie kódování, expandér kódy tvoří třídu kódy opravující chyby které jsou konstruovány z bipartitní expandérové grafy.Spolu s Justesenovy kódy, rozšiřující kódy jsou obzvláště zajímavé, protože mají konstantní pozitivní hodnotu hodnotit, konstantní kladný příbuzný vzdálenost a konstanta velikost abecedy Abeceda ve skutečnosti obsahuje pouze dva prvky, takže rozšiřující kódy patří do třídy binární kódy Dále mohou být kódy expandéru kódovány i dekódovány v čase úměrném délce bloku kódu.

Expander kódy

v teorie kódování, rozšiřovací kód je ${ displaystyle [n, n-m] _ {2} ,}$ lineární blokový kód jehož matice kontroly parity je maticí sousedství bipartity expandér graf. Tyto kódy mají dobrý relativní vzdálenost ${ displaystyle 2 (1- varepsilon) gama ,}$ , kde ${ displaystyle varepsilon ,}$ a ${ displaystyle gamma ,}$ jsou vlastnosti grafu expandéru, jak jsou definovány později), hodnotit ${ displaystyle left (1 - { tfrac {m} {n}} right) ,}$ a dekódovatelnost (algoritmy doby běhu ${ displaystyle O (n) ,}$ existovat).

Definice

Zvažte a bipartitní graf ${ displaystyle G (L, R, E) ,}$ , kde ${ displaystyle L ,}$ a ${ displaystyle R ,}$ jsou vrcholové množiny a ${ displaystyle E ,}$ je sada hran spojujících vrcholy v ${ displaystyle L ,}$ na vrcholy ${ displaystyle R ,}$ . Předpokládejme každý vrchol ${ displaystyle L ,}$ má stupeň ${ displaystyle d ,}$ (graf je ${ displaystyle d ,}$ -vlevo, odjet-pravidelný ), ${ displaystyle | L | = n ,}$ , a ${ displaystyle | R | = m ,}$ , ${ displaystyle m$ . Pak ${ displaystyle G ,}$ je ${ displaystyle (n, m, d, gama, alfa) ,}$ expandér graf, pokud je každá dostatečně malá podmnožina ${ displaystyle S podmnožina L ,}$ , ${ displaystyle | S | leq gamma n ,}$ má vlastnost, která ${ displaystyle S ,}$ má alespoň ${ displaystyle d alpha | S | ,}$ zřetelní sousedé v ${ displaystyle R ,}$ . Toto platí triviálně pro ${ displaystyle gamma leq { tfrac {1} {n}} ,}$ . Když ${ displaystyle { tfrac {1} {n}} < gamma leq 1 ,}$ a ${ displaystyle alpha = 1- varepsilon ,}$ pro konstantu ${ displaystyle varepsilon ,}$ , říkáme to ${ displaystyle G ,}$ je bezztrátový expandér.

Od té doby ${ displaystyle G ,}$ je bipartitní graf, můžeme uvažovat o jeho ${ displaystyle n krát m ,}$ matice sousedství. Pak lineární kód ${ displaystyle C ,}$ generovaný sledováním transpozice této matice jako matice kontroly parity je kód expandéru.

Ukázalo se, že existují netriviální bezztrátové expandérové grafy. Navíc je můžeme výslovně postavit.^[1]

Hodnotit

Míra ${ displaystyle C ,}$ je jeho rozměr dělený délkou bloku. V tomto případě má matice kontroly parity velikost ${ displaystyle m krát n ,}$ , a tedy ${ displaystyle C ,}$ má alespoň rozměr ${ displaystyle (n-m) / n = 1 - { tfrac {m} {n}} ,}$ .

Vzdálenost

Předpokládat ${ displaystyle varepsilon <{ tfrac {1} {2}} ,}$ . Pak vzdálenost a ${ displaystyle (n, m, d, gama, 1- varepsilon) ,}$ expandér kód ${ displaystyle C ,}$ je alespoň ${ displaystyle 2 (1- varepsilon) gama n ,}$ .

Důkaz

Všimněte si, že můžeme vzít v úvahu každé kódové slovo ${ displaystyle c ,}$ v ${ displaystyle C ,}$ jako podmnožina vrcholů ${ displaystyle S podmnožina L ,}$ , tím, že říká, že vrchol ${ displaystyle v_ {i} v S ,}$ jen a jen pokud ${ displaystyle i ,}$ th index of the codeword is a 1. Then ${ displaystyle c ,}$ je kódové slovo, pokud každý vrchol ${ displaystyle v v R ,}$ sousedí se sudým počtem vrcholů v ${ displaystyle S ,}$ . (Aby to bylo kódové slovo, ${ displaystyle cP = 0 ,}$ , kde ${ displaystyle P ,}$ je matice kontroly parity. Pak každý vrchol dovnitř ${ displaystyle R ,}$ odpovídá každému sloupci ${ displaystyle P ,}$ . Násobení matice skončilo ${ displaystyle { text {GF}} (2) = {0,1 } ,}$ pak dává požadovaný výsledek.) Takže pokud vrchol ${ displaystyle v v R ,}$ sousedí s jediným vrcholem v ${ displaystyle S ,}$ , víme to okamžitě ${ displaystyle c ,}$ není kódové slovo. Nechat ${ displaystyle N (S) ,}$ označit sousedy v ${ displaystyle R ,}$ z ${ displaystyle S ,}$ , a ${ displaystyle U (S) ,}$ označit ty sousedy z ${ displaystyle S ,}$ které jsou jedinečné, tj. sousedí s jediným vrcholem ${ displaystyle S ,}$ .

Lemma 1

Pro každého ${ displaystyle S podmnožina L ,}$ velikosti ${ displaystyle | S | leq gamma n ,}$ , ${ displaystyle d | S | geq | N (S) | geq | U (S) | geq d (1-2 varepsilon) | S | ,}$ .

Důkaz

Triviálně, ${ displaystyle | N (S) | geq | U (S) | ,}$ , od té doby ${ displaystyle v v U (S) ,}$ naznačuje ${ displaystyle v v N (S) ,}$ . ${ displaystyle | N (S) | leq d | S | ,}$ následuje od stupně každého vrcholu v ${ displaystyle S ,}$ je ${ displaystyle d ,}$ . Podle vlastnosti expanze grafu musí existovat sada ${ displaystyle d (1- varepsilon) | S | ,}$ hrany, které jdou na odlišné vrcholy. Zbývající ${ displaystyle d varepsilon | S | ,}$ maximálně hrany ${ displaystyle d varepsilon | S | ,}$ sousedé nejsou ojedinělí, takže ${ displaystyle U (S) geq d (1- varepsilon) | S | -d varepsilon | S | = d (1-2 varepsilon) | S | ,}$ .

Důsledek

Každý dostatečně malý ${ displaystyle S ,}$ má jedinečného souseda. Toto následuje od té doby ${ displaystyle varepsilon <{ tfrac {1} {2}} ,}$ .

Lemma 2

Každá podmnožina ${ displaystyle T podmnožina L ,}$ s ${ displaystyle | T | <2 (1- varepsilon) gamma n ,}$ má jedinečného souseda.

Důkaz

Lemma 1 dokazuje případ ${ displaystyle | T | leq gamma n ,}$ , tak předpokládejme ${ displaystyle 2 (1- varepsilon) gamma n> | T |> gamma n ,}$ . Nechat ${ displaystyle S podmnožina T ,}$ takhle ${ displaystyle | S | = gamma n ,}$ . Od Lemmy 1 to víme ${ displaystyle | U (S) | geq d (1-2 varepsilon) | S | ,}$ . Pak vrchol ${ displaystyle v v U (S) ,}$ je v ${ displaystyle U (T) ,}$ iff ${ displaystyle v notin N (T setminus S) ,}$ a my to víme ${ displaystyle | T setminus S | leq 2 (1- varepsilon) gamma n- gamma n = (1-2 varepsilon) gamma n ,}$ , takže o první části Lemmy 1 víme ${ displaystyle | N (T setminus S) | leq d (1-2 varepsilon) gama n ,}$ . Od té doby ${ displaystyle varepsilon <{ tfrac {1} {2}} ,}$ , ${ displaystyle | U (T) | geq | U (S) setminus N (T setminus S) | geq | U (S) | - | N (T setminus S) |> 0 ,}$ , a tedy ${ displaystyle U (T) ,}$ není prázdný.

Důsledek

Všimněte si, že pokud a ${ displaystyle T podmnožina L ,}$ má alespoň 1 jedinečného souseda, tj. ${ displaystyle | U (T) |> 0 ,}$ , pak odpovídající slovo ${ displaystyle c ,}$ souhlasí s ${ displaystyle T ,}$ nemůže být kódovým slovem, protože se nebude množit na všechny nulové vektory maticí kontroly parity. Podle předchozího argumentu ${ displaystyle c v C znamená wt (c) geq 2 (1- varepsilon) gama n ,}$ . Od té doby ${ displaystyle C ,}$ je lineární, došli jsme k závěru, že ${ displaystyle C ,}$ má vzdálenost alespoň ${ displaystyle 2 (1- varepsilon) gama n ,}$ .

Kódování

Čas kódování kódu expandéru je horně omezen časem obecného lineárního kódu - ${ displaystyle O (n ^ {2}) ,}$ násobením matic. Výsledek způsobený Spielmanem ukazuje, že kódování je možné v ${ displaystyle O (n) ,}$ čas.^[2]

Dekódování

Dekódování kódů expandéru je možné v ${ displaystyle O (n) ,}$ čas kdy ${ displaystyle varepsilon <{ tfrac {1} {4}} ,}$ pomocí následujícího algoritmu.

Nechat ${ displaystyle v_ {i} ,}$ být vrcholem ${ displaystyle L ,}$ který odpovídá ${ displaystyle i ,}$ th index v kódových slovech ${ displaystyle C ,}$ . Nechat ${ displaystyle y in {0,1 } ^ {n} ,}$ být přijatým slovem a ${ displaystyle V (y) = {v_ {i} mid { text {the}} i ^ { text {th}} { text {pozice}} y { text {je a}} 1 } ,}$ . Nechat ${ displaystyle e (i) ,}$ být ${ displaystyle | {v v R mid v_ {i} v N (v) { text {a}} N (v) cap V (y) { text {je sudý}} } | ,}$ , a ${ displaystyle o (i) ,}$ být ${ displaystyle | {v v R mid v_ {i} v N (v) { text {a}} N (v) cap V (y) { text {je zvláštní}} } | ,}$ . Pak zvažte chamtivý algoritmus:

Vstup: přijal slovo ${ displaystyle y ,}$ .

inicializujte y 'na y, zatímco v R sousedí s lichým počtem vrcholů v V (y'), pokud existuje i takové, že o (i)> e (i) převrátí vstup i v y 'else fail

Výstup: selhání nebo upravené kódové slovo ${ displaystyle y ',}$ .

Důkaz

Nejprve ukážeme správnost algoritmu a poté prozkoumáme jeho dobu běhu.

Správnost

Musíme ukázat, že algoritmus končí správným kódovým slovem, když je přijaté kódové slovo ve vzdálenosti poloviny kódu od původního kódového slova. Nechť je sada poškozených proměnných ${ displaystyle S ,}$ , ${ displaystyle s = | S | ,}$ a množina neuspokojených vrcholů (sousedících s lichým počtem vrcholů) ${ displaystyle R ,}$ být ${ displaystyle c ,}$ . Následující lemma se osvědčí.

Lemma 3

Li ${ displaystyle 0$ ~~, pak existuje ${ displaystyle v_ {i} ,}$ s ${ displaystyle o (i)> e (i) ,}$ .~~

Důkaz

Od Lemmy 1 to víme ${ displaystyle U (S) geq d (1-2 varepsilon) s ,}$ . Průměrný vrchol tedy má alespoň ${ displaystyle d (1-2 varepsilon)> d / 2 ,}$ jedineční sousedé (vzpomeňte si, že jedineční sousedé nejsou spokojeni, a proto přispívají k ${ displaystyle o (i) ,}$ ), od té doby ${ displaystyle varepsilon <{ tfrac {1} {4}} ,}$ , a tedy existuje vrchol ${ displaystyle v_ {i} ,}$ s ${ displaystyle o (i)> e (i) ,}$ .

Takže pokud jsme ještě nedosáhli kódového slova, pak bude vždy existovat nějaký vrchol, který se dá převrátit. Dále ukážeme, že počet chyb se už nikdy nemůže zvýšit ${ displaystyle gamma n ,}$ .

Lemma 4

~~Pokud začneme s ${ displaystyle s < gamma (1-2 varepsilon) n ,}$ , pak se nikdy nedostaneme ${ displaystyle s = gamma n ,}$ kdykoli v algoritmu.~~

Důkaz

Když překlopíme vrchol ${ displaystyle v_ {i} ,}$ , ${ displaystyle o (i) ,}$ a ${ displaystyle e (i) ,}$ jsou zaměňovány, a protože jsme měli ${ displaystyle o (i)> e (i) ,}$ , to znamená, že počet neuspokojených vrcholů vpravo klesá po každém otočení alespoň o jeden. Od té doby ${ displaystyle s < gamma (1-2 varepsilon) n ,}$ , počáteční počet neuspokojených vrcholů je maximálně ${ displaystyle d gamma (1-2 varepsilon) n ,}$ , podle grafu ${ displaystyle d ,}$ -pravidelnost. Pokud bychom dosáhli řetězce s ${ displaystyle gamma n ,}$ chyby, pak by u Lemmy 1 bylo alespoň ${ displaystyle d gamma (1-2 varepsilon) n ,}$ jedineční sousedé, což znamená, že by existovalo alespoň ${ displaystyle d gamma (1-2 varepsilon) n ,}$ neuspokojené vrcholy, rozpor.

Lemata 3 a 4 nám to ukazují, pokud začneme ${ displaystyle s < gamma (1-2 varepsilon) n ,}$ (poloviční vzdálenost ${ displaystyle C ,}$ ), pak vždy najdeme vrchol ${ displaystyle v_ {i} ,}$ převrátit. Každé převrácení snižuje počet neuspokojených vrcholů ${ displaystyle R ,}$ alespoň o 1, a proto algoritmus končí maximálně ${ displaystyle m ,}$ kroky a končí u nějakého kódového slova, lemmou 3. (Pokud by to nebylo u kódového slova, bylo by možné překlopit nějaký vrchol). Lemma 4 nám ukazuje, že nikdy nemůžeme být dále než ${ displaystyle gamma n ,}$ od správného kódového slova. Protože kód má vzdálenost ${ displaystyle 2 (1- varepsilon) gamma n> gamma n ,}$ (od té doby ${ displaystyle varepsilon <{ tfrac {1} {2}} ,}$ ), kódové slovo, na kterém končí, musí být správné kódové slovo, protože počet bitových převrácení je menší než poloviční vzdálenost (takže jsme nemohli cestovat dostatečně daleko, abychom dosáhli jakéhokoli jiného kódového slova).

Složitost

Nyní ukážeme, že algoritmus může dosáhnout lineárního dekódování času. Nechat ${ displaystyle { tfrac {n} {m}} ,}$ být konstantní a ${ displaystyle r ,}$ být maximální stupeň jakéhokoli vrcholu v ${ displaystyle R ,}$ . Všimněte si, že ${ displaystyle r ,}$ je také konstantní pro známé konstrukce.

~~Předběžné zpracování: Trvá to ${ displaystyle O (mr) ,}$ čas na výpočet, zda každý vrchol v ${ displaystyle R ,}$ má lichý nebo sudý počet sousedů.~~
Předběžné zpracování 2: Bereme ${ displaystyle O (dn) = O (dmr) ,}$ čas na výpočet seznamu vrcholů ${ displaystyle v_ {i} ,}$ v ${ displaystyle L ,}$ které mají ${ displaystyle o (i)> e (i) ,}$ .
Každá iterace: Jednoduše odstraníme první prvek seznamu. Aktualizace seznamu lichých / sudých vrcholů v ${ displaystyle R ,}$ , potřebujeme pouze aktualizaci ${ displaystyle O (d) ,}$ podle potřeby vkládání / odebírání. Poté aktualizujeme ${ displaystyle O (dr) ,}$ položky v seznamu vrcholů v ${ displaystyle L ,}$ s více lichými než sudými sousedy, vkládání / vyjímání podle potřeby. Každá iterace tedy trvá ${ displaystyle O (dr) ,}$ čas.
~~Jak je uvedeno výše, celkový počet iterací je maximálně ${ displaystyle m ,}$ .~~

~~To dává celkovou dobu běhu ${ displaystyle O (mdr) = O (n) ,}$ čas, kde ${ displaystyle d ,}$ a ${ displaystyle r ,}$ jsou konstanty.~~

Viz také

~~Expander graf~~
~~Kód kontroly parity s nízkou hustotou~~
~~Lineární časové kódování a dekódování kódů opravujících chyby~~
~~Kódy ABNNR a AEL~~

Poznámky

~~Tento článek je založen na poznámkách k kurzu Dr. Venkatesana Guruswamiho.^[3]~~

Reference

^ Capalbo, M .; Reingold, O .; Vadhan, S .; Wigderson, A. (2002). „Náhodné vodiče a bezztrátové expandéry konstantního stupně“. STOC '02 Sborník z třicátého čtvrtého ročníku ACM symposia o teorii práce s počítačem. ACM. str. 659–668. doi:10.1145/509907.510003. ISBN 978-1-58113-495-7.
^ Spielman, D. (1996). Msgstr "Kódy opravitelné v lineárním čase a dekódovatelné chyby". Transakce IEEE na teorii informací. 42 (6): 1723–31. CiteSeerX 10.1.1.47.2736. doi:10.1109/18.556668.
^ Guruswami, V. (15. listopadu 2006). „Lecture 13: Expander Codes“ (PDF). CSE 533: Oprava chyb. University of Washington.
Guruswami, V. (březen 2010). „Poznámky 8: Kódy expandérů a jejich dekódování“ (PDF). Úvod do teorie kódování. Univerzita Carnegie Mellon.
Guruswami, V. (září 2004). „Sloupec pro hosty: kódy opravující chyby a rozšiřující grafy“. Novinky ACM SIGACT. 35 (3): 25–41. doi:10.1145/1027914.1027924.

[lossless-1] Capalbo, M .; Reingold, O .; Vadhan, S .; Wigderson, A. (2002). „Náhodné vodiče a bezztrátové expandéry konstantního stupně“. STOC '02 Sborník z třicátého čtvrtého ročníku ACM symposia o teorii práce s počítačem. ACM. str. 659–668. doi:10.1145/509907.510003. ISBN 978-1-58113-495-7.

[spielman-2] Spielman, D. (1996). Msgstr "Kódy opravitelné v lineárním čase a dekódovatelné chyby". Transakce IEEE na teorii informací. 42 (6): 1723–31. CiteSeerX 10.1.1.47.2736. doi:10.1109/18.556668.

[3] Guruswami, V. (15. listopadu 2006). „Lecture 13: Expander Codes“ (PDF). CSE 533: Oprava chyb. University of Washington.
Guruswami, V. (březen 2010). „Poznámky 8: Kódy expandérů a jejich dekódování“ (PDF). Úvod do teorie kódování. Univerzita Carnegie Mellon.
Guruswami, V. (září 2004). „Sloupec pro hosty: kódy opravující chyby a rozšiřující grafy“. Novinky ACM SIGACT. 35 (3): 25–41. doi:10.1145/1027914.1027924.

[1]

[2]

[3]