摘要
在本論文中我們實作了一個超大型積體電路(VLSI)的算數編碼器架構，這個架構符合JPEG2000中對算數編碼器的規格。算數編碼法是一種無失真的壓縮方法，除了用在JPEG2000之外，也可用在一般通用的壓縮方法中。IBM的工程師 Pennebaker 等人在1988年就在IBM的期刊中發表了適合硬體實作的改良版算數編碼法Q-coder，JPEG2000中對算數編碼法的規定也主要承襲了Q-coder的精神。Q-coder演算法中除了用查表的方法來避免除法的使用，它對編碼區間(coding interval)的近似演算法也避免了乘法的使用，使得全演算法只有用到加減與位移等簡單的運算。另外JPEG2000的算數編碼器另外加入了對於內文(context)區分方式的支援。在考量與系統中前後晶片非同步的交握(handshake)步驟，我們使用Verilog設計並模擬了一個六階管線化的算數編碼器架構，使用台積電點三五製程來實作。在美商新思科技公司(Synopsys)的合成軟體中可以得到兩百兆赫、八千個邏輯閘的合成成果，不過在面積的考量下我們選擇了較小的一百兆赫、六千六百個邏輯閘得合成結果。為了讓電路的速度上限能突破兩百兆赫，我們討論了幾種改良演算法的方法： (一) 我們可以改變壓縮演算法使得輸入本文的變化範圍在一定的限度內。 (二) JPEG2000中加入的 MPS/LPS 區間交換的機制在我們的討論下效果不彰且增加電路複雜度，建議移除。 (三) 我們可以改良演算法將輸出符號由位元流改為位元組流，並將不同的本文資訊存在不同的位元組中，這樣可以幫助電路的平行化。
第一章
導論
無失真的壓縮法可以在沒有任何資料損失的情況下將資料的體積縮小，可以用在很廣泛的領域中，比如說單獨用來壓縮資料，或是跟有失真的壓縮法合用來壓縮影像或圖形資料。一般常用的無失真壓縮架構有字典法跟統計法，研究顯示統計法可以勝過任意特定的字典編碼法。
大部分的統計編碼法分為兩個部分：(一)機率模型的套用與 (二)編碼的機制。一般來說機率模型可以分為固定式的機率模型跟適應性的機率模型。另一分面，現代的機率模型多半加入了「內文」的資訊，內文資訊使得系統維持了多套機率模型以對映不同的內文。
有兩種知名的統計編碼法：霍夫曼編碼法與算數編碼法。只要機率模型是精確的話，算數編碼法可以比霍夫曼編碼法得到更好的壓縮率。但是算數編碼法在硬體實作上是比較慢的，因為在算數編碼法的原始型中每個對應的輸入符號都要使用至少一個乘法運算。
在本論文實作的算數編碼器中，我們用查表法來實作適應性的機率模型這樣可讓架構中不出現除法運算，另外我們也參考了Q-coder 架構來去除乘法的運算。這樣的架構是與 JPEG2000 中定義的QM-coder 相容的，當然也可以作為一個輔助運算器來幫助現代的 CPU。
第二章
算數編碼器的理論
無失真的壓縮法基本上就是將一連串的資料組轉為另一種形式的符號序列，算數編碼法是將這些資料由實數數線線的一段區間來表示資料組的資料。越小的區間用來表示越詳細完整的連串資料，在一般實用上，通常用區間中的一個點來表示區間，而另外儲存一個解碼長度的額外資訊。
現今的影像壓縮技術多加入了「內文」的資訊，也就是一張影像的資料我們將他分為不同的種類，而在輸出資訊時除了輸出這個點的資料另外還送出這個內文資訊，已方便後續的步驟來套用不同的機率模型。
在機率模型中適應性的壓縮法跟固定機率的壓縮法都是常用的，適應性的壓縮法比固定性的壓縮法通常能得到更好的壓縮率，並能即時的送出資訊，一般利用查表法來加快適應性機率模型的實作。
硬體實作時的算數編碼法跟理論有些許的不同，由於世界上並沒有無限位數的運算器，所以在運算的過程中必須將一些較固定的資訊先行輸出本章也將適合硬體的算數編碼演算法列出。
Q-coder 的趨近方法由 Q-coder 的提出者計算約會造成百分之四的壓縮率損失，而機率模型查表法會再造成百分之八左右的損失。有人提出 ELS-coder 的演算法可以避免這樣的壓縮率損失，不過現今並沒有任何這樣的硬體實作。
JPEG2000的算數編碼壓縮法是自 Q-coder 改良的 QM-coder。其機率模型比Q-coder 多出了能更快適應極低機率的資料機制。
第三章
算數編碼器晶片的實作
這本章中我們討論這個算數編碼器晶片的實作，他是符合 JPEG2000 規格的一個 QM-coder 具有十九個紀錄「本文」資訊的記憶體，機率表擁有四十七個狀態，並擁有一個測試的腳位可以測試到內部六十四個內部狀態。
我們首先分析了該演算法的資料相依程度並將他做成一個有向的圖，經過簡化後成了主要控制用的邏輯參考依據。再經過進一步的分析將它分成四個管線步驟。由於管線化後必定有的清理管線與管線初始化動作，我們用狀態轉移圖來規劃其間的控制電路。
在實作的過程中我們考慮到非同步的交握訊號，以及輸出訊號的穩定性，我們在前後共用了六層拴鎖器。
由於 JPEG2000 算數編碼器在每一個位元輸入的時候，有零至三個位元組輸出，考量到晶片的腳位不能佔太多並使電路變得複雜，由於「內文」機制的關係也使得加緩衝暫存器的方法也不可行。我們使用了一個訊號來通知外界的輸入訊號必須暫停，這個訊號的發生頻率依照計算約為百分之二左右。
第四章
結論與未來展望
算數編碼器的硬體實作有一些需要克服的限制，首先，每一個位元輸入都會有零到三個位元組的輸出，這樣的現象在壓縮上限越好的演算法中越為嚴重。
第二個問題就是「內文」種類的變化範圍問題，原本適應性的機率模型是可以預測下一位輸入資料所得到的機率值的，但是由於內文機制的關係，使得預測的實行難度大為增加，如果在演算法上能縮減「內文」的變化區間會改善這個問題。
第三個就是 JPEG2000 的 QM-coder 採用了 MPL/LPS 區間交換的機制，其增進壓縮效果的能力不到千分之二，但卻增加關鍵電路的複雜度，建議在演算法中移除。
第四是 JPEG 兩千用同樣的一個數線來壓縮不同的本文資訊，而實際上輸出是以位元組為單位來輸出，我們可以用不同的數線來壓縮不同的本文資訊，而在位元組輸出時再將它合併為一位元組流，這樣的架構也在本章中討論到。
我們並提出了一個方法來改善現在的關鍵電路複雜度，由於在每個暫存器運算後必須經過標準化的動作，但是由於經過分析，暫存器中的結果為特定的值，因此可以利用一些方法配合查表來加速標準化的速度。

