User Tools

Site Tools


projects:cordic_algorithm

CORDIC Implementation

Made by: Claire Barnes

What did you do?

For my final project, I decided to implement the CORDIC algorithm in Verilog. The CORDIC algorithm implements trigonometric, hyperbolic, and logarithmic functions in digital logic using only bit-shifts, additions (and subtractions), and one look up table. I was only able to implement the sine and cosine functions. My reach goal was to implement log in any base, but I did not have time. So I focused on sine and cosine and creating a program that could input a given angle and output the sine and cosine of that angle. Currently, it only works on angles between 0 and 90 degrees.

Why did you do it?

When I first heard about the CORDIC algorithm, I thought it was too good to be true. A way to calculate all these crazy functions without doing a single multiply? How could that be? So I was intrigued and I decided to do my project on that.

How Did You Do It?

My first step was to do a lot of research into CORDIC, what it is, how it works. I learned about the history of CORDIC. How it was used to replace analog computers in B-58 bombers and it was used to make calculators in as early as the 70's. I found this great website: “http://hdlexpress.com/Verilog/VT.html”, with a very helpful video tutorial explaining the CORDIC algorithm in great detail. I must have watched this at least 3 times before I felt ready to take a stab at CORDIC.

Python

I decided that instead of going straight to Verilog (a language that I have always found rather confusing) I decided to create an implementation in a language I was much more comfortable in: Python. Creating a CORDIC program in Python allowed me to see, at a bit of a higher level, how the CORDIC algorithm works. It helped me to wrap my brain around everything going on in this fairly simple, but often confusing algorithm.

Verilog

Finally, I was ready (or at least, as ready as I ever would be) to make CORDIC in verilog. Fortunately, people had done similar things and shared their work on the internet, so even though I am on a team by myself, I certainly didn't have no help. I started by making the simple module, defining x, y, and angle inputs and sine/cosine outputs.

Then I had to produce a 31-entry long table of atan values to be my look-up-table. Each value in the table is equivalent to atan(2-i) where i starts at 0 and ends at 30. But, to create a 32-bit scaled value so that all the unsigned, fixed-point arithmetic would work out, every value was multiplied by 232 and divided by 360. Thus the atan table was created.

The CORDIC algorithm only works for values between -90 and 90 degrees. This is why my next step was to check if these conditions were true, and make the necessary changes if not. Because of the way I scaled the angles, I could simply check the leading 2 bits to see what quadrant the angle was in.

The last part was to finally implement the meat of the CORDIC algorithm where all the iterations take place that produce cosine and sine values. The number of iterations that need to be implemented depends on how many bits wide the input is. Since my inputs were 16-bits wide, I only needed 16 iterations before I wouldn't be getting any more precision. So the entire algorithm is contained in a for loop that goes though, assigns the bit-shifted X and Y variables of the current iteration, finds the sign of the current Z angle, then calculates the next values of X, Y, and Z.

Difficulties

My main difficulty was understanding and implementing fixed-point, signed arithmetic. Many of the methods I implemented, I learned from other people's work on the internet who had done similar things. So I don't fully understand what those things accomplished or if there was a better way to do it.

Future Work

Since the quadrant-checking step seems to not be working, that would be the next step so that sine and cosine work for any input angle. The next logical step would be to implement more trigonometric, logarithmic, and hyperbolic functions.

Workplan Reflection

In my workplan, my goal was to create Verilog code that would implement the CORDIC algorithm and produce sine and cosine values with the reach goal of doing logarithm as well. I almost met my minimum deliverable, but my code does not perfectly do what I had planned it to do. I think I underestimated how difficult it would be to implement signed, fixed-point math.

I didn't follow my workplan very well. I think there were a lot of contributing factors as to why, namely that it took me longer than expected to understand the CORDIC algorithm. Most notably though, I realize now that verilog is still a language I am very uncomfortable with and this was what made it take so long implement CORDIC in verilog, although I think my understanding of verilog is significantly higher now.

Code Appendix

projects/cordic_algorithm.txt · Last modified: 2013/12/19 23:19 by cbarnes