WingNews logo WingNews
top | item 45290871

(no title)

rigtorp | 5 months ago

How is belief propagation used for decoding LDPC codes related to FFT?

discuss

order

srean|5 months ago

At the core both derive their optimization from the distributive property. If the expression graph has symmetry, you get more optimization out of it.

https://www.cs.ubc.ca/~murphyk/Teaching/Papers/GDL.pdf

Check out the first paragraph

    THE humble distributive
    law, in its simplest form
    states that...this leads
    to a large family of fast
    algorithms, including 
    Viterbi’s algorithm and 
    the fast Fourier
    transform (FFT).
Two extremely influential papers appeared back to back in transactions information theory. This is one of them.

The other is

https://vision.unipv.it/IA2/Factor graphs and the sum-product algorithm.pdf

Both are absolute gems of papers. The editor made sure that both appear in the same volume.

rigtorp|5 months ago

Interesting, of course many computations can be expressed as a graph. In the case of the bipartite graph we perform belief propagation on to decode LDPC where is the optimization from the distributive property? The parity matrix would typically be constructed so that there's few subexpression to factor out, to maximize the error correcting properties.

I agree both FFT and belief propagation can be expressed as message passing algorithms.