(35.175.212.130) 您好!臺灣時間:2021/05/15 09:48
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:蔡承恩
研究生(外文):Cheng-En Tsai
論文名稱:利用雜湊表解(73,37,13)平方剩餘碼
論文名稱(外文):Decoding of the (73,37,13) Quadratic Residue Code with Hash Table
指導教授:陳延華
指導教授(外文):Yan-Hua Chen
學位類別:碩士
校院名稱:義守大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2016
畢業學年度:104
語文別:中文
論文頁數:48
相關次數:
  • 被引用被引用:0
  • 點閱點閱:171
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
本論文主要針對 (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.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文
 
無相關期刊
 
無相關點閱論文