Two decoding algorithms for tailbiting codes

The paper presents two efficient Viterbi decoding-based suboptimal algorithms for tailbiting codes. The first algorithm, the wrap-around Viterbi algorithm (WAVA), falls into the circular decoding category. It processes the tailbiting trellis iteratively, explores the initial state of the transmitted sequence through continuous Viterbi decoding, and improves the decoding decision with iterations. A sufficient condition for the decision to be optimal is derived. For long tailbiting codes, the WAVA gives essentially optimal performance with about one round of Viterbi trial. For short- and medium-length tailbiting codes, simulations show that the WAVA achieves closer-to-optimum performance with fewer decoding stages compared with the other suboptimal circular decoding algorithms. The second algorithm, the bidirectional Viterbi algorithm (BVA), employs two wrap-around Viterbi decoders to process the tailbiting trellis from both ends in opposite directions. The surviving paths from the two decoders are combined to form composite paths once the decoders meet in the middle of the trellis. The composite paths at each stage thereafter serve as candidates for decision update. The bidirectional process improves the error performance and shortens the decoding latency of unidirectional decoding with additional storage and computation requirements. Simulation results show that both proposed algorithms effectively achieve practically optimum performance for tailbiting codes of any length.     

An artificial neural net Viterbi decoder

The Viterbi algorithm is a maximum likelihood means for decoding convolutional codes and has thus played an important role in applications ranging from satellite communications to cellular telephony. In the past, Viterbi decoders have usually been implemented using digital circuits. The speed of these digital decoders is directly related to the amount of parallelism in the design. As the constraint length of the code increases, parallelism becomes problematic due to the complexity of the decoder. In this paper an artificial neural network (ANN) Viterbi decoder is presented. The ANN decoder is significantly faster than comparable digital-only designs due to its fully parallel architecture. The fully parallel structure is obtained by implementing most of the Viterbi algorithm using analog neurons as opposed to digital circuits. Several modifications to the ANN decoder are considered, including an analog/digital hybrid design that results in an extremely fast and efficient decoder. The ANN decoder requires one-sixth the number of transistors required by the digital decoder. The connection weights of the ANN decoder are either +1 or -1, so weight considerations in the implementation are eliminated. This, together with the design's modularity and local connectivity, makes the ANN Viterbi decoder a natural fit for VLSI implementation. Simulation results are provided to show that the performance of the ANN decoder matches that of an ideal Viterbi decoder     

基于Radix-4实现高速Viterbi译码器设计

使用一种新的Viterbi译码器设计方法来达到高速率、低功耗设计。在传统Viterbi译码器中,ACS(add-compare-select)单元是基于radix-2网格设计的,而这里将介绍一种新的ACS设计方法,即基于radix-4网格的ACS单元设计。每个这样的ACS单元将有4路输入,即在每个时钟周期能够处理两级传统的基于radix-2设计的两级网格。同时在这里的Viterbi译码器设计中采用了Top-To-Down设计思想,用Verilog语言来描述RTL电路层。并用QuartusII软件进行电路仿真和综合。用本算法在33.333MHz时钟下实观在Altera公司的APEX20KFPGA的64状态Viterbi译码器译码速率可达8Mbps以上,且仅占用很小的硬件资源。采用此方法设计的高速Viterbi解码器SoftIPCore可应用于需要高速,低功耗译码的多媒体移动通讯上。     

Nonrecursive decoding algorithm for PR4 channel

The Viterbi algorithm (VA) is a recursive optimal solution to the state sequence estimation problem. The recursive nature of this algorithm puts limitations on high-speed implementations of Viterbi decoders. The authors propose a nonrecursive suboptimal decoding algorithm for the PR4 channel. The new decoder has negligible performance loss     

Nonrecursive decoding algorithm for PR4 channel

The Viterbi algorithm (VA) is a recursive optimal solution to the state sequence estimation problem. The recursive nature of this algorithm puts limitations on high-speed implementations of Viterbi decoders. The authors propose a nonrecursive suboptimal decoding algorithm for the PR4 channel. The new decoder has negligible performance loss     

Pseudo-syndrome methods for supervising Viterbi decoders at anycoding rate

A new technique for the supervision and synchronisation of Viterbi decoders, using the novel concept of the pseudo-syndrome, is presented. This technique is applicable with slight additional complexity, whatever the coding rate, to all decoders which contain the function of search for the maximum likelihood path. Simulation results are presented in the particular case of a K=7 encoder/decoder for different rates     

On the performance of sequential and Viterbi decoders for high-ratepunctured convolutional codes

