The equivalence of L-step orthogonalization and a Reed decoding procedure (Corresp.)

This correspondence shows the formal equivalence between Massey's decoding scheme called threshold decoding involvingL-step orthogonalizable codes and Reed's decoding scheme originally conceived for the Muller codes. Upon examining these two decoding algorithms it is shown that each can be described in terms of a decoding logic circuit. The formal equivalence of the algorithms is proved by showing the formal equivalence of their respective decoding circuits.     

基于FPGA的LDPC码编译码器联合设计

该文通过对低密度校验(LDPC)码的编译码过程进行分析,提出了一种基于FPGA的LDPC码编译码器联合设计方法,该方法使编码器和译码器共用同一校验计算电路和复用相同的RAM存储块,有效减少了硬件资源的消耗量。该方法适合于采用校验矩阵进行编码和译码的情况,不仅适用于全并行的编译码器结构,同时也适用于目前广泛采用的部分并行结构,且能够使用和积、最小和等多种译码算法。采用该方法对两组不同的LDPC码进行部分并行结构的编译码器联合设计,在Xilinx XC4VLX80 FPGA上的实现结果表明,设计得到的编码器和译码器可并行工作,且仅占用略多于单个译码器的硬件资源,提出的设计方法能够在不降低吞吐量的同时有效减少系统对硬件资源的需求。     

Codes defined on graphs

Low-density parity-check codes, turbo codes, and indeed most practically decodable capacity-approaching error correcting codes can all be understood as codes defined on graphs. Graphs not only describe the codes, but, more important, they structure the operation of the sum-product decoding algorithm (or one of many possible variations), which can be used for iterative decoding. Such coding schemes have the potential to approach channel capacity, while maintaining reasonable decoding complexity. In this tutorial article we review factor graphs, which can be used to describe codes and the joint probability distributions that must be dealt with in decoding. We also review the sum-product algorithm, and show how this algorithm leads to iterative decoding algorithms for codes defined on graphs.     

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.     

准循环LDPC码的两种典型快速译码算法研究

该文从译码速率、硬件实现的复杂度和误码率3个方面对比研究了两种典型的高速译码算法:Turbo型和积算法与并行加权比特翻转算法。以准循环LDPC码为对象,给出了Turbo型和积算法和并行加权比特翻转算法的实现时序、硬件复杂度以及误码率性能,其中,并行加权比特翻转算法的高效时序结构是首次给出的。计算机仿真结果表明,这两种算法都能够在迭代次数较少时取得良好的性能。     

Gear-Shift Decoding

This paper considers a class of iterative message-passing decoders for low-density parity-check codes in which the decoder can choose its decoding rule from a set of decoding algorithms at each iteration. Each available decoding algorithm may have different per-iteration computation time and performance. With an appropriate choice of algorithm at each iteration, overall decoding latency can be reduced significantly, compared with standard decoding methods. Such a decoder is called a gear-shift decoder because it changes its decoding rule (shifts gears) in order to guarantee both convergence and maximum decoding speed (minimum decoding latency). Using extrinsic information transfer charts, the problem of finding the optimum (minimum decoding latency) gear-shift decoder is formulated as a computationally tractable dynamic program. The optimum gear-shift decoder is proved to have a decoding threshold equal to or better than the best decoding threshold among those of the available algorithms. In addition to speeding up software decoder implementations, gear-shift decoding can be applied to optimize a pipelined hardware decoder, minimizing hardware cost for a given decoder throughput.     

Dynamics and performance analysis of analog iterative decoding for low-density parity-check (LDPC) codes

Conventional iterative decoding with flooding or parallel schedule can be formulated as a fixed-point problem solved iteratively by a successive substitution (SS) method. In this paper, we investigate the dynamics of a continuous-time (asynchronous) analog implementation of iterative decoding, and show that it can be approximated as the application of the well-known successive relaxation (SR) method for solving the fixed-point problem. We observe that SR with the optimal relaxation factor can considerably improve the error-rate performance of iterative decoding for short low-density parity-check (LDPC) codes, compared with SS. Our simulation results for the application of SR to belief propagation (sum-product) and min-sum algorithms demonstrate improvements of up to about 0.7 dB over the standard SS for randomly constructed LDPC codes. The improvement in performance increases with the maximum number of iterations, and by accordingly reducing the relaxation factor. The asymptotic result, corresponding to an infinite maximum number of iterations and infinitesimal relaxation factor, represents the steady-state performance of analog iterative decoding. This means that under ideal circumstances, continuous-time (asynchronous) analog decoders can outperform their discrete-time (synchronous) digital counterparts by a large margin. Our results also indicate that with the assumption of a truncated Gaussian distribution for the random delays among computational modules, the error-rate performance of the analog decoder, particularly in steady state, is rather independent of the variance of the distribution. The proposed simple model for analog decoding, and the associated performance curves, can be used as an "ideal analog decoder" benchmark for performance evaluation of analog decoding circuits.     

Modified majority logic decoding of cyclic codes in hybrid-ARQsystems

