限制樹狀結構搜尋不定長度錯誤更正前置碼 自由距離的高效演算法

Abstract

在這篇論文中，我們提出一個針對整合訊源-通道之不定長度錯誤更正前置碼(variable-length error correcting prefix code or VLECPC)計算自由距離(free distance)的新演算法，主要的發想是將碼字串接的序列對，建成樹狀結構，並經由樹狀結構找出最小漢米距離(Hamming distance)的等長序列對。我們運用不影響自由距離計算之特定條件，去掉非必要的樹狀分支，加快演算法的進行。而針對只有兩組碼字的VLECPC的特殊情況，我們證明在計算自由距離時，只需考慮特定個數的碼字串接序列即可決定自由距離，而特定個數可由兩碼長獲知。我們使用針對英文字母設計的VLECPC進行模擬，在位元距離(bitwise distance)的計算次數與執行時間上，我們的演算法皆比應用狄可斯特演算法(Dijkstra's algorithm)於成對距離圖(pairwise distance graph or PDG)搜尋自由距離的方法，有更好的表現。

In this paper, a new tree search algorithm for determining the free distance of variable-length error-correcting prefix code (VLECPC) is proposed. The idea is to structure all pairs of codeword-concatenation sequences as a tree, over which a pair of sequences that decide the free distance is located. Constraints that compromise no optimality in determining the free distance will be proven and applied to speed up the algorithm. In the particular case that only two codewords exist in a VLECPC, we show that all candidate equal-length codeword-concatenation sequence pairs that possibly decide the free distance can be explicitly listed, by which this quantity can be is straightforwardly obtained. In comparison with Dijkstra's algorithm operating over the pairwise distance graph (PDG) of the VLECPC for the 26 English alphabet, the number of bitwise distance computations required by our algorithm is considerably smaller and can be hundred times faster in terms of execution time.