This paper presents new computationally efficient and accurate techniques for estimating the performance of specific high-rate punctured convolutional codes and uses these techniques to evaluate the performance of sequential and Viterbi decoders for the best known codes. In particular, it demonstrates that the disparity between sequential and Viterbi decoding increases dramatically for long memory codes with high rates and for such codes, the union bound cannot be used as a criterion for selecting good codes for sequential decoders. In contrast, it shows that the proposed methods can be used as efficient tools for performance evaluation and/or identification of good high-rate punctured convolutional codes for use with sequential decoders     

Comments on `In-place updating of path metrics in Viterbi decoders'

For the original article see ibid., vol.24, no.4, p.1158-9 (1989). The authors of the above-titled paper proposed a computation scheme for updating path metrics in solid-state Viterbi decoders. They formally showed that the permutation of items in memory is a cyclic address rotation, and they described a hardware implementation based on the use of a barrel shifter. The commenter points out that the use of cyclic address rotation for Viterbi decoders has already been noted in the literature and shows that even greater VLSI area reduction is possible through the use of a tree shifter     

Optimal Datapath Widths Within Turbo and Viterbi Decoders for High Area- and Energy-Efficiency

Datapath widths in state-of-the-art Turbo and Viterbi decoder implementations depend on estimated upper bounds of the differences of processed metrics. Aiming at highest area and energy efficiency, this paper presents guidelines for designing Turbo and Viterbi decoder datapaths with minimal widths. This is based on maximum absolute values of branch, state and path metric differences within theMax-Log-MAP respectively Viterbi decoding algorithm applying modulo normalization. The proposed methodology for determining the maximum absolute values covers punctured as well as n-input binary convolutional and Turbo codes so it accommodates higherradix add-compare-select operations. Maximum absolute values of metric differences and minimum datapath widths are presented for the 3GPP-LTE, DVB-RCS2 and IEEE-802.16 (WiMAX) compliant Turbo decoders and for the IEEE-802.11 (Wi-Fi), IEEE-802.16 (WiMAX) and 3GPP-LTE compliant Viterbi decoders. Besides, a new dynamic branch-metric saturation scheme is presented, which enables a further datapath width reduction within Turbo decoders. In total, a datapath width reduction of two bits (?20 %) is achieved applying radix-4 Max-Log-MAP arithmetic. An overall area-time-energy complexity reduction of 31% is achieved for a soft-input soft-output decoder and of 24% for the LTE Turbo decoder.     

The Weight Spectra of Some Short Low-Rate Convolutional Codes

This paper reports the results of a computer analysis of the distance properties of some of the best known rate 1/2, 1/3, and 1/4 codes to constraint length 14. The data include the truncated weight distributions of the codewords belonging to the incorrect subset which specifies the performance of the Viterbi algorithm as well as the minimum asymptotic growth rate of the weights of unmerged codewords which has been conjectured to be related to the length of error events produced by Viterbi decoders.     

一种高速Viterbi译码器的设计与实现

Viterbi算法是卷积码的最优译码算法.设计并实现了一种高速(3,1,7)Viterbi译码器,该译码器由分支度量单元(BMU)、加比选单元(ACSU)、幸存路径存储单元(SMU)、控制单元(CU)组成.在StratixⅡ FPGA上实现、验证了该Viterbi译码器.验证结果表明,该译码器数据吞吐率达到231Mbit/s,在加性高斯白噪声(AWGN)信道下的误码率十分接近理论仿真值.与同类型Viterbi译码器比较,该译码器具有高速、硬件实现代价低的特点.     

A CMOS IC for Gb/s Viterbi decoding: system design and VLSIimplementation

At present, the Viterbi algorithm (VA) is widely used in communication systems for decoding and equalization. The achievable speed of conventional Viterbi decoders (VD's) is limited by the inherent nonlinear add-compare-select (ACS) recursion. The aim of this paper is to describe system design and VLSI implementation of a complex system of fabricated ASIC's for high speed Viterbi decoding using the “minimized method” (MM) parallelized VA. We particularly emphasize the interaction between system design, architecture and VLSI implementation as well as system partitioning issues and the resulting requirements for the system design flow. Our design objectives were 1) to achieve the same decoding performance as a conventional VD using the parallelized algorithm, 2) to achieve a speed of more than 1 Gb/s, and 3) to realize a system for this task using a single cascadable ASIC. With a minimum system configuration of four identical ASIC's produced by using 1.0 μ CMOS technology, the design objective of a decoding speed of 1.2 Gb/s is achieved. This means, compared to previous implementations of Viterbi decoders, the speed is increased by an order of magnitude     

Low-latency architectures for high-throughput rate Viterbi decoders

In this paper, a novel K-nested layered look-ahead method and its corresponding architecture, which combine K-trellis steps into one trellis step (where K is the encoder constraint length), are proposed for implementing low-latency high-throughput rate Viterbi decoders. The proposed method guarantees parallel paths between any two-trellis states in the look-ahead trellises and distributes the add-compare-select (ACS) computations to all trellis layers. It leads to regular and simple architecture for the Viterbi decoding algorithm. The look-ahead ACS computation latency of the proposed method increases logarithmically with respect to the look-ahead step (M) divided by the encoder constraint length (K) as opposed to linearly as in prior work. For a 4-state (i.e., K=3) convolutional code, the decoding latency of the Viterbi decoder using proposed method is reduced by 84%, at the expense of about 22% increase in hardware complexity, compared with conventional M-step look-ahead method with M=48 (where M is also the level of parallelism). The main advantage of our proposed design is that it has the least latency among all known look-ahead Viterbi decoders for a given level of parallelism.     

一种基于滑窗回溯多标准Viterbi译码器

为满足当前通信系统中存在的多种通信标准要求,提出了一种基于滑窗回溯的多标准Viterbi译码器。与其他Viterbi译码器相比,该译码器在支持任意长度序列译码的基础上,实现了1/2、1/3和1/4三种不同码率的配置,并适配5~9五种可变约束长度。此外,该译码器还具有软判决和硬判决两种判决模式,其中软判决采用8 bit有符号数量化。在对路径度量防溢出及幸存路径管理等模块进行优化后,该译码器能够在不显著增加延迟的前提下,具有更优异的工作性能。实验结果表明,该译码器可以根据设置的参数适用多种通信标准,并得到更好的误码性能。     

Design of a 20-mb/s 256-state Viterbi decoder

The design of high-throughput large-state Viterbi decoders relies on the use of multiple arithmetic units. The global communication channels among these parallel processors often consist of long interconnect wires, resulting in large area and high power consumption. In this paper, we propose a data transfer oriented design methodology to implement a low-power 256-state rate-1/3 Viterbi decoder. Our architectural level scheme uses operation partitioning, packing, and scheduling to analyze and optimize interconnect effects in early design stages. In comparison with other published Viterbi decoders, our approach reduces the global data transfers by up to 75% and decreases the amount of global buses by up to 48%, while enabling the use of deeply pipelined datapaths with no data forwarding. In the register-transfer level (RTL) implementation, we apply precomputation in conjunction with saturation arithmetic to further reduce power dissipation with provably no coding performance degradation. Designed using a 0.25 /spl mu/m standard cell library, our decoder achieves a throughput of 20 Mb/s in simulation and dissipates only 0.45 W.     

基于Xilinx FPGA的高速Viterbi回溯译码器

分析了新一代通信系统的发展对Viterbi译码器速率提出了更高的要求，通过优化Viterbi译码器结构，在Xilinx Virtex II PFGA上实现了速率30Mb／s以上的256状态Viterbi软译码。     

Improved decoding for a concatenated coding system recommended byCCSDS

The concatenated coding system recommended by CCSDS (Consultative Committee for Space Data Systems) uses an outer (255,233) Reed-Solomon (RS) code based on 8-b symbols, followed by the block interleaver and an inner rate 1/2 convolutional code with memory 6. Viterbi decoding is assumed. Two new decoding procedures based on repeated decoding trials and exchange of information between the two decoders and the deinterleaver are proposed. In the first one, where the improvement is 0.3-0.4 dB, only the RS decoder performs repeated trials. In the second one, where the improvement is 0.5-0.6 dB, both decoders perform repeated decoding trials and decoding information is exchanged between them     

Short convolutional codes with maximal free distance for rates 1/2, 1/3, and 1/4 (Corresp.)

This paper gives a tabulation of binary convolutional codes with maximum free distance for ratesfrac{1}{2}, frac{1}{3}, andfrac{1}{4}for all constraint lengths (measured in information digits)nuup to and includingnu = 14. These codes should be of practical interest in connection with Viterbi decoders.     

Some rate 1/3 and 1/4 binary convolutional codes with an optimum distance profile (Corresp.)

A tabulation of binary systematic convolutional codes with an optimum distance profile for rates1/3and1/4is given. A number of short rate1/3binary nonsystematic convolutional codes are listed. These latter codes are simultaneously optimal for the following distance measures: distance profile, minimum distance, and free distance; they appear attractive for use with Viterbi decoders. Comparisons with previously known codes are made.     

基于FPGA的高性能Viterbi译码器的设计与实现

对Viterbi译码器3个重要组成部分之一——幸存路径管理和存储模块进行优化设计。采用一种新的方法（改进的寄存器交换法）作为幸存路径管理方案，取消了译码时的回溯读操作。与采用传统回溯法的译码器相比，该译码器具有较低的译码时延、有效的存储空间管理和较低的硬件复杂度。在总体设计中对译码器的其他部分也进行了相应的优化设计，进行了综合布线后仿真，译码器输出的最大数据速率达到了90Mbps。