On the Computational Complexity of Blind Detection of Binary Linear Codes

Alexios Balatsoukas-Stimming, Aris Filos-Ratsikas

Onderzoeksoutput: Andere bijdrageOverige bijdrageAcademic

3 Citaten (Scopus)


In this work, we study the computational complexity of the Minimum Distance Code Detection problem. In this problem, we are given a set of noisy codeword observations and we wish to find a code in a set of linear codes \mathcal{C} of a given dimension k, for which the sum of distances between the observations and the code is minimized. We prove that, for the practically relevant case when the set \mathcal{C} only contains a fixed number of candidate linear codes, the detection problem is NP-hard and we identify a number of interesting open questions related to the code detection problem.

Originele taal-2Engels
Aantal pagina's5
ISBN van elektronische versie9781538692912
StatusGepubliceerd - jul 2019

Publicatie series

NaamIEEE International Symposium on Information Theory

Citeer dit