On the Computational Complexity of Blind Detection of Binary Linear Codes

Alexios Balatsoukas-Stimming, Aris Filos-Ratsikas

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Title of host publication2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers
Pages2449-2453
Number of pages5
ISBN (Electronic)978-1-5386-9291-2
DOIs
Publication statusPublished - 26 Sep 2019
Externally publishedYes
Event2019 IEEE International Symposium on Information Theory, ISIT 2019 - Paris, France
Duration: 7 Jul 201912 Jul 2019

Conference

Conference2019 IEEE International Symposium on Information Theory, ISIT 2019
Country/TerritoryFrance
CityParis
Period7/07/1912/07/19

Fingerprint

Dive into the research topics of 'On the Computational Complexity of Blind Detection of Binary Linear Codes'. Together they form a unique fingerprint.

Cite this