FPGA Implementaion of Soft Decision Viterbi Decoder

FPGA Implementaion of Soft Decision Viterbi Decoder

Sahar F. Abdelmomen Electrical Engineering Department Faculty of Engineering at Benha Benha, Egypt.

A. I. Taman

Electrical Engineering Department Faculty of Engineering at Benha Benha, Egypt.

Hatem M. Zakaria Electrical Engineering Department Faculty of Engineering at Benha

Benha, Egypt.

Mahmud F. M. Electrical Engineering Department Faculty of Engineering at Benha

Benha, Egypt.

Abstract This paper presents an implementation of a 3-bit soft decision Viterbi decoder. It uses survivor path with parameters for wireless communication in an attempt to reduce the power, area, and cost. At the same time, it increases the speed. The circuit design supports a constraint length of seven and a code rate of

1. The convolution encoder and the 3-bit soft decision Viterbi decoder are implemented on Virtex-6 XC6VLX240T FPGA at 66 MHZ core frequency starter kit. Xilinx ISE12.1 series is used for simulation. The implemented design shows an area overhead reduction of 50% compared to Spartan 3E device. In a Virtex-6 the proposal achieved 2014 LUTs in compared with Spartan 3E solutions, 3155 LUTs are achievable compared with Virtex_5 solutions. In addition, Slice Registers occupied 1011 , while 3214 in Spartan 3E then 69% are achievable in Virtex 5, then Virtex 6 better than previous state-of the- art solutions in terms of area, Higher data rates. Moreover, the implemented Viterbi decoder tested against an additive white Gaussian noise channel (AWGN) and consequently has gained more popularity in many applications.

   Keywords Viterbi decoder; convolution encoder; soft decision; FPGA.

   1. INTRODUCTION

      There are many techniques and algorithms available for transmission and reception of digital data over noisy channel but Convolution Encoder and Viterbi Decoder are most efficient. It gives improved coding gain and enhances performance [1]. Viterbi decoder is one of the efficient methods of decoding of convolution codes. Although widely-used, the most popular communications decoding algorithm, the Viterbi algorithm, requires an exponential increase in hardware complexity to achieve greater decode accuracy [2]. Its very necessary for the telecommunication to reduce the data corruption by providing a suitable solution to the errors occurred in the communication process [3]. One of the challenges of digital communication systems is that of providing transmitting information from one end of the system the reliability and quality that are acceptable to the user at the other end. Viterbi decoder swing between complex implementation and area. This paper introduce enhance the implementation of a soft decision Viterbi decoder on Virtex-6 FPGA XC6VLX240T to overcome problems complex implementation and area. Among the numerous advantages

      provided by the use of FPGAs three stand out in particular: the low cost of prototyping, the short production time, and conducting operations in parallel. Today, FPGAs are emerging as a useful parallel platform for executing demanding IP algorithms [4, 5]. FPGAs provide very high performance custom hardware solutions, and can be reconfigured in system. FPGAs also have advantages over conventional hardware implementations. Lower component count, lower real-estate requirements and simple assembly [6].

      A significant contribution is that our approach is the first to efficiently handle conditional asynchronous architectures with the presence of mismatched branch selection. The remainder of this paper is organized as follows. Section II reviews background on asynchronous pipelines and conditional pipelines. Section III explains the convolution encoding. Viterbi algorithm shown in section IV. Section V discusses types of Viterbi encoding. Selection mismatch effect on asynchronous circuits' behavior in results are discussed in section VIII. Finally, conclusions and future work are presented in Section VIII.

   2. LITERATURE REVIEW

      An exhaustive literature review has been carried out related to the titled work to find out the current research. In [13], K. Cholan, introduced new method of Viterbi decoder to improve in terms of area and speed. The design is based on reconfigurable FPGA technology, by adopting parallel pipeline features of the hardware resources. The overall system performance improved in terms of area and speed. In [1], Soreng B., a Convolution Encoder and Viterbi decoder of code rate1/2, and constraint length 7 was presented. It shows a large improvement in terms of area overhead. In [12], Gohel implemented a Viterbi decoder based on FPGA using a constraint length of 7 and a code rate of 1/2.Itshowed an improvement in the design by using trace back implementation of survivor sequence memory management for low power decoder design. In this paper an enhancement in the implementation of a soft decision Viterbi decoder on Virtex-6 FPGA XC6VLX240T is introduced to overcome problems of complex implementation and area.

   3. CONVOLUTIONAL ENCODING

      A convolutional encoder for K=7 and R=1/2 is depicted in Fig.1. The two output bits C1 and C2, which constitute a symbol, are generated and transmitted at every clock cycle. The number of memory elements, m, is one less than the constraint length K [32].C1 and C2 are the first and second code symbols respectively. The Viterbi algorithm estimates the maximum likelihood path through a trellis based on received symbols. Viterbi decoder needs a large number of arithmetic operations when decoding of each bit, for constraint length K=7, the Viterbi decoder performs 128 add and 64 compare-select operations for every encoded bit.

      Fig. 1. Convolutional Encoder for K=7 and R=1/2

   4. VITERBI ALGORITHM

      In this section, both the algorithm and operation behind the proposed 64 state Viterbi decoder, depicted in Fig. 2, are presented [1]. When a new symbol is received, the branch metric unit calculates the Euclidean distances (ED) for all possible trellis state transitions. The encoder is flushed with zeros at the end of each frame. The decoder performs frame by frame decoding. The computation of branch metrics is based on a comparison of the current input symbol with the expected value. The path metrics are identified as letters at different nodes of the trellis [7].

      The Viterbi algorithm is a maximum likelihood method to find the most probable sequence of hidden states based on a given sequence of observed outputs in Hidden Markov model. However it reduces the computational load by taking the advantage of special structure in code trellis. The algorithm involves calculating a measure of distance between the received signal at the time t1 and the entire trellis path entering each state at time t1. The most likely path through the trellis will maximize this metric. The early rejection of the unlikely paths reduces the decoding complexity. Advantage of Viterbi algorithm is that it has self- correction of the code, minimization of transmitting Energy, minimization of BW and very good ability to correct wrong transmitted bits [8].

   5. TYPES OF VITERBI DECODING

      The two decoding algorithms used for decoding the convolution codes are Viterbi algorithm and Sequential algorithm. The sequential decoding has an advantage that it can perform very well with long constraint length. The Viterbi

      decoding is the best technique for decoding the convolution codes but it is limited to smaller Constraint lengths [9].In order to realize a certain coding scheme a suitable measure of similarity or distance metric between two code words is vital. The two important metrics use to measure the distance between two code words are the Hamming distance and Euclidian distance adopted by the decoder depending on the code scheme, required accuracy, channel characteristics and demodulator type [10].

      Fig. 2. The Viterbi Algorithm [1].

      1. Hard Decision Viterbi Decoding:

         In the hard-decision decoding, the path through the trellis is determined using the Hamming distance measure. Thus, the most optimal path through the trellis is the path with the minimum distance. The Hamming distance can be defined as a number of bits that are different between the observed symbol at the decoder and the sent symbol from the encoder. Furthermore, the hard decision decoding applies one bit quantization on the received bits [10].

      2. Soft-Decision Decoding:

      Soft- decision decoding is applied for the maximum likelihood decoding, when the data is transmitted over the Gaussian channel. On the contrary to the hard decision the demodulator input is now an analog waveform and is usually quantized in to different levels in order to help the decoder decide more easily. A 3-bit quantization results in an 8-ary output [11, 12], as shown in Fig. 3. The advantage of using soft- decision decoding is to provide decoder with more information, which decoder then use for recovering the message sequences. It provides better error performance than hard- decision type Viterbi decoding also Performance improvement of approximately 2 dB in required S/N ratio compared to two level quantization for a Gaussian Channel. Disadvantage of using soft decision decoding is the increase in required memory size at the decoder and the reduce speed [8].

      Fig. 3. 3-bit Soft Decision.

      The sampled voltage (BPSK) is quantized in two levels and it is demodulated to a 0 or 1. Adding more levels to the quantization process improves the decoder performance, as the demodulator provides the decoder with a measure of confidence for its decision. For instance, in an 8 level soft decision, the demodulator identifies 8-levels. These levels indicate a 0 or 1 with a high or low confidence [9].Twos complement format can also be adopted.

      The "000" and "111" present the most confident '0' and '1'. On the contrary, the "011" and "110" present the most uncertain '0' and '1'. Since the soft decision will provide more information than the hard decision, it will prove 2-3 dB performance improvement for whole system. The table lists the interpretations of the eight possible input values for this example. For a Gaussian channel, 8-level quantization, when compared with 2 level quantization, results in a performance improvement in required signal to noise ratio of approximately 2 dB For the hard decision decoding, the Hamming distance is used. It is defined as the number of bits that are different between the received symbol at the decoder and the output symbol of the trellis diagram branch. The Euclidean distance such as in (1) is used to calculate the straight line distance between two points. In a plane with p1 at (x1, y1) and p2 at (x2, y2). In the Viterbi algorithm, there are two ways to calculate the distance to choose a most likelihood path. One is hamming distance which related to the hard decision. The other one is Euclidean distance related with soft decision.

      = (1 2)2 + (1 2)2

      TABLE I. INTERPRETATIONS OF EIGHT POSSIBLE INPUT VALUES

      Decision Value	Interpretation
      0	Most confident 0
      1	Second most confident 0
      2	Third most confident 0
      3	Least confident 0
      4	Least confident 1
      5	Third most confident 1
      6	Second most confident 1
      7	Most confident 1

   6. DECODER ARCHITECTURE AND IMPLEMENTATION

      A Viterbi decoder uses the Viterbi algorithm for decoding a bit stream that has been encoded using Forward error correction based on a code. There are other algorithms for decoding a convolutional encoded stream (for example, the Fano algorithm).The Viterbi algorithm is the most resource consuming, but it does the maximum likelihood decoding [12]. Fig.4 shows the block diagram of Viterbi decoder. It consists of the following modules Branch Metric Unit, ACS, and Survivor memory unit Block.

      Fig. 4. Block Diagram of the Viterbi decoder.

      1. Branch Metric Unit

         At each time step, the soft decision Viterbi algorithm implementation requires 2(m+1) distance calculations and 2m comparison operations, where m is the number of memory elements in the convolutional encoder. Thus, for a K=7 Viterbi decoder where m = 6, the number of distance calculations and comparisons per stage corresponds to 27 and 26 respectively [7]. For a trace-back length T, the number of distance calculations and comparisons can be expressed as 2(m+1) T and 2m T, respectively. Also, each distance calculation requires n comparisons for a rate 1/n system. Hence the total number of additions (Ya) and comparison (Yc) operations required can be expressed as:

         = 2(+1)

         = 2()

      2. ACS Architecture Unit

         Area and power consumption affected by some elements such as the constraint length, code rate, ACS path metric register size, and architecture. To increase throughput, different access can be adopted including the use of multiple ACS units. One such realization for K=7 mix 64 ACS units. Further improvements can be achieved by mixing parallelism in the branch metric unit. The approach adopted here is to process 2 new path metrics in a single ACS unit handle all 64 states in the trellis. The survivor path memory shown in consists of a stack of registers which store the intermediate and final path metrics at every state of the trellis. The trace-back unit parses the data stored in the SPM unit and outputs the estimated survivor path with a latency of TBL. The control unit provides control signals and synchronization between ACS, SPM and trace-back units. As the path metric is the cumulative sum of branch metrics, it increases with each addition. To limit the dynamic range of path metrics and to circumvent the problem of overflow, a concept of saturation arithmetic has been adopted [7].

      3. Survivor memory unit:

      The final unit is the trace-back process method, where the survivor path and the output data are identified. The trace-back

      (TB) and the register-exchange (RE) methods are the two major techniques used for the path history management in the chip designs of Viterbi decoders. The TB method takes up less area but requires much more time as compared to RE method because it needs to search or trace the survivor path back sequentially. Also, extra hardware is required to reverse the decoded bits. The major disadvantage of the RE approach is that its routing cost is very high especially in the case of long- constraint lengths and it requires much more resources [10].

   7. RESULTS AND DISCUSSION

      1. Simulation and Synthesis Results

         The utilization of Viterbi decoder is individually described in hardware description language. Then employment verification of each of this circuit is carried out using industry standard ModelSim SE 6.4 simulator and ISE. Then circuit is synthesized using Xilinx Synthesis Tool (XST). The synthesis report provides detailed information about the device utilization and the delay summary for Viterbi decoder architecture. The different modules in the Viterbi decoding design are:

         • Data Generator.

         • Convolutional Encoder.

         • Pseudo Random Noise Source.

         • Decoder.

           Different modules of the Viterbi decoder designed by ISE Schematic tool as RT. From fig. 5, the simulation for convolution encoder gives significant results when input = 0101100111000111100000, the output =

           001110001001110001001001110110. Fig. 6 shows that the

           soft decision Viterbi decoder decodes the original data. Viterbi algorithm is conceived more interesting and challenging for this paper topic, it is considered, and also it has wide variety of applications in digital communications field. Considering the effect of noise supposes if the encoded data is corrupted then also decoder should be able to retrieve the original message sequence. It shown from fig. 7, that soft decision Viterbi decoder correct one error test this soft decision Viterbi when two error. Fig. 8, show a soft decision Viterbi decoder detect errors and correct two errors, test soft decision Viterbi decoder at encoded data is corrupted with three.

           Fig. 5. Snapshots from simulation for convolution encoder.

           Fig. 6. Output waveform of decoder without noise.

           Fig. 7. Output waveform of decoder with one error noise.

           Fig. 8. Output of decoder if the error has occurred in the first bit and the error in second bit.

           From comparison between two figures the decoder output is different from generated data .i.e. Soft decision Viterbi decoder detects errors and correct two errors checking the details of the design after implementing each and every action is necessary.

      2. Implementation Results

      All architectures were synthesized, placed and routed in a Virtex-6 FPGA with the highest speed grade (-2) using ISE12.1 from Xilinx. All implementations of the VD have constraint length 7 and output rate1/2. Snapshot from executing process is shown in fig. 9.

      Fig. 9. FPGA Implementation.

      It shown in table II that an area overhead reduction of 50% compared to Spartan 3E. In a Virtex-6 we can achieve 2014 LUTs in compared with Spartan 3E solutions, 3155 LUTs are achievable compared with Virtex_5 solutions and also Slice Registers occupies 1011, while 3214 in Spartan 3E then 69% are achievable in virtex_5 then Virtex_6 better than previous state-of the- art solutions in terms of area. The implemented Viterbi decoder was tested against an additive white Gaussian noise channel (AWGN) and consequently has gained more and more popularity in many applications. Frequency of 3-bit soft decision Viterbi decoder obtained is 66 MHz with delay of

      28.165 ns.

      TABLE II. FPGA DEVICE SUMMARY RESULTS

      Parameters	Virtex-6 FPGA XC6VLX240T (the proposed design)	Virtex_5	Spartan 3E
      Number of Slice Registers	1011 / 301440	4012/ 207360	3214/4656
      Number of used LUTs	2824 / 150720	207,360	4838/9312
      Minimum period	28.165ns	16.821 ns	6.9 ns
      Maximum Frequency	66 MHz	59.45MHz	144.34 MHz

   8. CONCLUSION

