Wykładnik błędu

W teorii informacji wykładnik błędu kodu kanału lub kodu źródłowego na długości bloku kodu to szybkość, z jaką prawdopodobieństwo błędu spada wykładniczo wraz z długością bloku kodu. Formalnie definiuje się go jako graniczny stosunek ujemnego logarytmu prawdopodobieństwa błędu do długości bloku kodu dla dużych długości bloków. $jako$ , jeśli prawdopodobieństwo błędu - $e ^ {-n \ alfa$${\ displaystyle n}$ } } gdzie to długość bloku, wykładnik błędu to ${\ displaystyle \ alpha}$ . W tym przykładzie ${\ Displaystyle {\ Frac {- \ ln P _ {\ operatorname {błąd}}} {n}}}$$się$ do dużego ${ \displaystyle n}$ . Wiele teorii informacji ma charakter asymptotyczny, na przykład twierdzenie o kodowaniu kanałów stwierdza, że ​​dla dowolnej szybkości mniejszej niż przepustowość kanału prawdopodobieństwo błędu kodu kanału może spaść do zera, gdy długość bloku idzie do nieskończoności. W praktycznych sytuacjach opóźnienie komunikacji jest ograniczone, a długość bloku musi być skończona. Dlatego ważne jest zbadanie, w jaki sposób prawdopodobieństwo błędu spada, gdy długość bloku dąży do nieskończoności.

Wykładnik błędu w kodowaniu kanału

Dla niezmiennych w czasie DMC

Twierdzenie o kodowaniu kanału stwierdza, że ​​dla każdego ε > 0 i dla dowolnej szybkości mniejszej niż przepustowość kanału istnieje schemat kodowania i dekodowania, którego można użyć do zapewnienia, że ​​prawdopodobieństwo błędu bloku jest mniejsze niż ε > 0 dla wystarczająco długiej wiadomości blok X. _ Ponadto, dla dowolnej szybkości większej niż przepustowość kanału, prawdopodobieństwo błędu bloku w odbiorniku spada do jednego, gdy długość bloku dąży do nieskończoności.

$.$ : kanał może przesyłać dowolne z , przesyłając odpowiednie słowo kodowe (które n ) Każdy składnik w słowniku jest rysowany iid zgodnie z pewnym rozkładem prawdopodobieństwa z funkcją masy prawdopodobieństwa Q . Na końcu dekodowania przeprowadzane jest dekodowanie z maksymalnym prawdopodobieństwem.

Niech ${\ Displaystyle X_ {i} ^ {n}}$ będzie ${$ słowem kodowym w słowniku, gdzie przechodzi od $displaystyle$$1}$ do $\ styl wyświetlania M}$ . Załóżmy $, że$ pierwszą wiadomość, więc przesyłane jest słowo Biorąc pod uwagę, że $wynosi$ , prawdopodobieństwo, że słowo kodowe zostanie nieprawidłowo wykryte jako $\ Displaystyle X_ {2} ^ {n}}$ :

${\ Displaystyle P _ {\ operatorname {błąd} \ 1 \ do 2} = \ suma _ {x_ {2} ^ {n}} Q (x_ {2} ^ {n}) 1 (p (y_ {1} ^ {n}\mid x_{2}^{n})>p(y_{1}^{n}\mid x_{1}^{n})).}$

$} \ mid x_ {2} ^ {n })>p(y_{1}^{n}\mid x_{1}^{n})}}$ n ma górną granicę

${\ Displaystyle \ lewo ({\ Frac {p (y_ {1} ^ {n} \ mid x_ {2} ^ {n})}{p(y_{1}^{n}\mid x_{1}^{n})}}\right)^{s}}$

dla ${\ Displaystyle s> 0 \;}$ Tak więc,

${\ Displaystyle P _ {\ operatorname {błąd} \ 1 \ do 2} \ równoważnik \ suma _ {x_ {2} ^ {n}} Q (x_ {2} ^ {n}) \ lewo ({\ frac {p (y_{1}^{n}\mid x_{2}^{n})}{p(y_{1}^{n}\mid x_{1}^{n})}}\right)^{ S}.}$

