PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Pin-Jing Li, Yu-Chih Huang

arXiv:2610.34142v1cs.ITmath.IT

TL;DR

Conventional parallel ensembles keep every member active until completion, despite intermediate decoding states that can guide which members continue. EES ranks members at predefined stages and retains a prescribed number; simulations show suitable schedules approach full-ensemble error-rate performance with fewer LLR updates.

  • Problem

    Conventional parallel ensembles keep every member active until completion, while intermediate decoding states may help determine which members should continue.

    Source: §I · p. 1

  • Method

    EES ranks parallel SC-style decoder members using intermediate states and retains a prescribed number at predefined stages, with path-metric-based and learned policies.

    Source: §I · p. 1

  • Results

    Across eBCH PED and RM AED, suitable schedules approach full-ensemble error-rate performance with fewer LLR updates; at (t, M_t) = (113, 24), PM-EES achieves essentially full-ensemble BLER with 88,152 updates, approximately 33% fewer.

    Source: §VI · p. 5, §V · p. 5

  • Takeaways & Limitations

    Prescribing selection stages and retained-member counts provides a performance–complexity tradeoff for ensemble decoding.

    Source: §V · p. 5

Abstract

from arXiv · show

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.

I. INTRODUCTION

Conventional parallel ensembles keep all members active until decoding ends, while prior online approaches either activate members sequentially or prune through architecture-specific convergence. EES instead prescribes how many partially decoded members continue at predefined stages, controlling decoder LLR updates.

I. INTRODUCTION

  • Conventional parallel ensembles improve error-rate performance while retaining the latency advantage of small-list component decoders, but run multiple members to completion.The introduction identifies this continuing computation as the motivation for online selection.Source: §I · p. 1
  • Offline methods avoid redundancy among SC-equivalent members, or select complementary members using simulated decoding failures, producing fixed ensembles; reduced-delay AED allows early termination when partial outputs cover information bits.The fixed ensemble is independent of the received word; AED’s automorphism sets permit termination once partial outputs collectively cover the information bits.Source: §I · p. 1
  • Online alternatives include sequential AED, which uses completed attempts to decide whether to activate more members, and SCAL, which jointly prunes paths across automorphisms [11].For RM ensembles, QOPC and SEC trigger pruning through convergence and select one continuing member, with work depending on the received vector [12],.Source: §I · p. 1
  • EES ranks partially decoded members at predefined stages and retains a prescribed number, explicitly controlling decoder LLR updates while preserving independent component decoding.The framework supports path-metric-based and learned ranking policies.Source: §I · p. 1

A. Polar Codes and Parallel Ensemble Decoding

The section introduces polar-code encoding and sequential SC/SCL decoding, then describes parallel ensembles that decode permuted received vectors independently. Each SCL component extends surviving paths and retains candidates with the smallest path metrics.

A. Polar Codes and Parallel Ensemble Decoding

  • A length-N=2^m polar code or subcode encodes x=uG_m, with B_m identified as the bit-reversal permutation matrix.The remaining input positions are information bits or frozen bits constrained to zero or to linear combinations of preceding information bits.Source: A. Polar Codes and Parallel Ensemble… · p. 1
  • Parallel AED, and PED [2] run M independent list-L SCL decoders on differently permuted received LLR vectors, then select the most likely output.Their latency is approximately that of one list-L decoder, while complexity scales as MLN log2 N; suitable M and L tradeoffs can match or improve on a single list-ML decoder, [2].Source: A. Polar Codes and Parallel Ensemble… · pp. 1–2
  • At each stage, an SCL member extends surviving paths by admissible bits and retains up to L candidates with the smallest path metrics.The number retained for member i at stage t is denoted L_i,t.Source: A. Polar Codes and Parallel Ensemble… · p. 2

B. Ensemble Constructions

The section distinguishes ensemble constructions for RM and polar codes, then describes PED's use of coordinate permutations and code automorphisms. The proposed EES framework selects whole members during decoding.

