On the Computational Complexity of Blind Detection of Binary Linear Codes

Alexios Balatsoukas-Stimming; Aris Filos-Ratsikas

doi:10.1109/ISIT.2019.8849467

On the Computational Complexity of Blind Detection of Binary Linear Codes

Alexios Balatsoukas-Stimming, Aris Filos-Ratsikas

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-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 language	English
Title of host publication	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers
Pages	2449-2453
Number of pages	5
ISBN (Electronic)	978-1-5386-9291-2
DOIs	https://doi.org/10.1109/ISIT.2019.8849467
Publication status	Published - 26 Sept 2019
Externally published	Yes
Event	2019 IEEE International Symposium on Information Theory, ISIT 2019 - Paris, France Duration: 7 Jul 2019 → 12 Jul 2019

Conference

Conference	2019 IEEE International Symposium on Information Theory, ISIT 2019
Country/Territory	France
City	Paris
Period	7/07/19 → 12/07/19

Access to Document

10.1109/ISIT.2019.8849467

Cite this

@inproceedings{9dc9e242bd0f416d9e6d3fb691659267,

title = "On the Computational Complexity of Blind Detection of Binary Linear Codes",

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.",

author = "Alexios Balatsoukas-Stimming and Aris Filos-Ratsikas",

year = "2019",

month = sep,

day = "26",

doi = "10.1109/ISIT.2019.8849467",

language = "English",

pages = "2449--2453",

booktitle = "2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

note = "2019 IEEE International Symposium on Information Theory, ISIT 2019 ; Conference date: 07-07-2019 Through 12-07-2019",

}

Balatsoukas-Stimming, A & Filos-Ratsikas, A 2019, On the Computational Complexity of Blind Detection of Binary Linear Codes. in 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings., 8849467, Institute of Electrical and Electronics Engineers, pp. 2449-2453, 2019 IEEE International Symposium on Information Theory, ISIT 2019, Paris, France, 7/07/19. https://doi.org/10.1109/ISIT.2019.8849467

On the Computational Complexity of Blind Detection of Binary Linear Codes. / Balatsoukas-Stimming, Alexios; Filos-Ratsikas, Aris.
2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings. Institute of Electrical and Electronics Engineers, 2019. p. 2449-2453 8849467.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - On the Computational Complexity of Blind Detection of Binary Linear Codes

AU - Balatsoukas-Stimming, Alexios

AU - Filos-Ratsikas, Aris

PY - 2019/9/26

Y1 - 2019/9/26

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85073166644&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2019.8849467

DO - 10.1109/ISIT.2019.8849467

M3 - Conference contribution

SP - 2449

EP - 2453

BT - 2019 IEEE International Symposium on Information Theory, ISIT 2019 - Proceedings

PB - Institute of Electrical and Electronics Engineers

T2 - 2019 IEEE International Symposium on Information Theory, ISIT 2019

Y2 - 7 July 2019 through 12 July 2019

ER -

On the Computational Complexity of Blind Detection of Binary Linear Codes

Abstract

Conference

Access to Document

Other files and links

Fingerprint

Cite this