Canal simétrico binario

Un canal binario simétrico (o BSC _p ) es un modelo de canal de comunicaciones común utilizado en la teoría de codificación y la teoría de la información . En este modelo, un transmisor desea enviar un bit (un cero o un uno), y el receptor recibirá un bit. El bit se "invertirá" con una " probabilidad de cruce " de p , y de lo contrario se recibirá correctamente. Este modelo se puede aplicar a diversos canales de comunicación, como líneas telefónicas o unidades de almacenamiento en disco .

El teorema de codificación de canal ruidoso se aplica a BSC _p , y dice que la información se puede transmitir a cualquier velocidad hasta la capacidad del canal con un error arbitrariamente bajo. La capacidad del canal es bits, donde es la función de entropía binaria . Se han diseñado códigos que incluyen el código de Forney para transmitir información de manera eficiente a través del canal. ${\displaystyle 1-\operatorname {H} _{\text{b}}(p)}$ ${\displaystyle \operatorname {H} _{\text{b}}}$

Definición

El canal binario simétrico ve cada bit de un mensaje transmitido correctamente con una probabilidad de 1– p e incorrectamente con una probabilidad p , debido al ruido en el medio de transmisión.

Un canal binario simétrico con probabilidad de cruce , denotado por BSC _p , es un canal con entrada binaria y salida binaria y probabilidad de error . Es decir, si es la variable aleatoria transmitida y la variable recibida, entonces el canal se caracteriza por las probabilidades condicionales : ^[1] ${\displaystyle p}$ ${\displaystyle p}$ ${\displaystyle X}$ ${\displaystyle Y}$

${\displaystyle {\begin{aligned}\operatorname {Pr} [Y=0|X=0]&=1-p\\\operatorname {Pr} [Y=0|X=1]&=p\\\operatorname {Pr} [Y=1|X=0]&=p\\\operatorname {Pr} [Y=1|X=1]&=1-p\end{aligned}}}$

Se supone que . Si , entonces el receptor puede intercambiar la salida (interpretar 1 cuando ve 0, y viceversa) y obtener un canal equivalente con probabilidad de cruce . ${\displaystyle 0\leq p\leq 1/2}$ ${\displaystyle p>1/2}$ ${\displaystyle 1-p\leq 1/2}$

Capacidad

Gráfico que muestra la proporción de la capacidad de un canal ( eje y ) que se puede utilizar para carga útil en función de qué tan ruidoso es el canal (probabilidad de inversión de bits; eje x ).

La capacidad del canal binario simétrico, en bits , es: ^[2]

${\displaystyle \ C_{\text{BSC}}=1-\operatorname {H} _{\text{b}}(p),}$

donde es la función de entropía binaria , definida por: ^[2] ${\displaystyle \operatorname {H} _{\text{b}}(p)}$

${\displaystyle \operatorname {H} _{\text{b}}(x)=x\log _{2}{\frac {1}{x}}+(1-x)\log _{2}{\frac {1}{1-x}}}$

Teorema de codificación de canal ruidoso

El teorema de codificación de canal ruidoso de Shannon proporciona un resultado sobre la tasa de información que se puede transmitir a través de un canal de comunicación con un error arbitrariamente bajo. Estudiamos el caso particular de . ${\displaystyle {\text{BSC}}_{p}}$

El ruido que caracteriza es una variable aleatoria que consta de n bits aleatorios independientes (n se define más adelante) donde cada bit aleatorio es un con probabilidad y un con probabilidad . Esto lo indicamos escribiendo " ". ${\displaystyle e}$ ${\displaystyle {\text{BSC}}_{p}}$ ${\displaystyle 1}$ ${\displaystyle p}$ ${\displaystyle 0}$ ${\displaystyle 1-p}$ ${\displaystyle e\in {\text{BSC}}_{p}}$

Teorema  —  Para todos todos , todos suficientemente grandes (dependiendo de y ), y todos , existe un par de funciones de codificación y decodificación y respectivamente, tales que cada mensaje tiene la siguiente propiedad: ${\displaystyle p<{\tfrac {1}{2}},}$ ${\displaystyle 0<\epsilon <{\tfrac {1}{2}}-p}$ ${\displaystyle n}$ ${\displaystyle p}$ ${\displaystyle \epsilon }$ ${\displaystyle k\leq \lfloor (1-H(p+\epsilon ))n\rfloor }$ ${\displaystyle E:\{0,1\}^{k}\to \{0,1\}^{n}}$ ${\displaystyle D:\{0,1\}^{n}\to \{0,1\}^{k}}$ ${\displaystyle m\in \{0,1\}^{k}}$

