[Back to Results | New Search]

Student Number 86324008 Author Chia-Ho Pan(¼ï¨Îªe) Author's Email Address No Public. Statistics This thesis had been viewed 449 times. Download 11 times. Department Electrical Engineering Year 1998 Semester 2 Degree Master Type of Document Master's Thesis Language zh-TW.Big5 Chinese Title Modify Angle Recording Method for Cost-efficient Implementation of CORDIC Algorithm Date of Defense Page Count 48 Keyword AR-CORDIC CORDIC MAR-CORDIC SQNR Abstract The COordinate Rotational DIgital Computer (CORDIC) algorithm is a well-known Digital Signal Processing (DSP) algorithm for computing vector rotation and trigo-nometric functions. The main concept of the CORDIC algorithm is to decompose the de-sired rotation angle into iterations of pre-defined elementary rotation angles. The rotation operation can be performed by simple shift-and-add operations. The simplicity and regu-larity of CORDIC processor makes it very suitable for Very Large Scale Integrated (VLSI) circuit implementation. Nevertheless, the major disadvantage of CORDIC algorithm is its slow computational speed. Hence, it is essential to improve the processing latency. In the thesis, we consider a cost-efficient architecture, based on that the rotation angle is known in advance, to improve the speed performance of the CORDIC processor. We call it Modified Angle-Recording CORDIC (MAR-CORDIC). In the MAR-CORDIC scheme, we extend the set of rotational sequence from mi = {1, -1} to mi = {1, 0, -1}. Then, we also allow that each the micro-rotation can be performed more than once, so that the MAR-CORDIC can be operated in a more flexible way. On the other hand, we also restrict the maximum iteration number without sacrificing SQNR performance for cost-efficient of hardware implementation. The modifications presented in the thesis improve the speed and reduce the area of CORDIC implementation. The impact of speed performance on the CORDIC processor architecture is also discussed. Finally, we apply the MAR-CORDIC to Fast Fourier Transform (FFT) VLSI architecture. From the example, we can see its effec-tiveness in saving hardware cost in roataion-base circuit. Table of Content Chapter 1Introduction 1

1.1Motivation and Objective 2

1.2Thesis Organization 4

Chapter 2The Conventional CORDIC and Angle Recording Method5

2.1The Conventional CORDIC 5

2.2Angle Recording method of the CORDIC algorithm 10

2.2.1The advantages of AR-CORDIC 11

2.2.2The disadvantages of the AR-CORDIC 11

Chapter 3MAR-CORDIC and Searching Algorithm 13

3.1The Proposed MAR-CORDIC 14

3.2Searching Algorithm for ki and mi Sequence 16

3.2.1Greedy Algorithm 16

3.2.2Exhaustive Algorithm 18

3.2.3Semi-greedy Algorithm 18

3.2.4Design Example of the Searching Algorithm 18

3.3Scaling Operations 21

3.3.1Scaling operations in conventional CORDIC 22

3.3.2Scaling operations in MAR-CORDIC 22

Chapter 4Computational Complexity and SQNR Performance 24

4.1Comparison of the three searching algorithms 24

4.2Relationship between SQNR and parameters 26

4.2.1SQNR versus wordlength (N) 26

4.2.2SQNR versus restricted iteration number (R) 27

4.3Comparison of Hardware Complexity and Timing Delay 28

4.3.1Comparison of Area 29

4.3.2Comparison of speed 29

Chapter 5Implementation and Verification of MAR-CORDIC 31

5.1VLSI Implementation 31

5.1.1Iterated CORDIC structure 31

5.1.2Parallel and pipelined CORDIC structure 32

5.2Verification of conventional CORDIC and MAR-CORDIC 34

5.2.1Simulation Result of conventional CORDIC 34

5.2.2Simulation Result of MAR-CORDIC 34

Chapter 6Application of MAR-CORDIC to SIPO Lattice-based FFT 38

