Analysis of Connections Between Pseudocodewords

The role of pseudocodewords in causing non-codeword outputs in linear programming decoding, graph cover decoding, and iterative message-passing decoding is investigated. The three main types of pseudocodewords in the literature—linear programming pseudocodewords, graph cover pseudocodewords, and computation tree pseudocodewords—are reviewed and connections between them are explored. Some discrepancies in the literature on minimal and irreducible pseudocodewords are highlighted and clarified, and the minimal degree cover necessary to realize a pseudocodeword is found. Additionally, some conditions for the existence of connected realizations of graph cover pseudocodewords are given. This allows for further analysis of when graph cover pseudocodewords induce computation tree pseudocodewords. Finally, an example is offered that shows that existing theories on the distinction between graph cover pseudocodewords and computation tree pseudocodewords are incomplete.      

LP Decoding Corrects a Constant Fraction of Errors

We show that for low-density parity-check (LDPC) codes whose Tanner graphs have sufficient expansion, the linear programming (LP) decoder of Feldman, Karger, and Wainwright can correct a constant fraction of errors. A random graph will have sufficient expansion with high probability, and recent work shows that such graphs can be constructed efficiently. A key element of our method is the use of a dual witness: a zero-valued dual solution to the decoding linear program whose existence proves decoding success. We show that as long as no more than a certain constant fraction of the bits are flipped by the channel, we can find a dual witness. This new method can be used for proving bounds on the performance of any LP decoder, even in a probabilistic setting. Our result implies that the word error rate of the LP decoder decreases exponentially in the code length under the binary-symmetric channel (BSC). This is the first such error bound for LDPC codes using an analysis based on "pseudocodewords." Recent work by Koetter and Vontobel shows that LP decoding and min-sum decoding of LDPC codes are closely related by the "graph cover" structure of their pseudocodewords; in their terminology, our result implies that that there exist families of LDPC codes where the minimum BSC pseudoweight grows linearly in the block length     

An Efficient Pseudocodeword Search Algorithm for Linear Programming Decoding of LDPC Codes

In linear programming (LP) decoding of a low-density parity-check (LDPC) code one minimizes a linear functional, with coefficients related to log-likelihood ratios, over a relaxation of the polytope spanned by the codewords. In order to quantify LP decoding it is important to study vertexes of the relaxed polytope, so-called pseudocodewords. We propose a technique to heuristcally create a list of pseudocodewords close to the zero codeword and their distances. Our pseudocodeword-search algorithm starts by randomly choosing configuration of the noise. The configuration is modified through a discrete number of steps. Each step consists of two substeps: one applies an LP decoder to the noise-configuration deriving a pseudocodeword, and then finds configuration of the noise equidistant from the pseudocodeword and the zero codeword. The resulting noise configuration is used as an entry for the next step. The iterations converge rapidly to a pseudocodeword neighboring the zero codeword. Repeated many times, this procedure is characterized by the distribution function of the pseudocodeword effective distance. The efficiency of the procedure is demonstrated on examples of the Tanner code and Margulis codes operating over an additive white Gaussian noise (AWGN) channel.     

Using linear programming to Decode Binary linear codes

A new method is given for performing approximate maximum-likelihood (ML) decoding of an arbitrary binary linear code based on observations received from any discrete memoryless symmetric channel. The decoding algorithm is based on a linear programming (LP) relaxation that is defined by a factor graph or parity-check representation of the code. The resulting "LP decoder" generalizes our previous work on turbo-like codes. A precise combinatorial characterization of when the LP decoder succeeds is provided, based on pseudocodewords associated with the factor graph. Our definition of a pseudocodeword unifies other such notions known for iterative algorithms, including "stopping sets," "irreducible closed walks," "trellis cycles," "deviation sets," and "graph covers." The fractional distance d/sub frac/ of a code is introduced, which is a lower bound on the classical distance. It is shown that the efficient LP decoder will correct up to /spl lceil/d/sub frac//2/spl rceil/-1 errors and that there are codes with d/sub frac/=/spl Omega/(n/sup 1-/spl epsi//). An efficient algorithm to compute the fractional distance is presented. Experimental evidence shows a similar performance on low-density parity-check (LDPC) codes between LP decoding and the min-sum and sum-product algorithms. Methods for tightening the LP relaxation to improve performance are also provided.     

