On List-decodability of Random Rank Metric Codes

Original · EN

In the present paper, we consider list decoding for both random rank metric codes and random linear rank metric codes. Firstly, we show that, for arbitrary 0<R<1 and ε>0 (ε and R are independent), if 0<n/m≤ ε, then with high probability a random rank metric code in Fqᵐ× ⁿ of rate R can be list-decoded up to a fraction (1-R-ε) of rank errors with constant list size L satisfying L≤ O(1/ε). Moreover, if n/m≥Θᵣ(ε), any rank metric code in Fqᵐ× ⁿ with rate R and decoding radius ρ=1-R-ε can not be list decoded in poly(n) time. Secondly, we show that if n/m tends to a constant b≤ 1, then every Fq-linear rank metric code in Fqᵐ× ⁿ with rate R and list decoding radius ρ satisfies the Gilbert-Varsharmov bound, i.e., R≤ (1-ρ)(1-bρ). Furthermore, for arbitrary ε>0 and any 0<ρ<1, with high probability a random Fq-linear rank metric codes with rate R=(1-ρ)(1-bρ)-ε can be list decoded up to a fraction ρ of rank errors with constant list size L satisfying L≤ O((1/ε)).