Kanál binárního mazání - Binary erasure channel

Model kanálu pro kanál binárního mazání zobrazující mapování ze vstupu kanálu X na výstup kanálu Y (se známým symbolem mazání ?). Pravděpodobnost vymazání je ${displaystyle p_ {e}}$

v teorie kódování a teorie informace, a kanál binárního mazání (BEC) je komunikační kanál Modelka. Vysílač pošle a bit (nula nebo jedna) a přijímač bit přijme buď správně, nebo s určitou pravděpodobností ${displaystyle P_ {e}}$ přijme zprávu, že bit nebyl přijat ("vymazán").

Definice

Binární kanál pro mazání s pravděpodobností vymazání ${displaystyle P_ {e}}$ je kanál s binárním vstupem, ternárním výstupem a pravděpodobností vymazání ${displaystyle P_ {e}}$. To je, pojďme ${displaystyle X}$ být přenášeny náhodná proměnná s abecedou ${displaystyle {0,1}}$. Nechat ${displaystyle Y}$ být přijatá proměnná s abecedou ${displaystyle {0,1, {ext {e}}}}$, kde ${displaystyle {ext {e}}}$ je symbol mazání. Poté je kanál charakterizován podmíněné pravděpodobnosti:^[1]

${displaystyle {egin {aligned} operatorname {Pr} [Y = 0 | X = 0] & = 1-P_ {e} operatorname {Pr} [Y = 0 | X = 1] & = 0 operatorname {Pr} [Y = 1 | X = 0] & = 0 operatorname {Pr} [Y = 1 | X = 1] & = 1-P_ {e} operatorname {Pr} [Y = e | X = 0] & = P_ {e} operatorname {Pr} [Y = e | X = 1] & = P_ {e} konec {zarovnáno}}}$

Kapacita

The kapacita kanálu BEC je ${displaystyle 1-P_ {e}}$, dosažené jednotným rozdělením pro ${displaystyle X}$ (tj. polovina vstupů by měla být 0 a polovina by měla být 1).^[2]

Důkaz[2]

Symetrií vstupních hodnot je optimální vstupní rozdělení ${displaystyle Xsim mathrm {Bernoulli} vlevo ({frac {1} {2}} vpravo)}$. Kapacita kanálu je: ${displaystyle operatorname {I} (X; Y) = operatorname {H} (X) -operatorname {H} (Y | X)}$ Všimněte si, že pro funkce binární entropie ${displaystyle operatorname {H} _ {ext {b}}}$ (který má pro vstup hodnotu 1 ${displaystyle {frac {1} {2}}}$), ${displaystyle operatorname {H} (Y | X) = součet _ {y} P (y) operatorname {H} (X | y) = P_ {e} operatorname {H} _ {ext {b}} vlevo ({frac {1} {2}} ight) = P_ {e}}$ tak jako ${displaystyle X}$ je známo z (a rovno) y, pokud ${displaystyle y = e}$, což má pravděpodobnost ${displaystyle P_ {e}}$. Podle definice ${displaystyle operatorname {H} (X) = operatorname {H} _ {ext {b}} left ({frac {1} {2}} ight) = 1}$, tak ${displaystyle operatorname {I} (X; Y) = 1-P_ {e}}$.

Pokud je odesílatel upozorněn, když je bit vymazán, může opakovaně vysílat každý bit, dokud nebude správně přijat, čímž dosáhne kapacity ${displaystyle 1-P_ {e}}$. Avšak tím, že věta o kódování hlučných kanálů, kapacita ${displaystyle 1-P_ {e}}$ lze získat i bez takové zpětné vazby.^[3]

Související kanály

Pokud jsou bity spíše převráceny než vymazány, kanál je a binární symetrický kanál (BSC), který má kapacitu ${displaystyle 1-operatorname {H} _ {ext {b}} (P_ {e})}$ (pro funkce binární entropie ${displaystyle operatorname {H} _ {ext {b}}}$), což je méně než kapacita BEC pro ${displaystyle 0$.^[4][5] Pokud jsou bity vymazány, ale přijímač není upozorněn (tj. Nepřijímá výstup ${displaystyle e}$) pak je kanál a kanál pro smazání a jeho kapacita je otevřeným problémem.^[6]

Dějiny

BEC zavedla Peter Elias MIT v roce 1955 jako příklad hračky.^{[Citace je zapotřebí ]}

Viz také

• Vymazání kódu
• Kanál pro mazání paketů

Poznámky

Reference

• Thomas M. Cover; Joy A. Thomas (1991). Základy teorie informace. Hoboken, New Jersey: Wiley. ISBN  978-0-471-24195-9.
• MacKay, David J.C. (2003). Informační teorie, odvození a výukové algoritmy. Cambridge University Press. ISBN  0-521-64298-1.
• Mitzenmacher, Michael (2009), „Průzkum výsledků pro deleční kanály a související synchronizační kanály“, Pravděpodobnostní průzkumy, 6: 1–33, doi:10.1214 / 08-PS141, PAN  2525669