Identifying an unknown code by partial Gaussian elimination

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.