Canal binário simétrico

O canal binário simétrico (ou BSC) é um modelo de canal de comunicações, estudado no contexto de teoria de códigos, comunicações e teoria da informação. Neste modelo, um transmissor deseja enviar um bit (zero ou um), e o receptor recebe um bit (zero ou um). O bit pode ser transmitido corretamente ou existe uma probabilidade $p$ de que seja invertido. Este canal é utilizado com frequência em teoria da informação por ser um modelo simples de ser analisado e que dá base a outros modelos de canais.

Descrição

Diagrama de transição do canal binário simétrico.

O BSC é um canal binário, ou seja, pode transmitir apenas um dos dois símbolos possíveis (normalmente 0 e 1). A transmissão não é perfeita e eventualmente o receptor recebe um bit com erro. Deve-se salientar que outros tipos de canal são capazes de transmitir mais de dois símbolos e até mesmo um número infinito de símbolos.

Este canal é frequentemente utilizado por ser um dos canais com ruído mais simples de ser analisado. Muitos problemas em teoria de comunicação podem ser simplificados para o BSC. Por outro lado, a capacidade de transmissão eficaz através do BSC pode originar soluções para canais de maior complexidade.

Definição

O canal binário é simétrico se

P_Y|X( 0 | 0 ) = P_Y|X( 1 | 1 )

P_Y|X( 0 | 1 ) = P_Y|X( 1 | 0 )

As probabilidades dos símbolos de entrada são

P_X(0) = $\delta$

P_X(1) = 1 - $\delta$

Um canal binário simétrico com probabilidade de erro $\epsilon$ é um canal com entrada binária, saída binária e probabilidade de erro $\epsilon$. Portando, se X é a variável aleatória transmitida e Y é a variável recebida, então o canal é caracterizado pelas seguintes probabilidades condicionais:

P_Y|X( 0 | 0 ) = 1 - $\epsilon$

P_Y|X( 0 | 1 ) = $\epsilon$

P_Y|X( 1 | 0 ) = $\epsilon$

P_Y|X( 1 | 1 ) = 1 - $\epsilon$

Portanto, a matriz do canal é:

${\begin{pmatrix}1-\epsilon &\epsilon \\\epsilon &1-\epsilon \\\end{pmatrix}}$

E as relações do canal são:

P_Y(0) = (1 - $\epsilon$ )$\delta$ + $\epsilon$(1 - $\delta$)

P_Y(1) = $\epsilon$$\delta$ + (1 - $\epsilon$ )(1 - $\delta$)

Estas equações podem ser confirmadas pelo cálculo da soma:

P_Y(0) + P_Y(1) = (1 - $\epsilon$ + $\epsilon$)$\delta$ + (1 - $\epsilon$ + $\epsilon$)(1 - $\delta$) = $\delta$ + 1 - $\delta$ = 1

Finalmente, usando o Teorema de Bayes, temos a probabilidade dos símbolos que possivelmente foram enviados, dado o símbolo recebido:

P_X|Y( 0 | 0 ) = ${\frac {(1-\epsilon )\delta }{(1-\epsilon )\delta +\epsilon (1-\delta )}}$

P_X|Y( 1| 0 ) = ${\frac {\epsilon (1-\delta )}{(1-\epsilon )\delta +\epsilon (1-\delta )}}$

P_X|Y( 0 | 1 ) = ${\frac {\epsilon \delta }{\epsilon \delta +(1-\epsilon )(1-\delta )}}$

P_X|Y( 1| 1 ) = ${\frac {(1-\epsilon )(1-\delta )}{\epsilon \delta +(1-\epsilon )(1-\delta )}}$

Analisando os resultados acima observa-se que eles dependem das probabilidades de entrada do canal.

Capacidade do canal binário simétrico

Utilizando a definição de Informação mútua, chega-se na seguinte realação:

I(X;Y) = H(Y) - H(Y|X)

I(X;Y) = H(Y) - $\sum _{x\in X}$P_X(x)H(Y|X = x)

I(X;Y) = H(Y) - (P_X(0)H(Y|X = 0) + P_X(1)H(Y|X = 1)

I(X;Y) = H(Y) - H_b($\epsilon$)

I(X;Y) ≤ 1 - H_b($\epsilon$) bits Considerando que Y é uma variável aleatória. A igualdade I(X;Y) = 1 - H_b($\epsilon$) ocorre quando Y é uniforme e para isso, X também deve ser uniforme. Então a capacidade do canal binário simétrico pode ser representada da seguinte forma:

C = 1 - H_b($\epsilon$) bits

Figura 1 Informação mútua no BSC

E a distribuição de entrada atingida é:

px(0) = px(1) = 1/2

Alternativamente, podemos expressar I(X;Y) como:

I(X;Y) = - ($\delta$(1-ε) + (1- $\delta$)ε) $\log _{2}$($\delta$(1-ε)+(1-$\delta$)ε) - ($\delta$ε+ (1- $\delta$)(1-ε))$\log _{2}$($\delta$ε+ (1-ε)(1- $\delta$)) + (1-ε)$\log _{2}$ (1-ε) + ε$\log _{2}$ ε

Maximizando a quantidade acima no intervalo entre 0 e 1, obtemos o valor ótimo $\delta$ = 1/2, o que está de acordo com a capacidade do canal.

A figura 1 mostra o gráfico da informação mútua versus $\delta$ se relacionando com três diferentes valores da probabilidade de erro ε. Como esperado, o valor de pico de cada curva ocorre quando $\delta$ = 1/2.

Figura 2 Capacidade do BSC

A figura 2, por sua vez, mostra a capacidade C versus a probabilidade de erro ε . Observa-se que a maior capacidade

ocorre quando ε = 1 ou ε = 0, e é minima quando ε = 1/2. É interessante notar que, no caso em que ε = 1, basta trocar todos os bits no receptor, assim os bits serão recuperados sem erro. Ou seja, do ponto de vista das comunicações, para canais binários, um canal que nunca comete um erro (ε = 1) e um canal que sempre comete erros (ε = 0) são igualmente bons. Já no caso em que ε = 1/2, a saída do canal é independente da entrada, e nenhuma informação pode ser transmitida por ele.

Referências

• Stefan M. Moser, Po-Ning Chen. A student's guide to coding and information theory, 1st Edition. Cambridge University Press, January 2012. ISBN 978–1–107–01583–8.
• David J. C. MacKay. Information Theory, Inference, and Learning Algorithms Cambridge: Cambridge University Press, 2003. ISBN 0-521-64298-1
• Thomas M. Cover, Joy A. Thomas. Elements of information theory, 1st Edition. New York: Wiley-Interscience, 1991. ISBN 0-471-06259-6.
• Atri Rudra's course on Error Correcting Codes: Combinatorics, Algorithms, and Applications (Fall 2007), Lectures 9, 10, 29, and 30.
• Madhu Sudan's course on Algorithmic Introduction to Coding Theory (Fall 2001), Lecture 1 and 2.
• G. David Forney. Concatenated Codes. MIT Press, Cambridge, MA, 1966.
• Venkat Guruswamy's course on Error-Correcting Codes: Constructions and Algorithms, Autumn 2006.
• A mathematical theory of communication C. E Shannon, ACM SIGMOBILE Mobile Computing and Communications Review.
• Modern Coding Theory by Tom Richardson and Rudiger Urbanke., Cambridge University Pres