跳到主要內容

臺灣博碩士論文加值系統

(44.201.97.0) 您好!臺灣時間:2024/04/17 22:43
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:王晨屹
研究生(外文):Wang, Chen-Yi
論文名稱:循序解碼演算法於有限堆疊下之路徑移除策略
論文名稱(外文):Path Deletions for Finite Stack-Size Sequential-Type Decoding Algorithms
指導教授:陳伯寧
指導教授(外文):Chen, Po-Ning
學位類別:碩士
校院名稱:國立交通大學
系所名稱:電信工程系所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2009
畢業學年度:97
語文別:英文
論文頁數:94
中文關鍵詞:循序解碼有限堆疊路徑移除二階段解碼M演算法
外文關鍵詞:Sequential-Type DecodingFinite Stack-SizePath DeletionsTwo-Pass DecoderM-algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:162
  • 評分評分:
  • 下載下載:4
  • 收藏至我的研究室書目清單書目收藏:0
本篇碩士論文針對循序解碼演算法的特有實作限制進行研究,即路徑堆疊容量有限。在路徑堆疊容量有限的前提下,當路徑堆疊超過上限時的有效路徑移除策略對於系統效能甚至解碼複雜度相當重要。基於此一研究背景,我們論文針對即時輸出解碼結果模式下的循序解碼演算法提出了若干有效路徑移除策略。而當系統容許「離線」輸出解碼結果時 — 意即系統允許接收到所有接收向量值後才開始進行解碼 — 我們提出了二階段解碼結構為基礎的路徑移除策略。簡言之,我們提出於「反向階段」使用M演算法來估計啟發函數值(heuristics function)以作為「順向階段」解碼所用之解碼量度參數。由於M演算法可由硬體電路實現,因此我們論文中僅考慮順向階段的解碼複雜度。模擬結果顯示,我們所提出的兩階段路徑移除策略在順向階段的解碼複雜度不僅優於使用費諾測度的堆疊演算法,更低於Sikora與Costelo於2008年所提出的二階段超級碼(supercode)解碼器[1]。

[1] M. Sikora and D. J. Costello, Jr., “Supercode heuristics for tree search decoding,” in Proc. IEEE Inform. Theory Workshop, Porto, Portugal, pp. 411-415, May 2008.
In this thesis, we focus on a specific practical constraint on sequential-type decoding algorithms, namely, the finite stack size. Under such a finite-stack-size limitation, the path deletion policy that is effective when the stack exceeds its limit becomes essential in performance and decoding complexity. At this background, we proposed several path deletion schemes for sequential-type decoding algorithms that can produce decoding outputs in an on-the-fly or instantaneous fashion. When ``off-line'' decoding is allowed, where the decoding process starts after the reception of the entire received word, we proposed an alternative path deletion scheme based on a two-pass decoding structure. To be specific, the backward pass estimates the heuristic function in terms of the M-algorithm for use of the forward decoding search. As the M-algorithm can be hardware-implemented, only the computational complexity of the forward pass is accounted for. Simulations show that the computational complexity of the forward pass not only outperforms the stack algorithm with Fano metric but also is smaller than that of the two-pass supercode decoder proposed by Sikora and Costello in 2008 [1].

[1] M. Sikora and D. J. Costello, Jr., “Supercode heuristics for tree search decoding,” in Proc. IEEE Inform. Theory Workshop, Porto, Portugal, pp. 411-415, May 2008.
Abstract in Chinese i
Abstract in English ii
Acknowledgements iii
List of Tables vi
List of Figures vii

1 Introduction 1
2 Preliminaries 4
2.1 System Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Algorithm A and Algorithm A* . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.3 Supercode Heuristics of Sikora and Costello . . . . . . . . . . . . . . . . . . 7
3 Path Deletion Schemes for Limited Stack-Size Sequential-Type Decoding
Algorithm 9
3.1 Path Deletion Based on ML Path Metric . . . . . . . . . . . . . . . . . . . . 9
3.2 Path Deletion Based on Path Levels . . . . . . . . . . . . . . . . . . . . . . . 10
3.3 Path Deletion Based on Fano Metric . . . . . . . . . . . . . . . . . . . . . . 11
3.4 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
4 A Novel Two-Pass Sequential-type Decoding Algorithm 13
ii
4.1 Heuristics Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.2 M-algorithm-Based Heuristics Estimate . . . . . . . . . . . . . . . . . . . . . 15
5 Simulation Results 18
5.1 The Path Deletion Schemes in Chapter 3 . . . . . . . . . . . . . . . . . . . . 18
5.2 The Two-Pass Sequential-Type Decoding Algorithm in Chapter 4 . . . . . . 35
6 Concluding Remark and Future work 92
References 93
[1] J. B. Anderson and S. Mohan, "Sequential coding algorithms: A survey and cost analysis," IEEE Trans. Commun., vol. COM-32, pp. 169-176, February 1984.

[2] P. A. Bengough and S. J. Simmons,"Sorting-based VLSI architectures for the M-algorithm and T-algorithm trellis decoders," IEEE Trans. Commun., vol. 43(2/3/4),
pp. 514-522, April 1995.

[3] R. Fano, "A heuristic discussion of probabilistic decoding," IEEE Trans. Inform. Theory, vol. IT-9, no. 2, pp. 64-73, April 1963.

[4] 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, February 2002.

[5] F. Jelinek, "A fast sequential decoding algorithm using a stack," IBM J. Res. Develop., vol. 13, pp. 675-685, November 1969.

[6] J. L. Massey, "Variable-length codes and the Fano metric," IEEE Trans. Inform. Theory, vol. 18, no. 1, pp. 196-198, 1972.

[7] N. J. Nilsson, Principle of Artificial Intelligence. Palo Alto, CA: Tioga Publishing Co., 1980.

[8] S. L. Shieh, P.-N. Chen, Y. S. Han,"Reduction of computational complexity and sufficient stack size of the MLSDA by early elimination," in IEEE International Symposium
on Information Theory, Nice, France, pp. 1671-1675, June 2007.

[9] M. Sikora and D. J. Costello, Jr., "Supercode heuristics for tree search decoding," in Proc. IEEE Inform. Theory Workshop, Porto, Portugal, pp. 411-415, May 2008.

[10] S. J. Simmons, "A bitonic-sorter based VLSI implementation of the M-algorithm," in IEEE Pacific Rim Conference on Communications, Computer ans Signal Processing, pp. 337-340, June 1989.

[11] K. Zigangirov, "Some sequential decoding procedures," Probl. Peredach. Inform., vol. 2, no. 4, pp. 13-15, 1966.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top