Quasi-cyclic LDPC codes reach minimum distance limit with large lifts
CPM-LDPC Codes Attaining the Minimum-Distance Bound
Information Theory
Summary
This paper looks at a type of error-correcting code used in digital communication, called CPM-LDPC codes. These codes have a certain mathematical limit on how well they can detect and correct errors, called the minimum distance bound. The authors show that for these codes, it is possible to reach this limit exactly when the codes are built with large enough sizes, using specific mathematical constructions. They also provide examples with smaller sizes where the codes achieve high minimum distances, supported by computational checks.
What this means in practice
- •For communication engineers: Design error-correcting codes that reliably meet minimum error detection limits in digital communication systems using large-lift CPM-LDPC codes.
- •For storage system designers: Improve data integrity in storage devices by deploying CPM-LDPC codes with guaranteed minimum distance properties for better error detection.
Authors
Kenta Kasai
Abstract
We study binary quasi-cyclic LDPC codes whose parity-check matrices are full arrays of single circulant permutation matrices (CPMs), referred to here as CPM-LDPC codes. Their minimum distance is at most $(J+1)!$, where $J$ is the column weight. For every fixed pair of column and row weights $2\le J<L$, we show that this bound is attained for all sufficiently large integer lift sizes. First, we give one integer exponent matrix independent of the lift size $P$. Second, we show that independent uniform exponent choices attain the bound with probability $1-O_{J,L}(P^{-1})$. Both proofs use cycle conditions required by low-weight codewords and a lower bound on the number of terms in vectors satisfying polynomial check equations. Neither construction requires $P$ to be prime. We also give small-lift arrays attaining the bound 24 for $J=3$, $L=4,\ldots,8$, and arrays with distance at least 28 for $J=4$, $L=5,\ldots,8$, together with computational distance verification.