Búsqueda de código

En 1948, el mundo seguía siendo un lugar analógico. Candid Camera y Ed Sullivan apenas comenzaban sus largas carreras en televisión; El programa de radio de Jack Benny tuvo decenas de millones de oyentes. Pero la mala recepción era una realidad. La interferencia electromagnética, los obstáculos físicos entre una torre de transmisión y un receptor, y otras fuentes de lo que los ingenieros llaman ruido interrumpieron habitualmente los monólogos de Benny o las actuaciones de los invitados de Sullivan. En la mayoría de las áreas, al menos para algunas estaciones, la gente se resignó a las imágenes nevadas o al audio plagado de estática.

Claude Shannon, 1948

Ese mismo año, sin embargo, Claude Shannon, SM ‘40, PhD ‘40, publicó un artículo histórico en el que demostró matemáticamente que incluso en presencia de mucho ruido, era posible transmitir información prácticamente sin errores. Era un mundo analógico, pero la sorprendente conclusión de Shannon fue el resultado de su capacidad para pensar digitalmente. La información en cualquier medio, argumentó Shannon, podría representarse usando dígitos binarios o bits, una palabra que su artículo presentó al mundo. Si bien el ruido en un canal de comunicación puede corromper los bits, explicó, agregar bits adicionales que están relacionados con los bits originales mediante algún algoritmo conocido, un código de corrección de errores, permitirá deducir la secuencia original.

Cuanto más ruidoso sea el canal, más información adicional debe agregarse para hacer posible la corrección de errores. Y cuanta más información adicional se incluya, más lenta será la transmisión. Shannon mostró cómo calcular la menor cantidad de bits adicionales que podrían garantizar un error mínimo y, por lo tanto, la tasa más alta a la que es posible una transmisión de datos sin errores. Pero no pudo decir cómo sería un esquema de codificación práctico.

Los investigadores pasaron 45 años buscando uno. Finalmente, en 1993, un par de ingenieros franceses anunciaron un conjunto de códigos (códigos turbo) que lograron velocidades de datos cercanas al límite teórico de Shannon. La reacción inicial fue de incredulidad, pero la investigación posterior validó las afirmaciones de los investigadores. También resultó un hecho aún más sorprendente: los códigos tan buenos como los códigos turbo, que incluso se basaban en el mismo tipo de truco matemático, se habían introducido más de 30 años antes, en la tesis doctoral del MIT de Robert Gallager, SM ' 57, ScD '60. Después de décadas de negligencia, los códigos de Gallager finalmente han encontrado una aplicación práctica. Se utilizan en la transmisión de datos inalámbricos y de televisión por satélite, y en los teléfonos móviles comerciales se pueden encontrar chips dedicados a decodificarlos.

El nacimiento de la teoría de la información

Gallager llegó al MIT en 1956, el mismo año en que el propio Shannon regresó como profesor, después de 15 años en Bell Labs. Pero no fue la perspectiva de trabajar con Shannon lo que lo llevó a elegir el MIT en lugar de Yale, donde también había solicitado ingresar a la escuela de posgrado. Estaba en el ejército, en una tarea sin sentido, y realmente odiaba lo que estaba haciendo, dice Gallager, quien enseñó en el MIT durante más de 40 años después de obtener su doctorado y todavía asesora a estudiantes graduados como profesor emérito en el Laboratorio de Investigación de Electrónica. El MIT comenzó una semana antes que Yale. Y estaba tan ansioso por salir del ejército que esa fue realmente mi única razón para venir al MIT.

Gallager ni siquiera estaba seguro de querer estudiar teoría de la información, la nueva disciplina naciente del artículo de Shannon de 1948. Pero antes de unirse al Cuerpo de Señales del Ejército, Gallager también había trabajado durante varios años en Bell Labs, donde pasaba tres días a la semana en un salón de clases aprendiendo sobre los últimos avances en ingeniería eléctrica. Aunque nunca había conocido a Shannon, esa experiencia lo ayudó a reconocer el alcance de su logro. Simplemente lo veía como una especie de dios, dice Gallager.

De hecho, cuando Shannon se unió a la facultad del MIT, era una celebridad menor. Ya en 1953, un artículo sobre teoría de la información en la revista Fortune había declarado: No puede ser exagerado decir que el progreso del hombre en la paz y la seguridad en la guerra dependen más de aplicaciones fructíferas de la teoría de la información que de demostraciones físicas, ya sea en bombas. o en las centrales eléctricas, que funciona la famosa ecuación de Einstein.

