Turbo code
Turbo codes are a group of error-correcting block or convolutional codes which are used in digital signal processing for secure data transmission, for example on satellite transmission links. They were patented in 1992 by Claude Berrou , then employed by France Telecom . A publication followed in 1993 together with further work together with Alain Glavieux and Punya Thitimajshima .
The development of turbo codes was a major step forward in the field of channel coding , as they provide a method with which the real achievable channel utilization is close to the theoretically possible channel capacity (“Shannon limit”). This means that the spectral efficiency of these codes is almost at its maximum, i.e. comparable to that of the low-density parity check codes (LDPC).
General
A turbo coder consists of at least two coders connected in parallel or in series for the elementary coding. The elementary coders each represent a specific channel code. The first coder receives the useful data in unchanged form, and its output is passed on to the second coder as input via a so-called interleaver , which rearranges the data sequence according to certain rules. With only two encoders, the second encoder finally supplies the data sequence to be transmitted.
Correspondingly, several decoders are also operated in reverse order in parallel or in series on the receiver side. As a special feature, these decoders exchange statistical information with one another for error correction and carry out the decoding process iteratively, which results in a very powerful error correction for a comparatively low algorithmic effort. Although the number of decoders is the same as the number of coders, the number of iterations in the decoding process is generally greater than the number of decoders.
The information that is also exchanged between the individual decoders via the interleaver during decoding is also referred to as extrinsic information and is a probability statement as to whether a certain bit position of the code word corresponds to logic 0 or logic 1 . It is extrinsic that the decoder that generates this information does not use it itself, but “passes it on” to the other elementary decoder or decoders that are jointly involved in the concatenated code and the information for these decoders comes “from outside” .
This is linked to the fact that a turbo decoder, and thus also the individual elementary decoders in it, always work with so-called soft decision . In English this is also known as soft input soft output or SISO . This means processing the individual digits of a code word with certain probabilities.
This iterative “feedback” of information between the individual decoders is also used to derive the term “turbo”, which alludes to the functional principle of a turbocharger and its feedback mechanism to increase performance. Strictly speaking, only the decoding process is what makes a turbo code so special. The coding process, on the other hand, is only a parallel or serial code chain of block codes or convolutional codes by means of an interleaver.
Classification
In principle, any component codes can be used in the context of a turbo code. It is also not necessary to select uniform coders, but codes with different parameters can be combined in the parallel or serial code chain. When using block codes as component codes , one speaks of turbo product codes (TPC) , when using convolutional codes one speaks of turbo convolutional codes (TCC) .
Since relatively simple algorithms based on soft decision such as the BCJR algorithm or the soft output Viterbi algorithm (SOVA), an extension of the Viterbi algorithm , are available for decoding convolutional codes, turbo codes play a role especially the turbo convolutional codes (TCC) have a greater practical importance. In the case of the turbo product codes (TPC) based on block codes, a "soft decision" on the part of the decoder is associated with greater effort.
Turbo convolutional codes (TCC)
Turbo convolutional codes are systematic convolutional codes linked in parallel . The chaining takes place on the transmitter side by multiple coding between individual coders via a scrambling unit (interleaver). Through this process of code chaining , the various convolutional codes are decorrelated from one another , and the individual digits have little statistical dependency on one another. Scramblers based on pseudo randomness are also used. These are still part of research work.
In order to enable certain code rates, for example to achieve a certain data rate precisely, certain code positions of the component codes are punctured - usually periodically . Puncturing means that the affected area is not sent. This must consequently be taken into account as erasure on the recipient side.
The following example should clarify the punctuation: An encoder generates 12 bits at its output, which are to be transmitted. The puncturing z. B. 2 bits omitted. Since only 10 bits now have to be transmitted, the throughput increases by 12/10, i.e. by a factor of 1.2. The missing two bits appear to the decoder as an additional disturbance and worsen the BER (Bit Error Rate). Of course, you cannot puncture as many bits as you want because there is a limit at which the decoder can still reconstruct the information.
Turbo Product Codes (TPC)
Turbo Product Codes are chained in series. A simple line / column formation is usually used as the interleaver: The data bits are arranged in a matrix . If there are only two component codes, the first block code is formed over all rows of the matrix. The second block code then forms the code words across all columns of the matrix.
The first work on product codes goes back to Peter Elias in 1954. Product codes were further developed into turbo product codes in the 1990s. A variety of Turbo Product Codes are by patents of France Telecom protected.
Application examples
- In LTE , UMTS and DVB-RCS , in addition to convolutional codes, turbo convolutional codes are also used.
- The ESA - spacecraft SMART-1 and Rosetta use turbo codes in communication.
- In wireless radio networks (WLAN) for data transmission according to the IEEE 802.16 standard as part of WiMAX , Turbo Product Codes are used, among other things.
Individual evidence
- ↑ Patent US5446747 : Error-correction coding method with at least two systematic convolutional codings in parallel, corresponding iterative decoding method, decoding module and decoder. Applied on April 16, 1992 , published on August 25, 1995 , applicant: France Telecom, Telediffusion De France SA, inventor: Claude Berrou.
- ^ Claude Berrou, Alain Glavieux and Punya Thitimajshima: Near Shannon Limit error-correcting coding and decoding: Turbo-codes , Proceedings of IEEE International Communications Conference 1993
- ^ J. Li, E. Qi, Q. Liang: Pseudo-random Interleaver Design for Turbo Codes. Proceeding of the Communications and Computer Networks, CCN 2002, online
- ^ Peter Elias: Error-Free Coding . Technical Report 285. Ed .: Massachusetts Institute of Technology, Research Laboratory of Electronics. September 1954 ( Online [PDF; 912 kB ]).
literature
- Karl-Dirk Kammeyer , Volker Kühn: MATLAB in communications engineering . J.Schlembach Fachverlag, Weil der Stadt 2001, ISBN 3-935340-05-2 .
- Todd K. Moon: Error Correction Coding. Mathematical Methods and Algorithms . Wiley-Interscience, Hoboken NJ 2005, ISBN 0-471-64800-0 .
- Markus Hufschmid: Information and communication. Basics of information transfer . Vieweg and Teubner, Wiesbaden 2006, ISBN 3-8351-0122-6 ( textbook - information technology ).