Implementation of Soft Decision Viterbi Decoder Based on a Digital Signal Processor

Implementation of Soft Decision Viterbi Decoder Based on a Digital Signal Processor

AbstractThis paper describes theimplementation of soft decision Viterbi channeldecoding algorithm using a digital signal processor. This was done through a computer simulation and also through using a dsp56f807evm digital signal processor (DSP). The dsp56f807evm DSP can achieve the performance of up to 40 million instructions per second (MIPS) at 80MHz core frequency and consequently has gained more and more popularity in many applications. Moreover, the implemented Viterbi decoder was tested againstan additive white Gaussian noise channel (AWGN) at different signal to noise ratios (S / N) and different convolutional code constraint lengths.

KeywordsConvolutional Encoder, Viterbi Algorithm, Viterbi Convolutional Decoding Algorithm

1. CONVOLUTIONAL ENCODER Convolutional coding used channel coding method [2]. A general convolutional encoder shown in Fig.2, the encoder has a kK-stage shift register and n module-2 adders with constraint length K. The constraint length K is the number of k-bit shifts over

   1 2 3 .. kK

   kK- stage shift register

   m = m1 , m2 ,., mi

   ..

   Input Sequence (Shift in k at a time)

   1. INTRODUCTION

      The convolutional codingfirst introduced by Elias in 1955[5].Convolutional encoding and Viterbi decoding area powerful forward error correction (FEC) technique for additive white Gaussian noise (AWGN) channel. It is operating on data stream and has memory that uses previous bits to encode, and has good performance with

      1 2 .n

      Codeword sequence U = U1 , U2 ,, Ui,..

      Where Ui = u1i,.,uji ,. uni = ith codeword branch uji = jth binary code symbol of branch word U

      n module-2 adders

      low implementation cost [1].Convolutional codinghas beenused in communication systemsincluding deep spacecommunications and wireless communications to improve the bit error rate (BER) performance. The Viterbi decodingalgorithm (VA) proposed in 1967 by Andrew Viterbi was a decoding process for convolutional codes [5]. It is used for decoding a bit stream that has been encoded using FEC code. The convolutional encoder adds idleness to a continuous stream of input data by using a linear shift register. The Convolutional Encoder and Viterbi Decoder used in the Digital Communications System is shown in Fig.1,[1].

      In this paper, we concern with designing and implementing a convolutional encoder and soft decision Viterbi decoder which are the essential block in digital communication systems using DSP hardware kit.

      Fig.2. convolutional encoder (rate = k/n, length K) [2]

      Channel

      which a single message bit can affect the encoder output. The encoder is working in the following way. At every time units, k bits of data are serially input into the left k stages of the shift register, while all bits in the register are shifted k stages to the right. After that, the outputs of n adders are sampled one after another to generate the coded symbols. These coded symbols are then used by the modulator to generate the signals to be transmitted over the channel. Since at each input unit time, there are n bits in the encoded signal for k bits in the input message signal, the code rate is k/n message bits per code bit, where k<n. although k could be any positive integer, it is generally specified as k=1 in most applications, that is, the input message bits are shifted just one bit at a time into the encoder shift register [2].

      Convolutional Encoder

      Input

      bit stream

      Encoded stream

      Encoded stream

      with noise

      Decoded bits

      Viterbi Decoder

      without

      noise

      To explain the convolutional encoder, an example is shown in Fig.3,[2]. It is a k = 1 and n = 2 convolutional encoder with constraint length K = 3.

      Noise (AWGN)

      Fig.1.Convolutionalencoder and Viterbi decoder [1]

      Fig.3.Convolutional Encoder (rate = ½, length K = 3) [2]

