 Open Access
 Total Downloads : 376
 Authors : Aliaa Said Mousa, Prof. Dr. Mahmoud Fathi Mahmoud, A. I. Taman
 Paper ID : IJERTV4IS060452
 Volume & Issue : Volume 04, Issue 06 (June 2015)
 Published (First Online): 18062015
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
Implementation of Soft Decision Viterbi Decoder Based on a Digital Signal Processor
Aliaa S. Mousa 
A. I. Taman 
Mahmoud F. M. 
Electrical Engineering Department 
Electrical Engineering Department 
Electrical Engineering Department 
Faculty of Engineering at Benha 
Faculty of Engineering at Benha 
Faculty of Engineering at Benha 
Benha, Egypt 
Benha, Egypt 
Benha, Egypt 
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

CONVOLUTIONAL ENCODER Convolutional coding used channel coding method [2]. A general convolutional encoder shown in Fig.2, the encoder has a kKstage shift register and n module2 adders with constraint length K. The constraint length K is the number of kbit shifts over
1 2 3 .. kK
kK stage shift register
m = m1 , m2 ,., mi
..
Input Sequence (Shift in k at a time)

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 module2 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]


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.

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].

Sequential decoding: It was a suboptimal algorithm.Ithas betterperformance than the previous method. The advantage of sequential decoding isits usage for decoding long constraintlength convolutional codes. The disadvantage of sequential decoding was variable decoding time and required large memory [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 loglikelihood function [4].
No Trellis
stages
end?
End
Output decoding bits
Yes


56f807evm 16Bit Hybrid Processor Hardware

Architecture Overview

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

DSP and MCU functionality in a unified,Cefficient architecture

Hardware DO and REP loops

MCUfriendly instruction set supports bothDSP and controller functions: MAC, bitmanipulation unit, 14 addressing modes

60K Ã—16bit words Program Flash

2K Ã—16bit words Program RAM

8K Ã—16bit words Data Flash

4K Ã—16bit words Data RAM

2K Ã—16bit words Boot Flash

Up to 64K Ã—16 bit words each of externalProgram and Data memory

Two 6 channel PWM Modules

Four 4 channel, 12bit 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

160pin LQFP or 160 MAPBGA Packages
Fig.6.56F807 Block Diagram


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 SoftDecision Viterbi Decoding

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

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 softdecisionViterbi 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 threebit 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.

Results from Implementation:This section covers results/simulations done on 'code warrior IDE' and implemented on dsp56F807evmDigital 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


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.

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.


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.9E008 at 6db on an AWGN channel with BPSK modulation and K=7.
Convolutional encoder with soft decision Viterbi decoder is successfully implemented on DSP56f807evm.

REFERENCES

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.

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

Varsha P. Patil, Prof. D. G. Chougule, Radhika.R.Naik ,Viterbi Algorithm for error detection and correction, IOSR Journal of Electronicsl and Communication Engineering (IOSRJECE)
ISSN: 22782834, ISBN: 22788735, PP: 6065

SHU Lin and DANIEL J. Costello, Error Control Coding,
Prentice Hall, Englewood Cliffs, New Jersey, 19832004.

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

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