Wykładnik błędu - Error exponent

W teorii informacji The wykładnik błędu z kodu kanału i kodu źródłowego na długości bloku kodu jest szybkość, z którą rozkłada się prawdopodobieństwo błędu wykładniczo z długością bloku kodu. Formalnie definiuje się go jako ograniczający stosunek ujemnego logarytmu prawdopodobieństwa błędu do długości bloku kodu dla dużych długości bloków. Na przykład, jeśli prawdopodobieństwo błędu z dekodera jak krople , gdzie jest długością bloku, wykładnik błędu . W tym przykładzie podejścia do dużych plików . Wiele twierdzeń teorii informacji ma charakter asymptotyczny, na przykład twierdzenie o kodowaniu kanału stwierdza, że ​​dla dowolnej szybkości mniejszej niż pojemność kanału prawdopodobieństwo błędu kodu kanału można doprowadzić do zera jako długości bloku idzie w nieskończoność. W praktycznych sytuacjach istnieją ograniczenia dotyczące opóźnienia komunikacji, a długość bloku musi być ograniczona. Dlatego ważne jest, aby zbadać, jak spada prawdopodobieństwo błędu, gdy długość bloku osiąga nieskończoność. ${\ displaystyle P _ {\ mathrm {błąd}}}$${\ Displaystyle e ^ {- n \ alfa}}$${\ displaystyle n}$${\ displaystyle \ alpha}$${\ Displaystyle {\ Frac {- \ ln P _ {\ mathrm {błąd}}} {n}}}$${\ displaystyle \ alpha}$${\ displaystyle n}$

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

Dla niezmiennych w czasie DMC

Kodowanie kanału twierdzenie stwierdza, że dla każdego ε> 0 i dla każdej szybkości mniejszej niż pojemność kanału nie jest system kodowania i dekodowania, który może być stosowany w celu zapewnienia, że prawdopodobieństwo błędu bloku wynosiła poniżej ε> 0 wystarczająco długi komunikat blok X . Ponadto, dla dowolnej szybkości większej niż pojemność kanału, prawdopodobieństwo błędu bloku w odbiorniku spada do jedności, gdy długość bloku zbliża się do nieskończoności.

Zakładając następującą konfigurację kodowania kanału: kanał może przesyłać dowolne wiadomości, transmitując odpowiednie słowo kodowe (o długości n ). Każdego składnika w słowniku uwagę IID według pewnego rozkładu prawdopodobieństwa z funkcją masy prawdopodobieństwa P . Na końcu dekodowania wykonywane jest dekodowanie z maksymalnym prawdopodobieństwem. ${\ Displaystyle M = 2 ^ {nR} \;}$

Niech będzie tym losowym słowem kodowym w książce kodów, gdzie przechodzi od do . Załóżmy, że wybrano pierwszą wiadomość, więc słowo kodowe jest przesyłane. Biorąc pod uwagę, że zostało odebrane, prawdopodobieństwo, że słowo kodowe zostało nieprawidłowo wykryte, jak jest: ${\ Displaystyle X_ {i} ^ {n}}$${\ displaystyle i}$${\ displaystyle i}$${\ displaystyle 1}$${\ displaystyle M}$${\ Displaystyle X_ {1} ^ {n}}$${\ Displaystyle y_ {1} ^ {n}}$${\ Displaystyle X_ {2} ^ {n}}$

${\ displaystyle P _ {\ mathrm {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})).}$

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

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

w ten sposób ${\ Displaystyle s> 0 \;}$