B. Ensemble Constructions

  • RM-code AED uses general affine permutations so members share a frozen set while decoding differently permuted received vectors [1].Source: B. Ensemble Constructions · p. 2
  • For polar codes, upper triangular linear and block lower triangular affine structures can provide SC-compatible automorphisms for AED,,.The RM–polar connection also supports SC-style component decoders for RM-AED.Source: B. Ensemble Constructions · p. 2
  • PED uses coordinate permutations for equivalent polar-subcode representations, with automorphisms generating members that share dynamic frozen constraints [2], –.EES applies to these ensembles by selecting whole members during decoding.Source: B. Ensemble Constructions · p. 2

III. EARLY ENSEMBLE SELECTION FOR PARALLEL ENSEMBLE DECODING

EES uses intermediate path-metric information to select which parallel ensemble members continue, retaining a prescribed number at predefined stages. The motivating observation is that current best path metrics can help identify members that attain the full ensemble's minimum final metric.

III. EARLY ENSEMBLE SELECTION FOR PARALLEL ENSEMBLE DECODING

  • Retaining members with the smallest current best path metrics can preserve at least one member attaining the full ensemble's minimum final path metric; retention probability generally rises as decoding progresses.This suggests less promising members may be terminated early with only a small loss in error-rate performance.Source: §III · p. 2
  • EES selects after active members complete a bit at a predefined stage, using path-metric information to retain a prescribed number of members.The retained count is set before decoding and cannot exceed the active-member count.Source: §III · p. 2
  • Figure 1 compares final-winner retention for smallest-current-metric selection (solid curves) against uniform random selection (dashed lines) across bit positions.The caption notes that random-selection baselines can exceed M_t/M when multiple members attain the minimum final metric.Source: Figure 1 · p. 2

A. Selection Based on Path Metrics (PM-EES)

PM-EES ranks active ensemble members by their current best path metrics and retains a prescribed number at each selection stage.

A. Selection Based on Path Metrics (PM-EES)

B. Neural-Network-Based Selection (NN-EES)

NN-EES assigns members learned scores from recorded path-metric histories and member indices, then retains the highest-scoring members at predefined stages.

B. Neural-Network-Based Selection (NN-EES)

  • The NN-EES input combines each member’s recorded path-metric statistics with a one-hot encoding of its member index.The statistics include path count, best metric, gap between the two best metrics, mean metric, and the member index encoding.Source: B. Neural-Network-Based Selection… · p. 3
  • At each selection stage, a shared neural network scores active members, and the selector retains the M_t members with the largest scores.A separate network is trained for each stage.Source: B. Neural-Network-Based Selection… · p. 3
  • In the two-stage example, selection terminates discarded decoders, while survivors finish decoding, undo their permutations, and send candidates to the final combiner.The figure indicates omitted work with gray blocks and terminations with crosses.Source: Figure 2 · p. 3
  • Training labels come from decoding every training vector with the full ensemble, and multiple members may be labeled positive when their best final metrics tie for the minimum.Source: B. Neural-Network-Based Selection… · p. 3
  • The networks are trained by minimizing binary crossentropy between labels and sigmoid scores, summed across members and training vectors.Source: B. Neural-Network-Based Selection… · p. 3

A. Complexity Analysis

The complexity analysis counts scalar decoder LLR updates along the standard SC traversal and derives costs for full decoding, partial decoding, and staged selection.

A. Complexity Analysis

  • A full ensemble of M independent SCL decoders with list size L uses MLN log2 N LLR updates.The analysis counts scalar LLR updates along the standard SC traversal.Source: A. Complexity Analysis · p. 3
  • With multiple selection stages, members terminated at stage t_j have each decoded t_j bits, yielding a stage-dependent total update count.The retained members continue decoding, and the expression reduces to the single-stage cost when there is one stage.Source: A. Complexity Analysis · p. 4
  • For a length-N code, the cost C_N(b) of decoding the first b bits follows a two-branch recurrence split at h = N/2.For b ≤ h, the traversal enters the left child and decodes b bits there; for b > h, it completes the left subtree before entering the right child.Source: A. Complexity Analysis · p. 4
  • At b = N, the recurrence gives N log2 N updates, consistent with the full traversal cost.Source: A. Complexity Analysis · p. 4

B. Choice of Selection Stage t

