利用雜湊表解(23,12,7)二元平方剩餘碼之硬體實現

本計畫主要針對 (23, 12, 7) 二元平方剩餘碼 (Quadric Residue Code, QR code) 利用雜湊搜尋法取代二元搜尋法進行解碼改良實現於硬體電路。藉由硬體特性雜湊表透過分組方式減少查表次數的方法實現於硬體電路，以提高解碼器搜尋速度，分成多階段平行雜湊表以加速得到錯誤索引值，減少遞迴使用次數，減少遞迴這技術主要是利用轉址方法。所以改為雜湊表方法建立，則記憶體的使用量會比原先直接使用症狀子大小方式建立更節省記憶體使用量，利於硬體實現。由於硬體具有平行運算的特性，相較於軟體一對一對映，更能有效的提升解碼的速度。

關鍵字

雜湊搜尋法；二元搜尋法；雜湊表

並列摘要

An efficient decoding of the (23, 12, 7) quadratic residue (QR) codes utilizing hashing search to find error patterns is 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 signal primary known syndromes properties and correctable error patterns. Compared with the binary search time approach, one of the advantages of utilizing this method presented in this study is that the hashing search table can be paralleled by VLSI design. This method would help reduce the hash table hardware for finding error patterns when decoding the (23, 12, 7) QR code. Ultimately, the proposed decoding algorithm for QR codes can be made regular, simple, and suitable for hardware implementations.

並列關鍵字

Quadric Residue Code ； Hash Table ； Syndrome ； Error pattern

參考文獻

[7] [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] 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.

[3] J. L. Carter, and M. N. Wegman,“Universal classes of hash functions,” J. Comput. Syst. Sci., vol. 18, no. 2, pp. 143-154, 1979.

[4] Kasami, T.: 'A decoding procedure for multiple-error-correcting cyclic codes', IEEE Trans. Inf. Theory, 1964, 10, (2), pp. 134–138

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

國際替代計量

利用雜湊表解(23,12,7)二元平方剩餘碼之硬體實現

全文下載

主題瀏覽