Detection and recognition of a binary linear code Original Research Article

We examine the problem of detecting and recognizing a binary linear code in a binary stream under the following hypotheses: We assume the observed binary stream has crossed a [n,k]-encoder and a binary symmetric channel, and we can extract the consecutive (erroneous) codewords from it. The problem is to find the nearest (for the Hamming distance) [n,k]-code from these words. We formalize an associated decision problem and prove it is NP-complete. We then adopt a more pragmatic point of view and consider generalities about detection and recognition problems. Algorithms based on dual codewords recognition are suggested which will be efficient for codes of length up to 512 if the codewords contain no more than 1.5 errors on average and from which one could derive an algorithm to recognize the length, the dimension and the synchronisation of the code.