Turbo Codes

Turbo codes

1. INTRODUCTION

TURBO CODES constitute major development in the field of Forward Error Correction (FEC). In electrical engineering and digital communications turbo codes are a class of high performance error correction code developed in 1993 which are finding use in deep satellite communication and other applications where designers seek to achieve maximal information transfer over a limited bandwidth communication link in the presence of data corrupting noise. Exhibiting performance approaching the Shannon limit, Turbo Codes (TC) have the TC block set features efficient encoder and decoder designs seen rapid adoption in the design of digital communication systems. Desirable and Designable introduces the basics of turbo codes in their different flavors (more specifically, parallel concatenated convolutional turbo codes and block turbo codes). Through the application of systemic design methodology that considers data transfer and storage as top priority candidates for optimization, the authors show how turbo codes can be implemented and the attractive performance results that can be achieved in throughput, latency . The last ten years have seen the appearance of a new type of correction code the turbo code. This represents a significant development in the field of errorcorrecting codes. The principle of decoding is to be found in an iterative exchange of information between elementary decoders, called extrinsic information, and it is this principle from which the term turbo originates. The turbo concept is now applied to block codes as well as other parts of a digital transmission system, such as detection, demodulation. Applications that integrate turbo codes into their standards are mobile communications, wireless networks

and local radio loops. Future applications could

include cable transmission, short-distance communication or data storage includes cable transmission, short-distance communication or data storage.

Nehru College of Engineering And Research Centre

1

Turbo codes 2.

THE “TURBO PRINCIPLE”

Allows a single very complex operation (decoding a turbo code) to be split into two much simpler operations (decoding component codes). Use “soft information” from output of one operation to assist with the other operation.

3. ERROR DETECTION AND CORRECTION •Errors can be categorized as follows: a). Single bit: one bit error per data unit. b). Burst: two or more bit bit errors per data unit. •Redundancy is the concept of sending extra bits for use in error detection. •For common methods of error detection are the following: a). Vertical redundancy check(VRC) b). Longitudinal redundancy check (LRC) c). Cyclic redundancy check (CRC) d). Checksum •In VRC an extra bit is added to the data unit. •VRC can detect only an odd number of errors: it cannot detect an odd number of errors. •In LRC, a redundant data unit is follows n data units. •CRC, the most powerfull of the redundancy checking techniques, is based on binary division. •Checksum is used by the higher layer protocols ( TCP/IP) for error detection. a). To divides the data into sections . b). Add the sections together using one's complement arithmetic. c). Take the complement of the final sum; this is the checksum. •The hamming code is a single bit error correction method using redundant bits.

Nehru College of Engineering And Research Centre

2

Turbo codes

4. TYPES OF ERRORS

Wherever an electromagnetic signal flow one point to another ,it is subject to unpredictable inference from heat,magnetism and other forms of electricity.This inference can change the shape or timing of the signal.There are two types of errors :single bit error and burst error.In single bit error a ‘0’ is changed to ‘1’ or a ‘1’ is changed to ‘0’.In burst error ,multiple bits are changed. errors

Single bit

Burst

Fig(1) : Types of errors

4. A) SINGLE BIT ERROR The term single bit error means that only one bit of given data unit is changed from 1 to 0 or from 0 to 1. In single bit error only one bit in the data unit has changed. 0

0

0

0

1

0

1

0

0

1

0

↑ 0 changed to 1 ↑ 0

0

0

0

0

Fig (2): Single Bit Error

Nehru College of Engineering And Research Centre

3

Turbo codes Figure shows the effect of a single bit error as a data unit.For a single bit error to occur ,the noise must have a duration of ‘1’ microsecond.A single bit error can happen if we are sending data using parallel transmission. Example: If 8 wires are used to send all of the 8 bits of a byte at the sametime and one of the wires is noisy one bit can be corrupted in each time. BURST ERROR A burst error means that two or more bits in the data unit have changed.

0

0

0

1

↓ 0

0

1

0

1

0

1

1

1

0

