PaperlayerView exact revision on arXiv

Source-linked AI summary

Parallel Successive Cancellation Perturbation-Enhanced Decoding of Polar Codes via Offline Variance Design

Changwei Tu, Xuanyu Li, Kai Niu

arXiv:2609.34059v1cs.ITmath.IT

TL;DR

Existing perturbation schemes can generate or update attempts sequentially, adding decoding latency, while offline variance design for fixed parallel branches has received limited attention. This paper develops an analytical, greedy variance-selection method for PSCP decoding; simulations show lower BLER than conventional SCP at the same branch count across the evaluated code lengths.

  • Problem

    Many perturbation schemes generate or update attempts according to previous decoding outcomes, increasing latency, while offline variance design for a fixed number of parallel branches has received limited attention.

    Source: §I · p. 1

  • Method

    The method approximates recovery probability conditioned on ordinary SC failure and greedily selects perturbation variances offline from a finite candidate set for PSCP decoding.

    Source: §I · p. 2

  • Results

    OVD-PSCP achieves lower BLER than conventional SCP with the same number of branches for polar-code lengths 64, 128, 256, and 512, with larger gains for shorter codes and more branches.

    Source: §VI · p. 9

  • Takeaways & Limitations

    Because all variances are selected before decoding, the original SC branch and all perturbation branches can start simultaneously.

    Source: §VI · p. 9

Abstract

from arXiv · show

Successive cancellation perturbation-enhanced (SCP) decoding improves the performance of finite-length polar codes by performing multiple SC decoding attempts with receiver-side perturbations. However, many existing perturbation schemes generate or update subsequent perturbations according to the outcomes of previous decoding attempts, resulting in additional decoding latency. In this paper, we propose an offline variance design (OVD) method for parallel SCP (PSCP) decoding of short- and medium-length polar codes. First, we formulate the exact recovery objective conditioned on ordinary SC failure and classify failed frames by the position of the first genie-aided intrinsic error and the number of subsequent intrinsic errors. We also derive a consistent Gaussian representation of the perturbed channel that preserves min-sum SC hard decisions. Second, we construct a class-based approximation of the recovery objective using Gaussian approximation and backward recursions, accounting for both error correction and new errors introduced by perturbations. We prove that both the exact and analytical objectives are nondecreasing and exhibit diminishing marginal gains as independent branches are added. Third, we develop a greedy algorithm to select variances from a finite candidate set for a given code, signal-to-noise ratio (SNR), and number of perturbation branches. All variances are determined offline, allowing the original SC branch and all perturbation branches to start simultaneously. Simulations for rate-$1/2$ polar codes of lengths $64$, $128$, $256$, and $512$ show that OVD-PSCP achieves lower block error rates (BLERs) than conventional SCP with the same number of perturbation branches. The gains are larger for shorter codes and increase as the number of perturbation branches grows.

I. INTRODUCTION

Prior parallel perturbation schemes often update attempts sequentially or use empirically selected variances, while offline design for a fixed number of parallel branches has received limited attention. This paper proposes an analytical, greedy offline variance design for PSCP decoding, so all branches can start simultaneously.

I. INTRODUCTION

  • Sequentially generating or updating perturbations after decoding outcomes increases latency, and offline multiset design for a fixed number of parallel branches has received limited attention.Existing methods may also rely on empirically selected variances or online variance updates.Source: §I · p. 1
  • OVD selects a fixed number of perturbation variances from a finite candidate set using an analytical approximation of recovery probability conditioned on ordinary SC failure.The selected variances are determined offline, allowing the original SC branch and perturbation branches to start simultaneously.Source: §I · p. 2
  • The analysis classifies SC-failed frames by the first genie-aided intrinsic-error position and subsequent error count, and derives a Gaussian representation preserving min-sum SC hard decisions.This provides the basis for modeling the recovery objective under perturbation.Source: §I · p. 2
  • The analytical recovery model uses Gaussian approximation, local repair and damage probabilities, and backward recursions; both exact and approximate objectives have diminishing marginal gains as independent branches are added.Both objectives are also nondecreasing as branches are added.Source: §I · p. 2

