IRJET-Error Detection and Correction using Turbo Codes

IRJET-Error Detection and Correction using Turbo Codes

• 1.
  International Research Journalof Engineering and Technology (IRJET) e-ISSN: 2395-0056 Volume: 05 Issue: 06 | June-2018 www.irjet.net p-ISSN: 2395-0072 © 2018, IRJET | Impact Factor value: 7.211 | ISO 9001:2008 Certified Journal | Page 2688 ERROR DETECTION AND CORRECTION USING TURBO CODES Shivleela Biradar1, Mrs. Smitha Sasi2 1Shivleela Biradar, M. Tech student, Dept. of telecommunication Engineering, Dayananda SagarCollegeofEngineering,Bangalore 2Smitha Sasi, Assistant Professor, Dept. of Telecommunication Engineering, Dayananda Sagar College of Engineering, Bangalore --------------------------------------------------------------------------***---------------------------------------------------------------------------- Abstract - The general idea to achieve error detection and correction is to add some extra bit to an original message, in which the receiver can use to check the flexibility of the message which has been delivered, and to recover the noisy data. Turbo code is one of the forward error correction method, which is able to achieve the channel capacity, with nearer Shannon limit, encoding and decoding of text and images are performed. Methods and the working have been explained in this paper. The error has also introduced and detection and correction of errors have been achieved. Key Words: Forward Error Correction, Recursive systematic convolutional encoder, Maximum log-map algorithm, Turbo Encoder, Turbo Decoder, Interleaver, deinterleaver. 1. INTRODUCTION A Turbo code is a new technique, which is introduced for the burst error and which isalso designedfor the forward error correction in the year 1993, turbo coding was introduced by Berrou. Turbo coding is one of the best error correction techniques, in channel coding. This has made a great effect. It performs better than all other coding schemes which can be able to achieve the nearShannonlimit up to 0.7dB [1]. Turbo codes are designed in such a way that an interleaver is used between the two encoders which are connected parallelly, as shown in figure 1. The presence of an interleaver will be used to generate very large codeword length with good performance, at low SNRs. And even which are possible to achieve the Shannon limit which is nearly equals to 0.7 dB. The turbo encoders are formed with the help of a two RSC encoders in which they are separated by an interleaver, of length N. The RSC encoders used are systematic as the input bit will also occur at the output which will generates N-information bits as the inputs are followed by the parity bits [3]. The use of Turbo codes helps to increase the efficiency of the data transmission in communication systems. Nowadays Turbo codes are used in several spacecraft, and also it is used in UMTS and LTE for high speed communication [2]. Good communication is possible at the power controlled system communication channels at close to Shannon’s limit. The aim of channel coding is to Convert the data to code, that means the information sent over a communication channel. Errors get detected and corrected even in the presence of noise. II. RELATED WORK The turbo codes first introduced in a paper by Berrou, Glavieux and Thitimajshima [1, 2] presentedinIEEE conference on communication in which they have given the basic ideas about the turbo codes. It is further explained in [3, 4] by Berrou, Claude and Michael Peleg, Ran Ginnsar explained about new classesof convolutional codestheycan be called as turbo codes and the results are shown in terms of BER and also on Shannon limit. In [5, 8] Decoding is based on iterative process, for large interleaving size, it takes help from its previous value, in which it has done by the simulation. In [9, 11] Benedetto and Montorsi provides theoretical explanation for the performance of the codes. Later, Hagenauer was responsible for improving of the benefits of iterative decoding. In all papersthey havetriedto improve the performance of the turbo codes. In this paper, taken the necessary information and tried to achieve better performance for encoding and decoding and for encoder used two convolutional code in which they are able to correct more number of errors in one encoder and some in other. So, it takes less time to get corrected. For decoding, it verifieswithmanyalgorithmslike MAP, Log-MAP and Max-Log MAP, in which Max-Log-MAP gives better performance which is explained clearly in the decoding process, and also it gets similar result usingViterbi algorithm. But here, used Max-Log-MAP algorithm, for the decoding purpose. The decoder will also take a help of trellis implementation. The error location has been shown in this, so by that the errorsare easily recognized, and get corrected at the iterative decoding. After some fixed number of iterations it is possible to give the appropriate output. In which the output hasbeen shown with BER andSNRratio,as shown in the graph, at the result. It is able to achieve BER up to 10^-5 which means large number of errors get corrected, by achieving SNR within 1 dB. The same method can also apply for the audio and video error correction. III.STRUCTURE AND ALGORITHM FOR THE TURBO CODES BASED ENCODING AND DECODING 3.1 Encoding Process In the encoding process of the turbo codes, the two main components used in the turbo encoding are an interleaver and two recursive systematic convolutional (RSC) encoders as shown in the figure 1. By looking at the figure, the coding rate of the RSC is 1/2, the length will be K, the memory of the convolutional encoder will be equal to M=K-1, as the two RSC encoders are used which are able to achieve higher speed and also consumes less time. The
