Binarny kanał symetryczny

Binarny kanał symetryczny (lub BSC _p ) to powszechny model kanału komunikacyjnego używany w teorii kodowania i teorii informacji . W tym modelu nadajnik chce wysłać bit (zero lub jedynkę), a odbiornik otrzyma bit. Bit zostanie „odwrócony” z „ prawdopodobieństwem przecięcia ” równym p , a poza tym zostanie odebrany poprawnie. Model ten można zastosować do różnych kanałów komunikacyjnych, takich jak linie telefoniczne czy masowa na dyskach .

Twierdzenie o kodowaniu kanałów z szumem stosuje się do BSC _p , mówiąc, że informacje mogą być przesyłane z dowolną szybkością aż do pojemności kanału z dowolnie niskim błędem. Pojemność kanału wynosi ${\ Displaystyle 1- \ nazwa operatora {H} _ {\ tekst {b}} (p)}$ bitów, gdzie ${\ Displaystyle \ nazwa operatora {H} _ {\ text{b}}}$ to binarna funkcja entropii . Kody, w tym kod Forneya, zostały zaprojektowane w celu wydajnego przesyłania informacji w kanale.

Definicja

Binarny kanał symetryczny widzi każdy bit wiadomości przesłanej poprawnie z prawdopodobieństwem 1– p i niepoprawnie z prawdopodobieństwem p , z powodu szumu w medium transmisyjnym.

Binarny kanał symetryczny z prawdopodobieństwem przecięcia $oznaczony$ przez BSC _p , to kanał z wejściem binarnym i wyjściem binarnym oraz prawdopodobieństwem błędu ${\ displaystyle p}$ . Oznacza to, że jeśli jest przesyłaną zmienną losową , a odbieraną zmienną, to kanał charakteryzuje się prawdopodobieństwami warunkowymi : $\ displaystyle$$X}$

${\ Displaystyle {\ rozpocząć {wyrównane} \ nazwa operatora {Pr} [Y = 0 | X = 0] i = 1-p \\\ nazwa operatora {Pr} [Y = 0 | X = 1]&=p\\\nazwa_operatora {Pr} [Y=1|X=0]&=p\\\nazwa_operatora {Pr} [Y=1|X=1]&=1-p\end{wyrównane} }}$

Zakłada się, że ${\ Displaystyle 0 \ równoważnik p \ równoważnik 1/2}$ . Jeśli , $przejścia$${\ Displaystyle 1-p \ równoważnik 1/2}$ 0 i odwrotnie) i uzyskać równoważny kanał z .

Pojemność

Pojemność kanału binarnego kanału symetrycznego w bitach wynosi:

${\ Displaystyle \ C _ {\ tekst {BSC}} = 1 - \ nazwa operatora {H} _ {\ tekst {b}} (p),}$

gdzie ${\ Displaystyle \ nazwa operatora {H} _ {\ tekst {b}} (p)}$ jest binarną funkcją entropii , zdefiniowaną przez:

${\ Displaystyle \ operatorname {H} _ {\ tekst {b}} (x) = x \ log _ {2}{\frac {1}{x}}+(1-x)\log _{2}{\frac {1}{1-x}}}$

Dowód