Guessing Facets: Polytope Structure and Improved LP Decoder

We investigate the structure of the polytope underlying the linear programming (LP) decoder introduced by Feldman, Karger, and Wainwright. We first show that for expander codes, every fractional pseudocodeword always has at least a constant fraction of nonintegral bits. We then prove that for expander codes, the active set of any fractional pseudocodeword is smaller by a constant fraction than that of any codeword. We further exploit these geometrical properties to devise an improved decoding algorithm with the same order of complexity as LP decoding that provably performs better. The method is very simple: it first applies ordinary LP decoding, and when it fails, it proceeds by guessing facets of the polytope, and then resolving the linear program on these facets. While the LP decoder succeeds only if the ML codeword has the highest likelihood over all pseudocodewords, we prove that the proposed algorithm, when applied to suitable expander codes, succeeds unless there exists a certain number of pseudocodewords, all adjacent to the ML codeword on the LP decoding polytope, and with higher likelihood than the ML codeword. We then describe an extended algorithm, still with polynomial complexity, that succeeds as long as there are at most polynomially many pseudocodewords above the ML codeword.     

有限平面LDPC码的停止集

有限平面LDPC码是一类重要的有结构的LDPC码,在利用和积算法(SPA)等迭代译码方法进行译码时表现出卓越的纠错性能。众所周知,次优的迭代译码不是最大似然译码,因而如何对迭代译码的性能进行理论分析一直是LDPC码的核心问题之一。近几年来,Tanner图上的停止集(stopping set)和停止距离(stopping distance)由于其在迭代译码性能分析中的重要作用而引起人们的重视。该文通过分析有限平面LDPC码的停止集和停止距离,从理论上证明了有限平面LDPC码的最小停止集一定是最小重量码字的支撑,从而对有限平面LDPC码在迭代译码下的良好性能给出了理论解释。     

Signal-space characterization of iterative decoding

By tracing the flow of computations in the iterative decoders for low-density parity-check codes, we formulate a signal-space view for a finite number of iterations in a finite-length code. On a Gaussian channel, maximum a posteriori (MAP) codeword decoding (or “maximum-likelihood decoding”) decodes to the codeword signal that is closest to the channel output in Euclidean distance. In contrast, we show that iterative decoding decodes to the “pseudosignal” that has highest correlation with the channel output. The set of pseudosignals corresponds to “pseudocodewords”, only a vanishingly small number of which correspond to codewords. We show that some pseudocodewords cause decoding errors, but that there are also pseudocodewords that frequently correct the deleterious effects of other pseudocodewords     

Regular Low-Density Parity-Check codes based on shifted identity matrices

This paper extends the class of Low-Density Parity-Check （LDPC） codes that can be constructed from shifted identity matrices. To construct regular LDPC codes, a new method is proposed. Two simple inequations are adopted to avoid the short cycles in Tanner graph, which makes the girth of Tanner graphs at least 8. Because their parity-check matrices are made up of circulant matrices, the new codes are quasi-cyclic codes. They perform well with iterative decoding.     

On the stopping distance of finite geometry LDPC codes

In this letter, the stopping sets and stopping distance of finite geometry LDPC (FG-LDPC) codes are studied. It is known that FG-LDPC codes are majority-logic decodable and a lower bound on the minimum distance can be thus obtained. It is shown in this letter that this lower bound on the minimum distance of FG-LDPC codes is also a lower bound on the stopping distance of FG-LDPC codes, which implies that FG-LDPC codes have considerably large stopping distance. This may explain in one respect why some FG-LDPC codes perform well with iterative decoding in spite of having many cycles of length 4 in their Tanner graphs.     

Combinatorial Interleavers for Systematic Regular Repeat-Accumulate Codes [Transactions Letters]