↓ 1

1

Fig (3): Burst Error

Figure shows the effect of burst error on a data unit.In this case ‘00011010 ‘ was send but ‘00111110’ was received.The length of the burst is measured from the first corrupted bit to the last corrupted bit.Burst error is most likely to happen in a serial communication.the number of bits affected depends on the data rate and duration of noise.

5.

ERROR DETECTION Nehru College of Engineering And Research Centre

4

Turbo codes

Detection: We can de detect many errors during transmission Redundancy: One error detection mechanism allows to send every data unit twice. the receiving device would them be able to do a bit for bit comparison between the two versions of the data, instead of repeating the entire data stream ,a shorter groups of bits may be appended to the end of each unit. This technique is called redundancy. Error detection uses the concept of redudundancy, means adding extra bits to detecting errors at the destination.

Detection Methods A.VRC B.LRC C.CRC D.CHECKSUM

5. A) Vertical redundancy check: In a vertical redundancy check the parity bit is added to every data unit. So that the total number of 1’s becomes even. It is most common and least expensive mechanism. Performance: VRC cannot detect errors where the total number of bits changed is even. If any two bits change in transmission ,the changes cancel each other and the data unit will pass a parity check even though the data unit is damaged.The same holds true for any even number of errors.VRC can detect all single-bit errors.It can detect burst errors only if the total number of errors in each data unit is odd.

5. B) Longitudinal redundancy check:

Nehru College of Engineering And Research Centre

5

Turbo codes

A block of bits organized in a table. a block of bits divided into rows and a redundant row of bits is added to the whole block. These two are based on addition. Performance: LRC detecting burst errors .If two bits in one unit are damaged and two bits in exactly the same positions in another data unit are also damaged, the LRC checker will not detect an error.

5. C) Cyclic redundancy check: CRC is based on binary division. In CRC a no: of redundant bits, called CRC remainder is appended to the end of data units so that the redundancy data unit becomes exactly divisible by a second, predetermined binary number. As its destination the incoming data units is divided by the same number. If at this step there is no remainder, the data unit is accepted. The remainder indicates that the data units have been damaged in transmit and must be rejected. Performance CRC is very effective error detection method.CRC can detect all burst errors that affect an odd number of bits.

5. D) Checksum The error detection method used by the higher layer protocols is called checksum. In the sender the checksum generator subdivides the data units in to equal segments of n bits. These segments are added together using 1’s complement arithmetic. The total is then complemented and appended to the end of the original data units is redundancy bits, called the checksum failed.The extended data unit is transmitted across the network. So if the sum of the data segment T, The checksum will be –T.

6. ERROR CORRECTION Nehru College of Engineering And Research Centre

6

Turbo codes

This can be handled in two ways. In one when an error is discovered the receiver can have the sender retransmit the entire data units. In other, a receiver can use an error correcting code, which automatically corrects certain errors.It requires more redundancy bits than detection codes.

6. A) Single bit error correction: A bit has two states 0 and 1.an errors occurs when receiver reads a 1 bit 0 or a 0 bit as a 1.to correct the error the receiver simply reverse the value of the altered bit.

6. B) Hamming code: It can be applied to data units of any length and uses the relationships between data and redundancy. The number of redundancy bits required to make these corrections, in dramatically higher than that required for single bit correction.

7. BTC: BLOCK TURBO CODE Nehru College of Engineering And Research Centre

7

Turbo codes Block Turbo Code (BTC) is a type of turbo codes. . Block Turbo-codes (BTC) are promising forward error correction (FEC) codes providing close-to-optimal coding gain for rather high coding rate (R > 0.7) and less subject to an error floor than Convolution Turbo Codes (CTC).

8. CONVOLUTIONAL CODE In telecommunication, a convolutional code is a type of error-correcting code in which (a) each m-bit information symbol (each m-bit string) to be encoded is transformed into an n-bit symbol, where m/n is the code rate (n ≥ m) and (b) the transformation is a function of the last information symbols, where k is the constraint length of the code.

