On dualizing trellis-based APP decoding algorithms

The trellis of a finite Abelian group code is locally (i.e., trellis section by trellis section) related to the trellis of the corresponding dual group code which allows one to express the basic operations of the a posteriori probability (APP) decoding algorithm (defined on a single trellis section of the primal trellis) in terms of the corresponding dual trellis section. Using this local approach, any algorithm employing the same type of operations as the APP algorithm can, thus, be dualized, even if the global dual code does not exist (e.g., nongroup codes represented by a group trellis). Given this, the complexity advantage of the dual approach for high-rate codes can be generalized to a broader class of APP decoding algorithms, including suboptimum algorithms approximating the true APP, which may be more attractive in practical applications due to their reduced complexity. Moreover, the local approach opens the way for mixed approaches where the operations of the APP algorithm are not exclusively performed on the primal or dual trellis. This is inevitable if the code does not possess a trellis consisting solely of group trellis sections as, e.g., for certain terminated group or ring codes. The complexity reduction offered by applying dualization is evaluated. As examples, we give a dual implementation of a suboptimum APP decoding algorithm for tailbiting convolutional codes, as well as dual implementations of APP algorithms of the sliding-window type. Moreover, we evaluate their performance for decoding usual tailbiting codes or convolutional codes, respectively, as well as their performance as component decoders in iteratively decoded parallel concatenated schemes.     

Low-Density Parity-Check Codes with 2-State Trellis Decoding

A class of low-density parity-check (LDPC) codes with a simple 2-state trellis structure is presented. For LDPC decoding, the conventional belief propagation (BP) algorithm consists of numerous sub-decoders of single-parity check codes and exchanges information between sub-decoders in an iterative manner. If the single-parity check codes can be constructed and grouped in a proper way, the decoder can be decomposed into few identical 2-state trellis decoders. Therefore, instead of numerous sub-decoders of single-parity check codes, an iterative decoding algorithm based on few sub-decoders over 2-state trellis is proposed. The proposed decoding algorithm improves the efficiency of message passing between sub-decoders and hence provides a fast convergent rate as compared to the standard BP algorithm. Simulation results show that the proposed scheme provides a better performance and a fast convergent rate as compared to those of standard BP algorithm. The result also shows that the proposed algorithm has a similar performance as that of asynchronous replica shuffled BP algorithm and has a slightly inferior performance than that of synchronous replica shuffled BP algorithm. However, complexity analysis shows that our proposed algorithm has complexity that is lower than that of the replica shuffled BP algorithm.     

Computation of Posterior Marginals on Aggregated State Models for Soft Source Decoding

Optimum soft decoding of sources compressed with variable length codes and quasi-arithmetic codes, transmitted over noisy channels, can be performed on a bit/symbol trellis. However, the number of states of the trellis is a quadratic function of the sequence length leading to a decoding complexity which is not tractable for practical applications. The decoding complexity can be significantly reduced by using an aggregated state model, while still achieving close to optimum performance in terms of bit error rate and frame error rate. However, symbol a posteriori probabilities can not be directly derived on these models and the symbol error rate (SER) may not be minimized. This paper describes a two-step decoding algorithm that achieves close to optimal decoding performance in terms of SER on aggregated state models. A performance and complexity analysis of the proposed algorithm is given.     

Soft-decision decoding of Reed-Muller codes as generalized multipleconcatenated codes

Constructs Reed-Muller codes by generalized multiple concatenation of binary block codes of length 2. As a consequence of this construction, a new decoding procedure is derived that uses soft-decision information. The algorithm is designed for low decoding complexity and is applicable to all Reed-Muller codes. It gives better decoding performance than soft-decision bounded-distance decoding. Its decoding complexity is much lower than that of maximum-likelihood trellis decoding of Reed-Muller codes, especially for long codes     

A trellis-based recursive maximum-likelihood decoding algorithm forbinary linear block codes

This paper presents an efficient trellis-based maximum-likelihood decoding algorithm for binary linear block codes. This algorithm is recursive in nature and is devised based on the structural properties and optimum sectionalization of a code trellis. The complexity of the proposed decoding algorithm is analyzed. Numerical results show that the proposed decoding algorithm significantly reduces the decoding complexity. A recursive method for finding the optimum sectionalization of a trellis in terms of computational complexity is given     

