Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR15-161 | 24th September 2015 14:06

A new class of rank-metric codes and their list decoding beyond the unique decoding radius


Authors: Chaoping Xing, chen yuan
Publication: 30th September 2015 16:43
Downloads: 1638


Compared with classical block codes, efficient list decoding of rank-metric codes seems more difficult. The evidences to support this view include: (i) so far people have not found polynomial time list decoding algorithms of rank-metric codes with decoding radius beyond $(1-R)/2$ (where $R$ is the rate of code) if ratio of the number of rows over the number of columns is constant, but not very small; (ii) the Johnson bound for rank-metric codes does not exist as opposed to classical codes; (iii) the Gabidulin codes can not be list decoded beyond half of minimum distance.
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 $\rho(\mC)$ is extremely small, i.e., $\Theta(\Ge^2)$ , where $\rho(\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 $\rho(\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 $\rho(\mC)$
and efficiently list decode these codes with decoding radius beyond $(1-R)/2$. Specifically speaking, let $r$ be a prime power and let $c$ be an integer between $1$ and $r-1$. Let ${\Ge}>0$ be a small real. Let $q=r^{\ell}$ with $\gcd(r-1,\ell n)=1$. Then there exists an explicit rank-metric code $\mC$ in $\MM_{n\times(r-1)n}(\F_q)$ with rate ${R}$ that is $({\tau}, O(\exp(1/{\Ge^2})))$-list decodable with ${\tau}=\frac c{c+1}\left(1-\frac{r-1}{r-c}\times {R}-{\Ge}\right)$. Furthermore, encoding and list-decoding algorithms are in polynomial time ${\rm poly}(n,\exp(1/{\Ge}))$. The list size can be reduced to $O(1/{\Ge})$ by randomizing the algorithm. Note that the ratio $\rho(\mC)$ for our code $\mC$ is $1/(r-1)$.
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.

ISSN 1433-8092 | Imprint