Lo que cautivó la imaginación del público fue la idea de que la información en toda su diversidad (texto, audio, video) podía reducirse a meras secuencias de unos y ceros. Los dispositivos digitales comerciales aún no existían, por lo que a la gente le sorprendió que 001001010101000101011101 pudiera representar parte de una sinfonía, parte de una película, un color o una línea de un libro. Pero como señaló Shannon en su artículo, su colega de Bell Labs, Ralph Hartley, había hecho una sugerencia similar 20 años antes. El aspecto del artículo que cautivó (y sigue cautivando) a los compañeros ingenieros de Shannon fue la forma ingeniosa en que demostró que debe haber algún código capaz de producir transmisiones de datos sin errores hasta la capacidad de un canal.

Para comprender cómo funciona un código de corrección de errores, piense en alguien que intenta enviar un mensaje de cuatro bits a través de un canal ruidoso. Si el ruido hace que uno de los bits cambie a su opuesto, el receptor no tiene forma de saber que se ha producido un error. Simplemente repitiendo el mensaje, de modo que 0011 se convierta en 00110011, resuelve ese problema: ahora, si un bit cambia a su opuesto, el receptor sabe que hay un error, porque las dos versiones del mensaje no coinciden. Pero es imposible saber cuál es la correcta. Una mejor manera de codificar el mensaje podría usar los cuatro bits adicionales para representar información sobre los bits del mensaje: el quinto bit, por ejemplo, podría decirle si los dos primeros bits del mensaje tienen valores iguales o diferentes; el sexto bit podría hacer lo mismo para los bits tres y cuatro, el séptimo para los bits uno y tres y el octavo para los bits dos y cuatro. Si uno de los primeros cuatro bits se invierte, los últimos cuatro pueden identificarlo; si uno de los últimos cuatro bits se invierte, los otros tres pueden transmitir suficiente información para compensarlo.

El artículo de Shannon, sin embargo, evita tales cavilaciones sobre cómo construir realmente códigos. En cambio, se acerca al concepto de corrección de errores analizando estadísticamente las propiedades generales de los códigos seleccionados completamente al azar. Para tener una idea de su enfoque, podría ser útil ver cómo podría aplicarse a nuestras hipotéticas secuencias de ocho bits que codifican mensajes de cuatro bits.

Hay 16 posibles mensajes de cuatro bits, y el método de Shannon asignaría a cada uno de ellos su propio número de serie de ocho bits seleccionado al azar: su palabra de código. El receptor, como el remitente, tendría un libro de códigos que correlacionara los 16 mensajes posibles de cuatro bits con las 16 palabras de código aleatorias de ocho bits. Dado que hay 256 posibles secuencias de ocho bits, hay 240 que no aparecen en el libro de códigos. Alguien que reciba una de esas 240 secuencias sabrá que se ha infiltrado un error en los datos. Pero siempre que las 16 palabras de código permitidas sean lo suficientemente diferentes entre sí, es probable que solo haya una que se acerque más a la secuencia dañada. Por ejemplo, si 00000001 y 11111110 son palabras de código válidas pero 00000011 no lo es, entonces alguien que reciba la secuencia 00000011 puede concluir que es mucho más probable que la palabra de código deseada sea 00000001 que 11111110.

En la vida real, por supuesto, a nadie le preocupa transmitir mensajes de solo cuatro bits. Pero mediante el uso del análisis estadístico, Shannon pudo sacar conclusiones sobre mensajes codificados de cualquier longitud, enviados a través de canales con cualquier cantidad de ruido. En particular, pudo cuantificar rigurosamente tanto el grado de diferencia entre las palabras de código seleccionadas al azar como la probabilidad de que una secuencia corrupta se pareciera solo a una de ellas. Si bien la probabilidad de que dos secuencias de ocho bits sean similares es relativamente alta, Shannon mostró que a medida que las palabras de código se alargan, las posibilidades de similitud disminuyen exponencialmente. De hecho, uno de sus resultados más sorprendentes fue que para los mensajes largos, la mayoría de las palabras de código asignadas al azar serán casi tan diferentes entre sí como sea posible. Eso significa que casi cualquier esquema de codificación, cualquier forma de generar esas palabras, permitiría una transmisión sin errores a través de un canal ruidoso a una velocidad cercana a la máxima.

