Iterative threshold decoding without interleaving for convolutional self-doubly orthogonal codes

A novel iterative error control technique based on the threshold decoding algorithm and new convolutional self-doubly orthogonal codes is proposed. It differs from parallel concatenated turbo decoding as it uses a single convolutional encoder, a single decoder and hence no interleaver, neither at encoding nor at decoding. Decoding is performed iteratively using a single threshold decoder at each iteration, thereby providing good tradeoff between complexity, latency and error performance.     

Systematic analysis of the decoding delay in multiview video

We present a framework for the analysis of the decoding delay in multiview video coding (MVC). We show that in real-time applications, an accurate estimation of the decoding delay is essential to achieve a minimum communication latency. As opposed to single-view codecs, the complexity of the multiview prediction structure and the parallel decoding of several views requires a systematic analysis of this decoding delay, which we solve using graph theory and a model of the decoder hardware architecture. Our framework assumes a decoder implementation in general purpose multi-core processors with multi-threading capabilities. For this hardware model, we show that frame processing times depend on the computational load of the decoder and we provide an iterative algorithm to compute jointly frame processing times and decoding delay. Finally, we show that decoding delay analysis can be applied to design decoders with the objective of minimizing the communication latency of the MVC system.     

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.     

Fast factorization architecture in soft-decision Reed-Solomon decoding

Reed-Solomon (RS) codes are among the most widely utilized block error-correcting codes in modern communication and computer systems. Compared to its hard-decision counterpart, soft-decision decoding offers considerably higher error-correcting capability. The recent development of soft-decision RS decoding algorithms makes their hardware implementations feasible. Among these algorithms, the Koetter-Vardy (KV) algorithm can achieve substantial coding gain for high-rate RS codes, while maintaining a polynomial complexity with respect to the code length. In the KV algorithm, the factorization step can consume a major part of the decoding latency. A novel architecture based on root-order prediction is proposed in this paper to speed up the factorization step. As a result, the time-consuming exhaustive-search-based root computation in each iteration level, except the first one, of the factorization step is circumvented with more than 99% probability. Using the proposed architecture, a speedup of 141% can be achieved over prior efforts for a (255, 239) RS code, while the area consumption is reduced to 31.4%.     

FPGA implementation of low complexity LDPC iterative decoder

Low-density parity-check (LDPC) codes, proposed by Gallager, emerged as a class of codes which can yield very good performance on the additive white Gaussian noise channel as well as on the binary symmetric channel. LDPC codes have gained lots of importance due to their capacity achieving property and excellent performance in the noisy channel. Belief propagation (BP) algorithm and its approximations, most notably min-sum, are popular iterative decoding algorithms used for LDPC and turbo codes. The trade-off between the hardware complexity and the decoding throughput is a critical factor in the implementation of the practical decoder. This article presents introduction to LDPC codes and its various decoding algorithms followed by realisation of LDPC decoder by using simplified message passing algorithm and partially parallel decoder architecture. Simplified message passing algorithm has been proposed for trade-off between low decoding complexity and decoder performance. It greatly reduces the routing and check node complexity of the decoder. Partially parallel decoder architecture possesses high speed and reduced complexity. The improved design of the decoder possesses a maximum symbol throughput of 92.95 Mbps and a maximum of 18 decoding iterations. The article presents implementation of 9216 bits, rate-1/2, (3, 6) LDPC decoder on Xilinx XC3D3400A device from Spartan-3A DSP family.     

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     

Efficient VLSI Architecture for Soft-Decision Decoding of Reed–Solomon Codes

Reed–Solomon (RS) codes have very broad applications in digital communication and storage systems. The recently developed algebraic soft-decision decoding (ASD) algorithms of RS codes can achieve substantial coding gain with polynomial complexity. Among the ASD algorithms with practical multiplicity assignment schemes, the bit-level generalized minimum distance (BGMD) decoding algorithm can achieve similar or higher coding gain with lower complexity. ASD algorithms consist of two major steps: the interpolation and the factorization. In this paper, novel architectures for both steps are proposed for the BGMD decoder. The interpolation architecture is based on the newly proposed Lee-O'Sullivan (LO) algorithm. By exploiting the characteristics of the LO algorithm and the multiplicity assignment scheme in the BGMD decoder, the proposed interpolation architecture for a (255, 239) RS code can achieve 25% higher efficiency in terms of speed/area ratio than prior efforts. Root computation over finite fields and polynomial updating are the two main steps of the factorization. A low-latency and prediction-free scheme is introduced in this paper for the root computation in the BGMD decoder. In addition, novel coefficient storage schemes and parallel processing architectures are developed to reduce the latency of the polynomial updating. The proposed factorization architecture is 126% more efficient than the previous direct root computation factorization architecture.      

Threshold values and convergence properties of majority-based algorithms for decoding regular low-density parity-check codes

