Algoritmus dekódování Zemors - Zemors decoding algorithm - Wikipedia

v teorie kódování, Zemorův algoritmus, navržený a vyvinutý Gillesem Zemorem,^[1] je rekurzivní přístup ke konstrukci kódu s nízkou složitostí. Jedná se o vylepšení oproti algoritmu Sipser a Spielman.

Zemor považoval za typickou třídu Sipser – Spielmanovy konstrukce expandér kódy, kde je podkladový graf bipartitní graf. Sipser a Spielman představili konstruktivní rodinu asymptoticky dobrých kódů lineární chyby spolu s jednoduchým paralelním algoritmem, který vždy odstraní konstantní zlomek chyb. Článek je založen na poznámkách k kurzu Dr. Venkatesana Guruswamiho ^[2]

Konstrukce kódu

Zemorův algoritmus je založen na typu expandérové ​​grafy volala Tannerův graf. Konstrukce kódu byla poprvé navržena Tannerem.^[3] Kódy jsou založeny na dvojitý kryt ${ displaystyle d}$, pravidelný expandér ${ displaystyle G}$, což je bipartitní graf. ${ displaystyle G}$ =${ displaystyle left (V, E right)}$, kde ${ displaystyle V}$ je množina vrcholů a ${ displaystyle E}$ je sada hran a ${ displaystyle V}$ = ${ displaystyle A}$ ${ displaystyle cup}$ ${ displaystyle B}$ a ${ displaystyle A}$ ${ displaystyle cap}$ ${ displaystyle B}$ = ${ displaystyle emptyset}$, kde ${ displaystyle A}$ a ${ displaystyle B}$ označuje množinu 2 vrcholů. Nechat ${ displaystyle n}$ být počet vrcholů v každé skupině, tj, ${ displaystyle | A | = | B | = n}$. Okraj set ${ displaystyle E}$ být velikosti ${ displaystyle N}$ =${ displaystyle nd}$ a každý okraj dovnitř ${ displaystyle E}$ má jeden koncový bod v obou ${ displaystyle A}$ a ${ displaystyle B}$. ${ displaystyle E (v)}$ označuje sadu hran obsahující ${ displaystyle v}$.

Předpokládejme objednání dne ${ displaystyle V}$, proto bude objednávka provedena na všech okrajích ${ displaystyle E (v)}$ pro každého ${ displaystyle v ve V}$. Nechat konečné pole ${ displaystyle mathbb {F} = GF (2)}$a na slovo ${ displaystyle x = (x_ {e}), e v E}$ v ${ displaystyle mathbb {F} ^ {N}}$, nechte podřízené slovo slova indexovat pomocí ${ displaystyle E (v)}$. Nechť je toto slovo označeno ${ displaystyle (x) _ {v}}$. Podmnožina vrcholů ${ displaystyle A}$ a ${ displaystyle B}$ vyvolává každé slovo ${ displaystyle x in mathbb {F} ^ {N}}$ oddíl do ${ displaystyle n}$ nepřekrývající se dílčí slova ${ displaystyle left (x right) _ {v} in mathbb {F} ^ {d}}$, kde ${ displaystyle v}$ se pohybuje nad prvky ${ displaystyle A}$. Pro konstrukci kódu ${ displaystyle C}$, zvažte lineární subkód ${ displaystyle C_ {o}}$, což je ${ displaystyle [d, r_ {o} d, delta]}$ kód, kde ${ displaystyle q}$, velikost abecedy je ${ displaystyle 2}$. Pro jakýkoli vrchol ${ displaystyle v ve V}$, nechť ${ displaystyle v (1), proti (2), ldots, proti (d)}$ být nějaké objednání ${ displaystyle d}$ vrcholy ${ displaystyle E}$ přilehlý k ${ displaystyle v}$. V tomto kódu každý bit ${ displaystyle x_ {e}}$ je spojen s hranou ${ displaystyle e}$ z ${ displaystyle E}$.

Můžeme definovat kód ${ displaystyle C}$ být množina binárních vektorů ${ displaystyle x = left (x_ {1}, x_ {2}, ldots, x_ {N} right)}$ z ${ displaystyle {0,1 } ^ {N}}$ tak, že pro každý vrchol ${ displaystyle v}$ z ${ displaystyle V}$, ${ displaystyle left (x_ {v (1)}, x_ {v (2)}, ldots, x_ {v (d)} right)}$ je kódové slovo z ${ displaystyle C_ {o}}$. V tomto případě můžeme uvažovat o zvláštním případě, kdy každá hrana ${ displaystyle E}$ sousedí přesně ${ displaystyle 2}$ vrcholy ${ displaystyle V}$. Znamená to, že ${ displaystyle V}$ a ${ displaystyle E}$ tvoří vrcholovou množinu a hranovou množinu ${ displaystyle d}$ běžný graf ${ displaystyle G}$.