Se necesitó mucha intuición para pensar que un código perfectamente aleatorio podría ser un código bastante bueno en promedio, dice David Forney, SM '63, ScD '65, ex vicepresidente de Codex Corporation y Motorola que regresó al MIT en 1996 como profesor adjunto. Resulta que eso simplifica drásticamente el análisis, porque ahora puede hacer un análisis de caso promedio. Forney hace una pausa por un momento, luego agrega: No quiere decir que fuera totalmente simple: tuvo que inventar al menos algunos teoremas, si no ramas de las matemáticas. Pero Gallager está de acuerdo. Sobre el artículo de 1948 de Shannon, dice: Después de estudiarlo durante dos años, parece muy simple. Mucha gente te dirá: 'Es realmente muy simple'. Y después de que lo entiendas, lo es.

Un desafío irresistible

La descripción matemática de Shannon de la información tenía muchas ramificaciones. Su artículo de 1948 también introdujo la idea de compresión de datos, o representar la misma información con menos bits; La compresión es lo que permite a programas como WinZip o StuffIt reducir los archivos para que no abrumen los servidores de correo electrónico, y se utiliza para ahorrar espacio en las unidades de disco. La teoría de la información también colocó el estudio de la criptografía sobre una base matemática más segura; de hecho, Gallager cree que fue el trabajo criptográfico de Shannon en tiempos de guerra en Bell Labs lo que lo llevó a su nueva concepción de la comunicación.

Sin embargo, cuando Shannon regresó al MIT, había comenzado a sentir que el entusiasmo que rodeaba su teoría excedía incluso sus considerables méritos. En un artículo de 1956 llamado The Bandwagon, citó intentos de aplicar la teoría de la información a campos como la biología, la psicología, la lingüística, la física fundamental, la economía, la teoría de la organización y muchos otros, y se comprometió a inyectar una nota de moderación en esta situación.

El disgusto de Shannon por el centro de atención rozaba la reclusión. Según Joel West '79, profesor de la Facultad de Negocios de la Universidad Estatal de San José que está escribiendo un libro sobre el desarrollo de la teoría de la información, Shannon asesoró solo a siete estudiantes graduados durante sus 22 años en el MIT. Era bastante tímido y retraído, así que si querías contratarlo como supervisor, realmente tenías que ser bastante agresivo al respecto, dice Gallager. Yo también era tímido y retraído, y no tenía suficiente confianza en mí mismo como para entrar y hablar con el chico.

Como maestra, Shannon tenía poca paciencia para el tedio de lo familiar. Estaba mucho más interesado en lo nuevo que en lo antiguo, dice Elwyn Berlekamp '62, SM '62, PhD '64, profesor emérito de matemáticas en la Universidad de California, Berkeley, quien (con Gallager) fue coautor de Shannon's artículo final publicado.

No enseñó mucho, dice Gallager. Pero cuando enseñaba, era como dar charlas de investigación. Recuerdo una vez que dio un curso, que consistió en aproximadamente 25 conferencias durante el trimestre, y cada conferencia fue un nuevo resultado de investigación. Los hacía uno tras otro y nunca dejaba de pensar en algo interesante. Fue un período realmente fantástico.

Shannon estaba, en mi opinión, un poco fuera de lugar en el mundo académico, dice James L. Massey, SM ‘60, PhD ‘62, teórico de la información y profesor emérito en ETH Zurich. Su verdadero género era ser un investigador independiente y hacer las cosas a su manera, altamente individualista.

También puede ser que Shannon se sintiera simplemente incómoda con la adulación. Berlekamp recuerda cuando la Sociedad de Teoría de la Información IEEE invitó a Shannon a dar una conferencia y recibir su Premio Shannon inaugural en Israel en 1973. Nunca había visto a nadie con más mariposas que él, dice. Cinco minutos antes de que empiece la charla, él está en el bar y está bastante deprimido. Tiene mucho miedo de subir al escenario y decepcionar a todo el mundo. Porque, por supuesto, esperan a Dios, lo cual es cierto, y él sabe que no puede actuar como Dios.

