CS Paper Radar

When to Stop? Dynamic Early Termination of Sequential Ensembles

Paul Bezner, Felix Krieg, Stephan ten Brink

cs.IT eess.SP ·submitted 2026-08-11 08:53 UTC · v1

Abstract

Ordered-statistics decoding (OSD) post-processing substantially improves the performance of belief propagation (BP) ensembles, but it also removes their natural syndrome-based stopping criterion. The high computational complexity of ensemble decoding and OSD can be reduced by sequential activation of ensemble members paired with an early termination. Instead of a syndrome-based termination we therefore apply dynamic ensemble termination (DET) to sequential ensembles: members are evaluated one at a time and decoding stops when the estimated risk that an unseen member would correct the current decision falls below an offline-fitted threshold. With hardware-oriented design in mind, we instantiate the framework with layered normalized min-sum component decoders, a row-boosted ensemble, conditional low-order OSD on the dual code, and a conventional low-cost decoder gate. A decision tree estimates the residual risk from statistics of the current candidate list. Member-dependent thresholds then target a prescribed frame error rate (FER) loss. We validate this framework on mutliple IEEE 802.11 low-density parity-check (LDPC) codes with blocklengths \(648,1296\), and \(1944\) at rates \(1/2\) and \(5/6\). At each code's design point, where the full \(64\)-member list reaches an FER of \(10^{-3}\), the DET decoder processes \(1.04\) to \(1.15\) members on average. On the \((648,540)\) code, it reduces BP work by \(39\times\) and OSD activations by \(18\times\) against the full list while retaining an signal-to-noise ratio (SNR) gain of about \(0.4\,\mathrm{dB}\).

Comment
6 pages, 6 figures, submitted to an IEEE conference for possible publication

Closest papers

Nearest neighbours by meaning across the whole index.

Joint End-to-End Training of Weighted BP Decoder Ensembles

cs.IT cs.LGeess.SP ·2026-10-24 ·Felix Krieg, Paul Bezner, Stephan ten Brink
similarity 0.67
Abstract · 6 pages, 7 figures, submitted to an IEEE conference for possible publication

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.

0.26

SECS: A Soft Ensemble-Combining Stage for Low-Latency Decoding

cs.IT eess.SP ·2026-08-10 ·Felix Krieg, Paul Bezner, Stephan ten Brink
similarity 0.64
Abstract · 6 pages, 8 figures, submitted to an IEEE conference for possible publication

Ensemble decoding is a promising technique for ultra-reliable low-latency communication, as it trades hardware parallelism for decoding latency by running M diverse belief propagation (BP) decoders in parallel. Conventional ensembles select their output from the candidates. Hence, decoding fails whenever no member finds the correct codeword. In this work, we show that shallow, diverse BP members are poor correctors, but excellent sorters. Based on this observation, we propose a soft ensemble-combining stage (SECS) that combines extrinsic messages after only a few iterations, yielding a reliability ordering whose most reliable positions are nearly error-free. A subsequent re-encoding stage (like ordered-statistics decoding (OSD)) converts this ordering into a near-maximum likelihood (ML) candidate codeword, at a fraction of the BP latency of a fully converged ensemble. We demonstrate the proposed scheme on three short codes: a (63,30) Bose-Ray-Chaudhuri-Hocquenghem code, an overcomplete PG(2,8) code, and a search-designed (105,53) cyclic code. In all cases, the SECS with OSD post-processing closes most of the gap to ML decoding, while significantly reducing the number of required BP iterations.

0.09

Early Selection of Polar Ensemble Decoding with Successive Cancellation Style Component Decoder

cs.IT ·2026-10-25 ·Pin-Jing Li, Yu-Chih Huang
similarity 0.63
Abstract

Parallel ensembles of successive cancellation (SC)-style decoders improve error-rate performance by decoding multiple representations of the received vector. Conventional ensembles, however, keep every member active until completion. To reduce computational cost while retaining the diversity gain of ensemble decoding, we propose early ensemble selection (EES), which ranks members using intermediate decoding states and retains a prescribed numbers of members at each predefined selection stage. Within the EES framework, we propose two selection rules, namely path-metric-based selection (PM-EES) and neural-network-based selection (NN-EES). We analytically characterize the computational cost of EES through stage-dependent decoder log-likelihood ratio (LLR) update counts and provide an information-theoretically motivated criterion for choosing selection stages. Simulations on the \((128,64)\) extended BCH code and the \(\operatorname{RM}(4,8)\) code show that suitable selection schedules approach full-ensemble error-rate performance with fewer decoder LLR updates.

0.31

Row-Boosted Ensemble Belief Propagation for Short LDPC Codes

cs.IT eess.SP ·2026-08-10 ·Paul Bezner, Felix Krieg, Stephan ten Brink
similarity 0.62
Abstract · 6 pages, 9 figures, submitted to an IEEE conference for possible publication