Robustly good trellis codes

The relationship between the distance properties of trellis codes and the computational effort and error performance of sequential decoding is studied and optimum distance profile (ODP) and optimum free distance (OFD) trellis codes are constructed for 8-PSK and 16 QAM modulation. A comparison of the performance of both the ODP and the OFD trellis codes reveals that neither class of codes results in the best trade-off between error performance and computational effort when sequential decoding is used. A new algorithm is then proposed to construct robustly good trellis codes for use with sequential decoding. New trellis codes with asymptotic coding gains up to 6.66 dB are obtained using this algorithm, and the new codes achieve nearly the same free distances as the OFD codes and nearly the same distance profiles as the ODP codes     

Complexity Reduction in SISO Decoding of Block Codes

SISO decoding for block codes can be carried out based on a trellis representation of the code. However, the complexity entailed by such decoding is most often prohibitive and thus prevents practical implementation. This paper examines a new decoding scheme based on the soft-output Viterbi algorithm (SOVA) applied to a sectionalized trellis for linear block codes. The computational complexities of the new SOVA decoder and of the conventional SOVA decoder, based on a bit-level trellis, are theoretically analyzed and derived for different linear block codes. These results are used to obtain optimum sectionalizations of a trellis for SOVA. For comparisons, the optimum sectionalizations for Maximum A Posteriori (MAP) and Maximum Logarithm MAP (Max-Log-MAP) algorithms, and their corresponding computational complexities are included. The results confirm that the new SOVA decoder is the most computationally efficient SISO decoder, in comparisons to MAP and Max-Log-MAP algorithms. The simulation results of the bit error rate (BER) performance, assuming binary phase -- shift keying (BPSK) and additive white Gaussian noise (AWGN) channel, demonstrate that the performance of the new decoding scheme is not degraded. The BER performance of iterative SOVA decoding of serially concatenated block codes shows no difference in the quality of the soft outputs of the new decoding scheme and of the conventional SOVA.     

Iterative maximum-likelihood trellis decoding for block codes

An iterative trellis search technique is described for the maximum-likelihood (ML) soft decision decoding of block codes. The proposed technique derives its motivation from the fact that a given block code may be a subcode for a parent code whose associated trellis has substantially fewer edges. Through the use of list-Viterbi (1967) decoding and an iterative algorithm, the proposed technique allows for the use of a trellis for the parent code in the ML decoding of the desired subcode. Complexity and performance analyses, as well as details of potential implementations, indicate a substantial reduction in decoding complexity for linear block codes of practical length while achieving ML or near-ML soft decision performance     

Optimal sectionalization of a trellis

While the complexity of trellis decoding for a given block code is essentially a function of the number of states and branches in its trellis, the decoding complexity may be often reduced by means of an appropriate sectionalization of the trellis. Notwithstanding the many examples of such sectionalizations for particular codes that appeared in the literature, no systematic method for finding the best sectionalization of a given trellis is presently known. We present a polynomial-time algorithm which produces the optimal sectionalization of a given trellis T in time O(n²), where n is the length of the code generated by T. The algorithm is developed in a general setting of certain operations and functions defined on the set of trellises; it therefore applies to both linear and nonlinear codes, and easily accommodates a broad range of optimality criteria. The particular optimality criterion based on minimizing the total number of additions and comparisons required for maximum-likelihood trellis decoding is investigated in detail: several different methods for decoding a given trellis are discussed and compared in a number of examples. Finally, analysis of the dynamical properties of certain optimal sectionalizations is presented     

Space-Time Trellis Code Design Based on Super Quasi-Orthogonal Block Codes With Minimum Decoding Complexity

In this letter, we propose a new family of space-time trellis codes, which are constructed by combining a super set of quasi-orthogonal space-time block codes with minimum decoding complexity with an outer multiple trellis coded modulation encoder. A systematic set-partitioning method for quadratic amplitude modulation constellations is given. The proposed scheme can be used for systems with four or more than four transmit antennas. Furthermore, its decoding complexity is low because its branch metric calculation can be implemented in a symbolwise way. Simulation results demonstrate that the proposed scheme has a comparable performance as super quasi-orthogonal space-time trellis codes proposed by Jafarkhani and Hassanpour while providing a lower decoding complexity.     

