International Journal of Scientific & Engineering Research Volume 4, Issue 1, January-2013 1

ISSN 2229-5518

Apurva Choubey

1 NRI-Institute of Information Science & Technology, E.C.E Dept., Bhopal (M.P.), India

Email: apurva23choubey@gmail.com

Convolutional encoding with Viterbi decoding is a powerful method for forward error correction. It has been widely deployed in many wireless communication systems to improve the limited capacity of the communication channels. The Viterbi algorithm, which is the most extensively employed decoding algorithm for convolutional codes. The two decoding algorithms used for decoding the convolutional codes are Viterbi algorithm and Sequential algorithm. In register exchange (RE) method by using the pointer implementation the problem of survival memory management of a Viterbi Decoder was solved, in each row a pointer is assigned in the SMU .Instead of copy data of the first row to the second, than altered the content of the pointer from one row of memory to point to another row of memory. If the initial state of the convolutional encoder is known, the entire survivor memory unit (SMU) is reduced to only one row. Thus, the one-pointer architecture, referred to as memory less Viterbi Decoder (MLVD).

Key-Words: - Convolutional codes, Viterbi Algorithm, Adaptive Viterbi decoder, Path memory, Register

Exchange, Field-Programmable Gate Array (FPGA) implementation, memory less, wireless

Convolutional encoding is a forward error correction technique that is used for correction of errors at the receiver end. The two decoding algorithms used for decoding the convolutional codes are Viterbi algorithm and Sequential algorithm. Sequential decoding has advantage that it can perform very well with long constraint length. Viterbi decoding is the best technique for decoding the convolutional codes but it is limited to smaller constraint lengths. It has been widely deployed in many wireless communication systems to improve the limited capacity of the communication channels. The Viterbi algorithm is the most extensively

employed decoding algorithm for convolutional codes. The availability of wireless technology has revolutionized the way communication is done in our world today. With this increased availability comes increased dependence on the underlying systems to transmit information both quickly and accurately. Because the communications channels in wireless systems can be much more hostile than in “wired” systems, voice and data must use forward error correction coding to reduce the probability of channel effects corrupting the information being transmitted. A new type of coding, called Viterbi coding, can achieve a level of performance that comes closer to theoretical bounds than more

conventional coding systems.

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 4, Issue 1, January-2013 2

ISSN 2229-5518

The Viterbi Algorithm, an application of dynamic programming, is widely used for estimation and detection problems in digital communications and signal processing. It is used to detect signals in communications channels with memory, and to decode sequential error control codes that are used to enhance the performance of digital communication systems. Though various platforms can be used for realizing Viterbi Decoder including Field Programmable Gate Array (FPGAs), Complex Programmable Logic Devices (CPLDs) or Digital Signal Processing (DSP) chips but in this project benefit of using an FPGA to Implement Viterbi Decoding Algorithm has been described. FPGAs are a technology that gives the designer flexibility of a programmable solution, the performance of a custom solution and lowering overall cost. The advantages of the FPGA approach to DSP Implementation include higher sampling rates than are available from traditional DSP chips, lower costs than an ASIC. The FPGA also adds design flexibility and adaptability with optimal device utilization conserving both board space and system power that is often not the case with DSP chips.

The problem of survival memory management of a Viterbi Decoder (VD) was solved by introducing a pointer implementation for the register exchange (RE) method, where a pointer is assigned to each row of memory in the SMU. The content of the pointer which points to one row of memory is altered to point to another

row of memory, instead of copying the contents

of the first row to the second. In this paper, the one pointer VD is proposed; if the initial state of the convolutional encoder is known, the entire survivor memory unit (SMU) is reduced to only one row. Because the decoded data are generated in the required order, even this row of memory is dispensable. Thus, the one-pointer architecture, referred to as memory less Viterbi Decoder (MLVD), reduces the power consumption of a traditional trace back (TB) VD by approximately 50percent. A prototype of the MLVD with a one third convolutional code rate and a constraint length of nine is mapped into a Xilinx. In thesis The pointer to one row of memory simply carries the current state in the trellis of the VD. The pointer implementation avoids the power hungry register exchange operations of the traditional RE method, and is referred to as pointer Viterbi Decoder (PVD). In the next section the PVD is briefly reviewed, and then its memory less version is introduced.

