The Sum-Product Algorithm on Small Graphs

The following sections are included:

• Introduction

• Experimental Results

• Analysis of the Sum-Product Algorithm

  • Bipartite Graphs

  • The Sum-Product Algorithm

  • Reduction of the SPA to a local sum algorithm when check nodes have degree 2

• Examples

  • A cycle of length 2m

  • 2 bits n checks

  • 4-Choose-2

  • 3-to-1 covers of the complete 2-bits-3-checks graph

  • Degradation of performance with the coarse termination criterion

• Concluding Remarks

• References