Pojemność jest definiowana jako maksymalna wzajemna informacja między wejściem a wyjściem dla wszystkich możliwych rozkładów wejściowych ${\ Displaystyle p_ {X} (x)}$ : ${\ Displaystyle C = \ max _ {p_ {X} (x)} \ lewo \ {\, ja (X; Y) \, \ prawo \}}$ Wzajemne informacje można przeformułować jako ${\ Displaystyle {\ rozpocząć {wyrównane} I (X; Y) & = H ( Y)-H(Y|X)\\&=H(Y)-\suma _{x\in \{0,1\}}{p_{X}(x)H(Y|X=x)} \\&=H(Y)-\suma _{x\in \{0,1\}}{p_{X}(x)}\nazwa_operatora {H} _{\text{b}}(p)\ \&=H(Y)-\nazwa operatora {H} _{\text{b}}(p),\end{wyrównane}}}$ gdzie pierwszy i drugi krok wynika odpowiednio z definicji informacji wzajemnej i entropii warunkowej . Entropia na wyjściu dla danego i ustalonego symbolu wejściowego ( $jest$ do trzeciego wiersza i dalsze uproszczenie. W ostatnim wierszu tylko pierwszy termin zależy od rozkładu danych wejściowych. ${\ Displaystyle p_ {X$$)$ . Entropia zmiennej binarnej wynosi co najwyżej 1 bit, a równość jest osiągana, jeśli jej rozkład prawdopodobieństwa jest jednolity. Dlatego wystarczy przedstawić rozkład wejściowy, który daje jednolity rozkład prawdopodobieństwa dla wyniku. Y $\ displaystyle Y}$ W tym celu należy zauważyć, że właściwością dowolnego binarnego kanału symetrycznego jest to, że jednolity rozkład prawdopodobieństwa wejścia skutkuje jednolitym rozkładem prawdopodobieństwa wyjścia. Stąd wartość $x)$${$ { . Do ${\ Displaystyle C _ {\ tekst {BSC}} = 1- \ nazwa operatora {H} _ {\ tekst {b}$ .

Twierdzenie o kodowaniu kanałów szumowych

Shannona o hałaśliwym kanale kodowania daje wynik dotyczący szybkości informacji, które mogą być przesyłane kanałem komunikacyjnym z dowolnie niskim błędem. Badamy szczególny przypadek ${\ displaystyle {\ text {BSC}} _ ​​{p}}$ .

Szum , który charakteryzuje $jest$ zmienną $to$ z n niezależnych losowych bitów (n jest zdefiniowane poniżej), gdzie każdy losowy ${\ Displaystyle 1}$ z prawdopodobieństwem $\$ za { $Displaystyle 0}$ z prawdopodobieństwem ${\ Displaystyle 1-p}$ . Wskazujemy to, pisząc „ ${\ displaystyle e \ in {\ tekst {BSC}} _ ​​{p}}$ ”.

Twierdzenie - Dla wszystkich ${\ Displaystyle p <{\ tfrac {1} {2}}}$ wszystkie ${\ Displaystyle 0 <\ epsilon <{\ tfrac {1} {2} }} -p}$$duże$ wszystkie wystarczająco $-$ w ${\ Displaystyle k \ leq \ lfloor (1-H (p + \ epsilon)) n \ rfloor}$$)$ i wszystkie , istnieje para funkcji kodowania i dekodowania ${\ displaystyle E : \ {0,1 \} ^ {k} \ do \ {0,1 \} ^ {n}}$ i ${\ Displaystyle D: \ {0,1 \} ^ {n} \ do \ {0,1 \} ^ {k}}$ odpowiednio, tak że każda wiadomość ${\ Displaystyle m \ in \ {0,1 \} ^ {k} }$ ma następującą właściwość:

${\ Displaystyle \ Pr _ {e \ w {\ tekst {BSC}} _ ​​{p}} [D (E ( m)+e)\neq m]\równik 2^{-{\delta}n}}$ .

$to twierdzenie,$$to$ wiadomość wybrana z pomocą losowej funkcji kodowania wysłana hałaśliwy $lub w efekcie szybkość kanału jest$ , istnieje bardzo duże prawdopodobieństwo odzyskania oryginalnej wiadomości przez dekodowanie, jeśli ${\ displaystyle k}$ lub w efekcie szybkość kanału jest ograniczona przez wielkość określoną w twierdzeniu. Prawdopodobieństwo błędu dekodowania jest wykładniczo małe.

Dowód

Twierdzenie można dowieść bezpośrednio metodą probabilistyczną . Rozważ wybraną funkcję kodowania ${\ Displaystyle E: \ {0,1 \} ^ {k} \ do \ {0,1 \} ^ {n}}$ losowo. $wiadomości$ to, że dla wartość $)\in \{0,1\}^{n}}$${$ jest wybierany losowo (z równym prawdopodobieństwem). Dla danej funkcji kodowania mi ${\ Displaystyle E}$ dekodowania ${\ Displaystyle D: \ {0,1 \} ^ {n} \ do \ {0, 1 \} ^ {k}}$$otrzymane$ w następujący sposób: biorąc pod uwagę ${\ Displaystyle m \ in \ {0,1 \} ^ {k}}$ , takie, że odległość Hamminga ${\ Displaystyle \ Delta (y, E (m))}$ jest tak mały, jak to możliwe (z arbitralnie zerwanymi krawatami). ( $nazywana$ funkcją dekodowania największej wiarygodności ).

$,$ że co najmniej jeden taki wybór wniosek twierdzenia poprzez Załóżmy $,$ i $są$ . Najpierw pokazujemy, że dla ustalonego wybranego prawdopodobieństwa niepowodzenia przez ${\ displaystyle {\ text {BSC}} _ ​​{p}}$$}$$}$ szum jest wykładniczo mały w n . W tym momencie dowód działa dla ustalonej wiadomości ${\ displaystyle m}$ . Następnie rozszerzamy ten wynik, aby działał dla wszystkich wiadomości ${\ displaystyle m}$ . Osiągamy to poprzez wyeliminowanie połowy słów kodowych z kodu z argumentem, że dowód na prawdopodobieństwo błędu dekodowania zachodzi dla co najmniej połowy słów kodowych. Ta ostatnia metoda nazywa się oczyszczeniem. Daje to całemu procesowi nazwę losowego kodowania z usuwaniem .

