Linear growing minimum distance of ultra-sparse non-binary cluster-LDPC codes

In this paper, we study the asymptotic minimum distance of non-binary cluster-LDPC codes whose subjacent binary parity-check matrix is composed of localized density of ones, concentrated in clusters of bits. A particular attention is given to cluster codes represented by ultra-sparse bipartite graphs, in the sense that each symbol-node is connected to exactly d_v = 2 constraint-nodes. We derive a lower bound on the minimum distance of non-binary cluster-LDPC codes and we show that there exist ensembles of ultra-sparse codes whose minimum distance grows linearly with the code length (with probability going to 1 as the code length goes to infinity). This result is in contrast with “classical” non-binary LDPC codes based on graphs with strictly regular d_v = 2 symbol-nodes, whose minimum distance grows at most logarithmically with the code length. We also show that one can build practical non-binary cluster-LDPC codes with various finite codeword lengths, whose minimum distance is close to the Gilbert-Varshamov bound.