dk

Interleaver π

RSC1

RSC2





FIG(4) : Convolutional Code

The original Turbo code used a parallel concatenation of two relatively simple recursive systematic covolutional (RSC) codes with large interleaving. Although the component codes are weak, the output turbo code word is very powerful due to the “Interleaver gain” which produces a random-like overall codeword or floor than Convolution Turbo Codes (CTC).

9. TURBO DECODING

Nehru College of Engineering And Research Centre

8

Turbo codes •

Decoders are associated with each component encoder.

•

Decoders take turns estimating and exchanging distribution on information bits. Information about the decoded input bits is passed iteratively between the two

decoders.

Fig(5) : Turbo Decoding

Interleaver  The interleaver’s function is to permute low weight code words in one encoder into high weight code words for the other encoder.  Most input sequences are associated with parity sequences that are not selfterminating.

Nehru College of Engineering And Research Centre

9

Turbo codes Input sequences with self-terminating parity sequences form terminating code words. The original Turbo code used a parallel concatenation of two relatively simple recursive systematic convolutional (RSC) codes with large interleaving. Although the component codes are weak, the output turbo code word is very powerful due to the “Interleaver gain” which produces a random-like overall codeword.

Fig(6) : Concatenated encoder and decoder

The encoder is formed by the parallel concatenation of two convolutional codes separated by an interleaver or permuter. An iterative process through the two corresponding decoders is used to decode the data received from the channel. Each elementary decoder passes to the other soft (probabilistic) information about each bit of the sequence to decode. This soft information, called extrinsic information, is updated at each iteration.

Nehru College of Engineering And Research Centre

10

Turbo codes

10.THE MINIMUM DISTANCE OF TURBO-LIKE CODE We derive worst-case upper bounds on the minimum distance of parallel concatenated Turbo codes, serially concatenated Turbo codes, repeat-accumulate codes, repeat-convolute codes, and generalizations of these codes obtained by allowing non-linear and large-memory constituent codes. We show that parallelconcatenated Turbo codes and repeat-convolute codes with sub-linear memory are asymptotically bad. We also show that depth-two serially concatenated codes with constant-memory outer codes and sub-linear-memory inner codes are asymptotically bad. In contrast, we prove that depth-three serially concatenated codes obtained by concatenating a repetition code with two accumulator codes through random permutations can be asymptotically good.

11.TURBO CODES IN IEEE The goal is to describe the main ideas behind the new class of codes called turbo codes, whose performance in terms of bit error probability has been shown to be very close to the Shannon limit. A numerical example, using a simple concatenated coding scheme, provides a vehicle for illustrating how error performance can be improved when soft outputs from the decoders are used in an iterative decoding process.

Nehru College of Engineering And Research Centre

11

Turbo codes 12. ADVANTAGES

& DISADVANTAGES

ADVANTAGES Of all practical error correction methods known to date, turbo codes and lowdensity parity-check codes (LDPCs) 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. Their main drawbacks are the relatively high decoding complexity and relatively high latency, which make them unsuitable for some applications. For satellite use, this is not of great concern, since the transmission distance itself introduces latency due to the finite propagation speed. Prior to Turbo codes, because practical implementations of LDPCs had not been developed, the most widespread technique that approached the Shannon limit combined Reed-Solomon error correction block codes. DISADVANTAGES  Their main drawbacks are the relatively high decoding complexity and relatively high latency, which make them unsuitable for some applications. For satellite use, this is not of great concern, since the transmission distance itself introduces latency due to the finite propagation speed.

Nehru College of Engineering And Research Centre

12

Turbo codes 13. TURBO

CODES : PRINCIPLES AND APPLICATIONS