Kontynuacja dowodu (szkic)

Napraw ${\ displaystyle p}$ i ${\ displaystyle \ epsilon}$ . Biorąc $pod uwagę$ , musimy oszacować oczekiwaną wartość wraz z szumem oddać na dekodowanie ${\ displaystyle m} .$ Oznacza to, że musimy oszacować: ${\ Displaystyle \ mathbb {E} _ {E} \ lewo [\ Pr _ {e \ w {\ tekst {BSC}} _ ​​{p}} [D (E (m) + e) ​​\ neq m] \ prawo ].}$ Niech będzie $słowem$ kodowym. Aby zdekodowane słowo kodowe nie było równe wiadomości $Displaystyle$ musi wystąpić jedno z następujących zdarzeń: $D (y)}$ ${\ Displaystyle y}$ nie leży w kuli Hamminga o promieniu ${\ Displaystyle (p + \ epsilon) n}$ wyśrodkowanym w ${\ Displaystyle E (m)}$ . Ten warunek jest używany głównie w celu ułatwienia obliczeń. Jest ${\ Displaystyle \ Delta (y, E (m')) \ leqslant \ Delta (y, E (m))}$ że $)$ . Innymi słowy, błędy spowodowane szumem zbliżają przesyłane słowo kodowe do innej zakodowanej wiadomości. Możemy zastosować wiązanie Chernoffa , aby zapewnić brak wystąpienia pierwszego zdarzenia; otrzymujemy: ${\ Displaystyle Pr _ {e \ w {\ tekst {BSC}} _ ​​{p}} [\ Delta (y, E (m))> (p + \ epsilon) n] \ leqslant 2 ^ {- {\ epsilon ^ { 2}}n}.}$ Jest to wykładniczo małe dla dużych $($ , że $stałe$ ). W przypadku drugiego zdarzenia zauważamy, że prawdopodobieństwo, że ${\ Displaystyle E (m ') \ w B (y, (p + \ epsilon) n)}$ jest ${\ Displaystyle {\ tekst {tom}} (B (y, (p + \ epsilon) n) / 2 ^ {n}}$ gdzie ${\ Displaystyle B (x, r)}$ to kula Hamminga o promieniu ${\ displaystyle r}$ wyśrodkowana na wektorze ${\ displaystyle x}$ i ${\ Displaystyle {\ tekst {Vol}}(B(x,r))}$ to jego objętość. Wykorzystując przybliżenie do oszacowania liczby słów kodowych w kuli Hamminga, mamy ${\ Displaystyle {\ tekst {tom}} (B (y, (p + \ epsilon) n)} \ około 2 ^ {H (p) n}} . Stąd powyższe prawdopodobieństwo$ wynosi ${\ Displaystyle 2 ^ {H (p) n} / 2 ^ {n} = 2 ^ {H (p) nn}}.$ Teraz używając związku związkowego , my może górna granica istnienia takiego ${\ Displaystyle m'\ in \ {0,1 \} ^ {k}}$ przez ${\ Displaystyle \leq 2 ^ {k + H (p) nn}}$ , czyli ${\ Displaystyle 2 ^ {- \ Omega (n)}}$ , zgodnie z życzeniem przez wybór ${\ displaystyle k}$ .

Kontynuacja dowodu (szczegóły)

Na podstawie powyższej analizy obliczamy prawdopodobieństwo zdarzenia, w którym zdekodowane słowo kodowe plus szum kanału nie jest tożsame z oryginalną wysłaną wiadomością. Wprowadzimy tutaj kilka symboli. Niech ${\ Displaystyle p (y | E (m)}}$ oznacza prawdopodobieństwo otrzymania słowa kodowego ${\ Displaystyle y}$ , biorąc pod uwagę to słowo kodowe ${\ Displaystyle E (m)}$ został wysłany. Niech ${\ displaystyle B_ {0}}$ oznacza ${\ Displaystyle B (E (m), (p + \ epsilon) n).}$ ${\ Displaystyle {\ rozpocząć {wyrównane} \ Pr _ {e \ w {\text{BSC}}_{p}}[D(E(m)+e)\neq m]&=\suma _{y\in \{0,1\}^{n}}p( y|E(m))\cdot 1_{D(y)\neq m}\\&\leqslant \sum _{y\notin B_{0}}p(y|E(m))\cdot 1_{D (y)\neq m}+\suma _{y\in B_{0}}p(y|E(m))\cdot 1_{D(y)\neq m}\\&\leqslant 2^{- {\epsilon ^{2}}n}+\sum _{y\w B_{0}}p(y|E(m))\cdot 1_{D(y)\neq m}\end{wyrównane}} }$ Ostatnią nierówność otrzymujemy z naszej analizy przy użyciu powyższej granicy Chernoffa . Teraz biorąc pod uwagę oczekiwania po obu stronach mamy, ${\ Displaystyle {\ rozpocząć {wyrównane} \ mathbb {E} _{E}\left[\Pr _{e\in {\text{BSC}}_{p}}[D(E(m)+e)\neq m]\right]&\leqslant 2 ^{-{\epsilon ^{2}}n}+\suma _{y\in B_{0}}p(y|E(m))\mathbb {E} [1_{D(y)\neq m }]\\&\leqslant 2^{-{\epsilon ^{2}}n}+\sum _{y\in B_{0}}\mathbb {E} [1_{D(y)\neq m} ]&&\suma _{y\in B_{0}}p(y|E(m))\leqslant 1\\&\leqslant 2^{-{\epsilon ^{2}}n}+2^{k +H(p+\epsilon )nn}&&\mathbb {E} [1_{D(y)\neq m}]\leqslant 2^{k+H(p+\epsilon )nn}{\text{ (patrz wyżej) }}\\&\leqslant 2^{-\delta n}\end{wyrównane}}}$ odpowiednio wybierając wartość . ${\ displaystyle \ delta}$ . Ponieważ powyższa granica obowiązuje dla każdej wiadomości, mamy ${\ Displaystyle \ mathbb {E} _ {m} \ lewo [\ mathbb {E} _ {E} \ lewo [\ Pr _ {e \ w {\ tekst {BSC}} _ ​​{p}} \ lewo [D (E(m)+e)\right]\neq m\right]\right]\leqslant 2^{-\delta n}.}$ $w oczekiwaniu w odniesieniu do$ i wyboru funkcji kodowania . Stąd: ${\ Displaystyle \ mathbb {E} _ {E} \ lewo [\ mathbb {E} _ {m} \ lewo [\ Pr _ {e \ w {\ tekst {BSC}} _ ​​{p}} \ lewo [D (E(m)+e)\right]\neq m\right]\right]\leqslant 2^{-\delta n}.}$ Podsumowując, metodą probabilistyczną mamy pewną funkcję kodowania $E ^$ odpowiednią funkcję dekodowania taką, że ${*}}$ ${\ Displaystyle \ mathbb {E} _ {m} \ lewo [\ Pr _ {e \ w {\ tekst {BSC}} _ ​​{p}} \ lewo [D ^ {*} (E ^ {*} (m )+e)\neq m\right]\right]\leqslant 2^{-\delta n}.}$ W tym momencie dowód działa dla ustalonej wiadomości ${\ displaystyle m}$ . $dla$ musimy się upewnić, że powyższa granica obowiązuje wszystkich wiadomości jednocześnie . W tym celu posortujmy $komunikaty$ według prawdopodobieństwa ich błędów Teraz, stosując nierówność Markowa , możemy pokazać $Displaystyle 2 ^$ pierwszych co najwyżej $1}}$ . $,$ aby potwierdzić, że powyższy warunek obowiązuje dla $z$ , moglibyśmy prostu odciąć ostatnie posortowanej kolejności. To zasadniczo daje nam inną funkcję kodowania $z$$- \ delta n+1}}$ dekodowania z prawdopodobieństwem błędu dekodowania co najwyżej $\ Displaystyle 2 ^$ z tą samą szybkością. Biorąc ${\ Displaystyle \ delta '}$ za równe ${\ Displaystyle \ delta - {\ tfrac {1} {n}}}$ związaliśmy prawdopodobieństwo błędu dekodowania z ${\ Displaystyle 2^{-\delta 'n}}$ . Ten proces oczyszczania kończy dowód.

