A forward error correction technique known as convolutional coding with Viterbi decoding was explored in this final thesis. This Viterbi project is part of the baseband Error control project at electrical engineering department, Linköping University. In this project, the basic Viterbi decoder behavior model was built and simulated. The convolutional encoder, puncturing, 3 bit soft decision, BPSK and AWGN channel were implemented in MATLAB code. The BER was tested to evaluate the decoding performance. The main issue of this thesis is to implement the RTL level model of Viterbi decoder. With the testing results of behavior model, with minimizing the data path, register size and butterflies in the design, we try to achieve a low silicon cost design. The RTL Viterbi decoder model includes the Branch Metric block, the Add-Compare-Select block, the trace-back block, the decoding block and next state block. With all done, we further understand about the Viterbi decoding algorithm and the DSP implementation methods.

We address the problem of multi-view multi-target tracking using multiple stationary cameras in the application of hockey tracking and test the approach with data from two cameras. The system is based on the previous work by Okuma et al. [50]. We replace AdaBoost detection with blob detection in both image coordinate systems after background subtraction. The sets of blob-detection results are then mapped to the rink coordinate system using a homography transformation. These observations are further merged into the final detection result which will be incorporated into the particle filter. In addition, we extend the particle filter to use multiple observation models, each corresponding to a view. An observation likelihood and a reference color model are also maintained for each player in each view and are updated only when the player is not occluded in that view. As a result of the expanded coverage range and multiple perspectives in the multi-view tracking, even when the target is occluded in one view, it still can be tracked as long as it is visible from another view. The multi-view tracking data are further processed by trajectory smoothing using the Maximum a posteriori smoother. Finally, automatic camera selection is performed using the Hidden Markov Model to create personalized video programs. / Science, Faculty of / Computer Science, Department of / Graduate

Convolutinal coding is a coding scheme often employed in deep space communications and recently in digital wireless communications. Viterbi decoders are used to decode convolutional codes. Viterbi decoders employed in digital wireless communications are complex and dissipate large power. With the proliferation of battery powered devices such as cellular phones and laptop computers, power dissipation, along with speed and area, is a major concern in VLSI design. In this thesis, we investigated a low-power design of Viterbi decoders for wireless communications applications. In CMOS technology the major source of power dissipation is attributed to dynamic power dissipation, which is due to the switching of signal values. The focus of our research in the low-power design of Viterbi decoders is reduction of dynamic power dissipation at logic level in the standard cell design environment. We considered two methods, clock-gating and toggle-filtering, in our design. A Viterbi decoder consists of five blocks. The clock-gating was applied to the survivor path storage block and the toggle-filtering to the trace-back block of a Viterbi decoder. We followed the standard cell design approach to implement the design. The behavior of a Viterbi decoder was described in VHDL, and then the VHDL description was modified to embed the low-power design. A gate level circuit was obtained from the behavioral description through logic synthesis, and a full scan design was incorporated into the gate level circuit to ease testing. The gate level circuit was placed and routed to generate a layout of the design. Our experimental result shows the proposed design reduces the power dissipation of a Viterbi decoder by about 42 percent compared with the on without considering the low-power design. / Master of Science

In this work, a new method of approximating the Maximum-likelihood estimate has been presented. The method consists of first using the Viterbi algorithm to estimate the log likelihood of the state, and then approximating that log likelihood to keep the computational complexity down. Various methods for approximating the log likelihood are introduced, most of these using linear regression and feature vectors. The methods were compared to a Kalman filter or Extended Kalman filter (depending on wether the system was linear or nonlinear) as well as a Particle filter modified to return a maximum likelihood estimate. Two systems were used for testing, one very simple linear system as well as a complex nonlinear system. Both of these were 1-dimensional. When applied to the simple system, the presented method outperformed both the Kalman filter and the Particle filter. While many approximation methods gave a good results the best one was using a cubic spline. For the more complex system, the method presented here could not outperform the particle filter. The most promising approximation method for this system was a Chebyshev approximation.

No description available.

