-
摘要:
极化(Polar)码因其信道容量特征和具有较低的编译码复杂度，现已广泛应用于第五代移动通信技术(5G)当中。置信传播(BP)译码算法具有并行执行、高吞吐率的特点，是常用的极化码译码算法，为降低其译码复杂度和译码延时，提出了一种基于任务流图结构重构(TGR)的极化码BP译码算法，通过图等价关系，对译码算法进行两步结构优化。采用冗余消除算法去掉BP译码算法中的冗余计算，简化算法运算结构；采用分支变换算法调整运算顺序，缩减关键路径延时。与3种典型的结构优化BP译码算法相比，所提的BP-TGR译码算法可以至少降低2.3%的关键路径延时，减少4.2%的浮点运算量，且几乎没有纠错性能损失，具有更优秀的综合性能，尤其是在延时敏感和信道条件较恶劣的应用场景中。
Abstract:Polar codes have become prevalent in the fifth-generation mobile communication technology (5G) owing to their capacity characteristics and straightforward compilation. The belief propagation (BP) decoding algorithm, which demonstrates parallel execution and a high throughput rate, is a commonly employed polar code decoding algorithm. This paper proposes a BP decoding algorithm based on task graph reconstruction (TGR) to reduce the algorithm's decoding complexity and delay. Using graph equivalence relations, the decoding algorithm is structurally optimized in two steps. Firstly, the redundancy elimination algorithm is used to remove the redundant calculations in the BP decoding algorithm and simplify the algorithm's operation structure. Subsequently, the branch transformation algorithm is used to optimize the operation order and reduce the critical path delay. The suggested BP algorithm has a better overall performance, particularly in application scenarios with sensitive delay and harsh channel conditions, than the three BP decoding algorithms that aim for structural optimization. It can reduce the critical path delay by at least 2.3%, reduce the computational complexity by at least 4.2%, and virtually eliminate the loss of error correction performance.
-
图 1 (8,4)码BP译码因子图(N=8)
Figure 1. Factor graph of (8,4) polar code with code length N=8
图 3 单比特首次迭代BP译码的任务流图（N=8）
Figure 3. Task flow diagram for single-bit first iteration BP decoding with code length N=8
图 4 基于任务流图结构重构的BP译码算法流程
Figure 4. Flow chart of BP decoding algorithm based on task graph reconstruction
图 5 冗余结构等价变换示意
Figure 5. Schematic diagram of the redundant structural equivalence transformation
图 9 5种算法在不同码长下的关键路径延时
Figure 9. Critical path delay of five BP decoding algorithms at different code lengths
图 10 5种算法在不同Eb/N0下的关键路径延时
Figure 10. Critical path delay of five BP decoding algorithms with different Eb/N0
图 11 5种算法在不同码率下的关键路径延时
Figure 11. Critical path delay of five BP decoding algorithms with different code rates
图 12 5种算法在不同码长下的浮点运算量
Figure 12. Computational complexity of five BP decoding algorithms at different code lengths
图 13 5种算法在不同Eb/N0下的浮点运算量
Figure 13. Computational complexity of five BP decoding algorithms with different Eb/N0
图 14 5种算法在不同码率下的浮点运算量
Figure 14. Computational complexity of five BP decoding algorithms with different code rates
表 1 BP-TGR译码算法的消融实验
Table 1. Ablation experiment for BP-TGR
实验 关键路径延时 浮点运算量 Origin-BP 436 2.46×106 仅分支变换 412 2.79×106 仅冗余消除 213 1.12×106 联合优化 194 1.17×106 
下载: 导出CSV
-
[1] 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. [2] Arikan E. Polar codes: a pipelined implementation[C]//Proceedings of the 4th International Symposium on Broadband Communication. Piscataway: IEEE Press, 2010: 11-14. [3] Alamdar-Yazdi A, Kschischang F R. A simplified successive-cancellation decoder for polar codes[J]. IEEE Communications Letters, 2011, 15(12): 1378-1380. [4] Tal I, Vardy A. List decoding of polar codes[C]//Proceedings of the 2011 IEEE International Symposium on Information Theory Proceedings. Saint piscataway: IEEE Press, 2011: 1-5. [5] Fayyaz U U, Barry J R. Low-complexity soft-output decoding of polar codes[J]. IEEE Journal on Selected Areas in Communications, 2014, 32(5): 958-966. [6] Hussami N, Korada S B, Urbanke R. Performance of polar codes for channel and source coding[C]//Proceedings of the 2009 IEEE International Symposium on Information Theory. Piscataway: IEEE Press, 2009: 1488-1492. [7] Zhang Y, Zhang Q, Pan X, et al. A simplified belief propagation decoder for polar codes[C]//Proceedings of the 2014 IEEE International Wireless Symposium. Piscataway: IEEE Press, 2014: 1-4. [8] Abbas S M, Fan Y Z, Chen J, et al. High-throughput and energy-efficient belief propagation polar code decoder[J]. IEEE Transactions on Very Large Scale Integration Systems, 2017, 25(3): 1098-1111. [9] Feng B P, Liu R K. Efficient-memory and low-latency BP decoding algorithm for polar codes[J]. IEEE Communications Letters, 2020, 24(6): 1236-1239. [10] Cammerer S, Ebada M, Elkelesh A, et al. Sparse graphs for belief propagation decoding of polar codes[C]//Proceedings of the 2018 IEEE International Symposium on Information Theory. Piscataway: IEEE Press, 2018: 1465-1469. [11] Gong Z H, Shen Y F, Ji H R, et al. Bipartite belief propagation polar decoding with bit-flipping[C]//ICASSP 2020 - 2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). Barcelona: IEEE Press, 2020: 1703-1707. [12] Chen Z Y, Zhao H, Hou L. Sparse factor graph-based expanded iterative detection and decoding scheme for uplink polar coded SCMA system[C]//2022 IEEE International Symposium on Broadband Multimedia Systems and Broadcasting (BMSB). Bilbao: IEEE Press, 2022: 1-6. [13] Liu H, Gunawan E, Hu Y Y, et al. BP-based sparse graph list decoding of polar codes[J]. IEEE Communications Letters, 2023, 27(5): 1257-1261. [14] Li Z Y, Shen Y F, Ren Y Q, et al. Belief propagation decoding for short-length codes based on sparse tanner graph[J]. IEEE Communications Letters, 2024, 28(5): 969-973. [15] Arikan E. Channel combining and splitting for cutoff rate improvement[C]//Proceedings of International Symposium on Information Theory. Piscataway: IEEE Press, 2005: 671-675. [16] Kschischang F R, Frey B J, Loeliger H A. Factor graphs and the sum-product algorithm[J]. IEEE Transactions on Information Theory, 2001, 47(2): 498-519. [17] Pamuk A. An FPGA implementation architecture for decoding of polar codes[C]//Proceedings of the 2011 8th International Symposium on Wireless Communication Systems. Piscataway: IEEE Press, 2012: 437-441. [18] Yuan B, Parhi K K. Architecture optimizations for BP polar decoders[C]//Proceedings of the 2013 IEEE International Conference on Acoustics, Speech And Signal Processing. Piscataway: IEEE Press, 2013: 2654-2658. [19] Balogun P R, Marsland I D, Gohary R H, et al. Polar code design for irregular multidimensional constellations[J]. IEEE Access, 2017, 5: 21941-21953. -
下载:
点击查看大图
计量
- 文章访问数: 180
- HTML全文浏览量: 85
- PDF下载量: 16
- 被引次数: 0
