臺灣博碩士論文加值系統

隨著網際網路和數位相機快速發展，靜態數位影像廣泛地使用於儲存與傳輸媒介。JPEG2000 是一種較新的靜態影像壓縮標準，它比目前使用的JPEG標準有更好的壓縮率，並且提供很多實用特徵。然而這些有用特徵相對的也需要更複雜的運算量與硬體資源。對於JPEG2000編碼器而言，EBCOT Tier-1的Context Formation Encoder是複雜度最高的模組。為了要改善它的效能，Pass-Parallel 架構是目前最有效率的方法之一。在本論文中，我們提出一個高效能且低功率的JPEG2000 Context Formation 方塊編碼器架構。我們藉由三種加速方法並使用管線化技巧來實現新的硬體架構。使用Dual Column Pass1 generation method，Pass-Parallel Column-Based區塊編碼器所需的context window與目前存在的技術比較，面積可降低25%。使用Dual Column Pass1 generation method，all coding pass and significance change generation method 和 sample-parallel column-based coding method，可將整個系統架構的critical path降低。所提的新硬體架構可加快運算效率和減少編碼所需的硬體電路。最後我們利用Verilog硬體描述語言描述我們的架構並且使用Synopsys Design Compiler以TSMC CMOS 0.25μm製程合成後，pre-layout晶片面積大小為 40037μm2，工作頻率可以到達330 MHz，處理一張2304 × 1728的灰階影像時，編碼時間為0.021秒。

As the prompt development of Internet and digital still camera (DSC), still image is broadly used as storage and transmission contents. JPEG2000 is a relatively new still image compression standard. It has better compression performance than conventional JPEG standard, and it provides many useful features. However, these features require more complex computations and hardware resources. The Context Formation Encoder of EBCOT tire-1 is of high complexity in a JPEG2000 encoder. To improve performance, the Pass-Parallel architecture is one of the most efficient methods. In this thesis, a high performance and low-power hardware architecture design of Context Formation encoder for JPEG2000 is proposed. The new hardware architecture is implemented by three speedup methods and pipeline technique. The area of context window of Pass-Parallel Column-Based context formation encoder is reduced by 25% using the proposed Dual Column Pass1 generation method in comparison with existing techniques. The critical path of overall system architecture is reduced employing dual column pass1 generation, all coding pass and significance change generation method and sample-parallel column-based coding method. The new architecture is proposed to improve the computation efficiency and reduce hardware area in pass coding operations. Finally, Our design is described with Verilog HDL code and synthesized by Synopsys Design Compiler using TSMC CMOS 0.25μm process. The pre-layout synthesized area is 40037 μm2. In our simulation, the operation clock frequency can reach 330 MHz. With this clock frequency, it needs 0.021 second to encode an image with 2304 x 1728 image size.

Contents

Abstract (Chinese)....……..………………………………..……..……………………………………..i
Abstract (English)..….……………..…………………………………….……………………………..ii
Acknowledgements..…………………………………………………...…...………………………….iii
Contents.…………………………………………………………….....……………………………….iv
List of tables.…………………………………………………………..…………………………..…..vii
List of figures.……………………………………………………………………..…………………...ix
CHAPTER 1 INTRODUCTION………………………………………………………..………….1
1.1 JPEG2000 Encoder Overview……………………………………………………………..1
1.2 Research Motivation……………………………………………………………………….4
1.3 Thesis Organization…………………………………………………………………..……5
CHAPTER 2 ANALYSIS OF BASIC EBCOT TIER-1 CONTEXT
FORMATION ENCODER…………………………………………………………..7
2.1 Coding Order and Five Coding State Variables…………………………………………7
2.1.1 Coding Scan Order…………………………………………………………………….7
2.1.2 Five Coding State Variables…………………………………………………………...9
2.2 Four Coding Operations………………………………………………………………..11
2.3 Three Coding Passes…………………………………………………………………...18
CHAPTER 3 ANALYSIS OF PASS-PARALLEL EBCOT TIER-1 CONTEXT
FORMATION ENCODER………………………………………………………...23
3.1 The Core of Pass-Parallel Context Formation Architecture…………………………...23
3.2 Sample-Based Operation for Pass-Parallel …………………………….……………...27
3.3 Column-Based Operation for Pass-Parallel …………………………………………...31




