A two-dimensional visualisation of the Hamming distance, a critical measure in coding theory
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.
There are four types of coding:
- Data compression (or source coding)
- Error control (or channel coding)
- Cryptographic coding
- Line coding
Data compression attempts to remove unwanted redundancy from the data from a source in order to transmit it more efficiently. For example, DEFLATE data compression makes files smaller, for purposes such as to reduce Internet traffic. Data compression and error correction may be studied in combination.
Error correction adds useful redundancy to the data from a source to make the transmission more robust to disturbances present on the transmission channel. The ordinary user may not be aware of many applications using error correction. A typical music compact disc (CD) uses the Reed–Solomon code to correct for scratches and dust. In this application the transmission channel is the CD itself. Cell phones also use coding techniques to correct for the fading and noise of high frequency radio transmission. Data modems, telephone transmissions, and the NASA Deep Space Network all employ channel coding techniques to get the bits through, for example the turbo code and LDPC codes.
x∈𝒳 appears with probability C:𝒳→Σ∗ (or x.Length of the code word is written as
- C(x1,…,xk)=C(x1)C(x2)⋯C(xk).
The code word of the empty string is the empty string itself:
- C:𝒳∗→Σ∗ is uniquely decodable if injective.
- C(x2) (and vice versa).
Principle
editEntropy of a source is the measure of information. Basically, source codes try to reduce the redundancy present in the source, and represent the source with fewer bits that carry more information.
Data compression which explicitly tries to minimize the average length of messages according to a particular assumed probability model is called entropy encoding.
Various techniques used by source coding schemes try to achieve the limit of entropy of the source. C(x) ≥ H(x), where H(x) is entropy of source (bitrate), and C(x) is the bitrate after compression. In particular, no source coding scheme can be better than the entropy of the source.
Example
editFacsimile transmission uses a simple run length code. Source coding removes all data superfluous to the need of the transmitter, decreasing the bandwidth required for transmission.
Cell phones are subject to rapid fading. The high frequencies used can cause rapid fading of the signal even if the receiver is moved a few inches. Again there are a class of channel codes that are designed to combat fading.Channel coding
editThe term algebraic coding theory denotes the sub-field of coding theory where the properties of codes are expressed in algebraic terms and then further researched.
- Code word length
- Total number of valid code words
- The minimum distance between two valid code words, using mainly the Hamming distance, sometimes also other distances like the Lee distance
When transmitting, the code word is used to modulate the data bits representing the voice message. At the receiver, a demodulation process is performed to recover the data. The properties of this class of codes allow many users (with different codes) to use the same radio channel at the same time. To the receiver, the signals of other users will appear to the demodulator only as a low-level noise.James Irvine; David Harle (2002). "2.4.4 Types of Coding". Data Communications and Networks. John Wiley & Sons. p. 18. ISBN 978-0-471-80872-5. There are four types of codingLinear block codes
edit- ↑ Blahut, Richard E. (2003). Algebraic Codes for Data Transmission. Cambridge University Press. ISBN 978-0-521-55374-2.
- 1 2 Rivest, Ronald L. (1990). "Cryptology". In J. Van Leeuwen (ed.). Handbook of Theoretical Computer Science. Vol. 1. Elsevier.
- ↑ Dorfman, Robert (1943). "The detection of defective members of large populations". Annals of Mathematical Statistics. 14 (4): 436–440. doi:10.1214/aoms/1177731363.
- ↑ Shujun Li; Chengqing Li; Kwok-Tung Lo; Guanrong Chen (April 2008). "Cryptanalyzing an Encryption Scheme Based on Blind Source Separation" (PDF). IEEE Transactions on Circuits and Systems I. 55 (4): 1055–63. arXiv:cs/0608024. doi:10.1109/TCSI.2008.916540. S2CID 2224947.
- ↑ Gedeon, T.; Parker, A.E.; Dimitrov, A.G. (Spring 2002). "Information Distortion and Neural Coding". Canadian Applied Mathematics Quarterly. 10 (1): 10. Archived from the original on 2016-11-17. Retrieved 2013-06-30.
- ↑ ISBN 0-521-64298-1
- Vera Pless (1982), Introduction to the Theory of Error-Correcting Codes, John Wiley & Sons, Inc.,
- C:𝒳∗→Σ∗ is uniquely decodable if injective.