Sparse representations for codes and the hardness of decoding LDPC codes

The maximum likelihood decoding problem is known to be NP-hard for binary linear codes, while belief propagation decoding is known to work well in practice for several LDPC codes. In this paper we give a polynomial time reduction from the maximum likelihood decoding (MLD) problem for binary linear codes to the weighted MLD problem for (3,3)- LDPC codes. The reduction proves the NP-hardness of weighted MLD for (3,3)-LDPC codes. It also provides a method which can be used to transform the decoding problem for dense codes to the decoding of sparse codes. The later problem is often more amenable to the use of belief propagation algorithm. For ease of presentation, we have organized the total reduction in several intermediate reductions, most of which are elementary and easy to follow.