Coding theory

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
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:[1]

  1. Data compression (or source coding)
  2. Error control (or channel coding)
  3. Cryptographic coding
  4. Line coding

Data compression attempts to remove redundancy from the data from a source in order to transmit it more efficiently. For example, Zip data compression makes data files smaller, for purposes such as to reduce Internet traffic. Data compression and error correction may be studied in combination.

Error correction adds extra data bits to make the transmission of data 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 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.

History of coding theory


The binary Golay code was developed in 1949. It is an error-correcting code capable of correcting up to three errors in each 24-bit word, and detecting a fourth.


In 1972, Nasir Ahmed proposed the discrete cosine transform (DCT), which he developed with T. Natarajan and K. R. Rao in 1973.[2] The DCT is the most widely used lossy compression algorithm, the basis for multimedia formats such as JPEG, MPEG and MP3.

Source coding



Data can be seen as a random variable , where appears with probability .

Data are encoded by strings (words) over an alphabet .

A code is a function

(or if the empty string is not part of the alphabet).

is the code word associated with .

Length of the code word is written as


Expected length of a code is

The concatenation of code words .



  1. is non-singular if injective.
  2. is uniquely decodable if injective.
  3. is instantaneous if is not a prefix of (and vice versa).







Channel coding


CDs use cross-interleaved Reed–Solomon coding to spread the data out over the disk.[3]



Linear codes



  1. Linear block codes
  2. Convolutional codes


  • code word length
  • total number of valid code words

Linear block codes



  3. dmin is the minimum hamming distance for the code.

There are many types of linear block codes, such as

  1. Cyclic codes (e.g., Hamming codes)
  2. Repetition codes
  3. Parity codes
  4. Polynomial codes (e.g., BCH codes)
  5. Reed–Solomon codes
  6. Algebraic geometric codes
  7. Reed–Muller codes
  8. Perfect codes




Properties of linear block codes are used in many applications. For example, the syndrome-coset uniqueness property of linear block codes is used in trellis shaping,[7] one of the best known shaping codes. This same property is used in sensor networks for distributed source coding, and in lossy compression of noisy sparse sources[8].

Convolutional codes






Cryptographic coding

Cryptography or cryptographic coding is the practice and study of techniques for secure communication in the presence of third parties (called adversaries).[9] More generally, it is about constructing and analyzing protocols that block adversaries;[10] various aspects in information security such as data confidentiality, data integrity, authentication, and non-repudiation[11] are central to modern cryptography. Modern cryptography exists at the intersection of the disciplines of mathematics, computer science, and electrical engineering. Applications of cryptography include ATM cards, computer passwords, and electronic commerce.

Cryptography prior to the modern age was effectively synonymous with encryption, the conversion of information from a readable state to apparent nonsense. The originator of an encrypted message shared the decoding technique needed to recover the original information only with intended recipients, thereby precluding unwanted persons from doing the same. Since World War I and the advent of the computer, the methods used to carry out cryptology have become increasingly complex and its application more widespread.


Line coding

A line code (also called digital baseband modulation or digital baseband transmission method) is a code chosen for use within a communications system for baseband transmission purposes. Line coding is often used for digital data transport.

Line coding consists of representing the digital signal to be transported by an amplitude- and time-discrete signal that is optimally tuned for the specific properties of the physical channel (and of the receiving equipment). The waveform pattern of voltage or current used to represent the 1s and 0s of a digital data on a transmission link is called line encoding. The common types of line encoding are unipolar, polar, bipolar, and Manchester encoding.

Other applications of coding theory




Group testing


Analog coding

Information is encoded analogously in the neural networks of brains, in analog signal processing, and analog electronics. Aspects of analog coding include analog error correction,[13] analog data compression[14] and analog encryption.[15]

Neural coding

