利用雜湊表解(73,37,13)平方剩餘碼

Decoding of the (73,37,13) Quadratic Residue Code with Hash Table

蔡承恩(Cheng-En Tsai)

指導教授 ： 陳延華

義守大學/電機資訊學院/資訊工程學系/碩士(2016年)

摘要

本論文主要針對 (73, 37, 13) 二元平方剩餘碼 (Quadric Residue Code, QR code) 利用雜湊方法進行解碼改良，此QR碼之生成多項式 (Generator polynomial) 與 (23, 12, 11)、(41, 21, 9)、(47, 24, 11)、(71, 36, 11) QR碼之生成多項式具有不可分解的性質不同。因此二元平方剩餘碼之生成多項式具有可分解的特性，有限域元素數量無法一對一對映出糾錯樣式 (Error Pattern)，換句話說症狀子元素數量不足，無法一對一映對出錯誤樣式。本論文將使用分圓陪集 (Cyclotomic Coset) 的特性對已知症狀子進行連接，產生的組合症狀子與錯誤樣式具有一對一對映性質，再利用雜湊搜尋法進行解碼，效能預期比利用二元搜尋解碼方法約快2倍的解碼速度，實現方法非常適合用在硬體環境受限制的嵌入式系統中。

關鍵字

none

並列摘要

An efficient decoding of the (73, 37, 13) quadratic residue (QR) codes utilizing hashing search to find error patterns was presented in this study. The key idea behind the proposed decoding method is theoretically based on the existence of a one-to-one mapping between primary known syndromes in connection with the cyclotomic coset properties and correctable error patterns that is different only used signal primary known syndrome the (23, 12, 7), (41, 21, 9), (47, 24, 11) and (71,36, 11) QR codes. Compared with the binary search time approach, one of the advantages of utilizing this method presented in this study is that the hashing search time can be reduced by a factor of two. This method would help reduce the binary search time for finding error patterns when decoding the (73, 36, 11) QR code. Ultimately, the proposed decoding algorithm for QR codes can be made regular, simple, and suitable for software implementations.

並列關鍵字

none

參考文獻

[5] Y. H. Chen, T. K. Truong, Y. Chang, C. D. Lee, and S. H. Chen,“Algebraic decoding of quadratic residue codes using Berlekamp-Massey algorithm,” J. Inf. Sci. Eng., vol. 23, no. 1, pp.127-145, 2007.

[1] P. K. Meher,“Systolic and Non-Systolic Scalable Modular Designs of Finite Field Multipliers for Reed–Solomon Codec ,” IEEE Trans. Very Large Scale Integr. VLSI Syst, vol. 17, no. 6, pp. 747-757, 2009.

[2] J. L. Imaña, J. M. Sánchez, and F. Tirado,“Bit-parallel finite field multipliers for irreducible trinomials ,” IEEE Trans. Computers, vol. 55, no. 5, pp. 520–533, 2006.

[4] J. L. Massey,“Shift-register synthesis and BCH decoding,” IEEE Trans. Inf. Theory, vol. 15, no. 1, pp. 122–127, 1969.

[6] Y. Li, P. Zhang, L. Wang, T. K. Truong,“On Decoding of the (89, 45, 17) Quadratic Residue Code,” IEEE Trans. Commun, vol. 63, no. 2, 578-579, 2015.