Search

This paper presents a novel iterative hard decision decoding algorithm for binary linear block codes over a binary symmetric channel (BSC). The problem is formulated as a 0-1 integer programming problem which is known to be NP-hard. When the crossover probability ε of the channel is known, the solution space of the decoding problem can be decreased to a sphere whose radius is related to ε. Using the penalty function method, the problem is reformulated on this reduced solution space. Then an iterative multi-flip local search algorithm is designed to find the global solution of this decoding problem. For a code with minimum distance d, when the radius of the sphere is not greater than ⌊\fracd-12⌋, this algorithm has the maximum likelihood (ML) certificate property, i.e., if the decoder outputs a codeword, it is guaranteed to be the ML codeword. Compared to the probabilistic suboptimal iterative belief propagation (BP) decoder, this approach has lower complexity and better performance. Numerical results show that in terms of speed and performance the proposed decoding method outperforms BP decoding in the error floor region. [ABSTRACT FROM PUBLISHER]

A new combinatorial technique for constructing girth-6 structured binary regular low-density parity-check (LDPC) codes based on special types of t-designs is given. A very large number of well-known t-designs can be used by this method for code construction. Based on this method, a t-(v,k,λ) design D=(X,B) can be exploited for code construction if it satisfies the following three conditions: 1) |B_1 ∩ B_2|≤ t for any two blocks B_1,B_2∈ B and B_1 ≠ B_2; 2) λ>1; and 3) k>t. Though the technique works for any t-design satisfying these conditions, we focus only on the utilization of simple triple systems, super-simple BIBDs, Steiner systems, and large sets (LSs) of t-designs. We also construct binary and non-binary girth-6 QC-LDPC codes from the t-designs satisfying these conditions by using matrix dispersion method. Experimental results show that the constructed non-binary QC-LDPC codes can provide good practical performance under iterative decoding using the fast Fourier transform based q-ary sum-product algorithm (FFT-QSPA) and they can achieve acceptable coding gains over random-like codes of comparable parameters decoded with sum-product algorithm (SPA). [ABSTRACT FROM AUTHOR]

Difference sets are used to give a novel method for constructing structured regular quasi-cyclic low-density parity-check codes. Let F_q be a field with q elements and assume that D=d_1,..., d_k is a (v,k,1)-difference set for Z_v with d_1

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 γ × q, q ≥ 3 a prime, integer lattice L(γ × q). The (n - 1)- fold product of L(γ × q) by itself, denoted Ln(γ × q), represents a regular quasi-cyclic (QC) LDPC code, denoted Cγxqn, of high rate and girth 6. The minimum distance of Cγxq1 is equal to that of the core code Cγxq1 introduced by L(γ x q). The support of the minimum weight codewords in Cγ×qn are characterized by the support of the same type of codewords in Cγ×q1. From performance perspective the constructed codes compete with the pseudorandom LDPC codes. [ABSTRACT FROM AUTHOR]