Multilevel trellis MPSK modulation codes for the Rayleigh fadingchannel

The multilevel coding technique is used for constructing multilevel trellis M-ary phase-shift-keying (MPSK) modulation codes for the Rayleigh fading channel. In the construction of a code, all the factors which affect the code performance and its decoding complexity are considered. The error performance of some of these codes based on both one-stage optimum decoding and multistage suboptimum decoding has been simulated. The simulation results show that these codes achieve good error performance with small decoding complexity     

Non‐binary SOVA algorithms for decoding of block codes on a sectionalized trellis

In this paper, we explore computationally efficient implementations of the soft output viterbi algorithm (SOVA) applied to Soft‐Input Soft‐Output (SISO) decoding of linear block codes. In order to simplify the trellis‐based decoding of binary block codes with SOVA, we use the technique of sectionalization of the trellis, which has been successfully applied to the simplification of the MAP and Max‐Log‐MAP algorithms. Due to the branch complexity of the sectionalized trellis, we define a generalization of a non‐binary version of SOVA. However, the computational complexity of directly applying this approach remains too high for efficient implementation; we thus introduce the concept of non‐binary SOVA (NSOVA) with propagation of bit‐level reliabilities (BLR). This new algorithm is analyzed from a computational complexity viewpoint. Both serial and parallel implementations are explored. Finally, optimal sectionalizations are derived for selected codes; since the normal SOVA decoding is a particular case of NSOVA with BLR, we show that our approach is more efficient than a bit‐level trellis by showing that, for all the codes tested, the optimal trellis is a sectionalized one. Copyright © 2007 John Wiley & Sons, Ltd.     

A new high rate code scheme with highly parallel and low complexity decoding algorithm

A new high rate code scheme is proposed in this paper. It consists of serial concatenated recursive systematic ordinary (nonpunctured) convolutional codes with only 8 states in the trellis of the corresponding reciprocal dual codes. With a low complexity and highly parallel decoding algorithm, over additive white Gaussian noise channels, the proposed codes can achieve good bit error rate (BER) performance comparable to that of turbo codes and low density parity check (LDPC) codes. At code rate R=16/17, the overall decoding complexity of the proposed code scheme is almost half that of the LDPC codes.     

一种改进的空时Turbo网格码Log-MAP译码算法

提出应用于多天线系统的空时编码是未来无线移动通信中极具前途的一种技术.文中在详细论述了空时Turbo 网格码的基础上,针对Log-MAP译码提出了优化方案.仿真结果表明, 新的算法在大大降低译码复杂度的同时较好地保持了译码性能, 使其非常接近Log-MAP 算法的译码性能,同时也非常有利于硬件实现.     

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.     

Fast decoding of the Leech lattice

An efficient algorithm is presented for maximum-likelihood soft-decision decoding of the Leech lattice. The superiority of this decoder with respect to both computational and memory complexities is demonstrated in comparison with previously published decoding methods. Gain factors in the range of 2-10 are achieved. The authors conclude with some more advanced ideas for achieving a further reduction of the algorithm complexity based on a generalization of the Wagner decoding method to two parity constraints. A comparison with the complexity of some trellis-coded modulation schemes is discussed. The decoding algorithm presented seems to achieve a computational complexity comparable to that of the equivalent trellis codes     

Scarce-state-transition error-trellis decoding of block codes withBPSK signals

A novel decoding technique for linear block codes with coherent BPSK signals is proposed. The new system has the same error performance as and similar complexity to the conventional trellis decoding of block codes. Like the scarce-state-transition Viterbi decoding of convolutional codes, the proposed system is also well suited for CMOS VLSI implementation and has a lower power consumption     

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.     

Performance bound and trellis-code design criterion for discretememoryless channels and finite-delay symbol-by-symbol decoding

A new tight analytical upper bound is presented for the performance of finite-delay symbol-by-symbol (SBS) Abend-Fritchman-like decoding of trellis-encoded data crossing arbitrary (eventually time-varying) discrete memoryless channels (DMCs). On the basis of this bound, a related criterion for the optimal design of trellis codes with SBS decoding is then proposed. It gives rise to an effective procedure for the construction of good trellis codes (generally time varying and nonlinear) with assigned decoding complexity