Low Complexity Sequential Decoding Algorithm of PAC Code for Short Packet Communication

DAI Jingxin; YIN Hang; WANG Yuhuan; LV Yansong; YANG Zhanxin; LV Rui; XIA Zhiping

doi:10.11999/JEIT250533

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2025 >

DAI Jingxin, YIN Hang, WANG Yuhuan, LV Yansong, YANG Zhanxin, LV Rui, XIA Zhiping. Low Complexity Sequential Decoding Algorithm of PAC Code for Short Packet Communication[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250533

Citation:

DAI Jingxin, YIN Hang, WANG Yuhuan, LV Yansong, YANG Zhanxin, LV Rui, XIA Zhiping. Low Complexity Sequential Decoding Algorithm of PAC Code for Short Packet Communication[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT250533

Citation:

PDF( 5563 KB)

Low Complexity Sequential Decoding Algorithm of PAC Code for Short Packet Communication

doi: 10.11999/JEIT250533 cstr: 32379.14.JEIT250533

1.
State Key Laboratory of Media Convergence and Communication, Communication University of China, Beijing 100024, China
2.
China Academy of Broadcasting Sciences, National Radio and Television Administration, Beijing 100024, China

Funds: National Key Research and Development Project of China (2024YFC3015303), Fundamental Research Funds for the Central Universities (CUC25GT16)

Received Date: 2025-06-09
Rev Recd Date: 2025-09-18

Available Online: 2025-09-24

Abstract

Abstract

Objective With the rise of the intelligent Internet of Things (IoT), short packet communication among IoT devices must meet stringent requirements for low latency, high reliability, and very short packet length, posing challenges to the design of channel coding schemes. As an advanced variant of polar codes, Polarization-Adjusted Convolutional (PAC) codes enhance the error-correction performance of polar codes at medium and short code lengths, approaching the dispersion bound in some cases. This makes them promising for short packet communication. However, the high decoding complexity required to achieve near-bound error-correction performance limits their practicality. To address this, we propose two low complexity sequential decoding algorithms: Low Complexity Fano Sequential (LC-FS) and Low Complexity Stack (LC-S). Both algorithms effectively reduce decoding complexity with negligible loss in error-correction performance. Methods To reduce the decoding complexity of Fano-based sequential decoding algorithms, we propose the LC-FS algorithm. This method exploits special nodes to terminate decoding at intermediate levels of the decoding tree, thereby reducing the complexity of tree traversal. Special nodes are classified into two types according to decoder structure: low-rate nodes (Type-$T$ node) and high-rate nodes [Rate-1 and Single Parity-Check (SPC) nodes]. This classification minimizes unnecessary hardware overhead by avoiding excessive subdivision of special nodes. For each type, a corresponding LC-FS decoder and node-movement strategy are developed. To reduce the complexity of stack-based decoding algorithms, we propose the LC-S algorithm. While preserving the low backtracking feature of stack-based decoding, this method introduces tailored decoding structures and node-movement strategies for low-rate and high-rate special nodes. Therefore, the LC-S algorithm achieves significant complexity reduction without compromising error-correction performance. Results and Discussions The performance of the proposed LC-FS and LC-S decoding algorithms is evaluated through extensive simulations in terms of Frame Error Rate (FER), Average Computational Complexity (ACC), Maximum Computational Complexity (MCC), and memory requirements. Traditional Fano sequential, traditional stack, and Fast Fano Sequential (FFS) decoding algorithms are set as benchmarks. The simulation results show that the LC-FS and LC-S algorithms exhibit negligible error-correction performance loss compared with traditional Fano sequential and stack decoders (Fig. 5). Across different PAC codes, both algorithms effectively reduce decoding complexity. Specifically, as increases, the reductions in ACC and MCC become more pronounced. For ACC, LC-FS decoding algorithm ($T = 4$) achieves reductions of 13.77% ($N = 256$, $K = 128$), 11.42% ($N = 128$, $K = 64$), and 25.52% ($N = 64$, $K = 32$) on average compared with FFS (Fig. 6). LC-S decoding algorithm ($T = 4$) reduces ACC by 56.48% ($N = 256$, $K = 128$), 47.63% ($N = 128$, $K = 64$), and 49.61% ($N = 64$, $K = 32$) on average compared with the traditional stack algorithm (Fig. 6). For MCC, LC-FS decoding algorithm ($T = 4$) achieves reductions of 29.71% ($N = 256$, $K = 128$), 21.18% ($N = 128$, $K = 64$), and 23.62% ($N = 64$, $K = 32$) on average compared with FFS (Fig. 7). LC-S decoding algorithm ($T = 4$) reduces MCC by 67.17% ($N = 256$, $K = 128$), 49.33% ($N = 128$, $K = 64$), and 51.84% ($N = 64$, $K = 32$) on average compared with the traditional stack algorithm (Fig. 7). By exploiting low-rate and high-rate special nodes to terminate decoding at intermediate levels of the decoding tree, the LC-FS and LC-S algorithms also reduce memory requirements (Table 2). However, as $T$ increases, the memory usage of LC-S rises because all extended paths of low-rate special nodes are pushed into the stack. The increase in $T$ enlarges the number of extended paths, indicating its critical role in balancing decoding complexity and memory occupation (Fig. 8). Conclusions To address the high decoding complexity of sequential decoding algorithms for PAC codes, this paper proposes two low complexity approaches: the LC-FS and LC-S algorithms. Both methods classify special nodes into low-rate and high-rate categories and design corresponding decoders and movement strategies. By introducing Type-$T$ nodes, the algorithms further eliminate redundant computations during decoding, thereby reducing complexity. Simulation results demonstrate that the LC-FS and LC-S algorithms substantially decrease decoding complexity while maintaining the error-correction performance of PAC codes at medium and short code lengths.
- Short-packet communication,
- PAC code,
- Low complexity,
- Sequential decoding,
- Special node

FullText(HTML)

References(23)

References

[1]	International Telecommunication Union Radiocommunication Sector. ITU-R M. 216-0 Framework and overall objectives of the future development of IMT for 2030 and beyond[S]. Geneva: Electronic Publication, 2023.
[2]	European Telecommunications Standards Institute. 3GPP TR 138.913 Study on scenarios and requirements for next generation access technologies[S]. Sophia Antipolis: 3GPP, 2017. (查阅网上资料, 不确定本条文献标准号与出版社信息, 请确认).
[3]	JIANG Wei, ZHOU Qiuheng, HE Jiguang, et al. Terahertz communications and sensing for 6G and beyond: A comprehensive review[J]. IEEE Communications Surveys & Tutorials, 2024, 26(4): 2326–2381. doi: 10.1109/COMST.2024.3385908.
[4]	ROWSHAN M, QIU Min, XIE Yixuan, et al. Channel coding toward 6G: Technical overview and outlook[J]. IEEE Open Journal of the Communications Society, 2024, 5: 2585–2685. doi: 10.1109/OJCOMS.2024.3390000.
[5]	MIAO Sisi, KESTEL C, JOHANNSEN L, et al. Trends in channel coding for 6G[J]. Proceedings of the IEEE, 2024, 112(7): 653–675. doi: 10.1109/JPROC.2024.3416050.
[6]	ARIKAN E. Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels[J]. IEEE Transactions on Information Theory, 2009, 55(7): 3051–3073. doi: 10.1109/TIT.2009.2021379.
[7]	European Telecommunications Standards Institute. 3GPP TS 38.212 Multiplexing and channel coding[S]. Sophia Antipolis: 3GPP, 2018. (查阅网上资料, 不确定本条文献标准号与出版社信息和年份, 请确认).
[8]	ARıKAN E. From sequential decoding to channel polarization and back again[EB/OL]. https://arxiv.org/abs/1908.09594, 2019.
[9]	POLYANSKIY Y, POOR H V, and VERDU S. Channel coding rate in the finite blocklength regime[J]. IEEE Transactions on Information Theory, 2010, 56(5): 2307–2359. doi: 10.1109/TIT.2010.2043769.
[10]	FANO R. A heuristic discussion of probabilistic decoding[J]. IEEE Transactions on Information Theory, 1963, 9(2): 64–74. doi: 10.1109/TIT.1963.1057827.
[11]	JELINEK F. Fast sequential decoding algorithm using a stack[J]. IBM Journal of Research and Development, 1969, 13(6): 675–685. doi: 10.1147/rd.136.0675.
[12]	ROWSHAN M, BURG A, and VITERBO E. Complexity-efficient Fano decoding of polarization-adjusted convolutional (PAC) codes[C]. 2020 International Symposium on Information Theory and Its Applications (ISITA), Kapolei, USA, 2020: 200–204.
[13]	MORADI M. On sequential decoding metric function of polarization-adjusted convolutional (PAC) codes[J]. IEEE Transactions on Communications, 2021, 69(12): 7913–7922. doi: 10.1109/TCOMM.2021.3111018.
[14]	WU Yunzhi, LI Li, and FAN Pingzhi. A fast parallel SC-Fano decoding algorithm for PAC codes[J]. Science China Information Sciences, 2023, 66(5): 152301. doi: 10.1007/s11432-022-3498-8.
[15]	ZHANG Li, LIU Haina, and HE Yejun. Improved stack decoding for PAC codes[C]. 2023 32nd Wireless and Optical Communications Conference (WOCC), Newark, USA, 2023: 1–5. doi: 10.1109/WOCC58016.2023.10139571.
[16]	DAI Jingxin, YIN Hang, LV Yansong, et al. Neural network aided low-complexity decoding for PAC codes[J]. IEEE Wireless Communications Letters, 2025, 14(6): 1638–1642. doi: 10.1109/LWC.2025.3551288.
[17]	易方博, 蔡作鑫, 梁积卫, 等. CRC-MPAC码及其高效译码[J]. 移动通信, 2025, 49(2): 36–42. doi: 10.3969/j.issn.1006-1010.20250101-0001. YI Fangbo, CAI Zuoxin, LIANG Jiwei, et al. CRC-MPAC codes and its efficient decoding[J]. Mobile Communications, 2025, 49(2): 36–42. doi: 10.3969/j.issn.1006-1010.20250101-0001.
[18]	JI Houren, SHEN Yifei, ZHANG Zaichen, et al. Low-complexity fast Fano decoding for PAC codes[J]. IEEE Transactions on Vehicular Technology, 2023, 72(12): 15172–15184. doi: 10.1109/TVT.2023.3298847.
[19]	MOHSEN M. Performance and computational analysis of polarization-adjusted convolutional (PAC) codes[D]. [Ph. D. dissertation], Bilkent University, 2022.
[20]	DAI Jingxin, YIN Hang, LV Yansong, et al. Fast list decoding of PAC codes with new nodes[J]. IEEE Communications Letters, 2024, 28(3): 449–453. doi: 10.1109/LCOMM.2024.3354490.
[21]	ZHU Hongfei, CAO Zhiwei, ZHAO Yuping, et al. Fast list decoders for polarization-adjusted convolutional (PAC) codes[J]. IET Communications, 2023, 17(7): 842–851. doi: 10.1049/cmu2.12587.
[22]	MORADI M and MOZAMMEL A. A Monte-Carlo based construction of polarization-adjusted convolutional (PAC) codes[J]. Physical Communication, 2025, 68: 102578. doi: 10.1016/j.phycom.2024.102578.
[23]	ROWSHAN M, BURG A, and VITERBO E. Polarization-adjusted convolutional (PAC) codes: Sequential decoding vs list decoding[J]. IEEE Transactions on Vehicular Technology, 2021, 70(2): 1434–1447. doi: 10.1109/TVT.2021.3052550.