Viterbi decoding is the best technique for decoding the convolution codes. In this work, area has been achieved compared with previous work at same code rate, Viterbi decoders with constraint length 7 and code rate 1/2, have been successfully implemented on Virtex-6 FPGA XC6VLX240T device of Stratix IV family, and realized using ModelSim 6.4.Viterbi algorithm is employed in wireless communication to decode the Convolution codes; those codes are used in every strong digital communication systems. Such decoders are complex & dissipate large amount of power. We have implemented area optimized VLSI architecture of Convolution Encoder and Viterbi Decoder, Viterbi decoder allows safe data transmission via error correction and original message can be recovered accurately. This paper reduced the power and cost and at the same time increase in speed. Field Programmable Gate Array technology (FPGA) is considered a highly configurable option for implementing many progressing signal. Viterbi helps to generate more business by the contractor using Viterbi algorithm. Anyone reading this work will have to gain the knowledge of working with different tools like Xilinx ISE and Modelsim.

The highest frequency of clock obtained from the FPGA board used is 66 MHz, while the system can run on a higher frequency than that. Thus, In future, it should improve in a frequency to obtain higher clock frequency. The non-binary codes can be implemented in the future for the Viterbi decoder. Viterbi decoder is now being implemented in Xilinx in future it can also be implemented using JAVA. Viterbi decoder with Modified Register Exchange Method can be further investigated for higher constraint lengths and lower power

