As minhas referências bibliográficas de
Teoria da Informação e Códigos Correctores de Erros
(* - bibliografia para a cadeira "EEC4289 - Teoria da Informação", FEUP)
Livros (por ordem alfabética do autor)
* Sílvio A. Abrantes, Apontamentos de Teoria da Informação, FEUP, 2003.
O título diz tudo: trata-se dos acetatos (que pouco uso, na verdade) para as aulas teóricas da cadeira. São de leitura fundamental, claro!
* Sílvio A. Abrantes, Codificação de fonte: duas breves visitas, FEUP Edições, 2000.
Duas abordagens leves da codificação aritmética e dos códigos de Lempel-Ziv. Em música chamar-lhe-ia um "divertimento".
J. B. Anderson, Digital Transmission Engineering, IEEE Press/Prentice‑Hall, 1999.
R. Blahut, Theory and Practice of Error Control Codes, Addison‑Wesley, 1983.
R. Blahut, Principles and Practice of Information Theory, Addison‑Wesley, 1987.
R. Blahut, Digital Transmission of Information, Addison‑Wesley, 1990.
* A. B. Carlson, P. B. Crilly e J. C. Rutledge, Communication Systems, McGraw-Hill, 2001, 4ª Edição.
* T. M. Cover e J. A. Thomas, Elements of Information Theory, Wiley-Interscience, 1991.
Na actualidade este é, provavelmente, o melhor livro sobre Teoria da Informação.
R. G. Gallager, "Low-density parity-check codes," Monograph, M.I.T. Press, 1963. (Tese de Doutoramento)
Bob Gallager inventou os códigos LDPC aqui! Mas, como apareceram "antes do tempo", ficaram adormecidos muitos, muitos anos… Os turbo-códigos ressuscitaram-nos com imenso vigor trinta anos depois.
* R. G. Gallager, Information Theory and Reliable Communication, John Wiley, 1968.
Apesar da idade este livro ainda é uma das "bíblias" da Teoria da Informação.
R. Gitlin, J. Hayes e S. Weinstein, Data Communication Principles, Plenum Press, 1992.
L. Hanzo, T.H. Liew e B.L. Yeap, Turbo Coding, Turbo Equalisation and Space-Time Coding for Transmission over Fading Channels, John Wiley, 2002.
Contém muito material sobre o "princípio turbo". Moderno e muito recomendado.
* S. Haykin, Communication Systems, John Wiley, 2001, 4ª Edição.
Um dos melhores livros de texto de telecomunicações, juntamente com o de Sklar. Amplamente usado em inúmeras universidades de todo o mundo.
C. Heegard e S. B. Wicker, Turbo Coding, Kluwer Academic Publishers, 1999.
D. A. Lelewer e D. S. Hirschberg, Data Compression, ACM Computing Surveys, Setembro de 1987.
* S. Lin e D. Costello, Error Control Coding, 2ª Edição, Prentice‑Hall, 2004.
A primeira edição, de 1983, é um dos meus livros de referência sobre códigos de controlo de erros.
A. Michelson e A. Levesque, Error‑Control Techniques for Digital Communication, John Wiley, 1985.
Outra referência clássica sobre códigos de controlo de erros.
M. Nelson e J.-L. Gailly, The Data Compression Book, M&T Books, Nova Iorque, 1996, 2ª Edição.
Jean-Loup Gailly é o inventor dos códigos de compressão zip e gzip.
* J. R. Pierce, An Introduction to Information Theory, Dover, 1980, 2ª Edição.
Escrito por um importante e influente contemporâneo de Shannon, este fascinante livro de agradável leitura (sem matemática, "para ler na cama") mostra-nos as diferentes facetas da Teoria da Informação. Gosto dele. Altamente recomendado apesar da idade.
J. G. Proakis, Digital Communications, McGraw‑Hill, 1989, 2ª Edição.
O famoso "Proakis". O nível do livro é de pós-graduação.
K. Sayood, Introduction to Data Compression, Morgan Kaufmann Publishers, San Francisco, 1996.
C. Schlegel e L. Perez, Trellis and Turbo Coding, Wiley-IEEE Press, 2003.
Óptimo livro sobre os turbo-códigos. Muito actual.
* M. Schwartz, Information Transmission, Modulation and Noise, McGraw‑Hill, 1981, 3ª Edição.
* B. Sklar, Digital Communications, Prentice‑Hall, 2001, 2ª Edição.
Este e o livro de Haykin ("Communication Systems") são hoje, provavelmente, os dois melhores livros de texto genéricos de Telecomunicações.
P. Sweeney, Error Control Coding: from theory to practice, Wiley, 2002.
Interessante livro de um autor britânico, com uma abordagem diferente da americana.
Artigos clássicos (por ordem cronológica)
* Claude E. Shannon, "A Mathematical Theory of Communication", The Bell System Technical Journal, Vol. 27, pp. 379–423, 623–656, Julho e Outubro de 1948.
Pai, mãe, avô, avó, o que se quiser, da Teoria da Informação. Foi aqui que "tudo" começou!! O artigo, longo, continua muito actual, nada datado.
Este artigo também pode ser encontrado em http://cm.bell-labs.com/cm/ms/what/shannonday/paper.html em formatos pdf, PostScript e gzipped PostScript.
M. J. E. Golay, "Notes on digital coding," Proc. IRE, vol. 37, p.637, Junho de 1949.
Assim nasceu o código de Golay, um dos primeiros códigos a ser inventado, neste artigo de meia página!
David A. Huffmann, “A method for the construction of minimum redundancy codes”, Proceedings of the IRE, Setembro de 1952.
Assim nasceu o código de Huffman, neste artigo de apenas quatro páginas!
R. G. Gallager, "Low-density parity-check codes," IRE Transactions on Information Theory, vol. IT-8, pp. 21-28, Janeiro de 1962.
Versão abreviada da tese de doutoramento (ver acima). Primeira aparição pública dos códigos LDPC.
Foi aqui que surgiu a ideia dos códigos concatenados.
A. Viterbi. "Error bounds for convolutional codes and an asymptotically optimum decoding algorithm", IEEE Transactions on Information Theory, pp. 260-269, Abril de 1967.
Nascimento do algoritmo de Viterbi.
L.R. Bahl, J. Cocke, F. Jelinek , J. Raviv. "Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate", IEEE Transactions on Information Theory, IT-20, Março de 1974, pp. 284-287.
Artigo de apresentação do algoritmo MAP ou BCJR (Bahl, Cocke,...). Na época (1974) era apenas uma alternativa ao algoritmo de Viterbi mas, como era muito mais complexo, não era usado. Renasceu com os códigos turbo, que o usam de forma iterativa. Hoje em dia é dos algoritmos mais usados. Não admira!
J. Ziv e A. Lempel, “A universal algorithm for sequential data compression”, IEEE Transactions on Information Theory, Maio de 1977.
O código de compressão LZ77 nasceu aqui!
J. Ziv e A. Lempel, “Compression of individual sequences via variable rate coding”, IEEE Transactions on Information Theory, Setembro de 1978.
O código de compressão LZ78 nasceu aqui!
R. M. Tanner, “A recursive approach to low complexity codes", IEEE Transactions on Information Theory, Vol. IT-27, nº 5, Setembro de 1981, pp. 533-547.
A quem se devem os "gráficos de Tanner"? Foi aqui que apareceram.
T. Welch, “A technique for high performance data compression”, IEEE Computer, Junho de 1984.
O código de compressão LZW nasceu aqui!
C. Berrou, A. Glavieux e P. Thitimajshima, "Near Shannon limit error-correcting coding and decoding," Proceedings of the International Conference on Communications (ICC '93), Maio de 1993, pp. 1064-1070.
Nascimento dos turbo-códigos! Foi o início de uma "revolução" e aconteceu em Genebra. Para mim é o mais influente artigo das últimas décadas no domínio da codificação para correcção de erros. Os autores principais, Berrou e Glavieux, publicaram mais tarde uma versão alargada desta apresentação (ver mais abaixo).
D. J. C. MacKay e R. M. Neal, "Good Codes based on Very Sparse Matrices", Cryptography and Coding, 5th IMA Conference, Colin Boyd (ed.), Lecture Notes in Computer Science, nº 1025, pp. 100-111, 1995, Springer, Berlim.
Assim ressuscitaram os códigos LDPC. Ver versão abreviada mais adiante (1996).
C. Berrou e A. Glavieux, "Near optimum error correcting coding and decoding: Turbo-codes", IEEE Transactions on Communications, Vol. 44, N° 10, Outubro 1996, pp. 1261-1271. © 1996 IEEE.
D. J. C. MacKay e R. M. Neal, “Near Shannon limit performance of low density parity check codes”, Electronics Letters, vol. 32, nº 18, Agosto de 1996, pp. 1645-1646, reimpresso no vol. 33, nº 6, Março de 1997, pp. 457 458.
Versão muito abreviada do artigo que fez renascer os códigos LDPC.
Também este artigo ajudou a ressuscitar os códigos LDPC.
J. Hagenauer, "The turbo principle: Tutorial introduction and state of the art", Proceedings of the 1st International Symposium on Turbo Codes, Brest, França, Setembro de 1997, pp. 1-11.
Artigo fundamental e muito citado sobre o princípio turbo.
S. ten Brink, "Convergence of iterative decoding", Electronics Letters, vol. 35, nº 10, pp. 806–808, Maio de 1999.
Artigo onde os "EXIT Charts" foram apresentados pela primeira vez.
F. R. Kschischang, B. J. Frey e H.-A. Loeliger, "Factor graphs and the sum-product algorithm", IEEE Transactions on Information Theory, Vol. 47, nº 2, Fevereiro de 2001, pp. 498-519.
Referência fundamental dos gráficos de factores.
Aqui apareceu a técnica da "density evolution" usada na descodificação iterativa.
S. Y. Chung, G. D. Forney, Jr., T. J. Richardson e R. Urbanke, “On the Design of Low-Density Parity-Check Codes within 0.0045 dB of the Shannon Limit”, IEEE Communications Letters, Vol. 5, nº. 2, Fevereiro de 2001, pp. 58 60.
Usando "discretized density evolution" e códigos LDPC irregulares, os autores conseguiram aproximar-se muitíssimo do limite de Shannon. Ninguém o conseguira tanto antes.
H.-A. Loeliger, "An introduction to factor graphs", IEEE Signal Processing Magazine, Janeiro de 2004, pp. 28-41.
Também este artigo é uma referência inescapável dos gráficos de factores.
Artigos
mais… didácticos (ou nem tanto)
(por ordem alfabética do
autor)
* V. Barghava, "Forward Error Correction Schemes for Digital Communications", IEEE Communications Magazine, Janeiro de 1983.
S. Benedetto, G. Montorsi e D. Divsalar, "Concatenated Convolutional Codes with Interleavers", IEEE Communications Magazine, Agosto de 2003, pp- 102-109.
Altamente recomendado. Os autores são dos mais activos na investigação de turbo-códigos e sabem bem do que falam.
* E. Berlekamp, R. Peile e S. Pope, "The Application of Error Control to Communications", IEEE Communications Magazine, Abril de 1987.
C. Berrou e A. Glavieux, "Reflections on the Prize paper: 'Near optimum error correcting coding and decoding: Turbo codes'", IEEE Information Theory Society Newsletter, Vol. 48, N° 2, Junho 1998. © 1998 IEEE
Os inventores dos códigos turbo contam como eles apareceram. Dizem, do Francês para o Inglês, que o fizeram "using existing bricks that had never been put together in this way before". Vale a pena ler este relato de um acontecimento histórico na primeira pessoa.
* A. Burr, "Turbo-codes: the ultimate error control codes?" Electronics and Communication Engineering Journal, Agosto de 2001, pp. 155-165.
Não sabe o que são códigos turbo? Este artigo, de bonita apresentação e sem uma única fórmula ou equação, ajuda-o a aumentar o seu nível de cultura.
D. Divsalar, S. Dolinar e F. Pollara, "Iterative Turbo Decoder Analysis Based on Density Evolution", IEEE Journal on Selected Areas in Communications, Vol. 19, nº 5, Maio de 2001, pp. 891-907. © 2001 IEEE
Inicialmente publicado como um relatório de progresso (TMO PR 42-144) no Jet Propulsion Laboratory (CalTech), este artigo relata as experiências dos autores sobre a evolução, ao longo das iterações, das funções densidade de probabilidade das informações extrínsecas e das relações sinal-ruído que ocorrem na descodificação iterativa de códigos turbo e LDPC.
* P. Farrell, "Coding as a cure for communication calamities", Electronics & Communication Engineering Journal, 6, (2), 1990.
G. David Forney, Jr., "The Viterbi Algorithm: a Personal History", Viterbi Conference, University of Southern California, Los Angeles, 8 de Março de 2005, arXiv:cs.IT/0504020 v2, 29 Apr 2005.
A. Viterbi inventou o algoritmo mas Forney teve um papel preponderante na sua divulgação e compreensão. Este artigo, escrito mais de trinta e cinco anos depois do artigo original de Viterbi, é uma interessante história pessoal de convivência com A. V. e o seu algoritmo e de influência sobre desenvolvimentos tecnológicos. Muitas aplicações fora das intenções originais de Viterbi são apresentadas. Recomendado.
P. F. Gallardo, "Códigos correctores de errores, quinielas y empaquetamientos", El lenguaje de las Matemáticas en sus aplicaciones (José Luis Fernández y Manuel de Lorenzo, editores), Instituto Superior de Formación del Profesorado (MEC), Espanha, 2001 (livro com os seminários apresentados no curso com o mesmo nome realizado na Universidad Menéndez Pelayo de Santander).
Escrito por um professor de matemática da Universidade Autónoma de Madrid, o artigo começa por conceitos muito simples da codificação para detecção e correcção de erros (exemplificados com os números fiscais de contribuinte espanhóis) e leva-nos depois, suavemente, à aplicação dessas técnicas às apostas desportivas (totobola) e ao empacotamento de esferas (ou... bolas, se não nos quisermos afastar do desporto).
O "princípio turbo" aplicado aos sistemas MIMO pelo inventor dos "EXIT charts", Stephan ten Brink. Inclui uma interessante apresentação do logaritmo jacobiano.
* S. Lin, D. Costello e M. Miller, "Automatic‑Repeat‑Request Error‑Control Schemes", IEEE Communications Magazine, Dezembro de 1984.
J. Massey, "Information Theory: the Copernican System of Communications", IEEE Communications Magazine, Dezembro de 1984.
Jim Massey é sempre interessante. Aqui também.
* J. Peek, "Communications Aspects of the Compact Disc Digital Audio System", IEEE Communications Magazine, Fevereiro de 1985.
* B. Sklar e Harris, F. J., "The ABCs of Linear Block Codes: An intuitive treatment of error detection and correction", IEEE Signal Processing Magazine, Julho de 2004.
Muito recente. Altamente recomendado. Sklar é Sklar…
B. Sklar, "Fundamentals of Turbo Codes", http://radio-1.ee.dal.ca/~ilow/4540/readings/art_sklar3_turbocodes.pdf (acedido em 15-4-05)
S. W. Smith, "Data Compression", capítulo do livro The Scientist and Engineer's Guide to Digital Signal Processing, California Technical Publishing, 1997.
As técnicas de compressão com e sem perdas expostas com leveza.
S. ten Brink, "Iterative Decoding Trajectories of Parallel Concatenated Codes", Proc. of 3rd IEEE/ITG Conference on Source and Channel Coding, Munique, Alemanha, Janeiro de 2000, pp. 75-80.
S. ten Brink apresenta de novo os seus "EXIT charts", agora com mais clareza.
N. Wiberg, H.-A. Loeliger e R. Kötter, "Codes and Iterative Decoding on General Graphs", European Transactions on Telecommunications and Related Technologies, Special Issue on Turbo Coding, Vol. 6, Setembro/Outubro de 1995, pp. 513-525.
* A. Wyner, "Fundamental Limits in Information Theory", Proceedings of the IEEE, Fevereiro de 1981.
Locais de consulta não faltam. Aqui coloco apenas dois ou três, que o Google dará uma ajuda eficaz e rapidíssima para encontrar outros.
http://www.reference.com/Dir/Science/Math/Information_Theory/, interessante Directório de páginas sobre Teoria da Informação
Entropy in Information and Coding Theory, de Chris Hillman. Muita informação.
The Error Correcting Codes (ECC) Page, de Robert Morelos-Zaragoza.
JPL Turbo Codes Page, do Laboratório de Propulsão a Jacto, Califórnia. NASA…
Esta lista bibliográfica nunca estará completa. Aos poucos irei acrescentando mais referências.