Parallel vs. sequential belief propagation decoding of LDPC codes over GF(q) and Markov sources

A sequential updating scheme (SUS) for belief propagation (BP) decoding of LDPC codes over Galois fields, GF(q), and correlated Markov sources is proposed and compared with the standard parallel updating scheme (PUS). A thorough experimental study of various transmission settings indicates that the convergence rate, in iterations, of the BP algorithm for the SUS is about one half of that for the PUS, independent of the finite field size q. Moreover, this 12 factor appears regardless of the correlations of the source and the channel's noise model, while the error correction performance remains unchanged. These results may imply on the 'universality' of the one half convergence speed-up of SUS decoding. A comparison to the dynamics of physical spin systems is also addressed.