This work presents a detailed study of a family of binary message-passing decoding algorithms for low-density parity-check (LDPC) codes, referred to as "majority-based algorithms." Both Gallager's algorithm A (G/sub A/) and the standard majority decoding algorithm belong to this family. These algorithms, which are, in fact, the building blocks of Gallager's algorithm B (G/sub B/), work based on a generalized majority-decision rule and are particularly attractive for their remarkably simple implementation. We investigate the dynamics of these algorithms using density evolution and compute their (noise) threshold values for regular LDPC codes over the binary symmetric channel. For certain ensembles of codes and certain orders of majority-based algorithms, we show that the threshold value can be characterized as the smallest positive root of a polynomial, and thus can be determined analytically. We also study the convergence properties of majority-based algorithms, including their (convergence) speed. Our analysis shows that the stand-alone version of some of these algorithms provides significantly better performance and/or convergence speed compared with G/sub A/. In particular, it is shown that for channel parameters below threshold, while for G/sub A/ the error probability converges to zero exponentially with iteration number, this convergence for other majority-based algorithms is super-exponential.     

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.     

基于陷阱检测的咬尾卷积码译码算法

该文分析了循环维特比算法(CVA)中存在的循环陷阱问题,并证明了传统基于CVA的咬尾卷积码译码算法中存在的不足,提出了一种高效率的咬尾卷积码译码算法。该算法通过检测两次不同迭代中获得的两条最大似然路径是否相同来判断是否有循环陷阱产生,并及时终止循环,减少冗余迭代;在没有循环陷阱产生的情况下,新算法比较当前迭代中最大似然路径和已经发现的最优咬尾路径是否相同来自适应终止迭代。文中对循环陷阱检测方案和自适应终止方案做了进一步优化,即利用路径的净增量而非路径本身作为检测量。实验结果表明新算法提高了译码效率,降低了译码复杂度。     

Generalization of chase algorithms for soft decision decoding of binary linear codes

Soft decision decoding of binary linear block codes transmitted over the additive white Gaussian channel (AWGN) using antipodal signaling is considered. A set of decoding algorithms called generalized Chase algorithms is proposed. In contrast to Chase algorithms, which require alfloor (d- 1)/2 rfloorbinary error-correcting decoder for decoding a binary linear block code of minimum distanced, the generalized Chase algorithms can use a binary decoder that can correct less thanlfloor ( d - 1)/2 rfloorhard errors. The Chase algorithms are particular cases of the generalized Chase algorithms. The performance of all proposed algorithms is asymptotically optimum for high signal-to-noise ratio (SNR). Simulation results for the(47, 23)quadratic residue code indicate that even for low SNR the performance level of a maximum likelihood decoder can be approached by a relatively simple decoding procedure.     

IRA码最小和译码算法的改进算法

研究了重复累积(IRA)码的简化译码算法.IRA码的BP译码算法具有较高的复杂度,为了降低复杂度,首先提出将最小和算法应用于IRA码.然而,最小和算法使译码性能降低约1.2 dB.为了在复杂度和译码复杂度之间取得较好的折衷,提出了对IRA码的最小和算法的改进算法:归一化算法和偏移算法.仿真结果表明,IRA码归一化算法和偏移算法在复杂度略有增加的情况下,性能得到明显改善.     

基于VHDL的TPC译码器设计

Turbo乘积码是一种性能卓越的前向纠错码,具有译码复杂度低,且在低信噪比时可以获得近似最优的性能。介绍基于Chase算法的Turbo乘积码软入软出（SISO）迭代译码算法,提出基于VHDL硬件描述语言的TPC译码器设计方案,并在FPGA芯片上进行了仿真和验证。仿真结果证明该译码器有很大的实用性和灵活性。     

An efficient method for determining economical configurations ofelementary packet-switched networks

The packet-switched network design problem can be formulated as a capacity and flow assignment (CFA) problem. The CFA problem is investigated for an elementary network consisting of one tandem switch and n local switches. It is regarded as the structural unit of a hierarchical network. It is assumed that any line speed is available and the cost of each line is a linear function of its speed with a fixed charge for installation. This CFA problem is shown to be equivalent to a 0-1 integer programming problem with a discontinuous cost function. A threshold rule and a row-wise or column-wise improvement (RCI) iteration are proposed to solve the problem. The threshold rule assigns all the traffic between two local switches to a direct route if the required traffic exceeds a predetermined threshold value, and otherwise to a tandem route. The RCI iteration searches the vertices of the unit cube of 2n-dimensional Euclidean space by a procedure roughly like the simplex method. Whenever the network has external traffic, direct application of the threshold rule ensures a global optimum. When there is no external traffic, a simple modification of the RCI iteration yields almost a global optimum within 2n steps     

Efficient Generalized Minimum-distance Decoders of Reed-Solomon Codes

