Understanding the limits of list-decoding and list-recovery of Reed-Solomon (RS) codes is of prime interest in coding theory and has attracted a lot of attention in recent decades. However, the best possible parameters for these problems are still unknown, and in this paper, we take a step in this direction. We show the existence of RS codes that are list-decodable or list-recoverable beyond the Johnson radius for \emph{any} rate, with a polynomial field size in the block length. In particular, we show that for any $\epsilon\in (0,1)$ there exist RS codes that are list-decodable from radius $1-\epsilon$ and rate less than $\frac{\epsilon}{2-\epsilon}$, with constant list size. We deduce our results by extending and strengthening a recent result of Ferber, Kwan, and Sauermann on puncturing codes with large minimum distance and by utilizing the underlying code's linearity.
翻译：理解Reed- Solomon(RS) 编码列表解码和回收列表的限值, 主要是对编码理论的兴趣, 近几十年来引起了很多注意。 然而, 这些问题的最佳可能参数仍然未知, 而在本文中, 我们朝这个方向迈出了一步。 我们显示了在 \ emph{ anny) 率 的 Johnson 半径以外, 存在列表可辨别或列表可回收的RS 代码, 其范围在块长内是多球场大小 。 特别是, 我们显示, 对于任何 $\ epsilon\ in ( 0, 1) 的编码, 有 RS 代码, 从 半径 $- epslon$ 和 低于 $\\ frac lipsilon% 2\ epslon} 的 和 美元, 以恒定的大小为 。 我们通过扩大和加强 Ferber、 Kwan 和 Sauermann 的近期结果, 和 sauermann 以最短的距离和 线性来推断我们的结果 。
相关内容
微信扫码咨询专知VIP会员