IPASJ International Journal of Electronics & Communication (IIJEC)
Web Site: http://www.ipasj.org/IIJEC/IIJEC.htm
Email: [email protected]
ISSN 2321-5984
A Publisher for Research Motivatin........
Volume 2, Issue 7, July 2014
Low Constraint Length and High Performance
Viterbi Decoder using VHDL
A.Srujani1 , MD.SuhaliAfroz2
1
PG Scholar, 2Assistant Professor,
Department of Electronics and Communication Engineering, Teegala Krishnareddy Engineering College Hyderabad,
A.P-500 097
ABSTRACT
This paper deals with Error correcting techniques in communication network. In digital electronics, the error correcting
techniques plays a vital role in communication channels. The type of Error correcting techniques are considered in this paper
is convolution encoder and viterbi decoder. The viterbi decoder is designed to decode the encode data. By using convolution
encoder length k and code rate of k/n can be simulated by using Xilinx and Modelsim 10.1b.
Keywords: Convolution encoder, Viterbi decoder, Error correcting techniques, Constraint length, High performance.
1. INTRODUCTION
In Today’s digital wireless communications, error correction and detection for transmission of data are most pertaining
issue for communication channels. By correcting and detecting of errors improves the capacity of the source data
transmission. Many error controlling proficiencies are used to track down the delusion of bits that are transmitted from
source to destination. Convolutional encoding is a sort of error correcting code and is one of the forward error
correction schemes particularly being convenient to minimize the bit error rate. But the implementation with
convolutional coding involves aggressive increase in power and area to attain the accuracy of decoding.All
communication channels is vulnerable to additive white Gaussian noise. Convolutional coding is a type of FEC
Particularly used to detect the corrupted signal. Convolutional codes are used in numerous pertinence in order to
achieve the transfer of data and to minimize the errors, include mobile communications, digital video and satellite
communications. Convolutional encoding with viterbi decoding is mainly pre-owned to control the errors and is a FEC
technique meticulous for removing Additive white Gaussian noise which corrupts the signals through a channel. But
the transmission of bits and correcting it by using convolution encoding with viterbi decoding are the steeps for a stated
scheme. Therefore by using the conception of VHDL with convolution encoder and viterbi decoder are very ambitious
for controlling of errors at the receiving side from transmitting section.
Fig 1 Block Diagram of a Crypto System
In this paper by using the VHDL implementation in designing the convolution encoder and viterbi decoder which are
imperative in wireless communication. In this concept, a type of crypto system is used for transmitting of message bits
and they are generated by using convolution encoder and then decoded output is attained with viterbi decoder.
Convolution codes are used to reduce the errors that are occurred over a transmission channel. Viterbi decoder clears
up the errors and present at output errorless signal or bits.In this paper the upcoming topics deals with the
convolutional encoder, viterbi decoder and the implementation of the total system with software implementation using
Xilinx 9.1 and Modelsim altera Starter edition 6.6d.
Volume 2, Issue 7, July 2014
Page 15
IPASJ International Journal of Electronics & Communication (IIJEC)
A Publisher for Research Motivatin........
Volume 2, Issue 7, July 2014
Web Site: http://www.ipasj.org/IIJEC/IIJEC.htm
Email: [email protected]
ISSN 2321-5984
2. CONVOLUTIONAL ENCODER
A convolutional encoder is a type of error correcting code used to track down the error that are occurred by the additive
white Gaussian noise to detect the corrupted signal. In this a stream of input bits are transmitted in the form of message
and are generated such that the convolution encoder output mainly depends on the current state and the present Input.
In convolutional coding, message bits ‘m’ are encoded and transformed into an n-bit symbol where m/n is the code rate
(n>=m). Here, constraint length ‘k’ is the length of acode and depends upon on the transmission of bits, codes are
generated. In convolutional coding, code rates of ½ with constraint length, k of 3 are used.Convolutional coding is
pecularized with two parameters and can be implemented with a single Boolean xor gate. The two main parameters of
convolutional encoder implicate the code rate and constraint length. It is a simple possible code and involves set of ‘n’
generating polynomials. The ratio (n≥k) represents the ratio of number of bits into the convolutional encoder k into the
number of channel symbol outputs by the convolutional encoder ‘n’. A convolutional encoder is generally typified in k
inputs, n outputs and m shift registers or flip-flops with a rate of k/n.In this a cod rate of ½ is generated such that k is 1
and n is 2 and the format represent (k, n, m) or (n, k, m).
Fig 2 Convolution Encoder
As convolution encoder depends on current state and current input are sometime adverted as trellis codes. By using
convolution encoder, to encode the data we present with ‘m’ memory registers which grips the input ‘k’ to generate a
code vectors. The encoder has n modulo-2 adders and n generator polynomials one for each adder. The above figure
two represent two bits of encoded information for single bit. Here input sequence of 1 or 0 is generated and the shift
registers are used to shift the bit. Xor gates are connected such that based on the given condition polynomial are
generated and outputs are represented as code vectors y (0) and y(1).Based on the notion of state and trellis diagram,
convolution codes are generated. Convolution encoding is a finite state machine which involves different states to
represent the plight of input.
Fig 3: State Diagram of Convolutional Encoder
Table: Truth table for State Diagram
Volume 2, Issue 7, July 2014
Page 16
IPASJ International Journal of Electronics & Communication (IIJEC)
A Publisher for Research Motivatin........
Volume 2, Issue 7, July 2014
Web Site: http://www.ipasj.org/IIJEC/IIJEC.htm
Email: [email protected]
ISSN 2321-5984
Trellis code represents a graph whose node are ordered into vertical slices (time) and with each node at each time are
connected at an earlier and later time.
Fig 4: Trellis Diagram
3. VITERBI DECODER
A viterbi decoder uses the viterbi algorithm for decoding a bit stream that has been encoded using a convolutional code.
Mainly depends on the synchronization and quantization of analog signals results a digital signal. The binary inputs
are 1, o of a digital signal are coded and viterbi decoder decodes the symbols within the borderland in which frames are
analyzed. Based on the construction, two types of vertebra decoding are present.
 Hard decision vertebra decoding
 Soft decision vertebra decoding.
