Decoding Reed–Solomon Codes Beyond $(d-1)/2$ and Zeros of Multivariate Polynomials

Let $\bold e$ be an error vector of weight $t$ and let $\bold b$ be its syndrome. In this work we consider a symmetric polynomial $O(y_1,\dots, y_r,\bold b)$ from $F_q[y_1,\dots,y_r]$ of degree $t-r+1$, where $r=2t-d+2$, which has the following property: if $\Omega$ is the set of error locations with syndrome $\bold b$, then any $r$-element subset $\Omega'$ of the set $\Omega$ is a zero of $O(y_1,\dots, y_r,\bold b)$. The converse is also true, namely, the zeros of $O(y_1,\dots, y_r,\bold b)$ determine all the locations of errors of weight $t$ whose syndrome equals $\bold b$, i.e., decoding and finding zeros of $O(y_1,\dots, y_r,\bold b)$ that lie in a prescribed set are equivalent problems. Based on these properties, we suggest a decoding algorithm of Reed–Solomon codes for $t>(d-1)/2$. A large part of the paper is devoted to the study of a nontrivial class of symmetric polynomials in $r$ variables formed by the polynomials $O(y_1,\dots, y_r,\bold b)$.