二元迴旋碼之接近最大機率循序搜尋解碼演算法

Abstract

在本篇論文中，我們重新探索[17]裡的最大機率循序搜尋解碼演算法(Maximum-Likelihood Sequential-Search Algorithm)。藉由更換傳統的費諾計量值(Fano metric)為基於華格納規則(Wagner rule)推導出的計量值，[17]裡的循序搜尋解碼演算法可以保證產生最大機率效能，於是被命名為最大機率循序搜尋解碼演算法。藉由模擬結果顯示出此演算法比維特比演算法(Viterbi algorithm)擁有明顯較低的軟體解碼複雜度。 一個循序搜尋解碼演算法共通的問題是當訊雜比(signal-to-noise ratio)低於對應於切斷率(cut-off rate)的訊雜比時，平均解碼複雜度和所需的堆疊(stack)大小會隨著訊息長度快速增加。此共通問題限制了循序搜尋解碼演算法使用於訊息長度較長的迴旋碼。為了降低此問題的影響，本文中建議在搜尋過程中如果堆疊裡的最高路徑(top path)的層級(level)比搜尋過程最遠的展開層級還少超過△以上，則將此最高路徑直接丟棄。我們將此動作稱為提早淘汰(early elimination)。我們接著分析使得解碼的效能衰退忽略不計所需要的最小△值。由我們的理論分析結果顯示所需的△值大小對編碼率1/2的迴旋碼在加成性高斯白雜訊(additive white Gaussian noise)通道及二元對稱(binary symmetric)通道大約分別為3倍及2.2倍的限制長度(constraint length)。對編碼率1/3的迴旋碼，所需的△值大小更分別下降到2倍及1.2倍的限制長度。這些理論分析結果也幾乎與模擬的結果相吻合。 由於只需要很小的△值即可達到接近最大機率的效能，經過此修改的循序搜尋解碼演算法消除了大量的計算量及記憶體需求。這使得此修改過後的循序搜尋解碼演算法適合於需要低軟體複雜度卻又要求接近最大機率解碼效能的應用。我們更進一步使用Berry-Esseen不等式分析修改前及修改後的循序搜尋解碼演算法複雜度。理論分析得到的平均複雜度上界及模擬得到的平均複雜度結果都顯示此修改將大幅降低解碼的複雜度，並且使得修改過後循序搜尋解碼演算法的每單位訊息長度所需之解碼複雜度在中到高訊雜比狀況下幾乎與迴旋碼的計憶深度(memory order)無關。

In this work, the maximum-likelihood sequential-search decoding algorithm proposed in [17] is revisited. By replacing the conventional Fano metric with one that is derived based on the Wagner rule, the sequential-search decoding in [17] guarantees the maximum-likelihood (ML) performance, and was therefore named the maximum-likelihood sequential decoding algorithm (MLSDA). It was then concluded by simulations that when the MLSDA is operated over the convolutional code trellis, its software computational complexity is in general considerably smaller than that of the Viterbi algorithm. A common problem on sequential-type decoding is that at the signal-to-noise ratio (SNR) below the one corresponding to the cut off rate, the average decoding complexity and the required stack size grow rapidly with the information length [25]. This problem, to some extent, prevents the practical use of sequential-type decoding from codes with long information sequence. In order to alleviate the problem in the MLSDA, we propose to directly eliminate the top path whose end node is ∆-trellis-level prior to the farthest one among all nodes that have been expanded thus far by the sequential search, which we termed the early elimination. We then analyze the early-elimination window that results in negligible performance degradation for the MLSDA. Our asymptotic-based analytical result indicates that the required early elimination window for negligible performance degradation is around three times (resp. 2.2-fold) of the constraint length for rate one-half convolutional codes under additive white Gaussian (resp. binary symmetric) channel. For rate one-third convolutional codes, the required early-elimination window reduces to two times (resp. 1.2-fold) of the constraint length for the same channel. The theoretical level thresholds almost coincide with the simulation results. As a consequence of small early elimination window required for near maximum-likelihood performance, the MLSDA with early elimination modification rules out considerable computational burdens, as well as memory requirement, by directly eliminating a big number of the top paths. This makes the MLSDA with early elimination suitable for applications that dictate a low-complexity software implementation with near maximum-likelihood performance. The upper bounds of decoding complexity of both the MLSDAs with and without early elimination are subsequently derived by utilizing the Berry-Esseen inequality. Both the upper bound and the simulated complexity indicate that the average decoding complexity per output bit for the MLSDA with early elimination is almost irrelevant to the memory order, as well as the message length, for medium to high SNRs.