Zavolejme kód ${ displaystyle C}$ takto konstruováno jako ${ displaystyle left (G, C_ {o} right)}$ kód. Pro daný graf ${ displaystyle G}$ a daný kód ${ displaystyle C_ {o}}$, existuje několik ${ displaystyle left (G, C_ {o} right)}$ kódy, protože existují různé způsoby řazení hran dopadajících na daný vrchol ${ displaystyle v}$, tj., ${ displaystyle v (1), proti (2), ldots, proti (d)}$. Ve skutečnosti náš kód ${ displaystyle C}$ se skládají ze všech kódových slov takových, že ${ displaystyle x_ {v} v C_ {o}}$ pro všechny ${ displaystyle v v A, B}$. Kód ${ displaystyle C}$ je lineární ${ displaystyle [N, K, D]}$ v ${ displaystyle mathbb {F}}$ protože je generován z subkódu ${ displaystyle C_ {o}}$, který je lineární. Kód ${ displaystyle C}$ je definován jako ${ displaystyle C = {c v mathbb {F} ^ {N} :( c) _ {v} v C_ {o} }}$ pro každého ${ displaystyle v ve V}$.

Graf G a kód C.

Na tomto obrázku ${ displaystyle (x) _ {v} = left (x_ {e1}, x_ {e2}, x_ {e3}, x_ {e4} right) in C_ {o}}$. Zobrazuje graf ${ displaystyle G}$ a kód ${ displaystyle C}$.

V matici ${ displaystyle G}$, nechť ${ displaystyle lambda}$ se rovná druhé největší vlastní hodnota z matice sousedství z ${ displaystyle G}$. Zde je největší vlastní hodnota ${ displaystyle d}$. Uvádějí se dvě důležitá tvrzení:

Nárok 1

${ displaystyle left ({ dfrac {K} {N}} right) geq 2r_ {o} -1}$
. Nechat ${ displaystyle R}$ je míra lineárního kódu vytvořeného z bipartitního grafu, jehož číselné uzly mají stupeň ${ displaystyle m}$ a jejichž uzly subkódu mají stupeň ${ displaystyle n}$. Pokud jeden lineární kód s parametry ${ displaystyle left (n, k right)}$ a hodnotit ${ displaystyle r = left ({ dfrac {k} {n}} right)}$ je spojen s každým z uzlů subkódů ${ displaystyle k geq 1- left (1-r right) m}$.

Důkaz

Nechat ${ displaystyle R}$ je rychlost lineárního kódu, která se rovná ${ displaystyle K / N}$Nechť jsou ${ displaystyle S}$ uzly subkódů v grafu. Pokud je stupeň subkódu ${ displaystyle n}$, pak kód musí mít ${ displaystyle left ({ dfrac {n} {m}} right) S}$ číslic, ke kterým je připojen každý číslicový uzel ${ displaystyle m}$ z ${ displaystyle left (n right) S}$ okraje v grafu. Každý uzel subkódu přispívá ${ displaystyle (n-k)}$ rovnice pro kontrolu parity pro celkem ${ displaystyle left (n-k right) S}$. Tyto rovnice nemusí být lineárně nezávislé. Proto, ${ displaystyle left ({ dfrac {K} {N}} right) geq left ({ dfrac {({ dfrac {n} {m}}) S- (nk) S} {({ dfrac {n} {m}}) S}} vpravo)}$
${ displaystyle geq 1-m vlevo ({ dfrac {n-k} {n}} vpravo)}$
${ displaystyle geq 1-m doleva (1-r doprava)}$, Protože hodnota ${ displaystyle m}$, tj. číslicový uzel tohoto bipartitního grafu je ${ displaystyle 2}$ a tady ${ displaystyle r = r_ {o}}$, můžeme psát jako:
${ displaystyle left ({ dfrac {K} {N}} right) geq 2r_ {o} -1}$

2. nárok

