二进制准循环码的加法傅里叶变换编码算法

doi:10.19665/j.issn1001-2400.2020.06.004

西安电子科技大学学报 ›› 2020, Vol. 47 ›› Issue (6): 21-29.doi: 10.19665/j.issn1001-2400.2020.06.004

• 面对B5G/6G的信息传输与接入技术进展 • 上一篇下一篇

二进制准循环码的加法傅里叶变换编码算法

李润洲(),黄勤()

北京航空航天大学电子信息工程学院,北京 100191

收稿日期:2020-06-30 出版日期:2020-12-20 发布日期:2021-01-06
通讯作者: 黄勤
作者简介:李润洲(1996-),男,北京航空航天大学硕士研究生,E-mail: lirunzhou@buaa.edu.cn
基金资助:
国家自然科学基金(61941106);中国科协青年人才托举工程(2017QNRC001)

Additive Fourier transform encoding algorithm for binary quasi-cyclic codes

LI Runzhou(),HUANG Qin()

School of Electronic and Information Engineering, Beihang University, Beijing 100191, China

Received:2020-06-30 Online:2020-12-20 Published:2021-01-06
Contact: Qin HUANG

摘要/Abstract

摘要：

为了提高二进制准循环码编码效率,提出一种基于加法傅里叶变换的频域编码算法。利用向量与循环矩阵的乘法和向量循环卷积的等价性,通过有限域傅里叶变换加速循环卷积运算,实现快速编码。针对选择的加法傅里叶变换即Lin-Chung-Han变换工具,在其卷积定理基础上,结合狭义傅里叶变换的频域编码算法,证明了该变换也可以用于频域编码。为了减少二进制准循环码的编码复杂度,利用有限域傅里叶变换的共轭约束条件,提出了基于该变换的二进制准循环码编码算法。分析了给出的快速编码算法的复杂度,并与其他算法进行了对比。提出的算法在码长较长时具有很低的复杂度,而且其中的变换结构对称,在应用时具有一定的优势。

关键词: 准循环码, 有限域傅里叶变换, 卷积定理, 频域编码

Abstract:

To improve the encoding efficiency of binary quasi-cyclic codes, this paper proposes a frequency domain encoding algorithm based on the additive Fourier transform. Based on the equivalence of multiplication of vectors and cyclic matrices and cyclic convolution, finite field Fourier transform is used to accelerate the cyclic convolution operation, thereby realizing fast encoding. The Lin-Chung-Han transform is selected as a tool with its convolution theorem explained. Based on the frequency domain encoding algorithm with the normal Fourier transform, it is proved that the Lin-Chung-Han transform can also be used in frequency domain encoding. To reduce the encoding complexity of binary quasi-cyclic codes, the conjugate constraint of finite field Fourier transform is used to propose the encoding algorithm for binary quasi-cyclic codes. The complexity of the given fast encoding algorithm is analyzed and compared with other algorithms. The algorithm proposed in this paper has a low complexity when the code length is long, and the transformation structure is symmetrical, which has a certain advantage in applications.

Key words: quasi-cyclic codes, finite field Fourier transform, convolution theorem, frequency domain encoding

中图分类号:

TN911.22

李润洲,黄勤. 二进制准循环码的加法傅里叶变换编码算法[J]. 西安电子科技大学学报, 2020, 47(6): 21-29.

LI Runzhou,HUANG Qin. Additive Fourier transform encoding algorithm for binary quasi-cyclic codes[J]. Journal of Xidian University, 2020, 47(6): 21-29.

图/表 2

参考文献 15

