[Back to Results | New Search]

Student Number 85324017 Author Cheng-Shing Wu(§d¬F¾±) Author's Email Address benior@ee.ncu.edu.tw Statistics This thesis had been viewed 2149 times. Download 1134 times. Department Electrical Engineering Year 2001 Semester 2 Degree Ph.D. Type of Document Doctoral Dissertation Language English Title A UNIFIED DESIGN FRAMEWORK OF HIGH-SPEED/LOW-COST ROTATION ENGINES:

AN ANGLE QUANTIZATION PERSPECTIVEDate of Defense 2002-07-05 Page Count 123 Keyword CORDIC Vector Rotation VLSI Abstract Vector rotation is the key operation employed extensively in many digital

signal processing (DSP) applications. In this dissertation, we introduce a new

design concept called Angle Quantization (AQ). It can be used as a design

index for vector rotational operation, where the rotational angle is known in

advance. Based on the AQ process, we establish a unified design framework for

cost-effective low-latency rotational algorithms and architectures. Several

existing works, such as conventional CORDIC, AR-CORDIC, MVR-CORDIC, and

EEAS-based CORDIC algorithm, can be fitted into the design framework, forming a

Vector Rotational CORDIC Family. In addition, for MVR-CORDIC and

EEAS-based CORDIC algorithm, we address their corresponding optimization

searching algorithms, scaling operations, SQNR refinement schemes, systematic

design flow, and VLSI architectures. All the statements are supported by

extensive computer simulations and design examples. Based on the new design

framework, we can realize high-speed/low-complexity rotational VLSI circuits,

whereas without degrading the precision performance in fixed-point

implementations.Table of Content Abstract i

Acknowledgement iii

{1}Introduction}{1}

{1.1}Digital Filters}{2}

{1.2}Orthogonal Transformations}{6}

{1.3}Research Focus and Contributions}{9}

{1.3.1}Vector Rotation}{9}

{1.3.2}Definition of Vector Rotation}{10}

{1.3.3}Main Contributions}{11}

{1.4}Thesis Organization}{14}

{2}Angle Quantization Process and CORDIC Algorithm}{16}

{2.1}Concept of Angle Quantization}{16}

{2.1.1}Angle Quantization Process and SPT}{18}

{2.2}Conventional CORDIC Algorithm}{19}

{3}Modified Vector Rotational CORDIC Algorithm}{25}

{3.1}The MVR-CORDIC Algorithm}{26}

{3.2}Searching Algorithms and Comparisons}{29}

{3.2.1}Searching Algorithms}{29}

{3.2.2}Comparison of Computational Complexity and Error Performance}{32}

{3.3}Relationship between Error Performance and Design Parameters}{35}

{3.3.1}Error performance vs. number of elementary angles N}{36}

{3.3.2}Error performance vs. restricted iteration number Rm}{37}

{3.3.3}Error performance vs. searching block length D}{38}

{3.4}Selective Pre-rotation Scheme}{38}

{3.4.1}Conventional Pre-rotation Scheme}{38}

{3.4.2}Selective Pre-rotation Scheme}{40}

{3.4.3}Design Example and Simulation}{40}

{3.5}Selective Scaling Scheme}{43}

{3.5.1}Conventional Scaling Operations}{43}

{3.5.2}Selective Scaling Scheme}{45}

{3.5.3}Design Example}{46}

{3.6}Iteration-tradeoff Scheme and Design Flow}{47}

{3.6.1}Iteration-tradeoff Scheme for Rm and Rs}{47}

{3.6.2}Design Flow for the MVR-CORDIC Algorithm}{49}

{3.6.3}Design Example}{51}

{3.7}VLSI Implementation of MVR-CORDIC}{54}

{3.7.1}Iterative MVR-CORDIC Structure}{54}

{3.7.2}Parallel and Pipelined MVR-CORDIC Structure}{56}

{4}Extended Elementary Angle Set-Based CORDIC Algorithm}{58}

{4.1}Extended Elementary-Angle Set (EEAS)}{59}

{4.2}Searching Algorithms of the EEAS Scheme}{63}

{4.2.1}Greedy Algorithm}{64}

{4.2.2}Trellis-based Searching (TBS) Algorithm}{64}

{4.2.3}Error Bound of TBS Algorithm}{69}

