臺灣博碩士論文加值系統

摘 要

本論文主旨在影像系統中實現高產率的條件化可調性二位元算術解碼器。提出一個有效率處理殘值之三級管線化條件化可調性二位元算術解碼架構。所提出的架構包含三個主要的要素。第一個是內容模型引擎(context modeling engine)用來儲存及選擇在解碼單元中相關之機率。另一個是包含標準算術解碼器(regular arithmetic decoder)及旁道算術解碼器(bypass arithmetic decoder)之算術解碼器。最後一個是處理解碼完的位元之逆二元化映對(reverse binarization mapping)。為了簡化硬體的複雜度，我們引入一重新排列之內容模型。在算術解碼部分，針對打破遞回路徑(recursive path)使得在標準及旁道模式中之正規劃引擎(renormalization engine)關鍵路徑(critical path)得以縮短。提出逆二元化方法處理重建一包含特殊編碼案例之意義位元圖(significant map)。藉由針對k階哥倫布碼(EGk code)所提出之映對方法將二元化係數值之字尾碼(suffix codes)轉為原本語法元素(syntax elements)。以高產率目地，在考慮條件化可調性二位元算術解碼器最遭情況下設計此硬體。為了達成管線化之架構，我們事先把各引擎之執行時機的安排列入考慮。此架構利用UMC 0.18�慆的製程技術合成，能操作在高於200 MHz頻率下並且其產率為1 bit/clock，足以應付正常情況下的高解析視訊規格，此外，本架構透過ARM的發展平台進行軟硬體共同設計之驗證，其結果與軟體結果比較，得知本架構之正確性無誤。

Abstract

This thesis focuses on the implementation of the context-based adaptive binary arithmetic coding (CABAC) decoder with high throughputs in video coding systems. An efficient three-stage pipelined architecture of the CABAC decoder for residual data is proposed. The proposed design contains three major elements. First part is the context modeling engine which stores and selects the corresponding probabilities used in a decoding unit. Second part is the arithmetic decoders which contain the regular arithmetic decoder and the bypass arithmetic decoder. The last part is the reverse binarization mapping for the decoded bins. The rearrangement of the context models is introduced to simplify the hardware complexity. In the arithmetic decoding part, the recursive path was broken such that the critical paths of renormalization engines was reduced for both regular and bypass modes. With regard to the reverse binarization, a revere mapping function used in the significant map containing the special coding cases was proposed. The suffix codes of the binarizied coefficient levels are converted to the original syntax elements by the proposed mapping functions for EGk code. Designing the hardware is under the consideration of the high throughputs for the worse case of the CABAC. The arrangements of executing timing in every engine are considered in advance to achieve a pipelined architecture. The proposed architecture is synthesized with UMC 0.18 �慆 technology. The design can be operated at more than 200MHz and the throughput is one bit per clock. That is sufficient for the high resolutions video formats. The proposed design is also verified with the software/hardware co-design on the ARM development platform.

Table of Contents..................................................................... i
Acknowledgement .................................................................... iii
Abstract ............................................................................ vi
List of Figures ................................................................... viii
List of Tables ....................................................................... x

Chapter 1 Introduction ............................................................... 1
1.1 Motivation ...................................................................... 1
1.2 Organization for the Thesis ..................................................... 4

Chapter 2 Basic Concepts for Video Coding and Arithmetic Coding ...................... 5
2.1 Fundamental Concepts for Video Coding............................................ 6
2.2 The Hybrid DPCM/DCT Video Coding System.......................................... 9
2.2.1 Video Encoder: ............................................................... 10
2.2.2 Video Decoder:.................................................................11
2.3 Fundamental Concepts of Arithmetic Coding ...................................... 12
2.3.1 Preview Coding Process of Arithmetic Coding.................................. 13
2.3.1.1 Generating an Arithmetic Code:............................................ 13
2.3.1.1 Deciphering the Arithmetic Code .......................................... 16
2.3.2 Implementation Issue......................................................... 18