Ponieważ w sumie jest M wiadomości, a wpisy w książce kodów są iid, prawdopodobieństwo, że zostanie pomylony z jakąkolwiek inną wiadomością, wynosi ${$$\ displaystyle M$ razy powyższe wyrażenie. Używając powiązania unii, prawdopodobieństwo pomyłki z jakąkolwiek wiadomością jest ograniczone przez: ${\ displaystyle X_ {1} ^ {n}}$

${\ Displaystyle P _ {\ operatorname {błąd} \ 1 \ do \ operatorname {dowolny}} \ równoważnik M ^ {\ rho} \ lewo (\ suma _ {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}\right)^{\rho }}$

dla każdego ${\ Displaystyle 0 <\ rho <1}$ . Uśredniając wszystkie kombinacje ${\ Displaystyle x_ {1} ^ {n}, y_ {1} ^ {n}}$ :

${\ Displaystyle P _ {\ operatorname {błąd} \ 1 \ do \ operatorname {dowolny}} \ równoważnik M ^ {\ rho} \ suma _ {y_ {1} ^ {n}} \ lewo (\ suma _ {x_ { 1}^{n}}Q(x_{1}^{n})[p(y_{1}^{n}\mid x_{1}^{n})]^{1-s\rho }\ prawo)\lewo(\suma _{x_{2}^{n}}Q(x_{2}^{n})[p(y_{1}^{n}\mid x_{2}^{n} )]^{s}\right)^{\rho}.}$

Wybierając i łącząc dwie sumy w powyższym wzorze: $Displaystyle s = 1-$$s \ rho$

${\ Displaystyle P _ {\ operatorname {błąd} \ 1 \ do \ operatorname {dowolny}} \ równoważnik M ^ {\ rho} \ suma _ {y_ {1} ^ {n}} \ lewo (\ suma _ {x_ { 1}^{n}}Q(x_{1}^{n})[p(y_{1}^{n}\mid x_{1}^{n})]^{\frac {1}{1 +\rho }}\right)^{1+\rho }.}$

Wykorzystując niezależny charakter elementów słowa kodowego i dyskretny, pozbawiony pamięci charakter kanału:

${\ Displaystyle P _ {\ operatorname {błąd} \ 1 \ do \ operatorname {dowolny}} \ równoważnik M ^ {\ rho} \ prod _ {i = 1} ^ {n} \ suma _ {y_ {i}} \left(\sum _{x_{i}}Q_{i}(x_{i})[p_{i}(y_{i}\mid x_{i})]^{\frac {1}{1+ \rho }}\right)^{1+\rho }}$

Korzystając z faktu, że każdy element słowa kodowego jest identycznie rozłożony, a więc stacjonarny:

${\ Displaystyle P _ {\ operatorname {błąd} \ 1 \ do \ operatorname {dowolny}} \ równoważnik M ^ {\ rho} \ lewo (\ suma _ {y} \ lewo (\ suma _ {x} Q (x) [p(y\mid x)]^{\frac {1}{1+\rho }}\right)^{1+\rho }\right)^{n}.}$

Zastąpienie M przez 2 ^nR i zdefiniowanie

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

prawdopodobieństwo błędu staje się

${\ Displaystyle P _ {\ operatorname {błąd}} \ równoważnik \ exp (- n (E_ {o} (\ rho, Q) - \ rho R)).}$

Q i należy wybrać tak, aby granica była jak $.$ Zatem wykładnik błędu można zdefiniować jako

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

Wykładnik błędu w kodzie źródłowym

Dla niezmiennych w czasie źródeł dyskretnych bez pamięci

Twierdzenie o kodowaniu źródłowym stwierdza $,$ że ​​​​dla dowolnego $dyskretnym,$ takiego jak i dla dowolnej szybkości mniejszej niż entropia źródła, jest wystarczająco $}$$\$${\ Displaystyle n. (H (X) + \ varepsilon)}$$n$ i koder, który pobiera odwzorowuje je na bity binarne takie, że symbole źródłowe można odzyskać z pliku binarnego ${\ Displaystyle X ^ {1: n}}$ bity z prawdopodobieństwem co najmniej ${\ Displaystyle 1-\ varepsilon}$ .

