1
$\begingroup$

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.

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

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.