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 contribution

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 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 C only contains a fixed number of candidate linear codes, the detection problem is NPhard 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)
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages2449-2453
Number of pages5
ISBN (Electronic)978-1-5386-9291-2, 978-1-5386-9290-5
ISBN (Print)978-1-5386-9292-9
DOIs
Publication statusPublished - 26 Sep 2019
Event2019 IEEE International Symposium on Information Theory
- Paris, France
Duration: 7 Jul 201912 Jul 2019

Symposium

Symposium2019 IEEE International Symposium on Information Theory
Abbreviated titleISIT 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