Pero si Shannon rara vez era un mentor directo de los jóvenes estudiantes de teoría de la información, les había planteado un desafío irresistible. La codificación aleatoria nunca funcionaría en la práctica: el tamaño del libro de códigos hipotético de Shannon se duplicó con cada bit adicional en el mensaje. El libro de códigos para un solo paquete de datos de 1.000 bits que viaja a través de Internet requeriría más entradas que átomos en el universo. Pero cualquier mecanismo de codificación más práctico, como repetir el mensaje original o agregar bits adicionales que describieran los bits del mensaje, era equivalente a algún esquema de codificación aleatorio, en el sentido de que generaría las mismas palabras de código. Y al demostrar que la gran mayoría de los esquemas de codificación aleatoria se acercaban a la capacidad, Shannon ofreció la esperanza de que uno de los prácticos también lo fuera.

Códigos esquivos

En lugar de utilizar un libro de códigos para hacer coincidir las palabras de código y los mensajes, un esquema de codificación práctico proporcionaría una forma de extraer el mensaje de las palabras de código de forma computacional. Una serie de operaciones matemáticas podría, con una alta probabilidad de precisión, identificar y corregir errores en una secuencia de bits posiblemente corrupta recibida a través de un canal ruidoso.

Una de las peculiaridades de los códigos de corrección de errores es que un buen algoritmo de codificación no implica necesariamente un buen algoritmo de decodificación. Utilizando análisis estadísticos similares a los de Shannon, los teóricos de la codificación pudieron demostrar que un código dado se acercaba a la capacidad, que maximizaría la diferencia entre palabras de código. Pero eso no significaba que tuvieran una forma eficiente de decodificarlo.

Entre la publicación del artículo de Shannon y principios de la década de 1990, los investigadores propusieron códigos cada vez mejores y también algoritmos de decodificación cada vez mejores. Pero un código práctico que se acercara a la capacidad seguía siendo difícil de alcanzar. Solía ​​haber un dicho entre los teóricos de la codificación, dice Forney, que casi cualquier código es bueno, excepto todos los que se nos ocurren.

Los códigos que Gallager presentó en su tesis doctoral de 1960 fueron un intento de preservar algo de la aleatoriedad del sistema hipotético de Shannon sin sacrificar la eficiencia de decodificación. Como muchos códigos anteriores, Gallager utilizó los llamados bits de paridad, que indican si algún otro grupo de bits tiene sumas pares o impares. Pero los códigos anteriores generaban los bits de paridad de manera sistemática: el primer bit de paridad podría indicar si la suma de los bits de mensaje del uno al tres era par; el siguiente bit de paridad podría hacer lo mismo para los bits de mensaje del dos al cuatro, el tercero para los bits del tres al cinco, y así sucesivamente. En los códigos de Gallager, por el contrario, la correlación entre los bits de paridad y los bits de mensaje era aleatoria: el primer bit de paridad podría describir, digamos, la suma de los bits de mensaje 4, 27 y 83; el siguiente podría hacer lo mismo para los bits de mensaje 19, 42 y 65.

Gallager pudo demostrar matemáticamente que para mensajes largos, sus códigos pseudoaleatorios se acercaban a la capacidad. Excepto que sabíamos otras cosas que también se acercaban a nuestra capacidad, dice. Nunca fue una cuestión de qué códigos eran buenos. Siempre fue una cuestión de qué tipo de algoritmos de decodificación podría idear.

Ahí fue donde Gallager hizo su gran avance. Sus códigos usaban decodificación iterativa, lo que significa que el decodificador pasaría los datos varias veces, haciendo conjeturas cada vez más refinadas sobre la identidad de cada bit. Si, por ejemplo, los bits de paridad describían tripletes de bits, entonces la información confiable sobre dos bits cualesquiera podría transmitir información sobre un tercero. El algoritmo de decodificación iterativa de Gallager es el que se usa más comúnmente en la actualidad, no solo para decodificar sus propios códigos sino, con frecuencia, también para decodificar códigos turbo. También ha encontrado aplicación en el tipo de razonamiento estadístico utilizado en muchos sistemas de inteligencia artificial.

Las técnicas iterativas implican hacer una primera suposición de lo que podría ser un bit recibido y darle un peso de acuerdo con su confiabilidad, dice Forney. Entonces, tal vez obtenga más información al respecto porque está involucrado en verificaciones de paridad con otros bits, y eso le brinda una estimación mejorada de su confiabilidad. En última instancia, dice Forney, las conjeturas deberían converger hacia una interpretación coherente de todos los bits del mensaje.