Neural coding is a neuroscience-related field concerned with how sensory and other information is represented in the brain by networks of neurons. The main goal of studying neural coding is to characterize the relationship between the stimulus and the individual or ensemble neuronal responses and the relationship among electrical activity of the neurons in the ensemble.[16] It is thought that neurons can encode both digital and analog information,[17] and that neurons follow the principles of information theory and compress information,[18] and detect and correct[19] errors in the signals that are sent throughout the brain and wider nervous system.

See also


  1. ^ James Irvine; David Harle (2002). "2.4.4 Types of Coding". Data Communications and Networks. p. 18. ISBN 9780471808725. There are four types of coding
  2. ^ Nasir Ahmed. "How I Came Up With the Discrete Cosine Transform". Digital Signal Processing, Vol. 1, Iss. 1, 1991, pp. 4-5. Italic or bold markup not allowed in: |publisher= (help)
  3. ^ Todd Campbell. "Answer Geek: Error Correction Rule CDs".
  4. ^ a b Terras, Audrey (1999). Fourier Analysis on Finite Groups and Applications. Cambridge University Press. ISBN 978-0-521-45718-7.
  5. ^ a b Blahut, Richard E. (2003). Algebraic Codes for Data Transmission. Cambridge University Press. ISBN 978-0-521-55374-2.
  6. ^ a b Christian Schlegel; Lance Pérez (2004). Trellis and turbo coding. Wiley-IEEE. p. 73. ISBN 978-0-471-22755-7.
  7. ^ Forney, G.D., Jr. (March 1992). "Trellis shaping". IEEE Transactions on Information Theory. 38 (2 Pt 2): 281–300. doi:10.1109/18.119687o (inactive 2019-08-20).
  8. ^ Elzanaty, A.; Giorgetti, A.; Chiani, M. (2019). "Lossy Compression of Noisy Sparse Sources Based on Syndrome Encoding". IEEE Transactions on Communications. doi:10.1109/TCOMM.2019.2926080. ISSN 0090-6778.
  11. ^ Menezes, A. J.; van Oorschot, P. C.; Vanstone, S. A. (1997). Handbook of Applied Cryptography. ISBN 978-0-8493-8523-0.
  12. ^ Dorfman, Robert (1943). "The detection of defective members of large populations". Annals of Mathematical Statistics (14): 436–440.
  13. ^ Chen, Brian; Wornell, Gregory W. (July 1998). "Analog Error-Correcting Codes Based on Chaotic Dynamical Systems" (PDF). IEEE Transactions on Communications. 46 (7): 881–890. CiteSeerX doi:10.1109/26.701312. Archived from the original (PDF) on 2001-09-27. Retrieved 2013-06-30.
  14. ^ Hvala, Franc Novak Bojan; Klavžar, Sandi (1999). "On Analog Signature Analysis". Proceedings of the conference on Design, automation and test in Europe. CiteSeerX ISBN 1-58113-121-6.
  15. ^ 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. doi:10.1109/TCSI.2008.916540.
  17. ^ Thorpe, S.J. (1990). "Spike arrival times: A highly efficient coding scheme for neural networks" (PDF). In Eckmiller, R.; Hartmann, G.; Hauske, G. (eds.). Parallel processing in neural systems and computers (PDF). North-Holland. pp. 91–94. ISBN 978-0-444-88390-2. Retrieved 30 June 2013.
  18. ^ Gedeon, T.; Parker, A.E.; Dimitrov, A.G. (Spring 2002). "Information Distortion and Neural Coding". Canadian Applied Mathematics Quarterly. 10 (1): 10. CiteSeerX
  19. ^ Stiber, M. (July 2005). "Spike timing precision and neural error correction: local behavior". Neural Computation. 17 (7): 1577–1601. arXiv:q-bio/0501021. doi:10.1162/0899766053723069. PMID 15901408.


Retrieved from ""
This content was retrieved from Wikipedia :
This page is based on the copyrighted Wikipedia article "Coding theory"; it is used under the Creative Commons Attribution-ShareAlike 3.0 Unported License (CC-BY-SA). You may redistribute it, verbatim or modified, providing that you comply with the terms of the CC-BY-SA