This paper proposes novel interleaver and accumulator structures for systematic, regular repeat-accumulate (RA) codes. It is well known that such codes are amenable to iterative (sum-product) decoding on the Tanner graph of the code, yet are as readily encodable as turbo codes. In this paper, interleavers for RA codes are designed using combinatorial techniques as a basis for deterministic interleaver constructions, yielding RA codes whose Tanner graphs are free of 4-cycles. Further, a generalized RA code accumulator structure is proposed, leading to codes, termed w3RA codes, whose parity-check matrices have many fewer weight-2 columns than conventional RA codes. The w3RA codes retain the low-complexity encoding of conventional RA codes and exhibit improved error-floor performance.     

A class of low-density parity-check codes constructed based on Reed-Solomon codes with two information symbols

This letter presents an algebraic method for constructing regular low-density parity-check (LDPC) codes based on Reed-Solomon codes with two information symbols. The construction method results in a class of LDPC codes in Gallager's original form. Codes in this class are free of cycles of length 4 in their Tanner graphs and have good minimum distances. They perform well with iterative decoding.     

无线光通信下极化码DNN-NOMS译码方法研究

针对无线光通信中大气湍流引起极化码置信度传播译码性能不佳的问题,提出了一种无线光通信下极化码DNN-NOMS （Deep Neural Networks-Normalized and Offset Min-Sum）译码方法。首先,把传统的极化码置信传播译码算法因子图转化为类似于低密度奇偶校验（Low-density Parity Check, LDPC）码的Tanner图,在Tanner图展开并转化为深度神经网络（DNN）图形表示的基础上,将MS（Min-Sum）译码方法同时添加归一化因子和偏移因子来给Tanner图的边赋予权重,简化极化码对数似然比的计算方法,通过限制训练参数的数量,选取在损失函数最小的条件下的因子参数,训练得到最优归一化因子和偏移因子的译码模型。仿真结果表明,在不同的大气湍流强度下,该译码方法以牺牲较小的存储空间为前提的情况下能选取更优的归一化因子和偏移因子参数,从而获得更好的误码率性能,且大幅度降低译码复杂度;在误码率为10?4时,DNN-NOMS译码方法能产生0.21~3.56 dB的性能增益,且将迭代次数的运算次数降低87.5%。     

Explicit construction of families of LDPC codes with no 4-cycles

Low-density parity-check (LDPC) codes are serious contenders to turbo codes in terms of decoding performance. One of the main problems is to give an explicit construction of such codes whose Tanner graphs have known girth. For a prime power q and m/spl ges/2, Lazebnik and Ustimenko construct a q-regular bipartite graph D(m,q) on 2q/sup m/ vertices, which has girth at least 2/spl lceil/m/2/spl rceil/+4. We regard these graphs as Tanner graphs of binary codes LU(m,q). We can determine the dimension and minimum weight of LU(2,q), and show that the weight of its minimum stopping set is at least q+2 for q odd and exactly q+2 for q even. We know that D(2,q) has girth 6 and diameter 4, whereas D(3,q) has girth 8 and diameter 6. We prove that for an odd prime p, LU(3,p) is a [p/sup 3/,k] code with k/spl ges/(p/sup 3/-2p/sup 2/+3p-2)/2. We show that the minimum weight and the weight of the minimum stopping set of LU(3,q) are at least 2q and they are exactly 2q for many LU(3,q) codes. We find some interesting LDPC codes by our partial row construction. We also give simulation results for some of our codes.     

Low-density parity-check codes based on finite geometries: arediscovery and new results

This paper presents a geometric approach to the construction of low-density parity-check (LDPC) codes. Four classes of LDPC codes are constructed based on the lines and points of Euclidean and projective geometries over finite fields. Codes of these four classes have good minimum distances and their Tanner (1981) graphs have girth 6. Finite-geometry LDPC codes can be decoded in various ways, ranging from low to high decoding complexity and from reasonably good to very good performance. They perform very well with iterative decoding. Furthermore, they can be put in either cyclic or quasi-cyclic form. Consequently, their encoding can be achieved in linear time and implemented with simple feedback shift registers. This advantage is not shared by other LDPC codes in general and is important in practice. Finite-geometry LDPC codes can be extended and shortened in various ways to obtain other good LDPC codes. Several techniques of extension and shortening are presented. Long extended finite-geometry LDPC codes have been constructed and they achieve a performance only a few tenths of a decibel away from the Shannon theoretical limit with iterative decoding     