In this thesis, the VLSI implementation of Viterbi decoder using a design and simulation platform called SystemC is studied. For this purpose, the architecture of Viterbi decoder is tried to be optimized for VLSI implementations. Consequently, two novel area efficient structures for reconfigurable Viterbi decoders have been suggested. The traditional and SystemC design cycles are compared to show the advantages of SystemC, and the C++ platforms supporting SystemC are listed, installation issues and examples are discussed. The Viterbi decoder is widely used to estimate the message encoded by Convolutional encoder. For the implementations in the literature, it can be found that special structures called trellis have been formed to decrease the complexity and the area. In this thesis, two new area efficient reconfigurable Viterbi decoder approaches are suggested depending on the rearrangement of the states of the trellis structures to eliminate the switching and memory addressing complexity. The first suggested architecture based on reconfigurable Viterbi decoder reduces switching and memory addressing complexity. In the architectures, the states are reorganized and the trellis structures are realized by the usage of the same structures in subsequent instances. As the result, the area is minimized and power consumption is reduced. Since the addressing complexity is reduced, the speed is expected to increase. The second area efficient Viterbi decoder is an improved version of the first one and has the ability to configure the parameters of constraint length, code rate, transition probabilities, trace-back depth and generator polynomials.

Σκοπός της παρούσας διπλωματικής εργασίας είναι η μελέτη και ο σχεδιασμός VLSI επεξεργαστών για τη διόρθωση λαθών. Η κατηγορία των VLSI επεξεργαστών στην οποία εστιάζει η έρευνά μου είναι ο αποκωδικοποιητής Viterbi. Αρχικά, παρουσιάζεται η δομή του ψηφιακού τηλεπικοινωνιακού συστήματος και κάποιες βασικές έννοιες των κωδικών διόρθωσης λαθών. Έπειτα, αναλύονται οι Συνελικτικοί κωδικοποιητές, ανάμεσα στους οποίους περιλαμβάνεται ο Συνελικτικός κωδικοποιητής που χρησιμοποιείται στην εργασία μου και ο οποίος χρησιμοποιείται ευρέως στο πρότυπο Wifi 802.11a. Ακολούθως, γίνεται αναφορά στο κανάλι AWGN και στη διαμόρφωση BPSK. Ακόμα, παρουσιάζονται οι βασικές έννοιες του αλγόριθμου Viterbi, η λειτουργία του, η δομή του καθώς και οι εφαρμογές του. Στη συνέχεια, μελετώνται διάφορες αρχιτεκτονικές του αποκωδικοποιητή Viterbi σε VLSI. Με βάση τον τρόπο υλοποίησης αριθμητικών πράξεων, οι αρχιτεκτονικές που αναπτύσσονται είναι ο Radix-2 και ο Radix-4 Viterbi, ενώ με βάση τον τρόπο αποκωδικοποίησης αναπτύσσονται οι αρχιτεκτονικές του Viterbi για συνεχή αποκωδικοποίηση-εφαρμογές streaming και του Viterbi για αποκωδικοποίηση πακέτων των 20 bits. Επίσης, μελετάται η απόδοση των αρχιτεκτονικών αυτών με κριτήριο τη συχνότητα λαθών που πραγματοποιούνται (Bit Error Rate – BER) και αναλύεται η υλοποίηση των αρχιτεκτονικών αυτών στο αναπτυξιακό σύστημα Xilinx. Τέλος, προκύπτουν τα κατάλληλα συμπεράσματα. / The purpose of this diploma thesis is to study and implement VLSI processors for correcting errors. The category of VLSI processor which will focus in this work is the Viterbi decoder. Initially, the structure of the digital telecommunications system is presented along with some basic concepts of error correcting codes. Then we explain the theory behind convolutional encoders and we describe the convolutional encoder that is used in my work and is consistent in the Wifi 802.11a standard. Next we analyze briefly the AWGN channel and the BPSJ modulation. Also the basic concepts of the Viterbi algorithm, how it works, its structure and the different applications are given. For the practical part which is the main part of this project, is to study the different architectures of the Viterbi decoder in VLSI approach. The main architectures that were developed for the implementation arithmetic operations is Radix-2 and Radix-4 Viterbi, but in terms of decoding two more architectures were developed, Viterbi continuous decoding-streaming applications and Viterbi decoding for packets of 20 bits. Then, the performance of these architectures in terms of frequency of errors made (BER) was investigated and also the implementation of these architectures in the development system Xilinx was analyzed. At the end we give our conclusion regarding the results of the different simulations that we’ve done.

