En la teoría de la codificación y la teoría de la información , un canal de borrado binario ( BEC ) es un modelo de canal de comunicaciones . Un transmisor envía un bit (un cero o uno) y el receptor recibe el bit correctamente o con cierta probabilidad recibe un mensaje de que el bit no fue recibido ("borrado").
Definición
Un canal de borrado binario con probabilidad de borrado es un canal con entrada binaria, salida ternaria y probabilidad de borrado . Es decir, dejaser la variable aleatoria transmitida con alfabeto. Dejar ser la variable recibida con alfabeto , dónde es el símbolo de borrado. Entonces, el canal se caracteriza por las probabilidades condicionales : [1]
Capacidad
La capacidad de canal de un BEC es, logrado con una distribución uniforme para (es decir, la mitad de las entradas debe ser 0 y la mitad debe ser 1). [2]
Prueba [2] Por simetría de los valores de entrada, la distribución de entrada óptima es . La capacidad del canal es: Observe que, para la función de entropía binaria (que tiene el valor 1 para la entrada ),
como se conoce de (e igual a) y a menos que , que tiene probabilidad .
Por definición , entonces
- .
Si se notifica al remitente cuando se borra un bit, puede transmitir repetidamente cada bit hasta que se reciba correctamente, alcanzando la capacidad . Sin embargo, según el teorema de la codificación de canales ruidosos , la capacidad depuede obtenerse incluso sin dicha retroalimentación. [3]
Canales relacionados
Si los bits se invierten en lugar de borrarse, el canal es un canal simétrico binario (BSC), que tiene capacidad(para la función de entropía binaria ), que es menor que la capacidad del BEC para . [4] [5] Si se borran bits pero no se notifica al receptor (es decir, no recibe la salida) entonces el canal es un canal de eliminación y su capacidad es un problema abierto. [6]
Historia
El BEC fue presentado por Peter Elias del MIT en 1955 como un ejemplo de juguete. [ cita requerida ]
Ver también
Notas
- ^ MacKay (2003) , p. 148.
- ↑ a b MacKay (2003) , p. 158.
- ^ Portada y Thomas (1991) , p. 189.
- ^ Portada y Thomas (1991) , p. 187.
- ^ MacKay (2003) , p. 15.
- ^ Mitzenmacher (2009) , p. 2.
Referencias
- Thomas M. Cover; Joy A. Thomas (1991). Elementos de la teoría de la información . Hoboken, Nueva Jersey: Wiley. ISBN 978-0-471-24195-9.
- MacKay, David JC (2003). Teoría de la información, inferencia y algoritmos de aprendizaje . Prensa de la Universidad de Cambridge. ISBN 0-521-64298-1.
- Mitzenmacher, Michael (2009), "Una encuesta de resultados para canales de eliminación y canales de sincronización relacionados", Encuestas de probabilidad , 6 : 1–33, doi : 10.1214 / 08-PS141 , MR 2525669