A class of binary burst error-correcting quasi-cyclic codes

A class of binary quasi-cyclic burst error-correcting codes based upon product codes is studied. An expression for the maximum burst error-correcting capability for each code in the class is given. In certain cases, the codes exist in the class which have the same block length and number of check bits as the Gilbert codes, but correct longer bursts of errors than Gilbert codes. By shortening the codes, it is possible to design codes which achieve the Reiger bound     

Self-orthogonal quasi-cyclic codes

A new class of linear block codes, called self-orthogonal quasi-cyclic codes, is defined. It is shown that the problem of designing these codes is equivalent to the problem of designing disjoint difference sets. As a result, several classes of optimal and near-optimal codes can be constructed analytically and other codes can be found by a computer-aided search procedure. A list of codes is given for practical values of minimum distance and efficiency. Two easily implemented decoding algorithms are described, and a Monte Carlo evaluation of the performance of several codes on the binary symmetric channel is presented. This evaluation shows that, when decoded with the better of the two algorithms, these codes perform nearly as well as the Bose-Chaudhuri-Hocquenghem (BCH) codes with the same minimum distance and efficiency in the cases examined. Although these codes must be long relative to the BCH codes, the low cost and lack of complexity of the equipment required to correct large numbers of errors should make them competitive for practical systems.     

Good self-dual quasi-cyclic codes exist

We show that there are long binary quasi-cyclic self-dual (either Type I or Type II) codes satisfying the Gilbert-Varshamov bound.     

Near-Shannon-limit quasi-cyclic low-density parity-check codes

This letter presents two classes of quasi-cyclic low-density parity-check codes that perform close to the Shannon limit.     

A lattice-based systematic recursive construction of quasi-cyclic LDPC codes

This paper presents a low-complexity recursive and systematic method to construct good well-structured low-density parity-check (LDPC) codes. The method is based on a recursive application of a partial Kronecker product operation on a given gamma x q, q ges 3 a prime, integer lattice L(gamma x q). The (n - 1)- fold product of L(gamma x q) by itself, denoted Lⁿ(gamma x q), represents a regular quasi-cyclic (QC) LDPC code, denoted (see PDF), of high rate and girth 6. The minimum distance of (see PDF) is equal to that of the core code (see PDF) introduced by L(gamma x q). The support of the minimum weight codewords in (see PDF) are characterized by the support of the same type of codewords in (see PDF). From performance perspective the constructed codes compete with the pseudorandom LDPC codes.     

New binary one-generator quasi-cyclic codes

Sixteen new binary quasi-cyclic linear codes improving the best known lower bounds on minimum distance in Brouwer's tables are constructed. The parameters of these codes are [102, 26, 32], [102, 27, 30], [142, 35, 40], [142, 36, 38] [146, 36, 40], [170, 16, 72], [170, 20, 66], [170, 33, 52] [170, 36, 50], [178, 33, 56], [178, 34, 54], [182, 27, 64] [182, 36, 56], [186, 17, 76], [210, 23, 80], [254, 22, 102] Sixty cyclic and thirty quasi-cyclic codes, which attain the respective bounds in Brouwer's table and are not included in Chen's table are presented as well.     

Six new binary quasi-cyclic codes

Six new quasi-cyclic codes are presented, which improve the lower bounds on the minimum distance for a binary code. A local exhaustive search is used to find these codes and many other quasi-cyclic codes which attain the lower bounds.<>     

Equivalent rate 1/2 quasi-cyclic codes (Corresp.)

Chen et al. [1] give a list of quasi-cyclic (2m,m) codes which have the largest minimum distance of any quasi-cyclic code, for various values ofm. We present the weight distribution of these codes. It will be seen that many of the codes found by Chen et al. [1] are equivalent in the sense of having identical weight distributions.     

Efficient encoding of quasi-cyclic low-density parity-check codes

Quasi-cyclic (QC) low-density parity-check (LDPC) codes form an important subclass of LDPC codes. These codes have encoding advantage over other types of LDPC codes. This paper addresses the issue of efficient encoding of QC-LDPC codes. Two methods are presented to find the generator matrices of QC-LDPC codes in systematic-circulant (SC) form from their parity-check matrices, given in circulant form. Based on the SC form of the generator matrix of a QC-LDPC code, various types of encoding circuits using simple shift registers are devised. It is shown that the encoding complexity of a QC-LDPC code is linearly proportional to the number of parity bits of the code for serial encoding, and to the length of the code for high-speed parallel encoding.     

Combinatorial design-based quasi-cyclic LDPC codes with girth eight

This paper presents a novel regular Quasi-Cyclic (QC) Low Density Parity Check (LDPC) codes with column-weight three and girth at least eight. These are designed on the basis of combinatorial design in which subsets applied for the construction of circulant matrices are determined by a particular subset. Considering the non-existence of cycles four and six in the structure of the parity check matrix, a bound for their minimum weight is proposed. The simulations conducted confirm that without applying a masking technique, the newly implemented codes have a performance similar to or better than other well-known codes. This is evident in the waterfall region, while their error floor at very low Bit Error Rate (BER) is expected.     

High-throughput layered decoder implementation for quasi-cyclic LDPC codes

This paper presents a high-throughput decoder design for the Quasi-Cyclic (QC) Low-Density Parity-Check (LDPC) codes. Two new techniques are proposed, including parallel layered decoding architecture (PLDA) and critical path splitting. PLDA enables parallel processing for all layers by establishing dedicated message passing paths among them. The decoder avoids crossbar-based large interconnect network. Critical path splitting technique is based on articulate adjustment of the starting point of each layer to maximize the time intervals between adjacent layers, such that the critical path delay can be split into pipeline stages. Furthermore, min-sum and loosely coupled algorithms are employed for area efficiency. As a case study, a rate-1/2 2304-bit irregular LDPC decoder is implemented using ASIC design in 90nm CMOS process. The decoder can achieve the maximum decoding throughput of 2.2Gbps at 10 iterations. The operating frequency is 950MHz after synthesis and the chip area is 2.9mm².     

