Parallel Viterbi algorithm implementation: breaking theACS-bottleneck

The central unit of a Viterbi decoder is a data-dependent feedback loop which performs an add-compare-select (ACS) operation. This nonlinear recursion is the only bottleneck for a high-speed parallel implementation. A linear scale solution (architecture) is presented which allows the implementation of the Viterbi algorithm (VA) despite the fact that it contains a data-dependent decision feedback loop. For a fixed processing speed it allows a linear speedup in the throughput rate by a linear increase in hardware complexity. A systolic array implementation is discussed for the add-compare-select unit of the VA. The implementation of the survivor memory is considered. The method for implementing the algorithm is based on its underlying finite state feature. Thus, it is possible to transfer this method to other types of algorithms which contain a data-dependent feedback loop and have a finite state property     

Iterative Viterbi algorithm for concatenated multidimensional TCM

A novel compound code is designed for the multidimensional (M-D) Wei (1987) trellis code combined with a simple parity-check code. Using the iterative Viterbi decoding algorithm, we can achieve a remarkable performance improvement with low computational complexity. Simulation results show that at a bit error rate (BER) of 3.7 × 10^-6 about 2.2-dB additional net gain has been obtained over the conventional scheme of the 4-D 16-state Wei code at a spectral efficiency of 6.7871 bit/T     

The CPLD implementation of Viterbi algorithm in grand alliance ATSCsystems

Digital television has become one of the most promising industries. The advanced television system is scheduled to totally replace the current television broadcasting system in the US. In this paper, we present the implementation and discussion of the trellis en/decoder in the grand alliance digital television system proposed by the Advanced Television System Committee (ATSC). In the paper, we use a relatively efficient way to realize the en/decoding circuit. The correctness of our design has also been demonstrated     

A burst-error-correcting Viterbi algorithm

A dual-mode burst-error-correcting algorithm that combines maximum-likelihood decoding with a burst detection scheme is presented. The decoder nominally operates as a Viterbi decoder and switches to time diversity error recovery whenever an uncorrectable error pattern is identified. It is demonstrated that the new scheme outperforms interleaving strategies under the constraint of a fixed overall decoding delay. It also proves to be more powerful than known adaptive burst decoding schemes, such as the Gallager burst finding scheme. As the new method can be used with soft decision decoding, it is mainly intended for use on random-error channels affected by occasional severe bursts     

Implementing the Viterbi algorithm

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 communication channels with memory, and to decode sequential error-control codes that are used to enhance the performance of digital communication systems. The Viterbi algorithm is also used in speech and character recognition tasks where the speech signals or characters are modeled by hidden Markov models. The article explains the basics of the Viterbi algorithm as applied to systems in digital communication systems, and speech and character recognition. It also focuses on the operations and the practical memory requirements to implement the Viterbi algorithm in real-time     

High-speed parallel Viterbi decoding: algorithm andVLSI-architecture

The Viterbi algorithm (VA) is considered as an example of a fairly complex algorithm that needs to be implemented for high-speed applications. A brief introduction to the algorithm is given, and the state of the art of high-speed Viterbi decoders is reviewed. The three principal levels of introducing additional parallelism into an algorithm-bit level, word level, and algorithm level-are outlined, and a solution for the VA at the bit level is indicated     

联合判决估计的Viterbi译码算法

利用相邻几组判决数据之间的相互关系，对这几组数据进行联合判决估计，从而提两了Viterbi译码性能。从理论分析和仿真结果来看，当译码深度τ=2m左右时，译码性能相当于深度2τ传统算法的性能。此外，仿真表明参考状态的位置对性能影响不大。因此该算法在保证同等性能前提下，对留选路径存储的规模和功耗减少约20％，对回溯单元减少达30％。     

On the Viterbi decoding algorithm

A new interpretation of the Viterbi decoding algorithm based on the state-space approach to dyamical systems is presented. In this interpretation the optimum decoder solves a generalized regulator control problem by dynamic programming techniques.     

一种维特比译码器的矩阵实现方案

本文针对(2,1,l)卷积码提出一种维特比矩阵译码算法,通过引入整形、合并和动态选择等辅助模块,实现了所有环节的矩阵处理,构建出具有单一结构的并行译码器。由于只需要更改一部分模块的内部参数便可获得不同卷积码译码器,因此非常有利于分析和设计。仿真实验表明,在运算量更少的情况下,矩阵译码器可以取得接近最优的译码性能。     

The Viterbi algorithm for sparse channels

This paper presents a reduced complexity Viterbi algorithm for use as sequence estimator for linear intersymbol interference channels with coarsely located coefficients. In particular, the complexity does not depend on the channel impulse response length but only on the number of nonzero coefficients. No approximations are used in the algorithm. We consider a multipath environment producing time spreads     

Novel Viterbi decoder VLSI implementation and its performance

An advanced, high-speed, and universal-coding-rate Viterbi decoder VLSI implementation is presented. Two novel circuit design schemes have been proposed: scarce state transition (SST) decoding and direct high-coding-rate convolutional code generation and variable-rate decoding. SST makes it possible to omit the final decision circuit and to reduce the required path memory length without degrading error probability performance. Moreover, the power consumption of the SST Viterbi decoder is significantly reduced when implemented as a CMOS device. These features overcome the speed limits of high-speed and high-coding-gain Viterbi decoder VLSIs in the rate one-half mode imposed by the thermal limitation. The other Viterbi decoding scheme makes it possible to realize a simple and variable coding-rate forward-error-correction circuit by changing only the branch metric calculation ROM tables. By employing these schemes, high-speed (25-Mb/s) and universal-coding-rate Viterbi decoder VLSIs have been developed     

