A timeline of events related to information theory, quantum information theory and statistical physics, data compression, error correcting codes and related subjects.

- 1872 – Ludwig Boltzmann presents his H-theorem, and with it the formula Σ
*p*_{i}log*p*_{i}for the entropy of a single gas particle - 1878 – J. Willard Gibbs defines the Gibbs entropy: the probabilities in the entropy formula are now taken as probabilities of the state of the
*whole*system - 1924 – Harry Nyquist discusses quantifying "intelligence" and the speed at which it can be transmitted by a communication system
- 1927 – John von Neumann defines the von Neumann entropy, extending the Gibbs entropy to quantum mechanics
- 1928 – Ralph Hartley introduces Hartley information as the logarithm of the number of possible messages, with information being communicated when the receiver can distinguish one sequence of symbols from any other (regardless of any associated meaning)
- 1929 – Leó Szilárd analyses Maxwell's Demon, showing how a Szilard engine can sometimes transform information into the extraction of useful work
- 1940 – Alan Turing introduces the deciban as a measure of information inferred about the German Enigma machine cypher settings by the Banburismus process
- 1944 – Claude Shannon's theory of information is substantially complete
- 1947 – Richard W. Hamming invents Hamming codes for error detection and correction (to protect patent rights, the result is not published until 1950)
- 1948 – Claude E. Shannon publishes
*A Mathematical Theory of Communication* - 1949 – Claude E. Shannon publishes
*Communication in the Presence of Noise*– Nyquist–Shannon sampling theorem and Shannon–Hartley law - 1949 – Claude E. Shannon's
*Communication Theory of Secrecy Systems*is declassified - 1949 – Robert M. Fano publishes
*Transmission of Information*. M.I.T. Press, Cambridge, Massachusetts – Shannon–Fano coding - 1949 – Leon G. Kraft discovers Kraft's inequality, which shows the limits of prefix codes
- 1949 – Marcel J. E. Golay introduces Golay codes for forward error correction
- 1951 – Solomon Kullback and Richard Leibler introduce the Kullback–Leibler divergence
- 1951 – David A. Huffman invents Huffman encoding, a method of finding optimal prefix codes for lossless data compression
- 1953 – August Albert Sardinas and George W. Patterson devise the Sardinas–Patterson algorithm, a procedure to decide whether a given variable-length code is uniquely decodable
- 1954 – Irving S. Reed and David E. Muller propose Reed–Muller codes
- 1955 – Peter Elias introduces convolutional codes
- 1957 – Eugene Prange first discusses cyclic codes
- 1959 – Alexis Hocquenghem, and independently the next year Raj Chandra Bose and Dwijendra Kumar Ray-Chaudhuri, discover BCH codes
- 1960 – Irving S. Reed and Gustave Solomon propose Reed–Solomon codes
- 1962 – Robert G. Gallager proposes low-density parity-check codes; they are unused for 30 years due to technical limitations
- 1965 – Dave Forney discusses concatenated codes
- 1966 – Fumitada Itakura (Nagoya University) and Shuzo Saito (Nippon Telegraph and Telephone) develop linear predictive coding (LPC), a form of speech coding
^{ [1] } - 1967 – Andrew Viterbi reveals the Viterbi algorithm, making decoding of convolutional codes practicable
- 1968 – Elwyn Berlekamp invents the Berlekamp–Massey algorithm; its application to decoding BCH and Reed–Solomon codes is pointed out by James L. Massey the following year
- 1968 – Chris Wallace and David M. Boulton publish the first of many papers on Minimum Message Length (MML) statistical and inductive inference
- 1970 – Valerii Denisovich Goppa introduces Goppa codes
- 1972 – Jørn Justesen proposes Justesen codes, an improvement of Reed–Solomon codes
- 1972 – Nasir Ahmed proposes the discrete cosine transform (DCT), which he develops with T. Natarajan and K. R. Rao in 1973;
^{ [2] }the DCT later became the most widely used lossy compression algorithm, the basis for multimedia formats such as JPEG, MPEG and MP3 - 1973 – David Slepian and Jack Wolf discover and prove the Slepian–Wolf coding limits for distributed source coding
^{ [3] } - 1976 – Gottfried Ungerboeck gives the first paper on trellis modulation; a more detailed exposition in 1982 leads to a raising of analogue modem POTS speeds from 9.6 kbit/s to 33.6 kbit/s
- 1976 – Richard Pasco and Jorma J. Rissanen develop effective arithmetic coding techniques
- 1977 – Abraham Lempel and Jacob Ziv develop Lempel–Ziv compression (LZ77)
- 1982 – Valerii Denisovich Goppa introduces algebraic geometry codes
- 1989 – Phil Katz publishes the
`.zip`

