En matemáticas , informática , telecomunicaciones , teoría de la información y teoría de la búsqueda , los códigos de corrección de errores con retroalimentación se refieren a códigos de corrección de errores diseñados para funcionar en presencia de retroalimentación del receptor al remitente. [1]
Problema
Alice (el remitente) desea enviar un valor x a Bob (el receptor). El canal de comunicación entre Alice y Bob es imperfecto y puede introducir errores.
Solución
Un código de corrección de errores es una forma de codificar x como un mensaje de modo que Bob entienda con éxito el valor x como pretendía Alice, incluso si el mensaje que Alice envía y el mensaje que Bob recibe son diferentes. En un código de corrección de errores con retroalimentación, el canal es bidireccional : Bob puede enviar retroalimentación a Alice sobre el mensaje que recibió.
Comentarios ruidosos
En un código de corrección de errores sin comentarios ruidosos , los comentarios recibidos por el remitente siempre están libres de errores. En un código de corrección de errores con comentarios ruidosos , pueden producirse errores tanto en los comentarios como en el mensaje.
Un código de corrección de errores con retroalimentación silenciosa es equivalente a una estrategia de búsqueda adaptativa con errores. [1]
Historia
En 1956, Claude Shannon introdujo el canal discreto sin memoria con retroalimentación silenciosa. En 1961, Alfréd Rényi introdujo el juego Bar-Kochba (también conocido como Veinte preguntas ), con un porcentaje dado de respuestas incorrectas, y calculó el número mínimo de preguntas elegidas al azar para determinar la respuesta.
En su disertación de 1964, Elwyn Berlekamp consideró los códigos de corrección de errores con retroalimentación silenciosa. [2] En el escenario de Berlekamp, el receptor eligió un subconjunto de posibles mensajes y le preguntó al remitente si el mensaje dado estaba en este subconjunto, una respuesta "sí" o "no". Con base en esta respuesta, el receptor eligió un nuevo subconjunto y repitió el proceso. El juego se complica aún más debido al ruido; algunas de las respuestas estarán equivocadas.
Fuentes
- Deppe, Christian (2007), "Codificar con retroalimentación y buscar con mentiras", en Imre Csiszár; Gyula OH Katona; Gabor Tardos (eds.), Entropy, Search, Complexity , Bolyai Society Mathematical Studies, 16 , Berlín-Heidelberg: Springer, págs. 27–70, doi : 10.1007 / 978-3-540-32777-6 , ISBN 978-3-540-32573-4.
- Hill, Ray (1995), Buscando con mentiras , Cambridge London Mathematical Society Lecture Note Series, Surveys in Combinatorics, Cambridge: Cambridge Univ. Prensa, págs. 41–70 , ISBN 0-521-49797-3.
Referencias
- ^ a b Véase Deppe 2007 y Hill 1995 .
- ^ Deppe 2007 .