{4.2.4}Comparison of Computational Complexity}{71}

{4.3}Performance Comparisons}{74}

{4.3.1}EEAS Scheme vs. AR Technique {74}

{4.3.2}Trellis-based Searching (TBS) Algorithm vs. Greedy Algorithm}{75}

{4.3.3}Combination of EEAS Scheme and the TBS Algorithm}{77}

{4.4}Scaling Phase of the EEAS Scheme}{78}

{4.4.1}The Extended Type-II (ET-II) Scaling Operation}{78}

{4.4.2}Simulations}{79}

{4.5}Combination of Micro-rotation Phase and Scaling Phase}{80}

{4.5.1}Design Example}{80}

{4.5.2}Simulation of complete EEAS-based CORDIC Algorithm}{81}

{4.6}VLSI Structures of the EEAS-based CORDIC Algorithm}{83}

{5}Vector Rotational CORDIC Family}{87}

{5.1}Link AQ Process with Conventional CORDIC algorithm}{87}

{5.2}Link AQ Process with the AR Technique}{89}

{5.3}Link AQ Process with MVR-CORDIC Algorithm}{91}

{5.4}Link AQ Process with EEAS-based CORDIC Algorithm}{92}

{5.5}Generalized EEAS Scheme}{93}

{5.6}Family of Vector Rotational CORDIC Algorithm}{94}

{6}Conclusions and Future Researches}{96}

{A}Analysis of SQNR}{100}Reference 1. S Haykin Adaptive Filter Theory New Jersey Prentic Hall Inc 3rd ed

2. E C Ifeachor and B W Jervis Digital signal processing A practical approach Addison

Wesley

3. J D Markel and A H Gray Linear prediction of speech New York Springer Verlag

4. A V Oppenheim and R W Schafer Discrete time signal processing New Jersey Prentice

Hall

5. P P Vaidyanathan A uni ed approach to orthogonal digital lters and wave digital lters

based on the LBR two pair extraction IEEE Trans Circuits Syst pp July

6. A Y Wu K J R Liu and A Raghupathy System architecture of an adaptive recon g

urable DSP computing engine IEEE Trans Circuits Syst VideoTechnol vol pp

Feb

7. J G Chung and K K Parhi Pipelined lattiec and wave digital recursive lters Norwell

Kluwer Academic Publishers

8. J W Cooley and J W Tukey An algorithm for machine calculation of complex Fourier

series Math Computation vol pp April

9. S V Vaseghi Advanced signal processing and digital noise reduction Wiley Teubner

10. I Pitas Digital image processing algorithms and applications John Wiley Sons Inc

11. Asymmetric digital subscriber line ADSL metallic interface ANSI Std T

12. Very high speed rate digital subscriber line VDSL metallic interface T E ANSI Doc

uments Nov

13. K R Rao and P Yip Discrete cosine transform algorithm advantages applications

Academic Press San Diego Calif

14. Information technology Digital compression and coding of continuous tone still images

Requirements and guidelines ISO IEC ISO IEC

15. Information technology Coding of moving pictures and associated audio for digital storage

media at up to about Mbit s ISO IEC

16. M R Portno Time frequency representation of digital signals and systems based on short

time Fourier analysis IEEE Trans Acoust Speech Signal Processing vol pp

Feb

17. O Riol and M Vetterli Wavelets and signal processing IEEE Signal Processing Magazine

vol pp Oct

18. Y H Hu and Z Wu An e cient CORDIC array structure for the implementation of discrete

cosine transform IEEE Trans on Signal Processing vol pp Jan

19. J H Hsiao L G Ghen T D Chiueh and C T Chen High throughput CORDIC based

systolic array design for the descrete cosine transform IEEE Trans Circuits Syst Video

Technol vol pp Jan

20. A M Despain Fourier transform computers using CORDIC iterations IEEE Trans on

Computers vol pp Oct

21. A M Despain Very fast Fourier transform algorithms for hardware implementation IEEE

Trans on Computers vol pp May

22. A Madisetti A Kwentus and A J Willson A sine cosine direct digital frequency synthe

sizer using an angle rotation algorithm in IEEE International Solid State Circuits Confer

ence Digest of Technical Papers st ISSCC pp

