基于编码分布式快速哈达玛变换的多元LDPC码译码算法研究

doi:10.11959/j.issn.1000-436x.2023199

摘要/Abstract

摘要：

尽管多元 LDPC 码纠错性能优异且能抗突发错误，但高译码复杂度仍制约了其实际应用。在其经典的FHT-QSPA译码中，快速哈达玛变换（FHT）及其逆变换（IFHT）是校验节点更新的主要瓶颈。基于此，提出了基于系统型MDS码的编码分布式FHT方案。该方案在主节点上将信道概率建模为矩阵并对其进行切分，再编码生成冗余子矩阵；其后，将所有子矩阵卸载到从节点并行执行FHT和IFHT，然后将计算结果传回主节点并完成最终译码。编码冗余的嵌入克服了节点掉队问题，稳定地提升了变换效率，从而加速了整个译码过程。与先前的编码矩阵乘法方案相比，所提方案编码复杂度更低、译码恢复数值精度更高，并保持了高效蝶形运算结构，降低了从节点计算复杂度。耗时对比和译码性能分析表明，所提方案相比传统单节点FHT方案快了约3.8倍，大幅提升了FHT-QSPA译码效率，且没有译码性能损失。

关键词: 多元LDPC码译码, 编码分布式计算, 快速哈达玛变换

Abstract:

Despite the excellent error correction performance and burst error resistance capability of non-binary LDPC codes, the complexity of the decoding algorithms hinders their broader application.In the classic FHT-QSPA decoding, the fast Hadamard transform (FHT) and its inverse transform (IFHT) have become the main bottleneck for updating the check nodes.Therefore, a coded distributed FHT scheme based on systematic MDS codes was proposed.In the scheme, the channel probability was modeled by the master node as a matrix and it was segmented, and those sub-matrices were encoded into redundant ones.Then, all the sub-matrices were offloaded to worker nodes to perform parallel FHT and IFHT, and the results were sent back to the master node for the final decoding.By embedding redundant information, the proposed scheme resolved the straggling problem, improving the efficiency, and accelerating the entire decoding process.Comparisons with other coded matrix multiplication schemes, the proposed scheme provides lower encoding complexity, higher numerical accuracy in decoding recovery, and maintains an efficient butterfly operation, effectively reducing the computational complexity of worker nodes.The time comparison and decoding performance analysis reveal that the proposed scheme achieves up to approximately 3.8 times acceleration compared to the traditional single-node FHT scheme, significantly enhances the FHT-QSPA decoding efficiency without affecting the decoding performance.

Key words: non-binary LDPC code decoding, coded distributed computing, fast Hadamard transform

中图分类号:

TN911

刘锐, 黎勇. 基于编码分布式快速哈达玛变换的多元LDPC码译码算法研究[J]. 通信学报, 2023, 44(10): 23-33.

Rui LIU, Yong LI. Study on coded distributed fast Hadamard transform based non-binary LDPC code decoding algorithm[J]. Journal on Communications, 2023, 44(10): 23-33.

图/表 12

表1

校验节点更新过程的各计算步骤复杂度"

公式	GF(⊗)	GF(÷)	$R (\times)$	$R (+)$
式(1)	—	$O (2^{r} \times N)$	—	—
式(2)	—	—	—	$O (r \times 2^{r} \times N)$
式(3)	—	—	$O (2^{r} \times N)$	$O (r \times 2^{r} \times N)$
式(4)	$O (2^{r} \times N)$	—	—	—

表1

表2

图1

图2

表3

编码分布式FHT方案计算复杂度"

计算环节	$R (\times)$	$R (+)$
单节点FHT	—	$O (r \times 2^{r} \times N)$
编码环节	$O ((n - k) \times 2^{r} \times N)$	$O ((n - k) \times (k - 1) \times 2^{r} \times \frac{N}{k})$
译码环节	$O (n_{s} \times (k - n_{u}) \times 2^{r} \times \frac{N}{k})$	$O (n_{s} \times (k - 1) \times 2^{r} \times \frac{N}{k})$
从节点FHT	—	$O (r \times 2^{r} \times \frac{N}{k})$

表3

表4

图3

图4

图5

图6

图7

表5

参考文献 20

