A proof of the Hadamard transform decoding of the belief propagation algorithm for LDPCC over GF(q)

The LDPCC (low-density parity-check codes) belief propagation decoding algorithm uses a bipartite graph and sends belief messages between the variable symbols and the checks in an iterative process. The message that a check sends to a variable symbol can be calculated using a Hadamard transform, as introduced by T.J. Richardson and R.L. Urbanke (see IEEE Trans. Inform. Theory, vol.IT-47, p.599-618, 2001). However, the explicit proof of the correctness of the FHT (fast Hadamard transform) implementation of the decoding algorithm has not, so far, been seen in the literature. We give a proof for the FHT implementation of the decoding algorithm for LDPC codes over GF(q).