An exhaustive literature review has been carried out related to the titled work to find out the current research. Abstracts of some of the most relevant research works are reported in the following paragraphs:

HEMA.S. et al [1] presented a field- programmable gate array implementation of

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 4, Issue 1, January-2013 3

ISSN 2229-5518

Viterbi Decoder with a constraint length of 11 and a code rate of 1/3. It shows that the larger the constraint length used in a Convolutional encoding process, the more powerful the code produced. A Viterbi algorithm based on the strongly connected trellis decoding of binary

A convolutional code has been presented.

Sriram Swaminathan, et al [2] describes the analysis and implementations of a reduced complexity decode approach, the adaptive Viterbi algorithm (AVA). Our AVA design is implemented in reconfigurable hardware to take full advantage of algorithm parallelism and specialization. Run-time dynamic reconfiguration is used in response to changing channel noise conditions to achieve improved decoder performance.

Shoban Mude et al [3] introduced Viterbi Algorithm is widely used for the elimination of the potential noise in a data stream. Encoding is such that the Viterbi Decoder can remove potential noise in the incoming stream by decoding it. The characteristics of the decoder are its effectiveness in noise elimination, speed of decoding and cost (hardware utilization).

Jingzhao Ou, et al [4] proposed State-of-the-art FPGAs integrate multi-million gate configurable logic and heterogeneous hardware components. They are also purposed an architecture for implementing Viterbi decoders on FPGAs. Our architecture can provide various throughput and energy trade-offs. Considering the

throughput/energy performance metric, experimental results show that our design achieves improvements up to 26.1% compared with the previous designs.

B. Pandita, et.al. [5] describes the design and implementation of Viterbi decoder using FPGAs.In this paper we explore an FPGA based implementation methodology for rapid prototyping designs. We use high level synthesis to achieve this. One of the main blocks of a CDMA modem used during forward-link demodulation is a Viterbi decoder.

Moorthy, H.T., et. al. [6] investigates trellis structures of linear block codes for the integrated circuit (IC) implementation of Viterbi decoders capable of achieving high decoding speed while satisfying a constraint on the structural complexity of the trellis in terms of the maximum number of states at any particular depth. Only uniform sectionalizations of the code trellis diagram are considered. An upper- bound on the number of parallel and structurally identical (or isomorphic) subtrellises in a proper trellis for a code without exceeding the maximum state complexity of the minimal trellis of the code is first derived

Yang min [7] proposed a novel Viterbi decoder in part parallel structure. The core part of the decoder-Add - Compare - Select Unit, is improved by means of pipeline. BMC (Branch Metric Computation) is improved through linear transform. TB (Trace Back) method is adopted

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 4, Issue 1, January-2013 4

ISSN 2229-5518

for survivor path. The whole decoder has the advantages of speed and resource expense compared with traditional hybrid Viterbi decoder.

Saleem, S. et.al [8] examined the Viterbi decoder is widely used in digital communication systems. It performs the maximum-likelihood decoding of Convolutional codes received from a noisy channel Depending on the application (terrestrial, satellite, digital modems, digital cellular telephone applications and others) a Viterbi decoder must be designed to meet specific requirements such as small area, high speed or maximum efficiency. They also present a novel architecture for area efficient Viterbi decoder, which can be used for low bit rate applications. The design schedules all computations on less number of ACS processing elements as compared to parallel implementation assuming that a lot of clock cycles are available for decoding.

