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

Yi WU; Chunlan LUO; Xinqiu ZHANG; Xiao LIN; Zhexin XU

doi:10.11999/JEIT170983

Volume 40 Issue 8

Aug. 2018

Turn off MathJax

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2018 > 40(8): 1949-1955

Yi WU, Chunlan LUO, Xinqiu ZHANG, Xiao LIN, Zhexin XU. A Fast Algebraic Decoding of the (41, 21, 9) Quadratic Residue Code[J]. Journal of Electronics & Information Technology, 2018, 40(8): 1949-1955. doi: 10.11999/JEIT170983

Citation:

Yi WU, Chunlan LUO, Xinqiu ZHANG, Xiao LIN, Zhexin XU. A Fast Algebraic Decoding of the (41, 21, 9) Quadratic Residue Code[J]. Journal of Electronics & Information Technology, 2018, 40(8): 1949-1955. doi: 10.11999/JEIT170983

Citation:

PDF( 479 KB)

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

doi: 10.11999/JEIT170983

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)

Received Date: 2017-10-23
Rev Recd Date: 2018-04-23

Available Online: 2018-05-30

Publish Date: 2018-08-01

Abstract

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

FullText(HTML)

References(15)

References

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.

Relative Articles

Supplements(0)

Cited By

Proportional views