Kanał kasowania binarnego - Binary erasure channel

Model kanału dla kanału binarnego wymazywania pokazujący odwzorowanie z wejścia kanału X na wyjście kanału Y (ze znanym symbolem wymazywania ? ). Prawdopodobieństwo usunięcia wynosi ${\ displaystyle p_ {e}}$

W teorii kodowania i teorii informacji , A binarny kanał wymazywania ( BEC ) stanowi kanał komunikacyjny modelu. Nadajnik wysyła bit (zero lub jedynkę), a odbiornik albo odbiera bit poprawnie, albo z pewnym prawdopodobieństwem otrzymuje wiadomość, że bit nie został odebrany („skasowany”). ${\ displaystyle P_ {e}}$

Definicja

Kanał binarny z prawdopodobieństwem wymazania to kanał z wejściem binarnym, wyjście trójskładnikowe i prawdopodobieństwo wymazania . To znaczy, niech będzie przekazywana zmienna losowa z alfabetem . Niech otrzymana zmienna będzie miała alfabet , gdzie jest symbolem wymazania. Następnie kanał charakteryzuje się prawdopodobieństwami warunkowymi : ${\ displaystyle P_ {e}}$${\ displaystyle P_ {e}}$${\ displaystyle X}$${\ displaystyle \ {0,1 \}}$${\ displaystyle Y}$${\ displaystyle \ {0,1, {\ text {e}} \}}$${\ displaystyle {\ text {e}}}$

${\ Displaystyle {\ rozpocząć {wyrównane} \ nazwa operatora {Pr} [Y = 0 | X = 0] & = 1-P_ {e} \\\ operatorname {Pr} [Y = 0 | X = 1] & = 0 \\\ nazwa operatora {Pr} [Y = 1 | X = 0] & = 0 \\\ nazwa operatora {Pr} [Y = 1 | X = 1] & = 1-P_ {e} \\\ nazwa operatora {Pr} [Y = e | X = 0] & = P_ {e} \\\ nazwa operatora {Pr} [Y = e | X = 1] & = P_ {e} \ end {aligned}}}$

Pojemność

Pojemność kanału z BEC jest , osiągnięte z jednolitym rozkładzie (czyli połowie wejść powinno być 0 i pół powinien 1). ${\ displaystyle 1-P_ {e}}$${\ displaystyle X}$

Dowód

Dzięki symetrii wartości wejściowych optymalny rozkład wejściowy wynosi . Pojemność kanału to: ${\ Displaystyle X \ sim \ mathrm {Bernoulli} \ lewo ({\ Frac {1} {2}} \ prawej)}$ ${\ displaystyle \ operatorname {I} (X; Y) = \ operatorname {H} (X) - \ operatorname {H} (X | Y)}$ Zauważ, że dla binarnej funkcji entropii (która ma wartość 1 na wejściu ), ${\ displaystyle \ operatorname {H} _ {\ text {b}}}$${\ displaystyle {\ frac {1} {2}}}$ ${\ displaystyle \ operatorname {H} (X | Y) = \ suma _ {y} P (y) \ operatorname {H} (X | y) = P_ {e} \ operatorname {H} _ {\ tekst {b }} \ left ({\ frac {1} {2}} \ right) = P_ {e}}$ jak wiadomo z (i jest równe) y, chyba że ma prawdopodobieństwo . ${\ displaystyle X}$${\ displaystyle y = e}$${\ displaystyle P_ {e}}$ Z definicji tak ${\ Displaystyle \ operatorname {H} (X) = \ operatorname {H} _ {\ tekst {b}} \ lewo ({\ Frac {1} {2}} \ prawej) = 1}$ ${\ displaystyle \ operatorname {ja} (X; Y) = 1-P_ {e}}$ .

Jeśli nadawca zostanie powiadomiony o skasowaniu bitu, może wielokrotnie przesyłać każdy bit, aż zostanie prawidłowo odebrany, uzyskując pojemność . Jednak dzięki twierdzeniu o kodowaniu kanałów z szumami pojemność można uzyskać nawet bez takiego sprzężenia zwrotnego. ${\ displaystyle 1-P_ {e}}$${\ displaystyle 1-P_ {e}}$

Powiązane kanały

Jeśli bity są odwracane, a nie usuwane, kanał jest binarnym kanałem symetrycznym (BSC), który ma pojemność (dla binarnej funkcji entropii ), która jest mniejsza niż pojemność BEC dla . Jeśli bity są kasowane, ale odbiornik nie jest powiadamiany (tj. Nie odbiera wyjścia ), to kanał jest kanałem kasowania , a jego pojemność jest problemem otwartym. ${\ Displaystyle 1- \ operatorname {H} _ {\ tekst {b}} (P_ {e})}$ ${\ displaystyle \ operatorname {H} _ {\ text {b}}}$${\ displaystyle 0 <P_ {e} <1/2}$${\ displaystyle e}$

Historia

BEC został wprowadzony przez Petera Eliasa z MIT w 1955 roku jako przykład zabawki.

Zobacz też

• Kod kasowania
• Kanał usuwania pakietów

Uwagi

Bibliografia

• Thomas M. Cover; Joy A. Thomas (1991). Elementy teorii informacji . Hoboken, New Jersey: Wiley. ISBN   978-0-471-24195-9 .
• MacKay, David JC (2003). Teoria informacji, wnioskowanie i algorytmy uczenia się . Cambridge University Press. ISBN   0-521-64298-1 .
• Mitzenmacher, Michael (2009), „Badanie wyników dla kanałów usuwania i powiązanych kanałów synchronizacji”, Badania prawdopodobieństwa , 6 : 1–33, doi : 10.1214 / 08-PS141 , MR   2525669