Learning to Decode Linear Codes with Generalized Belief Propagation Network

Forward error correction is essential for reliable communication over noisy channels. Attention-based model-free neural decoders have shown strong performance for short codes, but their scalability to longer codes is limited by the quadratic memory and computational cost of attention. In this paper, we introduce the Mamba message-passing decoder (MMPD), an attention-free syndrome-based neural decoder for binary linear codes. MMPD retains the Tanner-graph structure of a message-passing decoder by performing local pairwise aggregation along variable-check edges. To enable efficient long-range information propagation, these local updates are combined with bidirectional Mamba state-space blocks. By avoiding dense attention matrices, MMPD scales more favorably for long codes in both memory and computation. Experiments on the (1056, 880) LDPC code show that MMPD achieves a 0.45 dB gain over the state-of-the-art CrossMPT decoder at a specified target bit error rate, while reducing memory consumption by a factor of 1.5. This reduction factor increases substantially for longer codes, demonstrating the applicability of MMPD to scalable neural decoding of practical long codes.

Maximum-likelihood (ML) decoding of linear block codes is NP-hard, so neural decoders are evaluated by how closely they approach it. We observe that proving a candidate optimal can be far easier than finding it, and build a decoder that does both. We cast decoding as a search over an absorbing-state discrete diffusion model, whose sequential commitment of coordinates turns generation into a tree, and run a probability beam search over it. A dual bound from a linear-programming relaxation and a distance-based test, both derived from the code, then certify per frame that the current candidate is the global ML solution; because both are theorems, certified frames incur no accuracy-computation trade-off. Across $15$ codes and five operating points we certify up to $99.9\%$ of frames, the two tests dividing the space as their derivations predict, one strong for sparse parity-check matrices and the other for codes with a large minimum distance. Certification also behaves as a per-frame reliability signal, with $96.7$-$100\%$ of all frame errors falling on uncertified frames. Against an exact ML reference at $5$ dB the decoder is within one standard deviation on three of the four codes where the reference is uncensored, and against four neural baselines it attains the best bit-error rate in $71$ of $75$ cells.

Ensemble decoding improves decoding reliability by combining component decoders with complementary failure events. Existing approaches typically obtain this diversity from code-specific structure, such as code automorphisms, multiple parity-check representations, or targeted modifications of the message-passing graph. In this work, we instead learn the diversity of an ensemble of weighted belief propagation decoders by jointly optimizing trainable Tanner-graph edge weights. A central design question is how the training objective should distribute gradient among the ensemble members to promote complementary decoding behavior. To this end, we compare four ensemble objectives under direct gradient-based optimization and identify best-member training as the most effective approach. For a (64,32) progressive edge-growth (PEG) low-density parity-check (LDPC) code, the resulting ensemble outperforms the considered trained and untrained belief-propagation-based ensemble baselines. With 10 members, it provides a gain of approximately 0.66 dB over a single belief propagation decoder at a target frame error rate (FER) of $10^{-4}$. Similar behavior is observed for a (128,64) CCSDS LDPC code, indicating that the learned complementarity is not specific to PEG. Although the ensemble performance improves substantially, all trained members show a higher standalone FER. The gain therefore results from learned specialization and complementary failure events rather than uniformly improved component decoders.