${ displaystyle D geq N left ({ dfrac {( delta - ({ dfrac { lambda} {d}}))} {(1 - ({ dfrac { lambda} {d}}) }}) vpravo) ^ {2}}$

${ displaystyle = N left ( delta ^ {2} -O left ({ dfrac { lambda} {d}} right) right)}$ ${ displaystyle rightarrow (1)}$

Li ${ displaystyle S}$ je lineární kód rychlosti ${ displaystyle r}$, délka kódu bloku ${ displaystyle d}$a minimální relativní vzdálenost ${ displaystyle delta}$, a pokud ${ displaystyle B}$ je graf dopadu vrcholového vrcholu a ${ displaystyle d}$ - pravidelný graf s druhou největší vlastní hodnotou ${ displaystyle lambda}$, pak kód ${ displaystyle C (B, S)}$ má rychlost alespoň ${ displaystyle 2r_ {o} -1}$ a minimální relativní vzdálenost alespoň ${ displaystyle left ( left ({ dfrac { delta - left ({ dfrac { lambda} {d}} right)} {1- left ({ dfrac { lambda} {d} } right)}} right) right) ^ {2}}$.

Důkaz

Nechat ${ displaystyle B}$ být odvozen z ${ displaystyle d}$ běžný graf ${ displaystyle G}$. Takže počet proměnných ${ displaystyle C (B, S)}$ je ${ displaystyle left ({ dfrac {dn} {2}} right)}$ a počet omezení je ${ displaystyle n}$. Podle Alon - Chung,^[4] -li ${ displaystyle X}$ je podmnožina vrcholů ${ displaystyle G}$ velikosti ${ displaystyle gamma n}$, pak je počet hran obsažených v podgrafu vyvolán ${ displaystyle X}$ v ${ displaystyle G}$ je nanejvýš ${ displaystyle left ({ dfrac {dn} {2}} right) left ( gamma ^ {2} + ({ dfrac { lambda} {d}}) gamma left (1- gamma right) right)}$.

Výsledkem je jakákoli sada ${ displaystyle left ({ dfrac {dn} {2}} right) left ( gamma ^ {2} + left ({ dfrac { lambda} {d}} right) gamma left (1- gama doprava) doprava)}$ proměnné budou mít alespoň ${ displaystyle gamma n}$ omezení jako sousedé. Průměrný počet proměnných na omezení je tedy: ${ displaystyle left ({ dfrac {({ dfrac {2.} {2}}) left ( gamma ^ {2} + ({ dfrac { lambda} {d}}) gamma left ( 1- gamma right) right)} { gamma n}} right)}$${ displaystyle = d left ( gamma + ({ dfrac { lambda} {d}}) left (1- gamma right) right)}$ ${ displaystyle rightarrow (2)}$

Takže když ${ displaystyle d left ( gamma + ({ dfrac { lambda} {d}}) left (1- gamma right) right) < gamma d}$, pak slovo relativní váhy ${ displaystyle left ( gamma ^ {2} + ({ dfrac { lambda} {d}}) gamma left (1- gamma right) right)}$, nemůže být kódovým slovem ${ displaystyle C (B, S)}$. Nerovnost ${ displaystyle (2)}$ je spokojen pro ${ displaystyle gamma < left ({ dfrac {1 - ({ dfrac { lambda} {d}})} { delta - ({ dfrac { lambda} {d}})}}) )}$. Proto, ${ displaystyle C (B, S)}$ nemůže mít nenulové kódové slovo relativní váhy ${ displaystyle left ({ dfrac { delta - ({ dfrac { lambda} {d}})} {1 - ({ dfrac { lambda} {d}})}} vpravo) ^ { 2}}$ nebo méně.

V matici ${ displaystyle G}$, můžeme to předpokládat ${ displaystyle lambda / d}$ je ohraničen od ${ displaystyle 1}$. Pro tyto hodnoty ${ displaystyle d}$ ve kterém ${ displaystyle d-1}$ je liché prvočíslo, existují explicitní konstrukce sekvencí ${ displaystyle d}$ - pravidelné bipartitní grafy s libovolně velkým počtem vrcholů, takže každý graf ${ displaystyle G}$ v pořadí je a Ramanujan graf. Říká se tomu graf Ramanujan, protože uspokojuje nerovnost ${ displaystyle lambda (G) leq 2 { sqrt {d-1}}}$. Určité vlastnosti expanze jsou viditelné v grafu ${ displaystyle G}$ jako oddělení mezi vlastními hodnotami ${ displaystyle d}$ a ${ displaystyle lambda}$. Pokud graf ${ displaystyle G}$ je graf Ramanujan, pak tento výraz ${ displaystyle (1)}$ bude ${ displaystyle 0}$ nakonec jako ${ displaystyle d}$ se zvětší.

