臺灣博碩士論文加值系統

摘 要
H.264/AVC為目前最新一代的視訊壓縮標準 ，相關研究顯示H.264/AVC相較於MPEG-2及MPEG-4，無論是壓縮率或視訊品質皆有大幅的提升，使得H.264/AVC非常適用於多媒體串流(multimedia streaming)及行動電視(mobile TV)的相關應用。本篇論文針對在小面積上提供一個快速H.264/AVC CABAC編碼與解碼；CABAC主要由三個方塊函數所組成: Binarization，Context Model，與 Arithmetic Coding。以傳統的方式處理，一個位元需要耗費13個步驟才能完成更新；在此藉由重新安排每個步驟(包含平行處理與加入pipeline)，成功的將之縮短到4 個步驟。在 Binarization方面，對於固定碼(Unary)在此皆以組合電路來實現，對於 UEGK編碼我們採table partition的作法以減少額外的編碼電路；相較於用軟體方式來實現該函數；微處理器需要額外的中斷來回應服務，因此利用硬體來分攤微處理器的工作量；多出的電路只有5k gate count。Context Model方面，為了將流程最佳化在此選擇雙埠記憶體讓同時讀寫記憶體得以實現。Arithmetic Coding中當range與low小於1/4*range時就會進入renormalization的步驟。renormalization有兩個迴圈，傳統的方式為將bit循序的處理。本論文作法為先使用one-slipping 的做法引用LZD 電路來偵測第一個迴圈的執行次數；緊接著利用bit-parallel的處理方式引入遮罩產生電路來實現第二迴圈。相比於傳統的作法，遮罩產生的作法大約省了AC 10%的執行時間，平均需要1.8個週期處理一個Bin；並將Arithmetic Coding的三個模式結合在一個電路以達到最大的硬體共享；另一方面[3]以prefix adder 來處理 renormalization，本論文為降低面積，引用shifter直接去除MSB並利用FSM來儲存狀態如此就可省去兩個10bits的加法電路。相較於[3]，約省了50%的電路。整體而言，實現的編碼器可操作在333MHz，gate count 為13.3k，運算時間約為傳統方法的90%。解碼可達 333MHz，總共的gate count 為16.7k。因此該設計符合低成本，高產出的特性。

ABSTRACT
H.264/AVC is the latest video compression standard. Relevant research shows that, comparing with MPEG-2 and MPEG-4, H.264/AVC has tremendously improved both compression ratio and video quality. Such feature makes H.264/AVC best fit in the applications of multimedia streaming and mobile TV. This thesis focused on fast CABAC encode/decode in a small area under H.264/AVC. CABAC is mainly composed of three function units: Binarization, Context Mode, and Arithmetic Coding. 13 steps will be required to renew a bin, if processed by traditional method. By re-arranging every step (including parallel processing and adding pipeline), the procedure can be successfully reduced to 4 steps. In term of Binarization, combination circuit is applied to Unary coding; and table partition is utilized to reduce extra computing complexity for UEGK coding. In contrast to performing the function by hardware, processing by software will interrupt the operation of the microprocessor in order to respond this service, whereas the hardware can share the loadings by additional 5k gate count only. In term of Context Mode, dual-port memory is adopted to read and write simultaneously and maximize the efficiency of the procedure. In term of arithmetic Coding, renormalization happens when range and low are less than 1/4*range. There are two loops in renormalization, and are traditionally processed bit by bit. In the experiment that this thesis based on, we followed the one-slipping method using LZD circuit to detect loop back times. Next, we use bit-parallel to generate mask hence to implement the second loop. Comparing to conventional method, the mask method saved AC around 10% time of execution with averagely 1.8 cycles to process a bin. Meanwhile, the thesis also integrates the three modes of Arithmetic Coding in one circuit in order to achieve the best hardware sharing. On the other hand, [3] also use prefix adder for renormalization. In order to lower the cost, we adopted shifter to remove MSB, take FSM for storing the status and eliminate two 10-bits adding circuits as result. Comparing with [3], that is about 50% of circuit saving. Overall, in respect of encoding, the implemented encoder can be operated at 333 MHz with gate counts at 13.3k, about 90% of the operation time of the traditional way. As for decoding, the decoder can also go up to 333 MHz with 16.7k gate counts. In short, this design fits in with the key feature of low-cost, high output.