A. Polar Codes

  • A polar code P(N, K+r) has length N=2^n and K+r non-frozen bits, selected from the most reliable subchannels; its CRC-aided effective rate is K/N.The remaining N−(K+r) subchannels are assigned to frozen bits.Source: A. Polar Codes · p. 2

B. SC Decoding of Polar Codes

SC decoding recursively applies f- and g-operations and makes hard decisions to produce a source-vector estimate. PSCP runs independent perturbation branches in parallel, and the analysis defines recovery as success by at least one branch conditioned on ordinary SC failure.

B. SC Decoding of Polar Codes

  • SC decoding recursively applies f- and g-operations over the decoding tree to produce an estimate of the source vector.Hard decisions on the decision LLRs yield the bit estimates.Source: B. SC Decoding of Polar Codes · p. 2

C. Parallel SC Perturbation-Enhanced Decoding

  • PSCP runs the original SC branch and T perturbation branches in parallel, with independent Gaussian perturbations added to each branch's channel LLR vector.The original branch uses the unperturbed channel LLR vector, and a CRC check is applied to each decoded candidate.Source: C. Parallel SC Perturbation-Enhanced… · pp. 2–3

III. PERFORMANCE ANALYSIS OF SC PERTURBATION-ENHANCED DECODING

  • The analysis develops an approximation to the conditional recovery objective because class priors and class-wise recovery probabilities are generally unavailable in closed form.Its stated sequence is to estimate those quantities and combine them into a tractable multi-branch objective.Source: §III · p. 3

A. Frame-Level Recovery Objective

  • The frame-level recovery objective is the probability that at least one perturbation branch recovers the transmitted source vector, conditioned on ordinary SC failure.For a fixed failed frame, the branch recovery probabilities combine because perturbation vectors are independent across branches.Source: A. Frame-Level Recovery Objective · p. 3

B. Genie-Aided Error Classification

The classification partitions ordinary-SC failures according to genie-aided intrinsic errors, enabling the frame-level recovery objective to be expressed as a weighted sum over error classes.

B. Genie-Aided Error Classification

  • An ordinary SC failure occurs if and only if at least one intrinsic error occurs in the genie-aided SC decisions.The genie-aided decoder sets preceding non-frozen decisions to their transmitted values.Source: B. Genie-Aided Error Classification · p. 3
  • Each failed-frame class is indexed by the position of its first intrinsic error and the number of subsequent intrinsic errors.For first-error position ℓ and subsequent-error count m, the total number of intrinsic errors is m+1.Source: B. Genie-Aided Error Classification · p. 3
  • The error-class events are mutually exclusive and partition the SC failure event, allowing the frame-level objective to be written using class priors and class-wise recovery probabilities.Those class priors and probabilities are generally unavailable in closed form, motivating an analytical model.Source: B. Genie-Aided Error Classification · p. 3

1) Gaussian Approximation and Decision-Equivalent Channel:

Gaussian approximation models genie-aided decision LLRs, while a positive common scaling converts the perturbed channel to a consistent Gaussian representation without changing min-sum SC hard decisions.

1) Gaussian Approximation and Decision-Equivalent Channel:

  • Under min-sum SC decoding, a perturbed channel is hard-decision equivalent to a consistent Gaussian channel representation.The original perturbed distribution is not consistent Gaussian for positive perturbation variance because its variance is not twice its mean.Source: 1) Gaussian Approximation and… · p. 4
  • Scaling all channel LLRs by a common positive factor preserves every min-sum SC hard decision, including in genie-aided SC decoding.The min-sum f- and g-operations are positively homogeneous, and positive scaling leaves LLR signs unchanged.Source: 1) Gaussian Approximation and… · p. 4
  • The scaled perturbed channel follows a consistent Gaussian distribution, to which Gaussian approximation is applied to estimate decision-LLR means and error probabilities.The passage defines μℓ(v) as the GA mean and pℓ(v) as an approximation of the corresponding error probability.Source: 1) Gaussian Approximation and… · p. 4