Generalized minimum distance (GMD) decoding of Reed–Solomon (RS) codes can correct more errors than conventional hard-decision decoding by running error-and-erasure decoding multiple times for different erasure patterns. The latency of the GMD decoding can be reduced by the Kötter’s one-pass decoding scheme. This scheme first carries out an error-only hard-decision decoding. Then all pairs of error-erasure locators and evaluators are derived iteratively in one run based on the result of the error-only decoding. In this paper, a more efficient interpolation-based one-pass GMD decoding scheme is studied. Applying the re-encoding and coordinate transformation, the result of erasure-only decoding can be directly derived. Then the locator and evaluator pairs for other erasure patterns are generated iteratively by applying interpolation. A simplified polynomial selection scheme is proposed to pass only one pair of locator and evaluator to successive decoding steps and a low-complexity parallel Chien search architecture is developed to implement this selection scheme. With the proposed polynomial selection architecture, the interpolation can run at the full speed to greatly increase the throughput. After efficient architectures and effective optimizations are employed, a generalized hardware complexity analysis is provided for the proposed interpolation-based decoder. For a (255, 239) RS code, the high-speed interpolation-based one-pass GMD decoder can achieve 53% higher throughput than the Kötter’s decoder with slightly more hardware requirement. In terms of speed-over-area ratio, our design is 51% more efficient. In addition, compared to other soft-decision decoders, the high-speed interpolation-based GMD decoder can achieve better performance-complexity tradeoff.     

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.     

A Dynamic Hybrid Decoder Apprroach Using EG-LDPC Codes for Signal Processing Applications

The Low-Density Parity Check (LDPC) codes of Euclidean Geometry (EG) are encrypted and decrypted in numerous ways, namely Soft Bit Flipping (SBF), Sequential Peeling Decoder (SPD), Belief Propagation Decoder (BPD), Majority Logic Decoder/Detector (MLDD), and Parallel Peeling Decoder (PPD) decoding algorithms. These algorithms provide aextensive range of trade-offs between latency decoding, power consumption, hardware complexity-required resources, and error rate performance. Therefore, the problem is to communicate a sophisticated technique specifying the both soft and burst errors for effective information transmission. In this research, projected a technique named as Hybrid SBF (HSBF) decoder for EG-LDPC codes, which reduces the decoding complexity and maximizes the signal transmission and reception. In this paper, HSBF is also known as Self Reliability based Weighted Soft Bit Flipping (SRWSBF) Decoder. It is obvious from the outcomes that the proposed technique is better than the decoding algorithms SBF, MLDD, BPD, SPD and PPD. Using Xilinx synthesis and SPARTAN 3e, a simulation model is designed to investigate latency, hardware utilization and power consumption. Average latency of 16.65 percent is found to be reduced. It is observed that in considered synthesis parameters such as number of 4-input LUTs, number of slices, and number of bonded IOBs, excluding number of slice Flip-Flops, hardware utilization is minimized to an average of 4.25 percent. The number of slices Flip-Flops resource use in the proposed HSBF decoding algorithm is slightly higher than other decoding algorithms, i.e. 1.85%. It is noted that, over the decoding algorithms considered in this study, the proposed research study minimizes power consumption by an average of 41.68%. These algorithms are used in multimedia applications, processing systems for security and information.

     

Turbo码高速译码器设计

Turbo码具有优良的纠错性能,被认为是最接近香农限的纠错码之一,并被多个通信行业标准所采用。Turbo码译码算法相比于编码算法要复杂得多,同时其采用迭代译码方式,以上2个原因使得Turbo码译码器硬件实现复杂,而且译码速度非常有限。从Turbo码高速译码器硬件实现出发,介绍Turbo码迭代译码的硬件快速实现算法以及流水线译码方式,并介绍利用Altera的Flex10k10E芯片实现该高速译码器硬件架构。测试和仿真结果表明,该高速译码器具有较高的译码速度和良好的译码性能。     

Reduced-Complexity Turbo Equalization for Turbo Coded MIMO/OFDM Systems

1IntroductionTowards wireless systems Beyondthe3G(B3G),it isa great challenge for the physical layer to support high-speed transmissioninthe mobile environment to providecomfortable Internet access.Multiple Input MultipleOutput(MI MO)technique is effectiv…     

An effective simplifying scheme for Viterbi decoder

A Viterbi decoding algorithm with a scarce-state transition-type circuit configuration, namely the probability selecting states (PSS) mode decoder, is presented. The algorithm has reduced complexity compared to a conventional Viterbi decoder. It is shown that this method has three advantages over the general Viterbi algorithm: it is suitable to the quick look-in code, it applies the optimum decoding in a PSS-type decoder, and it makes full use of the likelihood concentration property. The bit-error-rate (BER) performance of a r=1/2, k=7 (147,135) code and PSS-type Viterbi decoder approximates the optimum performance of the standard Viterbi decoder and reduces the hardware of the conventional Viterbi decoder to about half