Low-Complexity Successive-Cancellation List Decoding of 2×2 Kernel Non-Binary Polar Codes

Jul 16, 2026

Non-binary successive cancellation list (NB-SCL) decoding increases complexity because each surviving path is expanded into q candidate branches at every information symbol, then incurs heavy sorting and pruning. This paper presents low-complexity list decoders for 2×2-kernel non-binary polar codes by combining split reduction, Rate-1 structural switching, and adaptive pruning. SR-NBSCL skips splitting on sufficiently reliable symbols, ESR-NBSCL applies simplified NB-SC to the last group, and ABP-NBSCL prunes unreliable candidates using accumulated reliability deviation before sorting. Simulations show FER close to conventional NB-SCL with much lower complexity; ABP-NBSCL reduces path splitting by over 80% at tested SNRs with negligible loss.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages13

Reading Time33 min

Abstract

Introduction

Background on polar codes and decoding

Complexity challenge of NB-SCL decoding

Related work on low-complexity SCL/NB decoding

Motivation and contributions for 2×2 kernel NBPCs

Low-Complexity Successive-Cancellation List Decoding of 2 􀀂 2 Kernel Non-Binary Polar Codes Xinyu Zhou, Pingping Chen arXiv :2607 .09257v 1 [ cs .IT] 10 Jul 2026 Abstract—Non-binary successive cancellation list (NB-SCL) decoding expands each surviving path into q candidate branches at every information symbol, which causes high path expansion, sorting, and pruning complexity. To address this issue, this paper proposes low-complexity list decoding algorithms for 2 × 2 kernel non-binary polar codes (NBPCs). First, we design a split-reduced non-binary successive cancellation list (SR-NBSCL) decoder that skips path splitting when the current symbol is sufﬁciently reliable. We then exploit the ﬁnal Rate-1 node structure and switch the last group of information symbols to simpliﬁed nonbinary successive cancellation (NB-SC) decoding, resulting in the enhanced split-reduced non-binary successive cancellation list (ESR-NBSCL) decoder. To further reduce branch expansion at unreliable symbols, we introduce an accumulated reliabilitydeviation (ARD) metric and propose an adaptive branch-pruning non-binary successive cancellation list (ABP-NBSCL) decoder, which prunes unreliable candidate branches before sorting and then reducs the dominant sorting complexity. Simulation results show that the proposed decoders achieve frame-error-rate (FER) performance close to that of conventional NB-SCL decoding with much lower complexity. In particular, the ABP-NBSCL decoder reduces the path splitting number (PSN) by more than 80% at several tested signal-to-noise ratios (SNRs), with a negligible performance loss. Index Terms—Non-binary polar codes, successive cancellation list decoding, decoding complexity. I. INTRODUCTION Polar codes, ﬁrst discovered by Arikan, are the ﬁrst capacity-achieving codes for binary-input discrete memoryless channels with an explicit and deterministic structure [1], [2] . Polar codes have also been applied to ﬁnite-length packet recovery in unsourced random access, multi-user spatial modulation systems, and probabilistically-shaped polar-coded modulation for 6G systems [3]–[7] . Under successive cancellation (SC) decoding, polar codes asymptotically achieve capacity with complexity O (N log N) for the block length N [1] . For ﬁnite-length codes, successive cancellation list (SCL) decoding outperforms SC decoding and approaches maximumlikelihood (ML) decoding at high signal-to-noise ratios (SNRs) [8], but with the increased complexity O (LN log N) and Lis the list size [2], [9] . Moreover, Cyclic-redundancy-check (CRC)-aided SCL decoding can further improve the error rate performance [10], [11] . However, the increased decoding complexity for SCL with larger values of L makes polar codes less attractive for practical purposes [12] . This issue becomes more pronounced for non-binary polar codes (NBPCs) over GF (q), since each non-binary information symbol has q possible decisions [13], X. Zhou and P. Chen are with the College of Physics and Information Engineering, Fuzhou University, Fuzhou 350108, China. [14] . Under similar decoding algorithm and coding rate, nonbinary NBPCs often performs superior to their binary counterparts [15]–[17] . Recent studies on NBPCs focus on code construction, kernel design, and efﬁcient SC-based decoding [18]–[21] . Low-complexity SCL decoding has been extensively studied for binary polar codes. Zhang et al. proposed a splitreduced SCL decoder that skips splitting when the current unfrozen bit is sufﬁciently reliable [2] . Other works further introduced reliability tests, path-decision rules, tree pruning, partitioned list decoding, and fast SC/SCL decoding to reduce redundant path operations [22]–[27] . Quantized-softinformation GRAND decoding has also been investigated for CRC-concatenated polar codes, showing lower time and memory complexity than CA-SCL decoding under short-code settings [28] . For short CRC-polar codes, a guessing-ﬂipping framework further combines GR

FAQs

Why is NB-SCL decoding more complex than binary SCL decoding?

In non-binary polar codes over GF(q), each information symbol produces q candidate branches per surviving path, so the number of path-metric candidates grows with both list size L and field order q, making sorting and pruning dominant.

What does the split-reduced SR-NBSCL decoder do?

SR-NBSCL skips path splitting when the current symbol is sufficiently reliable, reducing unnecessary q-ary branch expansion during list decoding.

How does ABP-NBSCL reduce complexity further at unreliable symbols?

ABP-NBSCL introduces an accumulated reliability deviation (ARD) metric to prune unreliable candidate branches before sorting, which reduces the dominant sorting complexity while keeping FER close to conventional NB-SCL.

Jul 16, 2026

Upload by Seraphina