2
$\begingroup$

Which families of the error correcting codes have an efficient decoding algorithm? I know that decoding a general linear code is NP hard (the general decoding problem). I also know that Goppa codes and alternate codes have such algorithms due to Patterson. Hamming codes also belong to this category. If someone can provide a link or some source of list of such families that would be really helpful.

$\endgroup$

migrated from crypto.stackexchange.com Jul 22 '17 at 19:24

This question came from our site for software developers, mathematicians and others interested in cryptography.

  • $\begingroup$ This may be interesting. What do you mean by "efficient"? Do you have any requirements besides "efficient decoding"? $\endgroup$ – Evil Jul 22 '17 at 21:37
  • $\begingroup$ @Evil here is my understanding of the picture of coding theory. I believe you can get sense of what I mean by 'efficient.' The problem of decoding a random linear code is NP hard. So in the process of encoding one cannot use any code as it needs to be​ decoded later. So I was trying to ask which codes can we use. More specifically and importantly​ what are possible choices for the (structure of ) generator matrix. of now there are no other requirements but if thec code is binary it would be better. $\endgroup$ – Root Jul 23 '17 at 6:39
  • $\begingroup$ I understand that there are hundreds of such codes and possibly huge set of various decoding algorithms. So it's hard to get a complete list of that. So let me phrase this informally and less precisely. What are the top frequent choices of families of error correcting (binary) codes and why? What advantages do they offer over other codes? 5-6 examples would suffice. $\endgroup$ – Root Jul 23 '17 at 7:08
  • 1
    $\begingroup$ @D.W. sure. I am looking for an answer to which codes can replace goppa codes in McEliece cryptosystem. $\endgroup$ – Root Jul 23 '17 at 16:54
  • 1
    $\begingroup$ I would suggest edit to include your comment. It narrows down the topic, gives insight and honestly, I thought that link I gave was along lines of your needs. It looked like general reference request, now after your comment it has better defined purpose. $\endgroup$ – Evil Jul 23 '17 at 17:02

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.