Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41079
Title: | 使用螞蟻演算法之渦輪碼最大概度解碼的理論與效能分析 Theory and Performance of ML Decoding for Turbo Codes using Ant Colony Optimization |
Authors: | Kuan-Chi Chen 陳冠錡 |
Advisor: | 許大山(Da-Shan Shiu) |
Keyword: | 渦輪,碼,遞迴式解碼,最大概度,解碼,干擾式解碼,基因解碼演算法,螞蟻演算法,禮,物輔助演算法, turbo codes,iterative decoding,maximum likelihood decoding,perturbed decoding,genetic decoding algorithm,ant colony optimization,gift-assisted decoding algorithm, |
Publication Year : | 2008 |
Degree: | 碩士 |
Abstract: | 雖然渦輪碼使用最大概度解碼可以產生最低的封包錯誤率,但因為有效率的渦輪碼最大概度解碼器仍未被發明,所以渦輪碼使用最大概度解碼至今仍是件不可能的事情,在這篇論文中,我們提出一個新的解碼演算法去尋找渦輪碼最大概度解碼器的效能極限,這個演算法稱為螞蟻解碼演算法。
螞蟻解碼演算法的理論則結合了禮物輔助解碼演算法和螞蟻演算法。在螞蟻解碼演算法中,一個解答是一個禮物,費洛蒙是一個事前消息位元機率。螞蟻根據費洛蒙量搜尋解答。而傳統的渦輪解碼器被用來為每個解答評定個別的分數,經過許多循環的演化後,非常好的解答就會出現,而這些好的解答相對應到的是被解碼後的碼字,而這些碼字是非常好的且有可能是對的。 螞蟻解碼演算法在某些情況下可以是一個實際可行的解碼演算法,螞蟻解碼演算法同時也是一個多重輸出的解碼器。在我們認知下,螞蟻解碼演算法最重要的貢獻是可以利用它和最大概度解碼效能極限實驗技術來得到一個最大概度解碼的錯誤率最佳效能極限,而且是透過實驗模擬的方式得到。 從我們的實驗結果中可以知道在封包錯誤率等於1.5x10-4附近,我們提出的螞蟻解碼演算法已經可以達到最大概度解碼的效能,也可以確定這個錯誤率區間,針對WCDMA 規範的渦輪碼最大概度解碼器的效能僅比傳統遞迴式解碼器來得好一些。在消息區塊長2560 和5120 位元情況下,螞蟻解碼演算法優於傳統遞迴式解碼器0.08 到0.15 dB,優於基因解碼演算法[2]和干擾解碼演算法0.07 到0.08 dB。 Although yielding the lowest error probability, ML decoding of turbo codes has been considered unrealistic so far because efficient ML decoders have not been discovered. In this thesis, we propose the Ant Colony Decoding Optimization (ACDO) for turbo codes. ACDO combines the principles of gift-assisted decoding and ant colony optimization. In ACDO, a solution is a gift. The pheromone is the a priori information bit probability. Ants construct solutions based on the pheromone. A conventional decoder is used to give scores to these ant solutions. After iterations of evolution, good ant solutions that correspond to decoded codewords of very good likelihood emerge. ACDO can be used as a practical decoder for turbo codes in certain contexts. It is also a natural multiple-output decoder. The most important aspect of ACDO, in our opinion, is that one can utilize the ML bounding technique and ACDO to empirically determine a effective lower bound on the error probability with ML decoding. Our results show that, at a word error probability of 1.5*10^−4, ACDO achieves the performance of ML decoding. Using the ML bounding technique and ACDO, we establish that a ML decoder only slightly outperforms a MAP-based iterative decoder at this word error probability for the block size we used and the turbo code defined for WCDMA. Given information block sizes of 2560 and 5120 bits per block, ACDO outperforms conventional iterative MAP decoder by a gain of 0.08 to 0.15 dB and outperforms Genetic Decoding Algorithm (GDA) [2] and Perturbed Decoding Algorithm. (PA)decoder by a gain of 0.07 to 0.08 dB. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41079 |
Fulltext Rights: | 有償授權 |
Appears in Collections: | 電信工程學研究所 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-97-1.pdf Restricted Access | 1.78 MB | Adobe PDF |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.