• 2.
  International Research Journalof Engineering and Technology (IRJET) e-ISSN: 2395-0056 Volume: 05 Issue: 06 | June-2018 www.irjet.net p-ISSN: 2395-0072 © 2018, IRJET | Impact Factor value: 7.211 | ISO 9001:2008 Certified Journal | Page 2689 generators of the two RSC encoders are G1 = [ , ,... ] and G2=[ , …, ] respectively, then the outputs of the kth input bit are: = (1) = mod 2 (2) = mod 2 (3) Fig. 1: Structure of Normal Turbo Encoder Turbo Codes are formedfromparallellyconnectedtwo codesin which the encodersare separated by an interleaver. Both the encoders used in this are similar. The two encoders used are the recursive systematic convolutional codes, in which the interleaver is fixed in the middle and will read the input bits in a pseudo-random order. The encoding process is performed at the rate r=1/2, the encoders are also called as component encoders. Here the work of the interleaver is used to minimize the burst error, which also helpful at the decoder, to decode the information correctly. At the output side, only one of the systematic output is considered from the two encoders, other output will be the alternate output value. 3.2 Decoding Process 3.2.1 Turbo Decoding MAP Algorithm The decoding process of the turbo codes is based on iterations, performed by the MAP algorithm. This is applied for each constituent code. MAP algorithm is implementedby the SISO decoder, which is used to check the reliabilityofthe received information. This will become complex in computing the multiplications and exponential operations, which are needed in the trellis diagram implementation.For reducing the complexity of the decoder, the two other SISO decoders are developed, in which the complexity of these algorithms will be less as compared to MAP algorithm and those two algorithms are Max Log-MAP and Log-MAP algorithm [4]. 3.2.2 LOG-MAP Algorithm The Log-MAP algorithm is introduced to reduce the complexity of the MAP algorithm, and also it is suitable for the hardware implementation, due to its simple computation. It is also suitable for the iterative decoding. The hardware implementation is less complex, as it uses log operation instead of multiplication. This is also a form of SISO decoding algorithm. Hard decisions are taken from the LLR [5]. The required equation is followed in which Γ is a branch metric is calculated from the previous soft output of the log-MAP decoder and the received signals, which is according to the equation (4), in which LC is called as channel reliability. (4) The equations are needed for decoding and are given below and they are back-ward state metrics B, the forward state metrics and the LLR. By calculating these values soft output is obtained. (5) (6) (7) Here the values used are y, s and s’ are the received sequence, of the present and previous state of the trellis. Once the final iteration process is done, hard decision of the decoder is formed from the de-interleaved sequence, which is gained from the second log-MAP decoder. Fig. 2: Turbo decoder circuit The decoding processis explained with the helpofa Log-MAP algorithm. The structure of turbodecoderisshown in figure 2. It consists of two decoders which work together. The operation depends on the soft decision information based on each decoder. After starting of an operation, Le is noted as soft decision of one decoder, and is called as extrinsic information. This is used to initialize the other decoder. The decoded information is moved aroundtheloop until the soft decisions meet the set of values. Here, the last extrinsic information is used from the first decoder to calculate the values of messages.