Construction of type-II QC-LDPC codes with fast encoding based on perfect cyclic difference sets

In view of the problems that the encoding complexity of quasi-cyclic low-density parity-check (QC-LDPC) codes is high and the minimum distance is not large enough which leads to the degradation of the error-correction performance, the new irregular type-II QC-LDPC codes based on perfect cyclic difference sets (CDSs) are constructed. The parity check matricesof these type-II QC-LDPC codes consist of the zero matrices with weight of 0, the circulant permutation matrices (CPMs) with weight of 1 and the circulant matrices with weight of 2 (W2CMs). The introduction of W2CMs in parity check matrices makes it possible to achieve the larger minimum distance which can improve the error-correction performance of the codes. The Tanner graphs of these codes have no girth-4, thus they have the excellent decoding convergence characteristics. In addition, because the parity check matrices have the quasi-dual diagonal structure, the fast encoding algorithm can reduce the encoding complexity effectively. Simulation results show that the new type-II QC-LDPC codes can achieve a more excellent error-correction performance and have no error floor phenomenon over the additive white Gaussian noise (AWGN) channel with sum-product algorithm (SPA) iterative decoding.     

中继编码协作系统等效点对点传输模型的研究

研究了LDPC编码中继协作通信系统及其编码协作系统目的点译码器基于双层Tanner图的LDPC联合迭代译码算法,通过在目的点接收机引入算术/几何平均信噪比的概念,将中继编码协作系统转换成等效的易于分析的点对点传输模型,利用点对点传输中的原理研究较复杂编码中继协作系统的性能。理论分析和模拟结果表明：在相同的条件下LDPC中继编码协作系统及其等效点对点编码传输系统的性能非常接近,从而证实了本文所提出的等效点对点传输模型的合理性,以及基于双层Tanner图的LDPC联合迭代译码算法的有效性。     

Design of Quasi‐Cyclic Low‐Density Parity Check Codes with Large Girth

In this paper we propose a graph‐theoretic method based on linear congruence for constructing low‐density parity check (LDPC) codes. In this method, we design a connection graph with three kinds of special paths to ensure that the Tanner graph of the parity check matrix mapped from the connection graph is without short cycles. The new construction method results in a class of (3, ρ)‐regular quasi‐cyclic LDPC codes with a girth of 12. Based on the structure of the parity check matrix, the lower bound on the minimum distance of the codes is found. The simulation studies of several proposed LDPC codes demonstrate powerful bit‐error‐rate performance with iterative decoding in additive white Gaussian noise channels.     

Decoding low-density parity-check codes with probabilisticscheduling

We present a new message-passing schedule for the decoding of low-density parity-check (LDPC) codes. This approach, designated “probabilistic schedule”, takes into account the structure of the Tanner graph (TG) of the code. We show by simulation that the new schedule offers a much better performance/complexity trade-off. This work also suggests that scheduling plays an important role in iterative decoding and that a schedule that matches the structure of the TG is desirable     

Pseudocodeword Performance Analysis for LDPC Convolutional Codes

Message-passing iterative decoders for low-density parity-check (LDPC) block codes are known to be subject to decoding failures due to so-called pseudocodewords. These failures can cause the large signal-to-noise ratio (SNR) performance of message-passing iterative decoding to be worse than that predicted by the maximum-likelihood (ML) decoding union bound.      

Codes on finite geometries

New algebraic methods for constructing codes based on hyperplanes of two different dimensions in finite geometries are presented. The new construction methods result in a class of multistep majority-logic decodable codes and three classes of low-density parity-check (LDPC) codes. Decoding methods for the class of majority-logic decodable codes, and a class of codes that perform well with iterative decoding in spite of having many cycles of length 4 in their Tanner graphs, are presented. Most of the codes constructed can be either put in cyclic or quasi-cyclic form and hence their encoding can be implemented with linear shift registers.