Finding minimum weight codeword of MDS RS code

Question

For a $[n,k,n-k+1]_q$ Reed Solomon code is there a polynomial time algorithm to find at least one minimum weight $(n-k+1)$ codeword? I searched in literature and I could not find one and hence I am suspecting there is a decision version of this problem which might be $\mathsf{NP}$-complete.

Answer 1

The solution holds for any MDS code. I'm assuming the code is given by its generator matrix $G$. In that case, simply convert $G$ into its reduced row echelon form $G'$. This will be a matrix of the form $G'=[I | A]$, where $I$ is the $k\times k$ identity matrix, and $A$ is $k\times (n-k)$. (Note here: since the code is MDS, every $k$ columns of $G$ are linearly independent, and there is no need to permute columns) It is now easy to see each and every row of $G'$ is a codeword of weight $d=n-k+1$. That is because each row is non-zero, has weight at most $n-k+1$, and is a codeword. The procedure described is certainly polynomial time.

Answer 2

In this paper some useful information is given, see the introduction and references. The problem of finding the weights is NP-complete but not known to be NP-hard. Without the generating matrix, the best known algorithms are exponential in complexity. If $G$ is known, I think it is still going to be exponential, but let me think a bit.

Edit The complete weight distribution is known for MDS codes. $A_i$ denotes number of codewords of weight $i$, $A_0=1,$ and $A_i=0,$ for $1\leq i \leq d-1.$ The other nonzero weights are $$ A_i= \binom{n}{i} \sum_{j=0}^{i-d} (-1)^{j}\binom{i}{j} \left( q^{i+1-d-j}-1\right), $$ for $d\leq i \leq n.$ Letting $i=d$ gives $A_d=\binom{n}{d}(q-1)$ minimum weight codewords out of $q^{n-d+1}$ total codewords.

Edit 2 Actually any $k=n-d+1$ positions in an MDS code is an information set, i.e. One can choose those positions freely. So choose say first $k-1$ positions to be zero, the next to be $1$ and use $G$ to determine the rest of the coordinates, which all have to be nonzero. This gives a polynomial time algorithm, polynomial in $n$.