This is intended for use by advanced level students and professional engineers involved in coding and telecommunication research. The material is organized into a coherent framework, starting with basic concepts of block and Convolutional coding, and gradually increasing in a logical and progressive manner to more advanced material, including applications The application of turbo-codes in digital communication systems, mainly in three parts. The first part considers systems of combined turbo-code and modulation. It is shown that by optimizing the labeling method and/or modifying the puncturing pattern, improvements of more than 0. 5 dB in signal to noise ratio (SNR) are achieved at no extra cost of energy, complexity, or delay. Conventional turbocodes with binary signaling divide the bit energy equally among the transmitted turboencoder output bits. The second proposes a turbo-code scheme with unequal power allocation to the encoder output bits. 5 dB can be achieved over the conventional turbo-coding scheme. The third part of this tackles the question of ``the sensitivity of the turbo-code performance towards the choice of the interleaver'', which was brought up since the early studies of these codes. This is the first theoretical approach taken towards this subject. The variance of the bound is evaluated. It is proven that the ratio of the standard deviation over the mean of the bound is asymptotically constant (for large interleaver length, N), decreases with N, and increases with SNR. The distribution of the bound is also computationally developed. It is shown that as SNR increases, a very low percentage of the interleavers deviate quite significantly from the average bound but the majority of the random interleavers result performances very close to the average. The contributions of input words of different weights in the variance of performance bound are also evaluated. Results show that these contributions vary significantly with SNR and N. New turbo codes based on the (8, 4, 3, 8) UM Hamming code are developed and shown to possess better performance potential in some senses. The standard turbo decoding algorithms, however, do not appear to achieve this potential.

Nehru College of Engineering And Research Centre

13

Turbo codes 14. THE

MODEL

OSI is the model.It allows for communication across all types of computer systems.It consist of seven but related layers,each of which defines the process of moving information across a network.The OSI model is not a protocol ;it is a model for understanding and designing a network architecture that is interoperable.

15.LAYERED ARCHITECTURE The OSI model is built of seven ordered layers: a. Physical layer b. Data link layer c. Network layer d. Transport layer e. Session layer f. Presentation layer g. Application layer PHYSICAL LAYER: This is the lowest layer in a communication system and is responsible for the conversion of a stream of bits into signal that can be transmitted on the other side. The receiver at the other physical layer converts back the signals to streams. DATA LINK LAYER: The main task of this layer includes multiplexing of different data streams, correction of transmission errors .The data link layer is responsible for a reliable point to point connection between two devices or a point to multipoint connection between one sender and several receivers.

Nehru College of Engineering And Research Centre

14

Turbo codes NETWORK LAYER: This third layer is responsible for routing packets through a network or establishing a connection between two entities over many other systems.Important functions are addressing, routing, device location etc. TRANSPORT LAYER: This layer is used in the reference model to establish an end to end connection .Topics like flow and congestion control are relevant,especially if the transport protocols known from the Internet ,TCP and UDP are over the link. SESSION LAYER: The session layer is the network dialog controller. It establishes maintains the interaction between communicatng systems.It allows the communication between two processes to take place in half-duplex or full-duplex. PRESENTATION LAYER: This layer is responsible for translation, encryption and compression. Translation: The information should be changed to bit streams before being transmitted. Encryption: To carry information, a system must be able assure privacy. Encryption means that the sender transforms the original information to another form and sends the resulting message over the network. Compression: Data compression reduces the number of bits to be transmitted. APPLICATION LAYER: The application layer enables the user, to access the network, it provides user interface and support for mail such as electronic mail, file transfer, shared database management system etc. Nehru College of Engineering And Research Centre

15

Turbo codes

16.CONCLUSION

• Today, many modern systems use TURBO CODES. • We can use turbo codes for compression of binary sequences. Networks must be able to transfer data from one device

to another with complete

accuracy.Anytime data are transmitted from source to destination; they can become corrupted in passage. For reliable communication, errors must be deleted and corrected. Error detect ion and correction are implemented either at the data link layer or the transport layer of the OSI model.

Nehru College of Engineering And Research Centre

16

Turbo codes

17.REFERENCES Websites: 1) www.wikipedia.org 2) www.ieee.org 3) www.turbo-codes.com 4) www.lib-asc.ekm.org

Nehru College of Engineering And Research Centre

17