Coding theory

 
A two-dimensional visualisation of the , a critical measure in coding theory.

Coding theory is the study of the properties of and their respective fitness for specific applications. Codes are used for , cryptography, , and . Codes are studied by various scientific disciplines—such as , , , , and computer science—for the purpose of designing efficient and reliable 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. (or, source coding)
  2. (or channel coding)
  3. Cryptographic coding
  4.  

Data compression attempts to compress the data from a source in order to transmit it more efficiently. For example, makes data files smaller to reduce Internet traffic. Data compression and error correction may be .

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 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 all employ channel coding techniques to get the bits through, for example the turbo code and .

Contents

History of coding theory

In 1948, published “”, 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 a sender wants to transmit. In this fundamental work he used tools in probability theory, developed by , which were in their nascent stages of being applied to communication theory at that time. Shannon developed as a measure for the uncertainty in a message while essentially inventing the field of .

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.

won the in 1968 for his work at in numerical methods, automatic coding systems, and error-detecting and error-correcting codes. He invented the concepts known as Hamming codes, , , and .

Source coding

The aim of source coding is to take the source data and make it smaller.

Definition

Data can be seen as a <math>X:Omegarightarrowmathcal{X}</math>, where <math>x in mathcal{X}</math> appears with probability <math>mathbb{P}[X=x]</math>.

Data are encoded by strings (words) over an <math>Sigma</math>.

A code is a function

<math>C:mathcal{X}rightarrowSigma^*</math> (or <math>Sigma^+</math> if the empty string is not part of the alphabet).

<math>C(x)</math> is the code word associated with <math>x</math>.

Length of the code word is written as

<math>l(C(x))</math>.

Expected length of a code is

<math>l(C) = sum_{xinmathcal{X}}l(C(x))mathbb{P}[X=x]</math>

The concatenation of code words <math>C(x_1,…,x_k) = C(x_1)C(x_2)…C(x_k)</math>.

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

<math>C(epsilon) = epsilon</math>

Properties

  1. <math>C:mathcal{X}rightarrowSigma^*</math> is if .
  2. <math>C:mathcal{X}^*rightarrowSigma^*</math> is if injective.
  3. <math>C:mathcal{X}rightarrowSigma^*</math> is if <math>C(x_1)</math> is not a prefix of <math>C(x_2)</math> (and vice versa).

Principle

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 .

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.

Example

transmission uses a simple . Source coding removes all data superfluous to the need of the transmitter, decreasing the bandwidth required for transmission.

Channel coding

The purpose of channel coding theory is to find codes which transmit quickly, contain many valid and can correct or at least 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.

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 don’t 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 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. 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.

Linear codes

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:

  1. Linear block codes
  2. Convolutional codes

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

  • code word length
  • total number of valid code words
  • the minimum between two valid code words, using mainly the , sometimes also other distances like the

Linear block codes

Linear block codes have the property of , 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.

Another code property is the number of neighbors that a single codeword may have. 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. one of the best known shaping codes. This same property is used in sensor networks for distributed source coding

Convolutional 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 used in 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 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.

Cryptographical coding

Cryptography or cryptographic coding is the practice and study of techniques for in the presence of third parties (called ). More generally, it is about constructing and analyzing that block adversaries; various aspects in such as data confidentiality, , authentication, and are central to modern cryptography. Modern cryptography exists at the intersection of the disciplines of , computer science, and . Applications of cryptography include , computer passwords, and .

Cryptography prior to the modern age was effectively synonymous with , the conversion of information from a readable state to apparent . 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 and the advent of the , the methods used to carry out cryptology have become increasingly complex and its application more widespread.

Modern cryptography is heavily based on mathematical theory and computer science practice; cryptographic algorithms are designed around , making such algorithms hard to break in practice by any adversary. It is theoretically possible to break such a system, but it is infeasible to do so by any known practical means. These schemes are therefore termed computationally secure; theoretical advances, e.g., improvements in algorithms, and faster computing technology require these solutions to be continually adapted. There exist schemes that cannot be broken even with unlimited computing power—an example is the —but these schemes are more difficult to implement than the best theoretically breakable but computationally secure mechanisms.

Line coding

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

Line coding consists of representing the 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 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 , , , and .

Other applications of coding theory

Another concern of coding theory is designing codes that help . A code may be designed so that a can be easily detected and corrected and that multiple signals can be sent on the same channel.

Another application of codes, used in some mobile phone systems, is (CDMA). Each phone is assigned a code sequence that is approximately uncorrelated with the codes of other phones. When transmitting, the code word is used to modulate the data bits representing the voice message. At the receiver, a demodulation process is performed to recover the data. The properties of this class of codes allow many users (with different codes) to use the same radio channel at the same time. To the receiver, the signals of other users will appear to the demodulator only as a low-level noise.

Another general class of codes are the (ARQ) codes. In these codes the sender adds redundancy to each message for error checking, usually by adding check bits. If the check bits are not consistent with the rest of the message when it arrives, the receiver will ask the sender to retransmit the message. All but the simplest protocols use ARQ. Common protocols include (IBM), (Internet), (International) and many others. There is an extensive field of research on this topic because of the problem of matching a rejected packet against a new packet. Is it a new one or is it a retransmission? Typically numbering schemes are used, as in TCP.

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 when the needed to test its soldiers for . It originated from a ground-breaking paper by .

Analog coding

Information is encoded analogously in the of , in , and . Aspects of analog coding include analog error correction, analog data compression and analog encryption.

Neural coding

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

See Also on BitcoinWiki

  • Coding gain
  •  
  •  
  •  
  • ,
  •  
  •  
  • Spatial coding and in
    • is spatial coding that transmits replicas of the information signal along different spatial paths, so as to increase the reliability of the data transmission.
    •  
    •  
  •  
  •  
  •  

Notes

Source

http://wikipedia.org/