Chapter 3 Context-based Adaptive Binary Arithmetic Coding Algorithm ................. 20
3.1 Overview of CABAC Framework..................................................... 21
3.2 Binarization.................................................................... 23
3.2.1 Pre-Defined Binary Mapping Code:............................................. 24
3.2.2 Unary Code (U code): ........................................................ 31
3.2.3 Truncated Unary Code ( TU): ................................................. 32
3.2.4 k th Order Exp-Golomb Code:.................................................. 32
3.2.5 Fixed-Length Code Truncated Unary Code: ..................................... 33
3.2.6 Concatenation of Fundamental Binarization Schemes: .......................... 34
3.3 Context Modeling ............................................................... 37
3.3.1 Coded Block Flag: ........................................................... 39
3.3.2 Significant Map Process: .................................................... 40
3.3.3 Coefficient Levels Information: ............................................. 43
3.3.4 Adaptive Binary Arithmetic Coder: ........................................... 45
3.3.5 Probability Estimation in CABAC: ............................................ 49
3.3.6 Initialization of the Probability Index:..................................... 52
3.3.7 Termination of Arithmetic Codeword:.......................................... 64
3.3.8 Concept of the CABAC Systems:................................................ 69
3.3.8.1 Encoder: ................................................................. 69
3.3.8.2 Decoder: ................................................................. 69

Chapter 4 High Throughput Pipeline Context-Based Adaptive Binary Arithmetic Decoder...72
4.1 Overview of Coding Flow of the Residual Data inside the 4 × 4 blocks:........... 75
4.2 Context Modeling Stage:......................................................... 79
4.3 Propose Context Model Selector:................................................. 86
4.4 Arithmetic Decoder:............................................................. 98
4.5 Debinarization Stage:.......................................................... 106
4.5.1 Debinarization for Significant Map: ........................................ 106
4.5.2 Debinarization for Level Information:....................................... 108

Chapter 5 Verification and Experimental Results .....................................112
5.1 Verification....................................................................112
5.1.1 Verification Environment ....................................................112
5.1.2 RAM-based Interface Connection ..............................................113
5.1.3 Simulations..................................................................116
5.2 Experimental Result and Comparison .............................................119
5.3 Summary ....................................................................... 121

Chapter 6 Conclusions and Future Work .............................................. 122
6.1 Conclusions ................................................................... 122
6.2 Future Work ................................................................... 123
References ......................................................................... 125

