Coding theory

Data can be seen as a random variable ${\displaystyle X:\Omega \to {\mathcal {X}}}$, where ${\displaystyle x\in {\mathcal {X}}}$ appears with probability ${\displaystyle \mathbb {P} [X=x]}$.

Data are encoded by strings (words) over an alphabet ${\displaystyle \Sigma }$.

A code is a function

${\displaystyle C:{\mathcal {X}}\to \Sigma ^{*}}$ (or ${\displaystyle \Sigma ^{+}}$ if the empty string is not part of the alphabet).

${\displaystyle C(x)}$ is the code word associated with ${\displaystyle x}$.

Length of the code word is written as

${\displaystyle l(C(x)).}$

Expected length of a code is

${\displaystyle l(C)=\sum _{x\in {\mathcal {X}}}l(C(x))\mathbb {P} [X=x].}$

The concatenation of code words ${\displaystyle C(x_{1},\ldots ,x_{k})=C(x_{1})C(x_{2})\cdots C(x_{k})}$.

The code word of the empty string is the empty string itself:

${\displaystyle C(\epsilon )=\epsilon }$

1. ${\displaystyle C:{\mathcal {X}}\to \Sigma ^{*}}$ is non-singular if injective.
2. ${\displaystyle C:{\mathcal {X}}^{*}\to \Sigma ^{*}}$ is uniquely decodable if injective.
3. ${\displaystyle C:{\mathcal {X}}\to \Sigma ^{*}}$ is instantaneous if ${\displaystyle C(x_{1})}$ is not a prefix of ${\displaystyle C(x_{2})}$ (and vice versa).

Entropy 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.

Facsimile 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.

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.

Algebraic coding theory is basically divided into two major types of codes:

• Linear block codes
• Convolutional codes

It analyzes the following three properties of a code – mainly:

• 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 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.[4]

Linear block codes are summarized by their symbol alphabets (e.g., binary or ternary) and parameters (n,m,d_min)[5] where

1. n is the length of the codeword, in symbols,
2. m is the number of source symbols that will be used for encoding at once,
3. d_min 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

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) 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.[4][5]

Another code property is the number of neighbors that a single codeword may have.[6] 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.[6]

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.

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 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 gates. The 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.

Group testing uses codes in a different way. Consider a large group of items in which a very few are different in a particular way (e.g., defective products or infected test subjects). The idea of group testing is to determine which items are "different" by using as few tests as possible. The origin of the problem has its roots in the Second World War when the United States Army Air Forces needed to test its soldiers for syphilis.[11]

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,[12] analog data compression[13] and analog encryption.[14]