Abstract
Despite numerous results about the list decoding of Hammingmetric codes, development of list decoding on rankmetric codes is not as rapid as its counterpart. The bound of list decoding obeys the GilbertVarshamov bound in both the metrics. In the case of the Hammingmetric, the GilbertVarshamov bound is a tradeoff among rate, decoding radius and alphabet size, while in the case of the rankmetric, the GilbertVarshamov bound is a tradeoff among rate, decoding radius and columntorow ratio (i.e., the ratio between the numbers of columns and rows). Hence, alphabet size and columntorow ratio play a similar role for list decodability in each metric. In the case of the Hammingmetric, it is more challenging to list decode codes over smaller alphabets. In contrast, in the case of the rankmetric, it is more difficult to list decode codes with large columntorow ratio. In particular, it is extremely difficult to list decode square matrix rankmetric codes (i.e., the columntorow ratio is equal to 1).
The main purpose of this paper is to explicitly construct a class of rankmetric codes 𝒞 of rate R with the columntorow ratio up to 2/3 and efficiently list decode these codes with decoding radius beyond the decoding radius (1R)/2 (note that (1R)/2 is at least half of relative minimum distance δ). In literature, the largest columntorow ratio of rankmetric codes that can be efficiently list decoded beyond half of minimum distance is 1/2. Thus, it is greatly desired to efficiently design list decoding algorithms for rankmetric codes with the columntorow ratio bigger than 1/2 or even close to 1. Our key idea is to compress an element of the field F_qⁿ into a smaller F_qsubspace via a linearized polynomial. Thus, the columntorow ratio gets increased at the price of reducing the code rate. Our result shows that the compression technique is powerful and it has not been employed in the topic of list decoding of both the Hamming and rank metrics. Apart from the above algebraic technique, we follow some standard techniques to prune down the list. The algebraic idea enables us to pin down the message into a structured subspace of dimension linear in the number n of columns. This "periodic" structure allows us to preencode the message to prune down the list.
BibTeX  Entry
@InProceedings{liu_et_al:LIPIcs.ICALP.2023.89,
author = {Liu, Shu and Xing, Chaoping and Yuan, Chen},
title = {{List Decoding of RankMetric Codes with RowToColumn Ratio Bigger Than 1/2}},
booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)},
pages = {89:189:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772785},
ISSN = {18688969},
year = {2023},
volume = {261},
editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/18141},
URN = {urn:nbn:de:0030drops181416},
doi = {10.4230/LIPIcs.ICALP.2023.89},
annote = {Keywords: Coding theory, Listdecoding, Rankmetric codes}
}
Keywords: 

Coding theory, Listdecoding, Rankmetric codes 
Collection: 

50th International Colloquium on Automata, Languages, and Programming (ICALP 2023) 
Issue Date: 

2023 
Date of publication: 

05.07.2023 