Felexponent

I informationsteorin är felexponenten för en kanalkod eller källkod över kodens blocklängd den hastighet med vilken felsannolikheten avtar exponentiellt med kodens blocklängd. Formellt definieras det som det begränsande förhållandet mellan den negativa logaritmen för felsannolikheten och blocklängden för koden för stora blocklängder. Till exempel, om sannolikheten för fel $P_{\mathrm {error} }$ för en avkodare sjunker som ${\displaystyle e^{-n\alpha }} ,$ där $n$ är blocklängden, felexponenten är $\alpha$ . I det här exemplet närmar sig ${\displaystyle {\frac {-\ln P_{\mathrm {error} }}{n}}} α {\$ $alpha }$ \ för stora $n$ . Många av de informationsteoretiska satserna är av asymptotisk natur, till exempel säger kanalkodningssatsen att för varje hastighet som är mindre än kanalkapaciteten kan sannolikheten för felet i kanalkoden fås att gå till noll som blocklängd går till oändligheten. I praktiska situationer finns det begränsningar för kommunikationens fördröjning och blocklängden måste vara begränsad. Därför är det viktigt att studera hur sannolikheten för fel sjunker när blocklängden går till oändlighet.

Felexponent i kanalkodning

För tidsinvarianta DMC:er

Kanalkodningssatsen säger att för vilken som helst ε > 0 och för vilken frekvens som helst som är mindre än kanalkapaciteten finns det ett kodnings- och avkodningsschema som kan användas för att säkerställa att sannolikheten för blockfel är mindre än ε > 0 för ett tillräckligt långt meddelande block X. _ Dessutom, för vilken takt som helst som är större än kanalkapaciteten, går sannolikheten för blockfel vid mottagaren till ett när blocklängden går till oändlighet.

Om man antar en kanalkodningsuppställning enligt följande: kanalen kan sända vilket som helst av $M=2^{nR}\;$ meddelanden, genom att sända motsvarande kodord (som har längden n ). Varje komponent i kodboken ritas iid enligt någon sannolikhetsfördelning med sannolikhetsmassfunktion Q . Vid avkodningsänden görs maximal sannolikhetsavkodning.

Låt $X_{i}^{n}$ vara det ${\displaystyle i}:$ e slumpmässiga kodordet i kodboken, där $i$ går från $1$ till ${\ displaystil M}$ . Antag att det första meddelandet är valt, så kodord $X_{1}^{n}$ sänds. Med tanke på att $y_{1}^{n}$ tas emot, är sannolikheten för att kodordet felaktigt detekteras som $X_{2}^{n}$ :

P_{\mathrm {error} \ 1\to 2}=\summa _{x_{2}^{n}}Q(x_{2}^{n})1(p(y_{1}^ {n}\mid x_{2}^{n})>p(y_{1}^{n}\mid x_{1}^{n})).

Funktionen $1(p(y_{1}^{n}\mid x_{2}^{n })>p(y_{1}^{n}\mid x_{1}^{n}))$ har övre gräns

\left({\frac {p(y_{1}^{n}\mid x_{2}^ {n})}{p(y_{1}^{n}\mid x_{1}^{n})}}\right)^{s}

för $s>0\;$ Alltså,

P_{\mathrm {fel} \ 1\to 2}\leq \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})}}\right)^{ s}.

Eftersom det finns totalt M meddelanden, och posterna i kodboken är iid, är sannolikheten att $X_{1}^{n}$ förväxlas med något annat meddelande $M$ gånger ovanstående uttryck. Med hjälp av unionsbunden, är sannolikheten att förväxla $X_{1}^{n}$ med ett meddelande begränsat av:

P_{\mathrm {fel} \ 1\to \mathrm {valfri} }\leq M^{\rho }\left(\summa _{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})}}\höger)^{s}\höger)^{\rho }

för någon $0<\rho <1$ . Medelvärde över alla kombinationer av $x_{1}^{n},y_{1}^{n}$ :

