Largely constrained noise-guessing decoding of short LDPC codes

Abstract

When using guessing random additive noise decoding (GRAND) to decode linear block codes (LBCs), the list of error patterns to be tested is blind to any structure in the parity-check matrix. This paper starts by proposing simple and general set partitioning (SP) constraints that reduce the number of possible patterns to less than half when decoding random linear codes (RLCs). Sparser parity-check matrices induce faster decoding when using SP, but at the expense of a severe performance loss. This loss can be mostly recovered by considering regular or quasi-regular low-density parity-check (LDPC) codes. Given their structure, one can apply the proposed Sieving-GRAND that, for a given support of the syndrome, “filters” possible error positions. Subsequently, a guessing approach is applied to those few positions. The filtering threshold can be successively relaxed to extend the set of candidate positions. We further propose a largely constrained GRAND mechanism (LC-GRAND), which takes advantage of zeroed syndrome positions to efficiently eliminate incompatible error patterns, while not requiring quasi-regular LDPC codes. The two main proposed techniques lead to similar sharp pruning of the search space. For example, LC-GRAND, in combination with SP, reduces the number of membership tests to ≃ 1%. All the proposed hard-decoding techniques retain the same decoding performance of unconstrained GRAND.