Turbo code: Difference between revisions

Revision as of 06:52, 22 April 2019

Latest revision as of 20:06, 25 May 2025

(46 intermediate revisions by 30 users not shown)

Line 1:

{{Short description|High-performance forward error correction codes}}

{{Use dmy dates|date=SeptemberJanuary 20102020}}

{{Use American English|date = March 2019}}

In [[information theory]], '''turbo codes''' (originally in French ''Turbocodes'') are a class of high-performance [[forward error correction]] (FEC) codes developed around 1990–91, (but first published in 1993),. whichThey were the first practical codes to closely approach the maximum channel capacity or [[Shannon–Hartley theorem|channelShannon capacitylimit]], a theoretical maximum for the [[code rate]] at which reliable communication is still possible given a specific noise level. Turbo codes are used in [[3G]]/[[4G]] mobile communications (e.g., in [[UMTS]] and [[LTE (telecommunication)|LTE]]) and in ([[Deep Space Network|deep space]]) [[satellite]] [[telecommunication|communications]] 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 are nowadays competingcompete with [[LDPCLow-density parity-check code|low-density parity-check]]s (LDPC) codes, which provide similar performance. Until the patent for turbo codes expired,<ref>{{cite patent |url=https://www.google.com/patents/US5446747 |country=US |number=5446747}}</ref> the patent-free status of LDPC codes was an important factor in LDPC's continued relevance.<ref name="Closing">{{cite journal |author=Erico Guizzo |title=CLOSING IN ON THE PERFECT CODE |journal=IEEE Spectrum |date=Mar 1, 2004 |url=https://spectrum.ieee.org/closing-in-on-the-perfect-code|archive-url=https://archive.today/20230423205925/https://spectrum.ieee.org/closing-in-on-the-perfect-code|url-status=dead|archive-date=23 April 2023}} "Another advantage, perhaps the biggest of all, is that the LDPC patents have expired, so companies can use them without having to pay for intellectual-property rights."</ref>

{{Short description|High-performance forward error correction codes}}

{{Use mdy dates|date = March 2019}}

In [[information theory]], '''turbo codes''' (originally in French ''Turbocodes'') are a class of high-performance [[forward error correction]] (FEC) codes developed around 1990–91 (but first published in 1993), which were the first practical codes to closely approach the [[Shannon–Hartley theorem|channel capacity]], a theoretical maximum for the [[code rate]] at which reliable communication is still possible given a specific noise level. Turbo codes are used in [[3G]]/[[4G]] mobile communications (e.g., in [[UMTS]] and [[LTE (telecommunication)|LTE]]) and in ([[Deep Space Network|deep space]]) [[satellite]] [[telecommunication|communications]] 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 are nowadays competing with [[LDPC code]]s, which provide similar performance.

The name "turbo code" arose from the feedback loop used during normal turbo code decoding, which was analogized to the exhaust feedback used for engine [[turbocharging]]. [[Joachim Hagenauer|Hagenauer]] has argued the term turbo code is a misnomer since there is no feedback involved in the encoding process.<ref>{{cite webjournal |url=http://www.ima.umn.edu/csg/bib/bib16.0429hage.pdf |first1=Joachim |last1=Hagenauer |title=ArchivedIterative Decoding of Binary Block and Convolutional copyCodes |accessdate=2014-03-20 March 2014 |deadurlurl-status=yesdead |archiveurl=https://web.archive.org/web/20130611235418/http://www.ima.umn.edu/csg/bib/bib16.0429hage.pdf |archivedate=11 June 2013 |dffirst2=dmyElke |last2=Offer |first3=Luiz |last3=Papke |volume=42 |issue=2 |date=March 1996 |journal=IEEE Transactions on Information Theory|pages=429–445 |doi=10.1109/18.485714 }}</ref>

==History==

The fundamental patent application for turbo codes was filed on 23 April 23, 1991. The patent application lists [[Claude Berrou]] as the sole inventor of turbo codes. The patent filing resulted in several patents including [https://wwwpatents.google.com/patentspatent/US5446747 US Patent 5,446,747], which expired 29 August 29, 2013.

The first public paper on turbo codes was "''Near Shannon Limit Error-correcting Coding and Decoding: Turbo-codes''".<ref>{{Citation|chapter-url=httphttps://www-elec.enst-bretagneresearchgate.frnet/equipepublication/berrou/Near%20Shannon%20Limit%20Error.pdf3604275 |firstfirst1=Claude |first2=Alain |first3=Punya |lastlast1=Berrou |author1-link=Claude Berrou|last2=Glavieux |author2-link=Alain Glavieux |last3=Thitimajshima |titleauthor3-link=Punya Thitimajshima |chapter=Near Shannon Limit Error – Correcting |accessdate=11 February 2010 |date=1993 |volume=2 |pages=1064–70 |doi=10.1109/ICC.1993.397441 |title=Proceedings of IEEE International Communications Conference|s2cid=17770377 }}</ref> 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: [[Claude Berrou|Berrou]], [[Alain Glavieux|Glavieux]], and [[Punya Thitimajshima|Thitimajshima]] (from Télécom Bretagne, former [[École Nationale Supérieure des Télécommunications de Bretagne|ENST Bretagne]], France). However, it is clear from the original patent filing that Claude Berrou is the sole inventor of turbo codes and that the other authors of the paper contributed material other than the core concepts.{{Synthesis ofinline|date=February turbo codes.2021|sure=yes}}

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.<ref>{{cite journal |author=Erico Guizzo |title=CLOSING IN ON THE PERFECT CODE |journal=IEEE Spectrum |date=Mar 1, 2004 |url=https://spectrum.ieee.org/closing-in-on-the-perfect-code|archive-url=https://archive.today/20230423205925/https://spectrum.ieee.org/closing-in-on-the-perfect-code|url-status=dead|archive-date=23 April 2023}}</ref>

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, including serial versions [[serial concatenated convolutional codes]] and [[repeat-accumulate code]]s. Iterative turbo decoding methods have also been applied to more conventional FEC systems, including Reed-SolomonReed–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 theturbo invention of Turbo Codescodes, Claude Berrou also invented recursive systematic convolutional (RSC) codes, which are used in the example implementation of turbo codes described in the patent. Turbo Codescodes that use RSC codes seem to perform better than Turboturbo codes that do not use RSC codes.

Prior to turbo codes, the best constructions were serial [[concatenated code]]s based on an outer [[Reed-SolomonReed–Solomon error correction]] code combined with an inner [[Viterbi algorithm|Viterbi-decoded]] short constraint length [[convolutional code]], also known as RSV codes.

In a later paper, Berrou generously gave credit to the intuition of "G. Battail, [[Joachim Hagenauer|J. Hagenauer]] and P. Hoeher, who, in the late 80s, highlighted the interest of probabilistic processing." He adds "[[Robert G. Gallager|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.<ref>{{Citation|first=Claude|last=Berrou|title=The ten-year-old turbo codes are entering into service|___location=Bretagne, France|accessdate=11 February 2010|url=https://www.researchgate.net/publication/3199004_The_ten-year-old_turbo_codes_are_entering_into_service3199004}}</ref>

==An example encoder==

There are many different instances of turbo codes, using different component encoders, input/output ratios, interleavers, and [[Punctured code|puncturing 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 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 an RSC code. Thus, two redundant but different sub-blocks of parity bits are sent with the payload. The complete block has {{nowrap|''m'' + ''n''}} bits of data with a code rate of {{nowrap|''m''/(''m'' + ''n'')}}. The [[permutation]] of the payload data is carried out by a device called an [[interleaver]].

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

[[File:turbo encoder.svg]]

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 sequence ''d''_k appears at both outputs of the encoder, ''x''_k and'' y''_1k or ''y''_2k due to the encoder's systematic nature. If the encoders ''C''₁ and ''C''₂ are used respectively in ''n''₁ and ''n''₂ iterations, their rates are respectively equal to

:<math>\begin{align}

Line 74 ⟶ 73:

* 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 {{nowrap|''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 {{frac|''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==

Line 95 ⟶ 93:

* [[MediaFLO]], terrestrial mobile television system from [[Qualcomm]].

* The [[return link|interaction channel]] of [[satellite communication]] systems, such as [[DVB-RCS]]<ref>[http://www.etsi.org/deliver/etsi_en/301700_301799/301790/01.05.01_60/en_301790v010501p.pdf Digital Video Broadcasting (DVB); Interaction channel for Satellite Distribution Systems], ETSI EN 301 790, V1.5.1, May 2009.</ref> and [http://www.dvb.org/standards/dvb-rcs2 DVB-RCS2].

* NewRecent [[NASA]] missions such as [[Mars Reconnaissance Orbiter]] now use turbo codes, as an alternative to [[Reed–Solomon_error_correction|RSReed–Solomon error correction]]-[[Viterbi decoder|Viterbi]] codes.

* Turbo coding such as block turbo coding and convolutional turbo coding are used in [[IEEE 802.16]] ([[WiMAX]]), a wireless metropolitan network standard, uses block turbo coding and convolutional turbo coding.

==Bayesian formulation==

From an [[artificial intelligence]] viewpoint, turbo codes can be considered as an instance of loopy [[belief propagation]] in [[Bayesian network]]s.<ref>{{Citation

| author1last1=McEliece, |first1=Robert J. | author1-link=Robert McEliece

| author2last2=MacKay, |first2=David J. C. | author2-link=David J. C. MacKay

| author3last3=Cheng, |first3=Jung-Fu

| title=Turbo decoding as an instance of Pearl's "belief propagation" algorithm

| journal=IEEE Journal on Selected Areas in Communications

Line 112 ⟶ 110:

| doi=10.1109/49.661103

| postscript=.

| url=https://authors.library.caltech.edu/6938/1/MCEieeejstc98.pdf

}}</ref>

==See also==

* [[BCJR algorithm]]

* [[Convolutional code]]

* [[ViterbiForward algorithmerror correction]]

* [[Soft-decision decoding]]

* [[Interleaver]]

* [[BCJR algorithm]]

* [[Low-density parity-check code]]

* [[Serial concatenated convolutional codes]]

* [[Soft-decision decoding]]

* [[Turbo equalizer]]

* [[ForwardViterbi error correctionalgorithm]]

==References==

{{reflistReflist}}

==Further reading==

===Publications===

* {{cite journal |last=Battail |first=Gérard |title=A conceptual framework for understanding turbo codes |journal=IEEE Journal on Selected Areas in Communications |volume=916 |issue=2 |date=1998 |pages=245–254|doi=10.1109/49.661112 }}

* {{cite journal |last1=Brejza |first1=M.F. |last2=Li |first2=L. |last3=Maunder |first3=R.G. |last4=Al-Hashimi |first4=B.M. |last5=Berrou |first5=C. |last6=Hanzo |first6=L. |url=https://eprints.soton.ac.uk/378161/1/tutorial.pdf |doi=10.1109/COMST.2015.2448692

|title=20 years of turbo coding and energy-aware design guidelines for energy-constrained wireless applications |journal=IEEE Communications Surveys & Tutorials |volume=918 |issue=1 |date=2016 |pages=8–28|s2cid=12966388 }}

*{{cite conference |last1=Garzón-Bohórquez |first1=Ronald |first2=Charbel Abdel |last2=Nour |first3=Catherine |last3=Douillard |title=Improving Turbo codes for 5G with parity puncture-constrained interleavers |conference=9th International Symposium on Turbo Codes and Iterative Information Processing (ISTC)|date=2016 |pages=151–5 |url=https://hal.science/hal-01421989/file/Final%20Manuscript.pdf |doi=10.1109/ISTC.2016.7593095}}

==External links==

* [{{cite journal |first=Erico |last=Guizzo |url=https://spectrum.ieee.org/computing/software/closing-in-on-the-perfect-code |archive-url=https://web.archive.org/web/20091011113149/http://www.spectrum.ieee.org/computing/software/closing-in-on-the-perfect-code "|url-status=dead |archive-date=11 October 2009 |title=Closing In On The Perfect Code"], |journal=IEEE Spectrum, |date=March 2004 |volume=41 |issue=3 |pages=36–42 |doi=10.1109/MSPEC.2004.1270546 |s2cid=21237188 |url-access=subscription }}

* [http://www.csee.wvu.edu/~mvalenti/documents/valenti01.pdf "The UMTS Turbo Code and an Efficient Decoder Implementation Suitable for Software-Defined Radios"] {{Webarchive|url=https://web.archive.org/web/20161020193559/http://www.csee.wvu.edu/~mvalenti/documents/valenti01.pdf |date=20 October 2016 }} (''International Journal of Wireless Information Networks'')

* {{Citationcite |journal author|first=Dana |last=Mackenzie | title=Take it to the limit | journal=New Scientist | volume=187 | issue=2507 | year=2005 | pages=38–41 | postscripturl=. | issn=0262-4079 }} ([https://www.newscientist.com/article.ns?id=mg18725071.400 preview], [https://web.archive.org/web/20060902150939/http://geilenkotten.homeunix.org/TC_NS_09072005.pdf copy])}}

* [httphttps://www.sciencenews.org/articlesarticle/20051105/bob8.asppushing-limit "Pushing the Limit"], a ''[[Science News]]'' feature about the development and genesis of turbo codes

* [http://www-turbo.enst-bretagne.fr/ International Symposium On Turbo Codes]

* [http://www.iterativesolutions.com/Matlab.htm Coded Modulation Library], an open source library for simulating turbo codes in matlab

* [http://www.ifp.uiuc.edu/~singer/journalpapers/tuchler_2002a.pdf "Turbo Equalization: Principles and New Results"] {{Webarchive|url=https://web.archive.org/web/20090227062216/http://www.ifp.uiuc.edu/~singer/journalpapers/tuchler_2002a.pdf |date=27 February 2009 }}, an ''[[IEEE Transactions on Communications]]'' article about using convolutional codes jointly with channel equalization.

* [http://itpp.sourceforge.net IT++ Home Page] The [[IT++]] is a powerful C++ library which in particular supports turbo codes

* [http://www.inference.phy.cam.ac.uk/mackay/CodesTurbo.html Turbo codes publications by David MacKay]

* [https://aff3ct.github.io AFF3CT Home Page] ([[AFF3CT|A Fast Forward Error Correction Toolbox]]) for high speed turbo codes simulations in software

* [http://www.scholarpedia.org/article/Turbo_codes{{cite journal |title=Turbo code] by Dr. |first1=Sylvie |last1=Kerouédan and [[|author2-link=Claude Berrou|Dr. |first2=Claude |last2=Berrou]] (|journal=Scholarpedia |date=2010 |volume=5 |issue=4 |page=6496 |publisher=scholarpedia.org)|doi=10.4249/scholarpedia.6496 |doi-access=free |bibcode=2010SchpJ...5.6496K }}

* [https://www.intel.com/content/dam/www/programmable/us/en/pdfs/literature/an/an505.pdf 3GPP LTE Turbo Reference Design].

* [https://www.mathworks.com/help/comm/ug/estimate-turbo-code-ber-performance-in-awgn.html Estimate Turbo Code BER Performance in AWGN] {{Webarchive|url=https://web.archive.org/web/20190201172029/https://www.mathworks.com/help/comm/ug/estimate-turbo-code-ber-performance-in-awgn.html |date=1 February 2019 }} (MatLab).

* [https://www.mathworks.com/help/comm/examples/parallel-concatenated-convolutional-coding-turbo-codes.html Parallel Concatenated Convolutional Coding: Turbo Codes (MatLab Simulink)]

{{CCSDS|state=collapsed}}

{{Authority control}}

{{Use dmy dates|date=September 2010}}

{{DEFAULTSORT:Turbo Code}}

[[Category:Error detection and correction]]

[[Category:Capacity-approaching codes]]

[[Category:French inventions]]