2) Local Repair and Damage Probabilities:

The model represents perturbation locally as additive Gaussian noise and separates its effects into repairing erroneous decisions and damaging correct ones. Damage probabilities are chosen to preserve the perturbed marginal error probability, and both transitions are valid probabilities.

2) Local Repair and Damage Probabilities:

  • The local additive-Gaussian model estimates repair probability by perturbing the unperturbed decision LLR under Gaussian approximation.The effective perturbation variance is unchanged through an f-operation and doubled through a g-operation.Source: 2) Local Repair and Damage Probabilities · p. 4
  • Cℓ(v) is the probability that perturbation repairs an erroneous decision, while Dℓ(v) is the probability that it makes a correct decision erroneous.Both probabilities are zero when v = 0.Source: 2) Local Repair and Damage Probabilities · p. 4
  • The repair and damage transitions are valid probabilities, with 0 ≤ Dℓ(v) ≤ 1/2.The derivation uses bounds on the perturbed error probability and repair probability.Source: 2) Local Repair and Damage Probabilities · pp. 4–5
  • Dℓ(v) is determined from the marginal consistency relation so the perturbed error probability pℓ(v) is preserved.Evaluating both transitions directly from the local additive-Gaussian model need not satisfy that consistency relation.Source: 2) Local Repair and Damage Probabilities · pp. 4–5

3) Analytical Error Model and Recovery Recursions:

The analytical model approximates failed-frame error patterns and perturbation transitions, then uses backward recursions to estimate suffix errors and recovery. It combines these quantities into class priors and single-branch recovery probabilities.

3) Analytical Error Model and Recovery Recursions:

  • The analytical model approximates intrinsic-error indicators as independent Bernoulli variables and assumes repair and damage transitions are independent across non-frozen positions.These independence assumptions apply only to the analytical model and approximate the actual SC recovery process.Source: 3) Analytical Error Model and Recovery… · p. 5
  • The backward recursion Bℓ,j estimates the probability of exactly j analytical errors in the suffix after position aℓ.Its two terms represent a correct decision or an intrinsic error at the next position.Source: 3) Analytical Error Model and Recovery… · p. 5
  • The backward recursion Aℓ,j(v) tracks exactly j original suffix errors together with all suffix decisions being correct after perturbation.Its terms represent an originally correct decision remaining correct or an originally erroneous decision being repaired.Source: 3) Analytical Error Model and Recovery… · p. 5
  • The model forms analytical class priors and single-branch recovery probabilities from the first intrinsic-error position and the number of subsequent errors.The analytical class prior approximates the true class prior, and the single-branch recovery probability approximates true recovery probability.Source: 3) Analytical Error Model and Recovery… · p. 5

D. Analytical Objective and Structural Property

The analytical objective approximates the exact frame-level recovery objective using class-level recovery probabilities. Both objectives are nondecreasing as independent branches are added and have diminishing marginal gains.

D. Analytical Objective and Structural Property

  • The analytical objective is a tractable class-level approximation, not an exact representation of the frame-level objective.It replaces the frame-level conditional expectation with class-level probabilities derived using Gaussian, effective-perturbation, and independence approximations.Source: D. Analytical Objective and Structural… · p. 5
  • Both the exact and analytical recovery objectives are nondecreasing, with diminishing marginal gains as independent perturbation branches are added.Adding a branch cannot reduce either objective, and another branch's marginal gain cannot increase after a branch has already been added.Source: D. Analytical Objective and Structural… · p. 6
  • The marginal gain of adding a branch is expressed through recovery on frames or classes that existing branches have not recovered.The exact expression weights a newly added branch's recovery by the probability that all current branches fail.Source: D. Analytical Objective and Structural… · p. 6

IV. OFFLINE VARIANCE DESIGN FOR PSCP DECODING

The section designs perturbation variances offline for a fixed code, operating SNR, and branch count, then combines that design with parallel decoding.