Zemorův algoritmus

Níže napsaný iterativní dekódovací algoritmus střídá vrcholy ${ displaystyle A}$ a ${ displaystyle B}$ v ${ displaystyle G}$ a opraví kódové slovo z ${ displaystyle C_ {o}}$ v ${ displaystyle A}$ a poté se přepne a opraví kódové slovo ${ displaystyle C_ {o}}$ v ${ displaystyle B}$. Zde hrany spojené s vrcholem na jedné straně grafu nejsou incidenty s jiným vrcholem na této straně. Ve skutečnosti nezáleží na tom, v jakém pořadí, na sadě uzlů ${ displaystyle A}$ a ${ displaystyle B}$ jsou zpracovány. Zpracování vrcholů lze také provádět paralelně.

Dekodér ${ displaystyle mathbb {D}: mathbb {F} ^ {d} rightarrow C_ {o}}$znamená dekodér pro ${ displaystyle C_ {o}}$ který se správně zotaví s jakýmikoli kódovými slovy s méně než ${ displaystyle left ({ dfrac {d} {2}} right)}$ chyby.

Algoritmus dekodéru

Přijaté slovo: ${ displaystyle w = (w_ {e}), e v E}$
${ displaystyle z leftarrow w}$
Pro ${ displaystyle t leftarrow 1}$ na ${ displaystyle m}$ dělat //${ displaystyle m}$ je počet iterací
{if (${ displaystyle t}$ je liché) // Zde se bude algoritmus střídat mezi dvěma sadami vrcholů.
${ displaystyle X leftarrow A}$
jiný ${ displaystyle X leftarrow B}$
Opakování ${ displaystyle t}$: Pro každého ${ displaystyle v v X}$, nechť ${ displaystyle (z) _ {v} leftarrow mathbb {D} ((z) _ {v})}$ // Dekódování ${ displaystyle z_ {v}}$ na nejbližší kódové slovo.
}
Výstup: ${ displaystyle z}$

Vysvětlení algoritmu

Od té doby ${ displaystyle G}$ je bipartitní, sada ${ displaystyle A}$ vrcholů indukuje rozdělení sady hran ${ displaystyle E}$ = ${ displaystyle cup _ {v v A} E_ {v}}$ . Sada ${ displaystyle B}$ vyvolá další oddíl, ${ displaystyle E}$ = ${ displaystyle cup _ {v v B} E_ {v}}$ .

Nechat ${ displaystyle w in {0,1 } ^ {N}}$ být přijatým vektorem a připomenout si to ${ displaystyle N = dn}$. První iterace algoritmu spočívá v použití úplného dekódování kódu vyvolaného ${ displaystyle E_ {v}}$ pro každého ${ displaystyle v v A}$ . To znamená, že pro výměnu, pro všechny ${ displaystyle v v A}$, vektor ${ displaystyle left (w_ {v (1)}, w_ {v (2)}, ldots, w_ {v (d)} right)}$ jedním z nejbližších kódových slov z ${ displaystyle C_ {o}}$. Protože podmnožiny hran ${ displaystyle E_ {v}}$ jsou disjunktní pro ${ displaystyle v v A}$, jejich dekódování ${ displaystyle n}$ subvektory ${ displaystyle w}$ lze provést paralelně.

Iterací se získá nový vektor ${ displaystyle z}$. Další iterace spočívá v použití předchozího postupu na ${ displaystyle z}$ ale s ${ displaystyle A}$ nahrazen ${ displaystyle B}$. Jinými slovy, spočívá v dekódování všech subvektorů indukovaných vrcholy ${ displaystyle B}$. Nadcházející iterace tyto dva kroky opakují a střídavě aplikují paralelní dekódování na subvektory indukované vrcholy ${ displaystyle A}$ a na subvektory indukované vrcholy ${ displaystyle B}$.
Poznámka: [Li ${ displaystyle d = n}$ a ${ displaystyle G}$ je tedy úplný bipartitní graf ${ displaystyle C}$ je kód produktu ${ displaystyle C_ {o}}$ sám se sebou a výše uvedený algoritmus se redukuje na přirozené tvrdé iterativní dekódování produktových kódů].

