Ininformation theory,turbo codes are a class of high-performanceforward error correction (FEC) codes developed around 1990–91, but first published in 1993. They were the first practical codes to closely approach the maximum channel capacity orShannon limit, a theoretical maximum for thecode rate at which reliable communication is still possible given a specific noise level. Turbo codes are used in3G/4G mobile communications (e.g., inUMTS andLTE) and in (deep space)satellitecommunications as well as other applications where designers seek to achieve reliable information transfer over bandwidth- or latency-constrained communication links in the presence of data-corrupting noise. Turbo codes compete withlow-density parity-check (LDPC) codes, which provide similar performance. Until the patent for turbo codes expired,^[1] the patent-free status of LDPC codes was an important factor in LDPC's continued relevance.^[2]

The name "turbo code" arose from the feedback loop used during normal turbo code decoding, which was analogized to the exhaust feedback used for engineturbocharging.Hagenauer has argued the term turbo code is a misnomer since there is no feedback involved in the encoding process.^[3]

The fundamental patent application for turbo codes was filed on 23 April 1991. The patent application listsClaude Berrou as the sole inventor of turbo codes. The patent filing resulted in several patents includingUS Patent 5,446,747, which expired 29 August 2013.

The first public paper on turbo codes was "Near Shannon Limit Error-correcting Coding and Decoding: Turbo-codes".^[4] This paper was published 1993 in the Proceedings of IEEE International Communications Conference. The 1993 paper was formed from three separate submissions that were combined due to space constraints. The merger caused the paper to list three authors: Berrou,Glavieux, andThitimajshima (from Télécom Bretagne, formerENST Bretagne, France). However, it is clear from the original patent filing that Berrou is the sole inventor of turbo codes and that the other authors of the paper contributed material other than the core concepts.^{[improper synthesis]}

Turbo codes were so revolutionary at the time of their introduction that many experts in the field of coding did not believe the reported results. When the performance was confirmed a small revolution in the world of coding took place that led to the investigation of many other types of iterative signal processing.^[5]

The first class of turbo code was the parallel concatenated convolutional code (PCCC). Since the introduction of the original parallel turbo codes in 1993, many other classes of turbo code have been discovered, includingserial concatenated convolutional codes andrepeat-accumulate codes. Iterative turbo decoding methods have also been applied to more conventional FEC systems, including Reed–Solomon corrected convolutional codes, although these systems are too complex for practical implementations of iterative decoders. Turbo equalization also flowed from the concept of turbo coding.

In addition to turbo codes, Berrou also invented recursive systematic convolutional (RSC) codes, which are used in the example implementation of turbo codes described in the patent. Turbo codes that use RSC codes seem to perform better than turbo codes that do not use RSC codes.

Prior to turbo codes, the best constructions were serialconcatenated codes based on an outerReed–Solomon error correction code combined with an innerViterbi-decoded short constraint lengthconvolutional code, also known as RSV codes.

In a later paper, Berrou gave 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.^[6]

There are many different instances of turbo codes, using different component encoders, input/output ratios, interleavers, andpuncturing patterns. This example encoder implementation describes a classic turbo encoder, and demonstrates the general design of parallel turbo codes.

This encoder implementation sends three sub-blocks of bits. The first sub-block is them-bit block of payload data. The second sub-block isn/2 parity bits for the payload data, computed using a recursive systematicconvolutional code (RSC code). The third sub-block isn/2 parity bits for a knownpermutation of the payload data, again computed using an RSC code. Thus, two redundant but different sub-blocks of parity bits are sent with the payload. The complete block hasm +n bits of data with a code rate ofm/(m +n). Thepermutation of the payload data is carried out by a device called aninterleaver.

Hardware-wise, this turbo code encoder consists of two identical RSC coders,C₁ andC₂, as depicted in the figure, which are connected to each other using a concatenation scheme, calledparallel concatenation:

In the figure,M is a memory register. The delay line and interleaver force input bits d_k to appear in different sequences.At first iteration, the input sequenced_k appears at both outputs of the encoder,x_k and y_1k ory_2k due to the encoder's systematic nature. If the encodersC₁ andC₂ are used inn₁ andn₂ iterations, their rates are respectively equal to

The decoder is built in a similar way to the above encoder. Two elementary decoders are interconnected to each other, but in series, not in parallel. The${\displaystyle DE{C}_1}$ decoder operates on lower speed (i.e.,${\displaystyle R_1}$), thus, it is intended for the${\displaystyle C_1}$ encoder, and${\displaystyle DE{C}_2}$ is for${\displaystyle C_2}$ correspondingly.${\displaystyle DE{C}_1}$ yields asoft decision which causes${\displaystyle L_1}$ delay. The same delay is caused by the delay line in the encoder. The${\displaystyle DE{C}_2}$'s operation causes${\displaystyle L_2}$ delay.

An interleaver installed between the two decoders is used here to scatter error bursts coming from${\displaystyle DE{C}_1}$ output.DI block is a demultiplexing and insertion module. It works as a switch, redirecting input bits to${\displaystyle DE{C}_1}$ at one moment and to${\displaystyle DE{C}_2}$ at another. In OFF state, it feeds both${\displaystyle y_{1k}}$ and${\displaystyle y_{2k}}$ inputs with padding bits (zeros).

Consider a memorylessAWGN channel, and assume that atk-th iteration, the decoder receives a pair of random variables:

where${\displaystyle a_k}$ and${\displaystyle b_k}$ are independent noise components having the same variance${\displaystyle {\sigma }^2}$.${\displaystyle Y_k}$ is ak-th bit from${\displaystyle y_k}$ encoder output.

