Reed-Muller codes encode an $m$ -variate polynomial of degree $r$ by evaluating it on all points in $\{0,1\}^m$ . We denote this code by $RM(m,r)$ . The minimal distance of $RM(m,r)$ is $2^{m-r}$ and so it cannot correct more than half that number of errors in the worst case. For random errors one may hope for a better result. In this work we give an efficient algorithm (in the block length $n=2^m$ ) for decoding random errors in Reed-Muller codes far beyond the minimal distance. Specifically, for low rate codes (of degree $r=o(\sqrt{m})$ ) we can correct a random set of $(1/2-o(1))n$ errors with high probability. For high rate codes (of degree $m-r$ for $r=o(\sqrt{m/\log m})$ ), we can correct roughly $m^{r/2}$ errors. More generally, for any integer $r$ , our algorithm can correct any error pattern in $RM(m,m-(2r+2))$ for which the same erasure pattern can be corrected in $RM(m,m-(r+1))$ . The results above are obtained by applying recent results of Abbe, Shpilka and Wigderson (STOC, 2015), Kumar and Pfister (2015) and Kudekar et al. (2015) regarding the ability of Reed-Muller codes to correct random erasures. The algorithm is based on solving a carefully defined set of linear equations and thus it is significantly different than other algorithms for decoding Reed-Muller codes that are based on the recursive structure of the code. It can be seen as a more explicit proof of a result of Abbe et al. that shows a reduction from correcting erasures to correcting errors, and it also bares some similarities with the famous Berlekamp-Welch algorithm for decoding Reed-Solomon codes.Reed-Muller codes encode an $m$-variate polynomial of degree $r$ by evaluating it on all points in $\{0,1\}^m$. We denote this code by $RM(m,r)$. The minimal distance of $RM(m,r)$ is $2^{m-r}$ and so it cannot correct more than half that number of errors in the worst case. For random errors one may hope for a better result. In this work we give an efficient algorithm (in the block length $n=2^m$) for decoding random errors in Reed-Muller codes far beyond the minimal distance. Specifically, for low rate codes (of degree $r=o(\sqrt{m})$) we can correct a random set of $(1/2-o(1))n$ errors with high probability. For high rate codes (of degree $m-r$ for $r=o(\sqrt{m/\log m})$), we can correct roughly $m^{r/2}$ errors. More generally, for any integer $r$, our algorithm can correct any error pattern in $RM(m,m-(2r+2))$ for which the same erasure pattern can be corrected in $RM(m,m-(r+1))$. The results above are obtained by applying recent results of Abbe, Shpilka and Wigderson (STOC, 2015), Kumar and Pfister (2015) and Kudekar et al. (2015) regarding the ability of Reed-Muller codes to correct random erasures. The algorithm is based on solving a carefully defined set of linear equations and thus it is significantly different than other algorithms for decoding Reed-Muller codes that are based on the recursive structure of the code. It can be seen as a more explicit proof of a result of Abbe et al. that shows a reduction from correcting erasures to correcting errors, and it also bares some similarities with the famous Berlekamp-Welch algorithm for decoding Reed-Solomon codes.

arXiv:1503.09092Mar 31, 20152 citations

Hulls of Projective Reed–Muller Codes over the Projective Plane

Diego Ruano, Rodrigo San–José

Abstract. By solving a problem regarding polynomials in a quotient ring, we obtain the relative hull and the Hermitian hull of projective Reed–Muller codes over the projective plane. The dimension of the hull determines the minimum number of maximally entangled pairs required for the corresponding entanglement-assisted quantum error-correcting code. Hence, by computing the dimension of the hull we now have all the parameters of the symmetric and asymmetric entanglement-assisted quantum error-correcting codes constructed with projective Reed–Muller codes over the projective plane. As a byproduct, we also compute the dimension of the Hermitian hull for affine Reed–Muller codes in two variables.Abstract. By solving a problem regarding polynomials in a quotient ring, we obtain the relative hull and the Hermitian hull of projective Reed–Muller codes over the projective plane. The dimension of the hull determines the minimum number of maximally entangled pairs required for the corresponding entanglement-assisted quantum error-correcting code. Hence, by computing the dimension of the hull we now have all the parameters of the symmetric and asymmetric entanglement-assisted quantum error-correcting codes constructed with projective Reed–Muller codes over the projective plane. As a byproduct, we also compute the dimension of the Hermitian hull for affine Reed–Muller codes in two variables.

arXiv:2312.13921SIAM Journal on Applied Algebra and GeometryNov 18, 20246 citations

量子 Reed-Müller 碼

鄭閔鴻

In this thesis, we start from the theory of classical error-correcting codes. We also introduce classical Reed-Muller codes along with its properties. We discuss the encoding and decoding methods for classical Reed-Muller codes using the majority rule. Then we turn to the topic of quantum error-correcting codes.We talk about stabilizer codes and discuss how classical Reed-Muller codes can be transformed into quantum Reed-Muller codes using Steane's method. Finally, we give a construction of a quantum code with parameter [[8,3,3]], and discuss its encoding and decoding process.In this thesis, we start from the theory of classical error-correcting codes. We also introduce classical Reed-Muller codes along with its properties. We discuss the encoding and decoding methods for classical Reed-Muller codes using the majority rule. Then we turn to the topic of quantum error-correcting codes.We talk about stabilizer codes and discuss how classical Reed-Muller codes can be transformed into quantum Reed-Muller codes using Steane's method. Finally, we give a construction of a quantum code with parameter [[8,3,3]], and discuss its encoding and decoding process.

Jan 1, 20110 citations

Introduction to the theory of error-correcting codes

Ian F. Blake

Proceedings of the IEEEJul 1, 198430 citations

Reed-Muller codes encode an

m

-variate polynomial of degree

r

by evaluating it on all points in

\{0,1\}^m

. We denote this code by

RM(m,r)

. The minimal distance of

RM(m,r)

2^{m-r}

and so it cannot correct more than half that number of errors in the worst case. For random errors one may hope for a better result. In this work we give an efficient algorithm (in the block length

n=2^m

) for decoding random errors in Reed-Muller codes far beyond the minimal distance. Specifically, for low rate codes (of degree

r=o(\sqrt{m})

) we can correct a random set of

(1/2-o(1))n

errors with high probability. For high rate codes (of degree

m-r

for

r=o(\sqrt{m/\log m})

), we can correct roughly

m^{r/2}

errors. More generally, for any integer

r

, our algorithm can correct any error pattern in

RM(m,m-(2r+2))

for which the same erasure pattern can be corrected in

RM(m,m-(r+1))

. The results above are obtained by applying recent results of Abbe, Shpilka and Wigderson (STOC, 2015), Kumar and Pfister (2015) and Kudekar et al. (2015) regarding the ability of Reed-Muller codes to correct random erasures. The algorithm is based on solving a carefully defined set of linear equations and thus it is significantly different than other algorithms for decoding Reed-Muller codes that are based on the recursive structure of the code. It can be seen as a more explicit proof of a result of Abbe et al. that shows a reduction from correcting erasures to correcting errors, and it also bares some similarities with the famous Berlekamp-Welch algorithm for decoding Reed-Solomon codes.