Chybný exponent - Error exponent

Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) tento článek může být pro většinu čtenářů příliš technická na to, aby je pochopili. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (Srpna 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v teorie informace, chybový exponent a kód kanálu nebo zdrojový kód přes délku bloku kódu je rychlost, s jakou se pravděpodobnost chyby exponenciálně snižuje s délkou bloku kódu. Formálně je definován jako omezující poměr záporného logaritmu pravděpodobnosti chyby k délce bloku kódu pro velké délky bloku. Například pokud je pravděpodobnost chyby ${displaystyle P_ {mathrm {chyba}}}$ a dekodér kapky jako ${displaystyle e ^ {- nalpha}}$, kde ${displaystyle n}$ je délka bloku, chybový exponent je ${displaystyle alpha}$. V tomto příkladu ${displaystyle {frac {-ln P_ {mathrm {chyba}}} {n}}}$ přístupy ${displaystyle alpha}$ pro velké ${displaystyle n}$. Mnoho z informační teoretik věty jsou asymptotické povahy, například věta o kódování kanálu uvádí, že pro všechny hodnotit menší než kapacita kanálu, lze pravděpodobnost chyby kódu kanálu snížit na nulu, protože délka bloku jde do nekonečna. V praktických situacích existují omezení zpoždění komunikace a délka bloku musí být konečná. Proto je důležité studovat, jak klesá pravděpodobnost chyby s tím, jak délka bloku přechází do nekonečna.

Chybný exponent v kódování kanálu

Pro DMC časově neměnné

The věta o kódování kanálu uvádí, že pro libovolné ε> 0 a pro libovolné hodnotit menší než kapacita kanálu, existuje schéma kódování a dekódování, které lze použít k zajištění, že pravděpodobnost chyby bloku je menší než ε> 0 pro dostatečně dlouhý blok zpráv X. Také pro všechny hodnotit větší než kapacita kanálu, pravděpodobnost chyby bloku u přijímače jde na jednu, protože délka bloku jde do nekonečna.

Za předpokladu nastavení kódování kanálu následovně: kanál může vysílat kterýkoli z těchto kanálů ${displaystyle M = 2 ^ {nR};}$ zprávy zasláním odpovídajícího kódového slova (které je dlouhé n). Každá součást v číselníku je nakreslena i.i.d. podle nějakého rozdělení pravděpodobnosti s funkce pravděpodobnostní hmotnosti Q. Na konci dekódování se provede maximální pravděpodobnost dekódování.

Nechat ${displaystyle X_ {i} ^ {n}}$ být ${displaystyle i}$náhodné kódové slovo v číselníku, kde ${displaystyle i}$ jde od ${displaystyle 1}$ na ${displaystyle M}$. Předpokládejme, že je vybrána první zpráva, takže kódové slovo ${displaystyle X_ {1} ^ {n}}$ se přenáší. Vzhledem k tomu ${displaystyle y_ {1} ^ {n}}$ je přijata, pravděpodobnost, že kódové slovo bude nesprávně detekováno jako ${displaystyle X_ {2} ^ {n}}$ je:

${displaystyle P_ {mathrm {chyba} 1 o 2} = součet _ {x_ {2} ^ {n}} Q (x_ {2} ^ {n}) 1 (p (y_ {1} ^ {n} střední x_ {2} ^ {n})> p (y_ {1} ^ {n} uprostřed x_ {1} ^ {n})).}$

Funkce ${displaystyle 1 (p (y_ {1} ^ {n} střední x_ {2} ^ {n})> p (y_ {1} ^ {n} střední x_ {1} ^ {n}))}$ má horní mez

${displaystyle left ({frac {p (y_ {1} ^ {n} střední x_ {2} ^ {n})}} p (y_ {1} ^ {n} střední x_ {1} ^ {n})} } ight) ^ {s}}$

pro ${displaystyle s> 0;}$ Tím pádem,

${displaystyle P_ {mathrm {chyba} 1 o 2} leq součet _ {x_ {2} ^ {n}} Q (x_ {2} ^ {n}) vlevo ({frac {p (y_ {1} ^ {n } mid x_ {2} ^ {n})} {p (y_ {1} ^ {n} mid x_ {1} ^ {n})}} ight) ^ {s}.}$