23. E Grayver and B Daneshrad Direct digital frequency synthesis using a modi ed CORDIC

in Proc IEEE Int Symp Circuits and Systems vol Monterey CA USA pp

24. J Hormigo J Villalba and E Zapata Interval sine and cosine functions computation

based on variable precision CORDIC algorithm in th IEEE Symposium on Computer

Arithmetic Proceedings pp

25. J Vankka M Kosunen J Hubach and K Halonen A CORDIC based multicarrier QAM

modulator in Global Telecommunications Conference pp

26. J Vankka M Kosunen I Sanchis and K Halonen A multicarrier QAM modulator IEEE

Trans Circuits Syst II vol pp Jan

27. K Hwang Computer arithmetic Principles architecture and design New York Wiley

28. H Samueli An improved search algorithm for the design of multiplierless FIR lters with

power of two coe cients IEEE Trans Circuits Syst vol pp July

29. Y C Lim R Yang D Li and J Song Signed power of two term allocation scheme for

the design of digital lters IEEE Trans Circuits Syst II vol pp May

30. C S Wu and A Y Wu Modi ed vector rotational CORDIC MVR CORDIC algorithm

and architecture IEEE Trans Circuits Syst II vol pp June

31. C S Wu and A Y Wu A novel rotational VLSI architecture based on extended elementary

angle set CORDIC algorithm in Proc IEEE nd IEEE Asia Paci c ConferenceonASICs

Cheju South Korea pp

32. C S Wu A Y Wu and S J Jou A new CORDIC algorithm and architecture based

on extended elementary angle set and trellis based searching scheme submitted to IEEE

Trans Signal Processing for publication

33. G David Fornet Jr The Viterbi algorithm Proceedings of the IEEE vol pp

March

34. S Lin and Daniel J Costello Jr Error control coding Prentice Hall

35. B Sklar Digital communications fundamentals and applications Prentice Hall

36. Y H Hu and S Naganathan An angle recoding method for CORDIC algorithm implemen

tation IEEE Trans on Computers vol pp Jan

37. A Y Wu and C S Wu A uni ed view for vector rotational CORDIC algorithms and

architectures based on angle quantization approach to appear in IEEE Trans Circuits

Syst I

38. J E Volder The CORDIC trigonometric computing technique IRE Trans on Electronic

Computers vol pp Sept

39. J S Walther A uni ed algorithm for elementary functions Spring Joint Computer Conf

pp

40. Y H Hu CORDIC based VLSI architectures for digital signal processing IEEE Signal

Processing Magazine pp July

41. Y H Hu The quantization e ects of the CORDIC algorithm IEEE Trans on Signal

Processing vol pp April

42. M D Ercegovac and T Lang Redundant and on line CORDIC application to matrix

triangularization and SVD IEEE Trans on Computers vol pp June

43. N Takagi T Asada and S Yajima Redundant CORDIC methods with a constant scale

factor for sine and cosine computation IEEE Trans on Computers vol pp

Sept

44. G L Haviland and A A Tuszynski A CORDIC arithmetic processor chip IEEE Trans

on Computers vol no pp

45. H M Ahmed J M Delosme and M Morf Highly concurrent computing structures for

matrix arithmetic and signal processing IEEE Computer vol no pp

46. J M Delosme A processor for two dimensional symmetric eigenvalue and sigular value

arrays in Proc th Asilomar Conf on Circ Syst and Compu pp

47. C L Chen and A N W Jr A trellis search algorithm for the design of FIR lters with

signed powers of two coe cients IEEE Trans Circuits Syst II vol pp Jan

48. A P Chandrakasan S Sheng and R W Brodersen Low power CMOS digital design

IEEE J Solid State Circuits vol pp April

49. Y C Lim and S R Parker FIR lter design over a discrete power of two coe cient space

IEEE Trans Acoust Speech Signal Processing vol pp June

50. Q Zhao and Y Tadakoro A simple design FIR lters with power of two coe cients IEEE

Trans Circuits Syst vol pp MayAdvisor An-Yeu Wu(§d¦w¦t)

Shyh-Jye Jou(©P¥@³Ç)

Files approve immediately

85324017.pdf Date of Submission 2002-07-11

Our service phone is (03)422-7151 Ext. 57407,E-mail is also welcomed.