An algebraic design procedure is given for constructing rate 1/3 quasi-cyclic LDPC codes with Tanner graphs with girth 6. Parity check matrices consist of 2 × 3 block matrices of circulants of size p, a prime, exhibiting invariance under the action of a subgroup of the multiplicative group mod p. The group invariance converts the problem of avoiding short cycles into that of choosing orbits to solve connectivity constraints. A series of very low density H matrix codes constructed show surprisingly good minimum distances.

Peer-to-peer data dissemination in a mobile ad-hoc environment is characterized by three resource constraints, including energy, communication bandwidth, and storage. Most of the existing studies deal with these constraints separately. In this paper we propose an algorithm called RANk-based dissemination (RANDI), which provides an integral treatment to the three constraints. The contribution is in determining how to prioritize the reports in terms of their relevance, when to transmit the reports, and how many to transmit. We experimentally compare RANDI with IDS and PeopleNet, two mobile peer-to-peer dissemination algorithms. The results show that RANDI significantly outperforms both algorithms.

In this correspondence, we propose an approach to construct irregular low-density parity-check (LDPC) codes based on quasi-cyclic extension. When decoded iteratively, the constructed irregular LDPC codes exhibit a relatively low error floor in the high signal-to-noise ratio (SNR) region and are subject to relatively few undetected errors. The LDPC codes constructed based on the proposed scheme remain efficiently encodable

In this paper, we study the performance of different graph-based error-correcting codes over Gilbert–Elliot channels. We propose a hybrid coding scheme in which each code bit is checked by both a parity check and a Hamming code. A hybrid code can be represented by a code-to-code graph, which can be used to optimize the code. Asymptotic minimum distance properties of the hybrid code are derived, and it is shown that the expected minimum distance of the hybrid code increases linearly with respect to the code length. Simulation results show that for a typical Gilbert–Elliott channel, hybrid codes can outperform regular low-density parity-check codes by more than an order of magnitude, in terms of bit-error rate.

In this paper, we study the performance of different graph-based error-correcting codes over Gilbert-Elliott (GE) channels. We propose a hybrid coding scheme in which each code bit is checked by both a parity-check code and a Hamming code. A hybrid code can be represented by a code-to-code graph, which can be used to optimize the code. Asymptotic minimum distance properties of the hybrid code are derived, and it is shown that the expected minimum distance of the hybrid code increases linearly with respect to the code length. Simulation results show that for a typical GE channel, hybrid codes can outperform regular low-density parity-check codes by more than an order of magnitude, in terms of bit-error rate.

In this paper, we apply two improved min-sum algorithms, the normalized and offset min-sum algorithms, to the decoding of irregular LDPC codes. We show that the behavior of the two algorithms in decoding irregular LDPC codes is different from that in decoding regular LDPC codes, due to the existence of bit nodes of degree two. We analyze and give explanations to the difference, and propose approaches to improve the performance of the two algorithms.

A class of algebraically structured quasi-cyclic (QC) low-density parity-check (LDPC) codes and their convolutional counterparts is presented. The QC codes are described by sparse parity-check matrices comprised of blocks of circulant matrices. The sparse parity-check representation allows for practical graph-based iterative message-passing decoding. Based on the algebraic structure, bounds on the girth and minimum distance of the codes are found, and several possible encoding techniques are described. The performance of the QC LDPC block codes compares favorably with that of randomly constructed LDPC codes for short to moderate block lengths. The performance of the LDPC convolutional codes is superior to that of the QC codes on which they are based; this performance is the limiting performance obtained by increasing the circulant size of the base QC code. Finally, a continuous decoding procedure for the LDPC convolutional codes is described.

The parity-check matrix of a linear code is used to define a bipartite code constraint (Tanner) graph in which bit nodes are connected to parity-check nodes. The connectivity properties of this graph are analyzed using both local connectivity and the eigenvalues of the associated adjacency matrix. A simple lower bound on the minimum distance of the code is expressed in terms of the two largest eigenvalues. For a more powerful bound, local properties of the subgraph corresponding to a minimum-weight word in the code are used to create an optimization problem whose solution is a lower bound on the code's minimum distance. Linear programming gives one bound. The technique is illustrated by applying it to sparse block codes with parameters [7,3,4] and [42,23,6].

A binary cyclic code of length of n can be defined by a set of parity-check equations that is invariant under the additive cyclic group generated by A:i to i+1 modulo n. A class of quasicyclic codes that have parity-check equations invariant under the group generated by a subgroup of A and a subgroup of the multiplicative group M:i to 2/sup k/i modulo n is studied in detail. The Fourier transform transforms the action of the additive group, and a linearized polynomial transform transforms the action of the multiplicative group. The form of the transformed code equations permits a BCH-like bound on the minimum distance of the code. The techniques are illustrated by the construction of several codes that are decodable by the Berlekamp-Massey algorithm and that have parameters that approach or surpass those of the best codes known.>

A series of designs for a 256K memory are presented which integrate error-correcting coding into the memory organization. Starting from a simple single-error correcting product code, the successive designs explore trade-offs in coding efficiency, access delay, and complexity of communication and computation. In the most powerful design, all the 256K bits are organized so that they form a codeword in a double-error-correcting triple-error-detecting code derived from a projective plane. Because all of the bits are components of this single codeword, the coding efficiency is very high; the required parity check bits increase the storage by only 3 percent, approximately. Single error correction can take place at the time of a read with very little additional delay compared to that of a normal irredundant memory. Multiple error correction can be performed by the memory management system. A variety of failure modes, including failure of a whole column of one of the constituent 64 x 64 subarrays can be tolerated. Writing into the memory is somewhat slower than in a conventional memory, involving a read-write cycle.

A method is described for constructing long error-correcting codes from one or more shorter error-correcting codes, referred to as subcodes, and a bipartite graph. A graph is shown which specifies carefully chosen subsets of the digits of the new codes that must be codewords in one of the shorter subcodes. Lower bounds to the rate and the minimum distance of the new code are derived in terms of the parameters of the graph and the subeodes. Both the encoders and decoders proposed are shown to take advantage of the code's explicit decomposition into subcodes to decompose and simplify the associated computational processes. Bounds on the performance of two specific decoding algorithms are established, and the asymptotic growth of the complexity of decoding for two types of codes and decoders is analyzed. The proposed decoders are able to make effective use of probabilistic information supplied by the channel receiver, e.g., reliability information, without greatly increasing the number of computations required. It is shown that choosing a transmission order for the digits that is appropriate for the graph and the subcodes can give the code excellent burst-error correction abilities. The construction principles

A simple partitioning algorithm for merging two disjoint linearly ordered sets is given, and an upper bound on the average number of comparisons required is established. The upper bound is $1.06\log _2 \begin{pmatrix} {n + m} \\ m \end{pmatrix}$, where n is the number of elements in the larger of the two sets, m the number of the smaller, and $\begin{pmatrix} {n + m} \\ m \end{pmatrix} = (n + m)!/(m!n!)$. An immediate corollary is that any sorting problem can be done with an average number of comparisons within $6\% $ of the information theoretic bound using repeated merges; it does not matter what the merging order used is. Although the provable bound is $6\% $ over the lower bound, computations indicate that the algorithm will asymptotically make only $3\% $ more comparisons than the lower bound. The algorithm is compared with the Hwang-Lin algorithm, and modifications to improve average efficiency of this well known algorithm are given.