Convolutional code
Convolutional codes (also convolutional code;. Engl Convolutional code) - a term of coding theory - are, as well as block codes used in communications technology for channel coding, since they provide a forward error correction. A higher protection against transmission or storage errors is achieved by additionally introduced redundancy. By the eponymous mathematical method of folding the information content of the Nutzdatenstellen is distributed over several locations of the code word.
Convolutional codes have nothing to do with the similar-sounding code folding.
Importance
Convolutional codes are used for example in mobile communications and satellite transmission for digital data transmission. But can be found in storage media such as hard drives application, where they serve to protect against read errors. A combination of convolutional coding and digital modulation is the Trellis Coded Modulation.
A convolutional encoder forms a rule, on the input side k bits of information ( data bits ) to an n -bit long code word from wherein k is less than n. Successive codewords are interdependent, ie a convolutional block code has, in contrast to an internal "memory". However, since data can be edited sequences in practice only a finite time, these sequences are limited to a certain number of codewords. Thereafter, the convolutional encoder is placed by terminating to a predefined condition, which is usually equal to the initial state. Therefore, conventional convolutional code can be described as a form of special, non-systematic block codes.
For convolutional codes, the information is carrying a specific payload bit over several places ( bits) spread of the code word. The distribution of the information content - you can this as a kind of " smearing " of individual bits of the code word imagine - is achieved by the mathematical function of the convolution. This creates dependencies between the code bits. If by mistake individual digits of the code word distorted, with the number of errors per code word must not exceed a certain upper limit, the convolutional decoder can determine by several points distributed information correct Nutzdatenfolge from adjacent to the fault locations of the code word.
A significant feature of convolutional codes is that there is no known systematic procedure for their construction. Convolutional codes are obtained primarily through computationally expensive simulations and a full search on very many different folding structures or by serendipity. The majority of this by sampled structures provides so-called catastrophic convolutional codes which are not correct certain transmission errors, but replaced by a theoretically infinitely long sequence of errors. Therefore, compared to the block code, very few exist in practice relevant and actionable convolutional codes. For this very powerful method in the form of the Viterbi algorithm are known for the decoding of convolutional codes by means of so-called soft-decision.
Description
A convolutional encoder can be described by a shift register in which the data bits are serially shifted and a combinatorial structure of logical XOR operations that make up the output-side code word. A distinction is made between two main structures:
Recursive convolutional own internal feedback points which can lead to infinitely long output sequences. Recursive convolution structures can be systematically obtained from the non-recursive convolution structures. This coder are referred to in the literature as the RSC encoder ( Recursive Systematic Convolutional encoder).
The division is similar motivated as the digital filters with finite impulse response ( FIR) with a non- recursive filter structure or the infinite impulse response ( IIR) filter with a recursive structure. However convolutional have nothing to do except gross similarities in the structure with digital filters in particular.
Parameter
From the structure of a convolutional encoder results in the constraint length or memory order Lc. It describes the number of cycles it takes for an input bit ( user bit ) to go through all the points of the shift register, and thus there is an influence of a particular user data bits on the output-side code word. At non-recursive convolutional encoders to correspond to the number of memory elements of the convolutional encoder.
A further parameter of a convolutional code, its code rate Rc. It gives the ratio of the integral number k of the input information bits to the integral number n of the code bits generated on the output side:
Rc is always less than or equal 1, where the number K of the input information bit also be greater than 1. In this case, multiple data bits are sent in parallel to the encoder per clock. The parallel also deliver maturing output side n code bits are converted by a multiplexer in a serial data stream with a correspondingly higher clock rate.
In certain convolutional codes single input-side user data bits directly certain output-side code bits can be allocated without a convolution coding. In this case one speaks of asymmetric convolution codes. This method can be used for example in the trellis coded modulation as an integral part. If, however, all user data bits each with its own shift register chains of order Lc memory allocated, it is called symmetric convolution codes.
Termination
In practical applications are only payload data with a finite length is important. This makes a so-called termination ( engl: Termination) of the sequence required. Is hereby referred to the return of the encoder in a defined final state. If there is no termination at the end of the payload data is performed, it will have significant impact on the correction capability for decoding. Is the decoder, the final state of a sequence that is not known, it can estimate the last bits of information very unsure of what results in an increased probability of error result. If the final state and the sequence length N, however, known and agreed upon between the encoder and decoder, the determination of the last places a payload data to the decoder side can be done safely.
In the case of non-recursive convolutional code, a sequence of logic 0 bits are typically attached to the end of payload data. This so-called tail guides the encoder in a defined final state, called the zero state, back, is known to the decoder. These additional termination points at the end, however, increases the payload data, and the code rate is reduced to the value:
In the case of the recursive convolutional code tail is dependent on the previous user data.
Graph
A convolutional encoder can be interpreted as a finite state machine using state transition diagram, as depicted in the illustration for two memory with four states. The number of states generally results in binary code of the number z of the state memory to 2z.
The disadvantage of the display form by means of the state transition diagram is the lack of temporal relationship. This lack of temporal relationship for the serial decoding can be obtained by a trellis diagram ( trellis short ) can be visualized. A trellis diagram is an illustration of a state transition diagram which is " rolled " over the time axis. As part of the trellis diagram is also the decoding processes of convolutional codes using the Viterbi algorithm can be represented graphically: The idea involves the individual transitions from one state to the next different probability values assigned, which in itself in the sequence over several states across most clearly a single path in the trellis is emerging, which has the smallest sum probability of error over all other paths. This path, the associated symbols will be regarded by the decoder as the most likely transmitted symbols, and the information bits associated output for further processing ( = MLSE Maximum Likelihood Sequence Estimation ).
For convolutional codes with high constraint length, however, the number of states in the trellis diagram grow exponentially and this representation together with the transition edge is quickly become confusing. Thus, the trellis diagram is used to represent the decoding process by the Viterbi algorithm in the exemplary convolutional codes with a low length effect.
Decoding
Typically comes for the decoding of convolutional codes, the Viterbi decoder is used. This method is based, as mentioned on the trellis representation of the code, and intended for a disturbed code sequence the most likely associated user data or code sequence. The Viterbi decoder can process not only binary but also continuous input sequences. One then speaks of hardware and soft-decision decoding. In general, let the soft-decision decoder for convolutional codes implemented more easily than is the case for block codes.
The classical Viterbi decoder outputs binary sequences - but for different applications, it is important not only to know the individual decoded bits, but also the reliability thereof. Generating the reliabilities can be achieved for example by means of a modified Viterbi decoder, the so-called soft output Viterbi algorithm ( SOVA ), or the MAP / BCJR algorithm.
For codes with very large memory systems the trellis very complex and a trellis decoding by the Viterbi decoder is thus very expensive. In this case, alternatively, sequential sub-optimal decoder can be used which work on the representation of the code tree.
Dotting
For convolutional codes can be selected by a so-called dotting the codeword targeting a particular code rate Rc. Puncturing at specific bit positions of the code word ( " dots " ) may be omitted, thereby increasing the code rate. The decoder needs to know this so-called puncturing and taken into account when decoding.
The reason for puncturing is to accurately interpret the code word length to a specific frame length for the subsequent data transmission or data storage. By omitting individual digits of the code word, however, there is also a reduction of the correction performance.
Extension
The extension are concatenated convolutional codes. Several different or same convolutional codes are serial or parallel concatenated. The concatenation of the individual code is a feature referred to as the interleaver and allows a uniform distribution of errors of the different codes and a way of decoupling results in sub-codes. Thus, a larger code gain can be achieved than the sum of convolutional codes on its own.
A special form of code concatenation, the turbo codes. A subset of the turbo code, the so-called convolutional turbo code (TCC ) are based on recursive systematic convolutional codes. Non-recursive convolutional codes do not have the same improvement in the gain code in the TCC.