(3.235.108.188) 您好!臺灣時間:2021/03/07 20:37
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:張家輔
研究生(外文):Chia-Fu Chang
論文名稱:預估冗餘位元資訊在A *解碼演算法的應用
論文名稱(外文):Advanced information of parity bits for the A * DecodingAlgorithm
指導教授:林茂昭
口試委員:鐘嘉德楊谷章陸曉峯陳伯寧蘇賜麟蘇育德趙啟超呂忠津
口試日期:2014-06-13
學位類別:博士
校院名稱:國立臺灣大學
系所名稱:電信工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2014
畢業學年度:102
語文別:英文
論文頁數:90
中文關鍵詞:解碼線性區塊碼A&;#8727;演算法軟式區塊碼解碼
外文關鍵詞:decodinglinear block codeA&;#8727; algorithmsoft decoding of block codes
相關次數:
  • 被引用被引用:0
  • 點閱點閱:266
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
A*解碼演算法是一種樹狀搜尋解碼方式,可以有效率的針對短的線性區塊碼進行解碼,在本篇論文中,提出了數種改進的方法,無論A*解碼演算法以及本論文中提出的改進版本,都可以使用最大相似解碼,或是限制使用堆疊數目。

本篇論文的基本構想來自於,利用事先可取得的冗餘位元以及合併冗餘位元之資訊,可以減少樹狀解碼時,不必要之搜尋。對於需要多少資訊位元來決定冗餘位元或合併冗餘位元的值,本研究完成理論上的分析與數值上的檢驗,本研究提出三種使用冗餘位元之資訊的方法改良A*演算法。將A*解碼演算法用於二次剩餘碼和BCH碼的軟式解碼模擬,模擬結果顯示,使用事先冗餘位元之資訊之解碼相對於沒有使用冗餘位元之資訊之解碼,可以有效地減少樹狀圖中搜尋所需的分支數目。

The A* algorithm for decoding linear block codes is known to be an efficient tree-search method for decoding short linear block codes. The A* decoding algorithm and its modified methods can be applied to either maximum-likelihood (ML) soft-decision decoding or stack limited cases of linear block codes. In this thesis, several modified methods of A* decoding algorithm are proposed.

The basic concept of this thesis is to employ the early acquired information of some parity bits or some combined parity bits to reduce the needed search tree edges. Analysis for the number of required information bits for obtaining the parity bits is provided. In addition, three versions of the modified A* algorithm which take advantage of the advanced information of parity bits and combined parity bits are proposed. The computer simulation results of several quadratic residue codes and BCH codes are provided. Simulation results show that there is significant advantage in reducing the number of search tree edges in each proposed version as compared with two existing A* algorithms which do not consider the early information of parity bits or combined parity bits.

口試委員審定書 i
致謝iii
中文摘要v
Abstract vii
Contents ix
List of Figures xiii
List of Tables xvii
1 Introduction . . . 1
2 Some Basics . . . 7
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Tree Search with Reliability Ordering : A&;#8727; Decoding Algorithm I . . . 10
2.3 Tree Search with Heuristic Information Based on Code Minimum Hamming
Distance : A&;#8727; Decoding Algorithm II . . . . . . . . . . . . . . . 16
2.4 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3 Early Information of Parity Bits for the A&;#8727; Decoding Algorithm . . . 21
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2 Tree Search with Early Information of Parity Bits : A&;#8727; Decoding Algorithm
III . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.3 The Number of Message Bits for Determining Some Parity Bits . . . . 25
3.4 Tree Search with More Information of Parity Bits : A&;#8727; Decoding Algorithm
IV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.5 Non-Maximum-Likelihood Cases . . . . . . . . . . . . . . . . . . . . 33
3.5.1 Stack Limitation . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.5.2 Search Path Limitation . . . . . . . . . . . . . . . . . . . . . . 41
3.5.3 Search Tree Edges Limitation . . . . . . . . . . . . . . . . . . 43
3.6 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.7 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4 Early Information of Combined Parity Bits for the A&;#8727; Decoding Algorithm . . . 53
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2 Combined Parity Bits . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.2.1 Procedure of Searching Combined Parity Bits . . . . . . . . . . 55
4.2.2 Metric of Combined Parity Bits . . . . . . . . . . . . . . . . . 56
4.2.3 Most Reliable Combined Pairs . . . . . . . . . . . . . . . . . . 58
4.3 Tree Search with Information of Combined Parity Bits : A&;#8727; Decoding
Algorithm V . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.4 Simulation Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
4.5 Worst Case Scenarios . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
4.5.1 Search Path Limitation . . . . . . . . . . . . . . . . . . . . . . 78
4.6 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80
5 Conclusions and Future Research . . . 81
Bibliography . . . 85


