Complexity of Min-Sum Decoding

In general, there have been few results about the complexity and performance of min-sum decoding on an arbitrary Tanner graph. As was stated in Chapter 3, the min-sum algorithm runs in O(n²) time for cycle-free Tanner graphs, but we have shown that cycle-free Tanner graphs represent essentially trivial codes. The intuition in Section 3.5.3 suggests that for the Tanner graph of a given code there is a trade-off between cycle-complexity and the computational complexity of constraint checking. It would be interesting to study convergence and computational properties of the min-sum algorithm on Tanner graphs that have cycles. Of specific interest is the case when this trade-off is optimized.

Furthermore, given the localized structure of the min-sum algorithm, one could imagine that it would be easily parallelizable. In fact, the algorithm in its most general form breaks down problems into localized subproblems by means of variable marginalization. Thus it might be interesting to pursue such marginalization as a method of automatic parallelization.