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

doi:10.19665/j.issn1001-2400.2020.06.004

Abstract

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

CLC Number:

TN911.22

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

Figures/Tables 2

References 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)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 2

References 15

Related Articles 15

Metrics

Comments

Recommended 10

[1]	HE Yaping,HE Yucheng,ZHOU Lin. Permutation codesable to correct stable and unstable burst erasure errors [J]. Journal of Xidian University, 2021, 48(3): 49-55.
[2]	MA Guochen,JIAO Xiaopeng,MU Jianjun,HAN Hui,GUO Junjun. Simple proof the generalized Helberg codes being capable of correcting insertion/deletion errors [J]. Journal of Xidian University, 2020, 47(6): 158-163.
[3]	ZHANG Lu,SUN Rong,LIU Jingwei. Cloned piggybacking framework for distributed storage [J]. Journal of Xidian University, 2020, 47(6): 139-147.
[4]	CAI Zihao,MU Liwei,ZHAN Li,LIU Qiang. Research on the reliability of LDPC convolutional codes in the underwater acoustic communication system [J]. Journal of Xidian University, 2020, 47(6): 84-90.
[5]	ZHANG Yamei,ZHOU Lin,CHEN Chen,CHEN Qiwang,HE Yucheng. Sliding window decoding of the spatially coupled LDPC code Over Rayleigh fading channels [J]. Journal of Xidian University, 2020, 47(6): 78-83.
[6]	SONG Jiawei,ZHENG Huijuan,TONG Sheng. Method for designing CRC-Polar codes to improve minimum distances [J]. Journal of Xidian University, 2020, 47(6): 72-77.
[7]	ZHANG Meng,LI Zhuo,XING Lijuan. Weighted sum codes-aided SCL decoding of polar codes [J]. Journal of Xidian University, 2020, 47(6): 66-71.
[8]	NIU Kai,XU Wenjun,ZHANG Ping. Polar coded non-orthogonal multiple access to 6G wireless systems [J]. Journal of Xidian University, 2020, 47(6): 5-12.
[9]	ZHANG Yamei,ZHOU Lin,CHEN Chen,GUO Rongxin,HE Yucheng. Sliding window decoding algorithm for spatially coupled LDPC codes with a variable window [J]. Journal of Xidian University, 2020, 47(3): 128-134.
[10]	ZHANG Ying,WEI Minfeng,WANG Shihui,TAO Leiyan,CAO Jian,ZHANG Xing. Aircraft reinforcement learning multi-mode control in orbit [J]. Journal of Xidian University, 2020, 47(2): 75-82.
[11]	SUN Yue,LI Beilei,LIANG Caihong,LI Ying. Design of serial connecting multiple spatially coupled LDPC codes for block-fading channels [J]. Journal of Xidian University, 2019, 46(2): 1-5.
[12]	MA Yanping;YANG Hongyong;MA Zhangchao;WANG Zengfeng. Proportional fair resource allocation in the relay enhanced cellular system [J]. J4, 2015, 42(3): 179-185.
[13]	SUN Jinhua;WANG Xuemei;WU Xiaojun. Joint pilot and iterative decoding carrier synchronization for the short burst transmission system [J]. J4, 2014, 41(1): 23-28+63.
[14]	LI Xiaotian;ZHANG Runsheng;LI Yanbin. Research on the recognition algorithm of Turbo codes on trellis termination [J]. J4, 2013, 40(4): 161-166.
[15]	ZHANG Chengchang;PENG Wanquan;WU Xiaobing. Construction and decoding of second-order magic square convolutional codes [J]. J4, 2013, 40(1): 155-161.