臺灣博碩士論文加值系統

Huffman編解碼為MPEG-4 AAC（Advanced Audio Coding）中極為重要的一部分。他的工作為將資料串以較短的位元串取代，降低檔案大小。在Huffman解碼時，因為資料量龐大，而每一筆資料可能也會使用多次搜尋，造成解碼時間過長。而本篇論文提出一個快速的Huffman解碼法，它的出發點為擷取多個bit，降低搜尋次數。平均在一首歌的解碼之中，5 bit 長度之內得到結果的機率有72%。本篇論文提出的方法，一次搜尋就能夠解碼到5 bit長度，其他方法解碼到5 bit長度需要3~5次的搜尋。因此大大降低搜尋次數。並且單一次的搜尋計算量也比其他方法小。經實驗結果，與其他方法比較，搜尋次數可以節省26.92%~58.21%，指令數量也可以節省40.21%~66.53%。

Huffman coding is an important part in MPEG-4 Advanced Audio Coding（AAC）standard. The function of Huffman coding is to encode the input data stream with shorter length of bit string so that the audio samples can be compressed into smaller size. The compressed data can be recovered by Huffman decoding in decoder side. The process of Huffman decoding requires long delay because long computational time is consumed by the excessive number of searches for the decoded symbols. In this paper, a fast Huffman decoding algorithm is proposed to reduce the number of searches required in Huffman decoding. The algorithm uses a forward search scheme that 5-bit length is used for each search basis for decoding the symbols. The experimental results show that a 5-bit search scheme can be hit with the probability of 72% to decode the symbols. Thus the proposed method can reduce the number of searches, thus lead to the reduced processing delay and increasing processing speed for Huffman decoding. Comparing with other algorithms for Huffman decoding, the proposed algorithm can reduce the number of searches by 27% to 58%, the number of instructions by 40% to 67%.

摘要 i
ABSTRACT ii
誌謝 iii
表目錄 vi
圖目錄 viii
第一章 - 緒論 1
1.1. 研究背景與動機 1
1.2. 資料壓縮概論 2
1.2.1. 霍夫曼編碼 3
1.3. MPEG4-AAC簡介 5
1.3.1. MPEG4-AAC中的霍夫曼解碼 7
1.4. Helix Community背景 11
1.5. 章節組織 12
第二章 – 霍夫曼解碼搜尋法 13
2.1. 基礎霍夫曼解碼搜尋法 13
2.1.1. 直接查表法（lookup table search） 14
2.1.2. 二元樹搜尋法（binary tree search） 16
2.2. 近年來應用在AAC中的霍夫曼解碼搜尋法 20
2.2.1. Helix搜尋法 20
2.2.2. Lee搜尋法 25
2.2.3. Gutemberg搜尋法 30
第三章 – 霍夫曼解碼搜尋加速演算法 34
3.1. 加速演算法的開發概念 34
3.2. 索引表（Index table）的建立 34
3.3. 利用索引表（Index table）解碼流程 37
3.4. MPEG4-AAC解碼中各個長度的Codeword統計 38
3.4.1. 以音樂音檔統計 38
3.4.2. 以非音樂音檔統計 41
3.5. 與Gutemberg搜尋法做連結的解碼表修正 42
3.6. 加速演算法與Gutemberg搜尋法連結的解碼流程 50
第四章 – 驗證數值統計 52
4.1. Code size統計 52
4.2. 搜尋次數的Best cast與Worst cast 53
4.3. 搜尋次數統計 55
4.3.1. 本論文加速演算法與Helix搜尋法連結的搜尋次數統計 55
4.3.2. 本論文加速演算法與Lee搜尋法連結的搜尋次數統計 56
4.3.3. 本論文加速演算法與Gutemberg搜尋法連結的搜尋次數統計 57
4.3.4. 所有搜尋法在搜尋次數上的統計圖 57
4.4. 指令數量統計 62
4.4.1. 本論文加速演算法與Helix搜尋法連結的指令數量統計 62
4.4.2. 本論文加速演算法與Lee搜尋法連結的指令數量統計 63
4.4.3. 本論文加速演算法與Gutemberg搜尋法連結的指令數量統計 63
4.4.4. 所有搜尋法在指令數量上的統計圖 64
4.5. 記憶體增加量統計 68
第五章 - 結論 69
參考文獻 70

[1]ISO/IEC 11172-3, "Information technology - Coding of moving pictures and associated audio for digital storage media at up to about 1.5 Mbit/s - Part3.Audio," 1993.
[2]K. Brandenburg and G. Stoll, "ISO-MPEG-1 Audio:a generic standard for coding of high quality digitalaudio," AES, pp. 31-42, 1996.
[3]ISO/IEC 13818-7, "Information technology – Generic coding of moving pictures and associated audio information - Part 7: Advanced Audio Coding (AAC)," 1997.
[4]M. Bosi, K. Brandenburg, Sch. Quackenbush, L. Fielder, K. Akagiri, H. Fuchs, M. Dietz, J. Herre, G. Davidson, and Yoshiaki Oikawa, "ISO IEC MPEG-2 Advanced Audio Coding," Journal of Audio Enginnering Society, pp. 798-814, 1996.
[5]ISO/IEC 14496-3, "Information Technology – Coding of Audiovisual Objects - part3: Audio," 1998.
[6]A. Huffman, "a method for the Construction of Minimum Redundancy," Proc. IRE, vol. 40, 1952.
[7]戴顯權, 資料壓縮: 旗標, 2007.
[8]蔡文輝 林家禎 張真誠, 資料壓縮技術與應用: 全華, 2007.09.
[9]T. Painter and A. Spanias, "Perceptual coding of digital audio," Proceedings of the IEEE, vol. 88, pp. 451-515, 2000.
[10]Helix Community, "https://helixcommunity.org/."
[11]Hsieh Cheng-Teh and S. P. Kim, "A concurrent memory-efficient VLC decoder for MPEG applications," Consumer Electronics, IEEE Transactions on, vol. 42, pp. 439-446, 1996.
[12]Lee Jae-Sik, Jeong Jong-Hoon, and Chang Tae-Gyu, "An efficient method of Huffman decoding for MPEG-2 AAC and its performance analysis," Speech and Audio Processing, IEEE Transactions on, vol. 13, pp. 1206-1209, 2005.
[13]R. Hashemian, "Memory efficient and high-speed search Huffman coding," Communications, IEEE Transactions on, vol. 43, pp. 2576-2581, 1995.
[14]R. Hashemian, "Condensed table of Huffman coding, a new approach to efficient decoding," Communications, IEEE Transactions on, vol. 52, pp. 6-8, 2004.
[15]G. S. Gutemberg, M. A. M. Lima, W. O. G. Filho, A. Perkusich, M. R. A. Morais, and A. M. N. Lima, "A Fast and Memory Efficient Huffman Decoding Method for the MPEG-4 AAC Standard," in Consumer Electronics, 2008. ICCE 2008. Digest of Technical Papers. International Conference on, 2008, pp. 1-2.
[16]Wang Pi-Chung, Yang Yuan-Rung, Lee Chun-Liang, and Chang Hung-Yi, "A memory-efficient Huffman decoding algorithm," in Advanced Information Networking and Applications, 2005. AINA 2005. 19th International Conference on, 2005, pp. 475-479 vol.2.