臺灣博碩士論文加值系統

本論文主要針對 (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倍的解碼速度，實現方法非常適合用在硬體環境受限制的嵌入式系統中。

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.

摘要 I
目錄 III
圖目錄 IV
表目錄 V
第一章 緒論 1
1.1 前言 1
1.2 研究動機 2
第二章 研究背景 3
2.1 GALOIS FIELD 3
2.2 生成多項式 6
2.3 CYCLOTOMIC COSET(分圓陪集) 7
2.4 雜湊表(HASH TABLE) 8
2.5 二元搜尋法 9
第三章 利用雜湊表解碼方法與步驟 10
3.1 利用雜湊搜尋法於QR 碼 11
3.2 症狀子與錯誤樣式 12
3.3 HASH TABLE SIZE 選取 14
3.4 雜湊表建立格式 19
第四章 編解碼流程 22
4.1 雜湊表搜尋方式 22
4.2 注入錯誤 25
4.3 雜湊表解碼演算法 28
第五章 實驗結果分析 30
第六章 結論 33
參考文獻 34
附錄 35

[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.
[3]E. R. Berlekamp,“Algebraic decoding theory,” McGraw-Hill, New York, 1968, 1st edn.
[4]J. L. Massey,“Shift-register synthesis and BCH decoding,” IEEE Trans. Inf. Theory, vol. 15, no. 1, pp. 122–127, 1969.
[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.
[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.
[7]X. Chen, I. S. Reed, and T. K. Truong,“A performance comparison of the binary quadratic residue codes with the 1/2-rate convolutional codes,” IEEE Trans. Inf. Theory, vol. 40, no. 1, pp. 126-136, 1994.
[8]Y. H. Chen, T. K. Truong, C. H. Huang, and C. H. Chien,“A lookup table decoding of systematic (47, 24, 11) quadratic residue code,” Inf. Sci., vol. 179, no. 14, pp. 2470-2477, 2009.
[9]Y. H. Chen, C. H. Chien, C. H. Huang, T. K. Truong, and M. H. Jing,“Efficient decoding of systematic (23, 12, 7) and (41, 21, 9) quadratic residue codes,” J. Inf. Sci. Eng., vol. 26, no. 5, pp. 1831-1843, 2010.
[10]Y. H. Chen, and T. K. Truong,“Fast algorithm for decoding of systematic quadratic residue codes,” IET Commun., vol. 5, no. 10, pp. 1361-1367, 2011.
[11]M. L. Fredman, and J. Komlos, E. Szermeredi,“Storing a sparse table with O(1) worst case access time,” J. ACM, vol. 31, no. 3, pp. 538-544, 1984.
[12]G. H. Gonnet,“Handbook of algorithms and data structures,” Addision-Wesley, New York, 1984, 1st edn
[13]J. L. Carter, and M. N. Wegman,“Universal classes of hash functions,” J. Comput. Syst. Sci., vol. 18, no. 2, pp. 143-154, 1979.