Low-Complexity Successive-Cancellation List Decoding of $2\times2$ Kernel Non-Binary Polar Codes
2026-07-10 • Information Theory
Information Theory
AI summaryⓘ
The authors address the high complexity of decoding non-binary polar codes, where many candidate paths need to be considered at each step. They propose several new decoding methods that reduce this complexity by skipping unnecessary path splits when the data is reliable and pruning unlikely candidates early. Their approaches keep the decoding accuracy similar to traditional methods but with much less computational effort. One key method cuts down the number of path expansions by over 80% with only a small impact on error rates.
non-binary polar codessuccessive cancellation list decodingpath splittingpath pruningrate-1 nodesignal-to-noise ratioframe-error-ratebranch expansionadaptive decoding
Authors
Xinyu Zhou, Pingping Chen
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\times2$ 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 sufficiently reliable. We then exploit the final Rate-1 node structure and switch the last group of information symbols to simplified non-binary 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 reliability-deviation (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 reduces 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.