Zyablov vázán - Zyablov bound

V teorii kódování je Zyablov vázán je dolní mez sazby ${ displaystyle r}$ a relativní vzdálenost ${ displaystyle delta}$ které jsou dosažitelné do zřetězené kódy.

Prohlášení o vazbě

Vázaný uvádí, že existuje rodina ${ displaystyle q}$-ary (zřetězené, lineární) kódy s rychlostí ${ displaystyle r}$ a relativní vzdálenost ${ displaystyle delta}$ kdykoli

${ Displaystyle r leqslant max limity _ {0 leqslant r ' leqslant 1-H_ {q} ( delta)} r' cdot left (1 - { delta over {H_ {q} ^ {-1} (1-r ')}} vpravo)}$,

kde ${ displaystyle H_ {q}}$je ${ displaystyle q}$- funkce entropie

${ displaystyle H_ {q} (x) = x log _ {q} (q-1) -x log _ {q} (x) - (1-x) log _ {q} (1-x )}$.

Obrázek 1: Zyablovská vazba. Pro srovnání je také vynesena vazba GV (která poskytuje dosažitelné parametry pro obecné kódy, které nemusí být efektivně dekódovatelné).

Popis

Vazba se získá zvážením rozsahu parametrů, které lze získat zřetězením „dobrého“ vnějšího kódu ${ displaystyle C_ {out}}$ s „dobrým“ vnitřním kódem ${ displaystyle C_ {in}}$. Konkrétně předpokládáme, že vnější kód splňuje Singleton vázán, tj. má míru ${ displaystyle r_ {out}}$a relativní vzdálenost ${ displaystyle delta _ {out}}$ uspokojující ${ displaystyle r_ {out} + delta _ {out} = 1}$. Reed Solomon kódy jsou skupinou takových kódů, které lze vyladit žádný hodnotit ${ displaystyle r_ {out} v (0,1)}$ a relativní vzdálenost ${ displaystyle 1-r_ {out}}$ (i když přes abecedu tak velkou, jako je délka kódového slova). Předpokládáme, že vnitřní kód splňuje Gilbert – Varshamov vázán, tj. má míru ${ displaystyle r_ {in}}$a relativní vzdálenost ${ displaystyle delta _ {in}}$ uspokojující ${ displaystyle r_ {in} + H_ {q} ( delta _ {in}) geq 1}$. Je známo, že náhodné lineární kódy uspokojují tuto vlastnost s vysokou pravděpodobností, a explicitní lineární kód splňující tuto vlastnost lze najít vyhledáváním hrubou silou (což vyžaduje časový polynom ve velikosti prostoru pro zprávy).

Zřetězení ${ displaystyle C_ {out}}$ a ${ displaystyle C_ {in}}$, označeno ${ displaystyle C_ {out} circ C_ {in}}$, má rychlost ${ displaystyle r = r_ {in} cdot r_ {out}}$ a relativní vzdálenost ${ displaystyle delta = delta _ {out} cdot delta _ {in} geq (1-r_ {out}) cdot H_ {q} ^ {- 1} (1-r_ {in}). }$

Vyjadřování ${ displaystyle r_ {out}}$ jako funkce ${ displaystyle delta, r_ {in}}$,

${ displaystyle r_ {out} geq 1 - { frac { delta} {H ^ {- 1} (1-r_ {in})}}}$

Poté optimalizujte výběr ${ displaystyle r_ {in}}$, vidíme, že je možné, aby zřetězený kód uspokojil,

${ displaystyle r geq max limity _ {0 leq r_ {in} leq {1-H_ {q} ( delta)}} r_ {in} cdot left (1 - { delta over {H_ {q} ^ {- 1} (1-r_ {in})}} vpravo)}$

Na obrázku 1 je graf této vazby.

Všimněte si, že vázaný Zyablov to znamená pro každého ${ displaystyle delta> 0}$, existuje (zřetězený) kód s kladnou rychlostí a kladnou relativní vzdáleností.

Poznámky

Můžeme zkonstruovat kód, který dosáhne Zyablovovy hranice v polynomiálním čase. Zejména můžeme konstruovat explicitní asymptoticky dobrý kód (přes některé abecedy) v polynomiálním čase.

Lineární kódy nám pomohou dokončit důkaz výše uvedeného tvrzení, protože lineární kódy mají polynomiální reprezentaci. Ať je Cout ${ displaystyle [N, K] _ {Q}}$ Korekce chyb Reed-Solomon kód kde ${ displaystyle N = Q-1}$ (hodnotící body jsou ${ displaystyle mathbb {F} _ {Q} ^ {*}}$ s ${ displaystyle Q = q ^ {k}}$, pak ${ displaystyle k = theta ( log N)}$.

Musíme zkonstruovat vnitřní kód, na kterém leží Gilbert-Varshamov vázán. To lze provést dvěma způsoby

1. Provádět vyčerpávající vyhledávání na všech maticích generátoru, dokud nebude splněna požadovaná vlastnost ${ displaystyle C_ {in}}$. Důvodem je, že Varshamovs vázaný státy, že existuje lineární kód, který leží na Gilbert-Varshamon vázaný, který bude mít ${ displaystyle q ^ {O (kn)}}$ čas. Použitím ${ displaystyle k = rn}$ dostaneme ${ displaystyle q ^ {O (kn)} = q ^ {O (k ^ {2})} = N ^ {O ( log N)}}$, který je horní ohraničen ${ displaystyle nN ^ {O ( log nN)}}$, kvazi-polynomiální časová vazba.
2. Konstruovat ${ displaystyle C_ {in}}$ v ${ displaystyle q ^ {O (n)}}$ čas a použití ${ displaystyle (nN) ^ {O (1)}}$ čas celkově. Toho lze dosáhnout použitím metody podmíněného očekávání na důkazu, že náhodný lineární kód leží na hranici s vysokou pravděpodobností.

Můžeme tedy zkonstruovat kód, který dosáhne Zyablovovy hranice v polynomiálním čase.

Viz také

• Singleton vázán
• Gilbert-Varshamov vázán

Odkazy a externí odkazy

• Poznámky k přednášce MIT o základní teorii kódování - Dr. Madhu Sudan
• University at Buffalo Přednášky o teorii kódování - Dr. Atri Rudra
• Přednáškové poznámky University of Washington o teorii kódování - Dr. Venkatesan Guruswami