LDPC的分段多因子最小和译码算法

doi:10.12305/j.issn.1001-506X.2025.05.32

摘要/Abstract

摘要：

针对低密度奇偶校验码(low-density parity-check, LDPC)的最小和(minimum sum, MS)译码算法校验节点更新数值偏大而造成译码性能较差的问题, 引入分段修正和线性最小均方误差估计参数的方法, 对校验节点更新进行补偿, 提出基于线性最小均方误差估计准则的分段多因子MS(linear minimum mean square error-segmented multi-factor MS, LMMSE-SMFMS)译码算法。首先对比分析MS译码算法和置信度传播(belief propagation, BP)译码算法性能, 然后使用3组基于线性最小均方误差估计准则的修正因子对校验节点更新补偿的方法, 最后采用分层调度方式, 加快信息传递过程中的收敛速度。理论分析与仿真结果表明: 对于准循环LDPC(quasi-cyclic-LDPC, QC-LDPC), 在使用线性最小均方误差估计和分段修正因子的条件下, 所提算法与MS相比, 在误比特率、信息收敛速度等性能方面具有技术增益。

关键词: 低密度奇偶校验码, 最小和译码算法, 分段多因子, 分层调度

Abstract:

In order to solve the issue of inaccurate check node updates and the resulting decoding performance limitations in the minimum sum (MS) decoding algorithm for low-density parity-check (LDPC) codes, a method is proposed to compensate for the verification node updates. This method incorporates segmented correction and linear minimum mean square error estimation parameters. The resulting algorithm is referred to as the linear minimum mean square error segmented multi-factor MS (LMMSE-SMFMS) decoding algorithm. Firstly, a comparative analysis is conducted to assess the performance of the MS decoding algorithm and the belief propagation (BP) decoding algorithm. Subsequently, a compensation method for check node updates is employed using three sets of correction factors based on linear minimum mean square error estimation. Finally, a layered scheduling approach is implemented to expedite the convergence speed during the information propagation process. Theoretical analysis and simulation results demonstrate that for quasi-cyclic-LDPC (QC-LDPC), under the conditions of utilizing linear minimum mean square error estimation and segmented correction factors, the proposed algorithm demonstrates technical gains compared to the MS algorithm in terms of bit error rate, information convergence speed, and other performance aspects.

Key words: low-density parity-check (LDPC), minimum sum (MS) decoding algorithm, segmented multi-factor (SMF), hierarchical scheduling

中图分类号:

TN911.22

孙志国, 王一珂, 宁晓燕. LDPC的分段多因子最小和译码算法[J]. 系统工程与电子技术, 2025, 47(5): 1698-1705.

Zhiguo SUN, Yike WANG, Xiaoyan NING. Segmented multi-factor minimum sum decoding algorithm for LDPC[J]. Systems Engineering and Electronics, 2025, 47(5): 1698-1705.

图/表 13

图1

图2

图3

图4

图5

图6

表1

图7

图8

图9

表2

图10

图11

参考文献 30

1	GALLAGER R G . Low density parity check codes[J]. IRE Transactions on Information Theory, 1962, 8 (1): 21- 28. doi: 10.1109/TIT.1962.1057683
2	MACKAY D J C , NEAL R M . Near Shannon limit performance of low density parity check codes[J]. Electronics Letters, 1996, 33, 457- 458.
3	CHANVAT R, GARCIA-PENA A, PAONNI M. On efficient and low-complexity decoding of binary LDPC-coded CSK signals for GNSS links with increased data rates[C]//Proc. of the IEEE/ION Position, Location and Navigation Symposium, 2020: 1202-1213.
4	MAHDI A , KANISTRA N , PALIOURAS V . A multirate fully parallel LDPC encoder for the IEEE 802.11n/ac/ax QC-LDPC codes based on reduced complexity XOR trees[J]. IEEE Trans.on Very Large Scale Integration (VLSI) Systems, 2021, 29 (1): 51- 64. doi: 10.1109/TVLSI.2020.3034046
5	LEE S J , PARK S S , JANG B S , et al. Multi-mode QC-LDPC decoding architecture with novel memory access scheduling for 5G new-radio standard[J]. IEEE Trans.on Circuits and Systems Ⅰ: Regular Papers, 2022, 69 (5): 2035- 2048. doi: 10.1109/TCSI.2022.3150022
6	RICHARDSON T J , URBANKE R L . The capacity of low-density parity-check codes under message-passing decoding[J]. IEEE Trans.on Information Theory, 2002, 47 (2): 599- 618.
7	FOSSORIER M P C , MIHALIEVIC M , LMAI H , et al. Reduced complexity iterative decoding of low-density parity check codes based on belief propagation[J]. IEEE Trans.on Communications, 1999, 47 (5): 673- 680. doi: 10.1109/26.768759
8	LIU X C , ZHANG Y B , CUI R . Variable-node-based dynamic scheduling strategy for belief-propagation decoding of LDPC codes[J]. IEEE Communications Letters, 2015, 19 (2): 147- 150. doi: 10.1109/LCOMM.2014.2385096
9	CHEN J , FOSSORIER M P C . Near optimum universal belief propagation based decoding of low-density parity check codes[J]. IEEE Trans.on Communications, 2002, 50 (3): 406- 414. doi: 10.1109/26.990903
10	CHEN J , FOSSORIER M P C . Density evolution for two improved BP-based decoding algorithms of LDPC codes[J]. IEEE Communications Letters, 2002, 6 (5): 208- 210. doi: 10.1109/4234.1001666
11	范亚楠, 王丽冲, 姚秀娟, 等. 一种交叠的Shuffled-BP LDPC译码算法[J]. 电子与信息学报, 2016, 38 (11): 2908- 2915.
	FAN Y N , WANG L C , YAO X J , et al. An overlapped Shuffled-BP LDPC decoding algorithm[J]. Journal of Electronics & Information Technology, 2016, 38 (11): 2908- 2915.