${\displaystyle \Pr _{e\in {\text{BSC}}_{p}}[D(E(m)+e)\neq m]\leq 2^{-{\delta }n}}$.

Lo que este teorema implica en realidad es que, cuando se selecciona un mensaje de , se lo codifica con una función de codificación aleatoria y se lo envía a través de un canal ruidoso , existe una probabilidad muy alta de recuperar el mensaje original mediante la decodificación, si la velocidad del canal está limitada por la cantidad establecida en el teorema. La probabilidad de error de decodificación es exponencialmente pequeña. ${\displaystyle \{0,1\}^{k}}$ ${\displaystyle E}$ ${\displaystyle {\text{BSC}}_{p}}$ ${\displaystyle k}$

Prueba

El teorema se puede demostrar directamente con un método probabilístico . Considere una función de codificación que se selecciona al azar. Esto significa que para cada mensaje , el valor se selecciona al azar (con probabilidades iguales). Para una función de codificación dada , la función de decodificación se especifica de la siguiente manera: dada cualquier palabra de código recibida , encontramos el mensaje tal que la distancia de Hamming sea lo más pequeña posible (con empates resueltos arbitrariamente). ( se llama función de decodificación de máxima verosimilitud ). ${\displaystyle E:\{0,1\}^{k}\to \{0,1\}^{n}}$ ${\displaystyle m\in \{0,1\}^{k}}$ ${\displaystyle E(m)\in \{0,1\}^{n}}$ ${\displaystyle E}$ ${\displaystyle D:\{0,1\}^{n}\to \{0,1\}^{k}}$ ${\displaystyle y\in \{0,1\}^{n}}$ ${\displaystyle m\in \{0,1\}^{k}}$ ${\displaystyle \Delta (y,E(m))}$ ${\displaystyle D}$

La prueba continúa mostrando que al menos una de esas elecciones satisface la conclusión del teorema, por integración sobre las probabilidades. Supongamos que y son fijos. Primero mostramos que, para un fijo y elegido aleatoriamente, la probabilidad de falla sobre el ruido es exponencialmente pequeña en n . En este punto, la prueba funciona para un mensaje fijo . A continuación, ampliamos este resultado para que funcione para todos los mensajes . Logramos esto eliminando la mitad de las palabras de código del código con el argumento de que la prueba para la probabilidad de error de decodificación se cumple para al menos la mitad de las palabras de código. El último método se llama expurgación. Esto le da al proceso total el nombre de codificación aleatoria con expurgación . ${\displaystyle (E,D)}$ ${\displaystyle p}$ ${\displaystyle \epsilon }$ ${\displaystyle m\in \{0,1\}^{k}}$ ${\displaystyle E}$ ${\displaystyle {\text{BSC}}_{p}}$ ${\displaystyle m}$ ${\displaystyle m}$

Inverso del teorema de capacidad de Shannon

El inverso del teorema de capacidad establece básicamente que es la mejor tasa que se puede lograr en un canal binario simétrico. Formalmente, el teorema establece: ${\displaystyle 1-H(p)}$

Teorema  —  Si entonces lo siguiente es verdadero para cada función de codificación y decodificación : y : respectivamente: [ . ${\displaystyle k}$ ${\displaystyle \geq }$ ${\displaystyle \lceil }$ ${\displaystyle (1-H(p+\epsilon )n)}$ ${\displaystyle \rceil }$ ${\displaystyle E}$ ${\displaystyle \{0,1\}^{k}}$ ${\displaystyle \rightarrow }$ ${\displaystyle \{0,1\}^{n}}$ ${\displaystyle D}$ ${\displaystyle \{0,1\}^{n}}$ ${\displaystyle \rightarrow }$ ${\displaystyle \{0,1\}^{k}}$ ${\displaystyle \Pr _{e\in {\text{BSC}}_{p}}}$ ${\displaystyle D(E(m)+e)}$ ${\displaystyle \neq }$ ${\displaystyle m]}$ ${\displaystyle \geq }$ ${\displaystyle {\frac {1}{2}}}$

Sin embargo, la intuición detrás de la prueba muestra que la cantidad de errores crece rápidamente a medida que la tasa crece más allá de la capacidad del canal. La idea es que el remitente genera mensajes de dimensión , mientras que el canal introduce errores de transmisión. Cuando la capacidad del canal es , la cantidad de errores es típicamente para un código de longitud de bloque . La cantidad máxima de mensajes es . La salida del canal, por otro lado, tiene valores posibles. Si hay alguna confusión entre dos mensajes, es probable que . Por lo tanto, tendríamos , un caso que nos gustaría evitar para mantener la probabilidad de error de decodificación exponencialmente pequeña. ${\displaystyle k}$ ${\displaystyle {\text{BSC}}_{p}}$ ${\displaystyle H(p)}$ ${\displaystyle 2^{H(p+\epsilon )n}}$ ${\displaystyle n}$ ${\displaystyle 2^{k}}$ ${\displaystyle 2^{n}}$ ${\displaystyle 2^{k}2^{H(p+\epsilon )n}\geq 2^{n}}$ ${\displaystyle k\geq \lceil (1-H(p+\epsilon )n)\rceil }$