Niech ${\ Displaystyle M = e ^ {nR} \, \!}$ będzie całkowitą liczbą możliwych komunikatów. Następnie odwzoruj każdą z możliwych źródłowych sekwencji wyjściowych na jeden z komunikatów losowo przy użyciu jednolitego rozkładu i niezależnie od wszystkiego innego. Po wygenerowaniu źródła odpowiedni komunikat $.$ do miejsca docelowego Wiadomość jest dekodowana do jednego z możliwych ciągów źródłowych. Aby zminimalizować prawdopodobieństwo błędu, dekoder zdekoduje do sekwencji źródłowej, $}$ maksymalizuje $)$$(X_ {1} } ^ {$$.$$m}}$ , gdzie oznacza zdarzenie, że wiadomość przesłana Ta reguła jest równoważna znalezieniu sekwencji źródłowej wśród zbioru sekwencji źródłowych, które odwzorowują wiadomość $\ displaystyle m$ która maksymalizuje $styl wyświetlania P(X_{1}^{n})}$$}$$m$ . Ta redukcja wynika z faktu, że wiadomości były przydzielane losowo i niezależnie od wszystkiego innego.

$Displaystyle$ jako przykład wystąpienia błędu, przyjęto, że sekwencja źródłowa została odwzorowana na wiadomość, podobnie jak $X_ {1} ^ {n} (1)}$ sekwencja źródłowa ${\ Displaystyle X_ {1} ^ {n} (2)}$ . X ${\ Displaystyle X_ {1} ^ {n} (1) \,}$ został wygenerowany u źródła, ${\ Displaystyle P (X_ {1} ^ {n} (2))> P (X_ {1} ^ {n} (1))}$ wtedy pojawia się błąd.

