循序解碼演算法於有限堆疊下之路徑移除策略

Abstract

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