Bounds on List Decoding of Linearized Reed-Solomon Codes

Sven Puchinger; Johan Rosenkilde

doi:10.1109/ISIT45174.2021.9517777

Bounds on List Decoding of Linearized Reed-Solomon Codes

Sven Puchinger, Johan Rosenkilde

Computation, Information and Technology

GitHub Denmark Aps

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

3 Scopus citations

Abstract

Linearized Reed-Solomon (LRS) codes are sum-rank metric codes that fulfill the Singleton bound with equality. In the two extreme cases of the sum-rank metric, they coincide with Reed-Solomon codes (Hamming metric) and Gabidulin codes (rank metric). List decoding in these extreme cases is well-studied, and the two code classes behave very differently in terms of list size, but nothing is known for the general case. In this paper, we derive a lower bound on the list size for LRS codes, which is, for a large class of LRS codes, exponential directly above the Johnson radius. Furthermore, we show that some families of linearized Reed-Solomon codes with constant numbers of blocks cannot be list decoded beyond the unique decoding radius.

Original language	English
Title of host publication	2021 IEEE International Symposium on Information Theory, ISIT 2021 - Proceedings
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	154-159
Number of pages	6
ISBN (Electronic)	9781538682098
DOIs	https://doi.org/10.1109/ISIT45174.2021.9517777
State	Published - 12 Jul 2021
Event	2021 IEEE International Symposium on Information Theory, ISIT 2021 - Virtual, Melbourne, Australia Duration: 12 Jul 2021 → 20 Jul 2021

Publication series

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

Conference

Conference	2021 IEEE International Symposium on Information Theory, ISIT 2021
Country/Territory	Australia
City	Virtual, Melbourne
Period	12/07/21 → 20/07/21

Keywords

Linearized Reed-Solomon Codes
List Decoding
Sum-Rank Metric

Access to Document

10.1109/ISIT45174.2021.9517777

Cite this

Puchinger, S., & Rosenkilde, J. (2021). Bounds on List Decoding of Linearized Reed-Solomon Codes. In 2021 IEEE International Symposium on Information Theory, ISIT 2021 - Proceedings (pp. 154-159). (IEEE International Symposium on Information Theory - Proceedings; Vol. 2021-July). Institute of Electrical and Electronics Engineers Inc.. https://doi.org/10.1109/ISIT45174.2021.9517777

@inproceedings{eaeefee0fddb43f8ab209658f621e4c6,

title = "Bounds on List Decoding of Linearized Reed-Solomon Codes",

abstract = "Linearized Reed-Solomon (LRS) codes are sum-rank metric codes that fulfill the Singleton bound with equality. In the two extreme cases of the sum-rank metric, they coincide with Reed-Solomon codes (Hamming metric) and Gabidulin codes (rank metric). List decoding in these extreme cases is well-studied, and the two code classes behave very differently in terms of list size, but nothing is known for the general case. In this paper, we derive a lower bound on the list size for LRS codes, which is, for a large class of LRS codes, exponential directly above the Johnson radius. Furthermore, we show that some families of linearized Reed-Solomon codes with constant numbers of blocks cannot be list decoded beyond the unique decoding radius.",

keywords = "Linearized Reed-Solomon Codes, List Decoding, Sum-Rank Metric",

author = "Sven Puchinger and Johan Rosenkilde",

note = "Publisher Copyright: {\textcopyright} 2021 IEEE.; 2021 IEEE International Symposium on Information Theory, ISIT 2021 ; Conference date: 12-07-2021 Through 20-07-2021",

year = "2021",

month = jul,

day = "12",

doi = "10.1109/ISIT45174.2021.9517777",

language = "English",

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

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "154--159",

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

}

Puchinger, S & Rosenkilde, J 2021, Bounds on List Decoding of Linearized Reed-Solomon Codes. in 2021 IEEE International Symposium on Information Theory, ISIT 2021 - Proceedings. IEEE International Symposium on Information Theory - Proceedings, vol. 2021-July, Institute of Electrical and Electronics Engineers Inc., pp. 154-159, 2021 IEEE International Symposium on Information Theory, ISIT 2021, Virtual, Melbourne, Australia, 12/07/21. https://doi.org/10.1109/ISIT45174.2021.9517777

Bounds on List Decoding of Linearized Reed-Solomon Codes. / Puchinger, Sven; Rosenkilde, Johan.
2021 IEEE International Symposium on Information Theory, ISIT 2021 - Proceedings. Institute of Electrical and Electronics Engineers Inc., 2021. p. 154-159 (IEEE International Symposium on Information Theory - Proceedings; Vol. 2021-July).

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

TY - GEN

T1 - Bounds on List Decoding of Linearized Reed-Solomon Codes

AU - Puchinger, Sven

AU - Rosenkilde, Johan

PY - 2021/7/12

Y1 - 2021/7/12

N2 - Linearized Reed-Solomon (LRS) codes are sum-rank metric codes that fulfill the Singleton bound with equality. In the two extreme cases of the sum-rank metric, they coincide with Reed-Solomon codes (Hamming metric) and Gabidulin codes (rank metric). List decoding in these extreme cases is well-studied, and the two code classes behave very differently in terms of list size, but nothing is known for the general case. In this paper, we derive a lower bound on the list size for LRS codes, which is, for a large class of LRS codes, exponential directly above the Johnson radius. Furthermore, we show that some families of linearized Reed-Solomon codes with constant numbers of blocks cannot be list decoded beyond the unique decoding radius.

AB - Linearized Reed-Solomon (LRS) codes are sum-rank metric codes that fulfill the Singleton bound with equality. In the two extreme cases of the sum-rank metric, they coincide with Reed-Solomon codes (Hamming metric) and Gabidulin codes (rank metric). List decoding in these extreme cases is well-studied, and the two code classes behave very differently in terms of list size, but nothing is known for the general case. In this paper, we derive a lower bound on the list size for LRS codes, which is, for a large class of LRS codes, exponential directly above the Johnson radius. Furthermore, we show that some families of linearized Reed-Solomon codes with constant numbers of blocks cannot be list decoded beyond the unique decoding radius.

KW - Linearized Reed-Solomon Codes

KW - List Decoding

KW - Sum-Rank Metric

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

U2 - 10.1109/ISIT45174.2021.9517777

DO - 10.1109/ISIT45174.2021.9517777

M3 - Conference contribution

AN - SCOPUS:85115061363

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 154

EP - 159

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

PB - Institute of Electrical and Electronics Engineers Inc.

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

Y2 - 12 July 2021 through 20 July 2021

ER -

Bounds on List Decoding of Linearized Reed-Solomon Codes

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this