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(n2) 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.