Odwrotność twierdzenia Shannona o pojemności

Odwrotność twierdzenia o pojemności zasadniczo stwierdza, że $to$ szybkość, jaką można osiągnąć w Formalnie twierdzenie stwierdza:

Twierdzenie - Jeśli ${\ Displaystyle k}$${\ Displaystyle \ geq}$${\ Displaystyle \ lceil}$${\ Displaystyle (1-H (p + \ epsilon) n)}$${\ Displaystyle \ rceil}$ to następujące stwierdzenie jest prawdziwe dla każdej funkcji kodowania i dekodowania mi ${\ displaystyle E}$ { $\ Displaystyle \ {0,1 \} ^ {k}}$$​​{\ Displaystyle \ rightarrow }$${\ Displaystyle \ {0,1 \} ^ {n}}$ i re ${\ Displaystyle D}$ { $\ Displaystyle \ {0,1 \} ^ {n}}$$Pr$ odpowiednio: $BSC}} _ {p}}}$$\ Displaystyle$ [ re ${\ Displaystyle D (E (m) + e)}$$\ Displaystyle \ neq}$${\ Displaystyle m]}$${\ Displaystyle \ geq }$${\ Displaystyle {\ Frac {1} {2}}}$ .

Intuicja stojąca za dowodem wskazuje jednak, że liczba błędów szybko rośnie, gdy szybkość przekracza pojemność kanału. Chodzi $o$$to,$ że nadawca generuje wiadomości o wymiarze podczas gdy kanał wprowadza błędy transmisji Gdy pojemność kanału wynosi ${\ Displaystyle H (p)}$ , liczba błędów wynosi zazwyczaj ${\ Displaystyle 2 ^ {H (p + \ epsilon) n}}$ dla kod długości bloku ${\ displaystyle n}$ . Maksymalna liczba wiadomości to ${\ displaystyle 2 ^ {k}}$ . $możliwe$ strony wyjście kanału ma wartości. Jeśli istnieje jakiekolwiek zamieszanie między dowolnymi dwoma komunikatami, jest prawdopodobne, że ${\ Displaystyle 2 ^ {k} 2 ^ {H (p + \ epsilon) n} \ geq 2 ^ {n.}}$ . Stąd mielibyśmy ${\ Displaystyle k \ geq \ lceil (1-H (p + \ epsilon) n) \ rceil }$ , przypadek, którego chcielibyśmy uniknąć aby prawdopodobieństwo błędu dekodowania było wykładniczo małe.