CHAPTER 4 PROPOSED HIGH-SPEED AND SMALL-AREA PASS-PARALLEL CONTEXT FORMATION METHODS…………………………………………..38
4.1 Dual Column Pass1 Generation Method……………………………………….….…..41
4.1.1 Pre-Processing for Pass1 Generation of Samples in Register B………………….….44
4.1.2 Horizontal Processing for Pass1 Generation of Samples in Register B…….…….….47
4.1.3 Vertical Processing for Pass1 Generation of Samples in Register B………….….….49
4.2 All Coding Pass and Significance Change Generation Method……………………….51
4.3 Sample-Parallel Column-Based Coding Method………………………….…………...56
4.3.1 MRC Coding Expression for Sample C1 to C4 in Register C for Pass2……….……58
4.3.2 Zero Coding Expression of Sharing Between Pass1 and Pass3
for Sample C1 to C4 in Register C………………………………………….….….…62
4.3.3 Sign Coding Expression of Sharing Between Pass1 and Pass3
for Sample C1 to C4 in Register C……………………………………………..….…66
4.3.4 Run-Length Coding Expression for Sample C1 to C4 in Register C for Pass3……...72

CHAPTER 5 ARCHITECTURE DESIGN AND EXPERIMENT RESULTS…………………73
5.1 Overall Architecture of Pass-Parallel Context Formation Encoder with
High Speed and Small Area…………………………………………………………………73
5.2 Detailed Internal Structure of Pass-Parallel Context Formation Encoder
with High Speed and Small Area………..…………………………………………….82
5.2.1 Detailed Hardware Description of the Dual Column Pass1 Generation……………84
5.2.2 Detailed Hardware Description of all Coding Pass and
Significance Change Generation…………...……………………………………….84
5.2.3 Detailed Description of Fast Sample-Parallel Column-Based Coding……………..85
5.3 Analysis of Critical Path of CF Overall Architecture Proposed………………………87
5.4 Design Flow and Verification……………………………………………………..…...93
5.5 Experiment Results………………………………………………………………….…95

CHAPTER 6 CONCLUSION……………………………………………………………………..97
BIBLIOGRAPHY…………………………………………………………………………………….98
APPENDIX…………………………………………………………………………………………..100

A.1 The hardware description language of overall system top level of context formation proposed…………………..………….………………………………………………100
A.2 The hardware description language of dual column pass1generation………….……108
A.3 The hardware description language of all coding pass generation and significance change………………………………………………………………………………...111
A.4 The hardware description language of the magnitude refinement coding ….……….113
A.5 The hardware description language of the zero coding for pass1 coding operation or pass3 coding operation…….…………………………………………………………117
A.6 The hardware description language of the sign coding for pass1 coding operation or pass3 coding operation………………..………….…………………………………..121
A.7 Design Compiler Script File…………………..………….………………………….125
A.8 Gate-Level Netlist…………………………..…………….………………………….126
A.9 Cell list……………………….……………………..………………………………..179
A.10 Hardware Area Size…………………….………………..…………………………..183
