Niech $S_ {i} \,}$${ \$ , że sekwencja źródłowa że ${\ Displaystyle P (S_ {i}) = P (X_ {1} ^ {n} (i)) \,.}$ Wtedy prawdopodobieństwo błędu można podzielić jako ${\ Displaystyle P (E) = \ suma _ {i} P (E \ mid S_ {i}) P (S_ {i}) \,.} W związku z tym można skupić uwagę na znalezieniu górnej$ granicy ${\ Displaystyle P (E \ mid S_ {i}) \,}$ .

Niech ${\ Displaystyle A_ {i'} \,}$ oznacza zdarzenie, że sekwencja źródłowa została odwzorowana na tę samą ${\ Displaystyle X_ {1} ^ {n} (i')}$ wiadomość jako sekwencja źródłowa ${\ Displaystyle X_ {1} ^ {n} (i)}$ i że ${\ styl wyświetlania P(X_{1}^{n}(i'))\geq P(X_{1}^{n}(i))}$ . Tak więc, pozwalając ${\ Displaystyle X_ {i, i'} \,}$ na oznaczenie zdarzenia, na które odwzorowują dwie sekwencje źródłowe ${\ displaystyle i \,}$ i ja $\ displaystyle i' \,}$ ta sama wiadomość, mamy to

${\ Displaystyle P (A_ {i'}) = P \ left(X_{i,i'}\bigcap P(X_{1}^{n}(i')\right)\geq P(X_{1}^{n}(i)))\,}$

i wykorzystując fakt, że ${\ Displaystyle P (X_ {i, i'}) = {\ Frac {1} {M}} \$ } To

${\ Displaystyle P (A_ {i'}) = {\ Frac {1} {M}} P (P (X_ {1} ^ {n} (i')) \ geq P (X_ {1} ^ {n }(I)))\,.}$

Prostą górną granicę terminu po lewej stronie można ustalić jako

${\ styl wyświetlania \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))}}\right)^{s}\,}$

dla dowolnej liczby rzeczywistej ${\ Displaystyle s> 0 \,.}$ Tę górną granicę można zweryfikować, zauważając, że ${\ Displaystyle P (P (X_ {1} ^ {n} (i')}> P (X_ {1} ^ {n} (i)}) \,}$ równa się ${\ Displaystyle 1 \,}$ lub ${\ Displaystyle 0 \,},$ ponieważ prawdopodobieństwa danej sekwencji wejściowej są całkowicie deterministyczne. Tak więc, jeśli ${\ Displaystyle P (X_ {1} ^ {n} (i ')) \ geq P (X_ {1} ^ {n} (i)} \,,}$ wtedy ${\ Displaystyle {\ Frac {P (X_ {1} ^ {n }(i'))}{P(X_{1}^{n}(i))}}\geq 1\,}$ tak, aby w tym przypadku nierówność była spełniona. Nierówność zachodzi również w drugim przypadku, ponieważ

${\ Displaystyle \ lewo ({\ Frac {P (X_ {1} ^ {n} (i'))} P(X_{1}^{n}(i))}}\right)^{s}\geq 0\,}$

dla wszystkich możliwych ciągów źródłowych. $łącząc$ wszystko i wprowadzając to

${\ Displaystyle P (E \ mid S_ {i}) \ równoważnik P (\ bigcup _ {i \ neq i'} A_ {i'}) \ równoważnik \ lewo (\ suma _ {i \ neq i'} P ( A_{i'})\right)^{\rho }\leq \left({\frac {1}{M}}\sum _{i\neq i'}\left({\frac {P(X_{ 1}^{n}(i'))}{P(X_{1}^{n}(i))}}\right)^{s}\right)^{\rho }\,.}$

Gdzie nierówności wynikają z wariacji na temat Union Bound. Na koniec stosując tę ​​górną granicę do sumowania dla ${\ Displaystyle P (E) \,$ }

${\ Displaystyle P (E) = \ suma _ {i} P (E \ mid S_ {i}) P (S_ {i}) \ równoważnik \ suma _ {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}\,.}$

Gdzie suma może być teraz przejęta przez wszystkich $ponieważ$ to tylko zwiększy granicę Ostatecznie to daje

${\ Displaystyle P (E) \ równoważnik {\ Frac {1} {M ^ {\ rho}}} \ suma _ {i} P (X_ {1} ^ {n} (i)) ^ {1-s \ rho }\left(\suma _{i'}P(X_{1}^{n}(i'))^{s}\right)^{\rho }\,.}$

Teraz dla uproszczenia niech ${\ Displaystyle 1-s \ rho = s \,}$ tak, że ${\ Displaystyle s = {\ Frac {1} {1 + \ rho}} \,.}$ Podstawiając tę ​​nową wartość ${\ Displaystyle s \,}$ do powyższej granicy prawdopodobieństwa błędu i wykorzystując fakt, że ${\ Displaystyle i' \,}$ jest tylko zmienną fikcyjną w sumie, co daje następujące górne ograniczenie prawdopodobieństwa błędu:

${\ Displaystyle P (E) \ równoważnik {\ Frac {1} {M ^ {\ rho}}} \ lewo (\ suma _ {i} P (X_ {1} ^ {n} (i)) ^ {\ frac {1} {1+ \ rho}} \ prawo) ^ {1+ \ rho} \,.}$

${\ Displaystyle M = e ^ {nR} \, \!$ } z ${\ Displaystyle X_ {1} ^ {n} (i) \,}$ są niezależne. Zatem upraszczając powyższe równanie otrzymujemy

${\ Displaystyle P (E) \ równoważnik \ exp \ lewo (-n \ lewo [\ rho R- \ ln \ lewo (\ suma _ {x_ {i}} P (x_ {i}) ^ {\ Frac {1 }{1+\rho }}\right)(1+\rho )\right]\right).}$

Termin w wykładniku powinien być maksymalizowany w $celu$ najwyższej górnej granicy prawdopodobieństwa błędu.

Pozwalając ${\ Displaystyle E_ {0} (\ rho) = \ ln \ lewo (\ suma _ {x_ {i}}P(x_{i})^{\frac {1}{1+\rho }}\right)(1+\rho )\,,}$ zobacz, że wykładnik błędu dla przypadku kodu źródłowego to:

${\ Displaystyle E_ {r} (R) = \ max _ {\ rho \ w [0,1]} \ lewo [\ rho R-E_ {0} (\ rho) \ prawo]. \,}$

Zobacz też

• Kodowanie źródłowe
• Kodowanie kanałów

R. Gallager, Teoria informacji i niezawodna komunikacja , Wiley 1968