format including DEFLATE (LZ77 + Huffman coding); later to become the most widely used archive container - 1993 – Claude Berrou, Alain Glavieux and Punya Thitimajshima introduce Turbo codes
- 1994 – Michael Burrows and David Wheeler publish the Burrows–Wheeler transform, later to find use in bzip2
- 1995 – Benjamin Schumacher coins the term qubit and proves the quantum noiseless coding theorem
- 2003 – David J. C. MacKay shows the connection between information theory, inference and machine learning in his book.
- 2006 – Jarosław Duda introduces first Asymmetric numeral systems entropy coding: since 2014 popular replacement of Huffman and arithmetic coding in compressors like Facebook Zstandard, Apple LZFSE, CRAM or JPEG XL
- 2008 – Erdal Arıkan introduces polar codes, the first practical construction of codes that achieves capacity for a wide array of channels

In information theory, **data compression**, **source coding**, or **bit-rate reduction** is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compression reduces bits by identifying and eliminating statistical redundancy. No information is lost in lossless compression. Lossy compression reduces bits by removing unnecessary or less important information. Typically, a device that performs data compression is referred to as an encoder, and one that performs the reversal of the process (decompression) as a decoder.

In computer science and information theory, a **Huffman code** is a particular type of optimal prefix code that is commonly used for lossless data compression. The process of finding or using such a code is **Huffman coding**, an algorithm developed by David A. Huffman while he was a Sc.D. student at MIT, and published in the 1952 paper "A Method for the Construction of Minimum-Redundancy Codes".

**Information theory** is the mathematical study of the quantification, storage, and communication of information. The field was originally established by the works of Harry Nyquist and Ralph Hartley, in the 1920s, and Claude Shannon in the 1940s. The field, in applied mathematics, is at the intersection of probability theory, statistics, computer science, statistical mechanics, information engineering, and electrical engineering.

**Lossless compression** is a class of data compression that allows the original data to be perfectly reconstructed from the compressed data with no loss of information. Lossless compression is possible because most real-world data exhibits statistical redundancy. By contrast, lossy compression permits reconstruction only of an approximation of the original data, though usually with greatly improved compression rates.

**Image compression** is a type of data compression applied to digital images, to reduce their cost for storage or transmission. Algorithms may take advantage of visual perception and the statistical properties of image data to provide superior results compared with generic data compression methods which are used for other digital data.

In information theory, an **entropy coding** is any lossless data compression method that attempts to approach the lower bound declared by Shannon's source coding theorem, which states that any lossless data compression method must have an expected code length greater than or equal to the entropy of the source.

In the field of data compression, **Shannon–Fano coding**, named after Claude Shannon and Robert Fano, is one of two related techniques for constructing a prefix code based on a set of symbols and their probabilities.

**Lempel–Ziv–Welch** (**LZW**) is a universal lossless data compression algorithm created by Abraham Lempel, Jacob Ziv, and Terry Welch. It was published by Welch in 1984 as an improved implementation of the LZ78 algorithm published by Lempel and Ziv in 1978. The algorithm is simple to implement and has the potential for very high throughput in hardware implementations. It is the algorithm of the Unix file compression utility compress and is used in the GIF image format.

**LZ77** and **LZ78** are the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978. They are also known as **LZ1** and **LZ2** respectively. These two algorithms form the basis for many variations including LZW, LZSS, LZMA and others. Besides their academic influence, these algorithms formed the basis of several ubiquitous compression schemes, including GIF and the DEFLATE algorithm used in PNG and ZIP.

