臺灣博碩士論文加值系統

在這篇論文中，我們提出可藉由在連續的一對一字碼(One-to-One Code)之間安插特定字元(Unique Word)來分開一對一字碼，使得連續的一對一字碼符合唯一可解(Uniquely Decodable)性質，藉此產生一種新的編碼方式，我們稱為「唯一可解一對一碼」(Uniquely Decodable One-to-One Code)。我們接著分析唯一可解一對一碼的組合特性與壓縮能力，並由此推導出給定長度n的唯一可解一對一碼的個數公式。經由此公式，我們即可計算給定統計特性之信息源的唯一可解一對一碼的最佳平均碼長。我們另外推導出三個平均碼長的上限公式，與兩個平均碼長的極限值的上限公式，據此，我們證明當特定字元(Unique Word)的長度與信息源字元的整合個數皆趨近無限大時，唯一可解一對一碼的平均碼長的極限值可以達到信息源的理論極限熵值(Entropy)。論文接著提供在不同條件下的快速編碼與快速解碼的演算法。我們的數值實驗結果顯示，相對於赫夫曼碼(Huffman Code)，在相同的解碼複雜度的前提下，唯一可解一對一碼具有可與其相比的低壓縮率。相對於藍柏吉夫碼(Lembel-Ziv Code)，唯一可解一對一碼則具有較佳的平均碼長，此數值結果說明了唯一可解一對一碼在實際應用的可行性。

In this thesis, we consider the so-called uniquely decodable one-to-one code (UDOOC) that is formed by inserting a “comma” indicator, termed the unique word (UW), between consecutive one-to-one codewords for separation. Along this research direction, we first investigate the general combinatorial properties of UDOOCs, in particular the enumeration of UDOOC codewords for any (finite) codeword length. Based on the obtained formula on the number of length-n codewords for a given UW, the average codeword length of the optimal UDOOC for a given source statistics can be computed. Upper bounds on the average codeword length of UDOOCs are next established. The analysis on bounds of the average codeword length then leads to two asymptotic bounds on ultimate per-letter average codeword length, one of which is achievable and hence tight for a certain source statistics and UW, and the other of which proves the achievability of source entropy rate of UDOOCs when both the block size of source letters for UDOOC compression and UW length go to infinity. Efficient encoding and decoding algorithms for UDOOCs are subsequently given. Numerical results show that when grouping three English letters as a block, the UDOOCs with UW = 0001, 0000, 000001 and 000000 can respectively reach the compression rates of 3.531, 4.089, 4.115 and 4.709 bits per English letter (with the lengths of UWs included), where the source stream to be compressed is the book titled Alice’s Adventures in Wonderland. In comparison with the first-order Huffman code, the second-order Huffman code, the third-order Huffman code and the Lembel-Ziv code, which respectively achieve the compression of 3.940, 3.585, 3.226 and 6.028 bits per single English letter, the proposed UDOOCs can potentially in comparable compression rate to the Huffman code under similar decoding complexity and yield a better average codeword length than that of the Lempel-Ziv code, thereby confirming the practicability of the simple idea of separating OOC codewords by UWs.

Chinese Abstract i
English Abstract ii
Acknowledgements iii
Contents iv
List of Figures vi
List of Tables vii
1 Introduction 1
2 Construction of UDOOCs 10
2.1 Digraphs for UDOOCs 10
2.2 Code Trees for UDOOCs 11
3 Combinatorial Properties of UDOOCs 15
3.1 Enumeration of Codewords in Ck(n) 15
3.2 Equivalence among UWs 16
3.3 Growth Rates of UDOOCs 17
3.4 Enumeration of sk;n 21
3.5 Asymptotic Equivalence 30
4 Encoding and Decoding Algorithms of UDOOCs 32
4.1 Upper Bounds on Average Codeword Length of UDOOCs 33
4.2 General Encoding and Decoding Mappings for UDOOCs 41
4.3 Encoding and Decoding Algorithms for UW = 11...1 43
4.4 Encoding and Decoding Algorithms for UW = 11...10 45
4.5 Encoding and Decoding Algorithms for General UW k 46
4.6 Complexity Reduction of the Encoding and Decoding Algorithms for General UW k 47
4.7 Extension to N-ary UDOOCs 51
5 Practice and performance of UDOOCs 55
6 Conclusion 63
A Proof of Theorem 1 64
B Degree of det(I-A_kz) 69
C Verification of Algorithms 5 and 6 72
D Computation of limit_{t->\infty} L_{k,t} for all-zero UW and uniform i.i.d. source 76

