CORDIC for dummies

 http://www.jacques-laporte.org/cordic_for_dummies.htm

 

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 (2 SR since 10-2)
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