平行式最佳區塊碼解碼演算法

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：82

、訪客IP：18.118.16.91

姓名

趙明德(Ming-te Chao) 查詢紙本館藏

畢業系所

通訊工程學系在職專班

論文名稱

平行式最佳區塊碼解碼演算法
(On the Parallel Optimum Block Code Decoding Algorithm)

相關論文

★ Branch and Bound 演算法在全光網路包含串音局限的限制條件之最佳化規劃效能分析	★ 數位廣播之視訊系統架構與信號估測
★ 粒子群優化演算法應用於電信業解決方案選商及專案排程之優化	★ 結合PSO及K-Means聚類分析演算法的圖像分割
★ 利用粒子群優化演算法改善分群演算法在訊號分群上之應用	★ 應用模糊聚類與粒子演算法之色彩分群研究
★ 粒子群優化演算法應用於企業更新數據網路採購之優化	★ 粒子群演算法應用於無線區域網路產品硬體開發成本優化
★ 粒子群演算法應用企業伺服器負載平衡之省電優化	★ 粒子群優化演算法應用於瓦斯業微電腦瓦斯表自動讀表之優化
★ 近場通訊之智慧倉儲管理	★ 在Android 平台上實現NFC 室內定位
★ 適用於訊號傳輸暨無線電力傳輸之設計	★ 結合PSO及圖像品質評估演算法識別頻譜訊號
★ 粒子群優化與二維Otsu演算法於影像二元化閥值選取研究	★ 利用A*解碼法應用到線性區塊碼的最大可能性解碼之研究

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

以A*及分支界限演算法為解碼原理所發展出的平行式最佳區塊碼解碼演算法是一種人工智慧樹狀平行搜尋法，用來解決在圖形中的最短路徑，以評估分支界限搜尋法B&B中二元決策樹之每一個節點的度量，除了可以有效率地計算各個節點之度量外，更可以在搜尋的早期階段停止展開大量不適用的解，可在短時間內找到最可能的字碼，達到增加解碼效率的目的。 A*演算法已被應用到線性區塊碼的完全解碼。此篇論文主要描述以A*及分支界限演算法為基礎原理，加以平行式地將其應用到二元線性區塊碼的最大可能性解碼。模擬主要是利用一個線性碼，送出一組具0,1訊號的二元符號,發射端則使用BPSK調變二元正反訊號。它被送經一個AWGN通道，收到的訊號則是符號，這些是具連續性的軟符號；接收機先利用硬式決策估計被傳送bit信號±1，若接收訊經硬式決策判定為錯誤之字碼，則進行A*分支界限演算法之平行式最佳區塊碼解碼找出最大可能的原始訊號。

摘要(英)

By A*-branch and bound algorithm, parallel optimum block code decoding is an artificial intelligent searching method, which is used to solve the shortest path within a graph with branch and bound approach to determine the metric of each vertex in a tree. Apart from efficiently calculating the metric of every vertex, it can even prune uncompromising vertexes in the early searching phase so as to find the maximum likelihood codeword in a short period of time and achieve the goal for increasing decoding efficiency. A*-branch and bound algorithm has been employed to the fully decoding of linear block code. This thesis mainly describes the fundamental principle of A*-branch and bound algorithm parallel decoding strategy and application for the maximum likelihood decoding of binary linear block code. The simulation herein mainly used a linear code to send out 0 or 1 binary symbol. The transmitter employs BPSK to modulate binary antipodal signals; which is transmitted via a AWGN channel. The receiving signal is symbol which is consecutive soft symbol. Then the receiver firstly used hard limiter to evaluate the transmitted symbol ±1. If the receiving signals were determined as corruptive codeword, the parallel optimum block code decoding for A* branch and bound algorithm parallel decoding strategy will be employed to find the maximum likelihood original transmitted signal.

關鍵字(中)

★ 解碼演算法
★ 平行式最佳區塊碼

關鍵字(英)

★ Decoding Algorithm
★ Parallel Optimum Block Code

論文目次

中文摘要 IV
Abstract V
目錄 VII
圖目錄 IX
表目錄 XI
第一章緒論 1
1. 平行式最佳區塊碼解碼演算法 1
2. 內容與論文設計動機 1
第二章線性區塊碼 3
1. 線性區塊碼的定義 3
2. 同位檢查方程式 4
3. 同位檢查矩陣 5
4. 生成矩陣 5
5. 漢明權重與漢明距離 7
第三章 BCH碼之解碼原理 9
1. BCH碼之簡介 9
2. BCH碼之定義 9
3. 二元BCH碼之特性 11
4. BCH碼的解碼演算法 12
5. 徵狀的計算 12
6. 徵狀與錯誤模式 12
7. 錯誤位置多項式 13
8. 間的關係式 13
9. 彼得森的直接解(Peterson’s Direct-Solution) 14
第四章解碼演算法基本原理 16
1. 最大可能性解碼 17
2. 距離權重函數 18
3. 一致性單調條件 19
4. 訣竅評估函數 23
5. 演算法圖形表示 25
6. 最短路徑搜尋 26
7. 演算法與演算法之比較 28
8. 未排序訊號之解碼 29
9. 排序訊號之解碼 32
10. 系統化重排生成矩陣所衍生的問題 35
第五章平行式最佳區塊碼解碼演算法之實現 37
1. 無清單式單一根節點平行式解碼 39
2. 清單式多根節點平行式解碼 41
3. 無清單式單一根節點與清單式多根節平行式解碼之比較 43
4. 生成矩陣的建立 43
5. 系統化生成矩陣 44
6. 產生訊息序列 45
7. 編碼 46
8. BPSK調變 46
9. AWGN通道模擬 47
10. 硬決策解碼 48
11. 接收訊號排序 49
12. 系統化排序之生成矩陣 50
13. 分支界限演算法平行式解碼 53
14. 運用二元搜尋法操作節點序列 55
15. 競賽問題之deadlock現象 58
第六章平行式最佳區塊碼解碼演算法模擬結果 59
1. 清單序列式解碼 60
2. 無清單式單一根節點平行式解碼 62
3. 清單式多根節點平行式解碼 64
4. 序列和平行式解碼法解碼速度模擬結果比較 66
第七章總結 67
參考文獻 68

參考文獻

[1] C.L.Ho, Soft Decoding of A Block Codeword by Algorithm, National Central University, Chung-Li, Taiwan
[2] Laura Ekroot and Sam Dolinar, Decoding of Block Codes, IEEE Transactions on Communications, Vol. 44, No. 9. September 1996
[3] Ying, Heuristic Decoding Method, 17630twdl.doc, 6/2/2006
[4] San Ling and Chaoping Xing, Coding Theory A First Course, Cambridge University Press, 2005
[5] Robin R. Murphy, Introduction to AI Robtics, The MIT Press TJ211.M865 2000
[6] N.J. Nilsson, Principles of Artificial Intelligence, Palo Alto, CA: Tioga Publishing Co., 1980
[7] Judith L. Gersting, Mathematical Structures for Computer Science, Fifth Edition, Freeman
[8] S.H. Yang, On the Hybrid Decoding Method for LDPC Code by Using the Message Passing and the Algorithms, National Central University, Chung-Li, Taiwan
[9] 廖榮貴，資料結構與演算法，文魁資訊
[10] 馮玉珉，Communication System Principles,文京

指導教授

賀嘉律(C-L Ho)

審核日期

2007-12-2

推文