臺灣博碩士論文加值系統

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

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.

1 Introduction 1
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2.1 Part I:Characteristics of Error Detection and Error Synchronization of
RVLCs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2.2 Part II:The Construction Algorithms of RVLCs . . . . . . . . . . . . 4
1.3 Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
I Characteristics of RVLCs 7
2 Error Detection and Error Synchronization of VLCs and RVLCs 9
2.1 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2 Error Detection and Error Synchronization of VLCs . . . . . . . . . . . . . . 10
2.3 Error Detection and Error Synchronization of RVLCs . . . . . . . . . . . . . 21
2.4 Comparison of the Error Detection and Error Synchronization Characteristics
of Various RVLCs for a benchmark English Alphabet Source . . . . . . . . . 24
2.5 Phase Error Cases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
II RVLC Construction Algorithms 27
3 Huffman-Code Based RVLC Construction Algorithms 29
i
3.1 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.1.1 Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.1.2 Algorithms For RVLC Construction . . . . . . . . . . . . . . . . . . . 30
3.1.3 Algorithms For Constructing Error-Correcting RVLCs . . . . . . . . . 32
3.2 The Proposed Huffman-code Based Construction Algorithms . . . . . . . . . 34
3.2.1 A Generic Algorithm for Construction of RVLCs . . . . . . . . . . . . 34
3.2.2 A Generic Algorithm for Constructing RVLC with Error-Correcting
Capability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4 Iterative RVLC Construction Algorithms 51
4.1 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.1.1 Tseng and Chang’s Algorithm . . . . . . . . . . . . . . . . . . . . . . 51
4.2 The Proposed Iterative RVLC Construction Algorithms . . . . . . . . . . . . 53
4.2.1 The Proposed Generic Algorithm for Construction of Symmetrical
RVLCs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
4.2.2 The Proposed Generic Algorithm for Constructing Symmetrical RVLCs
with Error Correcting Capabilities . . . . . . . . . . . . . . . . . . . . 54
4.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
III Future Work 61
5 Conclusion And Future Works 63
5.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.2 Future Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.2.1 Issues on the Construction of RVLCs . . . . . . . . . . . . . . . . . . 64
5.2.2 Issues on the Decoding of RVLCs in Video Coding Standards . . . . . 64
5.2.3 Issues on the Theoretical Results of RVLCs . . . . . . . . . . . . . . 65
ii
Appendix 71
A Publication List 71

[1] ITU-T , ”Video codec for audiovisual services at p*64 kbits/sec,” Recommendation
H.261, 1993.

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

[3] ISO/IEC JTC1 CD 11172, ”Coding of Moving Pictures and Associated Audio for Digital
Storage Media at up to about 1.5 Mbits/s,” 1991.

[4] ISO/IEC Draft International Standard 13818, ”Information Technology-Generic Coding
of Moving Pictures and Associated Audio,” 1994.

[5] ISO/IEC, ”Coding of Audio-Visual Objects: Visual,” Final Draft International Standard
14496-2, 1998.

[6] Y. Wang, S. Wenger, J.-T. Wen, and A. K. Katsaggelos, ”Review of Error Resilient
Coding Techniques for Real-Time Video Communications, IEEE Signal Proc. Magazine,
vol. 17, no. 4, pp. 61-82, Jul. 2000.

