Coding theory

The coding theory is the mathematical theory of error-detecting and -korrigierenden codes . Such codes are used where digital data is to be protected against errors that occur during transmission or storage . Examples are communicating with objects in space and storing data on a CD .

Large parts of coding theory are based on algebra , which is why the term algebraic coding theory is often used to draw a clear boundary to the related information theory . In addition to algebra, coding theory also uses methods from combinatorics , number theory and finite geometry (for example, densest packing of spheres ).

history

The founders of the algebraic coding theory are Marcel JE Golay , who published the half-page article Notes on digital coding in 1949 , as well as Richard Hamming with his work Error detecting and error correcting codes , which appeared delayed in 1950 for patent reasons .

description

From cryptography and data compression , the coding theory is different in its objective: The former have data against unauthorized recipients covered or the amount of data to be reduced, there is interest in coding theory because the amount of data by inserting redundancies to increase awareness to in this way to achieve a safeguard against occurring errors. These types of data modification can also be combined with one another: It is not uncommon for data to be first compressed, then cryptographically encrypted and finally coded against transmission errors. In particular, it is often advisable to use a compression process, as this creates a statistical uniform distribution of the characters in the data, from which the coding benefits.

Important parameters of a code are the information rate (a parameter for the amount of information contained in a fixed amount of data) and the correction rate (a parameter for the error resistance in a fixed amount of data). In addition to codes with a good information and correction rate, there is usually also an interest in ensuring that the coding and decoding algorithms do not require excessive technical requirements. It is currently not possible to optimize all of these properties at the same time. Therefore, in practice, it must always be decided again which code offers the best compromise for a specific application.

For simple algorithms for coding and decoding, it is helpful to impress the richest possible algebraic structure on the code . The theoretical treatment of such codes is also simpler than in the general case. Against this background, the group codes (structure of a group ), the linear codes (structure of a finite vector space ), and the cyclic codes (structure of a finite algebra ) were created. The examination of the associated group ring over a finite field often provides further information about the structure of the code. Another class of codes are the convolutional codes .

See also

• Channel coding
• Block code
• Parity bit

literature

• Richard Wesley Hamming : Coding and Information Theory . Prentice-Hall, Englewood Cliffs NJ 1980, ISBN 0-13-139139-9 .
• Werner Heise , Pasquale Quattrocchi: Information and Coding Theory. Mathematical basics of data compression and backup in discrete communication systems . 3rd revised edition. Springer, Berlin et al. 1995, ISBN 3-540-57477-8 ( Springer textbook ).
• Herbert Klimant, Rudi Piotraschke, Dagmar Schönfeld: Information and coding theory . 2nd revised and expanded edition. Teubner, Stuttgart et al. 2003, ISBN 3-519-23003-8 .
• Vera S. Pless, W. Cary Huffman (Eds.): Handbook of Coding Theory . 2 volumes. Elsevier, Amsterdam et al. 1998, ISBN 0-444-50088-X .
• Ralph-Hardo Schulz: Coding Theory. An introduction. 2nd updated and expanded edition. Vieweg Verlag, Wiesbaden 2003, ISBN 3-528-16419-0 .
• Wolfgang Willems: Coding Theory . de Gruyter, Berlin et al. 1999, ISBN 3-110-15873-6 ( De Gruyter textbook ).

Individual evidence

1. ↑ Golay, Notes on digital coding, Proc. IRE, Volume 37, 1949, p. 657, PDF ( Memento of the original dated October 7, 2016 in the Internet Archive ) Info: The archive link was inserted automatically and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. 
2. ↑ Hamming, Error detecting and error correcting codes, Bell System Techn. J. Volume 29, 1950, pp. 147-160, PDF