Reliability information provided by sets of orthogonal check sums in a majority logic decoder for block codes is used in a type-I hybrid automatic-repeat-request (ARQ) error control scheme. The reliability information is obtained through a simple modification of the majority logic decoding rule. It is shown that the reliability performance of Reed-Muller and other majority logic decodable codes can be substantially improved at the expense of a very small reduction in throughput. The simplicity of the decoding circuit permits implementation in systems with very high data rates     

A 0.18-$muhbox m$CMOS Analog Min-Sum Iterative Decoder for a (32,8) Low-Density Parity-Check (LDPC) Code

Current-mode circuits are presented for implementing analog min-sum (MS) iterative decoders. These decoders are used to efficiently decode the best known error correcting codes such as low-density parity-check (LDPC) codes and turbo codes. The proposed circuits are devised based on current mirrors, and thus, in any fabrication technology that accurate current mirrors can be designed, analog MS decoders can be implemented. The functionality of the proposed circuits is verified by implementing an analog MS decoder for a (32,8) LDPC code in a 0.18-mum CMOS technology. This decoder is the first reported analog MS decoder. For low signal to noise ratios where the circuit imperfections are dominated by the noise of the channel, the measured error correcting performance of this chip in steady-state condition surpasses that of the conventional floating-point discrete-time synchronous MS decoder. When data throughput is 6 Mb/s, loss in the coding gain compared to the conventional MS decoder at BER of 10^-3 is about 0.3 dB and power consumption is about 5 mW. This is the first time that an analog decoder has been successfully tested for an LDPC code, though a short one     

Application of circulant matrices to the construction and decodingof linear codes

The Fourier transform technique is used to analyze and construct several families of double-circulant codes. The minimum distance of the resulting codes is lower-bounded by 2√r and can be decoded easily employing the standard BCH decoding algorithm or the majority-logic decoder of Reed-Muller codes. A decoding procedure for Reed-Solomon codes is presented, based on a representation of the parity-check matrix by circulant blocks. The decoding procedure inherits both the (relatively low) time complexity of the Berlekamp-Massey algorithm and the hardware simplicity characteristic of Blahut's algorithm. The procedure makes use of the encoding circuit together with a reduced version of Blahut's decoder     

Design and performance of turbo Gallager codes

The most powerful channel-coding schemes, namely, those based on turbo codes and low-density parity-check (LDPC) Gallager codes, have in common the principle of iterative decoding. However, the relative coding structures and decoding algorithms are substantially different. This paper shows that recently proposed novel coding structures bridge the gap between these two schemes. In fact, with properly chosen component convolutional codes, a turbo code can be successfully decoded by means of the decoding algorithm used for LDPC codes, i.e., the belief-propagation algorithm working on the code Tanner graph. These new turbo codes are here nicknamed "turbo Gallager codes." Besides being interesting from a conceptual viewpoint, these schemes are important on the practical side because they can be decoded in a fully parallel manner. In addition to the encoding complexity advantage of turbo codes, the low decoding complexity allows the design of very efficient channel-coding schemes.     

Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal Redundancy

In this paper, we present error-correcting codes that achieve the information-theoretically best possible tradeoff between the rate and error-correction radius. Specifically, for every 0 < R < 1 and epsiv < 0, we present an explicit construction of error-correcting codes of rate that can be list decoded in polynomial time up to a fraction (1- R - epsiv) of worst-case errors. At least theoretically, this meets one of the central challenges in algorithmic coding theory. Our codes are simple to describe: they are folded Reed-Solomon codes, which are in fact exactly Reed-Solomon (RS) codes, but viewed as a code over a larger alphabet by careful bundling of codeword symbols. Given the ubiquity of RS codes, this is an appealing feature of our result, and in fact our methods directly yield better decoding algorithms for RS codes when errors occur in phased bursts. The alphabet size of these folded RS codes is polynomial in the block length. We are able to reduce this to a constant (depending on epsiv) using existing ideas concerning ldquolist recoveryrdquo and expander-based codes. Concatenating the folded RS codes with suitable inner codes, we get binary codes that can be efficiently decoded up to twice the radius achieved by the standard GMD decoding.     

High-Speed Interpolation Architecture for Soft-Decision Decoding of Reed–Solomon Codes

Algebraic soft-decision decoding of Reed-Solomon (RS) codes delivers promising coding gains over conventional hard-decision decoding. The most computationally demanding step in soft-decision decoding of RS codes is bivariate polynomial interpolation. In this paper, we present a hybrid data format-based interpolation architecture that is well suited for high-speed implementation of the soft-decision decoders. It will be shown that this architecture is highly scalable and can be extensively pipelined. It also enables maximum overlap in time for computations at adjacent iterations. It is estimated that the proposed architecture can achieve significantly higher throughput than conventional designs with equivalent or lower hardware complexity     

Pattern-Flipping Chase-Type Decoders with Error Pattern Extracting Viterbi Algorithm over Partial Response Channels

