Bit-optimal decoding of codes whose Tanner graphs are trees Original Research Article

We introduce a group algebra formulation for bit-optimal decoding of binary block codes. We use this new framework to give a simple algebraic proof that Pearlʹs and Gallagerʹs belief propagation decoding algorithms are bit-optimal when the Tanner graph of the code is a tree. We believe that these derivations of known results give new insights into the issues of decoding on graphs from the algebraic coding theoristʹs point of view.