Códigos

Recientemente se ha trabajado mucho, y se sigue trabajando, en el diseño de códigos de corrección de errores explícitos para alcanzar las capacidades de varios canales de comunicación estándar. La motivación detrás del diseño de dichos códigos es relacionar la velocidad del código con la fracción de errores que puede corregir.

El enfoque detrás del diseño de códigos que cumplen con las capacidades del canal o el canal de borrado binario ha sido corregir un número menor de errores con una alta probabilidad y lograr la tasa más alta posible. El teorema de Shannon nos da la mejor tasa que se podría lograr en un , pero no nos da una idea de ningún código explícito que logre esa tasa. De hecho, tales códigos se construyen típicamente para corregir solo una pequeña fracción de errores con una alta probabilidad, pero logran una muy buena tasa. El primer código de este tipo se debió a George D. Forney en 1966. El código es un código concatenado mediante la concatenación de dos tipos diferentes de códigos. ${\displaystyle {\text{BSC}}}$ ${\displaystyle {\text{BEC}}}$ ${\displaystyle {\text{BSC}}_{p}}$

El código de Forney

Forney construyó un código concatenado para lograr la capacidad del teorema de codificación de canal ruidoso para . En su código, ${\displaystyle C^{*}=C_{\text{out}}\circ C_{\text{in}}}$ ${\displaystyle {\text{BSC}}_{p}}$

• El código externo es un código de longitud de bloque y velocidad sobre el campo , y . Además, tenemos un algoritmo de decodificación que puede corregir hasta una fracción de los errores más graves y se ejecuta a tiempo. ${\displaystyle C_{\text{out}}}$ ${\displaystyle N}$ ${\displaystyle 1-{\frac {\epsilon }{2}}}$ ${\displaystyle F_{2^{k}}}$ ${\displaystyle k=O(\log N)}$ ${\displaystyle D_{\text{out}}}$ ${\displaystyle C_{\text{out}}}$ ${\displaystyle \gamma }$ ${\displaystyle t_{\text{out}}(N)}$
• El código interno es un código de longitud de bloque , dimensión y una tasa de . Además, tenemos un algoritmo de decodificación para con una probabilidad de error de decodificación de como máximo sobre y se ejecuta en el tiempo. ${\displaystyle C_{\text{in}}}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle 1-H(p)-{\frac {\epsilon }{2}}}$ ${\displaystyle D_{\text{in}}}$ ${\displaystyle C_{\text{in}}}$ ${\displaystyle {\frac {\gamma }{2}}}$ ${\displaystyle {\text{BSC}}_{p}}$ ${\displaystyle t_{\text{in}}(N)}$

Para el código externo , el código Reed-Solomon habría sido el primer código que se nos habría ocurrido. Sin embargo, veremos que la construcción de un código de este tipo no se puede realizar en tiempo polinómico. Por eso se utiliza un código lineal binario . ${\displaystyle C_{\text{out}}}$ ${\displaystyle C_{\text{out}}}$

Para el código interno encontramos un código lineal mediante una búsqueda exhaustiva del código lineal de longitud de bloque y dimensión , cuya tasa cumpla con la capacidad de , mediante el teorema de codificación de canal ruidoso. ${\displaystyle C_{\text{in}}}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle {\text{BSC}}_{p}}$

La tasa que casi cumple con la capacidad. Observamos además que la codificación y decodificación de se puede realizar en tiempo polinomial con respecto a . De hecho, la codificación lleva tiempo . Además, el algoritmo de decodificación descrito lleva tiempo tanto como ; y . ${\displaystyle R(C^{*})=R(C_{\text{in}})\times R(C_{\text{out}})=(1-{\frac {\epsilon }{2}})(1-H(p)-{\frac {\epsilon }{2}})\geq 1-H(p)-\epsilon }$ ${\displaystyle {\text{BSC}}_{p}}$ ${\displaystyle C^{*}}$ ${\displaystyle N}$ ${\displaystyle C^{*}}$ ${\displaystyle O(N^{2})+O(Nk^{2})=O(N^{2})}$ ${\displaystyle Nt_{\text{in}}(k)+t_{\text{out}}(N)=N^{O(1)}}$ ${\displaystyle t_{\text{out}}(N)=N^{O(1)}}$ ${\displaystyle t_{\text{in}}(k)=2^{O(k)}}$

