Turbo码的一种全新的SOVA译码算法

SOVA算法因其译码时延低于MAP算法已成为Turbo码的实用译码算法。本文提出了一种放弃软判决值更新处理的全新的SOVA算法。该算法的独到之处在于,综合利用对栅格图的正向和反向搜索,从而实现了通过全局路径比较来产生软输出值。仿真结果表明,与传统SOVA算法相比这种全新的SOVA算法在不会明显增加译码计算量的前提下,显著地改善了译码性能。同时,其误码率性能在高信噪比时略优于Max-Log-MAP算法,并且已经逼近MAP算法。     

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.     

基于改进型SOVA的Turbo译码

第三代移动通信系统IMT-2000的高速率业务倾向于选择Turbo码,这就要求采用低时延、低复杂度的迭代译码技术,主要是软输出Viterbi算法(SOVA)和Max-Log-MAP算法.在先验等概和无限译码深度条件下,已证明略加修改的SOVA等效于Max-Log-MAP算法.由于在迭代译码中,先验概率须不断更新,本文证明了在存在先验概率的条件下改进型SOVA与Max-Log-MAP也是等效的,并讨论了有限译码深度限制下改进型SOVA与滑动窗口Max-Log-MAP算法的等效性.     

A Memory‐Efficient Block‐wise MAP Decoder Architecture

Next generation mobile communication system, such as IMT‐2000, adopts Turbo codes due to their powerful error correction capability. This paper presents a block‐wise maximum a posteriori (MAP) Turbo decoding structure with a low memory requirement. During this research, it has been observed that the training size and block size determine the amount of required memory and bit‐error rate (BER) performance of the block‐wise MAP decoder, and that comparable BER performance can be obtained with much shorter blocks when the training size is sufficient. Based on this observation, a new decoding structure is proposed and presented in this paper. The proposed block‐wise decoder employs a decoding scheme for reducing the memory requirement by setting the training size to be N times the block size. The memory requirement for storing the branch and state metrics can be reduced 30% to 45%, and synthesis results show that the overall memory area can be reduced by 5.27% to 7.29%, when compared to previous MAP decoders. The decoder throughput can be maintained in the proposed scheme without degrading the BER performance.     

一种新的基-4SOVA译码算法

SOVA (Soft Output Viterbi Algorithm)类算法因其译码时延远低于MAP类算法已成为Turbo码的实用译码算法,为了进一步减小译码延迟,提高译码速度,该文在简单分析基-4Max-Log-MAP算法的基础上,提出了一种新的基-4SOVA算法,并进行了完整的数学推导.该算法的关键是提出了一种新...     

Soft-Output BEAST Decoding With Application to Product Codes

A Bidirectional Efficient Algorithm for Searching code Trees (BEAST) is proposed for efficient soft-output decoding of block codes and concatenated block codes. BEAST operates on trees corresponding to the minimal trellis of a block code and finds a list of the most probable codewords. The complexity of the BEAST search is significantly lower than the complexity of trellis-based algorithms, such as the Viterbi algorithm and its list generalizations. The outputs of BEAST, a list of best codewords and their metrics, are used to obtain approximate a posteriori probabilities (APPs) of the transmitted symbols, yielding a soft-input soft-output (SISO) symbol decoder referred to as the BEAST-APP decoder. This decoder is employed as a component decoder in iterative schemes for decoding of product and incomplete product codes. Its performance and convergence behavior are investigated using extrinsic information transfer (EXIT) charts and compared to existing decoding schemes. It is shown that the BEAST-APP decoder achieves performances close to the Bahl–Cocke–Jelinek–Raviv (BCJR) decoder with a substantially lower computational complexity.      

一种基于SOVA的改进的Turbo码译码方案

本文在研究Ｔｕｒｂｏ 码反向ＳＯＶＡ（Ｓｏｆｔ－Ｏｕｔｐｕｔ ＶｉｔｅｒｂｉＡｌｇｏｒｉｔｈｍ ）译码性能的基础上,提出了一种同时利用正向和反向ＳＯＶＡ译码软输出信息的基于ＳＯＶＡ 的改进译码结构及其相应的软输出修正公式。计算机模拟结果表明,所提出的改进方案与传统的ＳＯＶＡ算法相比,其译码性能有明显的改善,并略优于Ｍａｘ－Ｌｏｇ－ＭＡＰ的性能     

