  Decoding of Low-Density Parity Check (LDPC) codes can be viewed as a special
case of XOR-SAT problems, for which low-computational complexity bit-flipping
algorithms have been proposed in the literature. However, a performance gap
exists between the bit-flipping LDPC decoding algorithms and the benchmark LDPC
decoding algorithms, such as the Sum-Product Algorithm (SPA). In this paper, we
propose an XOR-SAT solver using log-sum-exponential functions and demonstrate
its advantages for LDPC decoding. This is then approximated using the Margin
Propagation formulation to attain a low-complexity LDPC decoder. The proposed
algorithm uses soft information to decide the bit-flips that maximize the
number of parity check constraints satisfied over an optimization function. The
proposed solver can achieve results that are within $0.1$dB of the Sum-Product
Algorithm for the same number of code iterations. It is also at least 10x
lesser than other Gradient-Descent Bit Flipping decoding algorithms, which are
also bit-flipping algorithms based on optimization functions. The approximation
using the Margin Propagation formulation does not require any multipliers,
resulting in significantly lower computational complexity than other
soft-decision Bit-Flipping LDPC decoders.
