In electrical engineering and digital communications, turbo codes are a class of recently-developed high-performance error correction codes finding use in deep space satellite communications and other applications where designers seek to achieve maximal information transfer over a limited-bandwidth communication link in the presence of data-corrupting noise. Electrical Engineers design power systems… … and complex electronic circuits. ... Digital communication, as opposed to analogue communication refers to all emerging communications and technologies via a digital platform usually combining text, graphics, sound, and video, utilising computer or mobile technology. ... In information theory and coding, an error-correcting code or ECC is a code in which each data signal conforms to specific rules of construction so that departures from this construction in the received signal can generally be automatically detected and corrected. ... Outer space (also called just space), as a name for a region, refers to the relatively empty parts of the Universe, outside the atmospheres of celestial bodies. ... An Earth observation satellite, ERS 2 For other uses, see Satellite (disambiguation). ... Copy of the original phone of Alexander Graham Bell at the Musée des Arts et Métiers in Paris Telecommunication is the transmission of signals over a distance for the purpose of communication. ...

Advantages

Of all practical error correction methods known to date, turbo codes and low-density parity-check codes come closest to approaching the Shannon limit, the theoretical limit of maximum information transfer rate over a noisy channel. A low-density parity-check code (LDPC code) is an error correcting code, a method of transmitting message over a noisy transmission channel. ... In information theory, the Shannon-Hartley theorem states the maximum amount of error-free digital data (that is, information) that can be transmitted over a communication link with a specified bandwidth in the presence of noise interference. ...

Turbo codes make it possible to increase data rate without increasing the power of a transmission, or they can be used to decrease the amount of power used to transmit at a certain data rate. Its main drawbacks are the relative high decoding complexity and a relatively high latency, which makes it unsuitable for some applications. For satellite use, this is not of great concern, since the transmission distance itself introduces latency due to the limited speed of light. Latency is a time delay between the moment something is initiated, and the moment one of its effects begins. ... A line showing the speed of light on a scale model of Earth and the Moon The speed of light in a vacuum is an important physical constant denoted by the letter c for constant or the Latin word celeritas meaning swiftness.[1] It is the speed of all electromagnetic...

Prior to Turbo codes, because practical implementations of LDPCs had not been developed, the most widespread technique that approached the Shannon limit combined Reed-Solomon error correction block codes with Viterbi-decoded short constraint length convolutional codes, also known as RSV codes. Reed-Solomon error correction is a coding scheme which works by first constructing a polynomial from the data symbols to be transmitted and then sending an over-sampled plot of the polynomial instead of the original symbols themselves. ... The Railway Block Code is a system of bells used to send simple messages about train operations from one signalbox to another. ... The Viterbi algorithm, named after its developer Andrew Viterbi, is a dynamic programming algorithm for finding the most likely sequence of hidden states – known as the Viterbi path – that result in a sequence of observed events, especially in the context of hidden Markov models. ... In telecommunication, a convolutional code is a type of error-correcting code in which (a) each m-bit information symbol (each m-bit string) to be encoded is transformed into an n-bit symbol, where m/n is the code rate (n ≥ m) and (b) the transformation is a function...

NASA's Deep Space Missions ECC Codes (code imperfectness)

Image File history File links NASA_ECC_Codes-imperfection. ... Image File history File links NASA_ECC_Codes-imperfection. ...

History

