# Finding minimum weight codeword of MDS RS code

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.

• Presumably you don't know the generating matrix, but just the parameters. Jul 15, 2016 at 8:30
• @kodlu even if you know $G$ it is not clear whether it would be able to find minimum weight codeword in polytime right? Jul 15, 2016 at 8:32

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.

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$.

• for MDS code min weight is known. Jul 15, 2016 at 8:50
• yes but a specific min weight codeword need not be that easy to find. Jul 15, 2016 at 9:21
• sure is that np complete is the problem. Jul 15, 2016 at 9:22
• also a decision problem is NP-complete when it is both in NP and NP-hard. Jul 15, 2016 at 10:20
• hmm so how does this give a poly time alg for finding a min weight codeword? Jul 15, 2016 at 10:43