- 學位論文
使用雜湊表解二元平方剩餘碼
Decoding of Some Binary Quadratic Residue Codes with Hash Table
摘要
在電腦科學中，查表法 (LUT) 是基於一個簡單的陣列索引方法，利用預先計算好資料存成陣列，替代需要耗時電腦計算過程。所以節省運算處理的時間是非常顯著，因此從記憶體中檢索一個值，比採取複雜計算更為快速。在論文中，提出兩種型式建立出查表資料表單，並分析出哪種形式的雜湊搜尋法可以快速解二元平方剩餘碼 (QR碼)。第 3 章針對 (71, 36, 11) QR 碼建立快速解碼查表演算法，利用二元搜尋方法進行搜尋，並說明的解碼方法背後的關鍵理論，是基於單一已知症狀子與錯誤位址之間具有一對一映射關係的存在，再利用二元快速搜尋法找出症狀子所對應錯誤位址，達成具有即時除錯能力。第 4 章，提出使用雜湊搜尋法取代二元搜尋法，使得搜尋次數比二元搜尋法查詢次數約減少兩倍。因此在解(n、k、d)的QR碼時利用查詢症狀子對應出錯誤位置將有助於減少QR碼解碼時間。最後，第 5 章提出不同雜湊函數進行解碼運算，並對於 (23, 12, 7)、(41, 21, 9)、 (47, 24, 11) 與 (71, 36, 11) QR 碼進行分析與討論。所提出的方法結果顯示對(71, 36, 11) QR碼進行解碼效能比使用二元搜尋法(FLTD)更能快速查詢症狀子，約減少 45% 所耗時的查詢時間。因此Q碼利用雜湊搜尋演算法更能模組化與簡單化實現解碼器。
並列摘要
In computer science, Lookup-table (LUT)-based method is an array that replaces runtime computation with a simpler array indexing operation. The savings in terms of processing time can be significant, since retrieving a value from memory is often faster than undergoing an 'expensive' computation or input/output operation. In this dissertation, we present several new designs for table-based function evaluation and table-based error correcting coding. In Chapter 3, present an efficient table lookup algorithm for high-throughput decoding of the (71, 36, 11) quadratic residue (QR) code. The main ideas behind this decoding technique are based on one-to-one mapping between the syndromes “S1” and correctable error patterns. As compared with the binary lookup table method, the presented technique is faster than binary searching method for finding error pattern. In Chapter 4, an efficient decoding of quadratic residue codes utilizing hashing search to find error patterns is presented in this chapter. The key idea behind the proposed decoding method is theoretically based on the existence of a one-to-one mapping between the single primary known syndrome and correctable error patterns. This method would help reduce the binary search time for finding error patterns when decoding the (n, k, d) QR codes. Finally, Chapter 5, There are some analysis and discussion of experimental results for proposing two schemes for decoding of the (71, 36, 11) QR code using hash table which compared with the other decoding algorithms. Furthermore, it would reduce the decoding time by 45% using the fast lookup table decoding (FLTD) method to decode the (71, 36, 11) QR code. Ultimately, the proposed decoding of the (71, 36, 11) QR code with hash table can be made regular, simple, and suitable for software implementations.