Misplaced Pages

#416583

34-403: Based on the trellis : Berrou, Glavieux and Thitimajshima simplification. This algorithms or data structures -related article is a stub . You can help Misplaced Pages by expanding it . Convolutional code In telecommunication , a convolutional code is a type of error-correcting code that generates parity symbols via the sliding application of a boolean polynomial function to

68-507: A Finite impulse response (FIR) filter, while a recursive convolutional code might be considered an Infinite impulse response (IIR) filter. Convolutional codes are used extensively to achieve reliable data transfer in numerous applications, such as digital video , radio, mobile communications (e.g., in GSM, GPRS, EDGE and 3G networks (until 3GPP Release 7) ) and satellite communications . These codes are often implemented in concatenation with

102-478: A concatenated code with an inner convolutional code. The popular solution for this problem is to interleave data before convolutional encoding, so that the outer block (usually Reed–Solomon ) code can correct most of the errors. Several algorithms exist for decoding convolutional codes. For relatively small values of k , the Viterbi algorithm is universally used as it provides maximum likelihood performance and

136-480: A 'mother' code rate n / k = 1 / 2 {\displaystyle n/k=1/2} may be punctured to a higher rate of, for example, 7 / 8 {\displaystyle 7/8} 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

170-469: A constraint length of 2 and a rate of 1/2 is used in GSM as an error correction technique. 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. Puncturing is a technique used to make a m / n rate code from a "basic" low-rate (e.g., 1/ n ) code. It is achieved by deleting of some bits in

204-409: A continuous bitstream, the value of t applies to a quantity of errors located relatively near to each other. That is, multiple groups of t errors can usually be fixed when they are relatively far apart. 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

238-474: 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 trellis decoding using a time-invariant trellis. Time invariant trellis decoding allows convolutional codes to be maximum-likelihood soft-decision decoded with reasonable complexity. The ability to perform economical maximum likelihood soft decision decoding

272-456: A hard-decision code, particularly Reed–Solomon . Prior to turbo codes such constructions were the most efficient, coming closest to the Shannon limit . To convolutionally encode data, start with k memory registers , each holding one input bit. Unless otherwise specified, all memory registers start with a value of 0. The encoder has n modulo-2 adders (a modulo 2 adder can be implemented with

306-448: A single Boolean XOR gate , where the logic is: 0+0 = 0 , 0+1 = 1 , 1+0 = 1 , 1+1 = 0 ), and n generator polynomials — one for each adder (see figure below). An input bit m 1 is fed into the leftmost register. Using the generator polynomials and the existing values in the remaining registers, the encoder outputs n symbols. These symbols may be transmitted or punctured depending on