Eleftheriou, E. et.al [9] Quaternary codes for improving the reliability of baseband data transmission over noisy partial-response channels are proposed. These codes offer the spectral shaping properties of line codes, i.e. they exhibit spectral nulls at the frequencies where the channel transfer function has zeros, together with a significant increase in minimum Euclidean distance between allowed channel output sequences. Simple encoders and decoders for selected quaternary codes with a spectral null at DC are given for the decode channel. The

receiver employs soft-decision maximum- likelihood sequence estimation on the combined channel and FSTD (finite-state transition diagram) trellis followed by block decoding. The code design avoids long runs of identical symbols and limits the path memory of the Viterbi detector by eliminating all undesired sequences. Simulation results on the performance of 5B4Q, 8B6Q, and 9B6Q codes and their power spectral density are presented.

Arun, C, et.al [10] proposed the use of error- correcting codes has proven to be an effective way to overcome data corruption in digital wireless communication channels, enabling reliable transmission to be achieved over noisy and fading channels. In this paper a novel approach to design a high throughput with reduced bit error probability Viterbi decoder is described and implemented. Low bit error rate (BER) can be achieved by increasing the free distance (dfree) of the Viterbi decoder without increasing complexity.

A FPGA based MLVD is proposed and implemented in this work .The MLVD is a memory less encoder and synchronizing the VD with the resetting procedure. The new implementation is known by applying the pointer concept to the RE implementation, and by reinforcing the initial state of the convolutional encoder every L bits encoded. The hardware and computational overhead of the

IJSER © 2013 http://www.ijser.org

International Journal of Scientific & Engineering Research Volume 4, Issue 1, January-2013 5

ISSN 2229-5518

new implementation is only a 256 to 1 decoder, which is switching at the data rate frequency. The new MLVD is a memory less high speed, low latency.

[1] HEMA.S, SURESH BABU.V, RAMESH P., “FPGA Implementation of Viterbi Decoder”, Proceedings of the 6th WSEAS Int. Conf. on Electronics, Hardware, Wireless and Optical Communications, Corfu Island, Greece, February 16-19, 2007.

[2] Sriram Swaminathan, Russell Tessier, Dennis Goeckel, and Wayne Burleson,” A Dynamically Reconfigurable Adaptive Viterbi Decoder Wayne Burleson, FPGA’02, February

24-26, 2002.

[3] Shoban Mude, S Nagakishore Bhavanam,” Design and Implementation of Viterbi Decoder Using FPGA”, Sep-Oct 2011 ISSN: 2249-6645

Vol.1, Issue.1, pp-07-14.

[4] Jingzhao Ou, Viktor K. Prasanna, “TIME AND ENERGY EFFICIENT VITERBI DECODING USING FPGAS” IEEE proceeding Vol.5, Issue.1, pp-33-36.

[5] B.Pandita,et. al, **“**Design and Implementation of Viterbi Decoder Using FPGAs**”, **Published in the Proceedings of the 12th International Conference on VLSI Design.

[6] Moorthy, H.T., et. al, “Good trellises for IC implementation of Viterbi decoders for linear block codes”,IEEE Trans. Communication, vol.45, pp. 50-67, 1997.

[7] Yang min,” Design optimization of FPGA based Viterbi decoder”, IEEE international conference, April- 2011 ISSN: 978-1-4244-8036

Vol.1, Issue.1, pp- 4129 - 4131.

[8] Saleem, S. et.al,” Design and Tradeoff Analysis of an Area Efficient Viterbi Decoder”, IEEE international conference, march- 2007, ISSN: 0-7803-9429-1 Vol.1, Issue.1, pp-1-5.

[9] Eleftheriou, E., Cideciyan, R.,” Quaternary codes for partial-response channels”, IEEE Global international conference, August -2002

ISSN: 0-87942-632-2 Vol.3, Issue.1, pp-1673 -

1678

[10] Arun, C, et.al, ” Design and VLSI implementation of a Low Probability of Error Viterbi Decoder”, IEEE international conference, july-2008 ISSN: 978-0-7695-3267-

7 Vol.3, Issue.1, pp- 418 - 423

IJSER © 2013 http://www.ijser.org