ECCC-Report TR21-139https://eccc.weizmann.ac.il/report/2021/139Comments and Revisions published for TR21-139en-usMon, 08 Nov 2021 21:54:01 +0200
Revision 1
| Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity |
Venkatesan Guruswami,
Jonathan Mosheiff
https://eccc.weizmann.ac.il/report/2021/139#revision1We prove the existence of Reed-Solomon codes of any desired rate $R \in (0,1)$ that are combinatorially list-decodable up to a radius approaching $1-R$, which is the information-theoretic limit. This is established by starting with the full-length $[q,k]_q$ Reed-Solomon code over a field $\mathbb{F}_q$ that is polynomially larger than the desired dimension $k$, and "puncturing" it by including $k/R$ randomly chosen codeword positions.
Our puncturing result is more general and applies to any code with large minimum distance: we show that a random rate $R$ puncturing of an $\mathbb{F}_q$-linear "mother" code whose relative distance is close enough to $1-1/q$ is list-decodable up to a radius approaching the $q$-ary list-decoding capacity bound $h_q^{-1}(1-R)$. In fact, for large $q$, or under a stronger assumption of low-bias of the mother-code, we prove that the threshold rate for list-decodability with a specific list-size (and more generally, any "local" property) of the random puncturing approaches that of fully random linear codes. Thus, all current (and future) list-decodability bounds shown for random linear codes extend automatically to random puncturings of any low-bias (or large alphabet) code. This can be viewed as a general derandomization result applicable to random linear codes.
To obtain our conclusion about Reed-Solomon codes, we establish some hashing properties of field trace maps that allow us to reduce the list-decodability of RS codes to its associated trace (dual-BCH) code, and then apply our puncturing theorem to the latter. Our approach implies, essentially for free, optimal rate list-recoverability of punctured RS codes as well. Mon, 08 Nov 2021 21:54:01 +0200https://eccc.weizmann.ac.il/report/2021/139#revision1
Paper TR21-139
| Punctured Large Distance Codes, and Many Reed-Solomon Codes, Achieve List-Decoding Capacity |
Venkatesan Guruswami,
Jonathan Mosheiff
https://eccc.weizmann.ac.il/report/2021/139We prove the existence of Reed-Solomon codes of any desired rate $R \in (0,1)$ that are combinatorially list-decodable up to a radius approaching $1-R$, which is the information-theoretic limit. This is established by starting with the full-length $[q,k]_q$ Reed-Solomon code over a field $\mathbb{F}_q$ that is polynomially larger than the desired dimension $k$, and "puncturing" it by including $k/R$ randomly chosen codeword positions.
Our puncturing result is more general and applies to any code with large minimum distance: we show that a random rate $R$ puncturing of an $\mathbb{F}_q$-linear "mother" code whose relative distance is close enough to $1-1/q$ is list-decodable up to a radius approaching the $q$-ary list-decoding capacity bound $h_q^{-1}(1-R)$. In fact, for large $q$, or under a stronger assumption of low-bias of the mother-code, we prove that the threshold rate for list-decodability with a specific list-size (and more generally, any "local" property) of the random puncturing approaches that of fully random linear codes. Thus, all current (and future) list-decodability bounds shown for random linear codes extend automatically to random puncturings of any low-bias (or large alphabet) code. This can be viewed as a general derandomization result applicable to random linear codes.
To obtain our conclusion about Reed-Solomon codes, we establish some hashing properties of field trace maps that allow us to reduce the list-decodability of RS codes to its associated trace (dual-BCH) code, and then apply our puncturing theorem to the latter. Our approach implies, essentially for free, optimal rate list-recoverability of punctured RS codes as well. Fri, 24 Sep 2021 05:44:57 +0300https://eccc.weizmann.ac.il/report/2021/139