This is one of several papers published in Designs, Codes and Cryptography comprising the “Special Issue on Coding and Cryptography”.
Part of this work was supported by the Commission of the European Communities through the Horizon 2020 program under Project Number 645622 PQCRYPTO.
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
We consider in this paper the problem of reconstructing a linear code from a set of noisy codewords. We revisit the algorithms that have been devised for solving this problem and show that by generalizing and mixing two approaches that have been proposed in this setting, we obtain a significantly better algorithm. It basically consists in setting up a matrix whose rows are the noisy codewords, then running a partial Gaussian algorithm on it and detecting a small set of columns outside the echelon part of the matrix whose sum is sparse. We view the last task of the algorithm as an instance of the well known close neighbors search problem and we use an algorithm due to Dubiner to solve it more efficiently than the naive projection method which is generally invoked in this case. We analyze the complexity of our algorithm by focusing on an important practical case, namely when the code is an LDPC code. In doing so, we also obtain a result of independent interest, namely a tight upper-bound on the expected weight distribution of the dual of an LDPC code in a form that allows to derive an asymptotic formula.