I am studying the NP-Problem of the codes Syndrome Decoding. The formulation is show below.

Input: a binary matrix $H$ of dimension $r \times n$ and a bit string $S$ of length $r$.

Property: there exists a set of $w'$ columns of $H$ adding to $S$ (with $0 < w' \leq w$).

I understand that this problem is hard if the code is unknown. But if the code was know (i.e. we know its construction), for example a Goppa code where we know the support of the code and the polynomial that generates that code. Is there some class of codes where it is easy to generate several words, of certain class of codes, with the same weight and the same syndrome and the problem above is still hard?

  • $\begingroup$ I'm not sure what you're asking. What do you mean by "the code is known/unknown"? It's part of the input, so it's certainly known to the algorithm. Do you mean, for a specific class of codes, is this problem still NP-hard? Please edit the question to clarify. If so, it'll depend on the class of codes. What class of codes did you have in mind? And what research have you done? Have you done a literature search? $\endgroup$ – D.W. Jul 28 '15 at 0:15
  • $\begingroup$ @D.W. I have edited my question. $\endgroup$ – juaninf Jul 28 '15 at 11:40
  • $\begingroup$ That doesn't help. What do you mean by "we know its construction"? We know the binary matrix $H$; that is a construction of the code. I think my earlier question stands. If you're asking "Does there exist a class of codes for which the problem is easy" then the answer is a trivial but uninteresting yes, and that's probably not what you really intended to ask. If the question is "Please describe all classes of codes for which the problem is easy", then it's too broad for this site. In any case, you need to be more explicit about what the question is. $\endgroup$ – D.W. Jul 28 '15 at 16:33
  • $\begingroup$ I only know Hamming Codes and Goppa Codes. In the case of the Goppa Codes when I say that its construction is know, is because in the Syndrome Decoding problem if we know the Goppa polynomial and the support of the code then the problem Syndrome decoding is not problem, is too easy to solve. I need to know a class of Codes where it is easy to generate a several words with the same syndrome and same weight and the Syndrome Decoding Problem is still hard. $\endgroup$ – juaninf Jul 28 '15 at 19:34
  • $\begingroup$ OK, that's a fine question -- but it's not what your question currently says. So, edit your question to say that. List the requirements you want the code to have, and ask whether such a code exists. $\endgroup$ – D.W. Jul 28 '15 at 20:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.