Multiple Error Detection and Synchronization Based Reversible Variable-Length Codes Construction Algorithm

可逆式可變長度碼(Reversible Variable Length Code；RVLC) 是一種特殊的可變長度碼（Variable Length Code；VLC），特色是能夠從正反兩個方向來解碼，因此，當解碼端以正方向解碼發現錯誤，無法繼續解碼時，便可以往前尋找下一個再同步標記（Resync-Marker），然後從反方向解碼直到它偵測到錯誤為止，經由雙向解碼，可以有效地在錯誤發生時增加解碼的資料，提高傳輸品質，並將錯誤的資料限制在受影響的區域，因此，在MPEG-4 與H.263 等壓縮標準中，都採用RVLC 作為加強錯誤復原能力的方法。無論是VLC 或是RVLC，主要缺點就是容易受到錯誤的干擾，即使是一個位元發生錯誤，都可能導致接下來一連串的解碼錯誤，甚至無法解碼的情況；RVLC 發生位元錯誤後，錯誤可能被偵測出或是產生同步，從錯誤發生到偵測的長度愈短，代表解碼端愈快得知錯誤發生，可及早從反向進行解碼，以節省解碼所耗用的時間；而錯誤同步雖然代表錯誤的發生無法被解碼端所得知，同步後的資料也可以繼續解碼，但從錯誤發生到同步的長度卻會影響接收端解碼資料的品質，因此，藉由了解RVLC的錯誤偵測與錯誤同步的發生機率與長度等特性，將有助於我們設計出更具解碼效率與資料品質的RVLC。以往學者們多半著重於如何設計編碼效率更高的RVLC，而較少探討RVLC 在面臨錯誤發生時所產生的影響，雖然近期開始有文獻討論相關的議題，但仍著重於單一位元誤差的情況，因此，本計畫為二年期計畫，進行「以多位元錯誤偵測與同步為基礎之可逆式可變長度碼建構方法」，首先針對RVLC 在傳輸過程中遇到連串錯誤（burst error）及不連續位元發生多個錯誤的情況下錯誤偵測與錯誤同步的特性加以分析，並以此為基礎，設計出建構過程迅速並兼顧錯誤偵測與錯誤同步長度最低及編碼效率的RVLC，以符合實際傳輸的需求。此研究係由以下兩部分所構成：第一年：可逆式可變長度碼之多位元錯誤偵測與同步分析主要工作內容包括：建立與驗證可逆式可變長度碼之多位元錯誤偵測及錯誤同步分析模型、建立錯誤偵測及同步的分析公式與指標，並實作文獻中各種RVLC 的建構方法，進行不同的原始資料分佈及不同錯誤率下，錯誤偵測及同步分析指標的關係，並加以比較及探討。第二年：以多位元錯誤偵測與同步為基礎的RVLC 建構方法主要工作內容包括：建立RVLC 圖形模型（Graph model），並整合建構RVLC 的條件限制及前一年度所推導之多位元錯誤分析的RVLC 特性；藉由圖形模型，發展多種RVLC 建構演算法，如：（1）編碼效率最低的RVLC；（2）符合錯誤偵測需求的RVLC；（3）兼具編碼效率及符合錯誤偵測需求的RVLC 與現有文獻中的RVLC 進行不同錯誤率及不同資料來源分佈的分析比較。

Project ID:PB9709-1915
External Project ID:NSC97-2221-E182-028