Curiosidades históricas da
codificação para controlo de erros

Aos poucos irei acrescentando aqui curiosidades interessantes do mundo dos códigos correctores de erros.

“Damn it, if the machine can detect an error, why can’t it locate the position of the error and correct it?” - desabafo de Richard Hamming (fins dos anos 40 do século passado). Em duas segundas-feiras seguidas aconteceu a Hamming que o programa que tinha deixado a correr durante o fim-de-semana no computador dos Laboratórios Bell, onde trabalhava, tinha parado ou encravado devido a erros.

Tão aborrecido ficou com estas perdas de tempo que... inventou os códigos correctores de erros agora conhecidos pelo seu nome. O de menores dimensões, (7,4), até parece uma nave espacial nesta representação com gráfico de factores:

Em 1947, dois anos antes de Marcel Golay ter publicado o seu código, a revista finlandesa de apostas desportivas Veikkaaja apresentava um artigo com um método de apostar no "Totobola" da Finlândia que era nem mais nem menos que o código de Golay ternário corrector de erros duplos (11, 6). Claro que o autor, J. Virtakkalio, não sonhava com códigos correctores de erros quando pensou no Totobola!

	O termo "síndrome" é devido a D. W. Hagelbarger (1959).
	Foi David Slepian quem em 1956 apresentou a matriz padrão pela primeira vez. O mesmo Slepian tocava oboé como músico amador.
	A tese de doutoramento de Robert Gallager (MIT, 1962) foi supervisionada por Peter Elias, o inventor dos códigos convolucionais em 1955. Quem também reviu a tese? Fano e Wozencraft. Gente grande!
	Irving Reed, co-autor dos códigos de Reed-Muller e Reed-Solomon, ainda andava no Ensino Secundário e já frequentava aulas na Universidade de Fairbanks, no Alasca, onde vivia então.
	A Identidade de MacWilliams surgiu na tese de doutoramento da matemática inglesa Jessie MacWilliams em Harvard, em 1962, tinha ela 45 anos. Uma filha estudava em Harvard nessa mesma altura.

O primeiro aparecimento da palavra "survivor" na descodificação convolucional deve-se a Andrew Viterbi, naturalmente. No seu famoso artigo de 1967 (porquê famoso, já agora?!), pode ler-se: "Let the path corresponding to the greatest likelihood function in each comparison be denoted the survivor."

As treliças ("trellises") - quer o termo quer o gráfico - foram usadas pela primeira vez por Dave Forney, Jr. também em 1967, num relatório final de projecto com a NASA (ver ref. [62]), ao analisar e descrever o algoritmo de Viterbi. Ou seja, o próprio Viterbi não usou treliças no artigo em que apresentou o seu algoritmo, uns meses antes, como se pode comprovar ao lê-lo. Mas o algoritmo explica-se muito melhor com treliças, como muito bem fez Forney... este mesmo:

Trinta e oito anos depois, em Março de 2005, Dave Forney fez um pequeno levantamento sobre as aplicações do algoritmo de Viterbi e concluiu que nas revistas do IEEE a maior parte das referências mais recentes ao algoritmo surgem... onde...? Nas Transactions on Communications? Não, nas Transactions on Pattern Analysis and Machine Intelligence e Systems, Man and Cybernetics! Além das suas múltiplas aplicações em telecomunicações (onde? pegue no seu telemóvel...), hoje em dia o algoritmo também é aplicado em áreas tão díspares como o reconhecimento de voz e a bioinformática (no processamento de sequências de ADN).

Dos códigos convolucionais ao ADN: mas que caminho! Que percurso sobrevivente!

	Ainda a propósito de Viterbi: o seu algoritmo mereceu-lhe mais um prémio, a medalha Benjamin Franklin de 2005, atribuída pelo Franklin Institute de Filadélfia, "one of the United States' oldest centers of science education and development". (veja aqui a notícia).
	Foi Jim Massey quem deu o nome aos códigos catastróficos e à distância livre. Sempre simpático, aqui está ele há uns bons anos atrás:

	Quando a sonda espacial Voyager foi lançada pela NASA em 1977 não havia descodificadores de Reed-Solomon (RS) adequados. Só perto de Urano, em 1986, quando a tecnologia e a evolução dos algoritmos finalmente permitiram construir um codificador RS (255, 223) em Terra, é que a sonda passou a usar o codificador RS que levara (até então teve de usar um codificador de Golay).
	Gottfried Ungerboeck, da Áustria, é conhecido por ter inventado o importante método TCM ("trellis coded modulation"). Poucos saberão que uns dez anos antes, na sua tese de doutoramento (1971), ele aplicara os algoritmos da soma-e-produto e "min-sum" em igualização não linear. Precursor, sem dúvida...
	Não se contava com isso mas a verdade é que em 25 de Maio de 1993 uma revolução foi anunciada em Genebra (clique na imagem abaixo para a ver maior. Ora procure a apresentação 44.3!).

	"Procedé de codage correcteur d'erreurs à au moins deux codages convolutifs systématiques parallèles, procedé de décodage iteratif, module de décodage et decodeur correspondants": o que parece ser isto? É o título da patente francesa nº FR-9 105 280 (turbo-códigos). Quer ver a patente americana? Então vá até aqui...
	Olha quem fala!!

“Turbo codes [...] are one of the most exciting and potentially important developments in coding theory in many years”

S. Benedetto, D. Divsalar e J. Hagenauer, IEEE Journal on Selected Areas in Communications, Fev. 1998

Acertaram em cheio.

Outra frase, esta sobre os códigos LDPC:

“If the art of simulation had been more advanced in 1963, the history of coding theory might look very different today”

A. R. Calderbank, “The Art of Signaling: fifty years of coding theory”, IEEE Trans. Information Theory, Oct. 1998.

	Peter Elias morreu em 2001 aos 78 anos da doença de Kreutzfeld-Jacob, a variante humana da "doença das vacas loucas".
	Claude Shannon morreu em 2001 aos 85 anos com a doença de Alzheimer. Elias, Shannon...
	Frases mais ou menos célebres “Deep-space communication and coding: a marriage made in heaven” J. L. Massey, Lecture Notes on Control and Information Sciences 82, J. Hagenauer (ed.), Bonn, Germany, Springer-Verlag, 1992. “All codes are good, except those that we know of” Anónimo (que eu saiba) “Never discard information prematurely that may be useful in making a decision until after all decisions related to that information have been completed” A. J. Viterbi, “Wireless Digital Communication: a View Based on Three Lessons Learned”, IEEE Communications Magazine, Sept. 1991.

Página inicial

Curiosidades históricas da codificação para controlo de erros

Curiosidades históricas da
codificação para controlo de erros