一種(41, 21, 9)平方剩余碼的快速代數(shù)譯碼算法

吳怡; 羅春蘭; 張新球; 林瀟; 徐哲鑫

doi:10.11999/JEIT170983

一種(41, 21, 9)平方剩余碼的快速代數(shù)譯碼算法

doi: 10.11999/JEIT170983

福建師范大學(xué)福建省光電傳感應(yīng)用工程技術(shù)研究中心 ??福州 ??350007

基金項(xiàng)目: 國家自然科學(xué)基金(61571128, 61701118)

詳細(xì)信息

作者簡介:
吳怡：女，1970 年生，教授、博士生導(dǎo)師，研究方向?yàn)闊o線自組織網(wǎng)、信道編碼

羅春蘭：女，1994 年生，碩士生，研究方向?yàn)樾诺谰幋a

張新球：男，1954 年生，博士，研究方向?yàn)椴铄e(cuò)控制編碼

林瀟：男，1981 年生，助理研究員，研究方向?yàn)闊o線網(wǎng)絡(luò)通信

徐哲鑫：男，1985 年生，副教授，研究方向?yàn)闊o線自組織網(wǎng)絡(luò)

通訊作者:
吳怡　 wuyi@fjnu.edu.cn

中圖分類號: TN911.22
計(jì)量
- 文章訪問數(shù): 1666
- HTML全文瀏覽量: 602
- PDF下載量: 49
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2017-10-23
- 修回日期: 2018-04-23
- 網(wǎng)絡(luò)出版日期: 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)

摘要

摘要: 為了降低譯碼時(shí)的計(jì)算復(fù)雜度以及減少譯碼時(shí)間，該文通過對牛頓恒等式進(jìn)行推導(dǎo)得到了(41, 21, 9) QR碼不需要計(jì)算未知校驗(yàn)子就可求得錯(cuò)誤位置多項(xiàng)式系數(shù)的代數(shù)譯碼算法，同時(shí)也針對改善部分客觀地給出了計(jì)算復(fù)雜度的理論分析。此外，為了進(jìn)一步降低譯碼時(shí)間，提出判定接收碼字中出現(xiàn)不同錯(cuò)誤個(gè)數(shù)的更簡化的判斷條件。仿真結(jié)果表明該文提出算法在不降低Lin算法所達(dá)到的譯碼性能的前提下，降低了譯碼時(shí)間。
- 平方剩余碼 /
- 代數(shù)譯碼 /
- 牛頓恒等式 /
- 未知校驗(yàn)子 /
- 錯(cuò)誤位置多項(xiàng)式
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 兩種譯碼算法計(jì)算L₄(z)復(fù)雜度的比較

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

下載: 導(dǎo)出CSV

表 2 兩種譯碼算法平均譯碼時(shí)間(μs)

錯(cuò)誤個(gè)數(shù)	錯(cuò)誤模式總數(shù)	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

下載: 導(dǎo)出CSV

參考文獻(xiàn)(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碼的快速代數(shù)譯碼算法[J]. 重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版), 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.

相關(guān)文章

施引文獻(xiàn)

資源附件(0)

訪問統(tǒng)計(jì)