


























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<\frac{n}{m}\leq ε$, then with high probability a random rank metric code in $F_{q}^{m\times n}$ of rate $R$ can be list-decoded up to a fraction $(1-R-ε)$ of rank errors with constant list size $L$ satisfying $L\leq O(1/ε)$. Moreover, if $\frac{n}{m}\geqΘ_R(ε)$, any rank metric code in $F_{q}^{m\times n}$ with rate $R$ and decoding radius $ρ=1-R-ε$ can not be list decoded in ${\rm poly}(n)$ time. Secondly, we show that if $\frac{n}{m}$ tends to a constant $b\leq 1$, then every $F_q$-linear rank metric code in $F_{q}^{m\times n}$ with rate $R$ and list decoding radius $ρ$ satisfies the Gilbert-Varsharmov bound, i.e., $R\leq (1-ρ)(1-bρ)$. Furthermore, for arbitrary $ε>0$ and any $0<ρ<1$, with high probability a random $F_q$-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\leq O(\exp(1/ε))$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。