2. The Viterbi Algorithm for Decoding of Convolutional

   Codes

   There are different decoding methods for convolutional codes which are threshold decoding, sequential decoding and maximum likelihood decoding.

   1. Threshold decoding: It is called majority logicdecoding. It is the simplest of them, but it successfully applied only to the specific classes of convolutional code. It is applying to channel that having mid to good SNR. Moreover,It is also far away from optimal because of its inferior bit error performance [3].

   2. Sequential decoding: It was a sub-optimal algorithm.Ithas betterperformance than the previous method. The advantage of sequential decoding isits usage for decoding long constraint-length convolutional codes. The disadvantage of sequential decoding was variable decoding time and required large memory [3].

   3. Viterbi decoding: It is an optimal (in a maximumlikelihood sense) algorithm for decoding of convolutional code. It is dominant technique for convolutional codes. The advantage of Viterbi decoder is to satisfy bit error performance, low cost, fixed decoding time [3].But its computational necessities grow exponentially as a function of the constraint length, so it is generally limited in practice to constraint lengths of K= 9 or less [1]. Its main drawback is that the decoding complexity grows exponentially with the code length. So, it is used for short codes.

   Basically, the VA is the maximum likelihood decoding method. In other words, it finds the most likely transition sequence in a state diagram from a given set of input codes [2]. The encoder adds redundant information to the original information i, and the output t is transmitted through a channel. Input at receiver end (r) is the information with redundancy and possibly, noise. The receiver tries to extract the original information through a decoding algorithm and generates an estimate (z) of the transmitted code word. A decoding algorithm that maximizes the probability (|)is a maximum likelihood (ML) algorithm. An algorithm which maximizes the

   (|)through the proper selection of the estimate (z) is called a maximum a posteriori (MAP) algorithm. The two algorithms have identical results when the source information i has a uniform distribution. If the distribution of the source bits x is uniform, the two decoders are identical[5].

   By Bayers law, we can get [5]

   (|) () = (|) ()

   B. Flow Chart of Decoder of Viterbi Algorithm [5]:

   Start

   Initialize

   Calculate the four possible branch metric

   Load the branch metric

   ACS

   Store the path information

   States No

   end?

   Yes

   A. The Viterbi Convolutional Decoding Algorithm The Viterbi algorithm (VA) was proposed by Viterbi in 1967 as a technique of decoding convolutional codes. Later, Omura showed that the Viterbi algorithm was equivalent to finding the shortest path through a weighted graph. Forney recognized that it was a maxmum likelihood decoding algorithm for convolutional codes because the decoder output selected was the code word that gives the largest value of the log-likelihood function [4].

   No Trellis

   stages

   end?

   End

   Output decoding bits

   Yes

3. 56f807evm 16-Bit Hybrid Processor Hardware

   1. Architecture Overview

      • Up to 40million instructions per second(MIPS) at 80MHz core frequency

      • DSP and MCU functionality in a unified,C-efficient architecture

      • Hardware DO and REP loops

      • MCU-friendly instruction set supports bothDSP and controller functions: MAC, bitmanipulation unit, 14 addressing modes

      • 60K ×16-bit words Program Flash

      • 2K ×16-bit words Program RAM

      • 8K ×16-bit words Data Flash

      • 4K ×16-bit words Data RAM

      • 2K ×16-bit words Boot Flash

      • Up to 64K ×16- bit words each of externalProgram and Data memory

      • Two 6 channel PWM Modules

      • Four 4 channel, 12-bit ADCs

      • Two Quadrature Decoders

      • CAN 2.0 B Module

      • Two Serial Communication Interfaces (SCIs)

      • Serial Peripheral Interface (SPI)

      • Up to four General Purpose Quad Timers

      • JTAG/OnCETM port for debugging

      • 14 Dedicated and 18 Shared GPIO lines

      • 160-pin LQFP or 160 MAPBGA Packages

      Fig.6.56F807 Block Diagram

   2. Overview of the Simulation

      The model shownin Fig.7,is written in C- language code and simulated using MATLAB. The simulation ends after processing 100 bit errors or 106 message bits, whichever comes first.

      Fig.7. Block Diagram of Soft-Decision Viterbi Decoding

   3. Results

   The behavior simulation system was looped until 100 data bit errors were detected or 1000000 data bits were transmitted. Simulations were run with an Es/No from 0 dB to 3 dB with step .5 dB. The simulation and implementation of convolutional encoder and soft decision Viterbi decoder is tested against AWGN channelusing different signal to noise ratios(S / N) and different generatorpolynomials(different constraint length). The processor implementation results for rate ½ convolutional encoder and Viterbi decoder with different generator polynomials

   1. Results from Simulations:This section covers

      results/simulations done using Ccode and plots the results on matlab. Analysis of performance of the codes is done in terms of BER and Eb/No .This figure covers the BER plots of simulation results for rate 1/2 convolutional coding with soft-decisionViterbi decoding on an AWGN channel with various convolutional code constraint lengths

      Performance of Soft Decision Viterbi Decoder with Different Constraint Lengths

      -1

      				theoretical uncoded BER simulated BER,K=3 simulated BER,K=5 simulated BER,K=7 simulated BER,K=9

      10

      -2

      10

      -3

      10

      -4

      10

      BER

      -5

      10

      -6

      10

      -7

      10

      -8

      10

      -9

      10

      0 2 4 6 8 10 12

      Eb/No

      Fig.8. Simulation Results for Rate 1/2 and different constraint length

      The results obtained is shown in Fig.8, using the simulation code, with the trellis depth set to 5x K, using the adaptive quantizer with three-bit channel symbol quantization.For each data point, the simulation ran until 100 errors (or possibly more) occurred. With this number of errors, theconfidence indexwas 95%. This means that the true number of errors for the number of data bits through the simulation lies between 80 and 120.

   2. Results from Implementation:This section covers results/simulations done on 'code warrior IDE' and implemented on dsp56F807evm-Digital Signal Processing kit and plots the results on matlab. The implementation done until 100 data bit errors were detected or 128 data bits were transmitted.

      Performance of Soft Decision Viterbi Decoder with Different Constraint Lengths

      -1

      				theoretical uncoded BER simulated BER,K=3 simulated BER,K=5 simulated BER,K=7

      10

      -2

      10

      -3

      10

      -4

      10

