請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41079
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 許大山(Da-Shan Shiu) | |
dc.contributor.author | Kuan-Chi Chen | en |
dc.contributor.author | 陳冠錡 | zh_TW |
dc.date.accessioned | 2021-06-14T17:15:38Z | - |
dc.date.available | 2008-07-30 | |
dc.date.copyright | 2008-07-30 | |
dc.date.issued | 2008 | |
dc.date.submitted | 2008-07-25 | |
dc.identifier.citation | [1] C. Berrou, A. Glavieux, and P. Thitimajshima, “Near Shannon limit errorcorrecting coding and decoding: turbo codes,” Proc. IEEE Int. Conf. Commun. '93,, pp. 1064-1070, May 1993.
[2] T. Hsueh and D. Shiu, “Theory and Performance of ML Decoding for Turbo Codes using Genetic Algorithm,” 18th IEEE International Symposium on Information Theory, June. 2007. [3] Shu Lin and Daniel J. Costello, Jr., Error Control Coding: Fundamentals and applications, Second Edition, Prentice Hall, Inc., Upper Saddle River, NJ, 2004. [4] K. Shih and D. Shiu, “Perturbed Decoding Algorithm for Concatenated Error Correcting and Detecting Codes System,” 17th IEEE Intl. Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC’06), Sept. 2006. [5] T. Stutzle and H.H. Hoos, “MAX-MIN Ant System,”Future Generation Computer Systems, vol. 16, no. 8, pp. 889-914, 2000. [6] M. Dorigo, G. Di Caro, and L.M. Gambardella, “Ant algorithms for discrete optimization,” Artificial Life, vol. 5, no. 2, pp. 137-172, 1999. [7] M. Dorigo, M. Birattari, and T. Stutzle, “Ant colony optimization,” IEEE Computational Intelligence Magazine. vol 1, issue 4, Nov. 2006. [8] Krishna R. Narayanan, Gordon L. Stuber, “List Decoding of Turbo Codes ,”IEEE Transactions on Comunications. vol. 56, no.6, June 1998. [9] Carl Fredrik Leanderson and Carl-Erik W. Sundberg, “The Max-Log List Algorithm (MLLA)XA List-Sequence Decoding Algorithm That Provides Soft-Symbol Output,” IEEE Transactions on Comunications. vol. 53, no.3, March 2005. [10] Carl Fredrik Leanderson and Carl-Erik W. Sundberg, “On List Sequence Turbo Decoding,” IEEE Transactions on Comunications. vol. 53, no.5, May 2005. [11] J. S. Sadowsky, “A Maximum Likelihood Decoding Algorithm for Turbo Codes,”in Proc. IEEE Global Telecommun. Conf., vol. 2, Dallas, TX, Nov 1997. [12] S. Benedetto and G. Montorsi, “Unveiling Turbo-Codes: Some Results on Parallel Concatenated Coding Schemes,” IEEE Transactions on Information Theory. vol. 43, no.2, pp. 409-428, March 1996. [13] D. Divsalar, S. Dolinar, R. J. McEliece, and F. Pollara, “Transfer Function Bounds on the Performance of Turbo Codes,” TDA Progress Report 42-122, April-June 1995, Jet Propulsion Laboratory, Pasadena, California, pp. 44-45. Auguest 15, 1995. [14] T. M. Duman and M. Salehi, “New performance bounds for turbo codes,” IEEE Trans. Commun. vol. 46, pp. 717-723, June 1998. [15] I. Sason and S. Shamai, “Improved Upper Bounds on the ML Decoding Error Probability of Parallel and Serial Concatenated Turbo Codes Via Their Ensemble Distance Spectrum,” IEEE Transactions on Information Theory. vol. 46, no. 1, pp. 24-47, January 2000. [16] Third Generation Partnership Project (3GPP), Technical Specification 25.212: Multiplexing and Channel Coding (Frequency Division Duplex Mode), ver. 6.8.0, June, 2006. [17] M. Eroz and A. R. Hammons Jr, “On the design of prunable interleavers for turbo codes,” Proc. IEEE 49th VTC, vol. 2, pp. 1669V1673, July 1999. [18] R. Shao, S. Lin, and M. Fossorier, “Two simple stopping criteria for turbo decoding,”IEEE Trans. Commun. vol. 47, no. , pp. 1117-1120, Aug. 1999. [19] J. Hagenauer, E. Offer, and L. Papke, “Iterative Decoding of Binary Block and Convolutional Codes,” IEEE Transactions on Information Theory. vol. 42, no. 2, pp. 429-445, March 1996. [20] M. Dorigo, V. Maniezzo, and A. Colorni, “positive feedback as a search strategy,”Diparti- mento di Elettronica, Politecnico di Milano, Italy, Tech. Rep. 91-016, 1991. [21] M. Dorigo, V. Maniezzo, and A. Colorni, “Ant System: Optimization by a colony of cooperating agents,” IEEE Transactions on Systems, Man, and Cybernetics part B, vol. 26, no. 1, pp. 29-41, 1996. [22] C. E. Shannon, “Probability of error for optimal codes in a Gaussian channel,”Bell. Syst. Tech. J., vol. 38, pp. 611-656, May 1959. [23] S. J. MacMullan and O. M. Collins, “A Comparison of Known Codes, Random Codes, and the Best Codes,” IEEE Trans. Inform. Theory. vol. 44, no.7, pp. 3009-3022, Nov. 1998. [24] D. Owen, “A survey of properties and applications of the concentral tdistribution,”Technometrics, vol. 10, pp. 445-478, 1968. [25] N. Johnson and B. Welch, “Applications of the nonconcentral t-distribution,”Biometrika, vol. 31, pp. 362, 1939. [26] H. Chen, “The random gift channel and its applications,” preliminary work, 2008. [27] Tsutsui, S, and Lichi Liu, “Solving quadratic assignment problems with the cunning ant system,” Evolutionary Computation, 2007, pp. 173-179. [28] Goldberg, D. E. and Richardson, J, “Genetic Algorithms with Sharing for Multimodal Function Optimization. Genetic Algorithms and Their Applications,”Proceedings of the Second International Conference on Genetic Algorithms(1987). pp. 41-49. [29] Hua Yuan, Yi Li, Wenhui Li, Kong Zhao, Duo Wang,and Rongqin Yi, “Combining Immune with Ant Colony Algorithm for Geometric Constraint Solving,”Knowledge Discovery and Data Mining, 2008, pp. 524-527. [30] R. Smith, S. Forrest, and A. S. Perelson, “Searching for diverse, cooperative populations with genetic algorithms,” Evolutionary Computation, vol. 1, no. 2, pp. 127-149. 1993. [31] Third Generation Partnership Project 2 (3GPP2), “cdma2000 high rate packet data air interface specification, Release B,” 3GPP2 C.S0024VB Version 2.0, Mar. 2007. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/41079 | - |
dc.description.abstract | 雖然渦輪碼使用最大概度解碼可以產生最低的封包錯誤率,但因為有效率的渦輪碼最大概度解碼器仍未被發明,所以渦輪碼使用最大概度解碼至今仍是件不可能的事情,在這篇論文中,我們提出一個新的解碼演算法去尋找渦輪碼最大概度解碼器的效能極限,這個演算法稱為螞蟻解碼演算法。
螞蟻解碼演算法的理論則結合了禮物輔助解碼演算法和螞蟻演算法。在螞蟻解碼演算法中,一個解答是一個禮物,費洛蒙是一個事前消息位元機率。螞蟻根據費洛蒙量搜尋解答。而傳統的渦輪解碼器被用來為每個解答評定個別的分數,經過許多循環的演化後,非常好的解答就會出現,而這些好的解答相對應到的是被解碼後的碼字,而這些碼字是非常好的且有可能是對的。 螞蟻解碼演算法在某些情況下可以是一個實際可行的解碼演算法,螞蟻解碼演算法同時也是一個多重輸出的解碼器。在我們認知下,螞蟻解碼演算法最重要的貢獻是可以利用它和最大概度解碼效能極限實驗技術來得到一個最大概度解碼的錯誤率最佳效能極限,而且是透過實驗模擬的方式得到。 從我們的實驗結果中可以知道在封包錯誤率等於1.5x10-4附近,我們提出的螞蟻解碼演算法已經可以達到最大概度解碼的效能,也可以確定這個錯誤率區間,針對WCDMA 規範的渦輪碼最大概度解碼器的效能僅比傳統遞迴式解碼器來得好一些。在消息區塊長2560 和5120 位元情況下,螞蟻解碼演算法優於傳統遞迴式解碼器0.08 到0.15 dB,優於基因解碼演算法[2]和干擾解碼演算法0.07 到0.08 dB。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-06-14T17:15:38Z (GMT). No. of bitstreams: 1 ntu-97-R95942027-1.pdf: 1825569 bytes, checksum: 6e61430e077ad66d2f4d6b512d07c9d7 (MD5) Previous issue date: 2008 | en |
dc.description.tableofcontents | 1 Introduction 1
1.1 Motivation.............................................2 1.2 History................................................3 1.3 Related works..........................................7 1.4 Contribution and organization..........................8 2 Background 10 2.1 Parallel concatenated convolutional codes.............10 2.2 Maximum-a posteriori (MAP) iterative decoding algorithm .....11 2.3 Perturbed decoding algorithm..........................12 2.4 ML bounding technique.................................14 2.5 Perturbed decoding algorithm for turbo codes..........18 2.6 Genetic decoding algorithm for turbo codes............20 2.7 Gift-assisted decoding algorithm......................22 2.8 Ant colony optimization...............................24 2.9 Sphere packing bound(SPB).............................27 3 Gift-assisted Decoding Algorithm 29 3.1 Gift-assisted decoding for turbo codes................29 3.2 Feasibility of gift-assisted decoding with random gift selection.....33 3.3 Gift selection based on a priori bit probability......35 4 Ant Colony Decoding Optimization 44 4.1 Ant colony decoding optimization for turbo codes......44 4.2 Diversity issues......................................46 4.3 ML bound using ACDO...................................47 4.4 Complexity aspects for ACDO...........................48 5 Simulation Results 50 5.1 Simulation setup......................................50 5.2 Parameters and procedures for ACDO....................50 5.3 Performance of ACDO...................................52 6 Conclusions 59 6.1 Conclusions...........................................59 6.2 Future works..........................................60 Bibliography 62 | |
dc.language.iso | en | |
dc.title | 使用螞蟻演算法之渦輪碼最大概度解碼的理論與效能分析 | zh_TW |
dc.title | Theory and Performance of ML Decoding for Turbo Codes using Ant Colony Optimization | en |
dc.type | Thesis | |
dc.date.schoolyear | 96-2 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 林茂昭(Mao-Chao Lin),葉丙成(Ping-Cheng Yeh),王忠炫(Chung-Hsuan Wang) | |
dc.subject.keyword | 渦輪,碼,遞迴式解碼,最大概度,解碼,干擾式解碼,基因解碼演算法,螞蟻演算法,禮,物輔助演算法, | zh_TW |
dc.subject.keyword | turbo codes,iterative decoding,maximum likelihood decoding,perturbed decoding,genetic decoding algorithm,ant colony optimization,gift-assisted decoding algorithm, | en |
dc.relation.page | 65 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2008-07-28 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 電信工程學研究所 | zh_TW |
顯示於系所單位: | 電信工程學研究所 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-97-1.pdf 目前未授權公開取用 | 1.78 MB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。