International Telemetering Conference Proceedings / October 26-29, 1992 / Town and Country Hotel and Convention Center, San Diego, California / In the event of a NASA Space Shuttle mission landing at the While Sands Missile Range, White Sands, New Mexico, a data communications system for processing Shuttle’s telemetry data has been installed there in the Master Control Telemetry Station, JIG-56. This data system required a Viterbi decoder since the Shuttle’s data is convolutionally encoded. However, the Shuttle uses a nonstandard code, and the manufacturer which in the past has provided decoders for Shuttle support, no longer produces them. Since no other company produced a Viterbi decoder designed to decode the shuttle’s data, it was necessary to develop the required decoder. The purpose of this paper is to describe the functional performance requirements and design of this decoder.

In wireless communication systems, we may encounter many problems. One of the main issues is noise interference. To overcome the problem, the sender can use the Convolutional coding method to encode the data, and the receiver can utilize the Viterbi algorithm for decoding and correction purposes. Due to the high complexity of the Viterbi algorithm, the VLSI structure of Viterbi decoder will consume large amounts of power, leading the portable devices to short standby time and high operating temperature. In order to solve these problems we have to design a low power decoder. As a matter of fact, the Viterbi decoder can be actually shutdown when no noise interference exists. As a consequence, we use a detection circuit to determine whether the signal is influenced by noise. If the signal is interfered, we choose the Viterbi decoder to perform the decoding process. Otherwise, we utilize a low cost decoder to lessen the power consumed at the receiver end. In addition, dynamic adjustment of SMU module is also developed and implemented in the proposed decoder. SMU module consumes the most power in Viterbi decoder. So, our developed and goal is to reduce the usage of SMU module. If noise distribution is not so dense, we don¡¦t have to use high decoding ability to decode section data. Therefore, the registers in SMU can be decreased. Clock gating technique is adopted in this thesis to shutdown these idle registers to reduce the power consumption of SMU. The proposed decoder has been implemented and synthesized using the Artisan TSMC 0.13£gm standard cell library. Compared with the traditional Viterbi decoder, the proposed decoder can achieve 25% and nearly 60% power saving when the SNR is 1dB and 8dB respectively, with 6% area reduction. According to the above experimental results, we can say that the proposed decoder is able to reduce power consumption.

In wireless communication system, convolutional coding method is often used to encode the data. In decoding convolutional code (CC), Viterbi algorithm is considered to be the best mechanism. Viterbi decoder (VD) was developed to execute the algorithm on mobile devices more effectively. This decoder is often used on 2G and 3G mobile phones. However, on 2G phones, VD consumes about one third of total power consumption of the signal receiver. Therefore it is very necessary to reduce the power consumption of VD on 2G and 3G phones. VD uses large amount of register in survivor metric unit (SMU), so that the decoder can receive enough CC and converge automatically. The goal of this thesis is to decrease power consumption of SMU by using path metric compare unit (PMCU) to find the best state of path metric unit (PMU). This way decreases half of registers and multiplexers required in SMU, leading to significant area reduction in decoder. During the process of signal transmission in wireless communication, different causes like the atmosphere, outer space radiation and man-made will interfere the signal by different degree. The stronger the noise is, the more interference CC will get. The error detection circuit used will mark the sections with noise interference before the CC enters the VD. If CC is interfered, it will be decoded by the whole VD. Otherwise, it will be decoded by low power decoder, where the controller will start clock gating mechanism on SMU to close up unnecessary power consumption block. The power consumption of is varying proposed Adaptive Viterbi decoder according to the interference degree. When interference degree is high, the power consumption is 21% less than conventional VD; when interference is low, it is 44% less. The results show that the proposed method can effectively reduce the power consumption of VD.