ISSN ONLINE(2319-8753)PRINT(2347-6710)

Implementation of Adaptive Viterbi Decoder on FPGA for Wireless Communication

Parameshwara R 1, Ganesh V.N 2
  1. P.G. Student, Dept.of ECE, MITE College (Affiliated to VTU, Belagavi), Moodbidri, Karnataka, India
  2. Sr.Assistant Professor, Dept.of ECE, MITE College (Affiliated to VTU, Belagavi), Moodbidri, Karnataka, India
Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Innovative Research in Science, Engineering and Technology

Abstract

A new trend in wireless communication systems has dictated the need for dynamical adaptation of communication systems in order to suit environmental requirements. Wireless networks usually employ sophisticated Forward Error Correction (FEC) techniques such as Viterbi Algorithm to combat with the channel distortion effects such as multipath fading and intersymbol interference. Viterbi algorithm is employed in wireless communication to decode the Convolution codes; these are the class of FEC codes. Such decoders are complex & dissipates large amount of power. Thus this paper presents the design of an Adaptive Viterbi Decoder (AVD) that uses survivor path with parameters in an attempt to reduce the power and cost and at the same time increase in speed. Most of the researches aimed to reduce power consumption or work with high frequency for using the decoder in the modern applications such as 3 GPP, DVB, and wireless technology. Field Programmable Gate Array technology (FPGA) is considered as highly configurable option for implementing many sophisticated signal processing tasks. The proposed viterbi decoder design is simulated on Modelsim.SE6.3f and implemented using VHDL code.

Keywords

Viterbi Algorithm, Adaptive Viterbi Decoder, Field Programmable Gate Array, VHDL.

INTRODUCTION

Most digital communication systems nowadays convolutionally encoded the transmitted data to compensate for Additive White Gaussian Noise (AWGN), fading of the channel, quantization distortions and other data degradation effects. For its efficiency to improve the Viterbi algorithm has proven to be a very practical algorithm for forward error correction of convolutionally encoded messages. The prerequisites for the Viterbi decoder or Viterbi detector depend on the applications used. Recently, most of the researches work to reduce the cost, power consumption, or work with high frequency for using the decoder in the modern applications such as 3GPP, DVB, and Wireless communications. Some of the research on comparing between using FPGA, Application Specific Integrated Circuit (ASIC), and Digital Signal Processing (DSP) to find which one is suitable for the given applications. Other studies related to the differences method for back trace unit to find the correct path, and some trying to work with high frequency by using parallel operations of decoder units. The complexity of these decoders increased with the increase in the constraint length. Thus, we attempted to design an adaptive Viterbi decoder that intern uses survivor path storage with parameters for wireless communication and also to implement the decoder using Modelsim SE6.3f modeling tool and evaluated the decoder for timing accuracy and resource utilization.VHDL stands for VHSIC Hardware description language. VHSIC is an abbreviation for very high speed integrated Circuit. In 1981, this language was first introduced for the Department of Defence (DoD) under the VHSIC program. IBM, Texas instruments and intermetrics started to develop this language in 1983. In 1987 IEEE standardized the language. VHDL describes the behavior of an electronic circuit or a system from which the physical circuit or system can then be implemented. Where, it is intended for circuit synthesis as well as circuit simulation. VHDL is also a programming language that allows modeling and developing complex digital system in dynamic environment by dataflow, behavioral and structural style of modeling. The behavior of field programmable gate arrays can be illustrated by this language.

RELATED WORK

The Viterbi decoding algorithm was discovered and analysed by Andrew J Viterbi in 1967. A high performance “Generic Viterbi decoder” is prototyped on an FPGA board. The presented Decoder was intended to be used in a complete wireless LAN transceiver prototype. The generosity of the design facilitated not only the prototyping of Viterbi decoders with different specifications also tuning some of the parameters of the decoder to optimum for the given communication system constraints [2]. “Implementation of Viterbi Decoder on FPGA” with a constraint length of 11 and a code rate of 1/3. It showed that as larger the constraint length used in the convolutional encoding process, more powerful code can be produced [3]. “Low-Power Viterbi Decoder for Software-Defined WiMAX Receiver” described the effective insertion of FPGAs in Software Defined Radio. The designed adaptive Viterbi decoder for WiMAX benefited from the concept of trace back with clock gating for power reduction [4]. The “Asynchronous Viterbi Decoder in Action Systems” the purpose was to develop a formal power estimation flow, which can be used to monitor the power consumption from abstract level to the gate level implementation of the digital system. The formal model can be used as a case study for the power consumption of different models [5].VLSI Architecture for Adaptive Viterbi Decoder” by describing Through the reformulation of the Adaptive Viterbi Algorithm, the compare operation for threshold selection in Add Compare Select (ACS) unit was simplified from variable based to constant based and the width of path metric was reduced[6]. The “A Dynamically Reconfigurable Adaptive Viterbi Decoder” To take the full advantage of AVD algorithm’s parallelism and specialization. Run-time dynamic reconfiguration is used in response to changing the channel noise conditions to achieve improved decoder performance [7]. “Survivor Path Processing in Viterbi Decoders” presented a new class of hybrid survivor path architecture based on Register exchange and Trace back concepts. This architecture is not bound to a specialized memory implementation and can thus be optimized for different platforms [8].