A parallel MAP algorithm for low latency turbo decoding

To reduce the computational decoding delay of turbo codes, we propose a parallel algorithm for maximum a posteriori (MAP) decoders. We divide a whole noisy codeword into sub-blocks and use multiple processors to perform sub-block MAP decoding in parallel. Unlike the previously proposed approach with sub-block overlapping, we utilize the forward and backward variables computed in the previous iteration to provide boundary distributions for each sub-block MAP decoder. Our scheme depicts asymptotically optimal performance in the sense that the BER is the same as that of the regular turbo decoder     

Neural network decoding of the block Markov superposition transmission

A neural network (NN)-based decoding algorithm of block Markov superposition transmission (BMST) was researched.The decoders of the basic code with different network structures and representations of training data were implemented using NN.Integrating the NN-based decoder of the basic code in an iterative manner,a sliding window decoding algorithm was presented.To analyze the bit error rate (BER) performance,the genie-aided (GA) lower bounds were presented.The NN-based decoding algorithm of the BMST provides a possible way to apply NN to decode long codes.That means the part of the conventional decoder could be replaced by the NN.Numerical results show that the NN-based decoder of basic code can achieve the BER performance of the maximum likelihood (ML) decoder.For the BMST codes,BER performance of the NN-based decoding algorithm matches well with the GA lower bound and exhibits an extra coding gain.     

Performance of parallel and serial concatenated codes on fading channels

The performance of parallel and serial concatenated codes on frequency-nonselective fading channels is considered. The analytical average upper bounds of the code performance over Rician channels with independent fading are derived. Furthermore, the log-likelihood ratios and extrinsic information for maximum a posteriori (MAP) probability and soft-output Viterbi algorithm (SOVA) decoding methods on fading channels are developed. The derived upper bounds are evaluated and compared to the simulated bit-error rates over independent fading channels. The performance of parallel and serial codes with MAP and SOVA iterative decoding methods, with and without channel state information, is evaluated by simulation over independent and correlated fading channels. It is shown that, on correlated fading channels, the serial concatenated codes perform better than parallel concatenated codes. Furthermore, it has been demonstrated that the SOVA decoder has almost the same performance as the MAP decoder if ideal channel state information is used on correlated Rayleigh fading channels.     

A Flexible LDPC/Turbo Decoder Architecture

Low-density parity-check (LDPC) codes and convolutional Turbo codes are two of the most powerful error correcting codes that are widely used in modern communication systems. In a multi-mode baseband receiver, both LDPC and Turbo decoders may be required. However, the different decoding approaches for LDPC and Turbo codes usually lead to different hardware architectures. In this paper we propose a unified message passing algorithm for LDPC and Turbo codes and introduce a flexible soft-input soft-output (SISO) module to handle LDPC/Turbo decoding. We employ the trellis-based maximum a posteriori (MAP) algorithm as a bridge between LDPC and Turbo codes decoding. We view the LDPC code as a concatenation of n super-codes where each super-code has a simpler trellis structure so that the MAP algorithm can be easily applied to it. We propose a flexible functional unit (FFU) for MAP processing of LDPC and Turbo codes with a low hardware overhead (about 15% area and timing overhead). Based on the FFU, we propose an area-efficient flexible SISO decoder architecture to support LDPC/Turbo codes decoding. Multiple such SISO modules can be embedded into a parallel decoder for higher decoding throughput. As a case study, a flexible LDPC/Turbo decoder has been synthesized on a TSMC 90 nm CMOS technology with a core area of 3.2 mm². The decoder can support IEEE 802.16e LDPC codes, IEEE 802.11n LDPC codes, and 3GPP LTE Turbo codes. Running at 500 MHz clock frequency, the decoder can sustain up to 600 Mbps LDPC decoding or 450 Mbps Turbo decoding.     

MAP algorithms for decoding linear block codes based onsectionalized trellis diagrams

