Cronologia della teoria dell'informazione

Questa voce contiene una cronologia di eventi legati alla  teoria dell'informazione, alla  informazione quantistica, alla  compressione dei dati, ai  codici di correzione degli errori e argomenti correlati.

• 1872 – Ludwig Boltzmann presenta il suo teorema H, e con esso la formula Σp_i log p_i per l'entropia di una singola particella di gas.
• 1878 – J. Willard Gibbs definisce l'entropia di Gibbs: le probabilità nella formula dell'entropia sono assunte ora come probabilità dello stato dell'intero sistema.
• 1924 – Harry Nyquist discute la quantificazione dell'"informazione" e la velocità alla quale essa può essere trasmessa da un sistema di comunicazione.
• 1927 – John von Neumann definisce l'entropia di von Neumann, estendendo l'entropia di Gibbs alla meccanica quantistica.
• 1928 – Ralph Hartley introduce l'informazione di Hartley come il logaritmo del numero dei possibili messaggi, con l'informazione che è comunicata quando il ricevente può distinguere una sequenza di simboli da una qualsiasi altra (indipendentemente da qualsiasi significato associato).
• 1929 – Leó Szilárd analizza il diavoletto di Maxwell, mostrando come un motore di Szilard può talvolta trasformare l'informazione nell'estrazione di lavoro utile.
• 1940 – Alan Turing introduce il deciban come misura delle informazioni dedotte sulle impostazioni del cifratore tedesco Enigma mediante il processo di Banburismo.
• 1944 – La teoria dell'informazione di Claude Shannon è sostanzialmente completa.
• 1947 – Richard W. Hamming inventa i codici di Hamming per la rilevazione e correzione d'errore. Per ragioni di brevetto, il risultato non è pubblicato fino al 1950.
• 1948 – Claude E. Shannon pubblica Una teoria matematica della comunicazione.[1]
• 1949 – Claude E. Shannon pubblica La comunicazione in presenza di rumore – Teorema del campionamento di Nyquist-Shannon e teorema di Shannon–Hartley.
• 1949 – La teoria della comunicazione nei sistemi crittografici di Claude E. Shannon è declassificata.
• 1949 – Robert M. Fano pubblica Transmission of Information. M.I.T. Press, Cambridge, Mass. – Codifica di Shannon-Fano.
• 1949 – Leon G. Kraft scopre la disuguaglianza di Kraft, che mostra i limiti dei codici prefissi.
• 1949 – Marcel J. E. Golay introduce i Codici di Golay per la correzione degli errori inoltrati.
• 1951 – Solomon Kullback e Richard Leibler introducono la divergenza di Kullback–Leibler.
• 1951 – David A. Huffman inventa la codifica di Huffman, un metodo per trovare codici prefissi ottimali per la compressione dati lossless.
• 1953 – August Albert Sardinas e George W. Patterson escogitano l'algoritmo di Sardinas–Patterson, una procedura per decidere se un determinato codice a lunghezza variabile è univocamente decodificabile.
• 1954 – Irving S. Reed e D.E. Muller propongono i codici di Reed-Muller.
• 1955 – Peter Elias introduce i codici convoluzionali.
• 1957 – Eugene Prange discute per la prima volta i codici di ridondanza ciclica.
• 1959 – Alexis Hocquenghem, e indipendentemente l'anno successivo Raj Chandra Bose e Dwijendra Kumar Ray-Chaudhuri, scoprono i codici BCH.
• 1960 – Irving S. Reed e Gustave Solomon propongono i codici di Reed-Solomon.
• 1962 – Robert G. Gallager propone i codici di controllo di parità a bassa densità; sono inutilizzati per 30 anni a causa di limitazioni tecniche.
• 1965 – Dave Forney discute i codici concatenati.
• 1967 – Andrea Viterbi inventa l'algoritmo di Viterbi, rendendo praticabile la decodifica dei codici convoluzionali.
• 1968 – Elwyn Berlekamp inventa l'algoritmo di Berlekamp–Massey; la sua applicazione alla decodifica dei codici BCH e di Reed-Solomon è messa in evidenza da James L. Massey l'anno seguente.
• 1968 – Chris Wallace e David M. Boulton pubblicano il primo di molti studi sull'inferenza statistica e induttiva della lunghezza minima dei messaggi (minimum message length, MML).
• 1970 – Valerii Denisovich Goppa introduce i codici di Goppa.
• 1972 – J. Justesen propone i codici di Justesen, un miglioramento dei codici di Reed-Solomon.
• 1973 – David Slepian e Jack Wolf scoprono e provano i limiti della codifica di Slepian–Wolf per la codifica della sorgente distribuita.
• 1976 – Gottfried Ungerboeck presenta il primo studio sulla modulazione con codifica a griglia (Trellis Coded Modulation, TCM); un'esposizione più dettagliata nel 1982 porta a un innalzamento delle velocità POTS dei modem analogici da 9,6 kbit/s a 33,6 kbit/s.
• 1976 – R. Pasco e Jorma J. Rissanen sviluppano tecniche efficaci per la codifica aritmetica.
• 1977 – Abraham Lempel e Jacob Ziv sviluppano la compressione di Lempel-Ziv (LZ77).
• 1989 – Phil Katz pubblica il formato .zip che include DEFLATE (LZ77 + codifica di Huffman), destinato a diventare il più utilizzato contenitore archivio e algoritmo di compressione lossless (senza perdita di dati).
• 1993 – Claude Berrou, Alain Glavieux e Punya Thitimajshima introducono i codici Turbo.
• 1994 – Michael Burrows e David Wheeler pubblicano la trasformata di Burrows-Wheeler, che doveva in seguito trovare uso in bzip2.
• 1995 – Benjamin Schumacher conia il termine qubit e prova il teorema della codifica quantistica senza rumore.

Note

1. Shannon 2001.

Bibliografia

• (EN) Claude Elwood Shannon, A mathematical theory of communication, in ACM SIGMOBILE Mobile Computing and Communications Review, vol. 5, n. 1, New York (NY, USA), Association for Computing Machinery, 1º gennaio 2001 [prima pubblicazione 1948], DOI:10.1145/584091.584093, ISSN 1559-1662 (WC · ACNP).