• 3.
  International Research Journalof Engineering and Technology (IRJET) e-ISSN: 2395-0056 Volume: 05 Issue: 06 | June-2018 www.irjet.net p-ISSN: 2395-0072 © 2018, IRJET | Impact Factor value: 7.211 | ISO 9001:2008 Certified Journal | Page 2690 3.2.3 Max LOG-MAP Algorithm The difference between the Log-MAP and the Max Log-MAP is that in the Log-MAP it always consider all paths into calculations, and it splits them into two sets as s=1, s=0. Which may changes from step to step and it will create some problems in trellis structure, where as in Max-Log MAP algorithm it consider only two paths per step, so the trellis can be calculated easily without splitting any sets as it consider only two sets. In the decoding process, at trellis,the algorithm always considers two paths per step either with the bit zero or bit one. The paths of the likelihood will differ step by step at the output side. In this one path may change, but the other path will be the maximum likelihood path. In the max-log-MAP algorithm, maximum likelihoodpathtakes the decision of the output bits, which is suitable for both parity bits and the systematic bits [8]. (8) Here α, β and γ are used to represent the forward recursive, backward recursive and branch transition probabilities, respectively. Now, for expressing the max-log-mapdecoding algorithm, the equation (8) can be represented as follows (9) By considering the equation (9), it is clear that the max-log- MAP algorithm will take the same decisions as the decisions are taken by the soft-output Viterbi algorithm. IV. TRELLIS DIAGRAM The use of the Trellis diagram is to describe the behavior of the turbo encoder and it is important element in the process of decoding. The trellis representation is achieved from its state diagram, as shown in figure3.Forthe turbo encoder, the trellis is operated by including m = K-1 additional bits after the input sequence, where K is the number of columns in the generator matrix G. Extra bits are used to move the encoder with all-zero state, by using RSC encoders. The blocks which are used here are interleaver, trellis structure for the turbo code implementation. Fig. 3: Trellis Structure V. PUNCTURING Puncturing is a method used to increase the code rate, by multiplexing the two coded streams. Thepuncturing block determines which bits to remove or to preserve by using the binary puncture vector parameter. It allows encoding and decodingof higher rate codes. Andalsousedin converting the code rate. VI. INTERLEAVER DESIGN The interleaver place an important role in theturbo codes. Turbo codesare mainly designed for the burst errors, in which the interleaver helpsin removing the errors. Turbo encoder is designed with the help of an interleaver. It is also helpful for maintaining the BER performance by regularly changing the size of an interleaver. In turbo code, random interleaver is used for rearranging the data bitswithout any repetition. At both the encoding and decoding side the Interleaver is used [7]. The interleaver improves the code error performance at moderate to high signal-to-noise ratio [7]. It generates a long block of data at the encoder side, at the output it connect two decoders and helps in correcting the errors. When the encoded data passes fromthefirstdecoder, only some of the errors got corrected. Then the received message from first decoder has been sent through the interleaver, interleaved output of the first decoded data is passes to the second decoded data, then the remaining errors get corrected, then the same procedure has been repeated number of times. The interleaver is able to givethe random values and that will help to give the parity bits from each of the RSC encoders which are independent. These parity bits depend on the length or depth of an interleaver. VII. MAX LOG-MAP ALGORITHM AND VITERBI ALGORITHM Asin the Viterbi-algorithm only theblockof200bits of messages are decoded, but as in the case of turbo codes, the blocksare on the order of 16K bitslong are decoded.The
• 4.
  International Research Journalof Engineering and Technology (IRJET) e-ISSN: 2395-0056 Volume: 05 Issue: 06 | June-2018 www.irjet.net p-ISSN: 2395-0072 © 2018, IRJET | Impact Factor value: 7.211 | ISO 9001:2008 Certified Journal | Page 2691 main reason of this length is to reduce the bits which are entering into the second encoder, the use of this long length result in a better connection with the message which is coming from the first encoder. Viterbi algorithm is used for decoding a bit stream in which it uses the convolutionalcode or a trellis code for the encoding purpose. It is also used for decoding convolutional codes with constraint lengths in which k<=3. Both the algorithm are used for the decoding purpose, in this the map algorithm is suitable for both high and low SNR values [10]. Max-Log-maximum a posteriori (MAP) algorithmis mainly used for turbo decoding [9]. As in the case of complexity, the Max Log-MAP algorithm suits for turbo decoding over additive-white-Gaussian-noise channelsover frequency-selective channels. Even there is a loss in inter symbol-interference channelsthe algorithm triesto givethe better results [8]. As a result both the algorithm is used for the decoding purpose. In the project the Max log-MAPalgorithm has been taken which is able to achieve the decoded result, as it takes the soft decisions, in which it accepts the values which are other than 0 and 1, in order to take reliability. The method of exchanging extrinsic information between different components is achieved with log-MAP-algorithm. As a result both the algorithm gives the similar output [11]. VIII. ENCODING AND DECODING ALGORITHM The software used is MATLAB which is a matrix laboratory developed by Math Works, MATLAB allows multiple functions to be implemented. Such asmanipulation of the matrices, algorithm implementation, function or data plotting, interfacing with the programswhich are written in different languages, which includes C, C++, C#, Java and etc. For Encoding Process, following steps are processed. 1. For text encoding, select an appropriate text. 2. Convert the text into binary array, then add redundancy bit into the total length of the text. 3. Generate a prime number to get the encoding output. 4. Prime number can be taken as q, and then the frame length of the turbo should be equals to q-1. 5. Generate a random integer sequence, the length of the sequence is selected as q, and the total numbers in the sequence should be transverse from 0 to q-1. 6. Create a encoded output, which is equating to the parameters which are present in the encodercircuitandalso add puncture, weather to preserve or to remove the extra bit. 7. Get the output of the encoder which will be getting in the binary form. 8. The errors are introduced at the length of the encoded output, and the locations of the errors are also shown. To decode, the following steps are processed. 1. After the encoding process, the decoding is done by demultiplexing to get the input for decoder 1 and decoder 2. 2. After demultiplexing, equate the value to another parameter. Then, initialize the extrinsic information. 3. Log map algorithm is applied to the decoder1anddecoder 2 outputs, to get the demultiplexed output. 4. at last, convert back the binary array to text form, to get the decoded output. IX. TEST AND RESULT The test for the encoding and the decoding of the text and images are done, the error hasbeen introduced,and the location of the error has also shown. This will get corrected in the decoding part, and results are also shown. For text firstly got the results in a binary form, and converted back to the text and for the image, in Fig. (4) It shows the particular figure which need to be encoded and decoded. At fig. (5) It showsthe encoded outputof the figure which is considered at fig (4). And at Fig. (6) It shows the decoded output in which it removes the error and gives the appropriate decoded output. As encoded and decoded output are executed and also the error location is shown, By seeing at the results, turbo codes are suitable forthetextand image encoding and decoding. For text Text: 'Hello' Encoded output: Error_id 25 35 40 27 39 Decoded output: ‘Hello’
