741:
753:
1827:
1979:
776:
838:
2568:
808:
2066:
36:
441:
2620:
1854:
2289:
2192:
385:
simply by not transmitting a portion of code symbols. The performance of a punctured convolutional code generally scales well with the amount of parity transmitted. The ability to perform economical soft decision decoding on convolutional codes, as well as the block length and code rate flexibility
2571:
A turbo code with component codes 13, 15. Turbo codes get their name because the decoder uses feedback, like a turbo engine. Permutation means the same as the interleaving. C1 and C2 are recursive convolutional codes. Recursive and non-recursive convolutional codes are not so much different in BER
303:
Convolutional codes are often described as continuous. However, it may also be said that convolutional codes have arbitrary block length, rather than being continuous, since most real-world convolutional encoding is performed on blocks of data. Convolutionally encoded block codes typically employ
156:
The ability to perform economical maximum likelihood soft decision decoding is one of the major benefits of convolutional codes. This is in contrast to classic block codes, which are generally represented by a time-variant trellis and therefore are typically hard-decision decoded. Convolutional
1819:
is not really a memory cell because it represents a current value). We will designate such a state as "10". According to an input bit the encoder at the next turn can convert either to the "01" state or the "11" state. One can see that not all transitions are possible for (e.g., a decoder can't
2534:
For example, if we want to make a code with rate 2/3 using the appropriate matrix from the above table, we should take a basic encoder output and transmit every first bit from the first branch and every bit from the second one. The specific order of transmission is defined by the respective
827:
2033:
algorithm is the best known. Unlike
Viterbi decoding, sequential decoding is not maximum likelihood but its complexity increases only slightly with constraint length, allowing the use of strong, long-constraint-length codes. Such codes were used in the
2207:
In fact, predefined convolutional codes structures obtained during scientific researches are used in the industry. This relates to the possibility to select catastrophic convolutional codes (causes larger number of errors).
2624:
148:
function to a data stream. The sliding application represents the 'convolution' of the encoder over the data, which gives rise to the term 'convolutional coding'. The sliding nature of the convolutional codes facilitates
2918:
Bhaskar, Vidhyacharan, and Laurie L. Joiner. "Performance of punctured convolutional codes in asynchronous CDMA communications under perfect phase-tracking conditions." Computers & Electrical
Engineering 30.8 (2004):
988:
1857:
Theoretical bit-error rate curves of encoded QPSK (recursive and non-recursive, soft decision), additive white
Gaussian noise channel. Curves are small distinguished due to approximately the same free distances and
1395:
1671:
2914:
Fiebig, U-C., and
Patrick Robertson. "Soft-decision and erasure decoding in fast frequency-hopping systems with convolutional, turbo, and Reed-Solomon codes." IEEE Transactions on Communications 47.11 (1999):
1522:
2678:
3rd
Generation Partnership Project (September 2012). "3GGP TS45.001: Technical Specification Group GSM/EDGE Radio Access Network; Physical layer on the radio path; General description". Retrieved 2013-07-20.
1935:
2925:
Chen, Yuh-Long, and Che-Ho Wei. "Performance evaluation of convolutional codes with MPSK on Rician fading channels." IEE Proceedings F-Communications, Radar and Signal
Processing. Vol. 134. No. 2. IET,
1951:
Free distance can be interpreted as the minimal length of an erroneous "burst" at the output of a convolutional decoder. The fact that errors appear as "bursts" should be accounted for when designing a
1830:
Img.6. A trellis diagram for the encoder on Img.1. A path through the trellis is shown as a red line. The solid lines indicate transitions where a "0" is input and the dashed lines where a "1" is input.
2045:
Both
Viterbi and sequential decoding algorithms return hard decisions: the bits that form the most likely codeword. An approximate confidence measure can be added to each bit by use of the
2911:
Chen, Qingchun, Wai Ho Mow, and
Pingzhi Fan. "Some new results on recursive convolutional codes and their applications." Information Theory Workshop, 2006. ITW'06 Chengdu. IEEE. IEEE, 2006.
798:
The example encoder in Img. 2. is an 8-state encoder because the 3 registers will create 8 possible encoder states (2). A corresponding decoder trellis will typically use 8 states as well.
1132:
1205:
801:
Recursive systematic convolutional (RSC) codes have become more popular due to their use in Turbo Codes. Recursive systematic codes are also referred to as pseudo-systematic codes.
576:) and wait for the next input bit. If there are no remaining input bits, the encoder continues shifting until all registers have returned to the zero state (flush bit termination).
2296:
Convolutional code with any code rate can be designed based on polynomial selection; however, in practice, a puncturing procedure is often used to achieve the required code rate.
1268:
2185:
2126:
153:
decoding using a time-invariant trellis. Time invariant trellis decoding allows convolutional codes to be maximum-likelihood soft-decision decoded with reasonable complexity.
1590:
1439:
1730:
2195:
Theoretical bit-error rate curves of encoded QPSK (soft decision), additive white
Gaussian noise channel. Longer constraint lengths produce more powerful codes, but the
740:
1767:
355:
298:
2265:
1033:
795:
Recursive codes are typically systematic and, conversely, non-recursive codes are typically non-systematic. It isn't a strict requirement, but a common practice.
383:
267:
221:
2885:
2203:
with constraint lengths, limiting these more powerful codes to deep space missions where the extra performance is easily worth the increased decoder complexity.
752:
193:
580:
444:
Stages of channel coding in GSM. Block encoder and Parity check – error detection part. Convolutional encoder and
Viterbi decoder – error correction part.
2922:
Modestino, J., and Shou Mui. "Convolutional code performance in the Rician fading channel." IEEE Transactions on Communications 24.6 (1976): 592-606.
402:
determined that convolutional codes could be maximum-likelihood decoded with reasonable complexity using time invariant trellis based decoders — the
2940:
2687:
Halonen, Timo, Javier Romero, and Juan Melero, eds. GSM, GPRS and EDGE performance: evolution towards 3G/UMTS. John Wiley & Sons, 2004. p. 430
820:
869:
2584:
with much less decoding complexity than the Viterbi algorithm on the long convolutional codes that would be required for the same performance.
789:
because the input data is also used in the output symbols (Output 2). Codes with output symbols that do not include the input data are called
734:
Non-systematic convolutional codes are more popular due to better noise immunity. It relates to the free distance of the convolutional code.
2867:
1279:
540:
is fed into the leftmost register. Using the generator polynomials and the existing values in the remaining registers, the encoder outputs
1598:
53:
2742:
1454:
2585:
1953:
465:
2589:
2039:
1961:
845:
Useful as constituent code in low error rate turbo codes for applications such as satellite links. Also suitable as SCCC outer code.
469:
2019:
1888:
398:. It was thought that convolutional codes could be decoded with arbitrary quality at the expense of computation and delay. In 1967,
119:
2836:
2657:
417:
around 1991. These codes proved especially useful for iterative processing including the processing of concatenated codes such as
100:
2635:
2050:
1987:
72:
2908:
Francis, Michael. "Viterbi Decoder Block Decoding-Trellis Termination and Tail Biting." Xilinx XAPP551 v2. 0, DD (2005): 1-21.
2629:
57:
2572:
performance, however, recursive type of is implemented in Turbo convolutional codes due to better interleaving properties.
2038:
of the early 1970s to Jupiter and Saturn, but gave way to shorter, Viterbi-decoded codes, usually concatenated with large
2011:
1046:, which is closely related to the generator polynomial. An impulse response is connected with a transfer function through
816:
79:
2581:
2015:
495:, each holding one input bit. Unless otherwise specified, all memory registers start with a value of 0. The encoder has
779:
Img.2. Rate 1/2 8-state recursive systematic convolutional encoder. Used as constituent code in 3GPP 25.212 Turbo Code.
477:
2882:
2731:
2719:
1834:
An actual encoded sequence can be represented as a path on this graph. One valid path is shown in red as an example.
2788:
86:
2605:
1841:: if a received sequence doesn't fit this graph, then it was received with errors, and we must choose the nearest
46:
1059:
429:
239:
because channel coding inserts redundancy in the input bits. The memory is often called the "constraint length"
2709:
Moon, Todd K. "Error correction coding." Mathematical Methods and Algorithms. Jhon Wiley and Son (2005). p. 508
2539:
2292:
Convolutional codes with 1/2 and 3/4 code rates (and constraint length 7, Soft decision, 4-QAM / QPSK / OQPSK).
2042:
codes that steepen the overall bit-error-rate curve and produce extremely low residual undetected error rates.
1782:
1769:. For instance, in the first example the constraint length is 3, and in the second the constraint length is 4.
1138:
461:
68:
2799:
1882:) of a convolutional code is the number of errors that can be corrected by the code. It can be calculated as
452:
Convolutional codes are used extensively to achieve reliable data transfer in numerous applications, such as
2580:, a new class of iterated short convolutional codes that closely approach the theoretical limits imposed by
425:
2230:
1682:
1211:
2764:
2753:
2131:
2072:
1957:
579:
445:
145:
141:
2312:) code. It is achieved by deleting of some bits in the encoder output. Bits are deleted according to a
1940:
Since a convolutional code doesn't use blocks, processing instead a continuous bitstream, the value of
1826:
1533:
1788:
448:
and Deinterleaving – code words separation increasing in time domain and to avoid bursty distortions.
2234:
2026:
1991:
1978:
1944:
applies to a quantity of errors located relatively near to each other. That is, multiple groups of
1401:
775:
500:
2779:
The Telecommunications and Data Acquisition Progress Report 42-63, March–April 1981 (1981): 33-39.
2700:
The Telecommunications and Data Acquisition Progress Report 42-63, March–April 1981 (1981): 33-39.
1690:
2669:
Eberspächer J. et al. GSM-architecture, protocols and services. John Wiley & Sons, 2008. p.97
2200:
1983:
492:
304:
termination. The arbitrary block length of convolutional codes can also be contrasted to classic
133:
93:
544:
symbols. These symbols may be transmitted or punctured depending on the desired code rate. Now
2856:
2046:
2007:
1982:
Bit error ratio curves for convolutional codes with different options of digital modulations (
1973:
1528:
1043:
811:
Img. 3. Two-state recursive systematic convolutional (RSC) code. Also called an 'accumulator.'
545:
403:
2877:
1739:
318:
157:
codes are often characterized by the base code rate and the depth (or memory) of the encoder
2811:
1871:
583:
Img.1. Rate 1/3 non-recursive, non-systematic convolutional encoder with constraint length 3
457:
2776:
276:
2889:
2226:
2212:
2035:
1778:
785:
772:
encoder. Here's an example of a recursive one and as such it admits a feedback structure:
530:
504:
424:
Using the "convolutional" terminology, a classic convolutional code might be considered a
150:
2244:
2014:
performance and is highly parallelizable. Viterbi decoders are thus easy to implement in
1016:
360:
246:
198:
2697:
308:, which generally have fixed block lengths that are determined by algebraic properties.
2297:
2283:
2054:
837:
407:
399:
312:
273:
in the polynomial or the maximum possible number of states of the encoder (typically:
160:
2934:
2812:"Convert convolutional code polynomials to trellis description – MATLAB poly2trellis"
453:
414:
2241:
of 15 and a rate of 1/6; this code performs about 2 dB better than the simpler
2852:
2639:
2267:
code at a cost of 256× in decoding complexity (compared to Voyager mission codes).
826:
2824:
2567:
2270:
The convolutional code with a constraint length of 2 and a rate of 1/2 is used in
2211:
An especially popular Viterbi-decoded convolutional code, used at least since the
1798:
Imagine that the encoder (shown on Img.1, above) has '1' in the left memory cell (
807:
2593:
2065:
2030:
2025:
Longer constraint length codes are more practically decoded with any of several
1047:
855:
395:
35:
17:
1994:
Algorithms. (Exact and Approximate) over additive white Gaussian noise channel.
2577:
2562:
2196:
1956:
with an inner convolutional code. The popular solution for this problem is to
1845:(fitting the graph) sequence. The real decoding algorithms exploit this idea.
1039:
473:
440:
418:
305:
243:, where the output is a function of the current input as well as the previous
406:. Other trellis-based decoder algorithms were later developed, including the
2853:
The on-line textbook: Information Theory, Inference, and Learning Algorithms
1999:
386:
of convolutional codes, makes them very popular for digital communications.
2872:
1853:
983:{\displaystyle y_{i}^{j}=\sum _{k=0}^{\infty }h_{k}^{j}x_{i-k}=(x*h^{j}),}
428:(FIR) filter, while a recursive convolutional code might be considered an
2722:." Mathematical Methods and Algorithms. Jhon Wiley and Son (2005).- p.508
2543:
507:
2873:
Fundamentals of Convolutional Decoders for Better Digital Communications
2002:
exist for decoding convolutional codes. For relatively small values of
2069:
Shift-register for the (7, ) convolutional code polynomial. Branches:
1390:{\displaystyle H_{1}(z)={\frac {1+z^{-1}+z^{-3}}{1-z^{-2}-z^{-3}}},\,}
460:(e.g., in GSM, GPRS, EDGE and 3G networks (until 3GPP Release 7)) and
1960:
data before convolutional encoding, so that the outer block (usually
269:
inputs. The depth may also be given as the number of memory elements
2743:
Estimate BER for Hard and Soft Decision Viterbi Decoding (MathWorks)
841:
Img. 5. Sixteen-state recursive systematic convolutional (RSC) code.
1666:{\displaystyle \operatorname {polydeg} (f)=\max(\deg(P),\deg(Q))\,}
2316:. The following puncturing matrices are the most frequently used:
2288:
2287:
2190:
2064:
1977:
1852:
1825:
836:
825:
806:
774:
476:
such constructions were the most efficient, coming closest to the
439:
2576:
Simple Viterbi-decoded convolutional codes are now giving way to
1517:{\displaystyle m=\max _{i}\operatorname {polydeg} (H_{i}(1/z))\,}
830:
Img. 4. Four-state recursive systematic convolutional (RSC) code.
2191:
2053:(MAP) soft decisions for each bit can be obtained by use of the
1948:
errors can usually be fixed when they are relatively far apart.
727:
systematic repeats the structure of the message before encoding
644:. Therefore, output bits are calculated (modulo 2) as follows:
311:
The code rate of a convolutional code is commonly modified via
144:
that generates parity symbols via the sliding application of a
2547:
2271:
1930:{\displaystyle t=\left\lfloor {\frac {d-1}{2}}\right\rfloor .}
1053:
Transfer functions for the first (non-recursive) encoder are:
315:. For example, a convolutional code with a 'mother' code rate
29:
2777:"Performance of concatenated codes for deep space missions."
1820:
convert from "10" state to "00" or even stay in "10" state).
2698:"Performance of concatenated codes for deep space missions."
2553:
Punctured convolutional codes are also called "perforated".
533:— one for each adder (see figure below). An input bit
1273:
Transfer functions for the second (recursive) encoder are:
853:
A convolutional encoder is called so because it performs a
2862:
849:
Impulse response, transfer function, and constraint length
746:
A short illustration of non-systematic convolutional code.
723:
Convolutional codes can be systematic and non-systematic:
413:
Recursive systematic convolutional codes were invented by
2765:
Digital modulation: Approximate LLR Algorithm (MathWorks)
2328:
Free distance (for NASA standard K=7 convolutional code)
1042:. Every output of an encoder can be described by its own
2187:. All of the math operations should be done by modulo 2.
819:
code implementation and as inner constituent code for
758:
A short illustration of systematic convolutional code.
2538:
Punctured convolutional codes are widely used in the
2247:
2134:
2075:
1891:
1742:
1693:
1601:
1536:
1457:
1404:
1282:
1214:
1141:
1062:
1019:
872:
363:
321:
279:
249:
201:
163:
2837:
Role of recursive convolutional codes in turbo codes
2658:
Role of recursive convolutional codes in turbo codes
834:
Useful for SCCC's and multidimensional turbo codes.
231:is the data rate of output channel encoded stream.
2754:
Digital modulation: Exact LLR Algorithm (MathWorks)
503:(a modulo 2 adder can be implemented with a single
357:may be punctured to a higher rate of, for example,
60:. Unsourced material may be challenged and removed.
2259:
2179:
2120:
1929:
1761:
1724:
1665:
1584:
1516:
1433:
1389:
1262:
1199:
1126:
1027:
982:
804:Other RSC codes and example applications include:
377:
349:
292:
261:
215:
187:
2775:Butman, S. A., L. J. Deutsch, and R. L. Miller.
2696:Butman, S. A., L. J. Deutsch, and R. L. Miller.
1823:All possible transitions can be shown as below:
1620:
1465:
394:Convolutional codes were introduced in 1955 by
27:Type of error-correcting code using convolution
2859:, discusses convolutional codes in Chapter 48.
2732:LLR vs. Hard Decision Demodulation (MathWorks)
2839:." Electronics Letters 31.11 (1995): 858-859.
2789:Global system for mobile communications (GSM)
2660:." Electronics Letters 31.11 (1995): 858-859.
8:
730:non-systematic changes the initial structure
2892:, discusses convolutional codes on page 48.
2308:rate code from a "basic" low-rate (e.g., 1/
1127:{\displaystyle H_{1}(z)=1+z^{-1}+z^{-2},\,}
488:To convolutionally encode data, start with
195:. The base code rate is typically given as
2883:Information Theory and Coding (TU Ilmenau)
2800:Punctured Convolutional Coding (MathWorks)
2557:Turbo codes: replacing convolutional codes
2246:
2171:
2152:
2139:
2133:
2112:
2093:
2080:
2074:
1902:
1890:
1874:between different encoded sequences. The
1758:
1741:
1721:
1710:
1698:
1692:
1662:
1600:
1581:
1564:
1535:
1513:
1499:
1487:
1468:
1456:
1430:
1409:
1403:
1386:
1371:
1355:
1334:
1318:
1305:
1287:
1281:
1259:
1247:
1219:
1213:
1200:{\displaystyle H_{2}(z)=z^{-1}+z^{-2},\,}
1196:
1184:
1168:
1146:
1140:
1123:
1111:
1095:
1067:
1061:
1020:
1018:
959:
931:
921:
916:
906:
895:
882:
877:
871:
367:
362:
339:
325:
320:
284:
278:
248:
205:
200:
162:
120:Learn how and when to remove this message
2835:Benedetto, Sergio, and Guido Montorsi. "
2656:Benedetto, Sergio, and Guido Montorsi. "
2566:
2318:
578:
468:with a hard-decision code, particularly
2649:
1964:) code can correct most of the errors.
859:of the input stream with the encoder's
821:serial concatenated convolutional codes
736:
464:. These codes are often implemented in
2018:hardware and in software on CPUs with
1038:A convolutional encoder is a discrete
768:The encoder on the picture above is a
2863:The Error Correcting Codes (ECC) Page
7:
2588:with an outer algebraic code (e.g.,
1849:Free distance and error distribution
1837:This diagram gives us an idea about
1263:{\displaystyle H_{3}(z)=1+z^{-2}.\,}
58:adding citations to reliable sources
2010:is universally used as it provides
2274:as an error correction technique.
2180:{\displaystyle h^{2}=133_{o}=_{b}}
2121:{\displaystyle h^{1}=171_{o}=_{b}}
1009:is an impulse response for output
907:
615:) of 3. Generator polynomials are
611:) encoder with constraint length (
548:all register values to the right (
436:Where convolutional codes are used
25:
1795:binary cells will have 2 states.
764:Recursive and non-recursive codes
2623: This article incorporates
2618:
2596:inherent to turbo code designs.
1585:{\displaystyle f(z)=P(z)/Q(z)\,}
751:
739:
34:
2636:General Services Administration
227:is the raw input data rate and
45:needs additional citations for
2941:Error detection and correction
2300:is a technique used to make a
2168:
2161:
2109:
2102:
1718:
1704:
1659:
1656:
1650:
1638:
1632:
1623:
1614:
1608:
1578:
1572:
1561:
1555:
1546:
1540:
1510:
1507:
1493:
1480:
1421:
1415:
1299:
1293:
1231:
1225:
1158:
1152:
1079:
1073:
974:
968:
965:
946:
182:
164:
1:
2278:Punctured convolutional codes
2047:Soft output Viterbi algorithm
2040:Reed–Solomon error correction
1805:), and '0' in the right one (
1787:A convolutional encoder is a
1434:{\displaystyle H_{2}(z)=1.\,}
1968:Decoding convolutional codes
1725:{\displaystyle H_{i}(1/z)\,}
1040:linear time-invariant system
2476:
2428:
2392:
2362:
2338:
2327:
2061:Popular convolutional codes
587:The figure below is a rate
2957:
2606:Quantum convolutional code
2560:
2548:Digital Video Broadcasting
2281:
2215:, has a constraint length
1971:
1776:
1001:is a sequence from output
2878:Convolutional codes (MIT)
2592:) addresses the issue of
2199:of the Viterbi algorithm
2029:algorithms, of which the
430:Infinite impulse response
2540:satellite communications
2535:communication standard.
1783:Trellis coded modulation
462:satellite communications
2720:Error correction coding
2201:increases exponentially
1762:{\displaystyle K=m+1\,}
783:The example encoder is
426:Finite impulse response
350:{\displaystyle n/k=1/2}
2631:Federal Standard 1037C
2625:public domain material
2573:
2293:
2261:
2231:Mars Exploration Rover
2204:
2188:
2181:
2122:
1995:
1931:
1859:
1831:
1763:
1726:
1681:is the maximum of the
1667:
1586:
1518:
1435:
1391:
1264:
1201:
1128:
1029:
997:is an input sequence,
984:
911:
842:
831:
812:
780:
584:
510:, where the logic is:
484:Convolutional encoding
449:
379:
351:
294:
263:
217:
189:
2570:
2291:
2262:
2194:
2182:
2123:
2068:
1981:
1932:
1876:correcting capability
1856:
1829:
1764:
1727:
1668:
1587:
1519:
1436:
1392:
1265:
1202:
1129:
1035:denotes convolution.
1030:
985:
891:
840:
829:
810:
778:
582:
531:generator polynomials
458:mobile communications
443:
380:
352:
295:
293:{\displaystyle 2^{v}}
264:
218:
190:
142:error-correcting code
2245:
2132:
2073:
2051:Maximum a posteriori
1889:
1789:finite state machine
1740:
1691:
1599:
1534:
1455:
1402:
1280:
1212:
1139:
1060:
1017:
870:
410:decoding algorithm.
361:
319:
277:
247:
199:
161:
69:"Convolutional code"
54:improve this article
2868:Matlab explanations
2260:{\displaystyle K=7}
2027:sequential decoding
1028:{\displaystyle {*}}
926:
887:
378:{\displaystyle 7/8}
262:{\displaystyle K-1}
216:{\displaystyle n/k}
2888:2017-08-30 at the
2574:
2542:, for example, in
2325:Puncturing matrix
2294:
2257:
2205:
2189:
2177:
2118:
2022:instruction sets.
2012:maximum likelihood
1996:
1927:
1860:
1832:
1791:. An encoder with
1759:
1722:
1683:polynomial degrees
1663:
1582:
1514:
1473:
1431:
1387:
1260:
1197:
1124:
1025:
980:
912:
873:
843:
832:
813:
781:
585:
450:
375:
347:
290:
259:
213:
185:
146:boolean polynomial
138:convolutional code
2857:David J.C. MacKay
2582:Shannon's theorem
2532:
2531:
2525:
2524:
2465:
2464:
2417:
2416:
2381:
2380:
2351:
2350:
2314:puncturing matrix
2008:Viterbi algorithm
1974:Viterbi algorithm
1954:concatenated code
1918:
1870:) is the minimal
1734:constraint length
1529:rational function
1464:
1381:
1044:transfer function
861:impulse responses
524:1+1 = 0
520:1+0 = 1
516:0+1 = 1
512:0+0 = 0
404:Viterbi algorithm
313:symbol puncturing
134:telecommunication
130:
129:
122:
104:
16:(Redirected from
2948:
2840:
2833:
2827:
2822:
2816:
2815:
2808:
2802:
2797:
2791:
2786:
2780:
2773:
2767:
2762:
2756:
2751:
2745:
2740:
2734:
2729:
2723:
2716:
2710:
2707:
2701:
2694:
2688:
2685:
2679:
2676:
2670:
2667:
2661:
2654:
2644:
2643:
2638:. Archived from
2622:
2621:
2477:
2429:
2393:
2363:
2339:
2319:
2266:
2264:
2263:
2258:
2240:
2237:to Saturn use a
2219:of 7 and a rate
2218:
2186:
2184:
2183:
2178:
2176:
2175:
2157:
2156:
2144:
2143:
2127:
2125:
2124:
2119:
2117:
2116:
2098:
2097:
2085:
2084:
1936:
1934:
1933:
1928:
1923:
1919:
1914:
1903:
1872:Hamming distance
1768:
1766:
1765:
1760:
1731:
1729:
1728:
1723:
1714:
1703:
1702:
1680:
1672:
1670:
1669:
1664:
1591:
1589:
1588:
1583:
1568:
1523:
1521:
1520:
1515:
1503:
1492:
1491:
1472:
1447:
1440:
1438:
1437:
1432:
1414:
1413:
1396:
1394:
1393:
1388:
1382:
1380:
1379:
1378:
1363:
1362:
1343:
1342:
1341:
1326:
1325:
1306:
1292:
1291:
1269:
1267:
1266:
1261:
1255:
1254:
1224:
1223:
1206:
1204:
1203:
1198:
1192:
1191:
1176:
1175:
1151:
1150:
1133:
1131:
1130:
1125:
1119:
1118:
1103:
1102:
1072:
1071:
1034:
1032:
1031:
1026:
1024:
1012:
1008:
1004:
1000:
996:
989:
987:
986:
981:
964:
963:
942:
941:
925:
920:
910:
905:
886:
881:
755:
743:
643:
633:
624:
610:
609:
603:
596:
595:
591:
525:
521:
517:
513:
493:memory registers
384:
382:
381:
376:
371:
356:
354:
353:
348:
343:
329:
299:
297:
296:
291:
289:
288:
272:
268:
266:
265:
260:
242:
238:
234:
230:
226:
222:
220:
219:
214:
209:
194:
192:
191:
188:{\displaystyle }
186:
125:
118:
114:
111:
105:
103:
62:
38:
30:
21:
18:Convolution code
2956:
2955:
2951:
2950:
2949:
2947:
2946:
2945:
2931:
2930:
2929:
2904:
2899:
2897:Further reading
2890:Wayback Machine
2849:
2844:
2843:
2834:
2830:
2823:
2819:
2810:
2809:
2805:
2798:
2794:
2787:
2783:
2774:
2770:
2763:
2759:
2752:
2748:
2741:
2737:
2730:
2726:
2718:Moon, Todd K. "
2717:
2713:
2708:
2704:
2695:
2691:
2686:
2682:
2677:
2673:
2668:
2664:
2655:
2651:
2628:
2619:
2617:
2614:
2602:
2565:
2559:
2334:
2286:
2280:
2243:
2242:
2238:
2227:Mars Pathfinder
2216:
2213:Voyager program
2167:
2148:
2135:
2130:
2129:
2108:
2089:
2076:
2071:
2070:
2063:
2036:Pioneer program
1976:
1970:
1904:
1898:
1887:
1886:
1851:
1818:
1811:
1804:
1785:
1779:Trellis (graph)
1775:
1773:Trellis diagram
1738:
1737:
1694:
1689:
1688:
1678:
1597:
1596:
1532:
1531:
1527:where, for any
1483:
1453:
1452:
1445:
1405:
1400:
1399:
1367:
1351:
1344:
1330:
1314:
1307:
1283:
1278:
1277:
1243:
1215:
1210:
1209:
1180:
1164:
1142:
1137:
1136:
1107:
1091:
1063:
1058:
1057:
1015:
1014:
1010:
1006:
1002:
998:
994:
955:
927:
868:
867:
851:
791:non-systematic.
766:
759:
756:
747:
744:
718:
711:
704:
696:
689:
682:
674:
667:
660:
653:
641:
635:
631:
625:
622:
616:
605:
599:
598:
593:
589:
588:
575:
568:
561:
554:
539:
523:
519:
515:
511:
486:
438:
392:
359:
358:
317:
316:
280:
275:
274:
270:
245:
244:
240:
236:
232:
228:
224:
197:
196:
159:
158:
126:
115:
109:
106:
63:
61:
51:
39:
28:
23:
22:
15:
12:
11:
5:
2954:
2952:
2944:
2943:
2933:
2932:
2928:
2927:
2923:
2920:
2916:
2912:
2909:
2905:
2903:
2900:
2898:
2895:
2894:
2893:
2880:
2875:
2870:
2865:
2860:
2848:
2847:External links
2845:
2842:
2841:
2828:
2817:
2803:
2792:
2781:
2768:
2757:
2746:
2735:
2724:
2711:
2702:
2689:
2680:
2671:
2662:
2648:
2647:
2646:
2645:
2642:on 2022-01-22.
2613:
2610:
2609:
2608:
2601:
2598:
2561:Main article:
2558:
2555:
2530:
2529:
2526:
2523:
2522:
2519:
2516:
2513:
2510:
2507:
2504:
2500:
2499:
2496:
2493:
2490:
2487:
2484:
2481:
2474:
2470:
2469:
2466:
2463:
2462:
2459:
2456:
2453:
2450:
2446:
2445:
2442:
2439:
2436:
2433:
2426:
2422:
2421:
2418:
2415:
2414:
2411:
2408:
2404:
2403:
2400:
2397:
2390:
2386:
2385:
2382:
2379:
2378:
2375:
2371:
2370:
2367:
2360:
2356:
2355:
2352:
2349:
2348:
2344:
2343:
2336:
2330:
2329:
2326:
2323:
2284:Punctured code
2279:
2276:
2256:
2253:
2250:
2174:
2170:
2166:
2163:
2160:
2155:
2151:
2147:
2142:
2138:
2115:
2111:
2107:
2104:
2101:
2096:
2092:
2088:
2083:
2079:
2062:
2059:
2055:BCJR algorithm
1988:16-QAM, 64-QAM
1969:
1966:
1938:
1937:
1926:
1922:
1917:
1913:
1910:
1907:
1901:
1897:
1894:
1850:
1847:
1816:
1809:
1802:
1774:
1771:
1757:
1754:
1751:
1748:
1745:
1736:is defined as
1720:
1717:
1713:
1709:
1706:
1701:
1697:
1675:
1674:
1661:
1658:
1655:
1652:
1649:
1646:
1643:
1640:
1637:
1634:
1631:
1628:
1625:
1622:
1619:
1616:
1613:
1610:
1607:
1604:
1580:
1577:
1574:
1571:
1567:
1563:
1560:
1557:
1554:
1551:
1548:
1545:
1542:
1539:
1525:
1524:
1512:
1509:
1506:
1502:
1498:
1495:
1490:
1486:
1482:
1479:
1476:
1471:
1467:
1463:
1460:
1442:
1441:
1429:
1426:
1423:
1420:
1417:
1412:
1408:
1397:
1385:
1377:
1374:
1370:
1366:
1361:
1358:
1354:
1350:
1347:
1340:
1337:
1333:
1329:
1324:
1321:
1317:
1313:
1310:
1304:
1301:
1298:
1295:
1290:
1286:
1271:
1270:
1258:
1253:
1250:
1246:
1242:
1239:
1236:
1233:
1230:
1227:
1222:
1218:
1207:
1195:
1190:
1187:
1183:
1179:
1174:
1171:
1167:
1163:
1160:
1157:
1154:
1149:
1145:
1134:
1122:
1117:
1114:
1110:
1106:
1101:
1098:
1094:
1090:
1087:
1084:
1081:
1078:
1075:
1070:
1066:
1023:
991:
990:
979:
976:
973:
970:
967:
962:
958:
954:
951:
948:
945:
940:
937:
934:
930:
924:
919:
915:
909:
904:
901:
898:
894:
890:
885:
880:
876:
850:
847:
765:
762:
761:
760:
757:
750:
748:
745:
738:
732:
731:
728:
721:
720:
716:
709:
702:
697:
694:
687:
680:
675:
672:
665:
658:
651:
639:
629:
620:
573:
566:
559:
552:
537:
485:
482:
437:
434:
432:(IIR) filter.
400:Andrew Viterbi
391:
388:
374:
370:
366:
346:
342:
338:
335:
332:
328:
324:
287:
283:
258:
255:
252:
212:
208:
204:
184:
181:
178:
175:
172:
169:
166:
128:
127:
42:
40:
33:
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
2953:
2942:
2939:
2938:
2936:
2924:
2921:
2917:
2913:
2910:
2907:
2906:
2901:
2896:
2891:
2887:
2884:
2881:
2879:
2876:
2874:
2871:
2869:
2866:
2864:
2861:
2858:
2854:
2851:
2850:
2846:
2838:
2832:
2829:
2826:
2821:
2818:
2813:
2807:
2804:
2801:
2796:
2793:
2790:
2785:
2782:
2778:
2772:
2769:
2766:
2761:
2758:
2755:
2750:
2747:
2744:
2739:
2736:
2733:
2728:
2725:
2721:
2715:
2712:
2706:
2703:
2699:
2693:
2690:
2684:
2681:
2675:
2672:
2666:
2663:
2659:
2653:
2650:
2641:
2637:
2633:
2632:
2626:
2616:
2615:
2611:
2607:
2604:
2603:
2599:
2597:
2595:
2591:
2587:
2586:Concatenation
2583:
2579:
2569:
2564:
2556:
2554:
2551:
2549:
2545:
2541:
2536:
2527:
2520:
2517:
2514:
2511:
2508:
2505:
2502:
2501:
2497:
2494:
2491:
2488:
2485:
2482:
2479:
2478:
2475:
2472:
2471:
2467:
2460:
2457:
2454:
2451:
2448:
2447:
2443:
2440:
2437:
2434:
2431:
2430:
2427:
2424:
2423:
2419:
2412:
2409:
2406:
2405:
2401:
2398:
2395:
2394:
2391:
2388:
2387:
2383:
2376:
2373:
2372:
2368:
2365:
2364:
2361:
2358:
2357:
2353:
2346:
2345:
2341:
2340:
2337:
2332:
2331:
2324:
2321:
2320:
2317:
2315:
2311:
2307:
2303:
2299:
2290:
2285:
2277:
2275:
2273:
2268:
2254:
2251:
2248:
2236:
2235:Cassini probe
2232:
2228:
2224:
2222:
2214:
2209:
2202:
2198:
2193:
2172:
2164:
2158:
2153:
2149:
2145:
2140:
2136:
2113:
2105:
2099:
2094:
2090:
2086:
2081:
2077:
2067:
2060:
2058:
2056:
2052:
2048:
2043:
2041:
2037:
2032:
2028:
2023:
2021:
2017:
2013:
2009:
2005:
2001:
1993:
1989:
1985:
1980:
1975:
1967:
1965:
1963:
1959:
1955:
1949:
1947:
1943:
1924:
1920:
1915:
1911:
1908:
1905:
1899:
1895:
1892:
1885:
1884:
1883:
1881:
1877:
1873:
1869:
1865:
1864:free distance
1855:
1848:
1846:
1844:
1840:
1835:
1828:
1824:
1821:
1815:
1808:
1801:
1796:
1794:
1790:
1784:
1780:
1772:
1770:
1755:
1752:
1749:
1746:
1743:
1735:
1715:
1711:
1707:
1699:
1695:
1686:
1684:
1653:
1647:
1644:
1641:
1635:
1629:
1626:
1617:
1611:
1605:
1602:
1595:
1594:
1593:
1575:
1569:
1565:
1558:
1552:
1549:
1543:
1537:
1530:
1504:
1500:
1496:
1488:
1484:
1477:
1474:
1469:
1461:
1458:
1451:
1450:
1449:
1427:
1424:
1418:
1410:
1406:
1398:
1383:
1375:
1372:
1368:
1364:
1359:
1356:
1352:
1348:
1345:
1338:
1335:
1331:
1327:
1322:
1319:
1315:
1311:
1308:
1302:
1296:
1288:
1284:
1276:
1275:
1274:
1256:
1251:
1248:
1244:
1240:
1237:
1234:
1228:
1220:
1216:
1208:
1193:
1188:
1185:
1181:
1177:
1172:
1169:
1165:
1161:
1155:
1147:
1143:
1135:
1120:
1115:
1112:
1108:
1104:
1099:
1096:
1092:
1088:
1085:
1082:
1076:
1068:
1064:
1056:
1055:
1054:
1051:
1049:
1045:
1041:
1036:
1021:
977:
971:
960:
956:
952:
949:
943:
938:
935:
932:
928:
922:
917:
913:
902:
899:
896:
892:
888:
883:
878:
874:
866:
865:
864:
862:
858:
857:
848:
846:
839:
835:
828:
824:
822:
818:
809:
805:
802:
799:
796:
793:
792:
788:
787:
777:
773:
771:
770:non-recursive
763:
754:
749:
742:
737:
735:
729:
726:
725:
724:
715:
708:
701:
698:
693:
686:
679:
676:
671:
664:
657:
650:
647:
646:
645:
638:
628:
619:
614:
608:
602:
581:
577:
572:
565:
558:
551:
547:
543:
536:
532:
529:
509:
506:
502:
498:
494:
491:
483:
481:
479:
478:Shannon limit
475:
471:
467:
466:concatenation
463:
459:
455:
454:digital video
447:
442:
435:
433:
431:
427:
422:
420:
416:
415:Claude Berrou
411:
409:
405:
401:
397:
389:
387:
372:
368:
364:
344:
340:
336:
333:
330:
326:
322:
314:
309:
307:
301:
285:
281:
256:
253:
250:
235:is less than
210:
206:
202:
179:
176:
173:
170:
167:
154:
152:
147:
143:
140:is a type of
139:
135:
124:
121:
113:
102:
99:
95:
92:
88:
85:
81:
78:
74:
71: –
70:
66:
65:Find sources:
59:
55:
49:
48:
43:This article
41:
37:
32:
31:
19:
2902:Publications
2831:
2820:
2806:
2795:
2784:
2771:
2760:
2749:
2738:
2727:
2714:
2705:
2692:
2683:
2674:
2665:
2652:
2640:the original
2630:
2594:error floors
2590:Reed–Solomon
2575:
2552:
2546:systems and
2537:
2533:
2313:
2309:
2305:
2301:
2295:
2269:
2225:
2220:
2210:
2206:
2044:
2024:
2003:
1997:
1962:Reed–Solomon
1950:
1945:
1941:
1939:
1879:
1875:
1867:
1863:
1861:
1842:
1838:
1836:
1833:
1822:
1813:
1806:
1799:
1797:
1792:
1786:
1733:
1687:
1676:
1526:
1443:
1272:
1052:
1037:
992:
860:
854:
852:
844:
833:
814:
803:
800:
797:
794:
790:
784:
782:
769:
767:
733:
722:
713:
706:
699:
691:
684:
677:
669:
662:
655:
648:
636:
626:
617:
612:
606:
600:
586:
570:
563:
556:
549:
541:
534:
527:
496:
489:
487:
470:Reed–Solomon
451:
446:Interleaving
423:
412:
393:
310:
302:
155:
137:
131:
116:
107:
97:
90:
83:
76:
64:
52:Please help
47:verification
44:
2578:turbo codes
2335:(No perf.)
1984:QPSK, 8-PSK
1048:Z-transform
856:convolution
815:Useful for
474:turbo codes
472:. Prior to
419:turbo codes
396:Peter Elias
306:block codes
2915:1646-1654.
2825:Turbo code
2612:References
2563:Turbo code
2322:Code rate
2298:Puncturing
2282:See also:
2197:complexity
2000:algorithms
1972:See also:
1958:interleave
1777:See also:
1732:, and the
823:(SCCC's).
786:systematic
623:= (1,1,1),
80:newspapers
1909:−
1648:
1630:
1606:
1478:
1373:−
1365:−
1357:−
1349:−
1336:−
1320:−
1249:−
1186:−
1170:−
1113:−
1097:−
1022:∗
953:∗
936:−
908:∞
893:∑
642:= (1,0,1)
632:= (0,1,1)
569:moves to
555:moves to
546:bit shift
499:modulo-2
456:, radio,
254:−
2935:Category
2919:573-592.
2886:Archived
2600:See also
2544:Intelsat
2233:and the
2223:of 1/2.
1998:Several
1921:⌋
1900:⌊
1858:weights.
1839:decoding
508:XOR gate
223:, where
110:May 2015
2165:1011011
2106:1111001
1843:correct
1685:of the
1603:polydeg
1475:polydeg
1444:Define
604:⁄
592:⁄
526:), and
505:Boolean
390:History
151:trellis
94:scholar
2006:, the
1990:) and
993:where
634:, and
501:adders
96:
89:
82:
75:
67:
2926:1987.
2855:, by
2627:from
1677:Then
101:JSTOR
87:books
2473:7/8
2425:5/6
2389:3/4
2359:2/3
2031:Fano
2020:SIMD
2016:VLSI
1862:The
1812:). (
1781:and
1013:and
817:LDPC
408:BCJR
136:, a
73:news
2354:10
2333:1/2
2272:GSM
2150:133
2091:171
1992:LLR
1645:deg
1627:deg
1621:max
1466:max
1448:by
300:).
132:In
56:by
2937::
2634:.
2550:.
2528:3
2521:0
2518:1
2515:0
2512:1
2509:1
2506:1
2503:1
2498:1
2495:0
2492:1
2489:0
2486:0
2483:0
2480:1
2468:4
2461:0
2458:1
2455:0
2452:1
2449:1
2444:1
2441:0
2438:1
2435:0
2432:1
2420:5
2413:0
2410:1
2407:1
2402:1
2399:0
2396:1
2384:6
2377:1
2374:1
2369:0
2366:1
2347:1
2342:1
2229:,
2128:,
2057:.
2049:.
1986:,
1810:−1
1592:,
1428:1.
1050:.
1005:,
863::
717:−1
712:+
705:=
695:−1
690:+
683:=
673:−1
668:+
661:+
654:=
574:−1
562:,
522:,
518:,
514:,
480:.
421:.
2814:.
2310:n
2306:n
2304:/
2302:m
2255:7
2252:=
2249:K
2239:K
2221:r
2217:K
2173:b
2169:]
2162:[
2159:=
2154:o
2146:=
2141:2
2137:h
2114:b
2110:]
2103:[
2100:=
2095:o
2087:=
2082:1
2078:h
2004:k
1946:t
1942:t
1925:.
1916:2
1912:1
1906:d
1896:=
1893:t
1880:t
1878:(
1868:d
1866:(
1817:1
1814:m
1807:m
1803:0
1800:m
1793:n
1756:1
1753:+
1750:m
1747:=
1744:K
1719:)
1716:z
1712:/
1708:1
1705:(
1700:i
1696:H
1679:m
1673:.
1660:)
1657:)
1654:Q
1651:(
1642:,
1639:)
1636:P
1633:(
1624:(
1618:=
1615:)
1612:f
1609:(
1579:)
1576:z
1573:(
1570:Q
1566:/
1562:)
1559:z
1556:(
1553:P
1550:=
1547:)
1544:z
1541:(
1538:f
1511:)
1508:)
1505:z
1501:/
1497:1
1494:(
1489:i
1485:H
1481:(
1470:i
1462:=
1459:m
1446:m
1425:=
1422:)
1419:z
1416:(
1411:2
1407:H
1384:,
1376:3
1369:z
1360:2
1353:z
1346:1
1339:3
1332:z
1328:+
1323:1
1316:z
1312:+
1309:1
1303:=
1300:)
1297:z
1294:(
1289:1
1285:H
1257:.
1252:2
1245:z
1241:+
1238:1
1235:=
1232:)
1229:z
1226:(
1221:3
1217:H
1194:,
1189:2
1182:z
1178:+
1173:1
1166:z
1162:=
1159:)
1156:z
1153:(
1148:2
1144:H
1121:,
1116:2
1109:z
1105:+
1100:1
1093:z
1089:+
1086:1
1083:=
1080:)
1077:z
1074:(
1069:1
1065:H
1011:j
1007:h
1003:j
999:y
995:x
978:,
975:]
972:i
969:[
966:)
961:j
957:h
950:x
947:(
944:=
939:k
933:i
929:x
923:j
918:k
914:h
903:0
900:=
897:k
889:=
884:j
879:i
875:y
719:.
714:m
710:1
707:m
703:3
700:n
692:m
688:0
685:m
681:2
678:n
670:m
666:0
663:m
659:1
656:m
652:1
649:n
640:3
637:G
630:2
627:G
621:1
618:G
613:k
607:n
601:m
597:(
594:3
590:1
571:m
567:0
564:m
560:0
557:m
553:1
550:m
542:n
538:1
535:m
528:n
497:n
490:k
373:8
369:/
365:7
345:2
341:/
337:1
334:=
331:k
327:/
323:n
286:v
282:2
271:v
257:1
251:K
241:K
237:k
233:n
229:k
225:n
211:k
207:/
203:n
183:]
180:K
177:,
174:k
171:,
168:n
165:[
123:)
117:(
112:)
108:(
98:·
91:·
84:·
77:·
50:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