A square root bound on the minimum weight in quasi-cyclic codes

We establish a square root bound on the minimum weight in the quasi-cyclic binary codes constructed by Bhargava, Tavares, and Shiva. The proof rests on viewing the codes as ideals in a group algebra over GF (4). Theorem 6 answers a question raised by F. J. MacWilliams and N. J. A. Sloane in {em The Theory of Error-Correcting Codes.} Theorems 3, 4, and 5 provide information about the way the nonzero entries of a codeword of minimum weight are distributed among the coordinate positions.     

光通信中一种准循环非二进制LDPC码的新颖构造方法

在对目前普遍采用的非二进制低密度奇偶校验(NB -LDPC)码校验矩阵的准循环构造方法进行深入研究的基础上,提出了一种基于有限域的NB -LDPC码的立体构造方法,在构建基于有限域的基础矩阵后,运用立体扩展的方式构成循环 子矩阵,最终构造出具备准循环特性的非二进制校验矩阵。 通过对采用立体构造法构造的NB-LDPC码的性能仿真发现,与基于GF(2⁹)的 RS(511,5)相比,本文 构造的NB-LDPC码在误比特率(BER)为10－7时可 以增加3.3 dB的净编码增益(NCG);在BER为 10－6时,本文构造的LDPC码与采用传统准循环方式构造的二 进制LDPC码、随机构造 的二进制LDPC码、基于有限域构造的32进制准循环LDPC码和基于欧式 几何构造的64进制的循 环LDPC码比较,分别多获得了0.56、0.56、0.03dB的NCG。通过对本文 构造的NB-LDPC码性能仿真发现,这类具有高度结构化的NB-LDPC码不仅具备 准循环特性,有利于硬件实现,同时在中短码长情况时展现出较好的纠错性能。     

A combining method of quasi-cyclic LDPC codes by the Chinese remainder theorem

In this paper we propose a method of constructing quasi-cyclic low-density parity-check (QC-LDPC) codes of large length by combining QC-LDPC codes of small length as their component codes, via the Chinese remainder theorem. The girth of the QC-LDPC codes obtained by the proposed method is always larger than or equal to that of each component code. By applying the method to array codes, we present a family of high-rate regular QC-LDPC codes with no 4-cycles. Simulation results show that they have almost the same performance as random regular LDPC codes.     

A necessary and sufficient condition for determining the girth of quasi-cyclic LDPC codes

The parity-check matrix of a quasi-cyclic low- density parity-check (QC-LDPC) code can be compactly represented by a polynomial parity-check matrix. By using this compact representation, we derive a necessary and sufficient condition for determining the girth of QC-LDPC codes in a systematic way. The new condition avoids an explicit enumeration of cycles for determining the girth of codes, and thus can be well employed to generate QC-LDPC codes with large girth.     

Overlapped message passing for quasi-cyclic low-density parity check codes

In this paper, a systematic approach is proposed to develop a high throughput decoder for quasi-cyclic low-density parity check (LDPC) codes, whose parity check matrix is constructed by circularly shifted identity matrices. Based on the properties of quasi-cyclic LDPC codes, the two stages of belief propagation decoding algorithm, namely, check node update and variable node update, could be overlapped and thus the overall decoding latency is reduced. To avoid the memory access conflict, the maximum concurrency of the two stages is explored by a novel scheduling algorithm. Consequently, the decoding throughput could be increased by about twice assuming dual-port memory is available.     

一种可快速编码的QC-LDPC码构造新方法

为解决LDPC码的编码复杂度问题,使其更易于硬件实现,提出了一种可快速编码的准循环LDPC码构造方法。该方法以基于循环置换矩阵的准循环LDPC码为基础,通过适当的打孔和行置换操作,使构造码的校验矩阵具有准双对角线结构,可利用校验矩阵直接进行快速编码,有效降低了LDPC码的编码复杂度。仿真结果表明,与IEEE 802.16e中的LDPC码相比,新方法构造的LDPC码在低编码复杂度的基础上获得了更好的纠错性能。     

Finite field construction for quasi-cyclic LDPC convolutional codes with cyclic 2-D MDS codes

The parity-check matrices for quasi-cyclic low-density parity-check convolutional (QC-LDPC-C) codes have different characteristics of time-varying periodicity and need to realize fast encoding. The finite field construction method for QC-LDPC-C codes with cyclic two-dimensional maximum distance separable (2-D MDS) codes is proposed using the base matrix framework and matrix unwrapping, thus the constructed parity-check matrices are free of length-4 cycles. The unwrapped matrices are constructed respectively based on different cyclic 2-D MDS codes for the case of matrix period less than or greater than constraint block length, and construction examples are given. LDPC-C codes with different periodicity characteristics are compared with QC-LDPC-C codes constructed with the proposed method. Experimental results show that QC-LDPC-C codes with the proposed method outperform the other codes and have lower encoding and decoding complexity.

     

On quasi-cyclic codes with rate l m (Corresp.)

An integer linear programming problem and an additional divisibility condition are described such that they have a common solution if and only if there is a quasi-cyclic code with rate1/m. A table of binary quasi-cyclic codes with dimensions seven and eight and rate1/mfor smallmis included. In particular, there are binary linear codes with (length, dimension, minimum distance)=(35, 7,16), (42, 7,19), (80, 8, 37), (96, 8, 46), and(112,8,54).