minsum

Minsum, commonly written min-sum or min-sum algorithm, is an iterative message-passing decoding algorithm used for low-density parity-check (LDPC) codes. It provides a computationally efficient approximation to the sum-product algorithm, which is based on exact belief propagation on a Tanner graph. By simplifying the arithmetic that underpins the full belief propagation, the min-sum algorithm reduces hardware complexity and memory usage, making it attractive for practical decoders.

In operation, the algorithm passes messages between variable nodes and check nodes on a bipartite graph representing the LDPC code. At check nodes, the update uses a minimum-magnitude rule: the outgoing message magnitude is the minimum of the absolute values of the incoming messages from all other adjacent variable nodes, and the sign is determined by the product of the incoming message signs. At variable nodes, the update sums the incoming messages (excluding the target) and adds the channel log-likelihood ratio to form updated beliefs. After several iterations, a hard decision is made based on the sign of the total log-likelihood ratio.

Variants of the min-sum approach exist to improve accuracy. Normalized min-sum scales the magnitudes by a factor to compensate for systematic bias, while offset min-sum subtracts a fixed offset from magnitudes before applying the minimum operation. Both aim to close the gap to the sum-product performance while preserving low complexity.

The min-sum algorithm is widely used in practical LDPC decoders across communications and storage systems where decoding efficiency is critical. Its main advantages are reduced computational load and simpler hardware implementation, balanced against a modest potential loss in decoding performance compared with the optimal sum-product algorithm.