CONVOLUTIONAL CODES

A Convolutional code is described by three integers, n, k, K.
image
The k bit input is fed to the constraint length K shift register and the n outputs are calculated from the generator polynomials by the modulo-2 addition. Where the ratio k/n denotes the code rate. The generator polynomial specifies the connections of the encoder to the modulo-2 adder. convolutional encoding procedure is not only a function of an input k-tuple, but is also a function of the previous K-1 tuples. In practice, n and k are small integers and K is varied to control capability and complexity of the code.They operates on data stream, not static block. The Figure (a) below illustrates a simple Convolution encoder.
image

VITERBI ALGORITHM

The Viterbi decoding algorithm was discovered and analyzed by Viterbi in 1967.The Viterbi algorithm essentially performs maximum likelihood decoding; even, it reduces the computational load by taking advantage of the special structure in the code trellis. The viterbi algorithm involves calculating a measure of similarity, or distance, between the received signal and all the trellis paths entering each state at time ti. This algorithm removes from consideration those trellis paths that could not possibly be candidates for the maximum likelihood choice. the path called surviving path is When two paths enter the same state, the one having the best metric is to be chosen. for all the states This selection of surviving paths is performed . The decoder continues in this way to advance deeper into the trellis by making decisions to eliminate the least likely paths. The early rejection of the unlikely paths reduces the decoding complexity. The algorithm can be broken down into the following three steps;
a. Weight the trellis; that is, the branch metric to be calculated.
b. In this step the decisions are used to recursively updating the survivor path of the signal in terms of shortest paths to time n in terms of n-1. This is known as add-compare-select (ACS) recursion.
c. Using the decisions from Step 2, it Recursively finds the shortest path leading to each trellis state. The shortest path is called the survivor path for that state and the process is referred to as survivor path decode.
Finally, if all survivor paths are traced back in time, they merge into a unique path, which is the most likely signal path.

ARCHITECTURE OF VITERBI DECODER

The input to our proposed design is an identified code symbols and frames, i.e. the design decodes successive bit.
image
Figure (b): Basic building blocks of the Viterbi decoder
The basic performance of the Viterbi decoder is analyzed with the block diagram shown below. It consists of three main blocks:
1. Branch Metric calculation
2. Path Metric Calculation
3. Survivor Management Unit
1. The Branch Metric Calculation (BMC)
This is typically based on a look-up table containing the various bit metrics. The computer looks up the n-bit metrics associated with each branch and sums them to obtain the branch metric. The result is passed along to the path metric Calculation. The responsibility of this unit is to compute the Hamming code between the expected code and the receiving code as a frame. At each processing, the BMU finds the Hamming code for these symbols.
2. Path Metric Calculation
There are Path Metric Unit (PMU) and Add Compare Select Unit (ACSU) blocks in it.
a. Path Metric Unit (PMU)
It computes the partial path metrics at each node in the trellis.
b. Add Compare Select Unit (ACSU)
The add compare select unit is the main unit of the survivor path decoder. this unit finds the addition of the Hamming code received from BMU's and to compare the total hamming code. This takes the branch metrics computed by the BMC and computes the partial path metrics at each node in the trellis. The surviving path at each node is identified, and accordingly notifies the information-sequence updating and storage unit. Since the entire trellis is multiple images of the same simple element, a single circuit called ACS may be assigned to each trellis state.
3. Survivor Management Unit (SMU)
This unit is responsible for keeping track of the information bits associated with the surviving paths designated by the path metric Calculation. There are two basic design approaches: Register Exchange and Trace Back. In both techniques, a shift register is associated with every trellis node throughout the decoding operation. Since one of the major interests is the low power design, the proposed decoder has been implemented using the trace back approach which dissipates less power. The major disadvantage of the register exchange approach is that its routing cost is very high especially in the case of long-constraint lengths and it requires much more resources.

MODIFIED ARCHITECTURE OF ADAPTIVE VITERBI DECODER

The main aim of the adaptive Viterbi Decoder is to reduce the average computation and path storage required by the Viterbi algorithm. Instead of computing and retaining all 2K-1 possible paths, for each received symbol at each state node only those paths which satisfy certain cost conditions are retained. Path retention is based on the following criteria. A threshold T indicates that a path is retained if its path cost is less than dm + T, where dm is the minimum cost among all surviving paths in the previous trellis stage.
image
Figure (c): Block diagram of adaptive Viterbi decoder.