Kody

Bardzo niedawno wykonano i nadal wykonuje się wiele pracy w celu zaprojektowania jawnych kodów korygujących błędy, aby osiągnąć możliwości kilku standardowych kanałów komunikacyjnych. Motywacją do projektowania takich kodów jest powiązanie szybkości kodu z ułamkiem błędów, które może poprawić.

Podejście stojące za projektowaniem kodów, które spełniają możliwości kanału ${\ displaystyle {\ text {BSC}}}$ lub binarnego kanału kasowania ${\ displaystyle {\ text {BEC}}}$ polegało na poprawieniu mniejszej liczby błędy z dużym prawdopodobieństwem i osiągnięcie jak najwyższego wskaźnika. Twierdzenie Shannona daje nam najlepszą stopę, jaką można osiągnąć przez $BSC$ nie daje nam wyobrażenia o żadnych wyraźnych kodach, które osiągają tę szybkość. W rzeczywistości takie kody są zwykle konstruowane tak, aby korygować tylko niewielką część błędów z dużym prawdopodobieństwem, ale osiągają bardzo dobry wskaźnik. Pierwszy taki kod został napisany przez George'a D. Forneya w 1966 roku. Kod jest kodem połączonym przez połączenie dwóch różnych rodzajów kodów.

kod Forneya