4. COMPARISON BETWEEN SIMULATION AND THEORETICAL RESULTS:

   				theoretical uncoded BER simulated BER,K=3 theoretical BER,K=3

   -1 Performance of Soft Decision Viterbi Decoder with K=3 10

   -2

   10

   -3

   10

   -4

   10

   BER

   -5

   10

   -6

   10

   -7

   10

   -8

   10

   -9

   10

   0 2 4 6 8 10 12

   Eb/No

   Fig.11. cmparison between simulation results and theoretical results with a 1/2 rate and K=3

   BER

   -5

   10

   -6

   10

   -7

   10

   -8

   10

   -9

   10

   0 2 4 6 8 10 12

   Eb/No

   Fig.9.Implementation Results for Rate 1/2 and different constraint length

   The simulation and implementation results are matched with the theoretical results.

   1. Theoretical Results from Matlab:

   Performance of Soft Decision Viterbi Decoder with Different Constraint Lengths

   -1 Performance of Soft Decision Viterbi Decoder with K=5 10

   			theoretical uncoded BER simulated BER,K=5 theoretical BER,K=5

   -2

   10

   -3

   10

   -4

   10

   BER

   -5

   10

   -6

   10

   -7

   10

   -8

   10

   -9

   10

   0 2 4 6 8 10 12

   Eb/No

   Fig.12. comparison between simulation results and theoretical results with

   0

   				theoretical uncoded BER theoretical BER,K=3 theoretical BER,K=5 theoretical BER,K=7 theoretical BER,K=9

   10

   0

   -2 10

   10

   -2

   -4

   10 10

   a 1/2 rate and K=5

   Performance of Soft Decision Viterbi Decoder with K=7

   BER

   			theoretical uncoded BER simulated BER,K=7 theoretical BER,K=7

   -6

   10

   -4

   10

   BER

   -8

   10

   -6

   10

   -10

   10

   -12

   10

   -8

   10

   0 2 4 6 8 10 12

   Eb/No

   Fig.10. theoretical results with a1/2 rate and different constraint length

   -10

   10

   0 2 4 6 8 10 12

   Eb/No

   Fig.13. comparison between simulation results and theoretical results with a 1/2 rate and K=7

   			theoretical uncoded BER simulated BER,K=9 theoretical BER,K=9

   0 Performance of Soft Decision Viterbi Decoder with K=9 10

   -2

   10

   -4

   10

   BER

   -6

   10

   -8

   10

   -10

   10

   -12

   10

   0 2 4 6 8 10 12

   Eb/No

   Fig.14. comparison between simulation results and theoretical results with a 1/2 rate and K=9

   From the above figures, the simulation and theoretical results approximately with the same valuesat different constraint lengths.

5. CONCLUSION

   Convolutional Encoder and soft decision Viterbi decoder for the rate ½ is simulated and implemented for different constraint lengths for different constraint lengths and for AWGN channel using different signal to noise ratios(S / N). Moreover, the Viterbi decoding algorithm is mature error correct system, which will give us a BER at 2.9E-008 at 6db on an AWGN channel with BPSK modulation and K=7.

   Convolutional encoder with soft decision Viterbi decoder is successfully implemented on DSP56f807evm.

6. REFERENCES

1. A.Mallaiah, K.Lakshmi Narayana, A.Jaya Lakshmi ,Design and Simulation of a Low Power Viterbi Decoder using Constraint Length Nine,International Journal of Computer Applications (0975 8887) Volume 84 No 2, December 2013.

2. Haifeng Li, M.S.E.E. ,CMOS Current Mode Analog Viterbi Decoder, New Mexico state University, Las Cruces, New Mexico, December 2003.

3. Varsha P. Patil, Prof. D. G. Chougule, Radhika.R.Naik ,Viterbi Algorithm for error detection and correction, IOSR Journal of Electronicsl and Communication Engineering (IOSR-JECE)

   ISSN: 2278-2834-, ISBN: 2278-8735, PP: 60-65

4. SHU Lin and DANIEL J. Costello, Error Control Coding,

   Prentice Hall, Englewood Cliffs, New Jersey, 1983-2004.

5. WEI CHEN, RTL implementation of Viterbi decoder, Dept. of Computer Engineering at Linköpings universitet, Linköping June 02, 2006.

6. Suneha Gupta, Design and Implementation of an Optimized Viterbi Decoder, Department of Electronics and Communication Engineering, Thapar University, Patiala, July 2012.