[1]	BLAHUT R E. Transform Techniques for Error Control Codes[J]. IBM Journal of Research and Development, 1979, 23(3): 299-315. doi: 10.1147/rd.233.0299
[2]	BLAHUT R E. Algebraic Codes for Data Transmission[M]. Cambridge: Cambridge University Press, 2003.
[3]	TANNER R M. Spectral Graphs for Quasi-cyclic LDPC Codes[C]// Proceedings of the 2001IEEE International Symposium on Information Theory. Piscataway: IEEE, 2001: 226.
[4]	ZHANG L, HUANG Q, LIN S, et al. Quasi-cyclic LDPC Codes: An Algebraic Construction, Rank Analysis, and Codes on Latin Squares[J]. IEEE Transactions on Communications, 2010, 58(11): 3126-3139. doi: 10.1109/TCOMM.2010.091710.090721
[5]	ZHANG L, HUANG Q, LIN S, et al. Quasi-Cyclic LDPC Codes on Latin Squares and the Ranks of Their Parity-check Matrices[C]// Proceedings of the 2010 Information Theory and Applications Workshop. Washington: IEEE Computer Society, 2010: 16-22.
[6]	TANG L, HUANG Q, WANG Z, et al. Low-complexity Encoding of Binary Quasi-cyclic Codes Based on Galois Fourier Transform[C]// Proceedings of the 2013 IEEE International Symposium on Information Theory. Piscataway: IEEE, 2013: 131-135.
[7]	HUANG Q, TANG L, HE S, et al. Low-complexity Encoding of Quasi-cyclic Codes Based on Galois Fourier Transform[J]. IEEE Transactions on Communications, 2014, 62(6): 1757-1767. doi: 10.1109/TCOMM.2014.2316174
[8]	LIN S J, CHUNG W H, HAN Y S. Novel Polynomial Basis and Its Application to Reed-solomon Erasure Codes[C]// Proceedings of the 2014 Annual IEEE Symposium on Foundations of Computer Science. Washington: IEEE Computer Society, 2014: 316-325.
[9]	LIN S J, AL-NAFFOURI T Y, HAN Y S, et al. Novel Polynomial Basis with Fast Fourier Transform and Its Application to Reed-Solomon Erasure Codes[J]. IEEE Transactions on Information Theory, 2016, 62(11): 6284-6299. doi: 10.1109/TIT.2016.2608892
[10]	LI R, HUANG Q, WANG Z. Encoding of Non-binary Quasi-cyclic Codes by Lin-Chung-Han Transform[C]// Proceedings of the 2018 IEEE Information Theory Workshop. Piscataway: IEEE, 2018: 8613313.
[11]	BAREISS E H. Numerical Solution of Linear Equations with Toeplitz and Vector Toeplitz Matrices[J]. Numerische Mathematik, 1969, 13(5): 404-424. doi: 10.1007/BF02163269
[12]	DIAO Q, HUANG Q, LIN S, et al. A Transform Approach for Computing the Ranks of Parity-check Matrices of Quasi-cyclic LDPC Codes[C]// Proceedings of the 2011 IEEE International Symposium on Information Theory. Piscataway: IEEE, 2011: 366-370.
[13]	DIAO Q, HUANG Q, LIN S, et al. A Matrix-theoretic Approach for Analyzing Quasi-cyclic Low-density Parity-check Codes[J]. IEEE Transactions on Information Theory, 2012, 58(6): 4030-4048. doi: 10.1109/TIT.2012.2184834
[14]	DIAO Q, HUANG Q, LIN S, et al. A Transform Approach for Analyzing and Constructing Quasi-cyclic Low-density Parity-check Codes[C]// Proceedings of the 2011 Information Theory and Applications Workshop. Washington: IEEE Computer Society, 2011: 15-22.
[15]	WU X, WANG Y, YAN Z. On Algorithms and Complexities of Cyclotomic Fast Fourier Transforms Over Arbitrary Finite Fields[J]. IEEE Transactions on Signal Processing, 2012, 60(3): 1149-1158. doi: 10.1109/TSP.2011.2178844

二进制准循环码的加法傅里叶变换编码算法

Additive Fourier transform encoding algorithm for binary quasi-cyclic codes

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 2

参考文献 15

相关文章 15

Metrics

本文评价

推荐阅读 10

[1]	何雅萍,贺玉成,周林. 纠正稳定和非稳定突发擦除错误的置换码[J]. 西安电子科技大学学报, 2021, 48(3): 49-55.
[2]	马国臣,焦晓鹏,慕建君,韩辉,郭军军. 广义Helberg码纠插入/删除错误的一个简单证明[J]. 西安电子科技大学学报, 2020, 47(6): 158-163.
[3]	张璐,孙蓉,刘景伟. 分布式存储中的克隆piggybacking框架[J]. 西安电子科技大学学报, 2020, 47(6): 139-147.
[4]	蔡子浩,穆丽伟,占利,刘强. LDPC卷积码在水声通信系统中的可靠性研究[J]. 西安电子科技大学学报, 2020, 47(6): 84-90.
[5]	张娅妹,周林,陈辰,陈启望,贺玉成. 瑞利衰落信道中SC-LDPC码滑窗译码算法[J]. 西安电子科技大学学报, 2020, 47(6): 78-83.
[6]	宋嘉伟,郑惠娟,童胜. 一种提升最小距离的CRC-Polar码设计方法[J]. 西安电子科技大学学报, 2020, 47(6): 72-77.
[7]	张萌,李卓,邢莉娟. 加权和码辅助的极化码SCL译码算法[J]. 西安电子科技大学学报, 2020, 47(6): 66-71.
[8]	牛凯,许文俊,张平. 面向6G的极化编码非正交多址接入[J]. 西安电子科技大学学报, 2020, 47(6): 5-12.
[9]	张娅妹,周林,陈辰,郭荣新,贺玉成. 窗口可变的空间耦合LDPC码滑窗译码算法[J]. 西安电子科技大学学报, 2020, 47(3): 128-134.
[10]	张英,韦闽峰,王世会,陶磊岩,曹健,张兴. 飞行器强化学习多模在轨控制[J]. 西安电子科技大学学报, 2020, 47(2): 75-82.
[11]	孙岳,李蓓蕾,梁彩虹,李颖. 块衰落信道下串联多链空间耦合LDPC码设计[J]. 西安电子科技大学学报, 2019, 46(2): 1-5.
[12]	马艳萍;杨洪勇;马彰超;王增锋. 中继增强蜂窝系统中的比例公平资源分配[J]. J4, 2015, 42(3): 179-185.
[13]	孙锦华;王雪梅;吴小钧. 短突发传输系统的联合导频和迭代译码载波同步[J]. J4, 2014, 41(1): 23-28+63.
[14]	李啸天;张润生;李艳斌. 归零Turbo码识别算法[J]. J4, 2013, 40(4): 161-166.
[15]	张承畅;彭万权;伍小兵. 二阶幻方卷积码的构造及译码[J]. J4, 2013, 40(1): 155-161.