Good trellises for IC implementation of Viterbi decoders for linearblock codes

This paper 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. Parallel structures of trellises with various section lengths for binary BCH and Reed-Muller (RM) codes of lengths 32 and 64 are analyzed. Next, the complexity of the IC implementation of a Viterbi decoder based on an L-section trellis diagram for a code is investigated. A structural property of a Viterbi decoder called add-compare-select (ACS)-connectivity which is related to state connectivity is introduced. This parameter affects the complexity of wire-routing (interconnections within the IC). The effect of five parameters namely: (1) effective computational complexity; (2) complexity of the ACS-circuit; (3) traceback complexity; (4) ACS-connectivity; and (5) branch complexity of a trellis diagram on the very large scale integration (VLSI) complexity of a Viterbi decoder is investigated. It is shown that an IC implementation of a Viterbi decoder based on a nonminimal trellis requires less area and is capable of operation at higher speed than one based on the minimal trellis when the commonly used ACS-array architecture is considered     

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     

1000 BASE-T收发器中的Viterbi译码算法研究

采用4维8状态网格编码和Viterbi译码相结合的方法，理论上可以获得6dB的编码增益，用于补偿采用PAM-5编码所带来的噪声容限损失。文章给出了针对4维8状态网格编码的Viterbi译码算法的译码过程，并就译码深度、量化精度和溢出处理方法对译码器性能的影响进行了算法仿真，确定出适合1000 BASE-T收发器应用的译码器参数。     

A modular bit-serial architecture for large-constraint-lengthViterbi decoding

