Coding theory: Difference between revisions

Revision as of 01:37, 24 October 2023

Latest revision as of 08:44, 19 June 2025

(16 intermediate revisions by 14 users not shown)

Line 20:

# [[Line code|Line coding]]

Data compression attempts to remove unwanted redundancy from the data from a source in order to transmit it more efficiently. For example, [[Zip (file format)|ZIPDEFLATE]] data compression]] makes data files smaller, for purposes such as to reduce Internet traffic. Data compression and error correction may be [[Joint source and channel coding|studied in combination]].

[[Error detection and correction|Error correction]] adds useful [[Redundancy (information theory)|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 [[Compact Disc Digital Audio|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 code]]s.<!--Kvng RTH-->

==History of coding theory==

{{excerpt|History of information theory}}

In 1948, [[Claude Shannon]] published "[[A Mathematical Theory of Communication]]", an article in two parts in the July and October issues of the ''Bell System Technical Journal''. This work focuses on the problem of how best to encode the [[information]] a sender wants to transmit. In this fundamental work he used tools in probability theory, developed by [[Norbert Wiener]], which were in their nascent stages of being applied to communication theory at that time. Shannon developed [[information entropy]] as a measure for the uncertainty in a message while essentially inventing the field of [[information theory]].

InShannon’s 1948, [[Claude Shannon]] published "[[A Mathematical Theory of Communication]]", an article in two parts in the July and October issues of the ''Bell System Technical Journal''. This workpaper focuses on the problem of how to best to encode the [[information]] a sender wants to transmit. In this fundamental work he used tools in probability theory, developed by [[Norbert Wiener]], which were in their nascent stages of being applied to communication theory at that time. Shannon developed [[information entropy]] as a measure for the uncertainty in a message while essentially inventing the field of [[information 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.

Line 66 ⟶ 68:

# <math>C:\mathcal{X}\to\Sigma^*</math> is [[Variable-length code#Non-singular codes|non-singular]] if [[Injective function|injective]].

# <math>C:\mathcal{X}^*\to\Sigma^*</math> is [[Uniquely decodable code#Uniquely decodable codes|uniquely decodable]] if injective.

# <math>C:\mathcal{X}\to\Sigma^*</math> is [[Variable-length code#Prefix codes|instantaneous]] if <math>C(x_1)</math> is not a proper prefix of <math>C(x_2)</math> (and vice versa).

===Principle===

Line 128 ⟶ 130:

# [[Reed–Muller code]]s

# [[Hamming bound|Perfect codes]]

# [[Locally recoverable code]]

Block codes are tied to the [[sphere packing]] problem, which has received some attention over the years. In two dimensions, it is easy to visualize. Take a bunch of pennies flat on the table and push them together. The result is a hexagon pattern like a bee's nest. But block codes rely on more dimensions which cannot easily be visualized. The powerful (24,12) [[Binary Golay code|Golay code]] used in deep space communications uses 24 dimensions. If used as a binary code (which it usually is) the dimensions refer to the length of the codeword as defined above.

The theory of coding uses the ''N''-dimensional sphere model. For example, how many pennies can be packed into a circle on a tabletop, or in 3 dimensions, how many marbles can be packed into a globe. Other considerations enter the choice of a code. For example, hexagon packing into the constraint of a rectangular box will leave empty space at the corners. As the dimensions get larger, the percentage of empty space grows smaller. But at certain dimensions, the packing uses all the space and these codes are the so-called "perfect" codes. The only nontrivial and useful perfect codes are the distance-3 Hamming codes with parameters satisfying (2^''r'' – 1, 2^''r'' – 1 – ''r'', 3), and the [23,12,7] binary and [11,6,5] ternary Golay codes.<ref name=terras>

{{cite book | title = Fourier Analysis on Finite Groups and Applications |first=Audrey |last=Terras |author-link=Audrey Terras| publisher = [[Cambridge University Press]] | year = 1999 | isbn = 978-0-521-45718-7 | url = https://archive.org/details/fourieranalysiso0000terr | url-access = registration | page = [https://archive.org/details/fourieranalysiso0000terr/page/195 195] }}</ref><ref name=blahut>{{cite book |title = Algebraic Codes for Data Transmission |first=Richard E. |last=Blahut |author-link=Richard E. Blahut | publisher = Cambridge University Press | year = 2003 | isbn = 978-0-521-55374-2 | url = https://books.google.com/books?id=n0XHMY58tL8C&pg=PA60}}

</ref>

Line 172 ⟶ 175:

{{main|Line code}}

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 (telecommunications)|transmission]] purposes. Line coding is often used for digital data transport.

Line coding is often used for digital data transport. It consists of representing the [[Digital signal (electronics)|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 encoding|unipolar]], [[Polar encoding|polar]], [[Bipolar encoding|bipolar]], and [[Manchester encoding]].

==Other applications of coding theory==

Line 197 ⟶ 200:

==Neural coding==

[[Neural coding]] is a [[neuroscience]]-related field concerned with how sensory and other information is represented in the [[brain]] by [[neural network|networks]] of [[neurons]]. The main goal of studying neural coding is to characterize the relationship between the [[Stimulus (physiology)|stimulus]] and the individual or ensemble neuronal responses and the relationship among electrical activity of the neurons in the ensemble.<ref name="Brown">{{cite journal |vauthors=Brown EN, Kass RE, Mitra PP |title=Multiple neural spike train data analysis: state-of-the-art and future challenges |journal=Nature Neuroscience |volume=7 |issue=5 |pages=456–461 |date=May 2004 | url = http://www.stat.columbia.edu/~liam//teaching/neurostat-fall13/papers/brown-et-al/brown-kass-mitra.pdf |pmid=15114358 |doi=10.1038/nn1228 |s2cid=562815 }}</ref> It is thought that neurons can encode both [[Digital data|digital]] and [[analog signal|analog]] information,<ref>{{cite book |first=S.J. |last=Thorpe |chapter=Spike arrival times: A highly efficient coding scheme for neural networks |chapter-url=http://pop.cerco.ups-tlse.fr/fr_vers/documents/thorpe_sj_90_91.pdf |format=PDF |pages=91–94 |editor1-first=R. |editor1-last=Eckmiller |editor2-first=G. |editor2-last=Hartmann |editor3-first=G. |editor3-last=Hauske | editor3-link= Gert Hauske |title=Parallel processing in neural systems and computers |url=https://books.google.com/books?id=b9gmAAAAMAAJ |access-date=30 June 2013 |year=1990 |publisher=North-Holland |isbn=978-0-444-88390-2}}</ref> and that neurons follow the principles of information theory and compress information,<ref>{{cite journal |first1=T. |last1=Gedeon |first2=A.E. |last2=Parker |first3=A.G. |last3=Dimitrov |title=Information Distortion and Neural Coding |journal=Canadian Applied Mathematics Quarterly |volume=10 |issue=1 |pages=10 |date=Spring 2002 |url=http://www.math.ualberta.ca/ami/CAMQ/table_of_content/vol_10/10_1c.htm |citeseerx=10.1.1.5.6365 |access-date=2013-06-30 |archive-date=2016-11-17 |archive-url=https://web.archive.org/web/20161117220131/http://www.math.ualberta.ca/ami/CAMQ/table_of_content/vol_10/10_1c.htm |url-status=dead }}</ref> and detect and correct<ref>

{{cite journal |first=M. |last=Stiber |title=Spike timing precision and neural error correction: local behavior |journal=Neural Computation |volume=17 |issue=7 |pages=1577–1601 |date=July 2005 |doi=10.1162/0899766053723069

|pmid=15901408 |arxiv=q-bio/0501021|s2cid=2064645 }}