臺灣博碩士論文加值系統

本篇碩士論文針對循序解碼演算法的特有實作限制進行研究，即路徑堆疊容量有限。在路徑堆疊容量有限的前提下，當路徑堆疊超過上限時的有效路徑移除策略對於系統效能甚至解碼複雜度相當重要。基於此一研究背景，我們論文針對即時輸出解碼結果模式下的循序解碼演算法提出了若干有效路徑移除策略。而當系統容許「離線」輸出解碼結果時 — 意即系統允許接收到所有接收向量值後才開始進行解碼 — 我們提出了二階段解碼結構為基礎的路徑移除策略。簡言之，我們提出於「反向階段」使用Ｍ演算法來估計啟發函數值(heuristics function)以作為「順向階段」解碼所用之解碼量度參數。由於Ｍ演算法可由硬體電路實現，因此我們論文中僅考慮順向階段的解碼複雜度。模擬結果顯示，我們所提出的兩階段路徑移除策略在順向階段的解碼複雜度不僅優於使用費諾測度的堆疊演算法，更低於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.