一種適用於低功率高效能NRZI資料傳輸之新Huffman 編碼機制

簡易檢索 / 詳目顯示

回結果列表

研究生：	盧淑萍 Shu-ping Lu
論文名稱：	一種適用於低功率高效能NRZI資料傳輸之新Huffman 編碼機制 A New Huffman Encoding Scheme for Low Power High Performance NRZI Based Data Transmission
指導教授：	阮聖彰 Shanq-Jang Ruan
口試委員:	陳維美 Wei-Mei Chen 許孟超 Mon-Chau Shie 林昌鴻 Chang-Hong Lin
學位類別：	碩士 Master
系所名稱：	電資學院 - 電子工程系 Department of Electronic and Computer Engineering
論文出版年：	2008
畢業學年度：	97
語文別：	英文
論文頁數：	77
中文關鍵詞：	JPEG 、資料傳輸、影像壓縮、低功率、Huffman 編碼器
外文關鍵詞：	JPEG, data transmission, image compression, low-power, Huffman encoder
相關次數：	點閱：196 下載：2
分享至:	分享至facebook 分享至twitter

查詢本校圖書館目錄查詢臺灣博碩士論文知識加值系統勘誤回報

近年來，隨著多媒體技術的快速發展，影像與影音壓縮在網路上更被廣為使用。低功率的影像壓縮與資料傳輸技術已成為十分熱門的議題。然而，如何使得壓縮後的影像與影音資料在傳輸時能達到低功率，卻鮮少被研究與提出。對於影像而言，雖然資料通常只被壓縮一次，但壓縮後的資料在網路上卻經常地被使用與傳輸著。由此可知，資料在傳輸時所消耗的功率不容被忽視。有鑒於此，針對這些問題，我們改進了JPEG 的Huffman 編碼器，以使得壓縮後的資料在傳輸時能達到低功率的效果。

由於Huffman 編碼器為諸多影像壓縮流程的最後一個步驟，所以對傳輸資料行為的影響最為直接。另ㄧ方面，NRZI 編碼器為許多通訊系統所採行的第一個步驟。因此，本篇論文提出了一個根據改良Huffman 編碼器，使得資料在傳輸時能達到低功率的方法。為了能符
合NRZI 編碼器的條件，我們提出了一個新的且可使用在影像與影音的Huffman 表。

本研究使用許多在影像處理領域中，不同的標準圖片做為測試。實驗結果顯示，與JPEG 標準的壓縮方法比較時，本論文在減少NRZI bit stuffing 上比JPEG 標準方法降低了22.05 到83.95 的百分比。因此可以發現，資料在經過本論文所提出的編碼過程處理後，其資料量會比經JPEG 標準壓縮後的資料更為減小。換句話說，經實驗結果證實，本研究有使壓縮後的資料在傳輸時，具有降低消耗功率的能力。由此可知，在相同的資料壓縮率之下，本論文提出了一個可使得資料在傳輸時的減少能量消耗的方法。

With the rapid growth of multimedia processing technologies, image and video compression are widely used on the network access. In recent years, there has been increased interest in the field of low power image compression and data transmission. Few studies, however, about low power data transmission for compressed image and video were presented. The compressed files are frequently transmitted on the network even though an image is usually compressed only once. For this reason, we can not neglect the power dissipation during transmitting data on the network. In order to overcome these difficulties, we improve the Huffman encoder of the JPEG flow to
make the compressed data low power on transmission.

Huffman encoder affects the behavior of transmission data directly since it is adopted as the last step of well-known image and video standards. On the other hand, Non Return to Zero, Inverted (NRZI) encoder is the first step in many telecommunication systems. In this thesis, thus, a low power data transmission scheme for NRZI based on Huffman encoding is presented. We propose a new Huffman table for the image and video compression to match NRZI encoder for reducing bit stuffing to achieve low power on data transmission.

Simulation results test several images used by image processing research community. Our practical results indicate that the reduction rate in NRZI bit stuffing is from 22.05% to 83.95% compared with the standard JPEG compression. Therefore, it is observation that the file size after the proposed encoding process is less than that of the standard one. In other words, the compressed results can reduce power consumption during data transmission. The method provides a way to minimize the transmitted power under the same compression ratio.

Table of Contents
Table of Contents                                                            iv

List of Tables                                                               vi

List of Figures                                                             vii

Abstract                                                                   viii

Acknowledgements                                                              x

Introduction                                                                1

