Memory-Reduced Maximum A Posteriori Probability Decoding for High-Throughput Parallel Turbo Decoders

Wireless communication standards make use of parallel turbo decoder for higher data rate at the cost of large hardware resources. This paper presents a memory-reduced back-trace technique, which is based on a new method of estimating backward-recursion factors, for the maximum a posteriori probability (MAP) decoding. Mathematical reformulations of branch-metric equations are performed to reduce the memory requirement of branch metrics for each trellis stage. Subsequently, an architecture of MAP decoder and its scheduling based on the proposed back trace as well as branch-metric reformulation are presented in this work. Comparative analysis of bit-error-rate (BER) performances in additive white Gaussian noise channel environment for MAP as well as parallel turbo decoders are carried out. It has shown that a MAP decoder with a code rate of 1/2 and a parallel turbo decoder with a code rate of 1/3 have achieved coding gains of 1.28 dB at a BER of 10\(^{-5}\) and of 0.4 dB at a BER of 10\(^{-4}\), respectively. In order to meet high-data-rate benchmarks of recently deployed wireless communication standards, very large scale integration implementations of parallel turbo decoder with 8–64 MAP decoders have been reported. Thereby, savings of hardware resources by such parallel turbo decoders based on the suggested memory-reduced techniques are accounted in terms of complementary metal oxide semiconductor transistor count. It has shown that the parallel turbo decoder with 32 and 64 MAP decoders has shown hardware savings of 34 and 44 % respectively.     

Turbo decoder

We propose an adaptive channel SNR estimation algorithm required for the iterative MAP decoding of turbo decoders. The proposed algorithm uses the extrinsic values generated within the iterative MAP decoder to update the channel SNR estimate toward its optimum value per each decoder iteration or per each turbo code frame     

多维Turbo码研究

介绍了多维Turbo的编码原理,并提出了一种基于MAP算法的多维Turbo码译码器结构。研究了多维Turbo码的性能及优点,并通过仿真与二维的Turbo码进行了比较。分析表明,多维Turbo码可以获得更好的性能。     

Design and Architecture of Low‐Latency High‐Speed Turbo Decoders

In this paper, we propose and present implementation results of a high‐speed turbo decoding algorithm. The latency caused by (de)interleaving and iterative decoding in a conventional maximum a posteriori turbo decoder can be dramatically reduced with the proposed design. The source of the latency reduction is from the combination of the radix‐4, center to top, parallel decoding, and early‐stop algorithms. This reduced latency enables the use of the turbo decoder as a forward error correction scheme in real‐time wireless communication services. The proposed scheme results in a slight degradation in bit error rate performance for large block sizes because the effective interleaver size in a radix‐4 implementation is reduced to half, relative to the conventional method. To prove the latency reduction, we implemented the proposed scheme on a field‐programmable gate array and compared its decoding speed with that of a conventional decoder. The results show an improvement of at least five fold for a single iteration of turbo decoding.     

An FPGA Implementation of High‐Speed Flexible 27‐Mbps 8‐StateTurbo Decoder

In this paper, we propose a flexible turbo decoding algorithm for a high order modulation scheme that uses a standard half‐rate turbo decoder designed for binary quadrature phase‐shift keying (B/QPSK) modulation. A transformation applied to the incoming I‐channel and Q‐channel symbols allows the use of an off‐the‐shelf B/QPSK turbo decoder without any modifications. Iterative codes such as turbo codes process the received symbols recursively to improve performance. As the number of iterations increases, the execution time and power consumption also increase. The proposed algorithm reduces the latency and power consumption by combination of the radix‐4, dual‐path processing, parallel decoding, and early‐stop algorithms. We implement the proposed scheme on a field‐programmable gate array and compare its decoding speed with that of a conventional decoder. The results show that the proposed flexible decoding algorithm is 6.4 times faster than the conventional scheme.     

High-performance VLSI architectures for turbo decoders with QPP interleaver

