This paper presents two complementary constructions of finite-length non-binary protograph-based codes with the focus on the short block-length regime. The first class is based on the existing approaches of applying the copy-and-permute operations to the constituent protograph with unweighted edges, followed by assigning non-binary scales to the edges of the derived graph. The second class is novel and is based on the so-called graph cover of a non-binary protograph: the original protograph has fixed edge scalings and copy-and-permute operations are applied to the edge-weighted protograph. The second class is arguably more restrictive, but in turn it offers simpler design and implementation. We provide design and construction of these non-binary codes for short block-lengths. Performance, cycle distribution and the minimum distance of the binary image of selected codes over AWGN is provided for information block-lengths as low as 64 bits.
This paper presents two complementary constructions of finite-length non-binary protograph-based codes with the focus on the short block-length regime. The first class is based on the existing approaches of applying the copy-and-permute operations to the constituent protograph with unweighted edges, followed by assigning non-binary scales to the edges of the derived graph. The second class is novel and is based on the so-called graph cover of a non-binary protograph: the original protograph has fixed edge scalings and copy-and-permute operations are applied to the edge-weighted protograph. The second class is arguably more restrictive, but in turn it offers simpler design and implementation. We provide design and construction of these non-binary codes for short block-lengths. Performance, cycle distribution and the minimum distance of the binary image of selected codes over AWGN is provided for information block-lengths as low as 64 bits.
This paper introduces a novel class of non-binary graph-based codes, built upon graph covers of non-binary protograph LDPC codes. This new ensemble is more restrictive than previously considered constructions, but in turn is much simpler to design and implement. The simplifications in design allow for the enumeration of codeword weight, trapping set size, stopping set size, and pseudo codeword weights, both as exact quantities in the finite-length regime and as corresponding growth rates in the asymptotic setting. The presented construction and the accompanying enumerations enhance the analytical toolbox of non-binary LDPC codes.
This paper provides a comprehensive analysis of nonbinary low-density parity check (LDPC) codes built out of protographs. We consider both random and constrained edge-weight labeling, and refer to the former as the unconstrained nonbinary protograph-based LDPC codes (U-NBPB codes) and to the latter as the constrained nonbinary protograph-based LDPC codes (C-NBPB codes). Equipped with combinatorial definitions extended to the nonbinary domain, ensemble enumerators of codewords, trapping sets, stopping sets, and pseudocodewords are calculated. The exact enumerators are presented in the finite-length regime, and the corresponding growth rates are calculated in the asymptotic regime. An EXIT chart tool for computing the iterative decoding thresholds of protograph-based LDPC codes is presented, followed by several examples of finite-length U-NBPB and C-NBPB codes with high performance. Throughout this paper, we provide accompanying examples, which demonstrate the advantage of nonbinary protograph-based LDPC codes over their binary counterparts and over random constructions. The results presented in this paper advance the analytical toolbox of nonbinary graph-based codes.
The finite-length performance of multi-edge spatially coupled low-density parity-check (SC-LDPC) codes over the binary erasure channel (BEC) is analyzed. Existing scaling laws are extended to arbitrary protograph base matrices that include puncturing patterns and multiple edges between nodes. A regular protograph-based SC-LDPC construction based on the (4; 8)-regular LDPC block code works well in the waterfall region compared to more involved rate-1/2 structures proposed to improve the threshold to minimum distance trade-off. Scaling laws are also used for code design and to estimate the block length of a given SC-LDPC code ensemble to match the performance of some other code. Estimates on the performance degradation are developed if the chain length varies.
A (v,g)-cage is a (not necessarily unique) smallest v-regular graph of girth g. On such a graph, a nonbinary (2,v)-regular low-density parity-check (LDPC) code can be defined such that the Tanner graph has girth 2g and the code length achieves the minimum possible. In this paper, we focus on two aspects of this class of codes, structural property and code optimization. We find that, in addition to those found previously, many cages can be used to construct structured LDPC codes. We show that all cages with even girth can be structured as protograph-based codes, many of which have block-circulant Tanner graphs. We also find that four cages with odd girth can be structured as protograph-based codes with block-circulant Tanner graphs. For code optimization, we develop an ontology-based approach. All possible inter-connected cycle patterns that lead to low symbol-weight codewords are identified to put together the ontology. By doing so, it becomes handleable to estimate and optimize distance spectrum of equivalent binary image codes. We further analyze some known codes from the Consultative Committee for Space Data Systems recommendation and design several new codes. Numerical results show that these codes have reasonably good minimum bit distance and perform well under iterative decoding.
We are undergoing a revolution in data. The ever-growing amount of information in our world has created an unprecedented demand for ultra-reliable, affordable, and resource-efficient data storage systems. Error-correcting codes, as a critical component of any memory device, will play a crucial role in the future of data storage.One particular class of error-correcting codes, known as graph-based codes, has drawn significant attention in both academia and in industry. Graph-based codes offer superior performance compared to traditional algebraic codes. Recently, it has been shown that non-binary graph-based codes, which operate over finite fields rather than binary alphabets, outperform their binary counterparts and exhibit outstanding overall performance. For this reason, these codes are particularly suitable for emerging data storage systems.In this dissertation, we present a comprehensive combinatorial analysis of non-binary graph-based codes. We perform both finite-length and asymptotic analyses for these codes, providing a systematic framework to evaluate and optimize various families of non-binary graph-based codes.In the finite-length case, we provide a mathematical characterization of the error floor problem, including a general definition of absorbing sets over non-binary alphabets. We consider several structured low-density parity-check (LDPC) codes, including quasi-cyclic and spatially-coupled codes, as well as unstructured LDPC codes. We offer design guidelines for non-binary LDPC codes with outstanding performance in extremely low error-rate regimes; making them excellent candidates for data storage applications.In the asymptotic case, we provide a novel toolbox for the evaluation of families of non-binary graph-based codes. By utilizing insights from graph theory and combinatorics, we establish enumerators for a general family of graph-based codes which are constructed based on protographs. We provide asymptotic distributions of codewords and trapping sets for the family of protograph-based codes. Furthermore, we present an asymptotic enumeration of binary and non-binary elementary absorbing sets for regular code ensembles.The contributions of this dissertation can potentially impact a broad range of data storage and communication technologies that require excellent performance in high-reliability regimes.
In this paper we design protograph-based LDPC codes with short block sizes. Mainly we consider rate 1/2 codes with input block sizes 64, 128, and 256 bits. To simplify the encoder and decoder implementations for high data rate transmission, the structure of the codes is based on protographs and circulants. These codes are designed for short block sizes based on maximizing the minimum distance and stopping set size subject to a constraint on the maximum variable node degree. In particular, we consider codes with variable node degrees between 3 and 5. Increasing the node degree leads to larger minimum distances, at the expense of smaller girth. Therefore, there is a trade-off between undetected error rate performance (improved by increasing minimum distance) and the degree of sub-optimality of the iterative decoders typically used (which are adversely affected by graph loops). Various LDPC codes are compared and simulation results are provided.