Protože existuje celkem M zprávy a položky v číselníku jsou i.i.d., pravděpodobnost, že ${displaystyle X_ {1} ^ {n}}$ je zaměňována s jakoukoli jinou zprávou ${displaystyle M}$ krát výše uvedený výraz. Při použití svazku je pravděpodobnost záměny ${displaystyle X_ {1} ^ {n}}$ s jakoukoli zprávou je ohraničen:

${displaystyle P_ {mathrm {error} 1 o mathrm {any}} leq M ^ {ho} left (sum _ {x_ {2} ^ {n}} Q (x_ {2} ^ {n}) left ({frac {p (y_ {1} ^ {n} mid x_ {2} ^ {n})} {p (y_ {1} ^ {n} mid x_ {1} ^ {n})}} ight) ^ {s } ight) ^ {ho}}$

pro všechny ${displaystyle 0$. Průměrování všech kombinací ${displaystyle x_ {1} ^ {n}, y_ {1} ^ {n}}$:

${displaystyle P_ {mathrm {error} 1 o mathrm {any}} leq M ^ {ho} součet _ {y_ {1} ^ {n}} vlevo (součet _ {x_ {1} ^ {n}} Q (x_ {1} ^ {n}) [p (y_ {1} ^ {n} střední x_ {1} ^ {n})] ^ {1-sho} ight) vlevo (součet _ {x_ {2} ^ {n }} Q (x_ {2} ^ {n}) [p (y_ {1} ^ {n} uprostřed x_ {2} ^ {n})] ^ {s} ight) ^ {ho}.}$

Výběr ${displaystyle s = 1-sho}$ a sloučením těchto dvou součtů ${displaystyle x_ {1} ^ {n}}$ ve výše uvedeném vzorci:

${displaystyle P_ {mathrm {error} 1 o mathrm {any}} leq M ^ {ho} součet _ {y_ {1} ^ {n}} vlevo (součet _ {x_ {1} ^ {n}} Q (x_ {1} ^ {n}) [p (y_ {1} ^ {n} uprostřed x_ {1} ^ {n})] ^ {frac {1} {1 + ho}} ight) ^ {1 + ho} .}$

Pomocí nezávislosti prvků kódového slova a diskrétní paměti kanálu bez paměti:

${displaystyle P_ {mathrm {error} 1 o mathrm {any}} leq M ^ {ho} prod _ {i = 1} ^ {n} součet _ {y_ {i}} vlevo (součet _ {x_ {i}} Q_ {i} (x_ {i}) [p_ {i} (y_ {i} mid x_ {i})] ^ {frac {1} {1 + ho}} ight) ^ {1 + ho}}$

S využitím skutečnosti, že každý prvek kódového slova je identicky distribuován a tedy stacionární:

${displaystyle P_ {mathrm {error} 1 o mathrm {any}} leq M ^ {ho} left (sum _ {y} left (sum _ {x} Q (x) [p (ymid x)] ^ {frac { 1} {1 + ho}} ight) ^ {1 + ho} ight) ^ {n}.}$

Výměna M o 2^nR a definování

${displaystyle E_ {o} (ho, Q) = - ln vlevo (součet _ {y} vlevo (součet _ {x} Q (x) [p (ymid x)] ^ {1 / (1 + ho)} vpravo ) ^ {1 + ho} ight),}$

pravděpodobnost chyby

${displaystyle P_ {mathrm {error}} leq exp (-n (E_ {o} (ho, Q) -ho R)).}$

Q a ${displaystyle ho}$ by měl být zvolen tak, aby vázaný byl nejpevnější. Chybový exponent lze tedy definovat jako

${displaystyle E_ {r} (R) = max _ {Q} max _ {ho in [0,1]} E_ {o} (ho, Q) -ho R .;}$

Chybný exponent ve zdrojovém kódování

Pro časově neměnné diskrétní zdroje bez paměti

The zdrojové kódování věta říká, že pro všechny ${displaystyle varepsilon> 0}$ a jakékoli diskrétní i.i.d. zdroj jako ${displaystyle X}$ a pro všechny hodnotit méně než entropie zdroje je dostatečně velký ${displaystyle n}$ a kodér, který trvá ${displaystyle n}$ i.i.d. opakování zdroje, ${displaystyle X ^ {1: n}}$a mapuje to na ${displaystyle n. (H (X) + varepsilon)}$ binární bity tak, že zdrojové symboly ${displaystyle X ^ {1: n}}$ jsou obnovitelné z binárních bitů alespoň s pravděpodobností ${displaystyle 1-varepsilon}$.

Nechat ${displaystyle M = e ^ {nR} ,!}$ je celkový počet možných zpráv. Dále namapujte každou z možných výstupních sekvencí zdroje na jednu ze zpráv náhodně pomocí jednotného rozdělení a nezávisle na všem ostatním. Když je generován zdroj, odpovídající zpráva ${displaystyle M = m,}$ je poté přenesen do cíle. Zpráva se dekóduje na jeden z možných zdrojových řetězců. Aby se minimalizovala pravděpodobnost chyby, dekodér dekóduje zdrojovou sekvenci ${displaystyle X_ {1} ^ {n}}$ který maximalizuje ${displaystyle P (X_ {1} ^ {n} uprostřed A_ {m})}$, kde ${displaystyle A_ {m},}$ označuje událost, kterou zpráva ${displaystyle m}$ byl přenesen. Toto pravidlo je ekvivalentní hledání zdrojové sekvence ${displaystyle X_ {1} ^ {n}}$ mezi množinou zdrojových sekvencí, které se mapují na zprávu ${displaystyle m}$ který maximalizuje ${displaystyle P (X_ {1} ^ {n})}$. Toto snížení vyplývá ze skutečnosti, že zprávy byly přidělovány náhodně a nezávisle na všem ostatním.

Jako příklad toho, kdy dojde k chybě, se předpokládá, že zdrojová sekvence ${displaystyle X_ {1} ^ {n} (1)}$ byl namapován na zprávu ${displaystyle 1}$ stejně jako zdrojová sekvence ${displaystyle X_ {1} ^ {n} (2)}$. Li ${displaystyle X_ {1} ^ {n} (1),}$ byl vygenerován u zdroje, ale ${displaystyle P (X_ {1} ^ {n} (2))> P (X_ {1} ^ {n} (1))}$ pak dojde k chybě.

Nechat ${displaystyle S_ {i},}$ označují událost, že zdrojová sekvence ${displaystyle X_ {1} ^ {n} (i)}$ byl vygenerován u zdroje, takže ${displaystyle P (S_ {i}) = P (X_ {1} ^ {n} (i)) ,.}$ Potom lze pravděpodobnost chyby rozdělit na ${displaystyle P (E) = součet _ {i} P (Emid S_ {i}) P (S_ {i}) ,.}$ Pozornost tedy může být zaměřena na nalezení horní hranice k ${displaystyle P (Emid S_ {i}),}$.

Nechat ${displaystyle A_ {i '},}$ označují událost, že zdrojová sekvence ${displaystyle X_ {1} ^ {n} (i ')}$ byl namapován na stejnou zprávu jako zdrojová sekvence ${displaystyle X_ {1} ^ {n} (i)}$ a to ${displaystyle P (X_ {1} ^ {n} (i ')) geq P (X_ {1} ^ {n} (i))}$. Tak, nechat ${displaystyle X_ {i, i '},}$ označují událost, že dvě zdrojové sekvence ${displaystyle i,}$ a ${displaystyle i ',}$ na stejnou zprávu, máme to

${displaystyle P (A_ {i '}) = Pleft (X_ {i, i'} igcap P (X_ {1} ^ {n} (i ') ight) geq P (X_ {1} ^ {n} (i ))),}$

a s využitím skutečnosti, že ${displaystyle P (X_ {i, i '}) = {frac {1} {M}},}$ a je nezávislá na všem ostatním

${displaystyle P (A_ {i '}) = {frac {1} {M}} P (P (X_ {1} ^ {n} (i')) geq P (X_ {1} ^ {n} (i ))) ,.}$

Jednoduchou horní hranici pro výraz nalevo lze stanovit jako

${displaystyle left [P (P (X_ {1} ^ {n} (i ')) geq P (X_ {1} ^ {n} (i)) )ight] leq left ({frac {P (X_ {1 } ^ {n} (i '))} {P (X_ {1} ^ {n} (i))}} vpravo) ^ {s},}$

pro nějaké libovolné reálné číslo ${displaystyle s> 0 ,.}$ Tuto horní hranici lze ověřit uvedením ${displaystyle P (P (X_ {1} ^ {n} (i '))> P (X_ {1} ^ {n} (i))),}$ buď se rovná ${displaystyle 1,}$ nebo ${displaystyle 0,}$ protože pravděpodobnosti dané vstupní sekvence jsou zcela deterministické. Pokud tedy ${displaystyle P (X_ {1} ^ {n} (i ')) geq P (X_ {1} ^ {n} (i)) ,,}$ pak ${displaystyle {frac {P (X_ {1} ^ {n} (i '))} {P (X_ {1} ^ {n} (i))}} geq 1,}$ takže nerovnost v takovém případě platí. Nerovnost platí i v druhém případě, protože

${displaystyle left ({frac {P (X_ {1} ^ {n} (i '))} {P (X_ {1} ^ {n} (i))}} ight) ^ {s} geq 0,}$

pro všechny možné zdrojové řetězce. Tedy kombinace všeho a zavedení některých ${displaystyle ho in [0,1],}$, mít to

${displaystyle P (Emid S_ {i}) leq P (igcup _ {ieq i '} A_ {i'}) leq left (součet _ {ieq i '} P (A_ {i'}) ight) ^ {ho} leq left ({frac {1} {M}} součet _ {ieq i '} left ({frac {P (X_ {1} ^ {n} (i'))} {P (X_ {1} ^ {n } (i))}} ight) ^ {s} ight) ^ {ho} ,.}$

V případě, že nerovnosti vyplývají z variace na hranici Unie. Nakonec použijeme tuto horní hranici na součet pro ${displaystyle P (E),}$ mít to:

${displaystyle P (E) = součet _ {i} P (Emid S_ {i}) P (S_ {i}) leq součet _ {i} P (X_ {1} ^ {n} (i)) vlevo ({ frac {1} {M}} součet _ {i '} vlevo ({frac {P (X_ {1} ^ {n} (i'))} {P (X_ {1} ^ {n} (i)) }} ight) ^ {s} ight) ^ {ho} ,.}$

Kde nyní lze součet převzít vše ${displaystyle i ',}$ protože to jen zvýší vázanost. Nakonec to přineslo

${displaystyle P (E) leq {frac {1} {M ^ {ho}}} součet _ {i} P (X_ {1} ^ {n} (i)) ^ {1-sho} vlevo (součet _ { i '} P (X_ {1} ^ {n} (i')) ^ {s} ight) ^ {ho} ,.}$

Nyní pro jednoduchost ${displaystyle 1-sho = s,}$ aby ${displaystyle s = {frac {1} {1 + ho}} ,.}$ Nahrazení této nové hodnoty ${displaystyle s,}$ do výše uvedeného vázaného na pravděpodobnost chyby a s využitím skutečnosti, že ${displaystyle i ',}$ je jen fiktivní proměnná v součtu udává následující jako horní mez pravděpodobnosti chyby:

${displaystyle P (E) leq {frac {1} {M ^ {ho}}} vlevo (součet _ {i} P (X_ {1} ^ {n} (i)) ^ {frac {1} {1+ ho}} ight) ^ {1 + ho} ,.}$

${displaystyle M = e ^ {nR} ,!}$ a každá ze složek ${displaystyle X_ {1} ^ {n} (i),}$ jsou nezávislé. Zjednodušení výše uvedené rovnice tedy přináší

${displaystyle P (E) leq exp left (-nleft [ho R-ln left (sum _ {x_ {i}} P (x_ {i}) ^ {frac {1} {1 + ho}} ight) (1 + ho) ight] ight).}$

Termín v exponentu by měl být maximalizován ${displaystyle ho,}$ za účelem dosažení nejvyšší horní hranice pravděpodobnosti chyby.

Pronájem ${displaystyle E_ {0} (ho) = ln left (sum _ {x_ {i}} P (x_ {i}) ^ {frac {1} {1 + ho}} ight) (1 + ho) ,,}$ vidět, že chybový exponent pro případ kódování zdroje je:

${displaystyle E_ {r} (R) = max _ {ho in [0,1]} left [ho R-E_ {0} (ho) ight].,}$

Viz také

• Zdrojové kódování
• Kódování kanálu

Reference

R. Gallager, Informační teorie a spolehlivá komunikace, Wiley 1968