[1]	DAVEY M C , MACKAY D . Low-density parity check codes over GF(q)[C]// Proceedings of IEEE Communications Letters. Piscataway:IEEE Press, 2002: 165-167.
[2]	PENG R H , CHEN R R . Design of nonbinary quasi-cyclic LDPC cycle codes[C]// Proceedings of 2007 IEEE Information Theory Workshop. Piscataway:IEEE Press, 2007: 13-18.
[3]	SONG H X , CRUZ J R . Reduced-complexity decoding of q-ary LDPC codes for magnetic recording[J]. IEEE Transactions on Magnetics, 2003,39(2): 1081-1087.
[4]	RONG B , JIANG T , LI X M ,et al. Combine LDPC codes over GF(q) with q-ary modulations for bandwidth efficient transmission[J]. IEEE Transactions on Broadcasting, 2008,54(1): 78-84.
[5]	LI Y , WANG L , CHEN J B . The design and simulation of q-ary LDPC codes based on the PEG algorithm[C]// Proceedings of 14th IST Mobile and Wireless Communications Summit. Piscataway:IEEE Press, 2005: 1-5.
[6]	SAVIN V . Min-Max decoding for non binary LDPC codes[C]// Proceedings of 2008 IEEE International Symposium on Information Theory. Piscataway:IEEE Press, 2008: 960-964.
[7]	WANG C L , CHEN X H , LI Z W ,et al. A simplified min-sum decoding algorithm for non-binary LDPC codes[J]. IEEE Transactions on Communications, 2013,61(1): 24-32.
[8]	DECLERCQ D , FOSSORIER M . Decoding algorithms for nonbinary LDPC codes over GF(q)[J]. IEEE Transactions on Communications, 2007,55(4): 633-643.
[9]	FERRAZ O , SUBRAMANIYAN S , CHINTHALA R ,et al. A survey on high-throughput non-binary LDPC decoders:ASIC,FPGA,and GPU architectures[J]. IEEE Communications Surveys ＆ Tutorials, 2021,24(1): 524-556.
[10]	LEE K , LAM M , PEDARSANI R ,et al. Speeding up distributed machine learning using codes[J]. IEEE Transactions on Information Theory, 2018,64(3): 1514-1529.
[11]	YU Q , MADDAH-ALI M , AVESTIMEHR S . Polynomial codes:an optimal design for high-dimensional coded matrix multiplication[C]// Proceedings of the 31st International Conference on Neural Information Processing Systems. New York:ACM Press, 2017: 4406-4416.
[12]	FAHIM M , CADAMBE V R . Numerically stable polynomially coded computing[J]. IEEE Transactions on Information Theory, 2021,67(5): 2758-2785.
[13]	JEONG H , YANG Y Q , GROVER P . Systematic matrix multiplication codes[C]// Proceedings of 2019 IEEE International Symposium on Information Theory (ISIT). Piscataway:IEEE Press, 2019: 1-5.
[14]	DAS A B , RAMAMOORTHY A . Coded sparse matrix computation schemes that leverage partial stragglers[J]. IEEE Transactions on Information Theory, 2022,68(6): 4156-4181.
[15]	WANG S , LIU J , SHROFF N . Coded sparse matrix multiplication[J]. arXiv Preprint,arXiv:1802.03430, 2018.
[16]	PRAKASH S , DHAKAL S , AKDENIZ M R ,et al. Coded computing for low-latency federated learning over wireless edge networks[J]. IEEE Journal on Selected Areas in Communications, 2021,39(1): 233-250.
[17]	ZHOU B N , XIE J F , WANG B Q . Dynamic coded distributed convolution for UAV-based networked airborne computing[C]// Proceedings of 2022 International Conference on Unmanned Aircraft Systems (ICUAS). Piscataway:IEEE Press, 2022: 955-961.
[18]	MACWILLIAMS F J , SLOANE N J A . The theory of error-correcting codes[M]. North Holland: North Holland Publishing Co., 1977.
[19]	中国卫星导航办公室. 北斗系统空间信号接口控制文件 B1C（1.0版）[R]. 2017.
	China Satallite Navigation Office. BeiDou navigation satellite system signal in space interface control document B1C (version 1.0)[R]. 2017.
[20]	中国卫星导航办公室. 北斗系统空间信号接口控制文件 B2a（1.0版）[R]. 2017.
	China Satallite Navigation Office. BeiDou navigation satellite system signal in space interface control document B2a (version 1.0)[R]. 2017.

码长	GF(16)	GF(32)	GF(64)	GF(128)	GF(256)
200	82.91%	88.46%	91.89%	93.25%	93.91%
400	83.25%	88.59%	91.77%	93.48%	93.90%
800	83.99%	88.59%	91.79%	93.49%	93.90%
1 600	83.17%	88.43%	91.78%	93.19%	93.62%
2 000	83.98%	88.37%	91.66%	93.27%	93.92%

方案	n=5	n=10	n=20
多项式码方案	4.77×10^-2	6.06	1.52×10⁵
正交多项式码方案	1.99×10^-15	5.44×10^-15	6.42×10^-13
本文方案	3.93×10^-16	2.84×10^-16	7.95×10^-16

环节	FHT-QSPA/ms	编码分布式FHT-QSPA/ms
FHT	97.1	26.0
IFHT	97.5	26.1