LDPC codes from generalized polygons

We use the theory of finite classical generalized polygons to derive and study low-density parity-check (LDPC) codes. The Tanner graph of a generalized polygon LDPC code is highly symmetric, inherits the diameter size of the parent generalized polygon, and has minimum (one half) diameter-to-girth ratio. We show formally that when the diameter is four or six or eight, all codewords have even Hamming weight. When the generalized polygon has in addition an equal number of points and lines, we see that the nonregular polygon based code construction has minimum distance that is higher at least by two in comparison with the dual regular polygon code of the same rate and length. A new minimum-distance bound is presented for codes from nonregular polygons of even diameter and equal number of points and lines. Finally, we prove that all codes derived from finite classical generalized quadrangles are quasi-cyclic and we give the explicit size of the circulant blocks in the parity-check matrix. Our simulation studies of several generalized polygon LDPC codes demonstrate powerful bit-error-rate (BER) performance when decoding is carried out via low-complexity variants of belief propagation.     

High-Rate Quasi-Cyclic Low-Density Parity-Check Codes Derived From Finite Affine Planes

This paper shows that several attractive classes of quasi-cyclic (QC) low-density parity-check (LDPC) codes can be obtained from affine planes over finite fields. One class of these consists of duals of one-generator QC codes. Presented here for codes contained in this class are the exact minimum distance and a lower bound on the multiplicity of the minimum-weight codewords. Further, it is shown that the minimum Hamming distance of a code in this class is equal to its minimum additive white Gaussian noise (AWGN) pseudoweight. Also discussed is a class consisting of codes from circulant permutation matrices, and an explicit formula for the rank of the parity-check matrix is presented for these codes. Additionally, it is shown that each of these codes can be identified with a code constructed from a constacyclic maximum distance separable code of dimension 2. The construction is similar to the derivation of Reed-Solomon (RS)-based LDPC codes presented by Chen and Djurdjevic Experimental results show that a number of high rate QC-LDPC codes with excellent error performance are contained in these classes     

Efficient algorithm for calculating short cycles in Tanner graph based on matrix computation

Loop distribution of Tanner graph affects the BER performance of low-density parity-check codes(LDPC) decoding.To count short cycles in the Tanner graph efficiently,a side by side recursion algorithm based on matrix computation was proposed.Firstly,5 basic graph structures were defined to realize recursive calculate in the implementation process.Compared with previous works,the algorithm provided many methods for counting the same length of cycles.The same result confirmed the correctness of the algorithm.The new algorithm could not only calculate the total number of cycles,but also gave the number each edge participating in fixed-length cycles.Its complexity was proportional to the product of D and square of N,where D was the average degree of variable nodes,and N denoted the code length.For LDPC codes,D was far less than N.For most of the LDPC codes,the calculation for numbers of cycle-length g、g+2、g+4 was only several seconds.     

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.     

Studying the locator polynomials of minimum weight codewords of BCHcodes

Primitive binary cyclic codes of length n=2^m are considered. A BCH code with designed distance δ is denoted B(n,δ). A BCH code is always a narrow-sense BCH code. A codeword is identified with its locator polynomial, whose coefficients are the symmetric functions of the locators. The definition of the code by its zeros-set involves some properties for the power sums of the locators. Moreover, the symmetric functions and the power sums of the locators are related to Newton's identities. An algebraic point of view is presented in order to prove or disprove the existence of words of a given weight in a code. The principal result is the true minimum distance of some BCH codes of length 255 and 511. which were not known. The minimum weight codewords of the codes B(n2^h -1) are studied. It is proved that the set of the minimum weight codewords of the BCH code B(n,2^m-2-1) equals the set of the minimum weight codewords of the punctured Reed-Muller code of length n and order 2, for any m     

Systematic recursive construction of LDPC codes

This letter presents a systematic and recursive method to construct good low-density parity-check (LDPC) codes, especially those with high rate. The proposed method uses a parity check matrix of a quasi-cyclic LDPC code with given row and column weights as a core upon which the larger code is recursively constructed with extensive use of pseudorandom permutation matrices. This construction preserves the minimum distance and girth properties of the core matrix and can generate either regular, or irregular LDPC codes. The method provides a unique representation of the code in compact notation.     

Optimal space-time constellations from groups

We consider the design of space-time constellations based on group codes for fading channels with multiple transmit and receive antennas. These codes can be viewed as multiantenna extensions of phase-shift keying (PSK), in the sense that all codewords have equal energy, all are rotations of a fixed codeword, and there is a simple differential transmission rule that allows data to be sent without channel estimates at the transmitter or receiver. For coherent detection, we show that all optimal full-rank space-time group codes are unitary (each code matrix has equal-energy, orthogonal rows). This leads to a simpler code design criterion and suggests that unitary codes may play an important role in coherent as well as noncoherent communication. For any number of transmit antennas t, we then use the design criterion to characterize all full-rank unitary space-time group codes of minimum block length (also t) which have 2/sup p/ codewords. These results allow us to characterize all optimal 2/sup p/-ary unitary group codes with square code matrices. This restricted class of block codes matches the class proposed for differential modulation by Hughes (see IEEE Trans. Inform. Theory, vol.46, p.2567-78, Nov. 2000), and by Hochwald and Sweldens (see IEEE Trans. Commun., vol.48, p.2041-2052, Dec. 2000).     