P_{\mathrm {error} \ 1\to \mathrm {någon} }\leq M^{\rho }\summa _{y_{1}^{n}}\left(\summa _{x_{ 1}^{n}}Q(x_{1}^{n})[p(y_{1}^{n}\mid x_{1}^{n})]^{1-s\rho }\ höger)\left(\summa _{x_{2}^{n}}Q(x_{2}^{n})[p(y_{1}^{n}\mid x_{2}^{n} )]^{s}\höger)^{\rho }.

Välj $s=1-s\rho$ och kombinera de två summorna över $x_{1}^{n}$ i formeln ovan:

P_{\mathrm {error} \ 1\to \mathrm {någon} }\leq M^{\rho }\summa _{y_{1}^{n}}\left(\summa _{x_{ 1}^{n}}Q(x_{1}^{n})[p(y_{1}^{n}\mid x_{1}^{n})]^{\frac {1}{1 +\rho }}\right)^{1+\rho }.

Genom att använda oberoendekaraktären hos elementen i kodordet och kanalens diskreta minneslösa natur:

P_{\mathrm {error} \ 1\to \mathrm {any} }\leq M^{\rho }\prod _{i=1}^{n}\sum _{y_{i}} \left(\sum _{x_{i}}Q_{i}(x_{i})[p_{i}(y_{i}\mid x_{i})]^{\frac {1}{1+ \rho }}\right)^{1+\rho }

Genom att använda det faktum att varje element i kodord är identiskt fördelat och därmed stationärt:

P_{\mathrm {fel} \ 1\till \mathrm {valfri} }\leq M^{\rho }\left(\summa _{y}\left(\summa _{x}Q(x) [p(y\mid x)]^{\frac {1}{1+\rho }}\right)^{1+\rho }\right)^{n}.

Ersätter M med 2 ^nR och definierar

E_{o}( \rho ,Q)=-\ln \left(\sum _{y}\left(\sum _{x}Q(x)[p(y\mid x)]^{1/(1+\rho) }\right)^{1+\rho }\right),

sannolikheten för fel blir

P_{\mathrm {fel} }\leq \exp(-n(E_{o}(\rho ,Q)-\rho R)).

Q och $\rho$ ska väljas så att gränsen är tätast. Således kan felexponenten definieras som

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

Felexponent i källkodning

För tidsinvarierande diskreta minneslösa källor

Källkodssatsen anger att för vilken ${\displaystyle \varepsilon >0} som helst$ och vilken som helst diskret-tid iid-källa som $X$ och för alla fall mindre än källans entropi , finns det tillräckligt stort $n$ och en kodare som tar $n$ iid upprepning av källan, $X^{1:n}$ , och mappar den till $n.(H(X)+\varepsilon )$ binära bitar så att källsymbolerna $X^{1:n}$ är återvinningsbara från binären bitar med sannolikhet minst $1-\varepsilon$ .

Låt $M=e^{nR}\,\!$ vara det totala antalet möjliga meddelanden. Mappa sedan var och en av de möjliga källutgångssekvenserna till ett av meddelandena slumpmässigt med hjälp av en enhetlig fördelning och oberoende av allt annat. När en källa genereras sänds sedan motsvarande meddelande $M=m\,$ till destinationen. Meddelandet avkodas till en av de möjliga källsträngarna. $) {\displaystyle P(X_{1 }^{n}\mid A_{m})}$ för fel kommer avkodaren att avkoda till källsekvensen $X_{1}^{n}$ maximerar , där $A_{m}\,$ anger händelsen att meddelandet $m$ sändes. Denna regel motsvarar att hitta källsekvensen $X_{1}^{n}$ bland uppsättningen källsekvenser som mappas till meddelande $m$ som maximerar ${\ displaystil P(X_{1}^{n})}$ . Denna minskning följer av att meddelandena tilldelades slumpmässigt och oberoende av allt annat.

Således, som ett exempel på när ett fel uppstår, antas att källsekvensen $X_{1}^{n}(1)$ mappades till meddelande $1$ som var källsekvens $X_{1}^{n}(2)$ . Om $X_{1}^{n}(1)\,$ genererades vid källan, men $P(X_{1}^{n}(2))>P(X_{1}^{n}(1))$ så uppstår ett fel.