**Coding theory** is the study of the properties of codes and their respective fitness for specific applications. Codes are used for data compression, cryptography, error detection and correction, data transmission and data storage. Codes are studied by various scientific disciplines—such as information theory, electrical engineering, mathematics, linguistics, and computer science—for the purpose of designing efficient and reliable data transmission methods. This typically involves the removal of redundancy and the correction or detection of errors in the transmitted data.

**Adaptive coding** refers to variants of entropy encoding methods of lossless data compression. They are particularly suited to streaming data, as they adapt to localized changes in the characteristics of the data, and don't require a first pass over the data to calculate a probability model. The cost paid for these advantages is that the encoder and decoder must be more complex to keep their states synchronized, and more computational power is needed to keep adapting the encoder/decoder state.

This is a **list of information theory topics**.

In cryptography, the **McEliece cryptosystem** is an asymmetric encryption algorithm developed in 1978 by Robert McEliece. It was the first such scheme to use randomization in the encryption process. The algorithm has never gained much acceptance in the cryptographic community, but is a candidate for "post-quantum cryptography", as it is immune to attacks using Shor's algorithm and – more generally – measuring coset states using Fourier sampling.

**Algebraic geometry codes**, often abbreviated AG codes, are a type of linear code that generalize Reed–Solomon codes. The Russian mathematician V. D. Goppa constructed these codes for the first time in 1982.

**Abraham Lempel** was an Israeli computer scientist and one of the fathers of the LZ family of lossless data compression algorithms.

**Lempel–Ziv–Storer–Szymanski** (**LZSS**) is a lossless data compression algorithm, a derivative of LZ77, that was created in 1982 by James A. Storer and Thomas Szymanski. LZSS was described in article "Data compression via textual substitution" published in *Journal of the ACM*.

In data compression, a **universal code** for integers is a prefix code that maps the positive integers onto binary codewords, with the additional property that whatever the true probability distribution on integers, as long as the distribution is monotonic (i.e., *p*(*i*) ≥ *p*(*i* + 1) for all positive *i*), the expected lengths of the codewords are within a constant factor of the expected lengths that the optimal code for that probability distribution would have assigned. A universal code is *asymptotically optimal* if the ratio between actual and optimal expected lengths is bounded by a function of the information entropy of the code that, in addition to being bounded, approaches 1 as entropy approaches infinity.

The decisive event which established the discipline of **information theory**, and brought it to immediate worldwide attention, was the publication of Claude E. Shannon's classic paper "A Mathematical Theory of Communication" in the *Bell System Technical Journal* in July and October 1948.

**Lempel–Ziv–Stac** is a lossless data compression algorithm that uses a combination of the LZ77 sliding-window compression algorithm and fixed Huffman coding. It was originally developed by Stac Electronics for tape compression, and subsequently adapted for hard disk compression and sold as the Stacker disk compression software. It was later specified as a compression algorithm for various network protocols. LZS is specified in the Cisco IOS stack.

In information theory and communication, the **Slepian–Wolf coding**, also known as the **Slepian–Wolf bound**, is a result in distributed source coding discovered by David Slepian and Jack Wolf in 1973. It is a method of theoretically coding two lossless compressed correlated sources.

- ↑ Gray, Robert M. (2010). "A History of Realtime Digital Speech on Packet Networks: Part II of Linear Predictive Coding and the Internet Protocol" (PDF).
*Found. Trends Signal Process*.**3**(4): 203–303. doi: 10.1561/2000000036 . ISSN 1932-8346. - ↑ Nasir Ahmed. "How I Came Up With the Discrete Cosine Transform". Digital Signal Processing, Vol. 1, Iss. 1, 1991, pp. 4-5.
- ↑ Slepian, David S.; Wolf, Jack K. (July 1973). "Noiseless coding of correlated information sources".
*IEEE Transactions on Information Theory*.**19**(4). IEEE: 471–480. doi:10.1109/TIT.1973.1055037. ISSN 0018-9448.

This page is based on this Wikipedia article

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.

Text is available under the CC BY-SA 4.0 license; additional terms may apply.

Images, videos and audio are available under their respective licenses.