consumption than that of Viterbi decoder using register exchange method and trace back method.

REFERENCES

1. Soreng B. and kumar .S, Efficient Implementation of Convolution Encoder andViterbi Decoder , International Conference on Circuits, Power and Computing Technologies [ICCPCT-2013], 2013 .

2. Sonar N.S, Dr. Al-Naimy F. S and Dr. Mudholkar. R.R, An Improved Dynamically Reconfigurable Pipelined Adaptive Viterbi Decoder foHighThroughput International Journal of Engineering and Innovative Technology (IJEIT) Volume 2, Issue 7, January 2013

3. Kiran P. and Raju D. S, Implementation Of Hslp Viterbi Decoder Design For Tcm ecoders Global Journal of Advanced Engineering Technologies, Vol3, Issue1-2014.

4. Juan M Vilardy1, F. Giacometto, C. O. Torres and L. Mattos, " Design and implementation in VHDL code of the twodimensional fast Fourier transform for frequency filtering,convolution and correlation operations", Journal of Physics: Conference Series, vol. 274, No. 1, 2011,

5. Gribbon K.T, Bailey D.G and Smith A. B, Development Issues in Using FPGAs for Image Processing , Hamilton New Zealand, December 2007, pp. 217222, 2007.

6. Conmy P.M , Pygott C. and Bate, Vhdl Guidance For Safe And Certifiable FpgaDesign ,SSEI, Department of Computer Science, University of York, Heslington, U.K. Columbus Computing Ltd, Malvern, U.K., 2010.