The method was introduced by Berrou, Glavieux, and Thitimajshima (from ENST Bretagne, France) in their 1993 paper: "Near Shannon Limit error-correcting coding and decoding: Turbo-codes" published in the Proceedings of IEEE International Communications Conference [1]. Turbo code refinements and implementation are an area of active research at a number of universities. Claude Berrou (born September 23, French professor in electrical engineering at École Nationale Supérieure des Télécommunications de Bretagne who is the coinventor with Alain Glavieux and Punya Thitimajshima of a groundbreaking coding scheme called turbo codes. ... Alain Glavieux was a French professor in electrical engineering at École Nationale Supérieure des Télécommunications de Bretagne. ... Punya Thitimajshima (1954 - 9 May 2006), a Thai professor in the department of telecommunications engineering at King Mongkuts Institute of Technology at Ladkrabang, is the co-inventor with Claude Berrou and Alain Glavieux of a groundbreaking coding scheme called turbo codes. ... The École Nationale Supérieure des Télécommunications de Bretagne (ENST Bretagne, sometimes known as Télécom Bretagne or even Télécom Brest) is a French research centre and high level training institution in Information Technologies and telecommunications. ... Year 1993 (MCMXCIII) was a common year starting on Friday (link will display full 1993 Gregorian calendar). ...

The encoder

The encoder sends three sub-blocks of bits. The first sub-block is the m-bit block of payload data. The second sub-block is n/2 parity bits for the payload data, computed using a recursive systematic convolutional code (RSC code). The third sub-block is n/2 parity bits for a known permutation of the payload data, again computed using a RSC convolutional code. That is, two redundant but different sub-blocks of parity bits for the sent payload. The complete block has m+n bits of data with a code rate of m/(m+n). The permutation of the payload data is carried out by a device called interleaver. In telecommunication, a convolutional code is a type of error-correcting code in which (a) each m-bit information symbol (each m-bit string) to be encoded is transformed into an n-bit symbol, where m/n is the code rate (n ≥ m) and (b) the transformation is a function... Permutation is the rearrangement of objects or symbols into distinguishable sequences. ... Permutation is the rearrangement of objects or symbols into distinguishable sequences. ... ...

Hardware-wise, turbo-code encoder consists of two identical RSC coders, С₁ and C₂, as depicted on the figure, which are connected to each other using a concatenation scheme, called parallel concatenation:

Image File history File links This is a lossless scalable vector image. ...

On a figure, M is a memory register. Delay line and interleaver force input bits d_k to appear in different sequences. At first iteration, the input sequence d_k appears at both outputs of the encoder, x_k and y_1k or y_2k due to the encoder's systematic character. If the encoders C₁ and C₂ are used respectively in n₁ and n₂ iterations, their rates are respectively equal to

, .

The decoder

The decoder is built in the similar way as the above encoder - two elementary decoders are interconnected to each other, but in serial way, not parallel. The DEC₁ decoder operates on lower speed (i.e. R₁), thus, it is intended for the C₁ encoder, and DEC₂ is for C₂ correspondingly. DEC₁ yields a soft decision which causes L₁ delay. The same delay is caused by the delay line in the encoder. The DEC₂'s operation causes L₂ delay.

Image File history File links This is a lossless scalable vector image. ...

An interleaver installed between two decoders is used here to scatter error busts coming from DEC₁ output. DI block is a demultiplexing and insertion module. It works as a switch, redirecting input bits to DEC₁ at one moment and to DEC₂ at another. In OFF state, it feeds both y_1k and y_2k inputs with padding bits (zeros).

Consider a memoryless AWGN channel and assume that at k-th iteration, the decoder receives a couple of random variables: In communications, the additive white Gaussian noise (AWGN) channel is one in which the only impairment is the linear addition of wideband Gaussian noise with a constant spectral density (expressed as watts per hertz of bandwidth). ...

,

where a_k and b_k are independent noise components having the same variance σ². Y_k is a k-th bit from y_k encoder output.

Redundant information is demultiplexed and sent through DI to DEC₁ (when y_k=y_1k) and to DEC₂ (when y_k=y_2k).

DEC₁ yields a soft decision, i.e.:

and delivers it to DEC₂. Λ(d_k) is called the logarithm of likelihood ratio (LLR). p(d_k=i), _i=0,1 is a posteriori probability (APP) of the d_k data bit which shows the probability of interpreting a recevied d_k bit as i. Taking LLR into account, DEC₂ yields a hard decision, i.e. a decoded bit.

It's well known that a Viterbi algorithm is unable to calculate APP, thus it cannot be used in DEC₁. Instead of that, modified Bahl algorithm is used. For DEC₂, Viterbi algorithm is an appropriate one. The Viterbi algorithm, named after its developer Andrew Viterbi, is a dynamic programming algorithm for finding the most likely sequence of hidden states – known as the Viterbi path – that result in a sequence of observed events, especially in the context of hidden Markov models. ... The Viterbi algorithm, named after its developer Andrew Viterbi, is a dynamic programming algorithm for finding the most likely sequence of hidden states – known as the Viterbi path – that result in a sequence of observed events, especially in the context of hidden Markov models. ...

However, the depicted structure is not optimal, because DEC₁ uses only a fraction of available redundant information. In order to improve the structure, a feedback loop is often used (dotted line on a figure).

Soft decision approach

The decoder front-end produces an integer for each bit in the data stream. This integer is a measure of how likely it is that the bit is a 0 or 1 and is also called soft bit. The integer could be drawn from the range [-127, 127], where:

• -127 means "certainly 0"
• -100 means "very likely 0"
• 0 means "it could be either 0 or 1"
• 100 means "very likely 1"
• 127 means "certainly 1"
• etc

This introduces a probabilistic aspect to the data-stream from the front end, but it conveys more information about each bit than just 0 or 1.

For example, for each bit, the front end of a traditional wireless-receiver has to decide if an internal analog voltage is above or below a given threshold voltage level. For a turbo-code decoder, the front end would provide an integer measure of how far the internal voltage is from the given threshold.

To decode the m+n-bit block of data, the decoder front-end creates a block of likelihood measures, with one likelihood measure for each bit in the data stream. There are two parallel decoders, one for each of the n/2-bit parity sub-blocks. Both decoders use the sub-block of m likelihoods for the payload data. The decoder working on the second parity sub-block knows the permutation that the coder used for this sub-block.

Solving hypotheses to find bits

The key innovation of turbo codes is how they use the likelihood data to reconcile differences between the two decoders. Each of the two convolutional decoders generates a hypothesis (with derived likelihoods) for the pattern of m bits in the payload sub-block. The hypothesis bit-patterns are compared, and if they differ, the decoders exchange the derived likelihoods they have for each bit in the hypotheses. Each decoder incorporates the derived likelihood estimates from the other decoder to generate a new hypothesis for the bits in the payload. Then they compare these new hypotheses. This iterative process continues until the two decoders come up with the same hypothesis for the m-bit pattern nn of the payload, typically in 15 to 18 cycles.

An analogy can be drawn between this process and that of solving cross-reference puzzles like crossword or sudoku. Consider a partially-completed, possibly garbled crossword puzzle. Two puzzle solvers (decoders) are trying to solve it: one possessing only the "down" clues (parity bits), and the other possessing only the "across" clues. To start, both solvers guess the answers (hypotheses) to their own clues, noting down how confident they are in each letter (payload bit). Then, they compare notes, by exchanging answers and confidence ratings with each other, noticing where and how they differ. Based on this new knowledge, they both come up with updated answers and confidence ratings, repeating the whole process until they converge to the same solution. A crossword is a word puzzle that normally takes the form of a square grid of black and white squares. ... A sudoku puzzle. ...

Practical applications using Turbo Codes

Telecommunications:

• Turbo codes are used extensively in 3G mobile telephony standards.
• MediaFLO, terrestrial mobile television system from Qualcomm
• New NASA missions such as Mars Reconnaissance Orbiter now use Turbo Codes, as an alternative to RS-Viterbi codes.
• Turbo coding such as Block Turbo Coding and Convolutional Turbo Coding are used in IEEE 802.16, a wireless metropolitan network standard.

This article does not cite any references or sources. ... MediaFLO is Qualcomms new technology to broadcast video to portable devices, like cell phones. ... Qualcomm (NASDAQ: QCOM) is a wireless telecommunications research and development company based in San Diego, California. ... The National Aeronautics and Space Administration (NASA) is an agency of the United States federal government, responsible for the nations public space program. ... NASAs Mars Reconnaissance Orbiter (MRO) is a multipurpose spacecraft designed to conduct reconnaissance and exploration of Mars from orbit. ... A viterbi decoder uses the Viterbi algorithm for decoding a bitstream that has been encoded using Forward error correction based on a Convolutional code. ... The IEEE 802. ...

Bayesian formulation

From an artificial intelligence viewpoint, turbo codes can be considered as an instance of loopy belief propagation in Bayesian networks. Garry Kasparov playing against Deep Blue, the first machine to win a chess game against a reigning world champion. ... Belief propagation is an iterative algorithm for computing marginals of functions on a graphical model most commonly used in artificial intelligence and information theory. ... A bayesian network (or a belief network) is a probabilistic graphical model that represents a set of variables and their probabilistic dependencies. ...

See also

• Convolutional code
• Viterbi algorithm
• Soft decision
• Interleaver

In telecommunication, a convolutional code is a type of error-correcting code in which (a) each m-bit information symbol (each m-bit string) to be encoded is transformed into an n-bit symbol, where m/n is the code rate (n ≥ m) and (b) the transformation is a function... The Viterbi algorithm, named after its developer Andrew Viterbi, is a dynamic programming algorithm for finding the most likely sequence of hidden states – known as the Viterbi path – that result in a sequence of observed events, especially in the context of hidden Markov models. ... ...

External links

• "The UMTS Turbo Code and an Efficient Decoder Implementation Suitable for Software-Defined Radios" (International Journal of Wireless Information Networks)
• Dana Mackenzie (2005). "Take it to the limit". New Scientist 187 (2507): 38–41. ISSN 0262-4079.  (preview, copy)
• "Pushing the Limit", a Science News feature about the development and genesis of turbo codes
• Coded Modulation Library, an open source library for simulating turbo codes in matlab
• "Turbo Equalization: Principles and New Results", an IEEE Transactions on Communications article about using turbo codes jointly with channel equalization.