This paper analyses different VLSI architectures for 3GPP LTE/LTE-advanced turbo decoders for trade-offs in terms of throughput and area requirement. Data flow graphs for standard SISO MAP (maximum a posteriori) turbo decoder, SW – SISO MAP turbo decoder, PW SISO MAP turbo decoder have been presented, thus analysing their performance. Two variants of quadratic permutation polynomial (QPP) interleaver have been proposed which tend to simplify the complexity of ‘mod’ operator implementation and provide best compromise between area, delay and power dissipation. Implementation of decoder using one variant of QPP interleaver has also been discussed. A novel approach for area optimisation has been proposed to reduce required number of interleavers for parallel window turbo decoder. Multi-port memory has also been used for parallel turbo decoder. To increase the throughput without any effective increase in area complexity, circuit-level pipelining and retiming have been used. Proposed architectures have been synthesised using Synopsys Design Compiler using 45-nm CMOS technology.     

Highly-Parallel Decoding Architectures for Convolutional Turbo Codes

Highly parallel decoders for convolutional turbo codes have been studied by proposing two parallel decoding architectures and a design approach of parallel interleavers. To solve the memory conflict problem of extrinsic information in a parallel decoder, a block-like approach in which data is written row-by-row and read diagonal-wise is proposed for designing collision-free parallel interleavers. Furthermore, a warm-up-free parallel sliding window architecture is proposed for long turbo codes to maximize the decoding speeds of parallel decoders. The proposed architecture increases decoding speed by 6%-34% at a cost of a storage increase of 1% for an eight-parallel decoder. For short turbo codes (e.g., length of 512 bits), a warm-up-free parallel window architecture is proposed to double the speed at the cost of a hardware increase of 12%     

A 285-MHz pipelined MAP decoder in 0.18-/spl mu/m CMOS

Presented in this paper is a pipelined 285-MHz maximum a posteriori probability (MAP) decoder IC. The 8.7-mm/sup 2/ IC is implemented in a 1.8-V 0.18-/spl mu/m CMOS technology and consumes 330 mW at maximum frequency. The MAP decoder chip features a block-interleaved pipelined architecture, which enables the pipelining of the add-compare-select kernels. Measured results indicate that a turbo decoder based on the presented MAP decoder core can achieve: 1) a decoding throughput of 27.6 Mb/s with an energy-efficiency of 2.36 nJ/b/iter; 2) the highest clock frequency compared to existing 0.18-/spl mu/m designs with the smallest area; and 3) comparable throughput with an area reduction of 3-4.3/spl times/ with reference to a look-ahead based high-speed design (Radix-4 design), and a parallel architecture.     

APPLICATION OF TURBO CODES IN HIGH-SPEED REAL-TIME CHANNEL

I. Introduction Turbo code has obtained comprehensive atten-tion and research due to its near-Shannon perform-ance since it was proposed in 1993[1], and has be-come a research hotspot in information and coding theory area. Application and realization methods of turbo codes in various communication systems have also attracted great interest of researchers. The good BER performance of turbo codes provides it a wide application prospect in deep space and mobile com- munication systems. The IT…     

Modified Collision-Free Interleavers for High Speed Turbo Decoding

Inter-window shuffle (IWS) interleavers are a class of collision-free (CF) interleavers that have been applied to parallel turbo decoding. In this paper, we present modified IWS (M-IWS) interleavers that can further increase turbo decoding throughput only at the expense of slight performance degradation. By deriving the number of M-IWS interleavers, we demonstrate that the number is much smaller than that of IWS interleavers, whereas they both have a very simple algebraic representation. Further, it is shown by analysis that under given conditions, storage requirements of M-IWS interleavers can be reduced to only 368 storage bits for variable interleaving lengths. In order to realize parallel outputs of the on-line interleaving addresses, a low-complexity architecture design of M-IWS interleavers for parallel turbo decoding is proposed, which also supports variable interleaving lengths. Therefore, the M-IWS interleavers are very suitable for the turbo decoder in next generation communication systems with the high data rate and low latency requirements.     

Turbo Code译码方法的改进

在文章中，首先介绍Turbo码的基本编译码结构和它的译码算法MAP。在此基础上，尝试对MAP算法的循环译码的后向递推的起点以及循环译码结构的最终判决条件根据实际应用情况进行改进。将译码的后向递推的起点定义为译码的前向递推的终点，并且将每一轮译码结果进行加权相加，得到最后系统输出。最后，根据MATLAB仿真的结果论证改进后的算法能减少系统的误码率。     

A parallel decoder for low latency decoding of turbo product codes