Optimal binary one-error-correcting codes of length 10 have 72codewords

The maximum number of codewords in a binary code with length n and minimum distance d is denoted by A(n, d). By construction it is known that A(10, 3)⩾72 and A(11, 3)⩾144. These bounds have long been conjectured to be the exact values. This is here proved by classifying various codes of smaller length and lengthening these using backtracking and isomorphism rejection. There are 562 inequivalent codes attaining A(10, 3)=72 and 7398 inequivalent codes attaining A(11, 3)=144     

结合6-QAM和双层LDPC码的编码调制研究

针对阶数为3×2p的非标准调制与纠错编码难以匹配的问题,提出了一种面向6阶正交幅度调制（QAM）的双层编码调制传输方案。在发送端,采用有限域GF(2)低密度奇偶校验（LDPC）码与GF(3) LDPC码进行分层编码,并将两种编码码字映射为6进制码字后进行6-QAM调制;在接收端,根据GF(2) LDPC码和GF(3) LDPC码的译码顺序,设计了两种双层迭代译码方法。仿真结果表明,在加性高斯白噪声（AWGN）信道下,执行一次整体迭代译码时,先执行GF(3) LDPC码译码的6-QAM分层编码调制方案比先执行GF(2) LDPC码译码的方案获得了更优的误符号率（SER）性能;随着迭代次数增加,纠错性能可获得进一步改善。比较6-QAM与6阶相移键控（6-PSK）调制,若先执行GF(3) LDPC码译码,当SER为10-5时,6-QAM结合双层LDPC码的传输方案在AWGN信道下可获得约1.3dB的增益。      

A coding theorem for lossy data compression by LDPC codes

In this article, low-density parity-check (LDPC) codes are applied to lossy source coding and we study how the asymptotic performance of MacKay's (see ibid, vol.45, p.399-431, Mar. 1999 and vol.47, p.2101, July, 2001) LDPC codes depends on the sparsity of the parity-check matrices in the source coding of the binary independent and identically distributed (i.i.d.) source with Pr{x=1}=0.5. In the sequel, it is shown that an LDPC code with column weight O(logn) for code length n can attain the rate-distortion function asymptotically.     

一种基于伪循环MDS码的准循环LDPC码构造方法

该文提出了一种利用两个信息符号的伪循环最大距离可分(MDS)码,构造围长为6的准循环低密度奇偶校验(LDPC)码的方法。在GF(q)中,它通过直接计算长为q+1的伪循环MDS码生成多项式,构造准循环LDPC码的校验矩阵。其主要利用了含两个信息符号的伪循环MDS码字特殊的循环性,及任意两个码字间距离不小于q的特点,使所构造的准循环LDPC码保证无4环。仿真结果表明,基于伪循环MDS码的准循环LDPC码在高斯信道下,能获得较好的误码性能。     

Disproof of a conjecture on the existence of balanced optimal covering codes

The minimum number of codewords in a binary code with length n and covering radius R is denoted by K(n,R), and corresponding codes are called optimal. A code with M words is said to be balanced in a given coordinate if the number of 0's and 1's in this coordinate are at least /spl lfloor/M/2/spl rfloor/. A code is balanced if it is balanced in all coordinates. It has been conjectured that among optimal covering codes with given parameters there is at least one balanced code. By using a computational method for classifying covering codes, it is shown that there is no balanced code attaining K(9,1)=62.     

几种LDPC码的最小汉明距离的计算

本文提出一种计算LDPC码的真实最小汉明距离的方法．该方法能够用来计算多种LDPC码方案的真实最小汉明距离，比如准循环LDPC码、pi-旋转LDPC码等．该方法是通过计算码的环长间接地找到LDPC码最小距离，由于计算环长的计算量要远比直接计算最小汉明距离来得低，因而该算法能够在有限时间内找到LDPC码的真实最小距离．通过仿真表明，用目前主流的个人计算机利用该方法找出一个有最小距离24的码率为1／4的准循环LDPC码最小距离大概需要花77分钟。     

大小兼容的阵列LDPC码设计的新方法

阵列LDPC码构造简单,又易于VLSI实现.文献[4]对其进行了改进,支持任意码长,称为大小兼容的阵列LDPC码(记为SC阵列LDPC码).对于SC阵列LDPC码,本文提出3种改进方法,方法1对文献[4]SC阵列LDPC码进行了完善,排除了因k不是L的因子而产生的错误.方法2、3研究了新的子矩阵排列方法.这些方法对码的距离特性和误码性能都有很大改善.不仅在AWGN信道,还在UWB CM3信道上,通过仿真,证明了其良好性能.     

