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

On the Parallel Optimum Block Code Decoding Algorithm

趙明德(Ming-te Chao)

指導教授 ： 賀嘉律

國立中央大學/資訊電機學院/通訊工程研究所碩士在職專班/碩士(2007年)

摘要

以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

參考文獻

[2] Laura Ekroot and Sam Dolinar, Decoding of Block Codes, IEEE Transactions on Communications, Vol. 44, No. 9. September 1996

[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

[10] 馮玉珉，Communication System Principles,文京

[1] C.L.Ho, Soft Decoding of A Block Codeword by Algorithm, National Central University, Chung-Li, Taiwan