There has been intensive focus on turbo product codes (TPCs) which have low decoding complexity and achieve near-optimum performances at low signal-to-noise ratios. Different than the original TPC decoder, which performs row and column decoding in a serial fashion, we propose a parallel decoder structure. Simulation results show that with this approach, decoding latency of TPCs can be halved while maintaining virtually the same performance level     

Implementation and performance of a turbo/MAP decoder

The implementation and performance of a turbo/MAP decoder are described. A serial block MAP decoder operating in the logarithm domain is used to obtain a very-high-performance turbo decoder. Programmable gate arrays and EPROMs allow the decoder to be programmed for almost any code from four to 512 states, rate 1/3 to rate 1/7 (higher rates are achieved with puncturing) and interleaver block sizes to 65,536 bits. Seven decoding stages were implemented in parallel. For rate 1/3 and 1/7 16-state codes with an interleaver size of 65,536 bits and operating at up to 356 kbit/s the codec achieved an E_b/N₀ of 0⋅32 and −0⋅30 dB respectively for a BER of 10⁻⁵. BERs down to 10⁻⁷ were also achieved for a small increase in E_b/N₀. An efficient implementation of a continuous MAP decoder is also presented, along with a synchronization technique for turbo decoders. © 1998 John Wiley & Sons, Ltd.     

Area-efficient high-throughput MAP decoder architectures

Iterative decoders such as turbo decoders have become integral components of modern broadband communication systems because of their ability to provide substantial coding gains. A key computational kernel in iterative decoders is the maximum a posteriori probability (MAP) decoder. The MAP decoder is recursive and complex, which makes high-speed implementations extremely difficult to realize. In this paper, we present block-interleaved pipelining (BIP) as a new high-throughput technique for MAP decoders. An area-efficient symbol-based BIP MAP decoder architecture is proposed by combining BIP with the well-known look-ahead computation. These architectures are compared with conventional parallel architectures in terms of speed-up, memory and logic complexity, and area. Compared to the parallel architecture, the BIP architecture provides the same speed-up with a reduction in logic complexity by a factor of M, where M is the level of parallelism. The symbol-based architecture provides a speed-up in the range from 1 to 2 with a logic complexity that grows exponentially with M and a state metric storage requirement that is reduced by a factor of M as compared to a parallel architecture. The symbol-based BIP architecture provides speed-up in the range M to 2M with an exponentially higher logic complexity and a reduced memory complexity compared to a parallel architecture. These high-throughput architectures are synthesized in a 2.5-V 0.25-/spl mu/m CMOS standard cell library and post-layout simulations are conducted. For turbo decoder applications, we find that the BIP architecture provides a throughput gain of 1.96 at the cost of 63% area overhead. For turbo equalizer applications, the symbol-based BIP architecture enables us to achieve a throughput gain of 1.79 with an area savings of 25%.     

基于无冲突多项式交织器的高速并行Turbo解码器

提出了基于高次多项式无冲突交织器的Turbo码并行解码的优化实现方法,解码器采用MAX-Log-MAP算法,完成了从Matlab算法设计验证到RTL设计、FPGA验证,并在LTE无线通信链路中验证.设计的Turbo并行高速解码器半次迭代的效率为6.9 bit/cycle,在最高迭代为5.5次、时钟频率为309MHz下,达到207Mb/s的吞吐率,满足高速无线通信系统的要求,交织和解交织采用存储器映射方法.该设计节约了计算电路和存储量.     

Turbo decoding of quantized data

Much of the work on turbo decoding assumes that the decoder has access to infinitely soft (unquantized) channel data. In practice, however, a quantizer is used at the receiver and the turbo decoder must operate on finite precision, quantized data. Hence, the maximum a posteriori (MAP) component decoder which was designed assuming infinitely soft data is not necessarily optimum when operating on quantized data. We modify the well-known normalized MAP algorithm taking into account the presence of the quantizer. This algorithm is optimum given any quantizer and is no more complex than quantized implementations of the MAP algorithm derived based on unquantized data. Simulation results on an additive white Gaussian noise channel show that, even with four bits of quantization, the new algorithm based on quantized data achieves a performance practically equal to the MAP algorithm operating on infinite precision data     

Efficient hardware implementation of a highly-parallel 3GPP LTE/LTE-advance turbo decoder