[1] Berrou C. and Glavieux A., “Near optimum error correcting coding and decoding: Turbo codes,” IEEE Trans. Commun., vol. 44, pp. 1261–1271, Oct. 1996.
[2] R. G. Gallager, “Low-density parity-check codes,” IRE Trans. on Inf. Theory, vol. 8, pp. 21–28, Jan. 1962.
[3] D. J. C. Mackay and R. M. Neal, “Near shannon limit performance of low density parity check codes,” Electron. Lett., vol. 32, pp. 1645–1646, Aug. 1996.
[4] H. Jin, A. Khandekar and R. J. McEliece, “Irregular repeat-accumulate codes,”in Proceedings of the 2nd International Symposium on Turbo Codes and Related Topics, (Seoul, South Korea), Sep 2000.
[5] F. J. W. MacWilliams, N.J.A., The Theory of Error-Correcting Codes. North Holland, Amsterdan: Sloane, 1977.
[6] Wen-Ku Su, Pei-Yu Shih, Tsung-Ching Lin and Trieu-Kien Truong, “A method to reduce the decoding complexity of the binary (89, 45, 17) quadratic residue code,”Advanced Communication Technology, 2009.(ICACT 2009), vol. 02, pp. 1035–1037, Feb. 2009.
[7] Tsung-Ching Lin, Wen-Ku Su, Pei-Yu Shih and Trieu-Kien Truong, “Fast Algebraic Decoding of the (89, 45, 17) Quadratic Residue Code,” Communications Letters, IEEE., vol. 15, issue: 2, pp. 226–228, Feb. 2011.
[8] Yaotsu Chang, Trieu-Kien Truong, Reed Irving S., Cheng, H.Y. and Lee, C.-D., “Algebraic decoding of (71, 36, 11), (79, 40, 15), and (97, 49, 15) quadratic residue codes ,” IEEE Trans. Commun., vol. 51, issue: 9, pp. 1463–1473, 2003.
[9] Hung-Peng Lee and Hsin-Chiu Chang, “Improvement on decoding of the (71, 36, 11) quadratic residue code,” Computer Science &; Education (ICCSE), pp. 324–329, Aug. 2011.
[10] Esmaeili, M., Alampour A. and Gulliver, T.A., “Decoding Binary Linear Block Codes Using Local Search,” IEEE Trans. Commun., vol. 61, issue: 6, pp. 2138–2145, June 2013.
[11] M. Bossert, Channel Coding for Telecommunications. Sons, Chichester: John Wiley, 1999.
[12] J. L. Massey, Threshold Decoding. Cambridge: MIT Press, 1963.
[13] G.D. Forney, Jr., “Generalized minimum distance decoding,” IEEE Trans. Inf. Theory, vol. 12, no. 2, pp. 125–131, Apr. 1966.
[14] D. Chase, “A class of algorithms for decoding block codes with channel measurement information,” IEEE Trans. Inf. Theory, vol. 18, no. 1, pp. 170–182, Dec. 1972.
[15] M. P. C. Fossorier and S. Lin, “Soft-decision decoding of linear block codes based on ordered statistics,” IEEE Trans. Inf. Theory, vol. 44, pp. 1379–1396, 1995.
[16] L. Ekroot and S. Dolinar, “A* decoding of block codes,” IEEE Trans. Commun., vol. 44, pp. 1052–1056, 1996.
[17] Laura Ekroot and Sam Dolinar, “Maximum-likelihood soft-decision decoding of block codes using the A* algorithm,” Jet Propulsion Laboratory, Pasadena, CA, TDA Progress Report 42-117 Jan-Mar., pp. 129–144, May 1994.
[18] Y.S. Han, C. R. P. Hartmann, and Chih-Chieh Chen, “Efficient priority-first search maximum-likelihood soft-decision decoding of linear block codes,” IEEE Trans. Inf. Theory, vol. 39, pp. 1514–1523, 1993.
[19] Y. S. Han, C. R. P. Hartmann, and K. G. Mehrotra, “Decoding linear block codes using a priority-first search:performance analysis and suboptimal version,” IEEE Trans. Inf. Theory, vol. 44, pp. 1233–1246, May 1998.
[20] N. J. Nilsson, Principle of Artificial Intelligence. Palo Alto, CA: Tioga Publishing Co., 1980.
[21] Mao-Chao Lin and Chia-Fu Chang, “An improved A* algorithm for decoding linear block codes,” in Proc. of 2010 IEEE Wireless Communications and Networking Conference, (Sydney, Australia), pp. 1–6, April 2010.
[22] Tien-Yu Lin, Chia-Fu Chang and Mao-Chao Lin, “A* decoding for a block coded scheme with interblock memory,” in Proc. of 2012 IEEE Wireless Communications and Networking Conference, (Shanghai, China), pp. 163–167, April 2012.
[23] Chia-Fu Chang, Tien-Yu Lin, Chao-Liang Tai, and Mao-Chao Lin, “Advanced information of parity bits for decoding short linear block codes using the A* algorithm,”IEEE Trans. on Communications, vol. 61, no. 4, pp. 1201–1211, April 2013.
[24] Chia-Fu Chang, Tien-Yu Lin and Mao-Chao Lin, “Tree-search decoding with path constraints for linear block codes,” in Proc. of 2014 IEEE Wireless Communications and Networking Conference, (Istanbul, Turkey), April 2014.
[25] Chao-Liang Tai, “Design and implementation of a soft linear block code decoder with a modified A* algorithm,” Graduate Institute of Communication Engeineering National Taiwan University doctoral thesis, 2010.
[26] C. L. Ho and Hsu-Hung Yang, “MP&;A* Mixed Decoding Algorithm for LDPC Codes,” in Fifth Annual Conference on Communication Networks and Services Research, (Fredericton, New Brunswick, Canada), pp. 239–244, May 2007.
[27] Ruey-Yi Wei and Yen-Ming Chen, “Further results on noncoherent block-coded MPSK,” IEEE Trans. Commun., vol. 56, issue: 10, pp. 1616–1625, Oct. 2008.
[28] J. Jiang, K. R. Narayanan, “Iterative soft-input soft-output decoding of reedsolomon codes by adapting the parity-check matrix,” IEEE Trans. Inf. Theory, vol. 52, issue. 8, pp. 3746–3756, 2006.
[29] A. Kothiyal and O. Y. Takeshita, “A comparison of adaptive belief propagation and the best graph algorithm for the decoding of block codes,” ISIT 2005. Proceedings. International Symposium on Information Theory, vol. COM-12, pp. 724–728, 2005.
[30] S. Lin and D. J. Costello, Error Control Coding, 2nd ed. Upper Saddle River, NJ, USA: Prentice-Hall, Inc., 2004.
[31] B. G. Dorsch, “A decoding algorithm for binary block codes and j-ary output channels,”IEEE Trans. Inf. Theory, vol. 20, no. 3, pp. 391–394, May 1974.
[32] D. Gazelle and J. Snyders, “Reliability-based code-search algorithms for maximum-likelihood decoding of block codes,” IEEE Trans. Inf. Theory, vol. 43, no. 61, pp. 239–249, Nov. 1997.
[33] M. P. C. Fossorier and S. Lin, “Computationally efficient soft-decision decoding of linear block codes based on ordered statistics,” IEEE Trans. Inf. Theory, vol. 42, no. 3, pp. 738–750, Dec. 1996.
[34] A. Kothiyal, O. Y. Takeshita, W. Jin, and M. Fossorier, “Iterative reliability-based decoding of linear block codes with adaptive belief propagation,” IEEE Commun. Lett, vol. 9, issue. 12, pp. 1067–1069, Dec. 2005.
[35] S. Tong, D. Lin, A. Kavcic, B. Bai, and L. Ping, “On short forward error-correcting codes for wireless communication systems,” in Proc. IEEE Computer Communications and Networks, (Honolulu, HI), pp. 391–396, Aug 2007.
[36] J. H. van Lint and F. J. MacWilliams, “Generalized quadratic residue codes,” IEEE Trans. Inf. Theory, vol. 24, no. 6, pp. 730–737, Nov. 1978.
[37] V. K. Wei, “Generalized Hamming weights for linear codes,” IEEE Trans. Inf. Theory, vol. 37, no. 5, pp. 1412–1418, 1991.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