Canal de eliminação binária

Em teoria da codificação e teoria da informação, um canal de eliminação binária (BEC) é um modelo de canal de comunicação. Um transmissor envia um bit (zero ou um) e o receptor recebe o bit corretamente ou, com alguma probabilidade $P_{e}$, recebe uma mensagem de que o bit não foi recebido ("apagado").

O modelo de canal para o canal de eliminação binária mostrando um mapeamento da entrada do canal X para a saída do canal Y (com o símbolo de eliminação conhecido ? ). A probabilidade de apagamento é $p_{e}$

Definição

Um canal de eliminação binária com probabilidade de eliminação $P_{e}$ é um canal com entrada binária, saída ternária e probabilidade de eliminação $P_{e}$. Ou seja, seja $X$ a variável aleatória transmitida com o alfabeto $\{0,1\}$. Seja $Y$ a variável recebida com o alfabeto $\{0,1,{\text{e}}\}$, onde ${\text{e}}$ é o símbolo de apagamento. Então, o canal é caracterizado pelas probabilidades condicionais:

${\begin{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}\end{aligned}}$

Capacidade

A capacidade de canal de um BEC é $1-P_{e}$, obtida com uma distribuição uniforme para $X$ (ou seja, metade das entradas deve ser 0 e metade deve ser 1).

Comprovação

Por simetria dos valores de entrada, a distribuição ideal de entrada é $X\sim \mathrm {Bernoulli} \left({\frac {1}{2}}\right)$. A capacidade do canal é: $\operatorname {I} (X;Y)=\operatorname {H} (X)-\operatorname {H} (X|Y)$ Observe que, para a função de entropia binária $\operatorname {H} _{\text{b}}$ (que tem valor 1 para entrada ${\frac {1}{2}}$), $\operatorname {H} (X|Y)=\sum _{y}P(y)\operatorname {H} (X|y)=P_{e}\operatorname {H} _{\text{b}}\left({\frac {1}{2}}\right)=P_{e}$ como $X$ é conhecido de (e igual à) y a menos que $y=e$, que tem probabilidade $P_{e}$. Por definição $\operatorname {H} (X)=\operatorname {H} _{\text{b}}\left({\frac {1}{2}}\right)=1$, então $\operatorname {I} (X;Y)=1-P_{e}$.

Se o remetente for notificado quando um bit for apagado, ele poderá transmitir cada bit repetidamente até que seja recebido corretamente, atingindo a capacidade $1-P_{e}$. No entanto, pelo teorema de codificação de canal ruidoso, a capacidade de $1-P_{e}$ pode ser obtida mesmo sem tal feedback.

Canais relacionados

Se os bits forem invertidos em vez de apagados, o canal é um canal binário simétrico (BSC), que tem capacidade $1-\operatorname {H} _{\text{b}}(P_{e})$ (para a [ [função de entropia binária]] $\operatorname {H} _{\text{b}}$), que é menor que a capacidade do BEC para $0<P_{e}<1/2$ . Se os bits são apagados, mas o receptor não é notificado (ou seja, não recebe a saída $e$), então o canal é um canal de exclusão e sua capacidade é um problema aberto.

Referências

• Thomas M. Cover; Joy A. Thomas (1991). Elements of information theory. Hoboken, New Jersey: Wiley. ISBN 978-0-471-24195-9 

• MacKay, David J.C. (2003). Information theory, inference, and learning algorithms. [S.l.]: Cambridge University Press. ISBN 0-521-64298-1 

• Mitzenmacher, Michael (2009), «A survey of results for deletion channels and related synchronization channels», Probability surveys, 6: 1–33, MR 2525669, doi:10.1214/08-PS141