A New Class of Rank-Metric Codes and Their List Decoding Beyond the Unique Decoding Radius

DOI10.1109/TIT.2017.2780848MaRDI QIDQ5375522zbMATH OpenOpenAlexFDO

Authors Chaoping Xing, Chen Yuan

Publication date 14 September 2018

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.07337

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Decoding (94B35)

Abstract: Compared with classical block codes, efficient list decoding of rank-metric codes seems more difficult. Although the list decodability of random rank-metric codes and limits to list decodability have been completely determined, little work on efficient list decoding rank-metric codes has been done. The only known efficient list decoding of rank-metric codes $mC$ gives decoding radius up to the Singleton bound $1-R-Ge$ with positive rate $R$ when $ho(mC)$ is extremely small, i.e., $Theta(G{e}^2)$ , where $ho(mC)$ denotes the ratio of the number of rows over the number of columns of $mC$ cite[STOC2013]{Guru2013}. It is commonly believed that list decoding of rank-metric codes $mC$ with not small constant ratio $ho(mC)$ is hard. The main purpose of the present paper is to explicitly construct a class of rank-metric codes $mC$ with not small constant ratio $ho(mC)$ and efficiently list decode these codes with decoding radius beyond $(1-R)/2$. Our key idea is to employ two-variable polynomials $f(x,y)$, where $f$ is linearized in variable $x$ and the variable $y$ is used to "fold" the code. In other words, rows are used to correct rank errors and columns are used to "fold" the code to enlarge decoding radius. Apart from the above algebraic technique, we have to prune down the list. The algebraic idea enables us to pin down the messages into a structured subspace of dimension linear in the number $n$ of columns. This "periodic" structure allows us to pre-encoding the messages to prune down the list. More precisely, we use subspace design introduced in cite[STOC2013]{Guru2013} to get a deterministic algorithm with a larger constant list size and employ hierarchical subspace-evasive sets introduced in cite[STOC2012]{Guru2012} to obtain a randomized algorithm with a smaller constant list size.

Recommendations

• On the List Decodability of Rank Metric Codes
• Bounds on List Decoding of Rank-Metric Codes
• On List-Decodability of Random Rank Metric Codes and Subspace Codes
• On the list decodability of self-orthogonal rank-metric codes
• On the list decodability of rank-metric codes containing Gabidulin codes
• Encoding and decoding of several optimal rank metric codes
• Rank-metric codes and their applications
• Explicit List-Decodable Rank-Metric and Subspace Codes via Subspace Designs
• New technique for decoding codes in the rank metric and its cryptography applications
• A new rank metric for convolutional codes

Cited in

(2)

• A unique ranking of multilevel sequences and its application to source coding (Corresp.)
• Rank-metric codes and their applications

This page was built for publication: A New Class of Rank-Metric Codes and Their List Decoding Beyond the Unique Decoding Radius

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5375522)