利用A*解碼法應用到線性區塊碼的最大可能性解碼之研究

The Study of Linear Block Codes of Maximum-Likelihood Decoding based on Improved

吳克良(Ke-liang Wu)

指導教授 ： 賀嘉律

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

摘要

通道編碼已經廣泛應用在各通訊系統，並克服通道雜訊，確保傳送過程中的訊息可以正確的被接收端所接收。這原理主要是在傳送前將訊息編碼，並加入多餘的通道錯誤復原資訊，最後轉換成傳送資訊，接收端用特定的解碼演算法進行更正與錯誤偵測。
A*解碼法是利用樹狀搜尋法，經常用來解圖形中的最短路徑，此解碼法評估各個目標與分支的度量，在搜尋過程中早期階段停止展開大量不適合的解，在短時間內找到最可能的解，以達到增加效率目的。A*解碼法目前已經被使用在線性區塊碼的最大相似解碼上，且減少了搜索路徑。在本篇論文中，我們利用最短路徑搜索中最常使用的A*解碼法做為參考且加以改良，並保留A*演碼法原本最短路徑的優點，並應用到二元線性區塊碼的最大可能性解碼，經過電腦模擬改良A*演碼法性能表現做比較與整理。

關鍵字

線性區塊碼 ； 樹狀搜尋法 ； A*解碼法

並列摘要

Channel coding has been applied to various communication systems extensively
to overcome the channel noise and ensure transmission of information can be
acceptedcorrectly. The information symbols are coded by adding redundancy for recovery from channel errors before transmission. The receiver uses specific decoding algorithm to proceed correction and error detection.
A* decoding algorithm is a tree search algorithm, which is used to find the shortest path within a graph with branch and bound approach to determine the metric of each vertex in a tree. This algorithm estimates metrics between target and each vertex so that it can prune irrelevant vertexes in the early searching phase so as to find the most likely answer in a short period of time and achieve the goal of increasing efficiency.A* decoding algorithm hasbeen used to implement maximum-likelihood decoding of linear blockcodes. Moreover, it reduces the searching edges. In this thesis, we use the shortest path search in the most commonly used A * decoding algorithm as a reference and to be improved, retain the advantages of the original shortest path A decoding algorithm, and applied to the maximum likelihood decoding of binary linear block codes, through computer simulation method improved A * decoding algorithm performance comparison.

並列關鍵字

linear block code ； soft decoding ； A* decoding algorithm

參考文獻

[1]C.E. Shannon, “A Mathematical Theory of Communication,” Bell System Technical Journal, vol. 27, pp. 379-423, 623-656, July, October, 1948.

[2] Thomas M. Cover, Joy A. Thomas, “Elements of Information Theory,” MA:John Wiley & Sons, pp. 210-211, 1991.

[3]Richard W. Hamming, “Error detecting and error correcting codes,” Bell System Technical Journal, vol. 26, no. 2, April, 1950.

[4]I. Chabini and S. Lan, “Adaptations of the A* algorithm for the computation of fastest paths in deterministic discrete-time dynamic networks,” IEEE Transactions

on Intelligent Transportation Systems, vol. 3, no. 1, pp.60-74, Mar. 2002.