CORDIC for dummies
The CORDIC algorithm is still mysterious to many. Here is a presentation using only simple arithmetic.
In the late 50’s Convair designed for the USAF, the B-58 Hustler supersonic jet bomber.
In 56, a project was started to replace the analog computer driven navigation system with a digital computer.
Jack Volder, at that time, senior engineer in the Convair’s aero electronics department discovered an algorithm to compute transcendental functions needed for real-time navigation problems.
He started is research by the « massaging of the basic angle addition equations » that he found in his « 1946 edition of the Handbook of Chemistry and Physics » :
Let’s take now a very simple example. The angle is 0.984736 radians and we are
looking for the tangent.
We proceed by successive subtractions until overdraft. We can subtract only one time “arc tan” 1 and two times “arc tan” 0.1 :
|
0.984736 |
|
|
|
0.785398163500000 |
1 |
-0.785398163500000 |
|
0.199337836500000 |
|
|
|
-0.586060327000000 |
KO |
-0.785398163500000 |
|
|
|
|
|
0.199337836500000 |
1 |
|
|
0.099669184004000 |
2 |
-0.099668652496000 |
|
0.000000531508000 |
|
-0.099668652496000 |
|
-0.099668120988000 |
KO |
-0.099668652496000 |
Now we start back with the residual vector (X = 1, Y = 0.000000531508000) and we rotate counter clock wise (CCW) two times through angle “arc tan” 0.1 and one time through angle “arc tan” 1 :
|
|
|
|
|
|
|
CCW rotations |
X' |
Y' |
X |
Y |
|
X' = X - Y 10-j |
|
|
|
|
|
Y' = Y + X 10-j |
|
|
|
|
|
|
|
|
|
|
|
1 |
0.999999947 |
0.100000532 |
1 |
0.000000531508000 |
|
2 |
0.989999894 |
0.200000526 |
0.999999947 |
0.100000531508000 |
|
1 |
0.789999368 |
1.19000042 |
0.989999894 |
0.200000526 |
|
|
|
|
|
|
|
|
|
Y/X= |
1.50633085144 |
|
Important: there is no multiplication in the process, only shift right and subtraction operations
Look at the first CCW rotation, to calculate X’, two shift right (10-2 ) on Y and a subtraction are enough (the « digits » are shifted right in this implementation ; but in the Volder’s original Cordic the bits are shifted).
|
X |
1,000000000000000 |
|
|
|
|
Y |
0,000000531508000 |
|
|
0,000000005315080 |
|
|
|
|
|
|
|
X’ = |
0,999999994684920 |
_______________________________________________________________
(1)
The addition formula is given by Abul Wafa in the 10th century:
http://en.wikipedia.org/wiki/Abul_Wáfa
See also the Briggs’ work:
http://www.jacques-laporte.org/Briggs%20and%20the%20HP35.htm
(2) Implementing Cordic, Volder worked with powers of 2, because of the binary
ALU. HP introduced the first decimal Cordic in the HP 9100 (03/1968).
http://en.wikipedia.org/wiki/Rotation_%28mathematics%29
(3)
http://en.wikipedia.org/wiki/Imaginary_number
http://en.wikipedia.org/wiki/Complex_number
NB: The underlying structure explaining that Cordic can be presented in terms of rotations or complex number is the orthogonal group SO(2,R).
http://en.wikipedia.org/wiki/Orthogonal_group
and
http://en.wikipedia.org/wiki/Rotation_group.
See also for a unified “digit by digit” presentation of Volder’s Cordic and
Meggitt’s pseudo division and pseudo multiplication method (and the links to
download Volder’s and Meggitt’s work):
http://www.jacques-laporte.org/digit_by_digit.htm