基於搜尋演算法的不定長度錯誤更正前置碼之設計

Abstract

在這篇論文中，我們針對離散無記憶訊號源(discrete memoryless source)設計整合訊源-通道之不定長度錯誤更正前置碼(variable-length error correcting prefix code or VLECPC)。我們的研究成果包含：一、在給定自由距離(free distance)最小允許值的前提下，證明運用優先權搜尋演算法(priority first search algorithm)，於我們所新設計的搜尋樹結構中，可保證找到最低平均碼長的不定長度錯誤更正前置碼。二、為進一步降低解碼錯誤率，我們提出在所有可達最低平均碼長的不定長度錯誤更正前置碼中，可以使用錯誤率聯集上界(union bound)的主要項為依據，選取使主要項Bdfree最低的最低平均碼長之不定長度錯誤更正前置碼，獲取較佳的容錯能力。三、對於較大的自由距離最小允許值、或是較多的離散訊號源個數，前述所提的搜尋演算法因過於費時而不適用，因此在損失些微平均碼長的前提下，另提出簡化快速搜尋演算法。四、在解碼端，針對接收端另知不定長度碼的傳送個數的條件，設計了低複雜度的最大事後機率(maximum a posteriori)解碼演算法。模擬結果顯示，我們所提出的編碼演算法在平均碼長與效能上，皆優於現有文獻的方法。另外，與傳統的分散式訊源-通道編碼相比較，在相當的解碼複雜度下，我們所設計的整合式訊源-通道編解碼系統可達更低的傳輸錯誤率。

A joint source-channel coding problem that combines the efficient compression of discrete memoryless sources with their reliable communication over memoryless channels via binary variable-length error-correcting prefix codes (VLECPCs) is considered. Under a fixed free distance constraint, a priority-first search algorithm is devised for finding an optimal VLECPC with minimal average codeword length. Two variations of the priority-first-search-based code construction algorithm are also provided. The first one improves the resilience of the developed codes against channel noise by additionally considering a performance parameter Bdfree without sacrificing optimality in average codeword length. In the second variation, to accommodate a large free distance constraint as well as a large source alphabet such as the 26-symbol English data source, the VLECPC construction algorithm is modified with the objective of significantly reducing its search complexity while still yielding near-optimal codes. A low-complexity sequence maximum a posteriori (MAP) decoder for all VLECPCs (including our constructed optimal code) is then proposed under the premise that the receiver knows the number of codewords being transmitted. Simulations show that the realized optimal and suboptimal VLECPCs compare favorably with existing codes in the literature in terms of coding efficiency, search complexity and error rate performance.