TABLE OF CONTENTS
ABSTRACTS
LIST OF ILLUSTRATIONS
LIST OF TABLES
ACKNOWLEDGEMENTS
CHAPTER 1. INTRODUCTION
CHAPTER 2. ARITHMETIC CODING THEORY
2.1. Compare Between Arithmetic Coding and Huffman Coding
2.2. Concepts of Context
2.3. Advantage of Adaptive Probability Model
2.4. Original Form of Arithmetic Coding Implementation
2.5. Q-Coder and ELS-Coder
2.6. QM-coder in JPEG2000
CHAPTER 3. IMPLEMENTATION OF ARITHMETIC CODING CHIP
3.1. Overview
3.2. Data Dependency Analysis
3.3. Stall, Beginning and Flush Fix
3.4. Implementation Architecture
3.5. Performance Analysis
3.6. Consideration of Tape Out
3.7. Experimentation Result
CHAPTER 4. CONCLUSION AND FUTURE WORK
4.1. Conclusion
4.2. Some Possible Improvement
4.3. Lack of Synthesis Tool

Reference
[1] “JPEG 2000 image coding system -- Part 1,” Standard ISO/IEC 15444-1:2000
[2] ” Information technology - Coding of audio-visual objects,” Standard ISO/IEC 14496:2001
[3] S. R. Kuang, J. M. Jou, R. D. Chen, and Y. H. Shiau, ”Dynamic Pipeline Design of an Adaptive Binary Arithmetic Coder,” IEEE Trans. Circuits Syst. II, vol. 48, no. 9, pp. 813-825, Sep 2001.
[4] T. C. Bell, I. H. Written, and J. G. Cleary, “Modeling for text compression,” ACM Computing Survey, vol. 21, no. 4, pp. 557—591, Dec. 1989.
[5] S. R. Kuang, J. M. Jou, and Y. L. Chen, “The Design of an Adaptive On-Line Binary Arithmetic-Coding Chip,” IEEE Trans. Circuits Syst. I, vol. 45, no. 7, pp. 693-706, July 1998.
[6] Cleary, J.C., and Witten, I.H. "A comparison of enumerative and adaptive codes," IEEE Trans. Inf. Theory, vol. 30, no. 2, pp. 306-315 , Mar. 1984.
[7] D. E. Knuth, “Dynamic Huffman coding,” Algorithms, vol. 6, pp. 163—180, 1985.
[8] G. G. Langdon and J. Rissanen, “Compression of black—white image with arithmetic coding,” IEEE Trans. Commun., vol. COM-29, pp. 858—867, June 1981.
[9] T. C. Bell, J. G. Cleary, and I. H. Witten, Text Compression, Englewood Cliffs, NJ: Prentice-Hall, 1990.
[10] R. J. van der Vleuten “New methods for multiplication-free arithmetic coding,” in Proc. IEEE Data Compression Conf., Snowbird, UT, pp. 555, Mar 1999.
[11] M. Schindler, “A fast renormalisation for arithmetic coding,” in Proc. IEEE Data Compression Conf., Snowbird, UT, pp. 572, Apr. 1998.
[12] L. Stuiver and A. Moffat, “Piecewise integer mapping for arithmetic coding,” in Proc. IEEE Data Compression Conf., Snowbird, UT, pp. 3-12, Apr. 1998.
[13] M. H. Hsieh and C. H. Wei, “An adaptive Multialphabet Arithmetic Coding for Compression,” IEEE Trans. Circuits Syst. , vol. 8, no. 2, pp. 130-137, April 1998.
[14] M. Peon, R.R. Osorio and J.D. Bruguera, “A VLSI Implementation of an Arithmetic Coder for Image Compression,” in Proc. 23th EUROMICRO Conference, p.p. 591-598, Sep. 1997.
[15] R.R. Osorio and B. Vanhoof, “200 Mbit/s 4-symbol arithmetic encoder architecture for embedded zero tree-based compression,” in Proc. IEEE Workshop on Signal Processing System, pp. 397-405, 2001.
[16] P. G. Howard and J. S. Vitter, “Arithmetic coding for data compression,” Proc. IEEE, vol. 82, no. 6, pp. 857—865, June 1994.
[17] W. D. Withers, “A Rapid Probability Estimator and Binary Arithmetic Coder,“ IEEE Trans. Inf. Theory, vol. 47, no. 4, pp. 1533-1534, May 2001.
[18] R. Arps, T. Truong, D. Lu, R. Pasco, and T. Friedman, “A multi-purpose VLSI chip for adaptive data compression of bilevel images,” IBM J. Res. Develop., vol. 32, no. 6, pp. 775—794, Nov. 1988.
[19] W. B. Pennebaker, J. L. Mitchell, G. G. Langdon, and R. B. Arps, “An overview of the basic principles of the Q-coder adaptive binary arithmetic coder,” IBM J. Res. Develop., vol. 32, no. 6, pp. 717—725, Nov. 1988.
[20] G. Feygin, P. G. Gulak, and P. Chow, “Architectural advances in the VLSI implementation of arithmetic coding for binary image compression,” in Proc. IEEE Data Compression Conf., Snowbird, UT, pp. 254—263, Mar. 1994.
[21] B. Fu and K. K. Parhi, “Two VLSI design advances in arithmetic coding,” in Proc. ISCAS, Seattle, WA, Apr. 1995, pp. 1440—1443.
[22] C. E. Shannon, “A mathematical theory of communication,” Bell Syst, Tech. J., vol. 27, pp. 398-403, July 1948.
[23] D. A. Huffman, “A method for the construction of minimum redundancy codes,“ Proc. IRE, vol. 40, pp. 1098-1101, 1952.
[24] K. M. S. Soyjaudah and S. Ramsamy, “A comparative study of context free models of arithmetic coding,” International Conf. on EUROCON, vol. 2, pp. 428-431, 2001.
[25] K. F Chen, C. J. Lian, H. H. Chen, and L. G. Chen, “Analysis and architecture design of EBCOT for JPEG-2000,” in Proc. Symposium on Circuits and Syst., 2001., vol. 2, pp. 765 —768, May 2001.
[26] “Passport CB35IO122 0.35-Micron, 3-Volt I/O Pad Library,” Galax! Inc, subsidiary of Avant! Corporation, version 1.1, July 1998.