6.1Parallel Lattice Structure of the FFT 38

6.2Application of the MAR-CORDIC Structure to FFT 41

Chapter 7Conclusion 44Reference [1] Y. H. Hu, "CORDIC-based VLSI architecture for digital signal processing," IEEE Signal Processing Magazine, pp. 16-35, July 1992.

[2] K. Jainandunsing and E. F. Deprettere, "A new class of parallel algorithm for solving systems of linear equation," SIAM J. Sci. Stat Comput., vol. 10, pp. 880-912, Sep. 1989.

[3] P. P. Vaidyanathan, "A unified approach to orthogonal digital filters and wave digital filters based on the LBR two-pair extraction," IEEE Trans. Circuits Syst., pp. 673-686, July 1985.

[4] A. Y. Wu, K. J. R. Liu, and A. Raghupathy, "System architecture of and adaptive reconfigurable DSP computing engine," IEEE Trans. Circuits Syst. Video Technol., vol. 8, pp. 53-73, Feb. 1998.

[5] M. D. Ercegovac and T. Lang, "Redundant and on-line CORDIC : application to matrix triangularization and SVD," IEEE Trans. on Computers, vol. 39, pp. 725-740, June 1990.

[6] A. M. Despain, "Very fast Fourier transform algorithms for hardware iplementa-tion," IEEE Trans. on Computers, vol.28, pp. 333-341, May 1979.

[7] Y. H. Hu, "The quantization effects of the CORDIC algorithm," IEEE Trans. on Signal Processing, vol. 40, pp. 834-844, April 1992.

[8] N. Takagi, T. Asada, and S. Yajima, "Redundant CORDIC methods with a con-stant scale factor for sine and cosine computation," IEEE Trans. on Computers, vol. 40, pp. 989-995, Sept. 1991.

[9] J. E. Volder, "The CORDIC trigonometric computing technique," IRE Trans. on Electronic Computers, vol. EC-8, no. 3, pp. 330-334, 1959.

[10] J. S. Walther, "A unified algorithm for elementary functions," Proc. Spring Joint Computers Conference, pp. 379-385, 1971.

[11] D. Timmermann, H. Hahn, and B. J. Hosticka, "Low latency time CORDIC algo-rithms," IEEE Trans. on Computers, vol. 41, no. 8, pp. 1010-1015, Aug. 1992.

[12] Elisardo Antelo, Javier D. Bruguera, Julio Villalba, and Emilio L. Zapata, "Re-dundant CORDIC rotator based on parallel prediction," IEEE Symposium on Computer Arithmetic, pp. 172-179, 1995.

[13] Y. H. Hu, and S. Naganathan, "An angle recording method for CORDIC algo-rithm implementation," IEEE Trans. on Computers, vol. 42, no. 1, pp. 99-102, Jan. 1993.

[14] Y. H. Hu, and S. Naganathan, "Efficient Implementation of the Chirp Z-Transform using a CORDIC processor," IEEE Trans. ASSP, vol. 38, no. 2, pp. 352-354, Feb. 1990.

[15] Y. H. Hu, and P. H. Milenkovic, "A fast least square deconvolution algorithm for vocal tract corss-section estimation," IEEE Trans. ASSP, vol. 38, no. 6, pp. 921-924, June 1990.

[16] Cavallaro. J. R., and F. T. Luk, "Architecture for a CORDIC SVD processor," Proc. SPIE Int. Soc. Opt. Eng. (USA), vol. 698, pp. 45-53, 1987.

[17] Y. H. Hu, and S. Naganathan, "A novel implementation on CORDIC," IEEE Trans. on Computers, vol. 40, pp. 989-995, Sept. 1991.

[18] Oppenheim. A. V., and R. W. Schafer, Digital Signal Processing, Prentice-Hall, 1975.

[19] W. H. Chen, C. H. Smith, and S. C. Fralick, "A fast computational algorithm for the discrete cosine transform," IEEE Trans. on Communications, vol. COM-25, pp. 1004-1009, Sept. 1977.

