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     

Simplified parallel decision feedback equalisation for CCITT V.32/V.32 bis coded modems

A simplified parallel decision feedback equaliser (SPDFE) with the 32/64/128 AMPM CCITT trellis code is considered. The SPDFE detector consists of a whitened matched filter (WMF) and a reduced parallel decision feedback equaliser incorporated in the Viterbi decoder. The bit error rate simulation results show substantial improvement over the conventional detector with a linear equaliser and a separate Viterbi algorithm, although the implementation complexity remains the same.<>     

A 110 MHz 350 mW 0.6 μm CMOS 16-state generalized-target Viterbidetector for disk drive read channels

An architecture for efficiently implementing linear and nonlinear Viterbi detectors for magnetic read channels is presented. By employing generalized noiseless target values for the Viterbi trellis, the detector is better able to adapt to the actual binary data storage channel and less equalization is needed, resulting in a significant reduction in the probability of error. An implementation example is presented for the case of a 16-state Viterbi detector having a capability of handling any noiseless target of up to five adjacent nonzero values. In a 0.6 μm (drawn) 3.0 V CMOS process, the design has been implemented with a die area of 9 mm² consuming under 350 mW of power when operated at 110 MHz     

Reduced-state sequence estimation of digital sequences indispersive channels using state partitioning

A reduced-state sequence estimator for linear dispersive channels is described. The estimator is based on partitioning the set of all possible channel states in a way that defines a trellis with fewer states, and thus reduces complexity. Such a set partitioning approach provides a good performance/complexity tradeoff. The new technique is a generalisation of that described by Duel-Hallen and Heegard [1989]. The Viterbi algorithm (VA) is used to search for the best path through the reduced state trellis     

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     

Reduced complexity decoding of convolutional codes based on the M-algorithm and the minimal trellis

In this paper, we propose three new sub-optimum, reduced complexity decoding algorithms for convolutional codes. The algorithms are based on the minimal trellis representation for the convolutional code and on the M-algorithm. Since the minimal trellis has a periodically time-varying state profile, each algorithm has a different strategy to select the number of surviving states in each trellis depth. We analyse both the computational complexity, in terms of arithmetic operations, and the bit error rate performance of the proposed algorithms over the additive white Gaussian noise channel. Results demonstrate that considerable complexity reductions can be obtained at the cost of a small loss in the performance, as compared to the Viterbi decoder.     

Decision feedback sequence estimation for continuous phasemodulation on a linear multipath channel

An approach to reduced-complexity detection of partial response continuous phase modulation (CPM) on a linear multipath channel is presented. The method, referred to as decision feedback sequence estimation (DFSE), is based on a conventional Viterbi algorithm (VA) using a reduced-state trellis combined with decision feedback (DF). By varying the number of states in the VA, the receiver structure can be changed gradually from a DF receiver to the optimal maximum-likelihood sequence estimator (MLSE). In this way different tradeoffs between performance and complexity can be obtained. Results on the receiver performance, based on minimum distance calculations and bit error rate simulations, are given for Gaussian minimum-shift keying modulation on typical mobile radio channels. It is shown that for channels with a long memory, a significant complexity reduction can be achieved at the cost of a moderate degradation in performance     

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.     

Performance of Reduced State S–T Trellis Coded MC-CDMA Systems

In this paper, performance of reduced state space-time trellis coded multi carrier code division multiple access (STTC-MC-CDMA) system is evaluated and compared with the performance of original state STTC-MC-CDMA system. The optimum decoding scheme, i.e., maximum likelihood sequence estimation is employed which uses Viterbi algorithm for decoding STTC code. To simplify the implementation of the STTC decoder, the number of states is reduced by reducing the constraint length of the STTC encoder using generating function technique. In this technique, the generator matrix of STTC code is minimized to reduce the number of states of S–T trellis decoder. It is observed that the performance loss in terms of frame error rate of the reduced state STTC-MC-CDMA system is negligible compared to the original state STTC-MC-CDMA system. It is also noted that by using the reduced state technique the STTC decoder can be made faster since it is having lower computational complexity.     

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     

A chip-based multiuser detector for the downlink of a DS-CDMAsystem using a folded state-transition trellis

The maximum-likelihood sequence estimation (MLSE) multiuser detector has very good performance but at the expense of high computational complexity. The Viterbi algorithm is employed to implement the MLSE in the asynchronous uplink. In this scheme, the various bit-combinations are taken to be the different states in the decoding trellis. However, the number of states increases exponentially with the number of active users. We propose a scheme that exploits the feature of power-equality in the downlink to reduce the number of states involved. Each transmitted chip value can only take a certain number of possible discrete values. Using these discrete values as the states in the transition trellis diagram and operating the Viterbi algorithm at the chip level, the number of states is reduced from 4^K to (K+1) ^L where K is the number of users and L is the number of paths in the multipath channel     

Combined trellis coding and DFE through Tomlinson precoding

The authors propose and evaluate a receiver architecture which combines the power of a decision feedback equalizer (DFE) with trellis coding, while allowing for minimal decoding delay in such a way that the total gain of the system is additive. The system is based on a structure that transposes the feedback filter of the DFE into the transmitter and, for high-order constellations, provides negligible increase in transmitter power. The first known hardware realization of a high bit rate digital subscriber line (HDSL) system that achieves the coding gain provided by a trellis code in addition to the equalization gain provided by the DFE is presented. A system whose complexity of implementation is comparable to that of a typical DFE and an independent Viterbi decoder is proposed     

A 200-MSample/s trellis-coded PRML read/write channel with analogadaptive equalizer and digital servo