[1] T. M. Cover and J. A. Thomas, Elements of Information Theory, New York, NY: John
Wiley &; Sons, 1991.
[2] Sam E. Ganis, Notes on the Fibonacci Sequence, Amer. Math. Monthly, 1959, pp. 129-
130.
[3] A. D. WYNER, An Upper Bound on the Entropy Series, Inf. Control, vol. 20, pp. 176-181,
1972.
[4] S. K. Leung-Yan-Cheong and T. M. Cover, Some equivalences between Shannon entropy
and kolmogorov complexity, IEEE Trans. on Information theory, vol. IT-24, no. 3, pp.
331-338, May 1978.
[5] J. G. Dunham, Optimal noiseless coding of random variables, IEEE Trans. Inf. Theory,
vol. IT-26, no. 3, p. 345, May 1980.
[6] J. Rissanen, Tight lower bounds for optimum code length, IEEE Trans. Inf. Theory, vol.
IT-28, no. 2, pp. 348V349, Mar. 1982.
[7] E. I. Verriest, An achievable bound for optimal noiseless coding of a random variable,
IEEE Trans. Inf. Theory, vol. IT-32, no. 4, pp. 592V594, Jul. 1986.
[8] Noga Alon, Alon Orlitsky, A lower bound on the expected length of one-to-one codes,
IEEE TRANS. on Information theory, Vol. 40, Sep. 1994.
[9] Carlo Blundo, Roberto De Prisco, New Bounds on the Expected Length of One-to-one
Codes, IEEE TRANS. on Information theory, Vol. 42, NO. 1, Jan. 1996.
[10] Serap A. Savari, Akshay Naheta, Bounds on the Expected Cost of One-to-One Codes,
ISIT , June 2004
[11] Jay Cheng, Tien-ke Huang, Claudio Weidmann, New bounds on the expected length of
optimal one-to-one codes, IEEE TRANS. on Information theory, Vol. 53, NO. 5, May
2007.
[12] Serap A. Savari, On One-to-One Codes for Memoryless Cost Channels, IEEE TRANS.
on Information theory, Vol. 54, NO. 1, Jan. 2008
[13] Wojciech Szpankowski, A One-to-One Code and Its Anti-Redundancy, IEEE TRANS.
on Information theory, Vol. 54, NO. 10, Oct. 2008
[14] Wojciech Szpankowskia and Sergio Verdu, Minimum Expected Length of Fixed-to-
Variable Lossless Compression of Memoryless Sources, ISIT, Seoul Korea July. 2009
[15] Richard Stanley, Enumerative Combinatorics, Vols. 1 and 2, Cambridge Studies in Advanced
Mathematics, 2011.
[16] Norman Biggs, Algebraic Graph Theory, Cambridge Mathematical Library, 1994.
[17] Jrgen Bang-Jensen and Gregory Z. Gutin, Theory, Algorithms and Applications,
Springer Monographs in Mathematics, 2009.
[18] I. Goulden and D.M. Jackson, An inversion theorem for cluster decompositions of se-
quences with distinguished subsequences, J. London Math. Soc. 20 ,pp. 567-576., 1979.
[19] John Noonan and Doron Zeilberger, The Goulden-Jackson Cluster Method: Extensions,
Applications, and Implementations, J. Dierence Eq. Appl. 5, pp. 355-377, 1999.
[20] Xiangdong Wen, The symbolic Goulden-Jackson cluster method, J. Dierence Eq. Appl.
11:2,pp 173-179, 2006.
[21] Elizabeth J. Kupin and Debbie S. Yuster, Generalizations of the Goulden-Jackson clus-
ter method, J. Dierence Eq. Appl. 16:12,pp 1463-1480, 2010.
[22] John Noonan1, New Upper Bounds for the Connective Constants of Self-Avoiding Walks,
J. Statistical Physics, Vol. 91, Nos. 5/6, 1998
[23] R. Doroslovacki, Binary n-Words without the subword 1010 10, Novi SAD J. MATH.,
vol. 28, NO. 2 1998, 127-133.
[24] R. Doroslovacki, n-Words over any alphabet with forbidden any 3-subwords, Novi SAD
J. MATH., vol. 30, NO. 2 2000, 159-163.
[25] R. Doroslovacki, The set of all the words of length n over any alphabet with a forbidden
good subword, Univ. u Novom Sadu, Zb. Rad. Prirod.-Mat. Fak. Ser. Mat. 23, 2(1993),
239-244.
[26] R. Doroslovacki, The set of all the words of length n over alphabet f0,1 g with any
forbidden subword of length three, Univ. u Novom Sadu, Zb. Rad. Prirod.-Mat. Fak. Ser.
Mat. 25, 2(1995), 111-115.
[27] R. Doroslovacki, On Binary n-words with forbidden 4-subwords, Novi SAD J. MATH.,
vol. 29, NO. 1, 1999, 27-32.
[28] R. Doroslovacki, Binary n-Words without the subword 1010 10, Novi SAD J. MATH.,
vol. 28, NO. 2 1998, 127-133.
[29] Leo J. Guibas and Andrew M. Odlyzko, Periods in Strings, J. Combinatorial Theory,
series A 30, pp. 19-42, 1981.
[30] Eric Rivals and Sven Rahmann, Combinatorics of periods in strings, J. Combinatorial
Theory, series A 104, pp. 95-113, 2003.
[31] http://oxforddictionaries.com/words/what-is-the-frequency-of-the-letters-of-thealphabet-
in-english
[32] http://corpus.canterbury.ac.nz/descriptions/
[33] http://bcl?.comli.eu/?download-e?n.html
[34] Chris Godsil and Gordon F. Royle, Algebraic Graph Theory, Springer, 2001.
[35] Roger A. Horn and Charles R. Johnson, Matrix Analysis, 2nd edition, Cambridge University
Press, 2012.
[36] Kenneth M. Homan and Ray Kunze, Linear Algebra, 2nd edition, Pearson,1971.