Turbo code
From Wikipedia, the free encyclopedia
In computer science, turbo codes are a class of recently-developed high-performance error correction codes finding use in deep space satellite communications and other applications where designers seek to achieve maximal information transfer over a limited-bandwidth communication link in the presence of data-corrupting noise.
Contents |
[edit] Advantages
Of all practical error correction methods known to date, turbo codes, together with Low-density parity-check codes, come closest to approaching the Shannon limit, the theoretical limit of maximum information transfer rate over a noisy channel.
Turbo codes make it possible to increase data rate without increasing the power of a transmission, or they can be used to decrease the amount of power used to transmit at a certain data rate. Its main drawbacks are the relative high decoding complexity and a relatively high latency, which makes it unsuitable for some applications. For satellite use, this is not of great concern, since the transmission distance itself introduces latency due to the limited speed of light.
Prior to Turbo codes, the best known technique combined Reed-Solomon error correction block codes with Viterbi-decoded short constraint length convolutional codes, also known as RSV codes.
[edit] Who devised Turbo Codes?
The method was introduced by Berrou, Glavieux, and Thitimajshima (from ENST Bretagne, France) in their 1993 paper: "Near Shannon Limit error-correcting coding and decoding: Turbo-codes" published in the Proceedings of IEEE International Communications Conference [1]. Turbo code refinements and implementation are an area of active research at a number of universities.
[edit] The encoder
The encoder 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 RSC convolutional code. The third sub-block is n/2 parity bits for a known permutation of the payload data, again computed using a RSC convolutional code. That is, two redundant but different sub-blocks of parity bits for the sent payload. The complete block has m+n bits of data with a code rate of m/(m+n).
[edit] The decoder
The decoder front-end produces an integer for each bit in the data stream. This integer is a measure of how likely it is that the bit is a 0 or 1 and is also called soft bit. The integer could be drawn from the range [-127, 127], where:
- -127 means "certainly 0"
- -100 means "very likely 0"
- 0 means "it could be either 0 or 1"
- 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 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 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.
[edit] Solving hypotheses to find bits
The key innovation of turbo codes is how they use the likelihood data to reconcile differences between the two decoders. Each of the two convolutional decoders generates a hypothesis (with derived likelihoods) for the pattern of m bits in the payload sub-block. The hypothesis bit-patterns are compared, and if they differ, the decoders exchange the derived likelihoods they have for each bit in the hypotheses. Each decoder incorporates the derived likelihood estimates from the other decoder to generate a new hypothesis for the bits in the payload. Then they compare these new hypotheses. This iterative process continues until the two decoders come up with the same hypothesis for the m-bit pattern nn of the payload, typically in 15 to 18 cycles.
An analogy can be drawn between this process and that of solving cross-reference puzzles like crossword or sudoku. Consider a partially-completed, possibly garbled crossword puzzle. Two puzzle solvers (decoders) are trying to solve it: one possessing only the "down" clues (parity bits), and the other possessing only the "across" clues. To start, both solvers guess the answers (hypotheses) to their own clues, noting down how confident they are in each letter (payload bit). Then, they compare notes, by exchanging answers and confidence ratings with each other, noticing where and how they differ. Based on this new knowledge, they both come up with updated answers and confidence ratings, repeating the whole process until they converge to the same solution.
[edit] Practical applications using Turbo Codes
Telecommunications:
- Turbo codes are used extensively in 3G mobile telephony standards.
- Future DVB-S (Satellite television) standards will use Turbo Codes to replace the Reed-Solomon (RS) codes now used.
- MediaFLO, terrestrial mobile television system from Qualcomm
- New NASA missions such as Mars Reconnaissance Orbiter now use Turbo Codes, as an alternative to RS-Viterbi codes.
- Turbo coding such as Block Turbo Coding and Convolutional Turbo Coding are used in IEEE 802.16, a wireless metropolitan network standard.
[edit] Bayesian formulation
From an artificial intelligence viewpoint, turbo codes can be considered as an instance of loopy belief propagation in Bayesian networks.
[edit] External links
- "The UMTS Turbo Code and an Efficient Decoder Implementation Suitable for Software-Defined Radios" (International Journal of Wireless Information Networks)
- Dana Mackenzie (2005). "Take it to the limit". New Scientist 187 (2507): 38–41. ISSN 0262-4079. (preview, copy)
- "Pushing the Limit", a Science News feature about the development and genesis of turbo codes
- Coded Modulation Library, an open source library for simulating turbo codes in matlab
- "Turbo Equalization: Principles and New Results", an IEEE Transactions on Communications article about using turbo codes jointly with channel equalization.