The maximum a posterioriprobability (MAP) algorithm is a trellis-based MAP decoding algorithm. It is the heart of turbo (or iterative) decoding that achieves an error performance near the Shannon limit. Unfortunately, the implementation of this algorithm requires large computation and storage. Furthermore, its forward and backward recursions result in a long decoding delay. For practical applications, this decoding algorithm must be simplifled and its decoding complexity and delay must be reduced. In this paper, the MAP algorithm and its variation's, such as log-MAP and max-log-MAP algorithms, are first applied to sectionalized trellises for linear block codes and carried out as two-stage decodings. Using the structural properties of properly sectionalized trellises, the decoding complexity and delay of the MAP algorithms can be reduced. Computation-wise optimum sectionalizations of a trellis for MAP algorithms are investigated. Also presented in this paper are bidirectional and parallel MAP decodings     

New SISO decoding algorithms

A new maximum a posteriori (MAP)-equivalent soft-input soft-output (SISO) algorithm is derived together with its simplified versions. The proposed SISO algorithms provide a good compromise between complexity and performance. Our simplest SISO algorithm has lower complexity than the log-MAP, the max-log-MAP, and the soft-output Viterbi (1998) algorithm SISO algorithms, and it is an equivalent max-log-MAP algorithm. When this algorithm is used, turbo codes with block length as short as 150 bits will outperform convolutional codes when compared on the basis of equal decoder complexity.     

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     

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     

Simple MAP decoding of first-order Reed-Muller and Hamming codes

A maximum a posteriori (MAP) probability decoder of a block code minimizes the probability of error for each transmitted symbol separately. The standard way of implementing MAP decoding of a linear code is the Bahl-Cocke-Jelinek-Raviv (BCJR) algorithm, which is based on a trellis representation of the code. The complexity of the BCJR algorithm for the first-order Reed-Muller (RM-1) codes and Hamming codes is proportional to n/sup 2/, where n is the code's length. In this correspondence, we present new MAP decoding algorithms for binary and nonbinary RM-1 and Hamming codes. The proposed algorithms have complexities proportional to q/sup 2/n log/sub q/n, where q is the alphabet size. In particular, for the binary codes this yields complexity of order n log n.     

高码率自适应Turbo编译码器的设计与FPGA实现

提出了一种高码率自适应Turbo编译码器的FPGA实现方案。在编码模块中采用特定参数的分组螺旋对称交织器,使编码器能通过删余构造高码率,且能通过相同的结尾比特使两个分量编码器的寄存器状态均归零。在SOVA译码模块中,各状态下路径的累积度量值的并行计算和可靠性值的并行更新使译码速度大大提高。仿真结果表明,该高码率自适应编译码器有良好的误码性能和较高的实用价值。     

一种性能优越的Turbo码SOVA译码算法

MAP译码算法性能上是最优的,但是其复杂度也是十分高的,影响了硬件的实现,介绍了一种性能上接近于MAP译码算法,复杂度上有明显减少的译码算法,并且对其进行了完善,仿真结果表明对于二进制Turbo码,改进后的译码算法与MAP算法的译码性能更为接近。     

Truncated Turbo Decoding with Reduced Computational Complexity

The concept of concatenated codes and turbo decoding is well known and leads to a remarkably good performance in many applications. The resulting signal processing for this concept shows high complexity relative to conventional Viterbi decoding. This paper, therefore, considers an alternative concept of turbo decoding to reduce the computational complexity. In thiscase, those sections of the sequence to be decoded, where changes of bit decisions (compared to the previous iteration step) are very unlikely,are excluded from the soft-output viterbi algorithm (SOVA). This decoding is much easier to process and the loss of bit error rate (BER) performance isquite small or even negligible in comparison to conventional turbo decoding.     

Turbo码的一种高效改进型MAP译码算法

该文给出了一种改进型最大后验概率(MAP)译码算法用于实现并行级联卷积码(Turbo码)的最优译码。与基于对数域的Log-MAP算法相比较,该文给出的算法不引入对数域,但能够完全消除标准MAP算法在迭代过程中必须进行的大量指数和对数运算。计算机仿真结果表明,这种具有最优纠错性能的改进型MAP算法能够显著减少运行时间,其译码效率甚至优于牺牲了较多纠错性能的最快速的对数域MAP译码算法(Max-Log-MAP)。