一种(41, 21, 9)平方剩余码的快速代数译码算法

吴怡; 罗春兰; 张新球; 林潇; 徐哲鑫

doi:10.11999/JEIT170983

一种(41, 21, 9)平方剩余码的快速代数译码算法

doi: 10.11999/JEIT170983

福建师范大学福建省光电传感应用工程技术研究中心福州 350007

基金项目: 国家自然科学基金(61571128, 61701118)

详细信息

作者简介:
吴怡：女，1970 年生，教授、博士生导师，研究方向为无线自组织网、信道编码

罗春兰：女，1994 年生，硕士生，研究方向为信道编码

张新球：男，1954 年生，博士，研究方向为差错控制编码

林潇：男，1981 年生，助理研究员，研究方向为无线网络通信

徐哲鑫：男，1985 年生，副教授，研究方向为无线自组织网络

通讯作者:
吴怡　 wuyi@fjnu.edu.cn

中图分类号: TN911.22
计量
- 文章访问数: 1650
- HTML全文浏览量: 590
- PDF下载量: 47
- 被引次数: 0
出版历程
- 收稿日期: 2017-10-23
- 修回日期: 2018-04-23
- 网络出版日期: 2018-05-30
- 刊出日期: 2018-08-01

A Fast Algebraic Decoding of the (41, 21, 9) Quadratic Residue Code

Fujian Provincial Engineering Technology Research Center of Photoelectric Sensing Application, Fujian Normal University, Fuzhou 350007, China

Funds: The National Natural Science Foundation of China (61571128, 61701118)

摘要

摘要: 为了降低译码时的计算复杂度以及减少译码时间，该文通过对牛顿恒等式进行推导得到了(41, 21, 9) QR码不需要计算未知校验子就可求得错误位置多项式系数的代数译码算法，同时也针对改善部分客观地给出了计算复杂度的理论分析。此外，为了进一步降低译码时间，提出判定接收码字中出现不同错误个数的更简化的判断条件。仿真结果表明该文提出算法在不降低Lin算法所达到的译码性能的前提下，降低了译码时间。
- 平方剩余码 /
- 代数译码 /
- 牛顿恒等式 /
- 未知校验子 /
- 错误位置多项式
Abstract: In order to reduce the computational complexity of computing unknown syndromes for the coefficients of the error-locator polynomial and reduce the decoding time when one is decoding, this paper proposed an algebraic decoding algorithm of (41, 21, 9) QR code without calculating the unknown syndromes by solving the Newtonian identity. Simultaneously, an objective theoretical analysis of the computational complexity is given for the part of improvement. Besides, this paper also puts forward the simplifying conditions to determine the number of errors in the received word, which in order to further reducing the decoding time. Simulation results show that the proposed algorithm reduces the decoding time with maintaining the same decoding performance of Lin’s algorithm.
- Quadratic residue code /
- Algebraic decoding /
- Newtonian identity /
- Unknown syndrome /
- Error-locator polynomial

HTML全文

图 1 两种译码算法的BER与FER性能曲线图

下载: 全尺寸图片幻灯片

表 1 两种译码算法计算L₄(z)复杂度的比较

算法	乘法	加法
Lin算法	361	128
本文算法	294	101
降低百分比(%)	18.56	21.09

下载: 导出CSV

表 2 两种译码算法平均译码时间(μs)

错误个数	错误模式总数	Lin算法	本文算法
1	41	24.20	3.94
2	820	142.62	52.79
3	10660	275.60	231.73
4	101270	562.01	477.78

下载: 导出CSV

参考文献(15)

PRANGR E. Cyclic error-correcting codes in two symbols, AFCRC-TN-57-103[R]. Cambridge, MA: AirForce Cambridge Research Center, 1957.

LEE Chongdao, CHANG Yaotsu, and CHANG Hohsuan. Unusual general error locator polynomial for the (23, 12, 7) golay code[J]. IEEE Communications Letters, 2010, 14(4): 339–341. DOI: 10.1109/LCOMM.2010.04.091969.

REED I S, TRUONG T K, CHEN Xuemin, et al. The algebraic decoding of the (41, 21, 9) quadratic residue code[J]. IEEE Transactions on Information Theory, 1992, 38(3): 974–986. DOI: 10.1109/18.135639.

CHEN Xuemin, REED I S, HELLESETH T, et al. Use of gröbner bases to decode binary cyclic codes up to the true minimum distance[J]. IEEE Transactions on Communication, 1994, 40(5): 1654–1661. DOI: 10.1109/18.333885.

CHIEN R. Cyclic decoding procedure for Bose-Chaudhuri-Hocquenghem codes[J]. IEEE Transactions on Information Theory, 1964, 10(4): 357–363. DOI: 10.1109/TIT.1964.1053699.

CHEN Yanhaw, HUANG Chingfu, and CHANG J. Decoding of binary quadratic residue codes with hash table[J]. IET Communications, 2016, 10(1): 122–130. DOI: 10.1049/iet-com.2015.0546.

LIN Tsungching, LEE Chongdao, CHEN Yanhaw, et al. Algebraic decoding of cyclic codes without error-locator polynomials[J]. IEEE Transactions on Communications, 2016, 64(7): 2719–2731. DOI: 10.1109/TCOMM.2016.2569078.

ZHANG Pengwei, LI Yong, CHANG Hsinchiu, et al. Fast decoding of the (47, 24, 11) quadratic residue code without determining the unknown syndromes[J]. IEEE Communications Letters, 2015, 19(8): 1279–1282. DOI: 10.1109/LCOMM.2015.2440263.

陈高明, 黎勇, 董灿, 等. 一种(71, 36, 11)QR码的快速代数译码算法[J]. 重庆邮电大学学报(自然科学版), 2015, 27(6): 781–785. DOI: 10.3979 /j.issn.1673-825X.2015.06.013.

CHEN Gaoming, LI Yong, DONG Can, et al. A fast algebraic decoding algorithm of the (71, 36, 11) quadratic residue code[J]. Journal of Chongqing University of Posts and Telecommunications (Natural Science Edition), 2015, 27(6): 781–785. DOI: 10.3979/j.issn. 1673-825X. 2015.06.013.

LIN Tsungching, CHANG Hsinchiu, LI Yong, et al. Algebraic decoding of the (71, 36, 11) quadratic residue code[J]. IET Communications, 2016, 10(6): 734–738. DOI: 10.1049/iet-com.2015.0159.

HUANG Chingfu and CHEN Yanhaw. Efficient software method for decoding of the (71, 36, 11) quadratic residue code[C]. Intelligent Information Hiding and Multimedia Signal Processing (IIH-MSP), Adelaide, Australia, 2015: 45–48.

LIN Tsungching, TRUONG T K, LEE Hungpeng, et al. Algebraic decoding of the (41, 21, 9) quadratic residue code[J]. Information Sciences, 2009, 179(19): 3451–3459. DOI: 10.1016/j.ins.2009.06.002.

FENG G and TZENG K. A new procedure for decoding cyclic and BCH codes up to actual minimum distance[J]. IEEE Transactions on Information Theory, 1994, 40(5): 1364–1374. DOI: 10.1109/18.333854.

MACWILLIMS F J and SLOANE N J A. The Theory of Error Correcting Codes[M]. New York: North Holland, 1977: 244–245.

WANG C C, TRUONG T K, SHAO H M, et al. VLSI architectures for computing multiplications and inverses in GF(2^m)[J]. IEEE Transactions on Computers, 1985, C-34(8):709–717. DOI: 10.1109/TC.1985.1676616.

施引文献

资源附件(0)

访问统计