Upper and Lower Bounds for Continuous Non-Malleable Codes

Rafail Ostrovsky, Giuseppe Persiano, Daniele Venturi +1 more

Nils Fleischhacker, Vipul Goyal, Abhishek Jain +2 more

Yoones Hashemi, Amir H. Banihashemi

In this letter, we obtain lower and upper bounds on the minimum distance dminof low-density parity-check (LDPC) codes. The bounds are derived by categorizing the non-zero code words of an LDPC code into two categories of elementary and non-elementary. The first category contains code words whose induced subgraph has only degree-2 check nodes. We propose an efficient search algorithm that can find the elementary code words of an LDPC code with weight less than a certain value amax, exhaustively. We also derive a lower bound Lneon the weight of non-elementary code words. By performing the search with amax= Lne, we either obtain an elementary code word with the smallest weight dmin, or establish the lower bound of Lneon dmin. For the upper bound, we modify our search algorithm to reach elementary codewords of larger weights at the cost of being non-exhaustive. Once such a codeword is found, its weight acts as an upper bound on dmin. We examine a large number of regular and irregular LDPC codes, and demonstrate the efficiency and versatility of our technique in finding lower and upper bounds on, and in many cases the exact value of, dmin. Finding dmin, or establishing search-based lower or upper bounds, for many of the examined codes are out of the reach of any existing algorithm.

Özkaya, Buket, Özbudak, Ferruh

David Declercq, Valentin Savin, Lam Pham Sy

This paper continues a previous work on non-binary cluster-LDPC codes. Such codes are defined by locally dense parity-check matrices, with (possibly rectangular) dense clusters of bits, but which are cluster-wise sparse. We derive a lower bound on the minimum distance of non-binary cluster-LDPC codes that is based on the topological properties of the underlying bipartite graph. We also propose an optimization procedure, which allows designing finite length codes with large minimum distance, even in the extreme case of codes defined by ultra-sparse graphs, i.e. graphs with all symbol-nodes of degree dv= 2. Furthermore, we provide asymptotic thresholds of ensembles of non-binary cluster-LDPC codes, which are computed exactly under the Belief Propagation decoding, and upper-bounded under the Maximum a Posteriori (MAP) decoding. We show that the MAP-threshold upper bounds, which are conjunctured to be tight, quickly approach the channel capacity, which confirms the excellent minimal distance properties of non-binary cluster-LDPC codes.

Nasir Al-Darwish