Citizendia
Your Ad Here

In electrical engineering and digital communications, turbo codes are a class of high-performance error correction codes developed in 1993 which are 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 engineering, sometimes referred to as electrical and electronic engineering, is a field of Engineering that deals with the study and application of Digital communications refers to the transmission of a sequence of Digital messages (a Bit stream) or a digitized analog signal In Telecommunication and Information theory, forward error correction (FEC is a System of Error control for Data transmission, whereby This article is about artificial satellites For natural satellites also known as moons see Natural satellite.

Contents

Advantages

Of all practical error correction methods known to date, turbo codes and low-density parity-check codes (LDPCs) come closest to approaching the Shannon limit, the theoretical limit of maximum information transfer rate over a noisy channel. In Information theory, a low-density parity-check code (LDPC code is an Error correcting code, a method of transmitting a message over a noisy transmission In Information theory, the noisy-channel coding theorem establishes that however contaminated with noise interference a communication channel may be it is possible to communicate

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. Their main drawbacks are the relatively high decoding complexity and relatively high latency, which make them unsuitable for some applications. Latency is a time delay between the moment something is initiated and the moment one of its effects begins or becomes detectable For satellite use, this is not of great concern, since the transmission distance itself introduces latency due to the limited speed of light.

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 an Error-correcting code that works by Oversampling a Polynomial constructed from the data In Computer science, a block code is a type of Channel coding. The Viterbi algorithm is a Dynamic programming Algorithm for finding the most likely sequence of hidden states &ndash called the Viterbi path In Telecommunication, a convolutional code is a type of Error-correcting code in which (a each m - Bit Information symbol (each


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


Disadvantages

The Complexity of these algorithms and the fact that these algorithms have encumbering software patents are a detractor of implementing these algorithms in a system. Software patent does not have a universally accepted definition An open source codebase has yet to develop for Turbo Codes, due to their fairly low profile amongst all error correcting codes.

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]. Claude Berrou (born September 23, 1951) is a French professor in Electrical engineering at École Nationale Supérieure des Télécommunications Alain Glavieux (died 2004 was a French professor in Electrical engineering at École Nationale Supérieure des Télécommunications de Bretagne. Punya Thitimajshima (1955 - 9 May 2006 a Thai professor in the department of Telecommunications engineering at King Mongkut's Institute of Technology at Ladkrabang 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 Year 1993 ( MCMXCIII) was a Common year starting on Friday (link will display full 1993 Gregorian calendar) Berrou gives credit to the "intuition"of "G. Battail, J. Hagenauer and P. Hoeher, who, in the late 80s, highlighted the interest of probabilistic processing. " He adds "R. Gallager and M. Tanner had already imagined coding and decoding techniques whose general principles are closely related," although the necessary calculations were impractical at that time. [1]

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). In Telecommunication, a convolutional code is a type of Error-correcting code in which (a each m - Bit Information symbol (each The third sub-block is n/2 parity bits for a known permutation of the payload data, again computed using an RSC convolutional code. In several fields of Mathematics the term permutation is used with different but closely related meanings 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 several fields of Mathematics the term permutation is used with different but closely related meanings Interleaving in Computer science is a way to arrange Data in a non- Contiguous way in order to increase performance

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

Image:turbo encoder.svg

On the figure, M is a memory register. Delay line and interleaver force input bits dk to appear in different sequences. At first iteration, the input sequence dk appears at both outputs of the encoder, xk and y1k or y2k due to the encoder's systematic character. If the encoders C1 and C2 are used respectively in n1 and n2 iterations, their rates are respectively equal to

~R_1=\frac{n_1+n_2}{2n_1+n_2}, ~R_2=\frac{n_1+n_2}{2n_2+n_1}.

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 DEC1 decoder operates on lower speed (i. e. R1), thus, it is intended for the C1 encoder, and DEC2 is for C2 correspondingly. DEC1 yields a soft decision which causes L1 delay. The same delay is caused by the delay line in the encoder. The DEC2's operation causes L2 delay.

Image:turbo decoder.svg

An interleaver installed between two decoders is used here to scatter error bursts coming from DEC1 output. DI block is a demultiplexing and insertion module. It works as a switch, redirecting input bits to DEC1 at one moment and to DEC2 at another. In OFF state, it feeds both y1k and y2k 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:

~x_k=(2d_k-1)+a_k,
~y_k=2(Y_k-1)+b_k

where ak and bk are independent noise components having the same variance σ2. Explanation In communications, the additive white Gaussian noise ( AWGN) channel model is one in which the only impairment is the linear addition of Yk is a k-th bit from yk encoder output.

Redundant information is demultiplexed and sent through DI to DEC1 (when yk=y1k) and to DEC2 (when yk=y2k).

DEC1 yields a soft decision, i. e. :

\Lambda(d_k)=\log\frac{p(d_k=1)}{p(d_k=0)}

and delivers it to DEC2. Λ(dk) is called the logarithm of likelihood ratio (LLR). p(dk=i), i=0,1 is a posteriori probability (APP) of the dk data bit which shows the probability of interpreting a received dk bit as i. Taking LLR into account, DEC2 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 DEC1. The Viterbi algorithm is a Dynamic programming Algorithm for finding the most likely sequence of hidden states &ndash called the Viterbi path Instead of that, modified BCJR algorithm is used. For DEC2, Viterbi algorithm is an appropriate one. The Viterbi algorithm is a Dynamic programming Algorithm for finding the most likely sequence of hidden states &ndash called the Viterbi path

However, the depicted structure is not optimal, because DEC1 uses only a fraction of available redundant information. In order to improve the structure, a feedback loop is often used (dotted line on the 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:

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 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. is a Logic -based number-placement Puzzle. The objective is to fill a 9×9 grid so that each column each row and each of the nine 3×3 boxes (also called blocks 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.

Practical applications using Turbo Codes

Telecommunications:

Bayesian formulation

From an artificial intelligence viewpoint, turbo codes can be considered as an instance of loopy belief propagation in Bayesian networks. Belief propagation, also known as the sum-product algorithm, is an iterative Algorithm for computing marginals of functions on a Graphical model A Bayesian network (or a belief network) is a Probabilistic graphical model that represents a set of Variables and their probabilistic independencies

See also

References

  1. ^ Berrou comments at www-elec. In Telecommunication, a convolutional code is a type of Error-correcting code in which (a each m - Bit Information symbol (each The Viterbi algorithm is a Dynamic programming Algorithm for finding the most likely sequence of hidden states &ndash called the Viterbi path Interleaving in Computer science is a way to arrange Data in a non- Contiguous way in order to increase performance enst-bretagne. fr/equipe/berrou/com_mag_berrou. pdf

External links

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic