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 ( mC ) is extremely small, i.e., ( Ge 2 ) , where ( 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 ( 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 ( 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 0"> Ge 0 be a small real. Let q = r with gcd ( r ? 1 n ) = 1 . Then there exists an explicit rank-metric code mC in MM n ( r ? 1) n ( F q ) with rate R that is ( O ( exp (1 Ge 2 ))) -list decodable with = c c +1 1 ? r ? 1 r ? c R ? Ge . Furthermore, encoding and list-decoding algorithms are in polynomial time pol y ( n exp (1 Ge )) . The list size can be reduced to O (1 Ge ) by randomizing the algorithm. Note that the ratio ( 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.
展开▼
