可逆變異長度編碼之特徵分析及其建構演算法

Abstract

在本篇論文的第一部份，我們探討可逆變異長度編碼在遭遇編碼資料發生 錯誤下的解碼特性。我們提出一個可以分析變異長度編碼的正向解碼錯誤偵測 與正向解碼錯誤回復特性的數學模型。透過此數學模型，我們推導出描述變異 長度編碼的六種錯誤特性的數學公式：正向解碼錯誤偵測機率、正向解碼錯誤回 復機率、正向解碼錯誤偵測延遲長度的期望值與變異數、正向解碼錯誤回復延遲 長度的期望值與變異數。當此數學模型套用在可逆變異長度編碼時，我們發 現先前的六個數學公式中，有三個公式可以進行簡化。我們也推導出描述可 逆變異長度編碼的另外六種錯誤特性的數學公式：逆向解碼錯誤偵測機率、逆向 解碼錯誤回復機率、逆向解碼錯誤偵測延遲長度的期望值與變異數、逆向解碼錯 誤回復延遲長度的期望值與變異數。 在本篇論文的第二部份，我們探討可逆變異長度編碼的建構演算法。可逆 變異長度編碼的建構演算法可分為兩大類：第一類是以霍夫曼編碼為基礎的建構 演算法，第二類是反覆更新編碼的建構演算法。我們在這兩大類各別提出兩 個建構演算法：第一個演算法著重在減少編碼累贅，第二個演算法同時考慮減 少編碼累贅及提高錯誤偵測機率。

In part I of this dissertation, we present a model for analyzing the error detection and error synchronization characteristics of nonexhaustive VLCs. Six indices, the error detection probability, the mean and the variance of forward error detection delay length, the error synchronization probability, the mean and the variance of forward error synchronization delay length are formulated based on this model. When applying the proposed model to the case of nonexhaustive RVLCs, these formulations can be further simplified. Since RVLCs can be decoded in backward direction, the mean and the variance of backward error detection delay length, the mean and the variance of backward error synchronization delay length are also introduced as measures to examine the error detection and error synchronization characteristics of RVLCs. In addition, we found that error synchronization probabilities of RVLCs with minimum block distance greater than 1 are 0. We study the topics of RVLC construction algorithms in part II of this dissertation. RVLC construction algorithms can be classified into two categories : 1. Huffman code based RVLC construction algorithms, 2. Iterative RVLC construction algorithms. In each category, we proposed two algorithms : one of them aims at minimizing average codeword lengths while the other proposed algorithm jointly considers minimizing average codeword lengths and maximizing error detection probabilities.