Preliminaries                                                               7
1 Related Works . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.1 Huffman Coding . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.2 NRZI Encoding . . . . . . . . . . . . . . . . . . . . . . . . . .  9
1.3 JPEG Compression . . . . . . . . . . . . . . . . . . . . . . . .  12
1.4 The Source of Power Dissipation . . . . . . . . . . . . . . . . . 24
2 Motivation . . . . . .. . .  . . . . . . . . . . . . . . . . . . . . . 26

Modified Huffman Encoder for Low Power Data Transmission                   27
1 Key Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2 Modified Huffman Encoder for Low Power Data Transmission .. . . ..  . .31
2.1 The Overall Modification Process of The Huffman Tree . . . . . .  32
2.2 Creation of MAC Tree with The Effect of VLI Consideration . . . . 32
2.3 Grouping of MAC Tree . . . . . . . . .  . . . . . . . . . . . . . 33
2.4 Evaluation of Probabilities with NRZI Bit Stuffing Consideration. 34
2.5 Tuning of MAC Tree . . . . . . . . . . . . . . . . . . . . .  . . 38
2.6 Transformation into Modified Huffman Tree . . . . . . . . . . . . 39

Performance Evaluation                                                     42
1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . . . . 43
2 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . 44

Conclusion                                                                 55

Bibliography                                                                 56




              List of Tables
1 Typical Luminance Uniform Quantization Table . . . . . . . . . . . . . . 17
2 Huffman Table for DC Coefficients . . . . . . . . .  . . . . . . . . . . 22
3 Huffman Table for AC Coefficients . . . . . .. . . . . . . . . . . . . . 23
1 The probability of Within(Group) . . . . . . . . . . . . . . . . . . . . 38
2 The probability of Between head(Group) . . . . . .. . . . . . . . . . .  39
3 The probability of Between tail(Group) . . . . . . . . . . . . . . . . . 40
4 The probability of Pr(Group) . . . . . . . . . . . . . . . . . . . . . . 41
1 Test some images of lower resolution using JPEG standard method and our proposed method . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . 46
2 Test some images of higher resolution using JPEG standard method and our proposed method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  47
3 Test other standard images, part1 . . . . . . .  . . . . . . . . . . . . 49
4 Test other standard images, part2 . . . . . . . . . . . . . . . .. . . . 50
5 Test Baboon with different quality . . . . . . . . . . . . . . . . . . . 51
6 Test Peppers with different quality . . . . . . . .. . . . . . . . . . . 52
7 Test Lena with different quality . . . . . . . . . . . . . . . . . . . . 52
8 Test Airplane with different quality . . . . . . . . . . . . . . . . . . 53
9 Test Splash with different quality . . . . . . . . . . . . . . . . . . . 53
10 Test Testpat with different quality . . . . . . . . . . . . . . . . . . 54


              List of Figures
1 The Relationship Between Huffman Encoder and NRZI Encoder . . . . . . . . 5
1 Huffman Coding . . . . . . . . . . . . . . . . . . . . . . . . .  . . . . 9
2 NRZI Encoding Data . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3 NRZI Bit Stuffing . . . . . . . . . . . . . . . . . . . .. . . . . . . . 12
4 JPEG Block Diagram . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
5 RGB to YCbCr Conversion . . . . . . . . . .  . . . . . . . . . . . . .   14
6 A Transformation from Spatial Domain to Frequency Domain by DCT . . .. . 15
7 Frequency and Direction Distributions of 2-D DCT . . . . . . . . . . . . 16
8 JPEG Quantization Example . . . . . . . . . . . . . .  . . . . . . . . . 18
9 JPEG Entropy Coding Flowchart . . . . . . . . . . . .  . . . . . . . . . 19
10 JPEG Zigzag Sequence . . . . . . . . . . . . . . . . . . . . . . .. . . 20
11 DC Coefficients using Difference Encoding . . . . . . . . . . . . . . . 21
12 JPEG Bitstream . . . . . . . . . . . . . .. . . . . . . . . . . . . . . 24
1 An Example of Exchanging VLCs . . . . . . . . . . . . . . . . . . . . .  28
2 An Illustration of Key Idea . . . . . . . . . . . . . . . . . . .. . . . 29
3 An Example of Calculating Pr(ga) . . . . . . . . . . . . . . . . . .   . 37

                                

