跳到主要內容

臺灣博碩士論文加值系統

(44.222.218.145) 您好!臺灣時間:2024/03/04 16:51
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

我願授權國圖
: 
twitterline
研究生:范倫達
研究生(外文):Lan-Da Van
論文名稱:高效率超大型積體電路架構設計:乘法器、二維數位濾波器、適應性數位濾波器
論文名稱(外文):Design of Efficient VLSI Architectures:Multiplier, 2-D Digital Filter, and Adaptive Digital Filter
指導教授:馮武雄馮武雄引用關係
指導教授(外文):Wu-Shiung Feng
學位類別:博士
校院名稱:國立臺灣大學
系所名稱:電機工程學研究所
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2001
畢業學年度:89
語文別:英文
論文頁數:127
中文關鍵詞:固定寬度乘法器心律式二維數位濾波器架構延遲最小平均平方誤差遞迴最小平方誤差適應性數位濾波器等化器細紋管線式
外文關鍵詞:Fixed-Width MultiplierSystolic2-D Digital FilterDelay LMS (DLMS)RLSAdaptive FilterEqualizationFine-Grain Pipelining
相關次數:
  • 被引用被引用:0
  • 點閱點閱:323
  • 評分評分:
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:1
在本論文中我們設計許多高效率超大型積體電路(VLSI)架構與演算法,其中包含固定寬度乘法器、二維數位濾波器、延遲最小平均平方誤差(DLMS)及遞迴最小平方誤差(RLS)適應性數位濾波器。首先我們使用一廣義方法設計低誤差低面積固定寬度乘法器,此固定寬度乘法器輸入端為兩個s位元數值而輸出端為s位元數值。藉著選擇適當的二元區分法(Binary Thresholding)及通用性指標(Generalized Index),我們可提出幾個更好的低誤差低面積固定寬度乘法器。此外,我們更進一步地將此乘法器應用在處理語音訊號之數位濾波器,我們可在子音與母音部分獲得很好的結果。第二,設計一新型心律式(Systolic)二維無限脈衝響應(IIR)與有限脈衝響應(FIR)數位濾波器架構,我們利用改良式延遲排列及新的心律式轉換混合技巧而得到區域性傳遞(Local Broadcast)和低量化誤差(Quantization Error)架構,在滿足速度要求下,此濾波器不會犧牲乘法器與暫存器數目。第三,設計一高效率DLMS心律式適應性FIR數位濾波器架構因我們使用新型樹狀心律式處理單元(Tree-Systolic PE),此高效率心律式適應性FIR數位濾波器可得到比傳統DLMS架構較快的收斂特性、可在字元組上(Word-Level)達到最快速度和考慮回授誤差訊號之有限驅動能力。更進一步地,根據最佳決定樹狀層數的法則,我們可兼顧最低延遲與高規則性。最後,我們專注於發展有關於RLS之新演算法與架構,此新型架構簡稱為RGR-RLS架構有下列優點:更快的收斂速度,細紋管線式(Fine-Grain Pipelining)使之能任意提高產能(Throughput),避免開根號運算。

In this dissertation, we propose several efficient very-large-scale-integration (VLSI) architectures and algorithms including fixed-width multipliers, two-dimensional (2-D) digital filter, and delay least-mean-square (DLMS)-based as well as recursive-least-squares (RLS)-based adaptive digital filters. First, a general methodology for designing lower-error area-efficient fixed-width two’s-complement multipliers that receive two -bit numbers and produce an -bit product is proposed. While keeping different columns in the subproduct array, we propose several better and realizable error-compensation biases to reduce truncation error by properly choosing the proposed binary thresholding and generalized indices. Therefore, several lower-error area-efficient fixed-width multipliers suitable for VLSI implementation can be obtained. Furthermore, these new multipliers with better error-compensation circuits are suited to the fractional multiplication through a scaling box. Second, 2-D systolic-array infinite-impulse-response (IIR) and finite-impulse-response (FIR) digital filter architectures without global broadcast by the hybrid of a modified reordering scheme and a new systolic transformation are presented. This architecture possesses local broadcast, lower quantization error and zero latency without sacrificing the number of multipliers as well as delay elements under the satisfactory critical period. In addition, we extend this new architecture to a useful 2-D systolic cascade-form architecture and provide the comprehensive error analysis for the proposed architectures. Third, we propose an efficient systolic architecture for the DLMS adaptive FIR digital filter based on a new tree-systolic processing element ( ) and an optimized tree-level rule. Applying our tree-systolic , a higher convergence rate than that of the conventional DLMS structures can be obtained without sacrificing the properties of the systolic-array architecture. The efficient systolic adaptive FIR digital filter not only operates at the highest throughput in the word-level but also considers finite driving/update of the feedback error signal. Furthermore, based on our proposed optimized tree-level rule that takes account of minimum delay and high regularity, an efficient N-tap systolic adaptive FIR digital filter can be easily determined under the constraint of maximum driving of the feedback error signal. Finally, we focus on developing a new relaxed Givens rotation (RGR)-RLS algorithm to pipeline the RGR-RLS systolic array. The novel systolic adaptive architecture has faster convergence rate than that of the least-mean-square (LMS) and the DLMS-based adaptive filters. On the other hand, an arbitrarily high throughput due to the fine-grain pipelining and square-root free computation can be achieved.

封面
Abstract
Contents
List of Figures
List of Tables
Chapter 1 Introduction
1.1 Low-Error Area-Efficient Fixed-Width Multipliers
1.2 2-D Systolie Digital Filter Architecture
1.3 DLMS-Based Systolic Adaptive Digital Filter Architecture
1.4 RLS-Based Systolic Adaptive Architecture
1.5 Organization of Disseriation
Chpater 2 Lower-Error Area-Efficient Fixed-Width Multipliers
2.1 Introductior
2.2 Design of Fixed Width Multipliers
2.2.1 Realizable error-compensation bias keeping s columns (w=o)
2.2.2 Realizable error-compensation bias keeping more than s columns (w?1)
2.3 Lower-Error Fixed-Width Multipliers with Large Width s
2.3.1 Realizable error-compensation bias keeping s columns (w=0)
2.3.2 Realizable error-compensation bias keeping more than s columns (w>1)
2.4 Performance Discussion and Area Compatisions
2.5 Practional Operation and Overflow Detection
2.6 DSP Apllication of Fixed-Width Multiplier
2.7 Summary
Chapter 3 A New 2-D Systolic Digital Filter Architecture
3.1 Introduction
3.2 Effect of Global Broadeast
3.3 An improved Systolic Architecture Design
3.3.1 2-D systolic noneaseide-form digital filter
3.3.2 2-D systolic caseide-form digital filter
3.4 Error Analysis of New Digital Filter Architectures
3.5 Comparison Results of Hr and FIR Digital Filters
3.6 Chip Design
3.7 Summary
Chpater 4 An Efficient Systolic Architecture for the DLMS Adaptive Filter
4.1 Introduction
4.2 An Efficient Systolic Architecture
4.3 Comparison Results among Different Architectures
4.4 Applications of the Efficient Systolic Adaptive Digital Filter
4.5 Summary
Chapter 5 Pipelined RLS Adaptive Architecture Using Relaxed Givens Rotations (PGR)
5.1 Introduction
5.2 Background
5.3 RGR-RLS Algornhm and Architecture
5.4 Pipelined RGR-RLS (PRGR-RLS) Architecture
5.5 Comparison and Simulations Results
5.6 Summary
Chapter 6 Conclusions
Appedix
Appendix A
Appendix B
Appendix C
Bibliography
Publication List
Bilgraphy

[1] S. Y. Kung, VLSI Array Processors. Englewood Cliffs, NJ: Prentice-Hall, 1988.
[2] C. R. Baugh and B. A. Wooley, “A two’s complement parallel array multiplication algorithm,” IEEE Trans. Compt., vol. C-22, no. 12, pp. 1045-1047, Dec. 1973.
[3] L. B. Rabiner and B. Gold, Theory and Application of Digital Processing. Englewood Cliffs, NJ: Prentice-Hall, 1975.
[4] S. L. Freeny, “Special —purpose hardware for digital filtering,” Proc. IEEE, vol. 63, no. 4, pp. 633-647, Apr. 1975.
[5] L. B. Jackson, Digital Filters and Signal Processing. 3rd ed. Dordrecht, the Netherlands: Kluwer, 1996.
[6] P. Pirsch, Architectures for Digital Signal Processing. NY: Wiley, 1998, chap 5.
[7] K. K. Parhi, VLSI Digital Signal Processing Systems: Design and Implementation. NY: Wiley, 1999, chap 7.
[8] K. Hwang, Computer Arithmetic: Principles, Architecture, and Design. New York: John-Wiley, 1979.
[9] F. Cavanagh, Digital Computer Arithmetic: Design and Implementation. New York: McGraw-Hill, 1984.
[10] Y. P. Lim, “Single-precision multiplier with reduced circuit complexity for signal processing applications,” IEEE Trans. Comput., vol. 41, no. 10, pp. 1333-1336, Oct. 1992.
[11]M. J. Schulte and E. E. Swartzlander, Jr., “Truncated multiplication with correction constant,” VLSI Signal Processing, VI, New York: IEEE Press, 1993, pp. 388-396.
[12] S. S. Kidambi, F. El-Guibaly, and A. Antoniou, “Area-efficient multipliers for digital signal processing applications,” IEEE Trans. Circuits Syst. II, vol. CAS-43, no. 2, pp. 90-94, Feb. 1996.
[13] E. J. King and E. E. Swartzlander, Jr., “Data-dependent truncation scheme for parallel multipliers,” in Proc. 31st Asilomar Conference on Signals, Systems, and Computers, 1997, vol. 2, pp. 1178-1182, Pacific Grove, CA.
[14] E. E. Swartzlander, Jr., “Truncated multiplication with approximate rounding,” in Proc. 33rd Asilomar Conference on Signals, Systems, and Computers, 1999, vol. 2, pp. 1480-1483.
[15] M. J. Schulte, J. E. Stine and J. G. Jansen, “Reduced Power dissipation through truncated multiplication” in Proc. IEEE Alessandro Volta Memorial Workshop on Low Power Design, 1999, pp. 61-69, Como, Italy.
[16] J. M. Jou, S. R. Kuang, “Design of a low-error fixed-width multiplier for DSP applications,” Electron. Lett., vol. 33, no. 19, pp. 1597-1598, 1997.
[17] J. M. Jou, S. R. Kuang, and R. D. Chen, “Design of low-error fixed-width multiplier for DSP applications,” IEEE Trans. Circuits Syst. II, vol. CAS-46, no. 6, pp. 836-842, Jun. 1999.
[18] L. D. Van, S. S. Wang, S. Tenqchen, W. S. Fegn, and B. S. Jeng, “Design of a lower error fixed-width multiplier for speech processing application,” in Proc. IEEE Int. Symp. Circuits Syst., May 1999, vol. 3, pp. 130-133, Orlando, Florida.
[19] L. D. Van, S. S. Wang, and W. S. Feng, “Design of the lower-error fiexed-width multiplier and its application”, IEEE Trans. Circuits Syst. II, vol. 47, pp. 1112-1118, Oct. 2000.
[20] L. D. Van, “Generalized lower-error area-efficient fixed-width multipliers”, IEEE Trans. Computer, under revision, 2001.
[21] L. D. Van, C. C. Tang, S. Tengchen and W. S. Feng, “A new VLSI architecture without global broadcast for 2-D digital filters,” in Proc. IEEE Int. Symp. Circuits Syst., May 2000, vol. 1, pp. 547-550, Geneva, Switzerland.
[22] A. Papoulis, Probability, Random Variables, and Stochastic Processes. 3rd ed. NY: McGraw-Hill, 1991.
[23] M. E. Paul, and K. Bruce, C Language Algorithms for Digital Signal Processing. Englewood Cliffs, NJ: Prentice-Hall, 1991.
[24] C. S. Wallace, “A suggestion for a fast multiplier,” IEEE Trans. Electron. Comput., vol. EC-13, pp. 14-17, Feb. 1964.
[25] T. G. Noll, D. S. Landsiedel, H. Klar, and G. Enders, “ A pipelined 330-MHz multiplier,” IEEE J. Solid-State Circuits, vol. SC-21, pp. 411-416, June 1986.
[26] A. M. Tekalp, Digital Video Processing. Englewood Cliffs, NJ: Prentice-Hall, 1995, chap 14.
[27] A. K. Jain, Fundamentals of Digital Image Processing. Englewood Cliffs, NJ: Prentice-Hall, 1989.
[28] M. A. Sid-Ahmed, Image Processing: Theory, Algorithms, and Architectures. NY: McGraw-Hill, 1995.
[29] H. T. Kung, “Why systolic architectures?,” IEEE Computer, vol. 25, pp. 37-46, Jan. 1982.
[30] N. H. E. Weste and K. Eshraghian, Principles of COMS VLSI Design: A Systems Perspective, 2nd ed. Addison-Wesley, 1993, chap 3-5.
[31] M. A. Sid-Ahmed, “A systolic realization for 2-D digital filters,” IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-37, pp. 560-565, Apr. 1989.
[32] S. Sunder, F. El-Guibaly, and A. Antoniou, ”Systolic implementations of two-dimensional recursive digital filters,” in Proc. IEEE Int. Symp. Circuits Syst., May 1990, pp. 1034-1037.
[33] N. R. Shanbhag, “An improved systolic architecture for 2-D digital filters,” IEEE Trans. Signal Processing, vol. 39, no. 5, pp. 1195-1202, May 1991.
[34] L. D. Van, S. Tenqchen, C. H. Chang, and W. S. Feng, “A new 2-D digital filter using a locally broadcast scheme and its cascade form,” in Proc. IEEE Asia Pacific Conf. Circuits Syst., Dec. 2000, pp. 579-582, Tianjin, China.
[35] L. D. Van, “A new 2-D systolic digital filter architecture without global broadcast,” IEEE Trans. VLSI Syst., under revision, 2001.
[36] D. E. Dudgeon and R. M. Mersereau, Multidimensional Digital Signal Processing. Englewood Cliffs, NJ: Prentice-Hall, 1984, chap 4.
[37] Jayadema, “A new systolic design for digital IIR filters,” IEEE Trans. Circuits Syst., vol. CAS-37, no. 5, pp. 653-654, May 1990.
[38] A. V. Oppenheim and R. W. Schafer, Discrete-Time Signal Processing. Englewood Cliffs, NJ: Prentice-Hall, 1989, chap 6.
[39] B. G. Mertzios and A. N. Venetsanopoulos, “Combined error at the output of two-dimensional recursive digital filters,” IEEE Trans. Circuits Syst., vol. CAS-31, no. 10, pp. 888-891, Oct. 1984.
[40] D. Raghuramireddy and R. Unbehauen, “Error analysis of a systolic realization of 2-D Filters,” IEEE Trans. Signal Processing, vol. 40, no. 2, pp. 478-482, Feb. 1992.
[41] R. A. Robert and C. T. Mullis, Digital Signal Processing. Reading MA: Addision-Wesley, 1987.
[42] Cell-based ASIC Design Kit (Basic) Training Manual. Chip Implementation Center, July 2001.
[43] K. K. Parhi and D. G. Messerschmitt, “Concurrent architectures for two-dimensional recursive digital filtering,” IEEE Trans. Circuits Syst., vol. CAS-36, no. 6, pp. 813-829, June. 1989.
[44] B. Widrow and M. E. Hoff, Jr., Adaptive switching circuits,” IRE WESCON Conv. Rec., pt.5, pp.96-104, 1960.
[45] B. Widrow, J. M. McCool, M. G. Larimore, and C. R. Johnson, Jr., “Stationary and nonstationary learning characteristics of the LMS adaptive filter,” Proc. IEEE, vol. 64, no. 8, pp. 1151-1162, Aug. 1976.
[46] B. Widrow and S. Stearns, Adaptive Signal Processing, Englewood Cliffs, NJ: Prentice-Hall, 1985.
[47] S. Haykin, Adaptive Filter Theory, 3rd ed. Englewood Cliffs, NJ: Prentice-Hall, 1996.
[48] S. Haykin, Communication System. 4rd ed. John Wiley & Sons, 2001.
[49] S. D. Stearns and R. A. David, Signal Processing Algorithms in Matlab. Englewood Cliffs, NJ: Prentice-Hall, 1996, chap 12.
[50] M. M. Hadhoud and D. W. Thomas, “The two-dimensional adaptive LMS (TDLMS) algorithm,” IEEE Trans. Circuits Syst., vol. CAS-35, no. 5, pp. 485-494, May 1988.
[51] G. Long, F. Ling, and J. G. Proakis, “The LMS algorithm with delayed coefficient adaptation,” IEEE Trans. Acoust., Speech, Signal Processing, vol. ASSP-37, no. 9, pp. 1397-1405, Sept. 1989.
[52] G. Long, F. Ling, and J. G. Proakis, “Correction to “The LMS algorithm with delayed coefficient adaptation”,” IEEE Trans. Signal Processing, vol. 40, no. 1, pp. 230-232, Jan. 1992.
[53] H. Herzberg, R. Haimi-Cohen, and Y. Be’ery, “A systolic array realization of an LMS adaptive filter and the effects of delayed adaptation,” IEEE Trans. Signal Processing, vol. 40, no. 11, pp. 2799-2803, Nov. 1992.
[54] M. D. Meyer and D. P. Agrawal, “A high sampling rate delayed LMS filter architecture,” IEEE Trans. Circuits Syst., II, vol. CAS-40, no. 11, pp. 727-729, Nov. 1993.
[55] S. C. Douglas, Q. Zhu, and K. F. Smith, “A pipelined LMS adaptive FIR filter architecture without adaptation delay,” IEEE Trans. Signal Processing, vol. 46, no. 3, pp. 775-779, Mar. 1998.
[56] K. Matsubara, K. Nishikawa, and H. Kiya, “Pipelined adaptive filters based on delayed LMS algorithm,” IEICE Trans., vol. J79-A, pp. 1050-1057, May 1996, in Japanese.
[57] K. Matsubara, K. Nishikawa, and H. Kiya, “Pipelined LMS adaptive filter using a new look-ahead transformation,” IEEE Trans. Circuits Syst., II, vol. CAS-46, no. 1, pp. 51-55, Jan. 1999.
[58] R. D. Poltmann, “Conversion of the delayed LMS algorithm into the LMS algorithm,” IEEE Signal Processing Lett., vol. 2, pp. 223. Dec. 1995.
[59] L. D. Van, S. Tenqchen, C. H. Chang and W. S. Feng, “A tree-systolic array of DLMS adaptive filter,” in Proc. IEEE Int. Conf. Acoustics, Speech and Signal Processing, Mar. 1999, vol. 3, pp. 1253-1256, Phoenix, Arizona.
[60] L. D. Van and W. S. Feng, “Efficient systolic architectures for 1-D and 2-D DLMS adaptive digital filters,” in Proc. IEEE Asia Pacific Conf. Circuits Syst., Dec. 2000, pp. 399-402, Tianjin, China.
[61] L. D. Van and W. S. Feng, “An efficient systolic architecture for the DLMS adaptive filter and its applications,” IEEE Trans. Circuits Syst. II, accepted as a regular paper, 2001.
[62] A. Bellaouar, M. I. Elmasry, Low-Power Digital VLSI Design: Circuits and Systems. Kluwer Academic Publishers, 1995, chap 4.
[63] K. Matsubara, K. Nishikawa, and H. Kiya, “2-D pipelined adaptive filters based on 2-D delayed LMS algorithm,” IEICE Trans., vol. E80-A, no. 6, pp. 1009-1014, June 1997.
[64] N. R. Shanbhag and K. K. Parhi, “Relaxed look-ahead pipelined LMS adaptive filters and their application to ADPCM coder,” IEEE Trans. Circuits Syst., II, vol. 40, pp. 753-766, Dec. 1993.
[65] C. R. Ward, P. J. Hargrave, and J. G. McWhirter, “A novel algorithm and architecture for adaptive digital beamforming,” IEEE Trans. Antenna Propagat., vol.34, no. 3, pp. 338-346, Mar. 1986.
[66] A. Y. Wu and K. J. R. Liu, “Split recursive least-squares: algorithms, architectures, and applications,” IEEE Trans. Circuits Syst., II, vol. 43, pp. 645-658, Sept. 1996.
[67] G. H. Golub and C. F .V. Loan, Matrix Computation. 3rd ed. Baltimore, MD: Johns Hopkins University Press, 1996.
[68] W. M. Gentleman and H. T. Kung, “Matrix triangularization by systolic arrays,” in Proc. SPIE: Real Time Signal Process. IV, 1981, pp. 298-303.
[69] J. G. McWhirter, “Recursive least-squares minimization using a systolic array,” in Proc. SPIE: Real Time Signal Process. VI, vol. 431, 1983, pp. 105-112.
[70] T. H. Y. Meng, E. A. Lee, and D. G. Messerschmitt, “Least-squares computation at arbitrarily high speeds,“ in Proc. IEEE Int. Conf. Acoustics, Speech, Signal Processing, 1987, pp. 1398-1401.
[71] J. M. Cioffi, “The fast adaptive ROTORs’ RLS algorithm,” IEEE Trans. Acoust., Speech, Signal Processing, vol. 38, pp. 631-653, Apr. 1990.
[72] S. F. Hsieh, K. J. R. Liu, and K. Yao, “A unified square-root-free Givens rotation approach for QRD-based recursive least squares estimation,” IEEE Trans. Signal Processing, vol. 41, pp. 1405-1409, Mar. 1993.
[73] E. Frantzeskakis and K. J. R. Liu, “A class of square-root and division free algorithms and architectures for QRD-based adaptive signal processing,” IEEE Trans. Signal Processing, vol. 42, pp. 2455-2469, Sept. 1994.
[74] A. P. Chandrakasan, S. Sheng, and R. W. Broderson, “Low-power CMOS digital design,“ IEEE J. Solid-State Circuits, vol. SC-27, pp. 473-484, Apr. 1992.
[75] K. K. Parhi and D. G. Messerschmitt, “Pipeline interleaving and parallelism in recursive digital filters--Part I: Pipelining using scattered look-ahead and decomposition,” IEEE Trans. Acoust,, Speech, Signal Processing, vol. 37, pp. 1118-1134, July 1989.
[76] K. J. Raghunath and K. K. Parhi, “Pipelined RLS adaptive filtering using scaled tangent rotations (STAR),” IEEE Trans. Signal Processing, vol. 40, pp. 2591-2604, Oct. 1996.
[77] J. Ma, K. K. Parhi, and E. F. Deprettere, “Annihilation-reordering look-ahead pipelined CORDIC-based RLS adaptive filters and their application to adaptive beamforming,” IEEE Trans. Signal Processing, vol. 48, pp. 2414-2431, Aug. 2000.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top