IV. OFFLINE VARIANCE DESIGN FOR PSCP DECODING

  • For a fixed code, operating SNR, and number of branches, OVD selects T variances from a finite candidate set using a greedy algorithm.The candidate variance with the largest marginal gain is selected at each step, and a variance may be selected more than once.Source: §IV · p. 6
  • Variance design is performed offline using the analytical objective developed in Section III.The selected variances are used in online PSCP decoding.Source: §IV · p. 6
  • The complete OVD-PSCP procedure allows the original SC branch and all perturbation branches to decode in parallel.The procedure combines offline variance design with online parallel decoding.Source: §IV · p. 6

A. Candidate Variance Set

The candidate variances are chosen to cover the main perturbation-strength transition regions across non-frozen positions. The design uses a logarithmically spaced finite set, with the selected variances stored for parallel online decoding.

A. Candidate Variance Set

  • The common design range covers the main transition regions of all non-frozen positions under the local model.The perturbation fraction ηℓ(v) increases from 0 to 1, with ρℓ setting the transition's variance scale.Source: A. Candidate Variance Set · p. 6
  • The stored variance multiset lets the original SC branch and all perturbation branches start in parallel, with CRC checks determining whether a decoded estimate is returned.Each perturbation branch generates perturbed LLRs using its assigned variance before SC decoding.Source: A. Candidate Variance Set · p. 7
  • The candidate variances are logarithmically spaced over a model-based interval that need not contain the continuous-domain optimum.The finite candidate set has G variances.Source: A. Candidate Variance Set · pp. 6–7

B. Greedy Variance Allocation

The variance multiset is built offline by repeatedly selecting the candidate with the largest analytical marginal gain. The section also specifies the computational cost and simulation setup.

B. Greedy Variance Allocation

  • The greedy design repeatedly adds the candidate variance with the largest current analytical marginal gain, allowing the same candidate to be selected more than once.After T selections, variances are assigned to perturbation branches in selection order and stored for online decoding.Source: B. Greedy Variance Allocation · p. 7
  • Offline design costs O(GN + TGM^2) operations and O(GM^2) memory for class-wise recovery probabilities.The cost includes analytical precomputation and T greedy selections over G candidates and M(M + 1)/2 error classes.Source: B. Greedy Variance Allocation · p. 7

V. SIMULATION RESULTS

  • The simulations use 5G-standard-designed codes, set ϵ to 0.02 and G to 2049, and count a frame as correctly decoded when it passes CRC.Unlike the proposed LLR perturbation, the SCP variance setting in is applied to the received vector.Source: §V · p. 7

A. Error-Correction Performance

Across polar-code lengths 64–512, OVD-PSCP achieves lower BLER than conventional SCP at the same number of perturbation branches, with larger gains for shorter codes and more branches. Candidate-codeword statistics and the conclusion describe its performance and parallel offline design.

A. Error-Correction Performance

B. Candidate Codeword Analysis

  • At SNRs of 3 dB and above, OVD-PSCP has higher DC and EML than SCP for every listed T; at 5 dB and T = 80, its DC is 52.62% and EML is 3.13%, versus SCP's 10.02% and 1.28%.At 2 dB, the comparison depends on T: OVD-PSCP is higher on both metrics at T = 80, but lower at T = 10, 20, and 40.Source: B. Candidate Codeword Analysis · p. 9, Table I · p. 9

VI. CONCLUSION

  • The analytical recovery model guides a greedy selection of perturbation variances for a fixed branch count, with all branches able to start simultaneously because the variances are set beforehand.The paper's future work targets recovery difficulty among SC-failed frames within the same error class across SNRs and code lengths.Source: §VI · p. 9
  • Across lengths 64, 128, 256, and 512, OVD-PSCP achieves lower BLER than conventional SCP with the same number of branches, with larger gains for shorter codes and more branches.The conclusion also identifies recovery difficulty within an error class as a topic for future study.Source: §VI · p. 9
Loading 2609.34059v1…