Aunque Gallager no había podido reunir el valor para pedirle a Shannon que fuera su asesor, dice que sí habló con Shannon tres o cuatro veces mientras escribía su tesis. Excepto que hablar con Claude tres o cuatro veces era como hablar con la mayoría de las personas 50 veces, dice. Fue alguien que realmente se dio cuenta de las ideas muy, muy rápido. No estuvo muy bien en todos los detalles técnicos. Pero ver la estructura de algo, ver por qué debería funcionar y ver qué podría mejorarlo, bueno, ciertamente era la persona más inteligente que he conocido.

Aun así, Shannon no previó el éxito de los códigos de Gallager. Lo que recuerdo es que pensó que eran interesantes, pero yo no tenía la sensación de que estuviera emocionado por ellos, dice Gallager. Entiende por qué. Los códigos de Gallager se acercaban a la capacidad del canal a medida que se alargaban; pero a medida que se alargaban, el proceso de decodificación también se hacía más complejo, demasiado complejo para las computadoras de la época. Los investigadores de codificación sabían, por supuesto, que las computadoras mejorarían. Pero nadie sabía a qué códigos favorecerían esas mejoras.

No obstante, el MIT contrató inmediatamente a Gallager como miembro de la facultad sobre la base de su tesis. En los años siguientes, mientras su propio esquema de codificación languidecía en la oscuridad, enseñó y fue mentor de una ola de estudiantes brillantes, incluidos Massey, Forney y Berlekamp, ​​cuyas contribuciones a la teoría de la codificación tuvieron implicaciones prácticas más inmediatas que las suyas.

Gallager, sin embargo, parece tan imperturbable por el largo descuido de sus códigos como por su reciente resurgimiento, tal vez porque siempre tuvo una visión a largo plazo. Tiene la habilidad de inventar cosas que permanecen inactivas durante decenas de años hasta que la gente de repente se da cuenta de que son cosas bastante buenas, dice Vincent Chan '71, MS '71, EE '72, PhD '74, profesor de ingeniería eléctrica que todavía muestra por su escritorio la placa de la puerta de la oficina que una vez compartió con Shannon. Chan recuerda una visita reciente a los laboratorios de una importante empresa de software, donde un investigador se jactaba de una nueva técnica de compresión que permitiría que los archivos de video ocuparan solo una centésima parte de la memoria que ocupan ahora. Chan se sintió obligado a señalar que Gallager había introducido la técnica en 1974. Muchas de estas ideas requieren bastante tiempo para pensarlas, dice, y en el momento en que las está analizando, hay muchas, muchas opciones. . Y realmente tienes que pensar con mucho cuidado y tal vez durante un largo período de tiempo antes de descubrir cuál es el correcto. Bob hace mucho eso.

Muriel Médard '89, '90, MS '91, ScD '95, teórica de la información en el Laboratorio de Investigación de Electrónica, está de acuerdo. Bob no andaba de un lado para otro tratando de publicar y asegurarse de que no lo atrapara, dice ella. Por ejemplo, Médard recuerda una conversación entre Gallager y un destacado teórico de la información más joven, quien al describir su propio trabajo citó un teorema recientemente probado en el que se basó. Bob comienza a hurgar en las cosas, como lo hace, dice Médard. Finalmente, sacó una copia hecha jirones de uno de sus propios papeles. Tenía esta pequeña prueba diminuta, dice Médard. Y fue como una nota a pie de página. Una nota a pie de página gruesa, pero una nota a pie de página. '¿Le pusieron ese nombre?' 'Sí, Bob, ahora es un teorema importante'.

Hoy en día, los códigos de Gallager son la base de los enfoques que se acercan más a la velocidad máxima de datos para un canal de comunicación dado, más cerca incluso que los códigos turbo. Además de sus aplicaciones en telecomunicaciones, están comenzando a reemplazar los códigos más antiguos utilizados para proteger datos en unidades de disco y otros dispositivos de almacenamiento.

Para personas como Forney, que estuvieron en el MIT durante lo que él llama la edad de oro de la teoría de la codificación, el hecho de que se haya superado el desafío planteado por el artículo de 1948 de Shannon es algo agridulce. Aquellos de nosotros que conocemos y amamos la codificación somos reacios a decir que el problema se ha resuelto por completo, dice Forney. Pero es cierto que la mayoría de la gente ha pasado a otras cosas.

De 1950 a 1965, el MIT fue el semillero de la teoría de la información, dice Joel West. Realmente fue una edad de oro.

esconder