臺灣博碩士論文加值系統

在渦輪碼(turbo code)[1] 發展史上，疊代式解碼器(iterative decoder)為其核心所在，它能提供逼近Shannon理論之解碼效能。在疊代式解碼器中，一般常使用軟式輸出(soft output)BCJR[2] 演算法來獲得最佳的錯誤更正效能，但其計算複雜度會隨著格狀(trellis)圖上的節點個數增加而呈指數成長，軟式輸出堆疊(stack)演算法(簡稱S-SA)可降低此解碼器之計算複雜度。本論文以MAPSDA (Maximum A Posteriori soft-decision Sequential Decoding Algorithm)[3] 為基礎，提出另一種軟式輸出循序解碼演算法(簡稱S-MAPSDA)並探討其疊代式解碼效能。模擬結果顯示，相較於S-SA，S-MAPSDA不僅在解碼效能上有所提升且其計算複雜度亦顯著地降低需多。

The recent proposal of “turbo codes”, with their astonishing performance close to the theoretical Shannon capacity limits, has once again shown the great potential of coding schemes formed by two or more codes working in a concurrent way. The core of the iterative decoding structure is a soft-input soft-output (SISO) a posteriori probability (APP) module. Usually, the optimal performance can be achieved by using the Bahl-Cocke-
Jelinek-Raviv (BCJR) algorithm. However, the decoding complexity will become quite expensive due to the enormous number of trellis nodes. In order to reduce the decoding complexity, low-complexity but sub-optimal tree-based sequential decoding algorithms, such as soft-output stack algorithm, were proposed. In this thesis, based on a code trellis rather on a code tree, we first propose another one soft-output sequential decoding algorithm, so called Soft-output Maximum A Posteriori Sequential Decoding Algorithm; S-MAPSDA. Next, the proposed S-MAPSDA is applied to an iterative decoding scheme for decoding serially concatenated variable length code and convolutional code. Simulation results show that the proposed iterative decoding scheme outperforms the iterative decoding scheme using soft-output stack algorithm (S-SA), in terms of performance and complexity.

摘要 II
ABSTRACT III
目錄 V
圖片目錄 VII
表格目錄 VIII
第一章 緒論 1
1.1 前言 1
1.2 研究動機 1
1.3 論文架構 2
第二章 文獻探討 4
2.1 通訊系統架構 5
2.2 可逆式變動長度碼 9
2.3 交錯器 11
2.4 遞迴系統式迴旋碼 12
2.5 PUNCTURED CODE 14
2.6 格狀圖 15
2.6.1 迴旋碼之格狀圖 15
2.6.2 變動長度碼之格狀圖 17
2.7 硬式輸出解碼演算法 18
2.7.1 堆疊演算法 18
2.7.2 Viterbi解碼演算法 21
2.7.3 MLSDA 24
2.8 產生軟式輸出之演算法 28
2.8.1 傳統BCJR演算法 28
2.8.2 BCJR演算法應用於變動長度碼 30
2.8.3 軟式輸出堆疊演算法 32
2.9 疊代解碼演算法 34
第三章 疊代式整合型訊源/通道循序解碼演算法 36
3.1 設定可允許移動視窗之MAPSDA 36
3.2 S-MAPSDA 40
3.3 使用S-MAPSDA之疊代解碼演算法 42
第四章 實驗結果與分析 44
第五章 結論與未來研究方向 68
參考文獻 69

[1] Berrou, A Glavieux, and P Thitimajshima, “Near Shannon limit error-correcting coding and decoding: Turbo-codes,” Proc. 1993 IEEE Int. Conf. on Communications Geneva, Switzerland, pp. 1064-1070, 1993
[2] L. R. Bahl, J. Cocke, F. Jelinek, and J. Raviv, “Optimal decoding of linear codes for minimizing symbol error rate,” IEEE Trans. Inform. Theory, vol. IT-20, pp. 284-287, 1974.
[3] Y.-M. Huang, C.-F. Lo, and Y. S. Han, “Bit- and trellis- based soft-decision sequential decoding for variable-length error correcting codes,” in Proc. IEEE Asia-Pacific Conference on Communications, Akihabara, Tokyo Japan, Oct. 14-16, 2008.
[4] A. J. Viterbi, “Error bounds for convolutional codes and an asymptotically optimum decoding algorithm,” IEEE Trans. Inform. Theory, vol. IT-13, pp. 260-269, Apr. 1967.
[5] R. M. Fano, “A Heuristic Discussion of Probabilistic decoding,” IEEE Trans. Info. Theory, vol. 9, pp. 64-73, Apr 1963.
[6] F. Jelinek, “Fast Sequential Decoding Algorithm Using a Stack,” IBM J. Res. Develop., pp. 675-685, Nov. 1969.
[7] N. Champaneria, T. K. Moon, and J. H. Gunther, “A soft-output stack algorithm,” in Proceedings of IEEE 40th Asilomar Conference on Signals, Systems and Computers (ACSSC ’06), pp. 2195–2199, Pacific Grove, Calif, USA, October-November 2006..
[8] L Guivarch, JC Carlach, P Siohan, “Joint source-channel soft decoding of Huffman codes with turbo-codes,” Proceedings of the Conference on Data Compression, 2000.
[9] Y. Takishima, M. Wada, and H. Murakami “Reversible variable length codes” IEEE Transactions on Communications, 1995
[10] B. Vucetic and J. Yuan, Turbo codes: Principles and Applications. Kluwer Academic Publishers, 2000.
[11] Y. S. Han, P.-N. Chen, and H.-B. Wu, “A maximum-likelihood soft-decision sequential decoding algorithm for binary convolutional codes,” IEEE Trans. Commun., vol. 50, no. 2, pp. 173-178, Feb. 2002.
[12] M. Jeanne, J. C. Carlach, P. Siohan, and L. Guivarch, “Source and joint source- channel decoding of variable length codes,” in Proc. Int. Conf. Commun., vol. 2, New York, NY, Apr. 2002, pp. 768-772.
[13] Y.-M. Huang, Y. S. Han, and T.-Y. Wu, “Soft-decision priori-first decoding algorithms for variable-length error-correcting codes,” IEEE Communications Letters., Aug. 2008
[14] R Bauer, J Hagenauer, “On variable length codes for iterative source/channel decoding,” IEEE Data Compression Conference., 2001.
[15] Moon, T.K. Error correction coding: mathematical methods and algorithms, Wiley-Interscience, June 2005.
[16] J Hagenauer, O DFVLR, “Rate-compatible punctured convolutional codes (RCPC codes) and their applications,” IEEE Transactions on Communications, 1988.
[17] C Weiß, S Riedel, J Hagenauer, “ Sequential decoding using a priori information,“ Electronics Letters, 1996.
[18] Y Yang, W Yi, Y Chen, J Liu, “Iterative joint source channel decoding in wireless sensor networks,” 2008 International Conference On Communication, Circuits and Systems (ICCCAS 2008), pp.109-113, Xiamen University, Fujian Province, China, May 2008.