12	YEDIDIA J S , WANG Y , DRAPER S C . Divide and concur and difference-map BP decoders for LDPC codes[J]. IEEE Trans.on Information Theory, 2011, 57 (2): 786- 802. doi: 10.1109/TIT.2010.2094815
13	DARABIHA A, CARUSON A C, KSCHISCHANG F R. A bit-serial approximate min-sum LDPC decoder and FPGA implementation[C]//Proc. of the IEEE International Symposium on Circuits & Systems, 2006: 4-7.
14	WU Z J , SU K X , GUO L T . A modified min sum decoding algorithm based on LMMSE for LDPC codes[J]. AEUE-International Journal of Electronics and Communications, 2014, 68 (10): 994- 999.
15	WANG X M , CAO W L , LI J , et al. Improved min-sum algorithm based on density evolution for low-density parity check codes[J]. IET Communications, 2017, 11 (10): 1582- 1586. doi: 10.1049/iet-com.2017.0014
16	陈发堂, 张友寿, 杜铮. 5G低密度奇偶校验码的低复杂度偏移最小和算法[J]. 计算机应用, 2020, 40 (7): 2028- 2032.
	CHEN F T , ZHANG Y S , DU Z . Low complexity offset min-sum algorithm for 5G low density parity check codes[J]. Journal of Computer Applications, 2020, 40 (7): 2028- 2032.
17	陈发堂, 李贺宾, 李平安. 基于偏移最小和的LDPC译码改进算法[J]. 系统工程与电子技术, 2022, 44 (7): 2350- 2356. doi: 10.12305/j.issn.1001-506X.2022.07.32
	CHEN F T , LI H B , LI P A . Improved algorithm based on offset min-sum decoding for LDPC codes[J]. Systems Engineering and Electronics, 2022, 44 (7): 2350- 2356. doi: 10.12305/j.issn.1001-506X.2022.07.32
18	CAI H H, YANG Y K, YI Q. A low complexity decoding algorithm design based on quasi-cyclic LDPC codes[C]//Proc. of the International Conference on Computing, Electronics & Communications Engineering, 2020: 45-50.
19	宁晓燕, 孙晶晶, 孙志国, 等. LDPC码的分层类拟合修正最小和译码算法[J]. 哈尔滨工业大学学报, 2022, 54 (11): 88- 94.
	NING X Y , SUN J J , SUN Z G , et al. Layered class fitting modified minimum sum decoding algorithm for LDPC codes[J]. Journal of Harbin Institute of Technology, 2022, 54 (11): 88- 94.
20	JIAO X P , MU J J , WEI H Y . Reduced complexity node-wise scheduling of ADMM decoding for LDPC codes[J]. IEEE Communications Letters, 2017, 21 (3): 472- 475. doi: 10.1109/LCOMM.2016.2643629
21	CUI H X , GHAFFARI F , LE K , et al. Design of high-performance and area-efficient decoder for 5G LDPC codes[J]. IEEE Trans.on Circuits and Systems Ⅰ: Regular Papers, 2021, 68 (2): 879- 891. doi: 10.1109/TCSI.2020.3038887
22	JIAO X P , MU J J , HE Y C , et al. Efficient ADMM decoding of LDPC codes using lookup tables[J]. IEEE Trans.on Communications, 2017, 65 (4): 1425- 1437. doi: 10.1109/TCOMM.2017.2659733
23	BAI J , CHI Y H , YUEN C . Efficient MP decoding via fast G-BADMM approach for binary LDPC codes[J]. IEEE Communications Letters, 2023, 27 (3): 782- 786. doi: 10.1109/LCOMM.2022.3232703
24	LIU H Y , HE P Q , JIANG Y , et al. A simple check polytope projection penalized algorithm for ADMM decoding of LDPC codes[J]. IEEE Access, 2023, 11, 2524- 2530. doi: 10.1109/ACCESS.2023.3234182
25	XIA Q Q , LIN Y , TANG S D , et al. A fast approximate check polytope projection algorithm for ADMM decoding of LDPC codes[J]. IEEE Communications Letters, 2019, 23 (9): 1520- 1523. doi: 10.1109/LCOMM.2019.2926085
26	胡东伟. 5G LDPC码译码器实现[J]. 电子与信息学报, 2021, 43 (4): 1112- 1119.
	HU D W . On the implementation of 5G LDPC decoder[J]. Journal of Electronics & Information Technology, 2021, 43 (4): 1112- 1119.