On the application of LDPC codes to arbitrary discrete-memoryless channels

We discuss three structures of modified low-density parity-check (LDPC) code ensembles designed for transmission over arbitrary discrete memoryless channels. The first structure is based on the well-known binary LDPC codes following constructions proposed by Gallager and McEliece, the second is based on LDPC codes of arbitrary (q-ary) alphabets employing modulo-q addition, as presented by Gallager, and the third is based on LDPC codes defined over the field GF(q). All structures are obtained by applying a quantization mapping on a coset LDPC ensemble. We present tools for the analysis of nonbinary codes and show that all configurations, under maximum-likelihood (ML) decoding, are capable of reliable communication at rates arbitrarily close to the capacity of any discrete memoryless channel. We discuss practical iterative decoding of our structures and present simulation results for the additive white Gaussian noise (AWGN) channel confirming the effectiveness of the codes.     

On asymptotic ensemble weight enumerators of LDPC-like codes

For LDPC-like codes such as LDPC, GLDPC, and DGLDPC codes, it is well known that the error floor can be caused by the codewords of small weights or stopping sets of small sizes. In this paper, we investigate the computation of asymptotic weight enumerators such that it becomes a convenient tool to determine a good distribution of code ensembles. In addition, by analyzing the first order approximation, we derive a condition to obtain a negative asymptotic growth rate of the codewords of small linear-sized weights, which is an important constraint for distribution optimization. Also the weight enumerators of turbo and repeat-accumulate codes are investigated. Furthermore, we extend our results to nonbinary DGLDPC codes. Generalization to N-layer and convolutional code based LDPC-like codes are also developed.     

A new high rate code scheme with highly parallel and low complexity decoding algorithm

A new high rate code scheme is proposed in this paper. It consists of serial concatenated recursive systematic ordinary (nonpunctured) convolutional codes with only 8 states in the trellis of the corresponding reciprocal dual codes. With a low complexity and highly parallel decoding algorithm, over additive white Gaussian noise channels, the proposed codes can achieve good bit error rate (BER) performance comparable to that of turbo codes and low density parity check (LDPC) codes. At code rate R=16/17, the overall decoding complexity of the proposed code scheme is almost half that of the LDPC codes.     

带宽有效传输的GF(q)上LDPC编码设计

以Davey(1998)提出的Monte-Carlo方法为基础的、适用于二进制PSK调制的二进制LDPC(Low-Density Parity-Check,低密度奇偶校验)码的最优化理论已经在相关文献中得到了验证。但由于q进制星座没有旋转对称性,因而限制了Davey的方法的应用。本文提出了应用在准正规编码类型上的一种有效的Davey型Monte-Carlo最优化编码设计方法。应用这种方法,可直接将GF(q)上的最优LDPC编码和任意的q进制调制结合起来,获得很高的带宽效率。本文采用MQAM和MPSK调制机制与准正规LDPC编码相结合的若干实例来论证该设计方法。     

High-Rate Nonbinary Regular Quasi-Cyclic LDPC Codes for Optical Communications

The parity-check matrix of a nonbinary (NB) low-density parity-check (LDPC) code over Galois field GF(q) is constructed by assigning nonzero elements from GF(q) to the 1s in corresponding binary LDPC code. In this paper, we state and prove a theorem that establishes a necessary and sufficient condition that an NB matrix over GF(q), constructed by assigning nonzero elements from GF(q) to the 1s in the parity-check matrix of a binary quasi-cyclic (QC) LDPC code, must satisfy in order for its null-space to define a nonbinary QC-LDPC (NB-QC-LDPC) code. We also provide a general scheme for constructing NB-QC-LDPC codes along with some other code construction schemes targeting different goals, e.g., a scheme that can be used to construct codes for which the fast-Fourier-transform-based decoding algorithm does not contain any intermediary permutation blocks between bit node processing and check node processing steps. Via Monte Carlo simulations, we demonstrate that NB-QC-LDPC codes can achieve a net effective coding gain of 10.8 dB at an output bit error rate of 10^-12. Due to their structural properties that can be exploited during encoding/decoding and impressive error rate performance, NB-QC-LDPC codes are strong candidates for application in optical communications.     

Design of regular (2,d/sub c/)-LDPC codes over GF(q) using their binary images

In this paper, a method to design regular (2, d_c)- LDPC codes over GF(q) with both good waterfall and error floor properties is presented, based on the algebraic properties of their binary image. First, the algebraic properties of rows of the parity check matrix H associated with a code are characterized and optimized to improve the waterfall. Then the algebraic properties of cycles and stopping sets associated with the underlying Tanner graph are studied and linked to the global binary minimum distance of the code. Finally, simulations are presented to illustrate the excellent performance of the designed codes.