O algoritmo de Viterbi fez com que todo telefone celular decodificasse o próprio sinal

A comunicação digital por um enlace sem fio é uma batalha contra o ruído, que pode corromper os bits que uma antena recebe. A correção óbvia é adicionar código de correção de erros, mas decodificá-lo exige uma maneira de descobrir, a partir de um fluxo recebido com ruído, qual mensagem foi realmente enviada.

O algoritmo de Viterbi de 1967 fez exatamente isso. Um codificador convolucional restringe o transmissor a percorrer um conjunto finito de estados, e o receptor mantém uma treliça desses estados; a cada passo, ele mantém apenas o caminho mais barato para cada estado, de modo que, ao final, encontrou a única mensagem mais provável em vez de escolher cada bit independentemente.

Ao tornar viáveis códigos práticos de comprimento de restrição curto, o algoritmo tornou a correção de erros antecipada barata o suficiente para ser implantada em rádios reais. Ele transformou um vago "qual foi a mensagem?" em uma busca limpa por programação dinâmica, e hoje é usado para separar voz e dados do ruído de fundo.

Escolher a sequência oculta de estados mais provável

Manter apenas o único caminho mais barato para cada estado faz com que a busca leve tempo linear no comprimento da mensagem.

Ele recupera a sequência de máxima verossimilhança a partir de dados ruidosos sem adivinhação bit a bit.

Os códigos convolucionais só ganham poder real de correção de erros quando decodificados dessa maneira.

Quando um sinal estiver ruidoso demais para ser lido diretamente, reconstrua a única sequência mais provável da qual ele pode ter vindo; a estrutura que você adicionou torna essa busca quase sem esforço.

O algoritmo de Viterbi é usado na grande maioria dos telefones celulares do mundo e em receptores de satélite, gravação magnética, reconhecimento de fala e análise de DNA; Viterbi passou a cofundar a Qualcomm em 1985, e o algoritmo ajudou a tornar viáveis o CDMA e a telefonia celular digital.