In this paper, we construct protograph-based spatially coupled low-density parity-check (LDPC) codes by coupling together a series of L disjoint, or uncoupled, LDPC code Tanner graphs into a single ...coupled chain. By varying L , we obtain a flexible family of code ensembles with varying rates and frame lengths that can share the same encoding and decoding architecture for arbitrary L . We demonstrate that the resulting codes combine the best features of optimized irregular and regular codes in one design: capacity approaching iterative belief propagation (BP) decoding thresholds and linear growth of minimum distance with block length. In particular, we show that, for sufficiently large L , the BP thresholds on both the binary erasure channel and the binary-input additive white Gaussian noise channel saturate to a particular value significantly better than the BP decoding threshold and numerically indistinguishable from the optimal maximum a posteriori decoding threshold of the uncoupled LDPC code. When all variable nodes in the coupled chain have degree greater than two, asymptotically the error probability converges at least doubly exponentially with decoding iterations and we obtain sequences of asymptotically good LDPC codes with fast convergence rates and BP thresholds close to the Shannon limit. Further, the gap to capacity decreases as the density of the graph increases, opening up a new way to construct capacity achieving codes on memoryless binary-input symmetric-output channels with low-complexity BP decoding.
A new class of codes, Extended Product (EPC) Codes, consisting of a product code with a number of extra parities added, is presented and applications for erasure decoding are discussed. An upper ...bound on the minimum distance of EPC codes is given, as well as constructions meeting the bound for some relevant cases. A special case of EPC codes, Extended Integrated Interleaved (EII) codes, which naturally unify Integrated Interleaved (II) codes and product codes, is defined and studied in detail. It is shown that EII codes often improve the minimum distance of II codes with the same rate, and they enhance the decoding algorithm by allowing decoding on columns as well as on rows. It is also shown that EII codes allow for encoding II codes with an uniform distribution of the parity symbols.
Polar Subcodes Trifonov, Peter; Miloslavskaya, Vera
IEEE journal on selected areas in communications,
02/2016, Volume:
34, Issue:
2
Journal Article
Peer reviewed
Open access
An extension of polar codes is proposed, which allows some of the frozen symbols, called dynamic frozen symbols, to be data-dependent. A construction of polar codes with dynamic frozen symbols, being ...subcodes of extended BCH codes, is proposed. The proposed codes have higher minimum distance than classical polar codes, but still can be efficiently decoded using the successive cancellation algorithm and its extensions. The codes with Arikan, extended BCH and Reed-Solomon kernel are considered. The proposed codes are shown to outperform LDPC and turbo codes, as well as polar codes with CRC.
In this paper, we study the cycle distribution of random low-density parity-check (LDPC) codes, randomly constructed protograph-based LDPC codes, and random quasi-cyclic (QC) LDPC codes. We prove ...that for a random bipartite graph, with a given (irregular) degree distribution, the distributions of cycles of different length tend to independent Poisson distributions, as the size of the graph tends to infinity. We derive asymptotic upper and lower bounds on the expected values of the Poisson distributions that are independent of the size of the graph, and only depend on the degree distribution and the cycle length. For a random lift of a bi-regular protograph, we prove that the asymptotic cycle distributions are essentially the same as those of random bipartite graphs as long as the degree distributions are identical. For random QC-LDPC codes, however, we show that the cycle distribution can be quite different from the other two categories. In particular, depending on the protograph and the value of <inline-formula> <tex-math notation="LaTeX">c </tex-math></inline-formula>, the expected number of cycles of length <inline-formula> <tex-math notation="LaTeX">c </tex-math></inline-formula>, in this case, can be either <inline-formula> <tex-math notation="LaTeX">\Theta (N) </tex-math></inline-formula> or <inline-formula> <tex-math notation="LaTeX">\Theta (1) </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">N </tex-math></inline-formula> is the lifting degree (code length). We also provide numerical results that match our theoretical derivations. Our results provide a theoretical foundation for emperical results that were reported in the literature but were not well-justified. They can also be used for the analysis and design of LDPC codes and associated algorithms that are based on cycles.
Locally repairable codes (LRCs) are considered with equal or unequal localities, local distances, and local field sizes. An explicit two-layer architecture with a sum-rank outer code is obtained, ...having disjoint local groups and achieving maximal recoverability (MR) for all families of local linear codes (MDS or not) simultaneously, up to a specified maximum locality <inline-formula> <tex-math notation="LaTeX">r </tex-math></inline-formula>. Furthermore, the local linear codes (thus the localities, local distances, and local fields) can be efficiently and dynamically modified without global recoding or changes in architecture or outer code, while preserving the MR property, easily adapting to new configurations in storage or new hot and cold data. In addition, local groups and file components can be added, removed or updated without global recoding. The construction requires global fields of size roughly <inline-formula> <tex-math notation="LaTeX">g^{r} </tex-math></inline-formula>, for <inline-formula> <tex-math notation="LaTeX">g </tex-math></inline-formula> local groups and maximum or specified locality <inline-formula> <tex-math notation="LaTeX">r </tex-math></inline-formula>. For equal localities, these global fields are smaller than those of previous MR-LRCs when <inline-formula> <tex-math notation="LaTeX">r \leq h </tex-math></inline-formula> (global parities). For unequal localities, they provide an exponential field size reduction on all previous best known MR-LRCs. For bounded localities and a large number of local groups, the global erasure-correction complexity of the given construction is comparable to that of Tamo-Barg codes or Reed-Solomon codes with local replication, while local repair is as efficient as for the Cartesian product of the local codes. Reed-Solomon codes with local replication and Cartesian products are recovered from the given construction when <inline-formula> <tex-math notation="LaTeX">r=1 </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">h = 0 </tex-math></inline-formula>, respectively. The given construction can also be adapted to provide hierarchical MR-LRCs for all types of hierarchies and parameters. Finally, subextension subcodes and sum-rank alternant codes are introduced to obtain further exponential field size reductions, at the expense of lower information rates.
In this paper, we propose new constructions for regular girth-8 quasi-cyclic low-density parity-check (QC-LDPC) codes based on circulant permutation matrices (CPM). The constructions assume ...symmetries in the structure of the parity-check matrix and employ a greedy exhaustive search algorithm to find the permutation shifts of the CPMs. As a result of symmetries, the new codes have a more compact representation compared with their counterparts. In majority of cases, also, they achieve the girth 8 at a shorter block length for the same degree distribution (code rate). Deterministic (explicit) constructions are also presented to expand the proposed parity-check matrices to larger block lengths and higher rates. The proposed long high-rate codes are often substantially shorter than regular girth-8 QC-LDPC codes of similar rate in the literature. Simulation results demonstrate that the proposed symmetric codes have competitive performance in comparison with similar existing QC-LDPC codes that lack symmetry.
We prove that there is a Hermitian self-orthogonal <inline-formula> <tex-math notation="LaTeX">k </tex-math></inline-formula>-dimensional truncated generalised Reed-Solomon code of length ...<inline-formula> <tex-math notation="LaTeX">n \leqslant q^{2} </tex-math></inline-formula> over <inline-formula> <tex-math notation="LaTeX">{\mathbb F}_{q^{2}} </tex-math></inline-formula> if and only if there is a polynomial <inline-formula> <tex-math notation="LaTeX">g \in {\mathbb F}_{q^{2}} </tex-math></inline-formula> of degree at most <inline-formula> <tex-math notation="LaTeX">(q-k)q-1 </tex-math></inline-formula> such that <inline-formula> <tex-math notation="LaTeX">g+g^{q} </tex-math></inline-formula> has <inline-formula> <tex-math notation="LaTeX">q^{2}-n </tex-math></inline-formula> distinct zeros. This allows us to determine the smallest <inline-formula> <tex-math notation="LaTeX">n </tex-math></inline-formula> for which there is a Hermitian self-orthogonal <inline-formula> <tex-math notation="LaTeX">k </tex-math></inline-formula>-dimensional truncated generalised Reed-Solomon code of length <inline-formula> <tex-math notation="LaTeX">n </tex-math></inline-formula> over <inline-formula> <tex-math notation="LaTeX">{\mathbb F}_{q^{2}} </tex-math></inline-formula>, verifying a conjecture of Grassl and Rötteler. We also provide examples of Hermitian self-orthogonal <inline-formula> <tex-math notation="LaTeX">k </tex-math></inline-formula>-dimensional generalised Reed-Solomon codes of length <inline-formula> <tex-math notation="LaTeX">q^{2}+1 </tex-math></inline-formula> over <inline-formula> <tex-math notation="LaTeX">{\mathbb F}_{q^{2}} </tex-math></inline-formula>, for <inline-formula> <tex-math notation="LaTeX">k=q-1 </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">q </tex-math></inline-formula> an odd power of two.
Like classical block codes, a locally repairable code also obeys the Singleton-type bound (we call a locally repairable code optimal if it achieves the Singleton-type bound). In the breakthrough work ...of Tamo and Barg, several classes of optimal locally repairable codes were constructed via subcodes of Reed-Solomon codes. Thus, the lengths of the codes given by Tamo and Barg are upper bounded by the code alphabet size q. Recently, it was proved through the extension of construction by Tamo and Barg that the length of q-ary optimal locally repairable codes can be q +1 by Jin et al. Surprisingly, Barg et al. presented a few examples of q-ary optimal locally repairable codes of small distance and locality with code length achieving roughly q 2 . Very recently, it was further shown in the work of Li et al. that there exist q-ary optimal locally repairable codes with the length bigger than q+1 and the distance proportional to n. Thus, it becomes an interesting and challenging problem to construct new families of q-ary optimal locally repairable codes of length bigger than q+1. In this paper, we construct a class of optimal locally repairable codes of distances 3 and 4 with unbounded length (i.e., length of the codes is independent of the code alphabet size). Our technique is through cyclic codes with particular generator and parity-check polynomials that are carefully chosen.
Binary Linear Locally Repairable Codes Pengfei Huang; Yaakobi, Eitan; Uchikawa, Hironori ...
IEEE transactions on information theory,
11/2016, Volume:
62, Issue:
11
Journal Article
Peer reviewed
Open access
Locally repairable codes (LRCs) are a class of codes designed for the local correction of erasures. They have received considerable attention in recent years due to their applications in distributed ...storage. Most existing results on LRCs do not explicitly take into consideration the field size q, i.e., the size of the code alphabet. In particular, for the binary case, only a few results are known. In this paper, we present an upper bound on the minimum distance d of linear LRCs with availability, based on the work of Cadambe and Mazumdar. The bound takes into account the code length n, dimension k, locality r, availability t, and field size q. Then, we study the binary linear LRCs in three aspects. First, we focus on analyzing the locality of some classical codes, i.e., cyclic codes and Reed-Muller codes, and their modified versions, which are obtained by applying the operations of extend, shorten, expurgate, augment, and lengthen. Next, we construct LRCs using phantom parity-check symbols and multi-level tensor product structure, respectively. Compared with other previous constructions of binary LRCs with fixed locality or minimum distance, our construction is much more flexible in terms of code parameters, and gives various families of high-rate LRCs, some of which are shown to be optimal with respect to their minimum distance. Finally, the availability of LRCs is studied. We investigate the locality and availability properties of several classes of one-step majority-logic decodable codes, including cyclic simplex codes, cyclic difference-set codes, and 4-cycle free regular low-density parity-check codes. We also show the construction of a long LRC with availability from a short one-step majority-logic decodable code.
PDF
