Polar codes, the error-correcting codes used for 5G control channels, are usually decoded by successive cancellation (SC). SC walks a binary tree and decides one bit at a time, each decision depending on all earlier ones. That serial chain makes decoding slow, and the slowness is unpredictable: in medium-quality channels a few hard frames take far longer than typical ones. Two existing ideas each fix part of this. One prunes the tree: whole subtrees whose structure is trivial are decoded in a single step. The other checks a syndrome, meaning it tests whether a cheap hard guess already satisfies the code's parity constraints, and stops early if it does. Today the syndrome check is applied only to the whole codeword. It therefore helps almost only at high signal-to-noise ratio (SNR), where the entire frame is clean.
This note proposes moving the check inside the tree. At every internal node, the decoder takes the sign of its incoming soft values, maps that hard vector through the node's small polar transform, and tests whether the node's frozen positions come out zero. Frozen positions are the bit slots fixed to known values that carry the redundancy. If the test passes, the node is accepted in one step and its subtree is never visited. If it fails, the decoder descends as usual. The key point is that a frame which is globally dirty is usually locally clean almost everywhere. Errors cluster in a few weak subtrees, so a node-level gate should collapse most of the tree even at the medium SNRs where whole-block checks fail and latency spikes actually happen. A small learned scheduler decides where checks are worth their cost, because a check that is certain to fail is pure overhead.
Core Claim
For binary-input channels, the sign vector of a node's soft inputs maximizes correlation with those inputs over all binary vectors. If that sign vector is a codeword of the node's subcode, it is therefore the maximum-likelihood decision for that subcode given the node's inputs. Accepting it is never a worse local decision than descending. The check costs a length-$2^m$ polar transform, which has XOR depth $m$, plus an OR over the frozen positions.
The gate generalizes the special nodes of fast pruned SC in their passing case. A Rate-1 node, which has no frozen bits, always passes. A single-parity-check node passes exactly when parity holds. The same test now applies to arbitrary mixed nodes, which plain pruning must still traverse bit by bit. We claim three things. Local gating should lower mean decoding steps beyond both pruned SC and whole-block syndrome checking at medium SNR. It should cut the 99.9th-percentile step count by a larger factor than the mean. And the frame error rate (FER) should stay within Monte Carlo noise of SC. We cannot guarantee equal FER in theory, because the decision at a node changes what downstream nodes receive, so FER is measured rather than assumed.
Research Program
The work builds on three lines of prior research, each playing a different role.
Pruning supplies the baseline structure. Sublinear Latency for Simplified Successive Cancellation Decoding of Polar Codes proves that pruning Rate-0 and Rate-1 subtrees reduces SC's $2N-1$ steps to $O(N^{1-1/\mu})$, where $N$ is block length and $\mu$ is the channel's scaling exponent. That pruning is fixed by the code design and ignores the received frame. Our gate prunes per frame on top of it.
Whole-block checking motivates the gap. Successive Syndrome-Check Decoding of Polar Codes checks the full-block syndrome of the hard decisions, exits at zero steps when it passes, and otherwise refines from the first violated frozen bit. The file notes that at low SNR it falls back to near-full traversal. Our gate attacks exactly the frames it cannot shortcut.
Segmented checks show that intermediate verification pays off. Generalized Segmented Bit-Flipping and the CRC-aided list sphere decoder both insert intermediate checks, but they pay for them with extra parity bits that lower the code rate. Our checks reuse frozen bits the code already has, so they cost no rate.
The real-time optimization literature contributes a constraint rather than a mechanism. Unfolded solvers such as UWMMSE buy deterministic runtime with a fixed depth. The file flags that this wastes computation on easy instances and clashes with the heavy-tailed effort of search problems documented in Sequential Decoding of Tree Codes. We take from that literature the evaluation stance of judging a decoder by its deadline-miss rate, not its mean.
The engineering program has three parts. First, we implement the gate inside SC and fast pruned SC, with a step-accounting model that charges each check its XOR depth. Second, we build the scheduler. Its inputs are node depth, node index, frozen pattern, and two cheap reliability statistics of the incoming soft values: the minimum magnitude and the count below a threshold. A tiny model or a logistic rule trained on these predicts whether the gate will pass. A check is attempted only if expected savings exceed its cost. Third, we extend the gate to SC list decoding (SCL), where accepting a node means extending each path by its hard decision with zero metric penalty. Whether alternative branches can be skipped there is an open question, and we will measure the FER loss when they are.
Baselines
The naive reference is plain SC, which takes $2N-1$ tree steps on every frame regardless of channel quality, along with SCL that has a single CRC at the end of the block. Every method runs on identical noise realizations.
The strongest model-based competitor on latency is fast pruned SC with Rate-0, Rate-1, repetition and single-parity-check nodes, following Mondelli et al.. The file reports only asymptotic scaling for it: $N^{0.72}$ on the erasure channel and $N^{0.76}$ on the binary symmetric channel. It reports no finite-length step counts, so we will measure them ourselves. Beating this baseline means fewer mean and 99.9th-percentile steps at equal FER, counted under the same step model with checks charged.
The strongest per-frame adaptive competitor is successive syndrome-check decoding (Hashemi et al.). The file contains no reported latency number for it: no reported result found on Lacuna for its step counts on P(128,64). We will reimplement it on P(128,64) and treat its curve as the bar. Our gate must beat it in the 1–3 dB range where its whole-block check fails, and must not lose at high SNR. The two methods can also be stacked, with the whole-block check first and local gates on failure. That stacked variant is the version we expect to deploy.
The strongest learned competitor is CRC-Aided Learned Ensembles of BP Polar Decoders. It reports roughly 0.25 dB FER gain at medium-to-high SNR for $N\in\{128,256,512\}$, while keeping average latency near a single belief-propagation pass. We compare on FER versus 99.9th-percentile latency, under matched trained parameter budgets, on the same codes.
Two ablations isolate the ingredients. One is "gate everywhere," which attempts a check at every internal node with no scheduler, and isolates the value of local verification itself. The other is a "threshold scheduler," which attempts a check only when the minimum soft-value magnitude exceeds a tuned constant, and isolates the value of the learned scheduler. Every tuned component gets the same validation-set search budget.
Why not just…?
Why not just use whole-block syndrome checking? It is the right tool at high SNR and we keep it. But a single wrong bit anywhere fails the block check. The file notes this method falls back to near-full traversal when hard decisions contain errors. Deadline misses come from those frames, so the stacked-versus-alone comparison at medium SNR settles whether local gates add anything.
Why not just add more special node types to fast pruned SC? Special nodes are chosen offline from the frozen pattern and must be decodable in closed form for every frame. The gate is a per-frame test that falls back safely, so it applies to every mixed node. The real threat is that special nodes already absorb most of the savings. If gating over fast pruned SC yields under about 10% step reduction at medium SNR on $N=1024$, we will report that and drop the claim.
Why not just learn a neural decoder, as in CRISP or learned BP? CRISP runs every frame through all of its recurrent steps and has no early exit, and the file limits it to short codes. The learned ensemble gates only once, at the outer level, and depends on belief propagation over polar graphs, which the file notes is suboptimal relative to list decoding. Our learning is confined to scheduling. It can only change cost, never which decision a passing gate accepts.
Why learn the scheduler at all? A fixed reliability threshold may well match it. The threshold-scheduler ablation is designed to show this. If the gap is within noise, the final method will use the threshold.
Proposed Experiments
We will run polar codes P(128,64) (5G), and $N\in\{256,512,1024\}$ at rates 1/4 and 1/2, over binary-input AWGN and Rayleigh fading, with SNR swept across the waterfall region. The metrics are FER with confidence intervals, and the full distribution of decoding steps (mean, 99th and 99.9th percentiles), including check costs. We will also report the deadline-miss rate: the fraction of frames exceeding a step budget set to fast pruned SC's median at each SNR.
The decisive check is medium SNR on $N=1024$. If local gating stacked with the whole-block check reduces 99.9th-percentile steps relative to fast pruned SC and to the reimplemented whole-block method at FER within confidence bounds, the core claim holds. A second check plots gate pass rate against node size and depth. This tests the mechanism directly: errors should concentrate in a few weak subtrees. A third check, the SCL extension at list size 8, reports the FER cost of hard-decision acceptance. That result determines whether the idea reaches list decoding or stays an SC-only latency tool.
References
- Sublinear Latency for Simplified Successive Cancellation Decoding of Polar Codes
- Successive Syndrome-Check Decoding of Polar Codes
- Generalized Segmented Bit-Flipping Scheme for Successive Cancellation Decoding of Polar Codes With Cyclic Redundancy Check
- A cyclic redundancy check aided encoding construction method for list sphere polar decoder
- Unfolding WMMSE Using Graph Neural Networks for Efficient Power Allocation
- (Almost) Practical Tree Codes
- CRC-Aided Learned Ensembles of Belief-Propagation Polar Decoders
- CRISP: Curriculum based Sequential neural decoders for Polar code family