List of Tables
Table 1-1. Profile of Run Time Percentage (%) of JPEG2000…………………………………………5
Table 2-1. Neighbor significance states for context label generation………………………………...11
Table 2-2. Context Table for Zero Coding……………………………………………………………12
Table 2-3. Table of Horizontal contribution………………………………………………………….14
Table 2-4. Table of Vertical contribution…………………………………………………………….14
Table 2-5. Context table for Sign Coding…………………………………………………………….15
Table 2-6. Context table for Magnitude Refinement Coding…………………………………………16
Table 2-7. Context table for Run-Length Code 0…………………………………………………….17
Table 2-8. Context table for Run-Length Code 1 with uniform coding………………………………17
Table 3-1. The neighbor significance states of register B1 for pass1……………………………….29
Table 3-2. The neighbor significance states of register B1 for pass2………………………………..30
Table 3-3. The neighbor significance states of register D1 for pass3………………………………..30
Table 3-4. The neighbor significance states of column-based sample B1 for pass1………………...33
Table 3-5. The neighbor significance states of column-based sample B2 for pass1………………...34
Table 3-6. The neighbor significance states of column-based sample B3 for pass1………………...34
Table 3-7. The neighbor significance states of column-based sample B4 for pass1………………...34
Table 3-8. The neighbor significance states of column-based sample B1 for pass2………………...35
Table 3-9. The neighbor significance states of column-based sample B2 for pass2………………...35
Table 3-10. The neighbor significance states of column-based sample B3 for pass2………………...35
Table 3-11. The neighbor significance states of column-based sample B4 for pass2………………...36
Table 3-12. The neighbor significance states of column-based sample D1 for pass3………………..36
Table 3-13. The neighbor significance states of column-based sample D2 for pass3………………..36
Table 3-14. The neighbor significance states of column-based sample D3 for pass3………………..37
Table 3-15. The neighbor significance states of column-based sample D4 for pass3………………..37
Table 4-1. Neighbor significance states of sample B1 for pre-processing…………………………..45
Table 4-2. Neighbor significance states of sample B2 for pre-processing…………………………..45
Table 4-3. Neighbor significance states of sample B3 for pre-processing…………………………..46
Table 4-4. Neighbor significance states of sample B4 for pre-processing………………………….46
Table 4-5. Neighbor significance states of sample B1 for horizontal processing…………………...47
Table 4-6. Neighbor significance states of sample B2 for horizontal processing…………………...48
Table 4-7. Neighbor significance states of sample B3 for horizontal processing…………………...48
Table 4-8. New neighbor significance states of sample B4………………………………………...49
Table 4-9. Neighbor significance states of sample B1 for vertical processing……………………..49
Table 4-10. Neighbor significance states of sample B2 for vertical processing……………………...50
Table 4-11. Neighbor significance states of sample B3 for vertical processing……………………...50
Table 4-12. Neighbor significance states of sample B4 for vertical processing………………………51
Table 4-13. Neighbor significance states of sample C1 for MRC……………………………………60
Table 4-14. Neighbor significance states of sample C2 for MRC……………………………………61
Table 4-15. Neighbor significance states of sample C3 for MRC…………………………………….61
Table 4-16. Neighbor significance states of sample C4 for MRC……………………………………62
Table 4-17. Neighbor significance states of sample C1 for ZC……………………………………….64
Table 4-18. Neighbor significance states of sample C2 for ZC………………………………………65
Table 4-19. Neighbor significance states of sample C3 for ZC……………………………………….65
Table 4-20. Neighbor significance states of sample C4 for ZC……………………………………….66
Table 4-21. Neighbor significance states of sample C1 for SC……………………………………….69
Table 4-22. Neighbor sign states of sample C1 for SC……………………………………………….69
Table 4-23. Neighbor significance states of sample C2 for SC……………………………………….70
Table 4-24. Neighbor sign states of sample C2 for SC………………………………………………..70
Table 4-25. Neighbor significance states of sample C3 for SC……………………………………….71
Table 4-26. Neighbor sign states of sample C3 for SC……………………………………………….71
Table 4-27. Neighbor significance states of sample C4 for SC……………………………………….72
Table 4-28. Neighbor sign states of sample C4 for SC………………………………………………..72
Table 5-1. Function of the input signal, proposed architecture………………………………………75
Table 5-2. Function of the output signal, proposed architecture……………………………………..77
Table 5-3. Performance of proposed design………………………………………………………….95
Table 5-4. Performance comparison of Context Formation encoders………………………………95
















