Abstract
可變長度訊源碼已經很廣泛地應用在無損失資料壓縮的技術上. 這種編碼方式已經成為許多國際標準的一部份, 像數位傳真, JPEG, MPEG 等等, 也曾經提出被應用在數位高畫質電視系統 (HDTV) 中. 雖然可變長度碼可以有效地壓縮資料, 可是由於可變長度字元序列並沒有明顯的界線,位元錯誤可能導致嚴重的錯誤傳遞. 為了解決這問題, 可以在訊原碼中設計一些同部碼. 在本論文中, 我們研究可以防止因前面字元滑脫而導致錯誤傳遞的擴展同部字元. 我們提出一些有關這種具有擴展同部字元的可變長度碼之性質以及其平均長度的下限. 我們同時提供可以建構包含有擴展同步字元之可變長度碼的直觀演算法. 這些演算法在很多例子中都可以找到比先前方法所產生的碼擁有較短的平均長度. 我們也探討了另外一種應用整數線性規劃的方法, 來建構含有擴展同步字元的可變長度碼. 由於電腦計算容量有限, 此法產生的結果並不理想.本文共分六章. 第一章簡介; 第二章簡單描述一下由一些學者所研究同步字元和擴充同步字元的成果. 第二章我們研究一些擴充同步字元的性質及包含有這種字元的可變長度碼平均長度的下限. 第四章我們提出兩個建構的直觀演算法並且加以比較. 第五章嘗試用整數線性規劃的方法建構擴展同步字元. 第六章提出一些結論和未來可能繼續研究的方向.Variable-length source coding is widely used in lossless datacompression. It has become part of the international standardssuch as digital facsimile, JPEG, MPEG, and was used in theproposed digital HDTV systems. Though it is efficient atcompressing data, bit errors may lead to serious errorpropagation since there are no explicit boundaries in variable-length codeword sequences. In this thesis we study variable-length codes with extended synchronizing codewords which canprevent error propagation due to previous slippage. Propertiesof such codes and an lower bound on average length areproposed. Heuristic algorithms for constructing prefix codeswith extended synchronizing codewords are given, which can findcodes with less redundancy than those found by previouslyproposed methods in many cases. An alternative constructionmethod by using integer linear programming is also presented.