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

Characteristic Analysis and Construction Algorithms for Reversible Variable Length Codes

林佳緯(Jia-Wei Lin)

指導教授 ： 吳家麟

國立臺灣大學/電機資訊學院/資訊工程學研究所/博士(2005年)

https://doi.org/10.6342/NTU.2005.01143

摘要

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

關鍵字

變異長度編碼 ； 錯誤偵測 ； mpeg-4

並列摘要

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.

並列關鍵字

variable length code ； mpeg-4 ； error detection

參考文獻

[2] ITU-T, ”Video Coding for Low Bit Rate Communication,” Recommendation H. 263,

of Moving Pictures and Associated Audio,” 1994.

14496-2, 1998.

[7] Y. Wang and Q. Zhu, ”Error control and concealment for video communication: a

review,” Proceedings of the IEEE, vol. 86, pp. 974-997. May 1998.