Códigos de corrección de errores con retroalimentación

En matemáticas , informática , telecomunicaciones , teoría de la información y teoría de la búsqueda , los códigos correctores de errores con retroalimentación son códigos correctores de errores diseñados para funcionar en presencia de retroalimentación del receptor al emisor. ^{[ 1 ]}

Alice (la 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.

Un código corrector de errores es una forma de codificar x como un mensaje, de manera que Bob entienda correctamente el valor x tal como lo concibió Alice, incluso si el mensaje que Alice envía y el que Bob recibe difieren. En un código corrector de errores con retroalimentación, el canal es bidireccional : Bob puede enviar retroalimentación a Alice sobre el mensaje que recibió.

En un código de corrección de errores sin retroalimentación ruidosa , la retroalimentación que recibe el emisor siempre está libre de errores. En un código de corrección de errores con retroalimentación ruidosa, pueden producirse errores tanto en la retroalimentación como en el mensaje.

Un código corrector de errores con retroalimentación sin ruido es equivalente a una estrategia de búsqueda adaptativa con errores. ^{[ 1 ]}

En 1956, Claude Shannon introdujo el canal discreto sin memoria con retroalimentación sin ruido. En 1961, Alfréd Rényi introdujo el juego de 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 tesis doctoral de 1964, Elwyn Berlekamp analizó códigos correctores de errores con retroalimentación sin ruido. ^{[ 2 ] [ 3 ]} En el escenario de Berlekamp, ​​el receptor elegía un subconjunto de mensajes posibles y preguntaba al emisor si el mensaje dado pertenecía a dicho subconjunto, con una respuesta de «sí» o «no». En función de esta respuesta, el receptor elegía un nuevo subconjunto y repetía el proceso. El juego se complica aún más debido al ruido; algunas de las respuestas serán erróneas.

• Teorema de codificación de canal ruidoso

• Berlekamp, ​​Elwyn R. (1964). Codificación por bloques con retroalimentación sin ruido (PDF) (PhD). Instituto Tecnológico de Massachusetts.
• Deppe, Christian (2007), "Codificación con retroalimentación y búsqueda con mentiras" , en Imre Csiszár; Gyula OH Katona; Gabor Tardos (eds.), Entropía, búsqueda, complejidad , Bolyai Society Mathematical Studies, vol.  16, Springer, pp. 27–70 , doi : 10.1007/978-3-540-32777-6_2 , ISBN  978-3-540-32573-4.
• Hill, Ray (1995), "Búsqueda con mentiras" , Surveys in Combinatorics , London Mathematical Society Lecture Note Series, vol.  218, Cambridge University Press, pp. 41–70 , ISBN  0-521-49797-3.