$_$ skonstruował kod kanału twierdzenie o kodowaniu dla ${\ displaystyle {\ tekst {BSC}} _ ​​{p}}$ . W swoim kodzie

• Kod zewnętrzny $kodem$ o długości bloku $\$ szybkości $}$$Displaystyle 1- {\ Frac {\ epsilon}$$k = O (\ log N$ nad polem i $k$ Displaystyle . Dodatkowo mamy algorytm dekodowania dla $\ displaystyle C _ {\ text {out}}},$$może$ poprawić do ułamka $displaystyle \ gamma}$ najgorsze błędy i działa w czasie ${\ displaystyle t _ {\ text {out}} (N)} .$
• Wewnętrzny kod $}}$${\ Displaystyle 1-H (p) - {\ Frac {\ epsilon} {2}}$$współczynnika$ jest kodem długości bloku $ϵ$ wymiaru i } Dodatkowo mamy algorytm dekodowania ${\ displaystyle D _ {\ tekst {w}}}$ dla ${\ displaystyle C _ {\ tekst {w}}}$ z prawdopodobieństwem błędu dekodowania co najwyżej ${\ displaystyle { \ frac {\ gamma} {2}}}$ przez ${\ Displaystyle {\ tekst {BSC}} _ ​​{p}}$ i działa w ${\ Displaystyle t _ {\ tekst {w}} (N )}$ czas.

W przypadku kodu zewnętrznego $myśl$ Reeda-Solomona byłby pierwszym kodem, który przyszedłby na Widzielibyśmy jednak, że konstrukcji takiego kodu nie można wykonać w czasie wielomianowym. $jest$ dlatego kod liniowy używany do .

$Dla$ kodu wewnętrznego $C w$ liniowy , $wyczerpująco$ przeszukując kod liniowy o długości bloku wymiarze którego szybkość $o$ pojemność hałaśliwym kodowaniu kanału.

Szybkość ${\ Displaystyle R (C^{*})=R(C_{\text{in}})\times R(C_{\text{out}})=(1-{\frac {\epsilon }{2}})(1 -H (p) - {\ Frac {\ epsilon} {2}}} \ geq 1-H (p) - \ epsilon},$ co prawie spełnia ${\ Displaystyle {\ tekst {BSC}} _ ​​{p} }$ pojemność. $ponadto$$,$ że kodowanie i dekodowanie można wykonać w czasie wielomianowym w odniesieniu W rzeczywistości kodowanie $($ czasu $O (N ^ {2})$ . $_ N ) = N ^ {O (1)}}$ algorytm tak długo, jak ${\ Displaystyle t _ {\ tekst {na zewnątrz}} (N) = N ^ {O (1)}}$ ; i ${\ Displaystyle t _ {\ tekst {w}} (k) = 2 ^ {O (k)}}$ .

Prawdopodobieństwo błędu dekodowania

Naturalnym algorytmem dekodowania dla jest: do $\ displaystyle C ^ {*}}$

• Załóżmy ${\ Displaystyle y_ {i} ^ {\ pierwsza} = D _ {\ tekst {w}} (y_ {i}), \ quad ja \ w (0,N)}$
• Wykonaj ${\ Displaystyle D _ {\ text {out}}}$ na ${\ Displaystyle y ^ {\ pierwsza} = (y_ {1} ^ {\ pierwsza} \ ldots y_{N}^{\pierwsza})}$