Towards the goal of achieving better error correction performance in data storage systems, iterative soft decoding of low density parity check (LDPC) codes and soft-decision decoding of Reed-Solomon (RS) codes have started receiving increasing research attention. However, even with increased computing power, complexities of soft-decision decoding algorithms are still too high for real products which require high throughput and small hardware area. Another problem is that the performance gains of those approaches are smaller for magnetic recording channels than they are for memoryless additive white Gaussian noise (AWGN) channels. We propose a new soft-decision decoding algorithm (based on the Chase algorithm), which takes advantage of pattern reliability instead of symbol reliability or bit reliability. We also present a modified Viterbi algorithm that provides probable error patterns with corresponding reliabilities. Simulation results of the proposed algorithms over the partial response (PR) channel show attractive performance gains. The proposed algorithm dramatically reduces the number of iterations compared to the conventional Chase2 algorithm over the PR channel.     

Application of orthogonal codes to the calibration of active phasedarray antennas for communication satellites

This work describes two algorithms designed for remote calibration of an N_c-element active phased-array antenna. These algorithms involve transmission of N⩾N_c time multiplexed orthogonal encoded signals. The received signals are coherently detected, accumulated in vector forms, and decoded with the inverse of the orthogonal encoding matrix. The unitary transform encoding (UTE) algorithm is most suited for digital beamforming as it requires additional encoding hardware for an analog implementation. The control circuit encoding (CCE) algorithm is ideally suited for analog beamformers as it requires no additional encoding hardware. The CCE method encodes phased-array elemental signals using a Hadamard matrix to control the switching of intrinsic phase shifter delay circuits. The UTE and CCE algorithms can reduce the average measurement integration times for the complete set of calibration parameters by ~N_c relative to the corresponding values for single-element calibration procedures. This is significant for satellite systems as calibration must be performed in a short enough time window that the process can be treated as being stationary. Proofs are given that the orthogonal codes satisfy the mathematical lower bounds for the asymptotic forms of calibration parameter estimation variances     

一种低迭代次数的极化码置信传播译码算法

针对置信传播(Belief Propagation,BP)译码算法在迭代次数较多时吞吐量和译码时延性能提升受限的问题,提出了一种低迭代次数的极化码BP译码算法,通过采用比特翻转和子信道冻结的方式,降低译码过程中的迭代次数.仿真结果表明,相对于传统极化码BP译码算法(设置最大迭代次数为40次),所提算法在信噪比为3 dB...     

On algebraic soft-decision decoding algorithms for BCH codes

Three algebraic soft-decision decoding algorithms are presented for binary Bose-Chaudhuri-Hocquengham (BCH) codes. Two of these algorithms are based on the bounded distance (BD)+1 generalized minimum-distance (GMD) decoding presented by Berlekamp (1984), and the other is based on Chase (1972) decoding. A simple algebraic algorithm is first introduced, and it forms a common basis for the decoding algorithms presented. Next, efficient BD+1 GMD and BD+2 GMD decoding algorithms are presented. It is shown that, for binary BCH codes with odd designed-minimum-distance d and length n, both the BD+1 GMD and the BD+2 GMD decoding algorithms can be performed with complexity O(nd). The error performance of these decoding algorithms is shown to be significantly superior to that of conventional GMD decoding by computer simulation. Finally, an efficient algorithm is presented for Chase decoding of binary BCH codes. Like a one-pass GMD decoding algorithm, this algorithm produces all necessary error-locator polynomials for Chase decoding in one run     

LDPC码的级联译码算法的改进与实现

针对中短码长中LDPC码的OSD串行级联译码算法,给出了一种FPGA实现方案。该方案基于FPGA芯片中的块RAM资源,实现了OSD译码中GF(2)上的高斯消元算法,避免了其对逻辑资源的大量消耗。结果表明,该实现方案可在中低端FPGA上实现500 kbit·s^-1吞吐量的LDPC码OSD串行级联译码器。     

Turbo码译码性能的研究

Turbo码基于随机编码的思想,将卷积编码与交织器结合使其性能接近香农极限,所以Turbo码被3G移动通信系统所采纳并在深海通信、卫星通信等功率受限领域得以应用.文中介绍了Turbo码的译码原理并分析了几种主要的译码方法,在Matlab环境下对Turbo码进行了仿真研究,分析了不同的迭代次数、译码算法、帧长、码率及分量码对其译码性能的影响.仿真结果表明Turbo码纠错性能优良,具有广泛的应用前景.     

Memory-Efficient and High-Throughput Decoding of Quasi-Cyclic LDPC Codes

We propose turbo-sum-product (TSP) and shuffled-sum-product (SSP) decoding algorithms for quasi-cyclic low-density parity-check codes, which not only achieve faster convergence and better error performance than the sum-product algorithm, but also require less memory in partly parallel decoder architectures. Compared with the turbo decoding algorithm, our TSP algorithm saves the same amount of memory and may achieve a higher decoding throughput. The convergence behaviors of our TSP and SSP algorithms are also compared with those of the SP, turbo, and shuffled algorithms by their extrinsic information transfer (EXIT) charts.