Detection and recognition of a binary linear code

https://doi.org/10.1016/S0166-218X(00)00353-XGet rights and content
Under an Elsevier user license
open archive

Abstract

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.

Keywords

Linear codes
Detection
Recognition
Reconstruction
NP-complete
Criterion
Moments

Cited by (0)

Expanded version of a talk presented at the Workshop on Coding and Cryptography (Paris, January 1999).

1

This work is supported by a grant of the DGA.