Talk:CORDIC
From Wikipedia, the free encyclopedia
Contents |
[edit] Value of K in implentations
The value in the implentation section should really be what it was before someone changed it, 0.607. My comment wasn't correct which may have led to the confusion. The inverse of K is needed to get the true magnitude because all the shifts result in a gain of K = 1.647 which then must be removed to get the true magnitude.
See the article in the references section: http://www.dspguru.com/info/faqs/cordic2.htm
- "Now, having rotated our complex number to have a phase of zero, we end up with "C = Ic + j0". The magnitude of this complex value is just "Ic" (since "Qc" is zero.) However, in the rotation process, C has been multiplied by a CORDIC Gain (cumulative magnitude) of about 1.647. Therefore, to get the true value of magnitude we must multiply by the reciprocal of 1.647, which is 0.607. (Remember, the exact CORDIC Gain is a function of the how many iterations you do."
Addps4cat 19:56, 21 March 2006 (UTC)
Yeah, the value of K in the implentation is indeed correct. However, the equation for K given in previous edition was wrong, which led to my confusion and my changing of K in the implentation before. K is defined as cos(arctan(2^(-i))), you can simply check that K should be 1/sqrt(1+2^(-2i)), instead of sqrt(1+2^(-2i)) as given before. And by this definition, lim(K)=0.6073, again not 1.647 as given before. I've corrected it and removed the "inv" in the implentation to avoid further confusion. Cdpango 11:16, 23 March 2006 (UTC)
- I hate to belabor this but I think the definition of K = 1.647 is correct. The 1.647 is a result of the 2^-i shifts (I think). Then you must undo this gain by dividing by K at the end to remove this gain. I've done the algorithm on my computer and you do indeed up with a value K times greater than it should be. For example, if I ignore K, a 90 deg. shift of (1 , 0) becomes (0, 1.647). So you indeed must either multiply by inv. K or divide by K to obtain the true result. I'll wait until you respond to this so we don't end up reverting each other's edits. Addps4cat 21:08, 23 March 2006 (UTC)
Maybe I've not expressed myself clearly. You indeed needs to multiply 0.6073(or divide 1.647) after the iterations. But the problem is we define K as "product of cos(arctan(2^(-i)))", so its value should be "product of 1/sqrt(1+2^(-2i))", instead of "product of sqrt(1+2^(-2i))", and it approaches 0.6073 when n approaches infinite. On the other hand, the system gain is A="product of sqrt(1+2^(-2i))"=1.647=1/K. I think that you just mixed up A and K. You can check the beignning part of section 3 of the following article, which explains this issue quite clearly. http://www.andraka.com/files/crdcsrvy.pdf It's nice to have a discussion. Best wishes! Cdpango 04:59, 24 March 2006 (UTC)
- Ahh I see. You are right on all accounts. Thanks for the clarification. Addps4cat 07:03, 24 March 2006 (UTC)
[edit] Mixing i and n
The article mixes in n and i for subscripts and superscripts and it is confusing. n should be used to refer to the total number of iterations while i should refer to the current iteration. This pops up in the beta(n+1) equation. I don't know if I am right so I am hesitant to change it. Maybe someone with a little more experience w/the algorithm can edit it. Addps4cat 20:01, 3 March 2006 (UTC)
- *takes a second look at what actually is written*. Hm. You are absolutely correct, it is very unclear and confusing right now. If no one else beats me to it, I'll fix it tomorrow. Henrik 01:59, 4 March 2006 (UTC)
[edit] Disputed
I can't figure out who developed it, and the articles creator left us with two choices, hence the "dispute" —siroχo 21:49, Jul 26, 2004 (UTC)
- I presume by 'it', you mean who is credited with the original development of the algorithm? Andraka says the original work is credited to Volder.
- Andraka is right, Jack Volder was the first (1959), to say nothing about Henry Briggs (1624).
[edit] accuracy
any idea of the accuracy of this algorithm and connections with the number of iterations ? any comparison between this algorithm an some others ? --bloublou 10:58, 11 August 2006 (UTC)
found also in DSP forum from Andraka "Sounds about right. THe worst case angular error after each iteration is the rotation angle of that iteration (which happens if the previous iteration landed exactly on your target angle), so the max error angle is atan(2^-i) after iteration i. Iterations start at 0. The last iteration needed to get an error of less than 0.1 degrees is therefore log2(tan(0.1)) rounded away from zero => 10, and counting from 0 you have 11 iterations to complete not counting your angle reduction." --bloublou 17:23, 11 August 2006 (UTC)
about accuracy
you can have a look at: [2] on page 13 you can see the table contained the formulae of the CORDIC errors. naturally you cant read russian but the formulaes language is international. in this table:
n - word length (number of iterations equals to n for sin, cos, OR equals to 2n
for asin, acos, ln, exp)
r - the number of additional bits of the words
and here we say about root mean square errors.
you can find many other ideas incl. cordic accuracy in [3]
Vladimir Baykov
vladimir@baykov.de
[edit] Python
Just for the record, here is the souce code in Python programming language
#!/usr/bin/python
from __future__ import division
from math import atan,pi,sqrt
import sys
def main_function(degrees,iterations = 8):
# convert from degrees into radians
beta = degrees * pi / 180.0
ArcTanTable = []
for i in range(iterations):
ArcTanTable.append( atan( 2.0**(-1 * i) ) )
KN = []
value = 1.0
for i in range(iterations):
value = value * sqrt( 1.0 + 2.0**(-2 * i) )
KN.append(1.0 / value)
Vx , Vy = 1.0 , 0.0
for i in range(iterations):
if beta < 0:
Vx,Vy = Vx + Vy * 2.0**(-1 * i) , Vy - Vx * 2.0**(-1 * i)
beta = beta + ArcTanTable[i]
else:
Vx,Vy = Vx - Vy * 2.0**(-1 * i) , Vy + Vx * 2.0**(-1 * i)
beta = beta - ArcTanTable[i]
Vx,Vy = Vx * KN[iterations - 1] , Vy * KN[iterations - 1]
print "K[%9d] = %14.12f" % (iterations - 1,KN[iterations - 1])
print "Sin(%4.1f) = %14.12f and Cos(%4.1f) = %14.12f" % (degrees,Vy,degrees,Vx)
if __name__ == '__main__':
if len(sys.argv) == 2:
deg = float(sys.argv[1])
iter = 8
elif len(sys.argv) == 3:
deg = float(sys.argv[1])
iter = int(sys.argv[2])
else:
print "using default values of 17 degrees and 8 iterations"
deg = 17.0
iter = 8
main_function(deg,iter)
Here is a sample run
$ python cordic.py 30 40 K[ 39] = 0.607252935009 Sin(30.0) = 0.500000000000 and Cos(30.0) = 0.866025403785
[edit] Strange
It seems a little strange that Volder should publish his first paper describing the CORDIC in the IRE Transactions on Electronic Computers, September 1959 and in the very same journal Daggett publishes his work on CORDIC. I reckon Daggett was peer reviewing for the journal and stole some ideas!! But seriously had Volder written an earlier or paper or were the two actually working together? Graemec2 07:46, 10 October 2006 (UTC)