• 5.
  International Research Journalof Engineering and Technology (IRJET) e-ISSN: 2395-0056 Volume: 05 Issue: 06 | June-2018 www.irjet.net p-ISSN: 2395-0072 © 2018, IRJET | Impact Factor value: 7.211 | ISO 9001:2008 Certified Journal | Page 2692 For Image Fig.4: Selected Picture Fig.5: Encoded Output Error _id 24 22 7 25 2 Fig. 6: Decoded Output SIMULATION RESULT: Fig. 7: BER Performance of Rate R=1⁄2 Turbo codes for Different Iteration X. CONCLUSION AND FUTURE WORK In this the encoding and decoding oftheturbocodes are designed. Encoding is designed by two recursive systematic convolutional encoders which are separated by an interleaver in which the input will also takes place at the output, the turbo encoding is performed and in which the errors has been introduced. At the decoder side two decoders are used which are serially connected and are also separated by an interleaver, in which the interleaver randomize the bursty errors and get the decoded output. Max Log-map algorithm is used in the iterativedecoder,after some fixed number of iteration values, it can be able to give the iterative decoded output usually it takesthe order of 10- 20 as shown in the results. For the future work it can also be used for the audio and video error detection andcorrection. REFERENCES [1] Berrou, Claude; Glavieux, Alain; Thitimajshima, Punya, Near Shannon Limit Error-Correcting (PDF), Vol. 61, February 2010. [2] By Kenneth S. Andrews, Dariush Divsalar, Sam Dolinar “The Development of Turbo and LDPC Codesfor Deep-Space Applications” IEEE | Vol. 95, No. 11, November 2011. [3] Berrou, Claude, The ten-year-old turbo codes are entering into service (PDF), Bretagne, France, retrieved 11 Vol. 57, February 2012. [4] “PARALLEL VLSI ARCHITECTURE FOR MAP TURBO DECODER” Rnstislav (Reuven) Dnbkin, Michael Peleg, Ran Ginnsar, Vol. 36, pp.384-388, Jan.2015 IEEE. [5] M. P. C. Fossorier, F. Burkert, S. Lin, and J. Hagenauer on the equivalence between SOVA and max-log-MAPdecodings, IEEE Commun.Lett., vol. 2, no. 5, May 2015. [6] ThomasJerkovits, balazsMatuz “Turbo CodeDesign For Short Blocks”, Proceedings IEEE, International Conference on Communications, Vol. 19 Feb. 2016. [7] Andersen JD and Zyablov VV, “Interleaver Design for Turbo Coding”, Proceedingsof the InternationalSymposium on Turbo Codes, Vol. 54 September 2016. [8] Shaharam Talakoub, Leila Sabeti, Behnam Shahrrava, Majid Ahmadi. “An improved Max-Log-Map Algorithm for Turbo Decoding and Turbo Equalization”, IEEETransactions on Instrumentation and Measurement, Feb. 2016. [9] Benedetto, S., et al., “Soft Output Decoding Algorithm in Iterative Decoding of Turbo Codes,” TDA Progress Report 42-124, Jet Propulsion Laboratory, Pasadena, California,Vol. 18 pp. 63-87, February 15, 2017, [10] Bit Error Rate Estimation for Turbo Decoding - Nick Letzepis, Member, IEEE, and Alex Grant, Senior Member, IEEE, IEEE Transaction on Communications, Vol. 57, NO. 3 March 2017. [11] Pietrobon, S., “Implementation and Performance of a Turbo/MAP Decoder,” Int’l. J. Satellite Commun, vol. 16, pp. 23-46, Jan-Feb 2017, [12] Kenneth S. Andrews, Dariush Divsalar, Sam Dolinar “The Development of Turbo and LDPC CodesforDeep-Space Applications” IEEE | Vol. 95, No. 11, November 2014