7. Abdul-Shakoor.A.S and Szwarc.V, A High Performance Soft Decision Viterbi Decoder For Wlan And Broadband Applications, Communications Research Centre Canada 3701 Carling Avenue, Box 11490, Station H Ottawa, Ontario, K2H 8S2, 2006..

8. Hiral Pujara,and Pankaj Prajapati RTL Implementation of Viterbi Decoder using VHDL IOSR Journal of VLSI and Signal Processing (IOSR-JVSP) Volume 2, Issue 1, PP 65-71, 2013.

9. AjaySharma Design and Implementation of Viterbi Decoder using FPGAs,Electronics and Communication Engineering Department, Thapar university, patiala(Punjab)-147004(India), March,2008.

10. Suneha GuptaJuly, Design And Implementation Of an Optimized Viterbi Decoder, Department of Electronics and Communication Engineering THAPAR UNIVERSITY, PATIALA ,July 2012.

11. Bogdan, M. Munteanu, P. A. Ivey, N. L. Seed, and N. Powell Power Reduction Techniques for a Viterbi Decoder Implementation , Electronic Systems Group, University of Sheffield, Mappin Street, Sheffield S1 3EA, UK. 2000.

12. GOHEL. Pand DAVE K.C, Implementation Of Viterbi Decoder On Fpga To Improve Design, Proceedings of SARC-IRAJ International Conference, 14th, Delhi, India, ISBN: 978-93-82702-21- 4, July 2013.

13. K.Cholan, a, Design and Implementation of Low Power High SpeedViterbi Decoder, 1877-7058 © 2011 Publishedby Elsevier Ltd.,doi:10.1016/j.proeng.2012.01.834,2011.

14. Apurva Choubey, Review of Design of Viterbi Decoder on FPGA for Noisy Channel, International Journal of Scientific & Engineering Research, Volume 4, Issue 1 ISSN 2229-5518, 2013.