340-912: A strict requirement, but a common practice. 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. 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. Other RSC codes and example applications include: Useful for LDPC code implementation and as inner constituent code for serial concatenated convolutional codes (SCCC's). Useful for SCCC's and multidimensional turbo codes. Useful as constituent code in low error rate turbo codes for applications such as satellite links. Also suitable as SCCC outer code. A convolutional encoder

374-410: Is a finite state machine . An encoder with n binary cells will have 2 states. Imagine that the encoder (shown on Img.1, above) has '1' in the left memory cell ( m 0 ), and '0' in the right one ( m −1 ). ( m 1 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

SECTION 10

#1732858217417

408-462: Is called so because it performs a convolution of the input stream with the encoder's impulse responses : where x is an input sequence, y is a sequence from output j , h is an impulse response for output j and ∗ {\displaystyle {*}} denotes convolution. A convolutional encoder is a discrete linear time-invariant system . Every output of an encoder can be described by its own transfer function , which

442-449: Is closely related to the generator polynomial. An impulse response is connected with a transfer function through Z-transform . Transfer functions for the first (non-recursive) encoder are: Transfer functions for the second (recursive) encoder are: Define m by where, for any rational function f ( z ) = P ( z ) / Q ( z ) {\displaystyle f(z)=P(z)/Q(z)\,} , Then m

476-470: Is defined by the respective communication standard. Punctured convolutional codes are widely used in the satellite communications , for example, in Intelsat systems and Digital Video Broadcasting . Punctured convolutional codes are also called "perforated". Simple Viterbi-decoded convolutional codes are now giving way to turbo codes , a new class of iterated short convolutional codes that closely approach

510-546: Is highly parallelizable. Viterbi decoders are thus easy to implement in VLSI hardware and in software on CPUs with SIMD instruction sets. Longer constraint length codes are more practically decoded with any of several sequential decoding algorithms, of which the Fano algorithm is the best known. Unlike Viterbi decoding, sequential decoding is not maximum likelihood but its complexity increases only slightly with constraint length, allowing

544-415: 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 codes are often characterized by the base code rate and the depth (or memory) of the encoder [ n , k , K ] {\displaystyle [n,k,K]} . The base code rate

578-407: Is performed on blocks of data. Convolutionally encoded block codes typically employ termination. The arbitrary block length of convolutional codes can also be contrasted to classic block codes , which generally have fixed block lengths that are determined by algebraic properties. The code rate of a convolutional code is commonly modified via symbol puncturing . For example, a convolutional code with

612-405: Is the maximum of the polynomial degrees of the H i ( 1 / z ) {\displaystyle H_{i}(1/z)\,} , and the constraint length is defined as K = m + 1 {\displaystyle K=m+1\,} . For instance, in the first example the constraint length is 3, and in the second the constraint length is 4. A convolutional encoder

646-500: Is typically given as n / k {\displaystyle n/k} , where n is the raw input data rate and k is the data rate of output channel encoded stream. n is less than k because channel coding inserts redundancy in the input bits. The memory is often called the "constraint length" K , where the output is a function of the current input as well as the previous K − 1 {\displaystyle K-1} inputs. The depth may also be given as

680-484: The Viterbi algorithm . Other trellis-based decoder algorithms were later developed, including the BCJR decoding algorithm. Recursive systematic convolutional codes were invented by Claude Berrou around 1991. These codes proved especially useful for iterative processing including the processing of concatenated codes such as turbo codes . Using the "convolutional" terminology, a classic convolutional code might be considered

714-522: The Voyager program , has a constraint length K of 7 and a rate r of 1/2. Mars Pathfinder , Mars Exploration Rover and the Cassini probe to Saturn use a K of 15 and a rate of 1/6; this code performs about 2 dB better than the simpler K = 7 {\displaystyle K=7} code at a cost of 256× in decoding complexity (compared to Voyager mission codes). The convolutional code with

SECTION 20

#1732858217417

748-445: The "01" state or the "11" state. One can see that not all transitions are possible for (e.g., a decoder can't convert from "10" state to "00" or even stay in "10" state). All possible transitions can be shown as below: An actual encoded sequence can be represented as a path on this graph. One valid path is shown in red as an example. This diagram gives us an idea about decoding : if a received sequence doesn't fit this graph, then it

782-608: The bits that form the most likely codeword. An approximate confidence measure can be added to each bit by use of the Soft output Viterbi algorithm . Maximum a posteriori (MAP) soft decisions for each bit can be obtained by use of the BCJR algorithm . 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). An especially popular Viterbi-decoded convolutional code, used at least since

816-474: The block length and code rate flexibility of convolutional codes, makes them very popular for digital communications. Convolutional codes were introduced in 1955 by Peter Elias . It was thought that convolutional codes could be decoded with arbitrary quality at the expense of computation and delay. In 1967, Andrew Viterbi determined that convolutional codes could be maximum-likelihood decoded with reasonable complexity using time invariant trellis based decoders —

850-734: The desired code rate. Now bit shift all register values to the right ( m 1 moves to m 0 , m 0 moves to m −1 ) 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). The figure below is a rate 1 ⁄ 3 ( m ⁄ n ) encoder with constraint length ( k ) of 3. Generator polynomials are G 1 = (1,1,1), G 2 = (0,1,1) , and G 3 = (1,0,1) . Therefore, output bits are calculated (modulo 2) as follows: Convolutional codes can be systematic and non-systematic: Non-systematic convolutional codes are more popular due to better noise immunity. It relates to

884-401: The encoder output. Bits are deleted according to a puncturing matrix . The following puncturing matrices are the most frequently used: 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

918-511: The free distance of the convolutional code. The encoder on the picture above is a non-recursive encoder. Here's an example of a recursive one and as such it admits a feedback structure: The example encoder is systematic 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 non-systematic. Recursive codes are typically systematic and, conversely, non-recursive codes are typically non-systematic. It isn't

952-399: The number of memory elements v in the polynomial or the maximum possible number of states of the encoder (typically: 2 v {\displaystyle 2^{v}} ). 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

986-461: The theoretical limits imposed by Shannon's theorem with much less decoding complexity than the Viterbi algorithm on the long convolutional codes that would be required for the same performance. Concatenation with an outer algebraic code (e.g., Reed–Solomon ) addresses the issue of error floors inherent to turbo code designs. Peter Elias Peter Elias (November 23, 1923 – December 7, 2001 )

1020-481: The use of strong, long-constraint-length codes. Such codes were used in the Pioneer program of the early 1970s to Jupiter and Saturn, but gave way to shorter, Viterbi-decoded codes, usually concatenated with large Reed–Solomon error correction codes that steepen the overall bit-error-rate curve and produce extremely low residual undetected error rates. Both Viterbi and sequential decoding algorithms return hard decisions:

1054-822: Was a member of the Massachusetts Institute of Technology faculty from 1953 to 1991. From 1957 until 1966, he served as one of three founding editors of Information and Control . Elias received the Claude E. Shannon Award of the IEEE Information Theory Society (1977); the Golden Jubilee Award for Technological Innovation of the IEEE Information Theory Society (1998); and the IEEE Richard W. Hamming Medal (2002). Peter Elias

BCJR algorithm - Misplaced Pages Continue

1088-475: Was a pioneer in the field of information theory . Born in New Brunswick, New Jersey , he was a member of the Massachusetts Institute of Technology faculty from 1953 to 1991. In 1955, Elias introduced convolutional codes as an alternative to block codes . He also established the binary erasure channel and proposed list decoding of error-correcting codes as an alternative to unique decoding . Peter Elias

1122-766: Was born on November 23, 1923, in New Brunswick, New Jersey . His mother Anna Elias (née Wahrhaftig) was born on April 19, 1897, in New York City . His father Nathaniel Mendel Elias, born on February 21, 1895, worked for Thomas Edison in his Edison, New Jersey , laboratory after graduating from Columbia University with a degree in chemical engineering . His paternal grandparents were Emil Elias and Pepi Pauline Cypres (daughter of Peretz Hacohen Cypres and Lea Breindel Cypres ) who married in 1889 in Kraków, Poland . Elias died (at age 78) on December 7, 2001, of Creutzfeldt–Jakob disease . This biography of an American academic

1156-453: Was received with errors, and we must choose the nearest correct (fitting the graph) sequence. The real decoding algorithms exploit this idea. The free distance ( d ) is the minimal Hamming distance between different encoded sequences. The correcting capability ( t ) of a convolutional code is the number of errors that can be corrected by the code. It can be calculated as Since a convolutional code doesn't use blocks, processing instead

#416583