${\ Displaystyle P _ {\ mathrm {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 pomylenia z jakąkolwiek inną wiadomością jest razy większe niż powyższe wyrażenie. Korzystając ze związku związanego, prawdopodobieństwo pomylenia z jakąkolwiek wiadomością jest ograniczone przez: ${\ Displaystyle X_ {1} ^ {n}}$${\ displaystyle M}$${\ Displaystyle X_ {1} ^ {n}}$

${\ displaystyle P _ {\ mathrm {błąd} \ 1 \ to \ mathrm {any}} \ leq 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 . Uśrednianie ze wszystkich kombinacji : ${\ displaystyle 0 <\ rho <1}$${\ Displaystyle x_ {1} ^ {n}, y_ {1} ^ {n}}$

${\ displaystyle P _ {\ mathrm {błąd} \ 1 \ to \ mathrm {any}} \ 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} \ po prawej) \ left (\ sum _ {x_ {2} ^ {n}} Q (x_ {2} ^ {n}) [p (y_ {1} ^ {n} \ mid x_ {2} ^ {n}) )] ^ {s} \ right) ^ {\ rho}.}$

Wybór i połączenie dwóch sum w powyższym wzorze: ${\ displaystyle s = 1-s \ rho}$${\ displaystyle x_ {1} ^ {n}}$

${\ Displaystyle P _ {\ mathrm {błąd} \ 1 \ to \ mathrm {any}} \ 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żność elementów słowa kodowego i dyskretną, pozbawioną pamięci naturę kanału:

${\ displaystyle P _ {\ mathrm {błąd} \ 1 \ to \ mathrm {any}} \ leq 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}}$

Wykorzystując fakt, że każdy element słowa kodowego jest identycznie rozłożony, a zatem stacjonarny:

${\ Displaystyle P _ {\ mathrm {błąd} \ 1 \ do \ mathrm {any}} \ 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 \ lewo (\ suma _ {y} \ lewo (\ suma _ {x} Q (x) [p (y \ mid x)] ^ { 1 / (1+ \ rho)} \ right) ^ {1+ \ rho} \ right),}$

prawdopodobieństwo błędu

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

Q i powinien być tak dobrany, aby wiązanie było najtrudniejsze. W ten sposób wykładnik błędu można zdefiniować jako ${\ displaystyle \ rho}$

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

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

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

Źródło kodowania twierdzenie stwierdza, że dla każdego i dowolnego źródła IID dyskretnym w czasie, takie jak i dla każdej stawki niższej niż entropia źródła, nie jest wystarczająco duży i koder, który zajmuje IID powtórzenia źródła, i mapuje je do pliku binarnego bity takie, że symbole źródłowe można odzyskać z bitów binarnych co najmniej z prawdopodobieństwem . ${\ displaystyle \ varepsilon> 0}$${\ displaystyle X}$${\ displaystyle n}$${\ displaystyle n}$${\ Displaystyle X ^ {1: n}}$${\ Displaystyle n. (H (X) + \ varepsilon)}$${\ Displaystyle X ^ {1: n}}$${\ displaystyle 1- \ varepsilon}$

Niech będzie całkowita liczba możliwych wiadomości. Następnie mapuj każdą z możliwych sekwencji wyjściowych źródła do jednej z wiadomości, losowo używając jednolitej dystrybucji i niezależnie od wszystkiego innego. Gdy generowane jest źródło, odpowiedni komunikat jest następnie przesyłany do miejsca docelowego. Wiadomość zostaje zdekodowana do jednego z możliwych łańcuchów źródłowych. W celu zminimalizowania prawdopodobieństwa błędu dekoder dekoduje do sekwencji źródłowej, która maksymalizuje , gdzie oznacza zdarzenie, w którym wiadomość została przesłana. Ta reguła jest równoważna ze znalezieniem sekwencji źródłowej w zestawie sekwencji źródłowych, które są odwzorowywane na komunikat, który maksymalizuje . Ta redukcja wynika z faktu, że wiadomości były przydzielane losowo i niezależnie od wszystkiego innego. ${\ Displaystyle M = e ^ {nR} \, \!}$${\ Displaystyle M = m \,}$${\ Displaystyle X_ {1} ^ {n}}$${\ Displaystyle P (X_ {1} ^ {n} \ środkowy A_ {m.})}$${\ Displaystyle A_ {m.} \,}$${\ displaystyle m}$${\ Displaystyle X_ {1} ^ {n}}$${\ displaystyle m}$${\ Displaystyle P (X_ {1} ^ {n})}$

Tak więc, jako przykład wystąpienia błędu, założono, że sekwencja źródłowa została odwzorowana na komunikat, podobnie jak sekwencja źródłowa . Jeśli został wygenerowany u źródła, ale pojawia się błąd. ${\ Displaystyle X_ {1} ^ {n} (1)}$${\ displaystyle 1}$${\ Displaystyle X_ {1} ^ {n} (2)}$${\ Displaystyle X_ {1} ^ {n} (1) \,}$${\ Displaystyle P (X_ {1} ^ {n} (2))> P (X_ {1} ^ {n} (1))}$

Niech oznaczają zdarzenia, że ciąg źródłowy został wygenerowany u źródła, tak że to prawdopodobieństwo błędu może być rozłożona w ten sposób, można skupić uwagę na znalezieniu górną granicę do . ${\ Displaystyle S_ {i} \,}$${\ Displaystyle X_ {1} ^ {n} (i)}$${\ Displaystyle P (S_ {i}) = P (X_ {1} ^ {n} (i)) \ ,.}$${\ Displaystyle P (E) = \ suma _ {i} P (E \ środek S_ {i}) P (S_ {i}) \ ,.}$${\ displaystyle P (E \ mid S_ {i}) \,}$

Niech oznaczają zdarzenia, że sekwencja źródło zostało odwzorowane do tej samej wiadomości jako sekwencji źródłowej i że . Tak więc, pozwalając oznaczyć zdarzenie, że dwie sekwencje źródłowe i mapowanie na tę samą wiadomość, mamy to ${\ displaystyle A_ {i '} \,}$${\ Displaystyle X_ {1} ^ {n} (i ')}$${\ Displaystyle X_ {1} ^ {n} (i)}$${\ Displaystyle P (X_ {1} ^ {n} (i ')) \ geq P (X_ {1} ^ {n} (i))}$${\ displaystyle X_ {i, i '} \,}$${\ Displaystyle i \,}$${\ Displaystyle i '\,}$

${\ Displaystyle P (A_ {i '}) = P \ lewo (X_ {i, ja'} \ bigcap P (X_ {1} ^ {n} (i ') \ prawej) \ geq P (X_ {1} ^ {n} (i))) \,}$

i wykorzystując fakt, że i jest niezależny od wszystkiego innego, ma to ${\ Displaystyle P (X_ {i, i '}) = {\ Frac {1} {M}} \,}$

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

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

${\ Displaystyle \ lewo [P (P (X_ {1} ^ {n} (i ')) \ geq P (X_ {1} ^ {n} (i))) \ prawo] \ równoważnik \ lewo ({\ frac {P (X_ {1} ^ {n} (i '))} {P (X_ {1} ^ {n} (i))}} \ right) ^ {s} \,}$

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

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

dla wszystkich możliwych ciągów źródłowych. Tak więc, łącząc wszystko i wprowadzając kilka , masz to ${\ displaystyle \ rho \ in [0,1] \,}$

${\ 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ą ze zmiany Związku Związkowego. Wreszcie, stosując tę ​​górną granicę do sumowania, mamy to: ${\ Displaystyle P (E) \,}$

${\ Displaystyle P (E) = \ suma _ {i} P (E \ środek 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 sumę można teraz przejąć, ponieważ to tylko zwiększy granicę. Ostatecznie to daje ${\ Displaystyle i '\,}$

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

Teraz dla uproszczenia pozwólmy , że podstawienie tej nowej wartości do powyższej, związanej z prawdopodobieństwem błędu i użycie faktu, że jest to po prostu zmienna fikcyjna w sumie, daje następującą granicę prawdopodobieństwa błędu: ${\ Displaystyle 1-s \ rho = s \,}$${\ displaystyle s = {\ Frac {1} {1+ \ rho}} \ ,.$${\ Displaystyle s \,}$${\ Displaystyle i '\,}$

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

${\ Displaystyle M = e ^ {nR} \, \!}$a każdy ze składników jest niezależny. Zatem uproszczenie powyższego równania daje${\ Displaystyle X_ {1} ^ {n} (i) \,}$

${\ 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).}$

Składnik w wykładniku powinien być maksymalizowany , aby osiągnąć najwyższą górną granicę prawdopodobieństwa błędu. ${\ displaystyle \ rho \,}$

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

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

Zobacz też

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

Bibliografia

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