List of Figures
Figure 1-1. The system structure of JPEG2000 encoder.………………………………………………2
Figure 2-1. Bit planes in a code block and scan order………………………………………………….7
Figure 2-2. Stripes in a bit-plane and scan order……………………………………………………….8
Figure 2-3. (a) Columns in a stripe and scan order (b) Samples in a column and scan order………... 8
Figure 2-4. Wavelet coefficients in sign-magnitude representation……………………………………9
Figure 2-5. Neighbor significance and sign states for sign coding…………………………………...13
Figure 2-6. Order of coding operations of three passes………………………………………………18
Figure 2-7. Checking of pass coding operation of sample X in context window…………………….19
Figure 2-8. Neighbor significance states of samples X1 to X4 for Pass3……………………………22
Figure 3-1. Two Pass-Parallel column-based 5x3 shift register arrays for significance states S1,S3 and sign state X0……………………………………………………………………………...25
Figure 3-2. Pass-Parallel column-based shift register array (6x5)……………………………………26
Figure 3-3. Pass-Parallel sample-based shift register array (3x5) for
significance states S1, S3 and sign state X0……………………………………………..28
Figure 3-4. Pass-Parallel sample-based 1X5 shift register for magnitude state V0…………………..29
Figure 3-5. Pass-Parallel column-based shift register array (5x5) for
significance states S1, S3 and sign state X0……………………………………………..31
Figure 3-6. Pass-Parallel column-based shift register array (4x5) for magnitude state V0…………..32
Figure 3-7. Pass-Parallel sample-parallel shift register array (5x5)………………………………….33
Figure 4-1. Pass-Parallel Column-Based shift register array (5x4) proposed for static significance states S1,S3 and sign state X0……………………………………………………………39
Figure 4-2. Pass-Parallel column-based shift register array (4x4) proposed for magnitude state V0..40
Figure 4-3. A 5X3 shift register context window for Dual Column Pass1 generation method………42
Figure 4-4. Shift register array of state variables used in Dual Column Pass1 generation (a) ; (b) static significance states S1, S3 ; (c) Magnitude state V0……………………………………..43
Figure 4-5. A 5X3 shift register context window for generating all coding pass information and significance change of Pass1 or Pass3…………………………………………………...52
Figure 4-6. Shift register array for state variables used in generating all coding pass
(a) ; (b) Static significance states S1, S3 ; (c) Magnitude state V0………………………53
Figure 4-7. All static significance state and dynamic significance state used in MRC, SC and ZC…58
Figure 4-8. Hard-macro of magnitude refinement coding……………………………………………59
Figure 4-9. Hard-macro of zero coding………………………………………………………………63
Figure 4-10. Hard-macro of sign coding……………………………………………………………..67


Figure 5-1. Overall architecture of Pass-Parallel Context Formation Encoder with high speed and small area………………………………………………………………………………...74
Figure 5-2. Detailed internal structure of Pass-Parallel Context Formation Encoder with high speed and small area……………………………………………………………………………83
Figure 5-3. Detailed block circuit of Dual Column Pass1 generation………………………………..84
Figure 5-4. Top circuit of CF for searching gate delay of the second stage………………………….87
Figure 5-5. Circuit of pre-processing…………………………………………………………………88
Figure 5-6. Circuit of horizontal processing………………………………………………………….88
Figure 5-7. Circuit of vertical processing…………………………………………………………….89
Figure 5-8. Top level circuit for searching gate delay of the third stage……………………………..89
Figure 5-9. Circuit of all coding pass and significance change generation…………………………..90
Figure 5-10. Circuit of zero coding for pass1 or pass3……………………………………………….91
Figure 5-11. Internal circuit of zero coding…………………………………………………………..92
Figure 5-12. Circuit of sign coding for pass1 or pass3……………………………………………….92
Figure 5-13. Internal circuit of sign coding…………………………………………………………..93
Figure 5-14 . Flow chart of cell-based design………………………………………………………...93

