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 ${\displaystyle P_{e}}$, recebe uma mensagem de que o bit não foi recebido ("apagado").

Definição

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

${\displaystyle {\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 é ${\displaystyle 1-P_{e}}$, obtida com uma distribuição uniforme para ${\displaystyle X}$ (ou seja, metade das entradas deve ser 0 e metade deve ser 1).^[2]

Comprovação[2]

Por simetria dos valores de entrada, a distribuição ideal de entrada é ${\displaystyle X\sim \mathrm {Bernoulli} \left({\frac {1}{2}}\right)}$. A capacidade do canal é: ${\displaystyle \operatorname {I} (X;Y)=\operatorname {H} (X)-\operatorname {H} (X|Y)}$ Observe que, para a função de entropia binária ${\displaystyle \operatorname {H} _{\text{b}}}$ (que tem valor 1 para entrada ${\displaystyle {\frac {1}{2}}}$), ${\displaystyle \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 ${\displaystyle X}$ é conhecido de (e igual à) y a menos que ${\displaystyle y=e}$, que tem probabilidade ${\displaystyle P_{e}}$. Por definição ${\displaystyle \operatorname {H} (X)=\operatorname {H} _{\text{b}}\left({\frac {1}{2}}\right)=1}$, então ${\displaystyle \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 ${\displaystyle 1-P_{e}}$. No entanto, pelo teorema de codificação de canal ruidoso, a capacidade de ${\displaystyle 1-P_{e}}$ pode ser obtida mesmo sem tal feedback.^[3]

Canais relacionados

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

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