We present an efficient VLSI architecture for 3GPP LTE/LTE-Advance Turbo decoder by utilizing the algebraic-geometric properties of the quadratic permutation polynomial (QPP) interleaver. The high-throughput 3GPP LTE/LTE-Advance Turbo codes require a highly-parallel decoder architecture. Turbo interleaver is known to be the main obstacle to the decoder parallelism due to the collisions it introduces in accesses to memory. The QPP interleaver solves the memory contention issues when several MAP decoders are used in parallel to improve Turbo decoding throughput. In this paper, we propose a low-complexity QPP interleaving address generator and a multi-bank memory architecture to enable parallel Turbo decoding. Design trade-offs in terms of area and throughput efficiency are explored to find the optimal architecture. The proposed parallel Turbo decoder has been synthesized, placed and routed in a 65-nm CMOS technology with a core area of 8.3 mm² and a maximum clock frequency of 400 MHz. This parallel decoder, comprising 64 MAP decoder cores, can achieve a maximum decoding throughput of 1.28 Gbps at 6 iterations     

Stochastic analysis of turbo decoding

This paper proposes a stochastic framework for dynamic modeling and analysis of turbo decoding. By modeling the input and output signals of a turbo decoder as random processes, we prove that these signals become ergodic when the block size of the code becomes very large. This basic result allows us to easily model and compute the statistics of the signals in a turbo decoder. Using the ergodicity result and the fact that a sum of lognormal distributions is well approximated using a lognormal distribution, we show that the input-output signals in a turbo decoder, when expressed using log-likelihood ratios (LLRs), are well approximated using Gaussian distributions. Combining the two results above, we can model a turbo decoder using two input parameters and two output parameters (corresponding to the means and variances of the input and output signals). Using this model, we are able to reveal the whole dynamics of a decoding process. We have discovered that a typical decoding process is much more intricate than previously known, involving two regions of attraction, several fixed points, and a stable equilibrium manifold at which all decoding trajectories converge. Some applications of the stochastic framework are also discussed, including a fast decoding scheme     

Performance evaluation of superorthogonal turbo codes in AWGN andflat Rayleigh fading channels

Turbo codes are parallel concatenated codes whose performance in the additive white Gaussian noise (AWGN) channel has been shown to be near the theoretical limit. In this paper, we describe a low-rate superorthogonal turbo code that combines the principles of low-rate convolutional coding and that of parallel concatenation. Due to the bandwidth expansion, this code outperforms the ordinary turbo code both in AWGN and especially in fading channels. Thus, superorthogonal turbo codes are suited mainly for spread-spectrum applications. For the purposes of iterative decoding, we concisely describe the connection between the optimal maximum a posteriori symbol estimation and suboptimal soft-output decoding based on sequence estimation. The suboptimal decoder produces outputs that can directly be used as additive metrics at successive decoding iterations, without the need for estimating channel noise variance. Simulation results in AWGN and flat Rayleigh fading channels are also presented, along with analytical upper bounds of bit- and frame-error probabilities     

Turbo greedy multiuser detection

Previously, a novel scheme for iterative multiuser detection and turbo decoding was proposed by Damnjanovic and Vojcic (2000, 2001). In this scheme, multiuser detection and single-user turbo decoding are tightly coupled to maximize the overall gain. The extrinsic probabilities for the coded bits of the interfering users, obtained after each turbo decoding iteration, are used as a priori probabilities in the following multiuser iteration and the extrinsic information for the systematic bits of the desired user is used as a priori information in the next single-user turbo decoding iteration. Turbo decoding of parallel concatenated convolutional codes is carried out in parallel fashion. It has been shown that the proposed detector approaches the multiuser capacity limit within 1 dB in the low signal-to-noise ratio region. However, the main drawback of the scheme is its exponential complexity in the number of users, which is due to the complexity of the maximum a posteriori probability (MAP) multiuser detector. In this paper, we show that the complexity of the scheme can be significantly reduced by replacing the (MAP) multiuser detector with an iterative detector derived from the greedy multiuser detector proposed by AlRustamani and Vojcic (2000). In this paper, we demonstrate that, for both the additive white Gaussian noise and the frequency-nonselective Rayleigh fading, the substantial reduction in complexity of the iterative scheme proposed by Damnjanovic and Vojcic when the greedy detector is utilized introduces a slight degradation in performance