BIBLIOGRAPHY
[1] D. Taubman and M. W. Marcellin, JPEG2000 Image Compression Fundamentals, Standards and Practice, Kluwer Academic Publishers, 2002.
[2] ISO/IEC JTC1/SC29 WG 1 N1684, “JPEG2000 PartⅠ Final Committee Draft Version 1.0,” March 2000.
[3] ISO/IEC JTC1/SC29 WG 1 N1894, “JPEG 2000 Verification Model 8.6,” 2000.
[4] K.Andra, C.Chakrabarti and T.Acharya, “A High Performance JPEG2000 Architecture,” Circuits and Systems, 2002. ISCAS 2002. IEEE International Symposium on, vol.1,26-29 May 2002, Page(s): I-765 - I-768.
[5] D. Taubman, “High Performance scalable image compression with EBCOT,” IEEE Trans., Image Processing, vol. 9, issue 7, July 2000, Page(s):1158 –1170.
[6] Kuan-Fu Chen, Chung-Jr Lian, Hong-Hui Chen and Liang-Gee Chen, “Analysis and Architecture Design of EBCOT for JPEG 2000,” Circuits and Systems, 2001. ISCAS 2001. IEEE International Symposium on, Volume: 2, 2001, Page(s): 765 –768.
[7] Chung-Jr Lian, Kuan-Fu Chen, Hong-Hui Chen, and Liang-G.ee Chen, “Analysis and Architecture Design of Block-Coding Engine for EBCOT in JPEG 2000,” Circuits and Systems for Video Technology, IEEE Transactions on, Volume: 13, Issue:3, March 2003, Page(s) : 219 –230.
[8] Jen-Shiun Chiang, Yu-Sen Lin, and Chang-Yo Hsieh, “Efficient Pass-Parallel Architecture for EBCOT in JPEG2000,” Circuits and Systems, 2002. ISCAS 2002. IEEE International Symposium on, Volume: 1, 2002, Page(s): 773 -776.
[9] Hung-Chi Fang, Tu-Chih Wang, Chung-Jr Lian, Te-Hao Chang, Liang-G.ee Chen, “HGH SPEED MEMORY EFFICIENT EBCOT Architecture for JPEG2000,” Circuits and Systems, 2003. ISCAS 2003. IEEE International Symposium on, Volume: 2 , 2003, Page(s): 736 -739.
[10] Jen-Shiun Chiang, Chun-Hau Chang, Yu-Sen Lin, Chang-You Hsieh, and Chih-Hsien Hsia, “High-Speed EBCOT with Dual Context-Modeling Coding Architecture for JPEG2000,” Circuits and Systems, 2004. ISCAS 2004. IEEE International Symposium , Volume: 3, 2004, Page(s): 865 -868.
[11] Yun-Tai Hsiao, Hung-Der Lin, Kun-Bin Lee and Chein-Wei Jen, “High-Speed Memory-Saving Architecture for the Embedded Block Coding in JPEG2000,”Circuits and Systems, 2002. IEEE International Symposium on, Volume : 5, 2002, Page(s): 128 –136.
[12] Yijun Li, Ramy E. Aly, M. A. Bayoumi and S. A. Mashali, “Parallel High-Speed Architecture for EBCOT in JPEG2000,” Acoustics, Speech, and Signal Processing, 2003. Proceedings. 2003 IEEE International Conference on, Volume: 2, April 6 - 10, 2003, Page(s) 481 -484.
[13] Chi-Chin Chang, Sau-Gee Chen, “Efficient Design of JPEG2000 EBCOT TIER-I
Context Formation Encoder,“ Master Thesis, NCTU, January 2006.
[14] Pei-Chun Chen, Bin-Fei Wu, “Design of the efficient Pass-Parallel Context Formation Codec for JPEG2000,“ Master Thesis, NCTU, July 2004.
[15] Amit Kumar Gupta, David Taubman, Saeid Nooshabadi, “High Speed VLSI Architecture for Bit Plane Encoder of JPEG2000,” Circuits and Systems, 2004. ISCAS 2004. IEEE International Symposium on, vol. 2, 2004, Page(s): 233 -236.
[16] Yan Xiaolang, Qin Xing, Yang Ye, Ge,Haitong, “A High Performance Architecture of EBCOT Encoder in JPEG2000 ,” Circuits and Systems, 2005. ISCAS 2005. IEEE International Symposium, Page(s) 492-495.
[17] Tsung-Han Tsai and Lian-Tsung Tsai, “JPEG2000 Encoder Architecture Design with Fast EBCOT Algorithm,” Circuits and Systems, 2005. ISCAS 2005. IEEE International Symposium, Page(s) 279-282.
[18] Yijun Li and Magdy Bayoumi, “THREE-Level Parallel High Speed Architecture for EBCOT in JPEG2000,” Circuits and Systems, 2005. ISCAS 2005. IEEE International Symposium, Page(s) V-5 – V-8.
[19] Jasper Software, http://www.ece.uvic.ca/~mdadams/jasper.