Belief-propagation (BP) decoding of short and moderate-length low-density parity-check (LDPC) codes is limited by finite-length graph effects: a single decoder trajectory can become trapped or oscillatory even when an alternative trajectory would decode the received word. Existing ensemble-BP decoders create the required diversity through multiple parity-check matrices, automorphisms, modified schedules, subcodes, or altered update rules. We introduce row-boosted ensemble (RBE) decoding as a minimal decoder-side diversity mechanism: all ensemble members share the same parity-check matrix and the same BP kernel, and differ only in a small set of parity-check rows whose outgoing messages are boosted. On the 5G~NR BG1 \((144,96)\) code, RBE with \(32\) members lowers the frame-error rate of BP with \(20\) iterations (BP-20) from \(1.6\times10^{-2}\) to \(1.6\times10^{-3}\) at \(E_\mathrm{b}/N_0=4.0\,\mathrm{dB}\), outperforming saturated-min-sum and affine subcode ensembles of equal size. Increasing the ensemble size yields additional gains, indicating that RBE provides a scalable performance-complexity tradeoff. The gains transfer across 5G~NR block lengths and rates, to non-5G short LDPC codes, and across flooding and layered schedules.

0.43

Entropy-Based and Quadratic Conditional Innovation Metrics for Informed Dynamic Scheduling of Belief-Propagation Decoding for LDPC Codes

cs.IT ·2026-11-14 ·Tofar Chih-Yuan Chang, Chia-En Liu, Ying-Ren Jian, Di-Chun Liang
published similarity 0.57
Abstract · 25 pages, 18 figures, 3 tables

We propose two enhanced conditional innovation (CI) metrics for informed dynamic scheduling (IDS) in belief-propagation (BP) decoding of LDPC codes. The CI-based residual BP (CIRBP) algorithm uses the CI metric to guide the selection of the variable node (VN) to be updated and has been shown to outperform several existing IDS-based BP decoders, especially at the early decoding stage. However, the original CI metric uses only the absolute difference between the current and precomputed posterior probabilities and does not separately account for the reliability associated with each probability. By reformulating the CI metric relative to the decision boundary, we separate each posterior probability into its decision side and a linear-distance term reflecting reliability. Replacing the latter with the binary entropy complement yields the proposed entropy-based CI (E-CI) metric. Moreover, the proposed quadratic CI (Q-CI) metric is derived from the leading quadratic term in the local expansion of the entropy complement, avoiding the logarithmic operations required for direct E-CI evaluation. We apply both proposed metrics to the CIRBP decoder and its node-wise variant. Numerical results show that the proposed metrics generally provide lower frame error rates than the original CI metric, with their relative advantages depending on the code and decoding procedure.

0.37

Certified Adaptive List Decoding for Error-Correcting Codes

cs.IT cs.LG ·2026-10-20 ·Jaeho Hwang, Byung-Sun Won, Uiwon Hwang
similarity 0.56
Abstract

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.

0.31

On the Multi-Weight Shift-Sum Iterative Decoding of Short BCH Codes

cs.IT eess.SP ·2026-10-12 ·Yinglei Yang, Di Zhang, Aimin Li, Yifei Shen, Alexey Frolov +1 more
publishedtheoryhot direction similarity 0.55
Abstract

This paper investigates a shift-sum decoding algorithm that employs dual codewords. Existing dual codeword shift-sum decoding schemes mainly rely on minimum-weight dual codewords. However, the number of such codewords is often limited, which restricts the amount of reliability information available to the decoder. To address this issue, we extend the component counting mechanism from minimum-weight dual codewords to dual codewords whose Hamming weights lie within a prescribed upper bound. We further introduce a normalized component counting rule to suppress the overcounting bias caused by the much larger populations of higher-weight classes. Based on this framework, we develop a hard-decision iterative error reduction decoder and a soft information-aided iterative error reduction decoder. Numerical results show that the proposed method consistently outperforms existing minimum-weight shift-sum baselines especially for short codes where additional dual codeword information is particularly valuable.

0.51

Limits of Weight-Bounded Redundant Checks for Peeling Decoding of Random Regular LDPC Codes

cs.IT ·2026-10-04 ·Jianshen Zhu
similarity 0.55
Abstract

We study peeling decoding on the binary erasure channel when redundant parity checks may be added without restriction in number, but each check is subject to a row-weight constraint. For random simple binary regular low-density parity-check (LDPC) codes, we consider the parity-check matrix formed by all nonzero dual codewords up to a prescribed weight. We show that, throughout an explicit logarithmic row-weight range, this complete family of redundant checks has the same asymptotic normalized-residual threshold as peeling with the original LDPC matrix. In the same range, with probability tending to one over the random code, it still has a linear-size stopping set that is uniquely decodable. Consequently, every parity-check representation whose peeling decoder succeeds on every uniquely decodable erasure pattern must contain checks above this logarithmic scale, and the supports of those heavier checks must collectively contain a linear number of coordinates. Thus row weight remains an asymptotic limitation even when the number and selection of redundant checks are unrestricted.

0.11