FLOWCHART OF VITERBI DECODING ALGORITHM

Figure (d) shows the flowchart of Adaptive Viterbi Decoding Algorithm. As seen in Viterbi decoding algorithm, it can choose the best path or shortest path in terms of hamming distance at the end of trellis or decoded bits. This leads to an extra computations and processing delay. Decision unit (ACS) is the advantage and the bottle neck of this design. As seen in modified Viterbi algorithm, it can choose the survivor path. Decision unit takes care of these parameters by choosing the correct path by using the next received symbol.
image
Figure (d): Viterbi Decoding Flowchart.

SIMULATION RESULTS

Figure (e) shows the Viterbi Algorithm diagram and Figure (f) shows the simulation result of Adaptive Viterbi Decoder using ModelsimSE6.3F.
image
Figure (e): Viterbi algorithm
image
Figure (f) : Simulation result of Adaptive Viterbi Diagram

APPLICATIONS

• Radio communication: Digital TV (ATSC,QAM,DVB-T, etc..), Radio relay, Satellite communications,PSK31 Digital mode for Amateur radio.
• Decoding trellis-coded modulation (TCM), the technique used in telephone-line modems to squeeze high spectral efficiency out of 3 kHz-bandwidth analog telephone lines.
• Computer storage devices such as hard disk drives.
• Automatic speech recognition.
• Pipelined VLSI Architecture of the Viterbi Decoder for IMT-2000.
• 200Mbps Viterbi Decoder for UWB.

CONCLUSION

As mobile and wireless communication becomes increasingly omnipresent, the need for dynamic reconfigure ability of hardware shall pose fundamental challenges for communication algorithm designers as well as hardware architectures. This paper attempts to solve this problem for the Particular case of the Viterbi decoder, which is a critical component at a physical layer of most wireless communication systems. Important conclusion drawn from the work is Reconfigure the Viterbi decoder, and adaptive Viterbi decoder units will give simple elements in each unit and new algorithms. The processing execution time has been reduced by removing the trace back algorithms that is used to find the correct paths. The survivor path algorithm used the address of the memory unit to select the correct path which specifies the output code.

References

[1] Prof. Siddeeq Y. Ameen , Mohammed H. Al-Jammas and Ahmed S. Alenezi,” FPGA Implementation of Modified Architecture for Adaptive Viterbi Decoder” IEEE,2011.

[2] Obeid A. M., Ortiz A. G., Ludewig R., and Glenser M., "Prototype of a high performance generic Viterbi decoder", Proceedings. 13th IEEE International Workshop on Rapid System Prototyping I2002.

[3] Hema.S, Suresh and B.V, Ramesh, “FPGA implementation of Viterbi decoder”, Proceedings of the 6th WSEAS Int. Conf. Electronics,Hardware, Wireless and Optical Communications, Corfu Island, Greece, February 16-19,2007.

[4] S. W. Shaker, S. H. Alramely and K. A. Shehata, “Design andimplementation of low-power Viterbi decoder for software-defined WiMAX receiver”, 17th Telecommunication Forum TELFOR, Serbia, Belgrade, 2009.

[5] J. Tuominen and J. Plosila., "Asynchronous Viterbi decoder in action systems", 23rd NORCHIP Conference, 2005.

[6] Y. Gong, T. Arslan, and A. Erdogan, "An efficient reformulationsbased VLSI architecture for adaptive Viterbi decoding in wireless applications", PhD thesis, Electrical Engineering, Edinburgh University,July 2004.

[7] S. Swaminathan, R. Tressier, D. Goeckel., and W. Burleson, "A dynamically reconfigurable adaptive Viterbi decoder", IEEE Transactions on Very Large scale Integration (VLSI) Systems, Vol. 13, No. 4, pp. 484-488 , April 2005.

[8] M. Kamuf, V. Öwall and J. B. Anderson “Survivor Path Processing inViterbi Decoders Using Register Exchange and Traceforward” IEEE Transaction on circuit and systems, Vol. 54, No. 6, June 2007.

[9] Bernard Sklar, Digital Communications Fundamentals and Application, Published by Pearson education, Year 2003.

[10] J. S, Reeve., and K. Amarasinghe "A parallel Viterbi decoder for block cyclic and convolutional codes", Journal of Signal Processing, vol. 86page 278, 2006.

[11] M. Kamuf, V. Öwall and J. B. Anderson “Survivor Path Processing inViterbi Decoders Using Register Exchange and Traceforward” IEEE Transaction on circuit and systems, Vol. 54, No. 6, June 2007.

[12] Y. Tang, , D. Hu, , W. Wei,, W. Lin and H. Lin “A Memory-EfficientArchitecture for Low Latency Viterbi Decoders” International Symposium on VLSI design, Automation and Test, VLSI-DAT09, Hsinchu, July, 2009.