Redundant information is demultiplexed and sent throughDI to${\displaystyle DE{C}_1}$ (when${\displaystyle y_k=y_{1k}}$) and to${\displaystyle DE{C}_2}$ (when${\displaystyle y_k=y_{2k}}$).

${\displaystyle DE{C}_1}$ yields a soft decision; i.e.:

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

and delivers it to${\displaystyle DE{C}_2}$.${\displaystyle \mathrm{\Lambda }(d_k)}$ is called thelogarithm of the likelihood ratio (LLR).${\displaystyle p(d_k=i),i\in \{0,1\}}$ is thea posteriori probability (APP) of the${\displaystyle d_k}$ data bit which shows the probability of interpreting a received${\displaystyle d_k}$ bit as${\displaystyle i}$. Taking theLLR into account,${\displaystyle DE{C}_2}$ yields a hard decision; i.e., a decoded bit.

It is known that theViterbi algorithm is unable to calculate APP, thus it cannot be used in${\displaystyle DE{C}_1}$. Instead of that, a modifiedBCJR algorithm is used. For${\displaystyle DE{C}_2}$, theViterbi algorithm is an appropriate one.

However, the depicted structure is not an optimal one, because${\displaystyle DE{C}_1}$ uses only a proper fraction of the available redundant information. In order to improve the structure, a feedback loop is used (see the dotted line on the figure).

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 calledsoft 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"

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 them +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 then⁄2-bit parity sub-blocks. Both decoders use the sub-block ofm 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.

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 ofm 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 them-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 likecrossword orsudoku. 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.

Turbo codes perform well due to the attractive combination of the code's random appearance on the channel together with the physically realisable decoding structure. Turbo codes are affected by anerror floor.

Telecommunications:

• Turbo codes are used extensively in3G and4G mobile telephony standards; e.g., inHSPA,EV-DO andLTE.
• MediaFLO, terrestrial mobile television system fromQualcomm.
• Theinteraction channel ofsatellite communication systems, such asDVB-RCS^[7] andDVB-RCS2.
• RecentNASA missions such asMars Reconnaissance Orbiter use turbo codes as an alternative toReed–Solomon error correction-Viterbi decoder codes.
• IEEE 802.16 (WiMAX), a wireless metropolitan network standard, uses block turbo coding and convolutional turbo coding.

From anartificial intelligence viewpoint, turbo codes can be considered as an instance of loopybelief propagation inBayesian networks.^[8]

• BCJR algorithm
• Convolutional code
• Forward error correction
• Interleaver
• Low-density parity-check code
• Serial concatenated convolutional codes
• Soft-decision decoding
• Turbo equalizer
• Viterbi algorithm

• Battail, Gérard (1998). "A conceptual framework for understanding turbo codes".IEEE Journal on Selected Areas in Communications.916 (2):245–254.doi:10.1109/49.661112.
• Brejza, M.F.; Li, L.; Maunder, R.G.; Al-Hashimi, B.M.; Berrou, C.; Hanzo, L. (2016)."20 years of turbo coding and energy-aware design guidelines for energy-constrained wireless applications"(PDF).IEEE Communications Surveys & Tutorials.918 (1):8–28.doi:10.1109/COMST.2015.2448692.S2CID 12966388.
• Garzón-Bohórquez, Ronald; Nour, Charbel Abdel; Douillard, Catherine (2016).Improving Turbo codes for 5G with parity puncture-constrained interleavers(PDF). 9th International Symposium on Turbo Codes and Iterative Information Processing (ISTC). pp. 151–5.doi:10.1109/ISTC.2016.7593095.

• Guizzo, Erico (March 2004)."Closing In On The Perfect Code".IEEE Spectrum.41 (3):36–42.doi:10.1109/MSPEC.2004.1270546.S2CID 21237188. Archived fromthe original on 11 October 2009.
• "The UMTS Turbo Code and an Efficient Decoder Implementation Suitable for Software-Defined Radios"Archived 20 October 2016 at theWayback Machine (International Journal of Wireless Information Networks)
• Mackenzie, Dana (2005)."Take it to the limit".New Scientist.187 (2507):38–41.
• "Pushing the Limit", aScience News feature about the development and genesis of turbo codes
• International Symposium On Turbo Codes
• Coded Modulation Library, an open source library for simulating turbo codes in matlab
• "Turbo Equalization: Principles and New Results"Archived 27 February 2009 at theWayback Machine, anIEEE Transactions on Communications article about using convolutional codes jointly with channel equalization.
• IT++ Home Page TheIT++ is a powerful C++ library which in particular supports turbo codes
• Turbo codes publications by David MacKay
• AFF3CT Home Page (A Fast Forward Error Correction Toolbox) for high speed turbo codes simulations in software
• Kerouédan, Sylvie;Berrou, Claude (2010)."Turbo code".Scholarpedia.5 (4). scholarpedia.org: 6496.Bibcode:2010SchpJ...5.6496K.doi:10.4249/scholarpedia.6496.
• 3GPP LTE Turbo Reference Design.
• Estimate Turbo Code BER Performance in AWGNArchived 1 February 2019 at theWayback Machine (MatLab).
• Parallel Concatenated Convolutional Coding: Turbo Codes (MatLab Simulink)

• Error detection and correction
• Capacity-approaching codes
• French inventions

• Articles with short description
• Short description matches Wikidata
• Use dmy dates from January 2020
• Use American English from March 2019
• All Wikipedia articles written in American English
• Articles that may contain original research from February 2021
• Webarchive template wayback links