Ads-728

Ads-728

Psicología

Astrofísica

Genética

Neurociencia

» » Nueva frontera en los códigos de corrección de errores

Referencia: Phys.org.news .
por Larry Hardesty, 1 de octubre 2014

Los códigos de corrección de errores es una de las glorias de la era de la información: Son los que garantizan la perfecta transmisión de información digital a través de las ondas de radio o a través de los cables de cobre, incluso en presencia de las influencias corruptoras de lo que los ingenieros llaman "ruido".

Pero los códigos de corrección de errores clásicos funcionan mejor con grandes porciones de datos: La porción más grande a la mayor velocidad es la que se puede transmitir sin errores. En la era de Internet, sin embargo, la computación distribuida se está volviendo mucho más común, con dispositivos que intercambian reiteradamente pequeñas cantidades de datos durante largos períodos de tiempo.

Durante los últimos 20 años, los investigadores han estado investigando los esquemas de codificación interactivos que abordan el problema de las largas secuencias de cortos intercambios. Al igual que los clásicos códigos de corrección de errores, los códigos interactivos son evaluados de acuerdo con tres criterios: ¿Qué cantidad de ruido pueden tolerar? ¿Cuál es la máxima velocidad de transmisión que ofrecen? ¿Y cuánto tiempo consumen en los procesos de codificación y decodificación?

En el Symposium on Foundations of Computer Science de la IEEE de este mes, antiguos y presentes estudiantes de postgrado del MIT describen el primer esquema de codificación interactiva para acercarse a lo más óptimo en las tres medidas.

"Antes de este trabajo, se sabía cómo obtener dos de cada tres de estas cosas para que fuese óptimo", afirma Mohsen Ghaffari, estudiante graduado en ingeniería eléctrica y ciencias de la computación y uno de los dos co-autores del artículo. "En este trabajo alcanzamos los tres."

Ruido

Además, el innovador análisis de 1948 de Claude Shannon sobre los códigos correctores de errores, consideró el caso de ruido aleatorio, según el cual cada bit de datos transmitido tiene la misma probabilidad de estar dañado. Ghaffari y su colaborador, Bernhard Haeupler, que hizo su trabajo de posgrado en el MIT y ahora es un profesor asistente en la arnegie Mellon University, lo considera el caso más estricto de "ruido adversario", en el que un supuesto antagonista está tratando de interferir con la transmisión de la forma más perjudicial posible.

"No sabemos qué tipo de ruido aleatorio será el que primero se capture realmente", explica Ghaffari. "Si supiéramos el primero, simplemente usaríamos ese. Pero, en general, no lo sabemos. Así que se intenta generar una codificación que sea lo más general posible. "Un esquema de codificación que podría frustrar a un adversario activo también podría frustrar cualquier tipo de ruido aleatorio.”

Los códigos de corrección de errores, tanto clásicos como interactivos, funcionan añadiendo información extra al mensaje a transmitir. Podrían, por ejemplo, agregar una serie de bits que describen las relaciones aritméticas entre los bits del mensaje. Tanto los bits del mensaje como los bits adicionales son susceptibles de corrupción, así que, decodificar un mensaje --extrayendo la verdadera secuencia del mensaje de bits desde la secuencia que llega al receptor--, por lo general, es un proceso de iteración de ida y vuelta entre los bits de mensaje y los bits adicionales, procurando limar las discrepancias.

En la comunicación interactiva, la velocidad máxima de error tolerable es de una cuarta parte: Si el adversario puede corromper más de un cuarto de los bits enviados, se hace imposible una comunicación fiable. En algunos esquemas de codificación interactiva anteriores, comenta Ghaffari, pudieron manejar ese tipo de error sin necesidad de demasiados bits adicionales. Pero el proceso de decodificación resultaba prohibitivamente complejo.

Hacer una lista

Para mantener una baja complejidad, Ghaffari y Haeupler adoptaron una técnica llamada lista de decodificación. En lugar de una iteración de ida y vuelta entre los bits del mensaje y los bits adicionales hasta que la única interpretación emergente sea la más probable, sus algoritmos iteran sólo lo suficiente para crear una lista de posibles candidatos. Al final de su mutua, cómputación, cada uno de los dispositivos que interactúan pueden tener una lista con cientos de entradas.

Sin embargo, cada dispositivo, en tanto que sólo itiene un conocimiento mperfecto de los mensajes enviados por la otra parte, sí tiene un conocimiento perfecto de los mensajes que envió. Así pues, si al final de la computación, los dispositivos simplemente intercambian listas, cada uno tiene la suficiente información adicional para concentrarse en la decodificación óptima.

La tasa de error máxima tolerable para un esquema de codificación interactiva (de una cuarta parte) es un resultado teórico. La longitud mínima de un mensaje codificado y la complejidad mínima de decodificación, por otro lado, son suposiciones basadas en la observación.

Pero Ghaffari y el algoritmo de decodificación de Haeupler es casi lineal, lo que significa que su tiempo de ejecución es aproximadamente proporcional a la longitud de los mensajes intercambiados.

Sin embargo, las relaciones lineales aún definidas por las constantes: y = x siguen siendo una relación lineal, aunque también lo sea y = 1.000.000.000x. Un algoritmo lineal que toma un segundo adicional de computación por cada bit adicional de datos no se considera tan bueno como un algoritmo lineal que sólo le lleva un microsegundo adicional. 


- fuente.  Massachusetts Institute of Technology .
- imagen. ilustración red.
.

«
Next
Entrada más reciente
»
Previous
Entrada antigua
Editor del blog Pedro Donaire

Filosofía

Educación

Deporte

Tecnología

Materiales