Bounds on polynomial-time list decoding of rank metric codes

Antonia Wachter-Zeh

doi:10.1109/ISIT.2013.6620280

Bounds on polynomial-time list decoding of rank metric codes

Antonia Wachter-Zeh

University of Ulm

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

2 Scopus citations

Abstract

This contribution provides bounds on the list size of rank metric codes in order to understand whether polynomial-time list decoding is possible or not. First, an exponential upper bound is derived, which holds for any rank metric code of length n and minimum rank distance d. Second, a lower bound proves that there exists a rank metric code over F_qm of length n ≤ m such that the list size is exponential in the length of the code for any radius greater than half the minimum distance. This implies that in rank metric there cannot exist a polynomial upper bound depending only on n and d as the Johnson bound for Hamming metric. These bounds reveal significant differences between codes in Hamming and rank metric.

Original language	English
Title of host publication	2013 IEEE International Symposium on Information Theory, ISIT 2013
Pages	519-523
Number of pages	5
DOIs	https://doi.org/10.1109/ISIT.2013.6620280
State	Published - 2013
Externally published	Yes
Event	2013 IEEE International Symposium on Information Theory, ISIT 2013 - Istanbul, Turkey Duration: 7 Jul 2013 → 12 Jul 2013

Publication series

Name	IEEE International Symposium on Information Theory - Proceedings
ISSN (Print)	2157-8095

Conference

Conference	2013 IEEE International Symposium on Information Theory, ISIT 2013
Country/Territory	Turkey
City	Istanbul
Period	7/07/13 → 12/07/13

Keywords

List Decoding
Rank Metric Codes

Access to Document

10.1109/ISIT.2013.6620280

Cite this

@inproceedings{c2be6c25641e4c7f9bb57d1db15ea170,

title = "Bounds on polynomial-time list decoding of rank metric codes",

abstract = "This contribution provides bounds on the list size of rank metric codes in order to understand whether polynomial-time list decoding is possible or not. First, an exponential upper bound is derived, which holds for any rank metric code of length n and minimum rank distance d. Second, a lower bound proves that there exists a rank metric code over Fqm of length n ≤ m such that the list size is exponential in the length of the code for any radius greater than half the minimum distance. This implies that in rank metric there cannot exist a polynomial upper bound depending only on n and d as the Johnson bound for Hamming metric. These bounds reveal significant differences between codes in Hamming and rank metric.",

keywords = "List Decoding, Rank Metric Codes",

author = "Antonia Wachter-Zeh",

year = "2013",

doi = "10.1109/ISIT.2013.6620280",

language = "English",

isbn = "9781479904464",

series = "IEEE International Symposium on Information Theory - Proceedings",

pages = "519--523",

booktitle = "2013 IEEE International Symposium on Information Theory, ISIT 2013",

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

}

Wachter-Zeh, A 2013, Bounds on polynomial-time list decoding of rank metric codes. in 2013 IEEE International Symposium on Information Theory, ISIT 2013., 6620280, IEEE International Symposium on Information Theory - Proceedings, pp. 519-523, 2013 IEEE International Symposium on Information Theory, ISIT 2013, Istanbul, Turkey, 7/07/13. https://doi.org/10.1109/ISIT.2013.6620280

TY - GEN

T1 - Bounds on polynomial-time list decoding of rank metric codes

AU - Wachter-Zeh, Antonia

PY - 2013

Y1 - 2013

N2 - This contribution provides bounds on the list size of rank metric codes in order to understand whether polynomial-time list decoding is possible or not. First, an exponential upper bound is derived, which holds for any rank metric code of length n and minimum rank distance d. Second, a lower bound proves that there exists a rank metric code over Fqm of length n ≤ m such that the list size is exponential in the length of the code for any radius greater than half the minimum distance. This implies that in rank metric there cannot exist a polynomial upper bound depending only on n and d as the Johnson bound for Hamming metric. These bounds reveal significant differences between codes in Hamming and rank metric.

AB - This contribution provides bounds on the list size of rank metric codes in order to understand whether polynomial-time list decoding is possible or not. First, an exponential upper bound is derived, which holds for any rank metric code of length n and minimum rank distance d. Second, a lower bound proves that there exists a rank metric code over Fqm of length n ≤ m such that the list size is exponential in the length of the code for any radius greater than half the minimum distance. This implies that in rank metric there cannot exist a polynomial upper bound depending only on n and d as the Johnson bound for Hamming metric. These bounds reveal significant differences between codes in Hamming and rank metric.

KW - List Decoding

KW - Rank Metric Codes

UR - https://www.scopus.com/pages/publications/84890411959

U2 - 10.1109/ISIT.2013.6620280

DO - 10.1109/ISIT.2013.6620280

M3 - Conference contribution

AN - SCOPUS:84890411959

SN - 9781479904464

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 519

EP - 523

BT - 2013 IEEE International Symposium on Information Theory, ISIT 2013

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

Y2 - 7 July 2013 through 12 July 2013

ER -

Bounds on polynomial-time list decoding of rank metric codes

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this