[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.

[8] J. D. Villasenor, Y.-Q. Zhang and J. Wen, ”Robust video coding algorithms and systems,”
Proceedings of the IEEE, vol. 87, pp. 1724 -1733. Oct. 1999.

[9] R. Llados-Bernaus and R. L. Stevenson, ”Fixed-Length Entropy Coding for Robust
Video Compression,” IEEE Trans. Circuits and Systems for Video Tech., Vol. 8, No. 6,
Oct. 1998.

[10] A.S.Fraenkel and S. T. Klein, ”Bidirectional Huffman coding,” Computer Journal, vol.
33, no. 4, 1990.

[11] J. Wen and J.D. Villasenor, ”A Class of Reversible Variable Length Codes for Robust
Image and Video Coding,” Proc. 1997 IEEE Int. Conf. Image Processing, vol.2, pp.
65-68, Santa Barbara, Oct. 1997.

[12] J.Wen and J. D. Villasenor, ”Reversible Variable Length Codes for Efficient and Robust
Image and Video Coding,” Data Compression Conference, pp. 471-480, 1998.

[13] L. S. Bobrow and S. L. Hakimi, ”Graph theoretic prefix codes and their synchronizing
properties,” Inform. Contr., vol. 15, no. 1, pp. 70-94, July 1969.

[14] V. K. W. Wei and R. A. Scholtz, ”On the characterization of statistically synchronizable
codes,” IEEE Trans. Inform. Theory, vol. 26, pp. 733-735, Nov. 1980.

[15] J. Berstel and D. Perrin, Theory of Codes. Orlando, FL: Academic, 1985.

[16] Y. Takishima, M. Wada, and H. Murakami, ”Error states and synchronization recovery
for variable length codes,” IEEE Trans. Commun., vol. 42, pp. 783-792, Feb./Mar./Apr.
1994.

[17] P. F. Swaszek and P. DiCicco, ”More on the error recovery for variable-length codes,”
IEEE Trans. Inform. Theory, vol. 41, pp. 2064-2071, Nov. 1995

[18] M. R. Titchener, ”The synchronization of variable-length codes,” IEEE Trans. Inform.
Theory, vol. 43, pp. 683-691, Mar. 1997.

[19] Guangcai Zhou and Zhen Zhang, ”Synchronization Recovery of Variable-Length Codes,”
IEEE Transactions on Information Theory, vol. 48, no. 1, pp. 219-227, 2002.

[20] R. Bauer and J. Hagenauer, On variable length codes for iterative source/channeldecoding,
in Proc. IEEE Data Compression Conf., 2001, pp. 273V282.

[21] Buttigieg, V. (1995) Variable-length error-correcting codes. Ph.D. dissertation, Univ. of
Manchester, Manchester, U.K..

[22] Y. Takishima, M. Wada, and H. Murakami, ”Reversible variable length codes,” IEEE
Transactions on Communications, 43, 158-162, 1952.

[23] C. -W. Tsai and J. -L. Wu ”On Constructing the Huffman-Code-Based Reversible
Variable-Length Codes,” IEEE Transactions on Communications, vol. 49, pp. 1506-
1509, 2001.

[24] C. -W. Tsai and J. -L. Wu ”Modified Symmetrical Reversible Variable-Length Code
and Its Theoretical Bounds,” IEEE Transactions on Information Theory, vol. 47, pp.
2543-2548, 2001.

[25] Lakovi´c, K. and Vallasenor, J, ”An Algorithm for Construction of Efficient Fix-Free
Codes,” IEEE Communications Letters, vol. 7, no. 2, pp. 391-393, 2003.

[26] Lakovi´c, K. and Vallasenor, J, ”On Design of Error-Correcting Reversible Variable
Length Codes,” IEEE Communications Letters, 6, pp. 337-339, 2004.

[27] D. A. Huffman, ”A Method for the Construction of Minimum Redundancy Codes,”
Proceeding of the IRE 40, pp. 1098-1101, 1952.
[28] Tseng, H. -W. and Chang, C. -C.. ”Construction of Symmetrical Reversible Variable
Length Codes Using Backtracking,” The Computer Journal, 46, 100-105, 2003.

[29] C. -W. Lin and Y. -J. Chuang and J. -L. Wu ”Generic construction algorithms for symmetric
and asymmetric RVLCs,” Proceedings of ICCS ’02, Singapore, 25-28 November,
vol. 2, pp. 968-972, 2002.

[30] Tseng, H. -W. and Chang, C. -C.. ”A Branch-and-Bound Algorithm for the Construciton
of Reversible Variable Length Codes,” The Computer Journal, 47, pp. 701-707, 2004.

[31] Jin Wang, Lie-Liang Yang and Lajos Hanzo, ”Iterative Construction of Reversible
Variable-Length Codes and Variable-Length Error-Correcting Codes,” IEEE Communications
Letters, 6, pp. 671-673, 2004.

[32] Sunil Kumar and Liyang Xu, ”RVLC decoding scheme for improved data recovery in
MPEG-4 video coding standard,” Real-Time Imaging, pp. 315V323, 2004.

[33] Jennifer L. H. Webb, ”Efficient table access for reversible variable-length decoding”,
IEEE Trans. Circuits and Systems for Video Technology, vol. 11, pp. 981-985, 2001.

[34] K-L Chung and H-N Chen, ”On decoding MPEG-4 reversible variable length codes,”
Signal Processing: Image Communication, 20(2), pp. 187-192, 2005.