27	TIAN K D , WANG H . A novel base graph based static sche-duling scheme for layered decoding of 5G LDPC codes[J]. IEEE Communications Letters, 2022, 26 (7): 1450- 1453. doi: 10.1109/LCOMM.2022.3171658
28	LIANG Y H , LAM C T , NG B K. . A low complexity neural normalized min-sum LDPC decoding algorithm using tensor-train decomposition[J]. IEEE Communications Letters, 2022, 26 (12): 2914- 2918. doi: 10.1109/LCOMM.2022.3207506
29	CHEN J H , DHOLAKIA A , ELEFTHERIOU E , et al. Reduced-complexity decoding of LDPC codes[J]. IEEE Trans.on Communications, 2005, 53 (8): 1288- 1299. doi: 10.1109/TCOMM.2005.852852
30	LEI Y M , JIN Y , ZHANG J J . Check-node lazy scheduling approach for layered belief propagation decoding algorithm[J]. Electronics Letters, 2014, 50 (4): 278- 279. doi: 10.1049/el.2013.3199

算法	取幂	对数	乘法	除法	加法	比较	异或
BP	2ω	2ω	0	2ω	6ω－L	0	6ω－L
MS	0	0	0	0	0	2ω	2ω－L
NMS	0	0	ω	0	0	2ω	2ω－L
OMS	0	0	0	0	ω	3ω	2ω－L
OR-OMS	0	0	0	0	ω	3ω	2ω－L
LMMSE-MS	0	0	ω	0	ω	3ω	2ω－L
LMMSE-SMFMS	0	0	ω	0	ω	4ω	2ω－L

码长	信噪比/dB
码长	1.4	1.6	1.8	2.0
2016	0.003 9/0.006 8	0.000 7/0.001 4	9.6×10^-5/1.9×10^-4	3.9×10^-6/1.6×10^-5
768	0.012/0.014	0.005 1/0.006 5	0.002 2/0.002 9	6.0×10^-4/8.0×10^-4

[1]	袁磊, 杨艳娟, 郭毅, 戴鹏. 相关噪声下基于深度学习的LDPC码码率半盲识别算法[J]. 系统工程与电子技术, 2025, 47(4): 1335-1345.
[2]	郑仁乐, 李东阳, 刘文学, 万金涛, 刘学勇, 李金海. LDPC码的分层自适应最小和译码算法[J]. 系统工程与电子技术, 2024, 46(12): 4231-4237.
[3]	陈发堂, 李贺宾, 李平安. 基于偏移最小和的LDPC译码改进算法[J]. 系统工程与电子技术, 2022, 44(7): 2350-2356.
[4]	刘恒燕, 张立民, 闫文君, 钟兆根, 凌青, 梁晓军. 基于WBP-CNN算法的LDPC译码[J]. 系统工程与电子技术, 2022, 44(3): 1030-1035.
[5]	王任之, 潘克刚, 赵瑞祥. 跳频抗干扰通信系统中LDPC码的编码优化设计[J]. 系统工程与电子技术, 2022, 44(11): 3548-3555.
[6]	潘睿, 袁磊. 脉冲信道下基于深度学习的BP译码方法[J]. 系统工程与电子技术, 2020, 42(9): 2116-2122.
[7]	黄胜, 宋静, 袁建国. 基于完备循环差集的type-Ⅱ QC-LDPC码的构造[J]. 系统工程与电子技术, 2018, 40(11): 2586-.
[8]	高翔, 吴湛击, 吴熹. 基于低密度格码的编码协作中继系统[J]. 系统工程与电子技术, 2017, 39(5): 1126-1133.
[9]	袁建国, 李媛媛, 敖翔, 庞宇, 林金朝. 基于完备循环差集的大围长Type-Ⅱ QC-LDPC码的构造[J]. 系统工程与电子技术, 2017, 39(11): 2587-2591.
[10]	胡星, 马林华, 孙康宁, 黄天宇, 刘士平. 高阶量纠错码理论限及软判决编译码算法[J]. 系统工程与电子技术, 2017, 39(10): 2312-2319.
[11]	鲁凌云, 霍丽丽, 杜海峰. 多用户MIMO-OFDM的多维协同安全策略[J]. 系统工程与电子技术, 2016, 38(10): 2413-2419.
[12]	赵宏伟, 张凯. 卫星通信中低复杂度联合迭代译码算法及仿真[J]. 系统工程与电子技术, 2016, 38(1): 147-154.
[13]	陈正康1,2, 张会生1, 李立欣1, 朱梦1. LDPC码最小和译码算法的整数量化[J]. 系统工程与电子技术, 2015, 37(10): 2371-2375.
[14]	薛睿, 魏强, 徐锡超. [J]. 系统工程与电子技术, 2015, 37(1): 169-174.
[15]	林志国，彭卫东，林晋福，檀蕊莲，宋晓鸥. LDPC码最优化译码算法[J]. 系统工程与电子技术, 2014, 36(9): 1849-1853.