[1] ITU-T Recommendation H.261, "Video codec for audiovisual services at p X 64kbit/s," Mar. 1993.
[2] ITU-T Recommendation H.263, "Video coding for low bitrate communications, version 1," 1995.
[3] ISO/IEC 11172: "Information technology-coding of moving pictures and associated audio for digital storage media at up to about 1.5 Mbit/s," Geneva, 1993.
[4] ISO/IEC 13818-2: "Generic coding of moving pictures and associated audio information-part 2: video," ITU-T and ISO/IEC JTC1, ITU-T Recommendation H.262-ISO/IEC 13 818-2 (MPEG-2), 1994.
[5] "Coding of audio-visual objects-part 2: visual," ISO/IEC JTC1, ISO/IEC 14 496-2 (MPEG-4 Visual version 1), Apr. 1999; Amendment 1 (version 2), Feb. 2000; Amendment 4 (streaming profile), Jan. 2001.
[6] "Draft ITU-T recommendation H.264 and draft ISO/IEC 14 496-10 AVC," in Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-T SG16/Q.6 Doc. JVT-G050, T. Wieg, Ed., Pattaya, Thailand, Mar. 2003.
[7] D. Marpe, G. Blattermann, and T. Wiegand, "AdaptiveCodesfor H.26L,", Eibsee, Germany, ITU-TSG16/Q.6 Doc.VCEG-L13,2001.
[8] D. Marpe, G. Blattermann, G. Heising, and T.Wiegand, "Further Results for CABAC Entropy Coding Scheme,", Austin, TX, ITU-T SG16/Q.6
[9] D. Marpe, G. Blattermann, and T. Wiegand, "Improved CABAC,", Pattaya, Thailand, ITU-T SG16/Q.6 Doc. VCEG-O18, 2001.
[10] D. Marpe, G. Blattermann, T. Wiegand, R. Kurceren, M. Karczewicz, and J. Lainema, "New results on improved CABAC," in Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-T SG16/Q.6 Doc. JVTB101, Geneva, Switzerland, Feb. 2002.
[11] H. Schwarz, D. Marpe, G. Blattermann, and T. Wiegand, "Improved CABAC," in Joint Video Team of ISO/IEC JTC1/SC29/WG11& ITU-T SG16/Q.6 Doc. JVT-C060, Fairfax, VA, Mar. 2002.
[12] D. Marpe, G. Heising, G. Blattermann, and T. Wiegand, "Fast arithmetic coding for CABAC," in Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-T SG16/Q.6 Doc. JVT-C061, Fairfax, VA, Mar. 2002.
[13] H. Schwarz, D. Marpe, and T. Wiegand, "CABAC and slices," in Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-T SG16/Q.6 Doc. JVT-D020, Klagenfurt, Austria, July 2002.
[14] M. Karczewicz, "Analysis and simplification of intra prediction," in Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-T SG16/Q.6 Doc. JVT-D025, Klagenfurt, Austria, July 2002.
[15] D. Marpe, G. Blattermann, G. Heising, and T. Wiegand, "Proposed cleanup changes for CABAC," in Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-T SG16/Q.6 Doc. JVT-E059, Geneva, Switzerland, Oct. 2002.
[16] F. Bossen, "CABAC cleanup and complexity reduction," in Joint Video Team of ISO/IEC JTC1/SC29/WG11 & ITU-T SG16/Q.6 Doc. JVTE086, Geneva, Switzerland, Oct. 2002.
[17] D. Marpe, H. Schwarz, G. Blattermann, and T.Wiegand, "Final CABAC cleanup," in Joint Video Team of ISO/IEC TC1/SC29/WG11 & ITU-T SG16/Q.6 Doc. JVT-F039, Awaji, Japan, Dec. 2002.
[18] D. Marpe, G. Blattermann, G. Heising, and T. Wiegand, "Video compression using context-based adaptive arithmetic coding," in Proc. IEEE Int. Conf. on Image Processing, Vol. III, pp. 558-561, Oct. 2001.
[19] D. Marpe, H. Schwarz, G. Blattermann, G. Heising, and T. Wiegand, "Context-based adaptive binary arithmetic coding in JVT/H.26L," in Proc. IEEE Int. Conf. on Image Processing , Vol. II, Sep. 2002, pp. 513-516.
[20] D. Marpe and T. Wiegand, "A highly efficient multiplication-free binary Arithmetic coder and its in video coding," in Proc. IEEE Int. Conf. on Image Processing, Barcelona, Spain, pp.263-266, Sept. 2003.
[21] M. Mrak, D. Marpe, and T. Wiegand, "A context modeling algorithm and its application in video compression," in Proc. IEEE Int. Conf. on Image Processing, Barcelona, Spain, pp.845-848, Sept. 2003.
[22] D. Marpe, H. Schwarz, and T. Wiegand, "Context-based adaptive binary Arithmetic coding in the H.264 / AVC video compression standard," IEEE Trans. Circuits Syst. Video Technol., vol. 13, no. 7, pp. 620-636, July 2003.
[23] J. Ostermann, J. Bormans, P. List, D. Marpe, M. Narroschke, F. Pereira, T. Stockhammer, and T. Wedi, "Video coding with H.264 / AVC: tools, performance, and complexity," IEEE Circuits and Systems Magazine, vol. 4, no. 1, pp. 7-28, Apr. 2004.
[24] J.W. Chen, C.R. Chang, Y.L. Lin, "A hardware accelerator for context-based adaptive binary arithmetic decoding in H.264/AVC," in Proc. IEEE ISCAS, pp.4525-4528, May 2005.
[25] I. E. G. Richardson, Video CODEC Design: Developing Image and Video Compression Systems. Chichester, UK: John Wiley & Sons, 2003.
[26] I. E. G. Richardson, H.264 and MPEG-4 video compression: Video Coding for Next Generation Multimedia. Chichester, UK: John Wiley & Sons, 2003.
[27] G. G. Langdon, Jr., "An introduction to arithmetic coding," IBM J. Res. Dev.,1987.
[28] K. Sayood, Introduction to Data Compression. San Francisco, CA, USA: Morgan Kaufmann, 2000.