Editing Coding theory (section)

==Channel coding==
{{main|Error detection and correction}}

The purpose of channel coding theory is to find codes which transmit quickly, contain many valid [[Code word (communication)|code word]]s and can correct or at least [[error detection|detect]] many errors. While not mutually exclusive, performance in these areas is a trade-off. So, different codes are optimal for different applications. The needed properties of this code mainly depend on the probability of errors happening during transmission. In a typical CD, the impairment is mainly dust or scratches.

CDs use [[cross-interleaved Reed–Solomon coding]] to spread the data out over the disk.<ref>
Todd Campbell.
[https://abcnews.go.com/Technology/story?id=119305&page=1 "Answer Geek: Error Correction Rule CDs"].
</ref>

Although not a very good code, a simple repeat code can serve as an understandable example. Suppose we take a block of data bits (representing sound) and send it three times. At the receiver we will examine the three repetitions bit by bit and take a majority vote. The twist on this is that we do not merely send the bits in order. We interleave them. The block of data bits is first divided into 4 smaller blocks. Then we cycle through the block and send one bit from the first, then the second, etc. This is done three times to spread the data out over the surface of the disk. In the context of the simple repeat code, this may not appear effective. However, there are more powerful codes known which are very effective at correcting the "burst" error of a scratch or a dust spot when this interleaving technique is used.

Other codes are more appropriate for different applications. Deep space communications are limited by the [[thermal noise]] of the receiver which is more of a continuous nature than a bursty nature. Likewise, narrowband modems are limited by the noise, present in the telephone network and also modeled better as a continuous disturbance.{{Citation needed|date=July 2008}} 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.{{Citation needed|date=July 2008}}

===Linear codes===
{{Main|Linear code}}
The 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.{{Citation needed|date=July 2008}}

Algebraic coding theory is basically divided into two major types of codes:{{Citation needed|date=July 2008}}

* Linear block codes
* Convolutional codes

It analyzes the following three properties of a code – mainly:{{Citation needed|date=July 2008}}

* 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]]

====Linear block codes====
{{Main|Block code}}

Linear block codes have the property of [[linearity]], i.e. the sum of any two codewords is also a code word, and they are applied to the source bits in blocks, hence the name linear block codes. There are block codes that are not linear, but it is difficult to prove that a code is a good one without this property.<ref name=terras/>

Linear block codes are summarized by their symbol alphabets (e.g., binary or ternary) and parameters (''n'',''m'',''d<sub>min</sub>'')<ref name=blahut/> where

# n is the length of the codeword, in symbols,
# m is the number of source symbols that will be used for encoding at once,
# ''d<sub>min</sub>'' is the minimum hamming distance for the code.

There are many types of linear block codes, such as

# [[Cyclic code]]s (e.g., [[Hamming code]]s)
# [[Repetition code]]s
# [[Parity bit|Parity codes]]
# [[Polynomial code]]s (e.g., [[BCH code]]s)
# [[Reed–Solomon error correction|Reed–Solomon codes]]
# [[Algebraic geometric code]]s
# [[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<sup>''r''</sup> – 1, 2<sup>''r''</sup> – 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>

Another code property is the number of neighbors that a single codeword may have.<ref name=schlegel>
{{cite book
 | title = Trellis and turbo coding
 |author1=Christian Schlegel |author2=Lance Pérez | publisher = Wiley-IEEE
 | year = 2004
 | isbn = 978-0-471-22755-7
 | page = 73
 | url = https://books.google.com/books?id=9wRCjfGAaEcC&pg=PA73
 }}</ref>
Again, consider pennies as an example. First we pack the pennies in a rectangular grid. Each penny will have 4 near neighbors (and 4 at the corners which are farther away). In a hexagon, each penny will have 6 near neighbors. When we increase the dimensions, the number of near neighbors increases very rapidly.  The result is the number of ways for noise to make the receiver choose a neighbor (hence an error) grows as well. This is a fundamental limitation of block codes, and indeed all codes. It may be harder to cause an error to a single neighbor, but the number of neighbors can be large enough so the total error probability actually suffers.<ref name=schlegel/>

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,<ref>{{cite journal |first=G.D. Jr. |last=Forney |author-link=Dave Forney |title=Trellis shaping |journal=IEEE Transactions on Information Theory |volume=38 |issue=2 Pt 2 |pages=281–300 |date=March 1992 |doi=10.1109/18.119687 |s2cid=37984132 }}</ref> one of the best-known [[shaping codes]].

====Convolutional codes====
{{Main|Convolutional code}}

The idea behind a convolutional code is to make every codeword symbol be the weighted sum of the various input message symbols. This is like [[convolution]] used in [[linear time invariant|LTI]] systems to find the output of a system, when you know the input and impulse response.

So we generally find the output of the system convolutional encoder, which is the convolution of the input bit, against the states of the convolution encoder, registers.

Fundamentally, convolutional codes do not offer more protection against noise than an equivalent block code. In many cases, they generally offer greater simplicity of implementation over a block code of equal power. The encoder is usually a simple circuit which has state memory and some feedback logic, normally [[XOR gate]]s. The [[Decoding methods|decoder]] can be implemented in software or firmware.

The [[Viterbi algorithm]] is the optimum algorithm used to decode convolutional codes. There are simplifications to reduce the computational load. They rely on searching only the most likely paths. Although not optimum, they have generally been found to give good results in low noise environments.

Convolutional codes are used in voiceband modems (V.32, V.17, V.34) and in GSM mobile phones, as well as satellite and military communication devices.