El algoritmo de Viterbi hizo que cada teléfono móvil decodificara su propia señal

La comunicación digital por un enlace inalámbrico es una batalla contra el ruido, que puede corromper los bits que recibe una antena. La solución obvia es añadir código corrector de errores, pero decodificarlo requiere una forma de determinar, a partir de un flujo recibido con ruido, qué mensaje se envió realmente.

El algoritmo de Viterbi de 1967 hizo exactamente eso. Un codificador convolucional obliga al transmisor a moverse por un conjunto finito de estados, y el receptor mantiene una retícula de esos estados; en cada paso conserva solo la ruta más barata hacia cada estado, de modo que al final ha encontrado el único mensaje más probable en lugar de elegir cada bit de forma independiente.

Al hacer viables los códigos prácticos de longitud de restricción corta, el algoritmo hizo que la corrección de errores hacia adelante fuera lo bastante barata como para desplegarla en radios reales. Convirtió un vago «¿cuál era el mensaje?» en una búsqueda limpia de programación dinámica, y ahora se usa para separar la voz y los datos del ruido de fondo.

Elegir la secuencia oculta de estados más probable

Conservar solo la única ruta más barata hacia cada estado hace que la búsqueda tarde un tiempo lineal respecto a la longitud del mensaje.

Recupera la secuencia de máxima verosimilitud a partir de datos con ruido sin conjeturas bit a bit.

Los códigos convolucionales solo ganan verdadera capacidad de corrección de errores cuando se decodifican de esta manera.

Cuando una señal tiene demasiado ruido para leerla directamente, reconstruye la única secuencia más probable de la que podría haber provenido; la estructura que añadiste hace que esa búsqueda sea casi trivial.

El algoritmo de Viterbi se usa en la gran mayoría de los teléfonos móviles del mundo y en receptores de satélite, grabación magnética, reconocimiento de voz y análisis de ADN; Viterbi cofundó Qualcomm en 1985, y el algoritmo ayudó a hacer viables la CDMA y la telefonía celular digital.