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.
This dissertation presents a systematic exposition on finite-block-length coding theory and practice. We begin with the task of identifying the maximum achievable rates over noisy, finite-block-length constrained channels, referred to as (ε, n)-capacity Cεn, with ε denoting target block-error probability and n the block length. We characterize how the optimum codes look like over finite-block-length constrained channels. Constructing good, short-block-length error-correcting codes defined on sparse graphs is the focus of the thesis. We propose a new, general method for constructing Tanner graphs having a large girth by progressively establishing edges or connections between symbol and check nodes in an edge-by-edge manner, called progressive edge-growth (PEG) construction. Lower bounds on the girth of PEG Tanner graphs and on the minimum distance of the resulting low-density parity-check (LDPC) codes are derived in terms of parameters of the graphs. The PEG construction attains essentially the same girth as Gallager's explicit construction for regular graphs, both of which meet or exceed an extension of the Erdös-Sachs bound. The PEG construction proves to be powerful for generating good, short-block-length binary LDPC codes. Furthermore, we show that the binary interpretation of GF(2b) codes on the cycle Tanner graph TG(2, dc), if b grows sufficiently large, can be used over the binary-input additive white Gaussian noise (AWGN) channel as "good code for optimum decoding" and "good code for iterative decoding". Codes on sparse graphs are often decoded iteratively by a sum-product algorithm (SPA) with low complexity. We investigate efficient digital implementations of the SPA for decoding binary LDPC codes from both the architectural and algorithmic point of view, and describe new reduced-complexity derivatives thereof. The unified treatment of decoding techniques for LDPC codes provides flexibility in selecting the appropriate design point in high-speed applications from a performance, latency, and computational complexity perspective.