IntroductionPrinciple of Turbo CodesEncodingDecoding1. Viterbi Algorithm2. MAP algorithm3. Decoder of Turbo Code Based on the MAPImplement Turbo CodeEncoder based on MAP algorithmDecoder based on MAP algorithmAlgorithm modificationMemory analysis and Algorithm mappingInstruction OptimizationConclusionReferenceImplementation of Turbo Code in TI TMS320C8xECE 734 VLSI Array Structures for Digital Signal ProcessingCourese Project Report Spring 2004Hao ChenMay 13 2004IntroductionThe next generation communication and information services demands fro higherdata rates and communication capacity. (Transmitting multimedia data through thewireless communication network will be) The next generation communication systemwill be to a great extent due to the progress of devices and circuit technology. Also thetheoretical developments play an important role in modern communication system.Shannon established the fundamental theory about the transmission rates in digitalcommunication system. In 1993, Berrou, Glavieux and Thitimajshima proposed Turbocodes which the practically feasible channel utilization is almost closed to the theorycommunication capacity limit. In this project, I will implement the Turbo code in TITMS320C8.Principle of Turbo CodesAccording to the information theory, the communication channel capacity is justdecided by the channel bandwidth and the noise in the channel. It’s always possible tofind a code-decode schemes to transmit one information sequence when the entropy ofthe information sequence is less than the channel capacity. So the question become howto find a good code-decode schemes to utility the channel capacity more efficiently withPage 1less resource and less time delay. The large number of channel code-decode schemeshave been introduced to utilize the communication channel more efficiency. However,the some code-decode schemes required too complex decoder algorithms which causethe code-decode schemes unpractical. The good trade-off between coding gain andcomplexity can be achieved by concatenated codes. The concatenated code applied twolevels coding, an inner and an outer code linked by an interleaver. The lower complexityof decoder is gained through two separately decoder compared with one decoder.Figure 1 the basic channel codingThe basic idea of Turbo code uses two convolutional codes in parallel with somekind of interleaving in between. The performance of code-decode schemes depend notonly in the minimum distance between the output codes but also in the probabilitydistribution of the output code. The convolutional codes decide the minimum distance ofthe code words. A good designed interleaver can make it possible that the probabilitydistribution of the output code is nearly uniform distribution. Similar to the structure ofencoder of Turbo code, the decoder of Turbo code also is composed by two decoders forconvolutional codes.Page 2EncodingFigure 2 the encoder structure of Turbo CodeThe figure 2 shows the encoder structure of the Turbo Code. The binary sequenceD is input information. The binary sequence C is the input information after interleaver.The A and B are the output of convolutional encoder corresponding to D and C. Thefinal output sequence of Turbo Code is V. The figure 2 shows two output Turbo Codesequences: one has code rate 1/2; another has code rate 1/3. General the both encodersare recursive systematic convolutional (RSC) encoders. The interleaver is the pseudo-random interleaver in general. The output sequence has near uniform distributionprobability with well designed interleaver.The RSC code can be represented as:( )( )( )1g zG zh z� �=� �� �; ( )0niiig z g z-== *�, ( )0niiih z h z-== *�Here z is the time delay. The signal flow graph of RSC encoder with n=4 is showed atfigure 3.Page 3Figure 3 the signal flow graph of RSC encoderDecodingThe decoder of Turbo Code is composed by two RSC decoders. There are severalthe decoding algorithms for RSC.1. Viterbi AlgorithmViterbi algorithm based on the Trellis structure is recursive methods for estimationof the state sequence of a discrete-time finite-state Markov process observed inmemoryless noise. Its output is in the form of hard-quantized estimation of symbols inthe most likely transmitted code sequence. We consider a simple convolutional codewith generator matrix ( )1 21 1G z z z- -� �= + +� � whose code rate is 1/2. The statetransform diagram of encoder is showed as figure 4. Page 4Figure 4 the state diagram of a convolutional encoderWe assume that the initial state of convolutional encoder is 00. The next state willbe 00 for input 0 or 01 for input 1. There are two possible new states for each old state.So we can show a trellis diagrams as figure 5 according to the state diagram. The Viterbialgorithm will decode the convolutional code using this trellis structure.Figure 5 the trellis diagramThe Viterbi algorithm is a forward recursive operation. During recursion, there aretwo important variables:P(i,t) : path matric of state i at time t. This variable represents the min cost when thestate at the time t is i. The cost is defined as the distance between receivePage 5sequence and decoded sequence from the path.S(i, t): survival path of stat i at time t. The variable presents the path to state i in trellisstructure from time 0 to t. The cost of this path is minimized.During recursive, the P(i,t) and S(i,t) is obtained by P(i,t-1) and S(i,t-1) (i=1, … ,Mstate). So cost minimization is just local optimized. Also the output of Viterbi algorithmis hard symbol estimation. The Vertibi algorithm can be modified to produce softoutputs. That is called soft output Vertibi algorithm (SOVA).2. MAP algorithmMAP stands for "Maximum Aposteriori Probability". The MAP algorithm was firstpresented to the coding community on 1974 by Bahl, Cocke, Jelinik and Raviv. TheMAP algorithm is considerably more complex than the Viterbi algorithm. The errorperformance of both the Viterbi and the MAP algorithms are similar under high SNRand low BER’s. But the MAP algorithm is found to outperform the Viterbi algorithm byquite a margin at low SNR and high BER’s. (SNR: signal to noise ratio, BER: bit errorratio) Also the MAP produces soft outputs. The probability of bit equal to 1 or 0 iscalled the soft-value of
View Full Document
Unlocking...