High-performance VLSI architecture for the Viterbi algorithm

The Viterbi (1967) algorithm (VA) is known to be an efficient method for the realization of maximum-likelihood (ML) decoding of convolutional codes. The VA is characterized by a graph, called a trellis, which defines the transitions between states. To define an area efficient architecture for the VA is equivalent to obtaining an efficient mapping of the trellis. We present a methodology that permits the efficient hardware mapping of the VA onto a processor network of arbitrary size. This formal model is employed for the partitioning of the computations among an arbitrary number of processors in such a way that the data are recirculated, optimizing the use of the PEs and the communications. Therefore, the algorithm is mapped onto a column of processing elements and an optimal design solution is obtained for a particular set of area and/or speed constraints. Furthermore, the management of the surviving path memory for its mapping and distribution among the processors was studied. As a result, we obtain a regular and modular design appropriate for its VLSI implementation in which the only necessary communications between processors are the data recirculations between stages     

A new transform algorithm for Viterbi decoding

Implementation of the Viterbi decoding algorithm has attracted a great deal of interest in many applications, but the excessive hardware/time consumption caused by the dynamic and backtracking decoding procedures make it difficult to design efficient VLSI circuits for practical applications. A transform algorithm for maximum-likelihood decoding is derived from trellis coding and Viterbi decoding processes. Dynamic trellis search operations are paralleled and well formulated into a set of simple matrix operations referred to as the Viterbi transform (VT). Based on the VT, the excessive memory accesses and complicated data transfer scheme demanded by the trellis search are eliminated. Efficient VLSI array implementations of the VT have been developed. Long constraint length codes can be decoded by combining the processors as the building blocks     

Systolic array processing of the Viterbi algorithm

Results on efficient forms of decoding convolutional codes based on the Viterbi algorithm by using systolic arrays are presented. Various properties of convolutional codes are discussed. A technique called strongly connected trellis decoding is introduced to increase the efficient utilization of all the systolic array processors. Issues dealing with the composite branch metric generation, survivor updating, overall system architecture, throughput rate, and computational overhead ratio are also investigated. The scheme is applicable to both hard and soft decoding of any rate b/n convolutional code. It is shown that as the length of the code becomes large, the systolic Viterbi decoder maintains a regular and general interconnection structure as well as moderate throughput rate gain over the sequential Viterbi decoder     

A personal history of the Viterbi algorithm

This paper describes how Andrew J. Viterbi developed a non-sequential decoding algorithm which proved useful in showing the superiority of convolutional codes over block codes for a given degree of decoding complexity. The Viterbi algorithm is now used in most digital cellular phones and digital satellite receivers as well as in such diverse fields as magnetic recoding, voice recognition, and DNA sequence analysis.     

Parallel trellis Viterbi algorithm for sparse channels

The Viterbi algorithm (VA), which normally operates using a single trellis, can be optimally reformulated into a set of independent trellises for a special class of sparse intersymbol interference (ISI) channels. These independent trellises operate in parallel and have less overall complexity than a single trellis. This trellis decomposition can be applied to a more general class of sparse channels approximately resulting in a suboptimal reduced complexity equalizer     

Survivor memory reduction in the Viterbi algorithm

This paper presents a novel approach for implementation of the Viterbi algorithm, wherein survivor paths are generally kept in as low as one half of the storage required for traditional trace-back methods. Survivor memory reduction is obtained by storing only the useful part of the survivor paths. In other words, the redundancy in the survivor paths is removed. A decoder using this approach not only requires significantly less memory, but also runs faster than conventional decoders. Some instances of this approach are explicitly presented.     

Efficient Viterbi algorithm for signals with ISI

The authors propose an efficient method of implementing the Viterbi algorithm at Nyquist-rate, for linearly modulated signals corrupted by ISI and AWGN. When signalling is M-ary and ISI extends over L-1 symbols, this scheme results in M+CL (complex multiplications, C is the number of samples per symbol), whereas the whitened-matched-filter based Viterbi algorithm requires M^L complex multiplications     

AMR系统中Viterbi译码的仿真与实现

本文根据AMR技术在GSM系统中物理层信道卷积编码规范,提出了一种可控制信道差错,降低工程实现难度的译码MATLAB仿真方案。结果表明,通过该仿真方案适合AMR语音业务信道卷积码的译码。     

High-performance iterative Viterbi algorithm for conventionalserial concatenated codes

The Viterbi algorithm (1967) and conventional serial concatenated codes (CSCC) have been widely applied in digital communication systems over the last 30 years. We show that the Shannon capacity of additive white Gaussian noise (AWGN) channels can be approached by CSCCs and the iterative VA (IVA). We firstly study the algebraic properties of CSCCs. We then present the IVA to decode these codes. We also analyze the performance of the IVA and conclude that a better performance can be achieved if we replace the powerful block codes by some simple parity codes. One of the key results in this paper shows that by using a proper design for the decoding method, codes with small loops can be very efficiently decoded using a min-sum type algorithm. The numerical results show that the IVA can closely approach the Shannon sphere-packing lower bound and the Shannon limit. For block sizes ranging from 56 information bits to 11970 information bits, the IVA can perform to within about 1 dB of the Shannon sphere-packing lower bound at a block error rate of 10^-4. We show that the IVA has a very low complexity and can be applied to many current standard systems, for example, the Qualcomm code-division multiple-access (CDMA) system and the NASA concatenated system, with very little modification or, for some cases, without any modification