Sparsifying Parity-Check Matrices
This work addresses faster decoding for error-correcting codes, which is incremental as it builds on existing methods with specific optimizations.
The paper tackles the problem of minimizing the number of one-entries in parity-check matrices to speed up maximum-likelihood decoding, proposing a heuristic with simulated annealing and greedy search that reduces decoding time, especially for large codes, achieving results in minutes to hours on standard hardware.
Parity check matrices (PCMs) are used to define linear error correcting codes and ensure reliable information transmission over noisy channels. The set of codewords of such a code is the null space of this binary matrix. We consider the problem of minimizing the number of one-entries in parity-check matrices. In the maximum-likelihood (ML) decoding method, the number of ones in PCMs is directly related to the time required to decode messages. We propose a simple matrix row manipulation heuristic which alters the PCM, but not the code itself. We apply simulated annealing and greedy local searches to obtain PCMs with a small number of one entries quickly, i.e. in a couple of minutes or hours when using mainstream hardware. The resulting matrices provide faster ML decoding procedures, especially for large codes.