Låt $S_{i}\,$ beteckna händelsen att källsekvensen $X_{1}^{n}(i)$ genererades vid källan, så att ${\displaystyle P(S_{i})=P(X_{1}^{n}(i))\,.} Då kan$ sannolikheten för fel delas upp som ${\displaystyle P(E)=\sum _{i}P(E\mid S_{i})P(S_{i})\,.} Således kan uppmärksamheten fokuseras på att hitta en övre$ gräns till ${\displaystyle P(E\mid S_{i})\,$ .

Låt $A_{i'}\,$ beteckna händelsen att källsekvensen $X_{1}^{n}(i')$ mappades till densamma meddelande som källsekvensen $X_{1}^{n}(i)$ och att ${\ displaystil P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i))}$ . Låter alltså $X_{i,i'}\,$ beteckna händelsen som de två källsekvenserna $i\,$ och $i'\,$ mappar till samma budskap, det har vi

P(A_{i'})=P\ vänster(X_{i,i'}\bigcap P(X_{1}^{n}(i')\right)\geq P(X_{1}^{n}(i)))\,

och med det faktum att $P(X_{i,i'})={\frac {1}{M}}\,$ och är oberoende av allt annat har den där

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

En enkel övre gräns för termen till vänster kan fastställas som

_ displaystyle \left[P(P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i)))\right]\leq \left({\frac { P(X_{1}^{n}(i'))}{P(X_{1}^{n}(i))}}\höger)^{s}\,}

för några godtyckliga reella tal $s>0\,.$ Denna övre gräns kan verifieras genom att notera att ${\displaystyle P(P(X_) {1}^{n}(i'))>P(X_{1}^{n}(i)))\,} är antingen lika med$ 1 $\displaystyle 1\,}$ eller $0\,$ eftersom sannolikheterna för en given ingångssekvens är helt deterministiska. Således, om $P(X_{1}^{n}(i'))\geq P(X_{1} ^{n}(i))\,,$ sedan ${\frac {P(X_{1}^{n }(i'))}{P(X_{1}^{n}(i))}}\geq 1\,$ så att olikheten gäller i så fall. Ojämlikheten gäller även i det andra fallet eftersom

\left({\frac {P(X_{1}^{n}(i'))}{ P(X_{1}^{n}(i))}}\höger)^{s}\geq 0\,

för alla möjliga källsträngar. Således, kombinera allt och introducera några ${\displaystyle \rho \in [0,1]\,} ,$ har det

P(E\mid S_{i})\leq P(\bigcup _{i\neq i'}A_{i'})\leq \left(\sum _{i\neq i'}P( A_{i'})\right)^{\rho }\leq \left({\frac {1}{M}}\summa _{i\neq i'}\left({\frac {P(X_{ 1}^{n}(i'))}{P(X_{1}^{n}(i))}}\höger)^{s}\höger)^{\rho }\,.

Där ojämlikheterna följer av en variation på Union Bound. Om du slutligen tillämpar denna övre gräns på summeringen för $P(E)\,$ har det:

P(E)=\summa _{i}P(E\mid S_{i})P(S_{i})\leq \summa _{i}P(X_{1}^{n}( i))\left({\frac {1}{M}}\sum _{i'}\left({\frac {P(X_{1}^{n}(i'))}{P(X_ {1}^{n}(i))}}\right)^{s}\right)^{\rho }\,.

Där summan nu kan tas över alla $i'\,$ eftersom det bara kommer att öka gränsen. I slutändan ger det det

P(E)\leq {\frac {1}{M^{\rho }}}\sum _{i}P(X_{1}^{n}(i))^{1-s\ rho }\left(\sum _{i'}P(X_{1}^{n}(i'))^{s}\right)^{\rho }\,.

Låt nu för enkelhetens skull $1-s\rho =s\,$ så att $s={\frac {1}{1+\rho }}\,.$ Ersätter detta nya värde på $s\,$ med ovanstående gräns för sannolikheten för fel och använder det faktum att $i'\,$ är bara en dummyvariabel i summan ger följande som en övre gräns för sannolikheten för fel: