離散小波轉換（Discrete Wavelet Transform）是一種類似短週期的富立葉轉換 (Short-Time Fourier Transform)，它提供另一種信號處理的方法，特別適合用在空間及頻譜上區域聚集性的分析。在本論文中我們描述了各種一維與二維離散小波轉換之演算法、超大型積體電路 (VLSI) 架構及VLSI單晶片的實現。在一維上的研究，我們提出一個改良的一維離散小波轉換VLSI架構，及另外兩個版本的VLSI架構以進一步降低先前版本的硬體成本。在二維上的研究，我們提出一個使用「修正遞迴金字塔演算法 (Modified Recursive Pyramid Algorithm)」之「分離式」的VLSI架構，以及提出自行發展的「半金字塔演算法 (Semi-Pyramid Algorithm)」設計另一個「非分離式」的VLSI架構，並且已將此架構製作成一顆IC單晶片以驗證它的正確性。此外，為了重建一個已被分解的影像，我們也提出ㄧ個二維離散小波反轉換之VLSI架構，同時為了得到較佳的效能我們使用自行發展的「遞迴四元樹金字塔演算法 (Recursive Quaternary-Tree Pyramid Algorithm)」來設計其VLSI架構。
由於我們提出的各種一維及二維離散小波轉換之VLSI架構，擁有快速計算、較低的硬體成本及含有規則性的硬體結構，因此它們不僅適合於VLSI單晶片的實現外，也適合應用在即時的數位信號處理。

The wavelet transform, similar to the Short-Time Fourier Transform, provides an alternative approach to signal processing, especially suitable for the analysis of spatial and spectral locality where signal contains discontinuities and sharp spikes. In this Dissertation, we describe the algorithms, VLSI architectures, and single-chip implementations for the 1-D and 2-D discrete wavelet transforms. In the 1-D case, we improve the performance of an existing 1-D DWT VLSI architecture, and then present two other VLSI architectures to further reduce the hardware cost. In the 2-D case, we propose a separable implementation of DWT VLSI architecture based on the Modified Recursive Pyramid Algorithm (MRPA) algorithm. We also devise a non-separable implementation of DWT VLSI architecture based on our proposed 2-D semi-pyramid algorithm, and then map this architecture into a VLSI single chip to verify its function. Moreover, to reconstruct a decomposed image into the original one, a 2-D inverse DWT VLSI architecture using our proposed Recursive Quarter-Tree Pyramid Algorithm (RQTPA) is devised. Since the proposed 1-D and 2-D DWT/IDWT architectures have fast computation time, spend lower hardware cost, and own a regular hardware structure, they are suited for not only VLSI single-chip implementation, but also applications in digital signal processing, such as codec-based MPEG-4 and JPEG 2000.

封面
封面
目錄
第一章 簡介
第二章 離散小波轉換
第三章 離散小波轉換的演算法
第四章 一維離散小波轉換的VLSI架構設計
第五章 二維離散小波轉換的VLSI架構設計
第六章 VLSI的實作
第七章 結論
附錄 英文部份

[1] S. Mallat, "A theory for multiresolution signal decomposition: The wavelet representation," IEEE Trans. Pattern Anal. and Machine Intell., vol. 11, no. 7, pp. 674-693, July 1989.
[2] O. Rioul and M. Vetterli, "Wavelets and signal processing," IEEE Signal Processing Magazine, vol. 8, no.4, pp. 14-38, Oct. 1991.
[3] I. Daubechies, Ten Lectures on Wavelets, vol. 61 of CBMS-NSF Regional Conferences Series in Applied Mathematics, SIAM, Philadelphia, PA, 1992.
[4] D. Chang, Y. Cho, and S. Ann, "A new wavelet transform-based CELP coder with band selection and selective VQ," in Proc. Int''l Conference Acoustic Speech Signal Processing, 1995, pp. 462-465.
[5] H. Tewfik and H. Ahmed, "Enhanced wavelet based audio coder," in Proc. Conference Record of the Asilomar Conference on Signals, Systems & Computers, vol. 2, 1993, pp. 896-900.
[6] D. L. Donoho and I. M. Johnstone, "Ideal spatial adaptation by wavelet shrinkage," Biometrika, vol.81, no. 3, pp. 425-455, 1994.
[7] K. M. Chen, D. P. Nyquist, J. E. Ross, and R. Bebermeyer, "Radar target discrimination scheme using the discrete wavelet transform for reduced data storage," IEEE Trans. Antennas Propagat., vol. 42, no. 7, pp. 1033-1037, July 1994.
[8] S. Mallat, "Multifrequency channel decompositions of images and wavelet models," IEEE Trans. Acoust., Speech, Signal Processing, vol. 37, no. 12, pp. 2091-2110, Dec. 1989.
[9] M. Antonini, M. Barlaud, P. Mathieu, and I. Daubechies, "Image coding using wavelet transform," IEEE Trans. Image Processing, vol. 1, no. 2, pp. 205-220, Apr. 1992.
[10] J. M. Shapiro, "Embedded image coding using zerotrees of wavelet coefficients," IEEE Trans. Signal Processing, vol. 41, no. 12, pp. 3445-3462, Dec. 1993.
[11] A. Averbuch, D. Lazar, and M. Israeli, "Image compression using wavelet transform and multiresolution decomposition," IEEE Trans. Image Processing, vol. 5, no. 1, pp. 4-15, Jan. 1996.
[12] S. A. Martucci, I. Sodagar, and T. Chiang, Y.-Q. Zhang "A Zerotree Wavelet Video Coder," IEEE Trans. Circuits and Systems for Video Technology, vol. 7, no. 1, pp. 109-118, Feb. 1997.
[13] A. S. Lewis and G. Knowles, "Video compression using 3-D wavelet transforms," Electron. Lett., vol. 26, no. 6, pp. 396-398, Mar. 1990.
[14] K. H. Goh, J. J. Soraghan, and T. S. Durrani, "New 3-D wavelet transform coding algorithm for image sequences," Electron. Lett., vol. 29, no. 4, pp. 401-402, Feb. 1993.
[15] G. Knowles, "VLSI architecture for the discrete wavelet transform," Electron. Lett., vol. 26, no. 15, pp. 1184-1185, July 1990.
[16] M. Vishwanath, "The recursive pyramid algorithm for the discrete wavelet transform," IEEE Trans. Signal Processing, vol.42, no. 3, pp. 673-676, Mar. 1994.
[17] M. Vishwanath, R. Owens, and M. J. Irwin, "VLSI architectures for the discrete wavelet transform," IEEE Trans. Circuits and Systems II, Analog and Digital Signal Processing, vol. 42, no. 5, pp. 305-316, May 1995.
[18] C. Chakrabarti and M. Vishwanath, "Efficient realizations of the discrete and continuous wavelet transforms: from single chip implementations to mappings on SIMD array computers," IEEE Trans. Signal Processing, vol. 43, no. 3, pp. 759-771, Mar. 1995.
[19] K. K. Parhi and T. Nishitani, "VLSI architecture for discrete wavelet transform," IEEE Trans. VLSI Syst., vol. 1, no. 2, pp. 191-202, June 1993.
[20] K. K. Parhi, "Systematic synthesis of DSP data format converters using lift-time analysis and forward-backward register allocation," IEEE Trans. Circuits and Systems II, Analog and Digital Signal Processing, vol. 39, no. 7, pp. 423-440, July 1992.
[21] A. Grzeszczak, M. K. Mandal, S. Panchanathan, and T. Yeap, "VLSI implementation of discrete wavelet transform," IEEE Trans. VLSI Syst., vol. 4, no. 4, pp. 421-433, Dec. 1996.
[22] C. Nagendra, M. J. Irwin, R. M. Owens, "Digit pipelined discrete wavelet transform," in Proc Int''l Conference Acoustic Speech Signal Processing, vol.2, pp. II-405- II-408, Apr. 1994.
[23] J. Fridman and E. S. Manolakos, "On the synthesis of regular VLSI architectures for the 1-D discrete wavelet transform," in Proc. of SPIE Conf. on Mathematical Imaging: Wavelet Applications in Signal and Image Processing II, San Diego CA, July 1994, pp. 296-307.
[24] M. H. Sheu, S. F. Cheng, and M. D. Shieh, "A pipelined VLSI with module structure design for discrete wavelet transform," in Proc. IEEE Int. Symp. Circuits and Systems, May 1996, pp. 352-255.
[25] M. H. Sheu, M. D. Shieh, S. F. Cheng, "A unified VLSI architecture for decomposition and synthesis of discrete wavelet transform," in proc. the 39th Midwest Symposium on Circuits and Systems, Aug. 1996, pp. 113-116.
[26] S. Simon, P. J. Rieder, and A. Nossek, "Efficient VLSI suited architectures for discrete wavelet transforms," in IEEE Workshop on VLSI Signal Processing, vol. IX, Nov. 1996, pp. 388 -397.
[27] S. Simon, P. J. Rieder, C. Schimpfle, and A. Nossek, "CORDIC-based architectures for the efficient implementation of discrete wavelet transforms," in Proc. IEEE Int. Symp. Circuits and Systems, May 1996, pp. 77-80.
[28] T. C. Denk and K. K. Parhi, "VLSI architecture for lattice structure based orthonormal discrete wavelet transforms," IEEE Trans. Circuits and Systems II, Analog and Digital Signal Processing, vol. 44, no. 2, pp. 129-132, Feb. 1997.
[29] T. C. Denk and K. K. Parhi, "Synthesis of folded pipelined architectures for Multirate DSP algorithms," IEEE Trans. VLSI Syst., vol. 6, no. 4, pp. 595-607, Dec. 1998.
[30] Aware, Inc., Aware Wavelet Transform Processor (WTP) preliminary, Cambridge, MA, 1991.
[31] H. Sava, M. Fleury, A.C. Downton, and A.F. Clark "Parallel pipeline implementation of wavelet transform", IEE Proc.-Vis. Image Signal Proc., 1997, pp. 355-359.
[32] A. S. Lewis and G. Knowles, "VLSI architecture for 2-D daubechies wavelet transform without multipliers," Electron. Lett., vol. 27, no. 2, pp. 171-173, Jan. 1991.
[33] M. Holschneider, R. Kronland-Martinet, J. Morlet, and Ph. Tchamitchian, "A real-time algorithm for signal analysis with the help of the wavelet transform," in Wavelets, Time-Frequency Methods and Phase Space, J. M. Combes, A. Grossmann, and Ph. Tchamitchian, Eds. Berlin: Springer, IPTI, 1989, pp. 286-297.
[34] C. Chakrabarti, M. Vishwanath, R. Owens, "Architectures for wavelet transforms: a survey," Journal of VLSI Signal Processing, vol. 14, no. 2, pp.171-192, Nov. 1996.
[35] T. C. Denk and K. K. Parhi, "Calculation of minimum number of registers in 2-D discrete wavelet transforms using lapped block processing," in Proc. IEEE Int''l Symposium Circuits and Systems, May, 1994, pp. 524-527.
[36] R. Rumian, "An architecture for real-time wavelet image decomposition," in Proc. IEEE Int. Symp. on Circuits and Systems, London, England, May 1994, pp. 73-76.
[37] J. Chen and M. A. Bayoumi, "A scalable systolic array architecture for 2-D discrete wavelet transforms," in IEEE Workshop on VLSI Signal Processing, vol. III, Nov. 1995, pp. 303 -312.
[38] J. C. Limqueco and M. A. Bayoumi, "A VLSI architecture for separable 2-D discrete wavelet transform," Journal of VLSI Signal Processing, vol. 18, no.2, pp.125-140, Feb. 1998.
[39] M. H. Sheu, M. D. Shieh, and S. W. Liu, "A VLSI architecture design with lower hardware cost and less memory for separable 2-D discrete wavelet transform," in Proc. IEEE Int. Symp. Circuits and Systems, May 1998, pp. 457-460.
[40] S. K. Paek, H. K. Jeon, and L. S. Kim, "Semi-recursive VLSI architecture for two-dimensional discrete wavelet transform," in Proc. IEEE Int. Symp. Circuits and Systems, May 1998, pp. 469-472.
[41] S. K. Paek, H. K. Jeon, and L. S. Kim, ŖD DWT VLSI architecture for wavelet image processing," Electron. Lett., vol. 34, no. 6, pp. 537-538, Mar. 1998.
[42] R. M. Owens and M. Vishwanath, "A very efficient storage structure for DWT and IDWT filters," Journal of VLSI Signal Processing, vol. 19, no.3, pp.215-225, Aug. 1998.
[43] M. H. Sheu, M. D. Shieh, and S. W. Liu, "A low-cost VLSI architecture design for non-separable 2-D discrete wavelet transform," in Proc. the 40th Midwest Symposium on Circuits and Systems, Aug. 1997, pp.1217-1220.
[44] A. Brizio, G. Masera, G. Piccinini, M. R. Roch, and P. di Zamboni, "A high speed bit-serial 2D-DWT VLSI processor" in Proc. the 2nd International Multiconference on Computational Engineering in Systems Applications, CESA''98, Tunisia, April 1998, pp. 297-300.
[45] J. D. Legat, J. P. David, and P. Desneux, "Programmable architectures for subband coding: FPGA-based system versus dedicated VLSI chip," in Proc. the 2nd International Multiconference on Computational Engineering in Systems Applications, CESA''98, Tunisia, April 1998, pp. 301-305.
[46] L. Breveglieri, V. Piuri, E. E. Swartzlander, Jr. "A serial discrete wavelet transform processor" in Proc. the 2nd International Multiconference on Computational Engineering in Systems Applications, CESA''98, Tunisia, April 1998, pp. 306-311.
[47] H. Y. H. Chunang and L. Chen, "VLSI architecture for fast 2D orthonormal wavelet transform," Journal of VLSI Signal Processing, vol. 10, no. 3, pp.225-236, Aug. 1995.
[48] C. A. Hsieh, VLSI architecture design and implementation of discrete wavelet transform, M.S. Thesis, National Taiwan University, June 1996.
[49] C. Yu, C. A. Hsieh, and S. J. Chen, "Design and implementation of a highly efficient VLSI architecture for discrete wavelet transform," in Proc. IEEE Custom Integrated Circuits Conference, May 1997, pp. 237-240.
[50] C. Yu and S. J. Chen, "Efficient VLSI architecture for separable 2-D discrete wavelet transforms," in Proc. IEEE Int''l Symposium Consumer Electronics, Oct, 1998, pp. WAB1 01-04.
[51] C. Yu and S. J. Chen, "Design of an efficient VLSI architecture for 2-D discrete wavelet transforms" IEEE Trans. on Consumer Electronic, vol. 45, no. 1, pp. 135-140, Feb. 1999.
[52] C. Yu and S. J. Chen, "VLSI implementation of 2-D discrete wavelet transform for real time video signal processing" IEEE Trans. on Consumer Electronic, vol. 43, no. 4, pp. 1270-1279, Nov. 1997.
[53] C. Yu and S. J. Chen, "Efficient VLSI architecture for 2-D inverse discrete wavelet transforms," in Proc. IEEE Int''l Symposium Circuits and Systems, May, 1999, pp. 524-527.
[54] C. Yu and S. J. Chen, "An improved pyramid algorithm for synthesizing 2-D discrete wavelet transforms," to appear in Proc. IEEE Workshop Signal Processing Systems, 1999.
[55] O. Rioul and P. Duhamel, "Fast algorithms for discrete and continuous wavelet transforms," IEEE Trans. on Inform. Theory, vol. 38, no. 2, pp. 569-586, Mar. 1992
[56] G. Karlsson and M. Vetterli, "Extension of finite length signals for sub-band coding," Signal processing , vol.17, no.2 , pp. 161-166, June 1989.
[57] M. J. T. Smith and S. L. Eddins, "Analysis/synthesis techniques for subband image coding" IEEE Trans. Acoust., Speech, Signal Processing, vol. 38, no. 8, pp. 1446-1456, Aug. 1990.
[58] H. Kiya, K. Nishkawa, and M. Iwahashi, "A development of symmetric extension method for subband image coding," IEEE Trans. Image Processing, vol. 3, no. 1, pp. 78-81, Jan. 1994.
[59] R. H. Bamberger, S. L. Eddins, and V. Nuri, "Generalized symmetric extension for size-limited multirate filter banks," IEEE Trans. Image Processing, vol. 3, no. 1, pp. 82-87, Jan. 1994.
[60] T. Miyazaki, T. Nishitani, M. Ishikawa, M. Edahiro, and K. Mitsuhashi, "Chrominance/Luminance signal separation and syntheses chips developed with a DSP silicon compiler," IEEE Trans. Circuits and Systems for Video Technology, vol. 2, no. 2, pp. 245-254, June 1992.
[61] M. Vetterli and J. Kovacevic, Wavelet and Subband Coding, Prentice Hall PTR, Englewood Cliffs, 1995.
[62] G. Strang and T. Nguyen, Wavelets and Filter Banks, Wellesley-Cambridge Press, 1996.
[63] S. Mallat, "A theory for multiresolution approximations and wavelet orthonormal bases L2(R)," Trans. Amer. Math. Soc., vol. 315, pp. 69-87, Sep. 1989.
[64] Y. Meyer, Ondelettes et Operateurs, Hermann, Paris, 1990. In two volumes.
[65] J. D. Villasenor, B. Belzer, and J. Liao, "Wavelet filter evaluation for image compression," IEEE Trans. Image Processing, vol. 4, no. 8, pp. 1053-1060, Aug. 1995.
[66] G. Karlsson and M. Vetterli, "Extension of finite length signals for sub-band coding," Signal processing, vol.17, no. 2, pp. 161-166, June 1989.
[67] M. J. T. Smith and S. L. Eddins, "Analysis/synthesis techniques for subband image coding" IEEE Trans. Acoust., Speech, Signal Processing, vol. 38, no. 8, pp. 1446-1456, Aug. 1990.
[68] C. S. Wallace, "A suggestion for fast multipliers," IEEE Trans. Electron. Comput., vol. EC-13, pp. 14-17, Feb 1964.
[69] A. D. Booth, "A signed binary multiplication technique," Quarterly J. mechanics and Applied Mathematics, vol. 4, pt. 2, pp. 236-240, 1951.
[70] E. E. Swartzlander Jr., ed., Computer Arithmetic, vol. 1, Los Alamitos, Ca:IEEE Computer Society Press, 1990.
[71] O. L. Mac Sorley, "High speed arithmetic in binary computers," Proc. IRE, vol. 49, Jan. 1961, pp. 67-91.
[72] L. P. Rubinfield, "A proof of the modified booth''s algorithm for multiplication," IEEE Trans. Computers, vol. 24, pp. 1014-1015, 1975.
[73] S. Vassiliadis, E. M. Schwartz, and D. J. Hanrahan, "A general proof for overlapped multiple-bit scanning multiplications," IEEE Trans. Computers, vol. 38, no. 8, pp. 172-183, Aug. 1989.
[74] H. Sam and A. Gupta, "A generalized multibit recording of two''s complement binary numbers and its proof with applications in multiplier implementations," IEEE Trans. Computers, vol. 39, no. 2, pp. 1006-1015, Feb. 1990.
[75] J. Fadavi-Ardekani, "M’N booth encoded multiplier generator using optimized wallace trees," IEEE Trans. VLSI Syst., vol. 1, no. 2, pp. 120-125, June 1993.
[76] P. E. Madrid, B. Millar, and E. E. Swartzlander Jr., "Modified booth algorithm for higher radix fixed point multiplication," IEEE Trans. VLSI Syst., vol. 1, no. 2, pp. 164-167, June. 1993.
[77] N. Phkubo, "A 4.4 ns CMOS 54’54-b multiplier using pass-transistor multiplexer," in Proc. IEEE Custom Integrated Circuits Conference, May 1994, pp. 26.4.1-26.4.4.
[78] O. Salomon, J.-M. Green, and H. Klar, "General algorithms for a simplified addition of 2''s complement numbers," IEEE J. Solid-State Circuits, vol. SC-30, no. 7, pp. 839-844, July 1995.