Stack Exchange network consists of 183 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.
@AlexanderChervov Could you provide some details of how Hadamard transform decoding can be used for any linear block code over $\mathbb F_2$? I am not aware of this result.
Alexander Vardy showed in 1997 that computing the minimum distance of a binary linear code is a NP-hard problem, and Daniele Micciancio, Ilya Dumer and Madhu Sudan showed in 2003 that computing the minimum distance approximately (to within a constant factor) is also NP-hard. I would suspect, and will not at all be surprised if I am told that it already has been proven, that the same would apply to your problem, which is essentially that of computing the free distance of a convolutional code.