Zauważ, że każdy blok kodu dla ${\ displaystyle C _ {\ text {in}}}$ jest uważany za symbol ${\ displaystyle C _ {\ text {out}}}$ . Teraz, ponieważ prawdopodobieństwo błędu w dowolnym indeksie $_ {\ tekst {w}}}$ { $D$ wynosi co najwyżej ${\ Displaystyle {\ tfrac {\ gamma}} {2}}}$ a błędy w $Displaystyle$ niezależne, oczekiwana liczba błędów dla $D _ {\ tekst {w}}}$ wynosi co najwyżej ${\ displaystyle {\ tfrac {\ gamma N} {2}}}$ przez liniowość oczekiwań. Stosując teraz ograniczenie Chernoffa , mamy związane prawdopodobieństwo błędu większe niż występujące błędy mi $}}$$\ Displaystyle e ^ {\ Frac {- \ gamma N$ . Ponieważ kod zewnętrzny $błędy$ poprawić co najwyżej , jest to $Displaystyle C ^$ dekodowania $*} }$ . Wyrażone asymptotycznie, daje nam prawdopodobieństwo błędu ${\ Displaystyle 2 ^ {- \ Omega (\ gamma N)}}$ . Zatem osiągnięte prawdopodobieństwo błędu dekodowania $.$ hałaśliwym kanale kodowania

Podaliśmy ogólną technikę konstruowania $\ displaystyle C ^ {*}}$ . Aby uzyskać bardziej szczegółowe opisy ${\ displaystyle C _ {\ text {in}}}$ i ${\ displaystyle C _ {\ text {out}}},$ przeczytaj poniższe odniesienia. Ostatnio skonstruowano również kilka innych kodów dla osiągnięcia tych zdolności. LDPC zostały wzięte pod uwagę w tym celu ze względu na ich szybszy czas dekodowania.

Aplikacje

Binarny kanał symetryczny może modelować dysk używany do przechowywania pamięci: wejście kanału reprezentuje bit zapisywany na dysku, a wyjście odpowiada bitowi później odczytywanemu. Błąd może wynikać z odwrócenia magnetyzacji, szumu tła lub błędu głowicy piszącej. Inne obiekty, które może modelować binarny kanał symetryczny, obejmują telefoniczną lub radiową linię komunikacyjną lub podział komórki , z którego komórki potomne zawierają informacje DNA z ich komórki macierzystej.

Ten kanał jest często używany przez teoretyków, ponieważ jest jednym z najłatwiejszych do analizy kanałów z szumem . Wiele problemów w teorii komunikacji można zredukować do BSC. I odwrotnie, możliwość skutecznej transmisji przez BSC może dać początek rozwiązaniom dla bardziej skomplikowanych kanałów.

Zobacz też

• kanał Z

Notatki

•   Okładka, Thomas M.; Thomas, Joy A. (1991). Elementy teorii informacji . Hoboken, New Jersey: Wiley. ISBN 978-0-471-24195-9 .
• G. David Forney. Kody łączone . MIT Press, Cambridge, MA, 1966.
• Kurs Venkata Guruswamy'ego na temat [1] Kody korekcji błędów: konstrukcje i algorytmy], jesień 2006.
•   MacKay, David JC (2003). Teoria informacji, wnioskowanie i algorytmy uczenia się . Wydawnictwo Uniwersytetu Cambridge. ISBN 0-521-64298-1 .
• Kurs Atri Rudry na temat kodów korygujących błędy: kombinatoryka, algorytmy i aplikacje (jesień 2007), wykłady 9 , 10 , 29 i 30 .
• Kurs Madhu Sudan na temat algorytmicznego wprowadzenia do teorii kodowania (jesień 2001), wykład 1 i 2 .
• Matematyczna teoria komunikacji C. E Shannon, ACM SIGMOBILE Mobile Computing and Communications Review.
• Nowoczesna teoria kodowania autorstwa Toma Richardsona i Rudigera Urbanke., Cambridge University Press