In hard decision viterbi decoding, hamming distance place a crucial role in which it depends on two possibilities that is
0 and 1. Hamming distance is used to determine the count of bits on the operation of xor gate.In soft decision decoding
based on most probable code words at output so that noise can be avoided in the corrupted bits. In this quantization of
multibit occurs where as in hard decision decoding only single bit quantization occurs. Functional description of viterbi
decoder involves
i. Branch metric unit
ii. Path metric unit
iii. Trace back unit.
Fig 5: Description of Viterbi Decoder
A branch metric unit function is to calculate branch metrics, which are normed at a distance between every possible
symbol in the code alphabet and the received symbol. BMU (Branch metric unit) is calculated mainly on the concept of
hamming distance with xor operation for every possible state. BMU is calculated at node to node level.
Fig 6: Branch Metric Unit (BMU)
Volume 2, Issue 7, July 2014
Page 17
IPASJ International Journal of Electronics & Communication (IIJEC)
A Publisher for Research Motivatin........
Volume 2, Issue 7, July 2014
Web Site: http://www.ipasj.org/IIJEC/IIJEC.htm
Email: [email protected]
ISSN 2321-5984
In PMU (Path metric unit) finds all the paths through which the symbols in states are achieved from the current states
and previous states. In PMU based on the length of nodes which are connected in trellis, the incoming links and present
links of both adders are compared and select a particular path based on the decision and stores as a new path.
Fig 7: Path Metric Unit (PMU)
Trace Back unit (TBU) stores the path from the decision made by PMU. Based on the decision computes the decoded
output. One of the outstanding accessions in TBU involves PNPH (Permutation network based path history) implements
the trellis in survivor path sequentially. PNPH performs less occupancy of area and increases the decoding speed.
4. VITERBI DECODER ALGORITHM
Based on the data that is transmitted from input source to destination involves different modules of convolutional
encoder and viterbi decoder.
Fig 8: Viterbi Decoder Algorithm
5. Simulation results
Viterbi test bench is simulated using Modelsim 10.1b. Code is written in Very High Speed Integrated Circuit Hardware
Description Language (VHDL). Viterbi decoder have the different modules that are Add compare select, Branch metric
unit, Decoder, Encoder, Trace back unit, SMU control unit and Test random data. Simple clock designs are completely
synchronous.
5.1 Simulation Waveforms of Viterbi Decoder
The Simulation Waveform of Viterbi Decoder is shown in Fig. 6. To observe the speed and resource utilization, RTL is
generated, verified and synthesized using Xilinx Synthesis Tool (XST).
Figure 6: Simulation Waveform of Viterbi Decoder
Volume 2, Issue 7, July 2014
Page 18
IPASJ International Journal of Electronics & Communication (IIJEC)
A Publisher for Research Motivatin........
Volume 2, Issue 7, July 2014
Web Site: http://www.ipasj.org/IIJEC/IIJEC.htm
Email: [email protected]
ISSN 2321-5984
5.2 RTL Schematic of Viterbi Decoder
Below Shown is the RTL Schematic of the Viterbi Decoder.
Figure 7: RTL Schematic of Viterbi Decoder
5.3 Device Utilization Report
This synthesis report is generated after the compilation of Design for the targeted Xilinx SPARTAN 3A based
Xc3s400a FPGA Device. Here, The Design unit is not implemented on targeted FPGA Device. This report contains
about component used.
Table 1: Device utilization Summary
5.4 Timing and Power Summary
After the synthesis report, the timing diagram generated according to the given input. With the help of timing diagram
speed grade, Minimum period, Maximum Frequency, Maximum output required time after clock is calculated.
Timing Summary
• Speed Grade: -4
• Minimum period: 30.190ns
• Maximum Frequency: 33.124MHz
• Minimum input arrival time before clock: 2.993ns
• Maximum output required time after clock: 5.531ns
Power summary
Total estimated power consumption: P (mw): 49 mw
5.5 Comparative Analysis between Various FPGA Devices
Different FPGA family of SPARTAN are used to measure the performance of proposed Viterbi Decoder
Design.
5.5.1 Performance Comparison of proposed Viterbi Decoder Design in Various SPARTAN FPGA Devices
Table 2: Comparison between various SPARTAN FPGA Devices
Volume 2, Issue 7, July 2014
Page 19
IPASJ International Journal of Electronics & Communication (IIJEC)
A Publisher for Research Motivatin........
Volume 2, Issue 7, July 2014
Web Site: http://www.ipasj.org/IIJEC/IIJEC.htm
Email: [email protected]
ISSN 2321-5984
5.5.2 Performance Comparison of proposed Viterbi Decoder Design in Various VIRTEX FPGA Devices
Different FPGA family of VIRTEX is used to measure the performance of proposed Viterbi Decoder Design.
Table 3: Comparison between various VIRTEX FPGA Devices
6. CONCLUSIONS
In this Paper Resource optimized Viterbi Decoder has been proposed. The proposed Viterbi Decoder has been
designedwith VHDL using traceback method. The designed Viterbi Decoder has been simulated using Xilinx ISE
simulator and synthesized with XST. The simulated and synthesized results show that proposed design can work at an
estimated frequency of 33.124 MHz by using considerable less resources of target FPGA device SPARTAN 3A. This
Paper also contains comparative analysis between various FPGA devices for the same Design. The result shows that
proposed design can work at Max. Frequency 113.104 MHz for targeted FPGA Device VIRTEX 5 among all FPGA
Devices. So, VRTEX 5 FPGA Device can give Max. Frequency for proposed Design among all FPGA Devices.
We are giving inputs to the Viterbi decoder test bench is Test random data and the length of track back will be of 64.
The inputs are Clock, Reset, bit-in and valid-in outputs are Symbol0,symbol1 and valid-out. The simulation result of
Encoder and Test bench of viterbi decoder (Test random data) is shown in below figures.
References
[1] Mahe Jabeen and Salma Khan, Design of Convolution Encoder and Reconfigurable Viterbi Decoder,
International Journal of Engineering and Science, Vol. 1, No.3, Sep 2012.
[2] P. Subhashini, D. R. Mahesh Varma and Y. David Solomon Raju, Implementation Analysis of adaptive Viterbi
Decoder for High Speed Applications, International Journal of Computer Applications (0975-– 8887), Volume 31–
No.2, October 2011
[3] S.V.Viraktamath and G.V.Attimarad, Impact of constraint length on performance of Convolutional Codec in
AWGN channel for image application, International Journal of Engineering Science and Technology, Vol. 2(9) ,
2010, 4696-4700.
[4] Bernard Sklar, Digital Communications Fundamentals and Application, Published by Pearson education, Year
2003
[5] B.P.Lathi, Modern Digital and Analog Communication Systems, Third Edition.
[6] J.G. Proakis, Digital Communications, McGraw Hill.
[7] J. Bhaskar, A VHDL Primer, Third Edition
[8] Volnei A. Pedroni, Circuit Design with VHDL
[9] Christian Baumann, ―Field Programmable Gate Arrray (FPGA), Summary paper for the seminar Embedded
System Architecture, University of Innsbruck, January 13, 2010.
[10] Matthias Kamuf, Member, IEEE, Viktor Öwall, Member, IEEE, and John B. Anderson, Fellow, IEEE,
Optimization and Implementation of a Viterbi Decoder under Flexibility Constraints, IEEE Transactions on
Circuits and Systems—I: Regular Papers,Vol. 55, No. 8, September 2008.
[11] C. Arun, V. Rajamani, Design and VLSI implementation of a Low Probability of Error Viterbi decoder,
First International Conference on Emerging Trends in Engineering and Technology, IEEE 2008.
[12] Miloš Pilipovic, Marija Tadic, FPGAImplementation of Soft Input Viterbi Decoder for CDMA2000
System,
16Th Telecommunication forum TELEFOR, 2008.
Volume 2, Issue 7, July 2014
Page 20
IPASJ International Journal of Electronics & Communication (IIJEC)
A Publisher for Research Motivatin........
Volume 2, Issue 7, July 2014
Web Site: http://www.ipasj.org/IIJEC/IIJEC.htm
Email: [email protected]
ISSN 2321-5984
[13] Behzad Mohmad Heravi and Bahram Honary, Multi-rate Parameterized Viterbi Decoding for Partial
Reconfiguration, PGNet 2006.
[14] Sriram Swaminathan, Russel Tessier, Dennis Goeckel and Wayne Burleson, A Dynamically Reconfigurable
Adaptive Viterbi Decoder, FPGA 02, Feb 2002, pages 24-26.
[15] T. K. Truong, Senior Member IEEE, Ming- Tang Shih, Irving S. Reed, Fellow IEEE, and E.H. Sartorius,
Member IEEE, A VLSI Design for Trace- back Viterbi Decoder, IEEE Transaction on Communications, Vol. 40,
No. 3, March 1992.
[16] A. J. Viterbi, Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm,
IEEE Trans. Inform Theory, vol. IT-13, pp. 260-269, Apr. 1967.
AUTHOR
1) A.Srujani PG Scholar, Department of Electronics and Communication Engineering, Teegala
Krishnareddy Engineering college Hyderabad, A.P-500 097, India.
2) SuhaliAfroz MD Asst Professor, Department of Electronics and Communication Engineering,Teegala Krishna
eddy Engineering college Hyderabad, A.P-500 097, India.
Volume 2, Issue 7, July 2014
Page 21