Contents
中文摘要 iii
Abstract iv
誌謝 vi
Contents vii
Chapter 1 Introduction 1
1.0 Motivation 1
1.1 Related Work 1
1.2 Thesis Organization 3
Chapter 2 Algorithm review of Arithmetic Coder 4
2.0 Introduction 4
2.1 Arithmetic Coding 5
2.2 Binary Arithmetic Coding 8
Chapter 3 Flowchart of H.264 CABAC 14
3.0 Introduction 14
3.1 CABAC Binarization Schemes 16
3.2 Initialisation of Context Models 20
3.3 CABAC Context Modeling Schemes 22
3.3.1 An Example for Context Model of Syntax Element mvd 27
3.3.2 Another Example for Encoding Syntax Element coded_block_pattern 28
3.4 Arithmetic Coding Scheme 30
3.4.1.1 Encoding a Decision 31
3.4.1.2 Encoding a Bypass 32
3.4.1.3 Encoding a Termination 33
3.4.1.4 Renormalization in Encoding Engine 34
3.4.2.1 Arithmetic Decoding Process for a Binary Decision 35
3.4.2.2 Bypass Decoding Process for Binary Decision 35
3.4.2.3 Decoding a Termination 36
3.4.2.4 Renormalization Process in the Arithmetic Decoding Engine 37
Chapter 4 Architecture Design of H.264 CABAC 38
4.0 Architecture Design of CABAC 38
4.1 Architecture Design of Binarizer 41
4.1.1 TYPE 1 Binarizer 42
4.1.1 TYPE 2 Binarizer 43
4.2 Architecture Design of Context Modeler 45
4.3 Architecture Design of Arithmetic Coder 46
4.3.1 Architecture Design of Binary Arithmetic Coder 47
4.3.2 Architecture Design of Renormalization 49
4.3.3 Architecture Design of BitsPacking 52
4.3.4 Output FIFO 53
4.4 Architecture Design of Decoder 54
4.4.1 Architecture Design of Bitstream Organizer 54
4.4.2 Architecture Design of Context Modeler 55
4.4.3 Architecture Design of Arithmetic Decoder 55
4.4.3.1 Architecture Design of Binary Arithmetic Decoder 56
4.4.3.2 Architecture Design of Data Recovery Unit 58
Chapter 5 Design Methodology and Experimental Result 60
5.0 Design Flow 60
5.1 Experiment Result 61
5.1.1 Comparison AC with the Other 61
5.1.2 Experimental Result 61
Chapter 6 Conclusion 64
References 65

[1] ITU-T Rec. H.264 (2003 E) Advanced video coding for generic audiovisual services.
[2] Marpe. D, Schwarz. H, Wiegand. T, “Context-based adaptive binary arithmetic coding in the H.264/AVC video compression standard,” Circuits and Systems for Video Technology, IEEE Transactions on Volume 13, Issue 7, July 2003 Page(s):620 – 636.
[3] Osorio. R. R, Bruguera. J.D, “Arithmetic coding architecture for H.264/AVC CABAC compression system,” in Digital System Design 2004, on Euromicro Symposium on 31 Aug.-3 Sept. 2004 Page(s):62 – 69.
[4] Mrak. M, Marpe. D, Grgic. S, “Comparison of context-based adaptive binary arithmetic coders in video compression,” Video/Image Processing and Multimedia Communications, EURASIP Conference focused on Volume 1, 2-5 July 2003 Page(s):277 - 286.
[5] Marpe. D, Wiegand. T, “A highly efficient multiplication-free binary arithmetic coder and its application in video coding,” in Image Processing, International Conference on Volume 2, 14-17 Sept. 2003 Page(s):II - 263-6.
[6] Ghandi. M, Ghandi. M. M, Shamsollahi. M. B, “A novel context modeling scheme for motion vectors context-based arithmetic coding,” Electrical and Computer Engineering, Canadian Conference on Volume 4, 2-5 May 2004 Page(s):2021 - 2024 Vol.4.
[7] Pastuszak G., “A Novel Architecture of Arithmetic Coder in JPEG2000 Based on Parallel Symbol Encoding,” in Parallel Computing in Electrical Engineering, International Conference on 7-10 Sept. 2004 Page(s):303 – 308
[8] Qiang Peng, Jin Jing, “H.264 codec system-on-chip design and verification,” in ASIC, Proceedings, 5th International Conference on Volume 2, 21-24 Oct. 2003 Page(s):922 - 925 Vol.2.
[9] Mrak. M, Marpe. D, Wiegand. T, “A context modeling algorithm and its application in video compression,” in Image Processing, International Conference on Volume 3, 14-17 Sept. 2003 Page(s):III - 845-8 vol.2.
[10] Tamhankar. A, Rao. K. R, “An overview of H.264/MPEG-4 Part 10,” in Video/Image Processing and Multimedia Communications 2003. 4th EURASIP Conference focused on
Volume 1, 2-5 July 2003 Page(s):1 - 51 vol.1.
[11] Ha. V.H.S, Woo-Sung Shim, and Jung-Woo Kim, “Real-time MPEG-4 AVC/H.264 CABAC entropy coder,” in Consumer Electronics Digest of Technical Papers, International Conference on Jan. 8-12, 2005 Page(s):255 - 256