[1] De Maria Elio A. A., Edgardo Gho, Carlos E. Maidana, Fernando I. Szklanny,
and Hugo R. Tantignone, A low cost fpga based usb device core, IEEE 2008
4th Southern Conference on Programmable Logic, March 2008, pp. 149–154.
[2] Don Anderson, Usb system architecture, Addison-Wesley, 1997.
[3] Jan Axelson, Usb complete: Everything you need to develop custom usb
peripherals, lakeview research llc, 2005.
[4] Nilanjan Banerjee, Georgios Karakonstantis, and Kaushik Roy, Process
variation tolerant low power dct architecture, IEEE in Design, Automation
and Test in Europe Conference and Exhibition, April 2007, pp. 1–6.
[5] Jan Bormans, Jean Gelissen, and Andrew Perkis, Mpeg-21: The 21st century
multimedia framework, IEEE Signal Process. Mag., vol. 20, Mar. 2003, pp.
53–62.
[6] Ian Burnett, Rik Van de Walle, Keith Hill, Jan Bormans, and Fernando
Pereira, Mpeg-21: Goals and achievements, IEEE MultiMedia, vol. 10, Oct.-
Dec. 2003, pp. 60–70.
[7] Julien Cartigny, David Simplot, and Ivan Stojmenovic, Localized
minimumenergy broadcasting in ad-hoc networks, IEEE INFOCOM,, April 2003,
pp. 2210–2217.
[8] Dionisis Chaikalis, Nikos Sgouros, Dimitris Maroulis, and P. Papageorgas,
Hardware implementation of a disparity estimation scheme for real-time
compression in 3d imaging applications, ACM Journal of Visual
Communication and Image Representation 19, Issue 1 (2008).
[9] Te-Hao Chang, Li-Lin Chen, Chung-Jr Lian, Hong-Hui Chen, and Liang-Gee
Chen, Computation reduction technique for lossy jpeg2000 encoding through
ebcot tier-2 feedback processing, Image Processing. 2002. IEEE
Proceedings. 2002 International Conference on, vol. 3, Jun. 2002, pp. 85–
88.
[10] Yanling Chen, Xixin Cao, Qingqing Xie, and Chungan Peng, An area
efficient high performance dct distributed architecture for video
compression, in The 9th IEEE International Conference on Advanced
Communication Technology( ICACT 2007), vol. 1, 12–14 Feb. 2007, pp. 238– 241.
[11] Archana Chidanandan and Magdy Bayoumi, Area-efficient neda architecture
for the 1-d dct/idct, in IEEE International Conference on Acoustics,
Speech and Signal Processing(ICASSP 2006), vol. 3, 14–19 May 2006, pp.
III–III.
[12] Archana Chidanandan, Archana Chidanandan, Wendi Pan, and Magdy A. Bayoumi,
Neda: A low-power high-performance dct architecture, in IEEE Transactions
On Signal Processing 54 (2006), 955–964.
[13] Charilaos Christopoulos, Athanassios Skodras, and Touradj Ebrahimi, The
jpeg2000 still image coding system: An overview, IEEE Trans. Consum.
Electron., vol. 46, Nov. 2000, pp. 1103–1127.
[14] Turek Danvish and Mugdy Buyoumi, Energy aware distributed arithmetic dct
architectures, Signal Processing Systems, 2003. SIPS 2003. IEEE Workshop
on, August 2003.
[15] Harris Albert F., Robin Snader, and Robin Kravets, Energy-efficient
transmission for multimedia streams in last-hop wireless internet, Fourth
IEEE International Conference on Broadband Communications, Networks and
Systems, 2007.(BROADNETS 2007), Sep. 2007.
[16] Lijun Hang, Zhengyu Lu, and Zhaoming Qian, High speed and intelligent
communication topology dedicated to complex power electronic system
integration, 2007. ISIE 2007. IEEE International Symposium on Industrial
Electronics, June 2007, pp. 485–490.
[17] Thomas H.Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford
Stein, Introduction to algorithms, MIT Press, 2001.
[18] Gurdeep S. Hura and Mukesh Singhal, Data and computer communications:
Networking and internetworking, CRC Press, 2001.
[19] Sungbae Hwang and Jacob A. Abraham, Test data compression and test time
reduction using an embedded microprocessor, IEEE Trans. Very Large Scale
Integr. (VLSI) Syst.,, vol. 11, Oct. 2003, pp. 853––862.
[20] Hideyuki Ichihara, Atsuhiro Ogawa, Tomoo Inoue, and Akio Tamura, Dynamic
test compression using statistical coding, IEEE Proc. 10th ATS, 2001,
2001, pp. 143–148.
[21] Kees A. Schouhamer Immink, Coding techniques for digital recorders,
Englewood Cliffs, NJ: Prentice-Hall, 1991.
[22] Rai Jain, Error characteristics of fiber distributed data interface
(fddi), Communications, IEEE Transactions on, Aug. 1990.
[23] Abhijit Jas, Jayabrata Ghosh-Dastidar, Mom-Eng Ng, and Nur A.Touba, An
efficient test vector compression scheme using selective huffman coding,
IEEE Trans. Comput.-Aided Design Integr. Circuits Syst, vol. 22, Jun.
2003, p. 797.
[24] Bongjin Jung andWayne P. Burleson, Vlsi array architectures for pyramid
vector quantization, IEEE Journal of VLSI Signal Processing Systems 18
(1996), 141-154.
[25] Xrysovalantis Kavousianos, Emmanouil Kalligeros, and Dimitris Nikolos,
Multilevel huffman coding: An efficient test-data compression method for
ip cores, IEEE Transactions on Computer-Aided Design of Integrated
Circuits and Systems 26 (2007), 1070–1083.
[26] Tadahiro Kuroda, Tetsuya Fujita, Shinji Mita, Tetsu Nagamatsu, Shinichi
Yoshioka, and Kojiro Suzuki, A 0.9 v, 150 mhz, 10 mw, 4 mm2, 2-dct core
processor with variable v scheme, IEEE Journal of Solid-State
Circuits,JSSC 31 (1996), 1770–1778.
[27] Dong-U Lee, Hyungjin Kim, Steven Tu, and Mohammad Rahimi, Energyoptimized
image communication on resource-constrained sensor platforms, Proceedings
of the ACM 6th international conference on Information processing in
sensor networks, 2007, pp. 216–225.
[28] Kangmin Lee, SeJoong Lee, and HoiJun Yo0, Silent serialized low energy
transmission coding for on-chip interconnection networks, Computer Aided
Design, 2004. ICCAD-2004. IEEE/ACM International Conference on, 2004.
[29] Eun-Choen Lim, Choon-Bo Shim, and Kang Soo You, An efficient rank-based
image transformation scheme using entropy coding in gray-level images,
Software Engineering Research, Management and Applications, 2007. SERA
2007. 5th IEEE ACIS International Conference on, Aug. 2007.
[30] Cheng-Hung Liu, Bai-Jue Shieh, and Chen-Yi Lee, A low-power group-based
vld design, Circuits and Systems, 2004. ISCAS ’04.IEEE Proceedings of
the 2004 International Symposium on, May 2004.
[31] Rafael Peset Llopis, Ramanathan Sethuraman, Carlos A Alba Pinto, Harm
Peters, S Maul, and M Oosterhuis, A low-cost and low-power multi-standard
video encoder, Proceedings of the 1st IEEE/ACM/IFIP international
conference on Hardware/software codesign and system synthesis, 2003, pp.
97–102.
[32] Jason McNeely and Magdy Bayoumi, Low power lookup tables for huffman
decoding, Image Processing, 2007. ICIP 2007. IEEE International Conference
on, Oct. 2007.
[33] D Munoz-Rodriguez and J.B. Arevalo-Galarza, Line coding for very high
speed lans, IEEE Electronics Letters, vol. 26, Nov. 1990, pp. 2051–2053.
[34] Rusty L. Myers, The basics of physics, Greenwood Publishing Group, 2006.
[35] Jongsun Park, Jung Hwan Choi, and Kaushik Roy, Dynamic bit-width
adaptation in dct : Image quality versus computation energy trade-off,
IEEE Proceedings of the conference on Design, automation and test in
Europe: Proceedings, 2006, pp. 520–521.
[36] Jongsun Park and Kaushik Roy, A low power reconfigurable dct architecture
to trade off image quality for computational complexity, Acoustics,
Speech, and Signal Processing, 2004. Proceedings. (ICASSP ’04). IEEE
International Conference on, May 2004.
[37] William B. Pennebaker and Joan L. Mitchell, Jpeg still image data
compression, New York: Van Nostrand Reinhard, 1993.
[38] Balaji Prabhakar, Elif Uysal Biyikoglu, and Abbas El Gamal, Energy-
efficient transmission over a wireless link via lazy packet scheduling,
IEEE INFOCOM, 2001.
[39] Daji Qiao, Sunghyun Choi, Amit Jain, and Kang G. Shin, Miser: an optimal
lowenergy transmission strategy for ieee 802.11a/h, Proceedings of the 9th
annual international conference on Mobile computing and networking,
September 2003.
[40] Shanq-Jang Ruan and Wei-Te Lin, Bipartition architecture for low power
jpeg huffman decoder, The 12th Asia-Pacific Computer Systems Architecture
Conference, August 2007, pp. 235–243.
[41] Richard C. Schneider, Write equalization for generalized (d,k) codes,
IEEE Transactions on Magnetics, vol. 24, Nov. 1988.
[42] Chen Shoushun, Amine Bermak, Senior Member, and Dominique Martinez,
Adaptive-quantization digital image sensor for low-power image
compression, IEEE Trans. Circuits Syst. I, Reg. Papers 54 (2007), no. 1,
13–25.
[43] Chen Shoushun, Amine Bermak, Wang Yan, and Dominique Martinez, A cmos
image sensor with combined adaptive-quantization and qtd-based on-chip
compression processor, Conference 2006, IEEE Custom Integrated Circuits,
Sep,2006.
[44] William Stallings, Data and computer communications, Pearson Prentice
Hall, 2007.
[45] David. S. Taubman and Michael. W. Marcellin, Jpeg2000: Standard for
interactive imaging,, Proceedings of the IEEE, vol. 90, Aug. 2002, pp.
1336–1357.
[46] Clark N. Taylor and Sujit Dey, Adaptive image compression for enabling
mobil multimedia communication, in Proc. IEEE Intl. Conference on
Communications (ICC), vol. 6, June 2001, pp. 1925–9.
[47] Mohammad H. Tehranipour, Mehrdad Nourani, Karim Arabi, and A Afzali-
Kusha, Mixed rl-huffman encoding for power reduction and data compression
in scan test, Circuits and Systems, 2004. ISCAS ’04. IEEE Proceedings of
the 2004 International Symposium o, May 2004.
[48] Kun-Lin Tsai, Paul Lan, Shanq-Jang Ruan, and Mou-Chau Shie, A low power
high performance design for jpeg huffman decoder, The 15th IEEE
International Conference on Electronics, Circuits and Systems (ICECS
2008), Aug. 2008, pp. 1151–1154.
[49] Elif Uysal-Biyikoglu, Balaji Prabhakar, and Abbas El Gamal, Energy-
efficient packet transmission over a wireless link, IEEE/ACM Transactions
on Networking, vol. 10, Aug. 2002.
[50] Adriaan J. van Wijngaarden, A.J. Immink, and Kees A. Schouhamer Immink,
Maximum runlength-limited codes with error control capabilities, Selected
Areas in Communications, IEEE Journal on (2001).
[51] Gregory K.Wallace, The jpeg still picture compression standard, Commun.
ACM, vol. 34, Apr. 1991, pp. 30–44.
[52] Kun Wang, Fan Yang, Qian Zhang, Dapeng Oliver Wu, and Yinlong Xu,
Distributed cooperative rate adaptation for energy efficiency in IEEE
802.11-based multi-hop networks, ACM International Conference Proceeding
Series, vol. 191, 2006.
[53] Huaming Wu and A.A. Abouzeid, Power aware image transmission in energy
constrained wireless networks, in Proc. IEEE Intl Symp. on Computers and
Communications, vol. 2, 2004, pp. 202–207.
[54] Thucydides Xanthopoulos and Anantha Chandrakasan, A low-power dct core
using adaptive bitwidth and arithmetic activity exploiting signal
correlations and quantization, Solid-State Circuits, IEEE Journal of 35
(2000), no. 5.
[55] Katsu Yamatani and Naoki Saito, Improvement of dct-based compression
algorithms using poisson’s equation, IEEE Transactions on Image
Processing, Dec. 2006.
[56] Y.-M. Yeung, O C Au, and Andy Chang, Efficient rate control technique for
jpeg2000 image coding using priority scanning, Proceedings of the 2003
International Conference on Multimedia and Expo, vol. 3, July 2003, pp.
277–280.
[57] Yick Ming Yeung, Oscar C. Au, and Andy Chang, An efficient optimal rate
control scheme for jpeg2000 image coding, Image Processing, 2003. ICIP
2003. IEEE Proceedings. 2003 International Conference on, Sep. 2003, pp.
761–764.

簡易檢索 / 詳目顯示

相關論文