Turbo code

Turbo codes are a special kind of code used in information theory to make sure information gets through even when there is noise or interference. These codes were developed around 1990–91 and first shared with the world in 1993. They were very exciting because they were the first practical codes that could get very close to the Shannon limit, a theoretical maximum for how much information can be sent reliably over a noisy channel.

These powerful codes are used in many places where clear communication is important. You can find them in 3G and 4G mobile networks, like in UMTS and LTE, as well as in deep space satellite communications. They help make sure that data reaches its destination without errors, even when the connection is not perfect.

Turbo codes work by using a method similar to how a car’s engine can be boosted with extra air, which is called turbocharging. This idea came from the feedback loop used when decoding the codes. Even though the encoding process doesn’t actually use feedback, the name “turbo code” stuck. These codes are often compared to another type of code called low-density parity-check (LDPC) codes, which can perform just as well but were free of patents, making them very popular until turbo code patents expired.

History

The idea for turbo codes was first shared in 1991 by Claude Berrou, who is credited as the sole inventor. His work led to important patents, one of which ended in 2013. The first public paper about turbo codes came out in 1993, and it listed three authors, but Berrou was the main creator.

Turbo codes were a big surprise when they were introduced because they worked so well that some experts were unsure at first. After their success, many new types of similar codes were developed. These codes help make sure information travels safely even when there is noise or interference.

An example encoder

Turbo codes have many different ways to work, but this section explains a classic example. This encoder sends three parts of data: the original payload, and two sets of extra bits created from the payload using special math rules. These extra bits help make sure the data can be understood even if some of it gets mixed up during travel.

The encoder uses two identical parts called RSC coders, connected together in a special way. This setup helps organize the data bits so they are sent out in different orders, making it easier to correct mistakes when the data arrives.

The decoder

The decoder for turbo codes is built similarly to the encoder, using two decoders connected in series. DEC₁ works more slowly and handles one part of the encoded data, while DEC₂ handles the other part. Between them, an interleaver helps spread out errors.

The decoder uses algorithms to decide what the original data was, even when some information got mixed up during transmission. One algorithm used in DEC₁ can't handle all the information, so another helps improve the results.

Soft decision approach

The decoder front-end gives a number for each bit in the data stream. This number shows how likely it is that the bit is a 0 or a 1 and is called a soft bit. The number can be between -127 and 127. For example, -127 means “certainly 0”, -100 means “very likely 0”, 0 means “it could be either 0 or 1”, 100 means “very likely 1”, and 127 means “certainly 1”. This way, more information about each bit is shared than just saying it is a 0 or a 1.

For each bit, a regular wireless receiver decides if a voltage is above or below a certain level. But for a turbo code decoder, the front end gives a number showing how far the voltage is from that level. To decode the data, the decoder creates a list of these numbers for each bit. There are two decoders working together, each handling part of the data.

Solving hypotheses to find bits

Turbo codes solve a puzzle by using two special tools called decoders. Each decoder makes a guess about a set of bits, and they share their guesses and how sure they are about each bit. By comparing and sharing these guesses, the decoders keep improving their guesses until they both agree on the correct answer.

This process is like solving a tricky puzzle, such as a crossword or sudoku. Imagine two friends solving different parts of the puzzle, sharing their ideas and confidence levels, and working together until they finish the puzzle together.

Performance

Turbo codes work well because they look random on the communication channel, which helps in correcting errors. However, they can have a problem called an error floor, where errors become harder to fix at very low error rates.

Practical applications using turbo codes

Turbo codes are used in many types of wireless communication. They help make sure information gets through even when there is noise or interference. For example, they are used in 3G and 4G mobile phone networks like HSPA, EV-DO, and LTE. They are also used in systems like MediaFLO for mobile TV and in satellite communications such as DVB-RCS and DVB-RCS2. Space missions, including recent ones by NASA like the Mars Reconnaissance Orbiter, use turbo codes to protect data. Even wireless networks like IEEE 802.16 (WiMAX) use turbo codes to keep information safe during transmission.

Bayesian formulation

From an artificial intelligence viewpoint, turbo codes can be thought of as a special kind of message-passing process in Bayesian networks. This connects them to a method called loopy belief propagation, which helps in understanding how these codes work to correct errors in data transmission.