A node-parallel Viterbi decoding architecture and bit-serial processing and communication are presented. An important aspect of this structure is that short-constraint-length decoders may be interconnected, without loss of throughput, to implement a Viterbi decoder of larger constraint length. The convolutional encoder trellis is modeled by appropriate wiring of decoder processing nodes: a variety of generating codes can be accommodated. Bit-serial communication links between nodes require only a single wire each and thus interconnection area is relatively small. During each decoding cycle, more than 50 b need to be communicated on each serial link and thus the technique is limited to moderate bit rate applications. A constraint length K=4 `proof of concept' chip was developed using 9860 transistors in 3 μm CMOS on a 4.51-mm×4.51-mm die size. The complete circuit operates at 280 kb/s and supports any rate 1/2 or 1/3 code with eight-level soft decision     

Design of Voltage Overscaled Low-Power Trellis Decoders in Presence of Process Variations

In hardware implementations of many signal processing functions, timing errors on different circuit signals may have largely different importance with respect to the overall signal processing performance. This motivates us to apply the concept of unequal error tolerance to enable the use of voltage overscaling at minimal signal processing performance degradation. Realization of unequal error tolerance involves two main issues, including how to quantify the importance of each circuit signal and how to incorporate the importance quantification into signal processing circuit design. We developed techniques to tackle these two issues and applied them to two types of trellis decoders including Viterbi decoder for convolutional code decoding and Max-Log-Maximum A Posteriori (MAP) decoder for Turbo code decoding. Simulation results demonstrated promising energy saving potentials of the proposed design solution on both trellis decoding computation and memory storage at small decoding performance degradation.      

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     

Joint Erasure Marking and List Viterbi Algorithm for Decoding in Unknown Non-Gaussian Noise

In many real-world communication systems, the channel noise is non-Gaussian due to the presence of impulsive noise as well as the background Gaussian noise. In such situations, the conventional Euclidean distance based decoder may suffer from the problem of severe metric mismatch. To overcome the problem, we recently proposed the joint erasure marking and Viterbi algorithm (JEVA) as a robust trellis decoder that does not require an estimate of the impulsive noise distribution. In this work, two ways to further improve JEVA are presented for systems with an error detecting code. Specifically, the JEVA is integrated with the list Viterbi algorithm (LVA) to form the two-dimensional joint erasure marking and list Viterbi algorithm (JELVA) and the switched JELVA, respectively. By combining the respective strengths of the JEVA and the LVA, the integrated decoding schemes are able to achieve significant performance gains over the original JEVA and achieve a wide range of performance-complexity-delay tradeoffs.     

A Differential Architecture for an Online Analog Viterbi Decoder

A differential architecture of an analog Viterbi decoder is presented. Analog processing enables the analog-digital converter to be excluded from the decoder realization. Moreover, high-speed operation can be achieved via differential processing. We describe the differential operation, together with the resulting decoder structure. The differential architecture enables the trace-back memory to be excluded and makes online decoding after initial transitional stages possible. We analyze the performance of the differential analog decoder by including analog circuit nonidealities in the system-level model. The decoder obeys a nonlinear transfer function, and the monotonical growth of path metrics is avoided by scaling and subtraction of the global minimum. The resulting differential analog decoder performance is compared with the performance of a 3-bit soft-decision digital Viterbi decoder. The simulations are performed for a (2,1,7) convolutional code.     

Efficient complexity reduction technique in trellis decodingalgorithm

An efficient reduced search trellis decoding algorithm in which the decoder selects a part of existing paths by using a threshold value of the path metric is proposed. The threshold value at each time stage of the trellis is found by simply investigating the statistics of the path metrics, and does not require any prior knowledge such as the signal-to-noise ratio     

A 100-Mb/s 2.8-V CMOS current-mode analog Viterbi decoder

This paper describes a 4-state rate-1/2 analog convolutional decoder fabricated in 0.8-μm CMOS technology. Although analog implementations have been described in the literature, this decoder is the first to be reported realizing the add-compare-select section entirely with current-mode analog circuits. It operates at data rates up to 115 Mb/s (channel rate 230 Mb/s) and consumes 39 mW at that rate from a single 2.8-V power supply. At a rate of 100 Mb/s, the power consumption per trellis state is about 1/3 that of a comparable digital system. In addition, at 50 Mb/s (the only rate at which comparative data were available), the power consumption per trellis state is similarly about 1/3 that of the best competing analog realization (i.e., excluding, for example, PR4 detectors which use a simplified form of the Viterbi algorithm). The chip contains 3.7 K transistors of which less than 1 K are used in the analog part of the decoder. The die has a core area of 1 mm², of which about 1/3 contains the analog section. The measured performance is close to that of an ideal Viterbi decoder with infinite quantization. In addition, a technique is described which extends the application of the circuits to decoders with a larger number of states. A typical example is a 64-state decoder for use in high-speed satellite communications     

高速无线数传网格编码信号的简化解码算法

简单分析了网格编码信号在加性白高斯噪声(AWGN)信道中基于相位解码的维特比算法原理,并给出了一个两阶段解码算法的实现过程.该解码算法是基于接受到信号的相位信息进行解码,并带有一个简单的锁相环解决了相位模糊问题.两阶段解码算法对信号中的编码位和未编码位分别进行译码,因此增加了解码器的可移植性.该译码算法在保证译码性能的同时,明显降低了接收机的复杂度.     

State Transparent Convolutional Codes and Their Novel Maximum-Likelihood Decoding Algorithm

Almost all the probabilistic decoding algorithms known for convolutional codes, perform decoding without prior knowledge of the error locations. Here, we introduce a novel maximum-likelihood decoding algorithm for a new class of convolutional codes named as the state transparent convolutional (STC) codes, which due to their properties error detection and error locating is possible prior to error correction. Hence, their decoding algorithm, termed here as the STC decoder, allows an error correcting algorithm to be applied only to the erroneous portions of the received sequence referred to here as the error spans (ESPs). We further prove that the proposed decoder, which locates the ESPs and applies the Viterbi algorithm (VA) only to these portions, always yields a decoded path in trellis identical to the one generated by the Viterbi decoder (VD). Due to the fact that the STC decoder applies the VA only to the ESPs, hence percentage of the single-stage (per codeword) trellis decoding performed by the STC decoder is considerably less than the VD, which is applied to the entire received sequence and this reduction is overwhelming for the fading channels, where the erroneous codewords are mostly clustered. Furthermore, through applying the VA only to the ESPs, the resulting algorithm can be viewed as a new formulation of the VD for the STC codes that analogous to the block decoding algorithms provides a predecoding error detection and error locating capabilities, while performing less single-stage trellis decoding.     

An optimal circular Viterbi decoder for the bounded distance criterion

We propose a Viterbi-type decoder for tailbiting trellis codes that works by traversing the tailbiting circle somewhat more than once. The traversal is the least possible for any bounded distance Viterbi decoder. Procedures are given that compute this minimum. Unlike previous decoders of the type, the new scheme does not suffer limit cycles or from pseudocodewords. The bit-error rate is compared to that of Bahl-Cocke-Jelinek-Raviv and maximum-likelihood decoding.     

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     

A hardware-efficient technique to implement a trellis code modulation decoder

This brief presents a new technique in implementing a very large-scale integration trellis code modulation (TCM) decoder. The technique aims to reduce hardware complexity and increase decoding throughput. The technique is introduced in the design of a Viterbi decoder. To simplify the decoding algorithm and calculation, branch cost distances are pre-calculated and stored in a distance look-up table (DLUT). The concept of DLUT significantly reduces hardware requirements as this table eliminates the need for calculation circuitry. In addition, an output LUT (OLUT) is constructed based on the trellis diagram of the code. This table generates the decoding output using information provided by the algorithm. The use of this OLUT reduces the amount of storage requirement. The technique was used to design a 16-state, radix-4 codec for two-dimensional and four-dimensional TCM. The decoder was implemented in hardware after functional simulation. The tested ASIC has a core area of 1.1 mm/sup 2/ in 0.18-/spl mu/m CMOS. A decoding speed of 1 Gbps was achieved. Implementation results have shown that LUTs can be used to decrease hardware requirement and increase decoding speed.     

Soft-decision phase detection with Viterbi decoding for CPM signals

It is known that continuous phase modulation (CPM) signals can be optimally detected by using coherent demodulation followed by Viterbi decoding. However, such a receiver is generally complicated, particularly at higher numbers of states, as it requires many correlators and many reference signals in the demodulator. In this study, a much simpler receiver, which employs a soft-decision phase detector followed by a Viterbi decoder, is proposed for the detection of CPM signals. The phase detector makes a decision in favor of one of the preselected phase subregions at the end of every interval, which is then used to calculate metrics for decoding. As in optimal detection, the Viterbi decoder decodes according to the trellis structure of CPM signals. The proposed receiver is analyzed in a narrow-band Gaussian channel with 2REC, 2-h, and trellis-coded continuous-phase frequency-shift keying signals. Numerical results show that the proposed receiver performs close to optimal detection with all types of signals considered in this study. The effect of the number of subregions in the phase detector is examined     

Decoding of trellis-encoded signals in the presence of intersymbolinterference and noise

A novel receiver for data-transmission systems using trellis-coded modulation is investigated. It comprises a whitened-matched filter and a trellis decoder which combines the previously separated functions of equalization and trellis-coded modulation (TCM) decoding. TCM encoder, transmission channel, and whitened-matched filter are modeled by a single finite-state machine with combined intersymbol interference and code states. Using ISI-state truncation techniques and the set-partitioning principles inherent in TCM, a systematic method is then developed for reducing the state complexity of the corresponding ISI and code trellis. A modified branch metric is used for canceling those ISI terms which are not represented by the trellis states. The approach leads to a family of Viterbi decoders which offer a tradeoff between decoding complexity and performance. An adaptive version of the proposed receiver is discussed, and an efficient structure for reduced-state decoding is given. Simulation results are presented for channels with severe amplitude and phase distortion. It is shown that the proposed receiver achieves a significant gain in noise margin over a conventional receiver which uses separate linear equalization and TCM decoding     

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     

FPGA design and implementation of a low-power systolic array-based adaptive Viterbi decoder

In this paper, by modifying the well-known Viterbi algorithm, an adaptive Viterbi algorithm that is based on strongly connected trellis decoding is proposed. Using this algorithm, the design and a field-programmable gate array implementation of a low-power adaptive Viterbi decoder with a constraint length of 9 and a code rate of 1/2 is presented. In this design, a novel systolic array-based architecture with time multiplexing and arithmetic pipelining for implementing the proposed algorithm is used. It is shown that the proposed algorithm can reduce by up to 70% the average number of ACS computations over that by using the nonadaptive Viterbi algorithm, without degradation in the error performance. This results in lowering the switching activities of the logic cells, with a consequent reduction in the dynamic power. Further, it is shown that the total power consumption in the implementation of the proposed algorithm can be reduced by up to 43% compared to that in the implementation of the nonadaptive Viterbi algorithm, with a negligible increase in the hardware.     

一种基于FPGA的Viterbi译码器的研究与设计

针对通信系统中传统维特比(Viterbi)译码器结构复杂、译码延时大、资源消耗大的问题,提出了一种新的基于FPGA的Viterbi译码器设计。结合(2,1,7)卷积编码器和Viterbi译码器的工作原理,设计出译码器的核心组成模块,具体采用3比特软判决译码,用曼哈顿距离计算分支度量,32个碟型加比选子单元并行运算,完成幸存路径和幸存信息的计算。幸存路径管理模块采用Viterbi截短译码算法,回溯操作分成写数据、回溯读和译码读,以改进的流水线进行并行译码操作,译码延时和储存空间分别降低至和。