A fully integrated partial response maximum likelihood (PRML) read/write IC with analog adaptive equalization operates up to 200 MSample/s. The chip implements both matched spectral null (MSN) trellis and standard PR4 Viterbi detectors in the digital domain as well as digital servo. The device is integrated in a mature 0.7-μm BiCMOS technology, has a die size of 54 mm², and dissipates 2 W with MSN code or 1.5 W with PR4 code at 4.5-V supply and 200 MSample/s     

A new decoding algorithm for geometrically uniform trellis codes

A new decoding algorithm for geometrically uniform trellis codes is presented. The group structure of the codes is exploited in order to improve the decoding process. Analytical bounds to the algorithm performance and to its computational complexity are derived. The algorithm complexity does not depend on the number of states of the trellis describing the code. Extensive simulations yield results on the algorithm performance and complexity, and permit a comparison with the Viterbi algorithm and the sequential Fano algorithm     

串行级联多指数连续相位调制的迭代检测

针对多调制指数连续相位调制(Multi-h CPM)信号给出了卷积编码、随机符号交织器串行级联系统的迭代检测,研究了针对Multi-h CPM信号的逐符号最大后验概率(MAP)检测算法及不同系统参数下的迭代检测性能。最后提出在频率脉冲截断(FPT)的基础上使用奇异值分解(SVD)的联合降复杂度算法,有效简化了部分响应多指数CPM信号的状态转移网格以及接收端的匹配滤波器。在高斯白噪声信道下,针对第二代遥测新体制(Tier2)信号进行仿真,与相同码率及码长的低密度奇偶校验(LDPC)编码系统相比,串行级联系统有着3.5 dB的性能增益。最后采用本文提出的联合降复杂度算法,能够将Tier2信号的网格状态数由256简化到64,匹配滤波器个数由64降到2,而由此带来的迭代检测性能损失却可以忽略不计。     

Matched information rate codes for Partial response channels

In this paper, we design capacity-approaching codes for partial response channels. The codes are constructed as concatenations of inner trellis codes and outer low-density parity- check (LDPC) codes. Unlike previous constructions of trellis codes for partial response channels, we disregard any algebraic properties (e.g., the minimum distance or the run-length limit) in our design of the trellis code. Our design is purely probabilistic in that we construct the inner trellis code to mimic the transition probabilities of a Markov process that achieves a high (capacity-approaching) information rate. Hence, we name it a matched information rate (MIR) design. We provide a set of five design rules for constructions of capacity-approaching MIR inner trellis codes. We optimize the outer LDPC code using density evolution tools specially modified to fit the superchannel consisting of the inner MIR trellis code concatenated with the partial response channel. Using this strategy, we design degree sequences of irregular LDPC codes whose noise tolerance thresholds are only fractions of a decibel away from the capacity. Examples of code constructions are shown for channels both with and without spectral nulls.     

Golden Space–Time Trellis Coded Modulation

In this paper, we present a multidimensional trellis coded modulation scheme for a high rate 2times2 multiple-input multiple-output (MIMO) system over slow fading channels. Set partitioning of the Golden code is designed specifically to increase the minimum determinant. The branches of the outer trellis code are labeled with these partitions and Viterbi algorithm is applied for trellis decoding. In order to compute the branch metrics, a sphere decoder is used. The general framework for code design and optimization is given. Performance of the proposed scheme is evaluated by simulation and it is shown that it achieves significant performance gains over the uncoded Golden code     

On noncoherent sequence detection of coded QAM

New noncoherent sequence detection algorithms for combined demodulation and decoding of coded linear modulations transmitted over additive white Gaussian noise channels are presented. These schemes may be based on the Viterbi algorithm and have a performance which approaches that of coherent detection for increasing complexity. The tradeoff between complexity and performance is simply controlled by a parameter referred to as implicit phase memory and the number of trellis states     

On the BCJR trellis for linear block codes

In this semi-tutorial paper, we will investigate the computational complexity of an abstract version of the Viterbi algorithm on a trellis, and show that if the trellis has e edges, the complexity of the Viterbi algorithm is Θ(e). This result suggests that the “best” trellis representation for a given linear block code is the one with the fewest edges. We will then show that, among all trellises that represent a given code, the original trellis introduced by Bahl, Cocke, Jelinek, and Raviv in 1974, and later rediscovered by Wolf (1978), Massey (1978), and Forney (1988), uniquely minimizes the edge count, as well as several other figures of merit. Following Forney and Kschischang and Sorokine (1995), we will also discuss “trellis-oriented” or “minimal-span” generator matrices, which facilitate the calculation of the size of the BCJR trellis, as well as the actual construction of it     

Low-complexity iterative decoding with decision-aided equalizationfor magnetic recording channels

Turbo codes are applied to magnetic recoding channels by treating the channel as a rate-one convolutional code that requires a soft a posteriori probability (APP) detector for channel inputs. The complexity of conventional APP detectors, such as the BCJR algorithm or the soft-output Viterbi algorithm (SOVA), grows exponentially with the channel memory length. This paper derives a new APP module for binary intersymbol interference (ISI) channels based on minimum mean squared error (MMSE) decision-aided equalization (DAE), whose complexity grows linearly with the channel memory length, and it shows that the MMSE DAE is also optimal by the maximum a posteriori probability (MAP) criterion. The performance of the DAE is analyzed, and an implementable turbo-DAE structure is proposed. The reduction of channel APP detection complexity reaches 95% for a five-tap ISI channel when the DAE is applied. Simulations performed on partial response channels show close to optimum performance for this turbo-DAE structure. Error propagation of the DAE is also studied, and two fixed-delay solutions are proposed based on combining the DAE with the BCJR algorithm