Zde je počet iterací, ${ displaystyle m}$ je ${ displaystyle left ({ dfrac {( log {n})} { log (2- alpha)}} right)}$. Obecně může výše uvedený algoritmus opravit kódové slovo, jehož Hammingova hmotnost není větší než ${ displaystyle ({ dfrac {1} {2}}). alpha N delta left (({ dfrac { delta} {2}}) - ({ dfrac { lambda} {d}} ) right) = left (({{dfrac {1} {4}}). alpha N ( delta ^ {2} -O ({ dfrac { lambda} {d}}) right)}$ pro hodnoty ${ displaystyle alpha <1}$. Zde je dekódovací algoritmus implementován jako obvod velikosti ${ displaystyle O (N log {N})}$ a hloubka ${ displaystyle O ( log {N})}$ který vrací kódové slovo, protože vektor chyby má váhu menší než ${ displaystyle alpha N delta ^ {2} (1- epsilon) / 4}$ .

Teorém

Li ${ displaystyle G}$ je graf Ramanujan dostatečně vysokého stupně pro všechny ${ displaystyle alpha <1}$může dekódovací algoritmus opravit ${ displaystyle ({ dfrac { alpha delta _ {o} ^ {2}} {4}}) (1 in) N}$ chyby, v ${ displaystyle O ( log {n})}$ kola (kde velká ${ displaystyle O}$ notace skrývá závislost na ${ displaystyle alpha}$). To lze implementovat v lineárním čase na jednom procesoru; na ${ displaystyle n}$ procesory každé kolo lze implementovat v konstantním čase.

Důkaz

Protože dekódovací algoritmus je necitlivý na hodnotu hran a lineárností, můžeme předpokládat, že přenášené kódové slovo je all nula - vektor. Nechte přijaté kódové slovo být ${ displaystyle w}$. Je zohledněna sada hran, která má při dekódování nesprávnou hodnotu. Zde máme na mysli nesprávnou hodnotu ${ displaystyle 1}$ v kterékoli z bitů. Nechat ${ displaystyle w = w ^ {0}}$ být počáteční hodnotou kódového slova, ${ displaystyle w ^ {1}, w ^ {2}, ldots, w ^ {t}}$ být hodnoty po první, druhé. . . ${ displaystyle t}$ fáze dekódování. Tady, ${ displaystyle X ^ {i} = {e v E | x_ {e} ^ {i} = 1}}$, a ${ displaystyle S ^ {i} = {v ve V ^ {i} | E_ {v} cap X ^ {i + 1}! = emptyset}}$. Tady ${ displaystyle S ^ {i}}$ odpovídá těm souborům vrcholů, které nebyly schopny úspěšně dekódovat své kódové slovo v ${ displaystyle i ^ {th}}$ kolo. Z výše uvedeného algoritmu ${ displaystyle S ^ {1}$ protože počet neúspěšných vrcholů bude opraven v každé iteraci. Můžeme to dokázat ${ displaystyle S ^ {0}> S ^ {1}> S ^ {2}> cdots}$je klesající sekvence. ${ displaystyle | S_ {i + 1} | <= ({ dfrac {1} {2- alpha}}) | S_ {i} |}$. Jak předpokládáme, ${ displaystyle alpha <1}$, výše uvedená rovnice je v a geometrická klesající posloupnost. Takže když ${ displaystyle | S_ {i} |$, více než ${ displaystyle log_ {2- alpha} n}$ kola jsou nutná. Dále ${ displaystyle sum | S_ {i} | = n sum ({ dfrac {1} {(2- alpha) ^ {i}}}) = O (n)}$, a pokud implementujeme ${ displaystyle i ^ {th}}$ zaokrouhlit ${ displaystyle O (| S_ {i} |)}$ čas, pak bude celková sekvenční doba chodu lineární.

Nevýhody Zemorova algoritmu

1. Je to zdlouhavý proces jako počet iterací ${ displaystyle m}$ v dekodéru algoritmus trvá ${ displaystyle [( log {n}) / ( log (2- alpha))]}$
2. Zemorův dekódovací algoritmus považuje za obtížné dekódovat vymazání. Podrobný způsob, jak můžeme algoritmus vylepšit, je

uvedeny v.^[5]

Viz také

• Expander kódy
• Tannerův graf
• Lineární časové kódování a dekódování kódů opravujících chyby

Reference