[20] E. H. Wold, and A. M.. Despain, "Pipelined and parallel-pipelined FFT proces-sors for VLSI implementation," IEEE Trans. on Computers, May 1984.

[21] L. R. Rabiner, and B. Gold, Theory and Application of Digital Signal Processing, Prentice-Hall, 1975.

[22] Shousheng He, and M. Torkelson, "A new approach to pipeline FFT processor," IEEE Proceedings of IPPS'96, pp. 766-770, 1996.

[23] A. A. J. Delange, Ed. F. Deprettere, A. J. Vander Veen, and J. Bu, "Real time ap-plications of the floating point pipeline CORDIC processor in massive-parallel pipelined DSP algorithms," Proc. ICASSP Int'l Conf. On Acoustic, Speech, and Signal Processing, pp. 1013-1016, April 1990.

[24] Ed. F. Deprettere, P. Dewide, and R. Udo, "Pipelined CORDIC architecture for fast VLSI filtering," IEEE Int'l Conf. On ASSP, Florida, pp. 41A.6.1-4, April 1984.

[25] J. S.Chow, J. C. Tu, and J. M. Cioffi, "A discrete multitone transceiver system for HDSL applications," IEEE J. Select. Areas Commun., vol. 9, pp. 895-908, Aug. 1991.

[26] K. Sistanizadeh, P. Chow, and J. M. Cioffi, "Muti-tone transmission for asymmet-ric digital subscriber lines (ADSL)," in Proc. ICC'93, pp. 756-760, 1993.

[27] I. Lee, J. S. Chou, and J. M. Cioffi, "Performance evaluation of a fast computa-tion algorithm for the DMT in high-speed subscriber loop," IEEE J. Select. Areas Commun., vol. 13, pp. 1560-1570, Dec. 1995.

[28] T. N. Zogakis, J. T. Aslanis Jr., and J. M. Cioffi, "A coded and shaped discrete multitone system ," IEEE Trans. Commun., vol. 43, pp. 2941-2949, Dec. 1995.

[29] Ulrich Reimers, "Digital Video Broascasting (DVB): The future of television," Physics World, April 1998.

[30] Web site at URL: http://www.dvb.org/.

[31] "Draft Implementation Guideline for DVB-T Transmission aspects," Valida/Implementation Guideline to DVB-T/30, April 1997.

[32] Xiaobo Hu, Steven C. Bass, "A neglected error source in the CORDIC algo-rithm," IEEE Symposium on Circuits and Systems, vol. 1, pp. 766-769, May 1993.

[33] B. Yang, and J. F. Bohme, "Reducing the computations of the SVD array given by Brent and Luk," Proc. SPIE Advanced algorithms and architectures for signal processing, vol. 1152, pp. 92-102, Aug. 1989.

[34] A. Y. Wu, and T. S. Chan, "Cost-efficient parallel lattice VLSI architecture for the IFFT/FFT in DMT transceiver technology," IEEE Int. Conf. Acoust., Speech, and Signal Processing (ICASSP'98), Seattle, pp. VI 3517-3520, May. 1998.

[35] K. J. Ray Liu, and C. T. Chiu, "Unified parallel lattice structures for time-recursive discrete cosine/sine/Hartly transforms," IEEE Trans. Signal Processing, vol. 41, no. 3, pp. 1357-1377, Mar. 1993.

[36] K. J. Ray Liu, C. T. Chiu, T. K. Kolagotla, and J. F. J'aJ'a, "Optimal unified ar-chitectures for the real-time computation of time-recursive discrete sinusoidal transforms," IEEE Trans. on Circuits and Systems for Video Technology, vol. 4, no. 2, pp. 168-180, Apr. 1994.Advisor An-Yeu Wu(§d¦w¦t)

Files No Any Full Text File. Date of Submission

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