Selection-stage placement is motivated by changes in decoding uncertainty: information bits add uncertainty, while frozen constraints can reduce uncertainty about earlier information bits.

B. Choice of Selection Stage t

  • An information bit adds its remaining uncertainty, whereas revealing a frozen constraint can reduce uncertainty about preceding information bits.Source: B. Choice of Selection Stage t · p. 4
  • The uncertainty identities motivate placing selection stages immediately after frozen constraints, subject to a heuristic criterion; optimal scheduling is left for future work.Source: B. Choice of Selection Stage t · p. 4
  • For PM-EES, positions that are information bits for all members leave the ranking unchanged because each surviving path has a zero-increment child.This explains the flat retention probability across shared information positions and motivates selecting after frozen positions, where rankings can change.Source: B. Choice of Selection Stage t · p. 4

V. SIMULATION RESULTS

Simulations evaluate EES for eBCH PED-SCL and RM AED-SC ensembles, comparing error-rate performance against decoder LLR-update cost. Results show benefits from choosing both selection stages and retained-member counts, with NN-EES especially helpful at earlier eBCH stages.

NN-EES scorer

  • The NN-EES scorer uses 689 parameters and 10,752 multiplications per 64-member ensemble at t = 16, about 4.7% of the 229,376 LLR updates required by the full ensemble.The scorer improves error-rate performance over PM-EES at early selection stages.Source: §V · p. 4

(128, 64) eBCH PED-SCL

  • At t = 96, both selectors approach full-ensemble error-rate performance with 186,368 LLR updates, approximately 19% fewer than the full ensemble; at t = 64, both beat the matched-cost baseline.At t = 16 and 32, NN-EES improves error-rate performance over PM-EES.Source: §V · p. 4, Figure 3 · p. 5

RM(4, 8) AED

  • PM-EES prescribes both the selection stage and retained-member count, giving a fixed LLR-update count, whereas QOPC's count depends on the received vector and mean varies with SNR.The evaluation uses AWGN with BPSK, (128, 64) eBCH PED-SCL with L = 4, and RM(4, 8) AED-SC; both full ensembles have 64 members.Source: §V · pp. 4–5
  • 88,152 LLR updates at (t, Mt) = (113, 24) give PM-EES essentially the full-ensemble BLER, about 33% fewer updates; at Mt = 6 and 8 it gains about 0.01 dB over QOPC.At (64, 16), PM-EES uses 60,416 updates, below the minimum under the configured QOPC verification schedule.Source: §V · p. 5

(128, 64) eBCH PED-SCL

  • At t = 29, NN-EES beats the smaller-ensemble baseline at a lower LLR-update budget than PM-EES; at t = 48 and 64, both selectors similarly beat the baseline at higher budgets.Figure 4 fixes each EES curve's selection stage and varies the retained-member count.Source: Figure 4 · p. 5

VI. CONCLUSIONS

The conclusion presents EES as a way to retain prescribed numbers of SC-style decoder members using partial path metrics at predefined stages. Simulations find that suitable schedules approach full-ensemble error-rate performance with fewer LLR updates, while several extensions remain future work.

VI. CONCLUSIONS

  • Suitable EES schedules on eBCH PED and RM AED approach full-ensemble error-rate performance with fewer decoder LLR updates.NN-EES improves over PM-EES at earlier stages, while their performance is similar at later stages.Source: §VI · p. 5
  • Joint optimization of selection stages and retained counts, adaptive selection, joint path pruning, and further information-theoretic analysis are left for future work.The listed future work includes joint path pruning across ensemble members.Source: §VI · pp. 5–6
  • For RM(4, 8) AED, Fig. 5 compares PM-EES with QOPC and groups settings with similar complexity; NN-EES is omitted because its performance is nearly identical to PM-EES at these stages.QOPC update counts depend on the received vector and are reported as ranges of mean counts over the simulated SNR range.Source: Figure 5 · p. 6
  • The multistage eBCH schedules closely track single-stage EES at (64, 8), using 121,344 and 109,568 updates—about 6% and 15% fewer than 129,024.The two schedules use PM-EES at both stages, or NN-EES followed by PM-EES.Source: Figure 6 · p. 6

Related papers

Loading 2610.34142v1…