Probabilidad de error de decodificación

Un algoritmo de decodificación natural es: ${\displaystyle C^{*}}$

• Asumir ${\displaystyle y_{i}^{\prime }=D_{\text{in}}(y_{i}),\quad i\in (0,N)}$
• Ejecutar en ${\displaystyle D_{\text{out}}}$ ${\displaystyle y^{\prime }=(y_{1}^{\prime }\ldots y_{N}^{\prime })}$

Tenga en cuenta que cada bloque de código para se considera un símbolo para . Ahora, dado que la probabilidad de error en cualquier índice para es como máximo y los errores en son independientes, el número esperado de errores para es como máximo por linealidad de expectativa. Ahora, aplicando el límite de Chernoff , hemos limitado la probabilidad de error de que ocurran más de errores a . Dado que el código externo puede corregir como máximo los errores, esta es la probabilidad de error de decodificación de . Esto, cuando se expresa en términos asintóticos, nos da una probabilidad de error de . Por lo tanto, la probabilidad de error de decodificación lograda de es exponencialmente pequeña como el teorema de codificación de canal ruidoso. ${\displaystyle C_{\text{in}}}$ ${\displaystyle C_{\text{out}}}$ ${\displaystyle i}$ ${\displaystyle D_{\text{in}}}$ ${\displaystyle {\tfrac {\gamma }{2}}}$ ${\displaystyle {\text{BSC}}_{p}}$ ${\displaystyle D_{\text{in}}}$ ${\displaystyle {\tfrac {\gamma N}{2}}}$ ${\displaystyle \gamma N}$ ${\displaystyle e^{\frac {-\gamma N}{6}}}$ ${\displaystyle C_{\text{out}}}$ ${\displaystyle \gamma N}$ ${\displaystyle C^{*}}$ ${\displaystyle 2^{-\Omega (\gamma N)}}$ ${\displaystyle C^{*}}$

Hemos proporcionado una técnica general para construir . Para obtener descripciones más detalladas sobre y lea las siguientes referencias. Recientemente, también se han construido algunos otros códigos para lograr las capacidades. Se han considerado los códigos LDPC para este propósito por su tiempo de decodificación más rápido. ^[4] ${\displaystyle C^{*}}$ ${\displaystyle C_{\text{in}}}$ ${\displaystyle C_{\text{out}}}$

Aplicaciones

El canal binario simétrico puede modelar una unidad de disco utilizada para el almacenamiento de memoria: la entrada del canal representa un bit que se escribe en el disco y la salida corresponde al bit que se lee más tarde. El error puede surgir de la inversión de la magnetización, el ruido de fondo o el error del cabezal de escritura. Otros objetos que el canal binario simétrico puede modelar incluyen una línea de comunicación telefónica o por radio o la división celular , de la que las células hijas contienen información de ADN de su célula madre. ^[5]

Los teóricos suelen utilizar este canal porque es uno de los canales ruidosos más sencillos de analizar. Muchos problemas de la teoría de la comunicación se pueden reducir a un BSC. Por el contrario, la capacidad de transmitir de forma eficaz a través del BSC puede dar lugar a soluciones para canales más complicados.

Véase también

• Canal Z

Notas

1. MacKay (2003), pág. 4.
2. MacKay (2003), pág. 15.
3. Cover y Thomas (1991), pág. 187.
4. Richardson y Urbanke
5. MacKay (2003), págs. 3–4.

Referencias

• Portada, Thomas M.; Thomas, Joy A. (1991). Elementos de la teoría de la información . Hoboken, Nueva Jersey: Wiley. ISBN 978-0-471-24195-9.
• G. David Forney. Códigos concatenados. MIT Press, Cambridge, MA, 1966.
• Curso de Venkat Guruswamy sobre [1] Códigos de corrección de errores: construcciones y algoritmos], otoño de 2006.
• MacKay, David JC (2003). Teoría de la información, inferencia y algoritmos de aprendizaje. Cambridge University Press. ISBN 0-521-64298-1.
• Curso de Atri Rudra sobre Códigos de corrección de errores: combinatoria, algoritmos y aplicaciones (otoño de 2007), conferencias 9, 10, 29 y 30.
• Curso de Madhu Sudan sobre Introducción algorítmica a la teoría de codificación (otoño de 2001), conferencias 1 y 2.
• Una teoría matemática de la comunicación C. E Shannon, ACM SIGMOBILE Mobile Computing and Communications Review.
• Teoría de codificación moderna, de Tom Richardson y Rudiger Urbanke, Cambridge University Press