CORDIC Algorithm

CORDIC Algorithm

COordinate Rotation DIgital Computer

Introduction :

Most engineers tasked with implementing a mathematical function such as sine, cosine or square root within an FPGA may initially think of doing so by means of a lookup table, possibly combined with linear interpolation or a power series if multipliers are available. However, in cases like this

the CORDIC algorithm also known as Volder's algorithm, is a simple and efficient algorithm to calculate hyperbolic and trigonometric functions,

The modern CORDIC algorithm was first described in 1959 by Jack E. Volder. It was developed to replace the analog resolver in the B-58 bomber's navigation computer ,also used in Intel 80x87 coprocessor and Intel 80486 .

•      This figure shows the different mode of the cordic algorithm. in our project we are intrested in the circular rotation mode.

1- Rotation of a vector by an angle θ:

For the time being, let's forget about electronics and go back to mathematics to see which operations can be achieved by simply rotating a vector.

Suppose that we have an efficient system that receives a vector and rotates it by an arbitrary angle θ.

Choosing the origin as the center of rotation, we will get to the point (xR,yR) by rotating the point (xin,yin) by θ.

xin = cos(β)        xR = cos(θ+β)

                        yin = sin(β)          yR = sin(θ+β)

xR = cos(θ) * cos(β) - sin(θ) * sin(β)

yR = cos(θ) *cos(β) + sin(θ) * sin(β)

                    

                     xR = xin cos(θ)−yin sin(θ)

yR = xin sin(θ)+yin cos(θ)

•    If we choose yin=0 and xin=1 , after rotation we will have : 

                                                          xR=cos(θ)
                                                yR=sin(θ)

2-CORDIC Algorithm: Key Ideas

Rather than computing vector rotation of (xin,yin) by θ directly, we iteratively rotate with smaller steps towards θ :

Step 1: set α = 45°

Step 2: if (θ >= α) then

α  = α + (45/2)° else α = α - (45/2)°

α  = α + (45/4)° else α = α - (45/4)° Continue by halving step size of α in each iteration Exemple : θ =30°

α   = 45 - (45/2)° =22.5°

α   = 22.5 +(45/4)°=33.75°

α  = 33.75 - (45/8)° =28.125°

• these iterations helped us to determine the choice of steps to converge toward our desired angle , which are ±45/2^i with i is the number of iteration and "± " indicates the rotation direction.

CORDIC Algorithm:

• Rotation by an arbitrary angle (± 45/2^𝑖 ,with i the number of iteration ) is difficult, because we need to calculate the tangent of each angle ,so we perform psuedorotations with special angles that :

• 2^-i is a simple shift can be directly implemented .

With these angles αi= arctan(2^-i) we will start convergerging to our desiredangle teta with small step until hopefully approching zero.

                                           If (zi>0){zi =zi –αi}

                                           Else {zi= zi+αi}

•  So we can write it this way :

                                          zi =zi – di * αi ; with di : rotation direction

3- Algorithme :

Exemple θ=30° :   z=30°
                               𝑥=1
                               𝑦=0
Iteration 0 : 
                  𝑥0 =𝑥−𝑦=1
                  𝑦0 =𝑦+𝑥=1 
                  𝑧0 =𝑧−45=−15<0                                             k0=0.7071

Iteration 1 : 
                  𝑥1 =𝑥0 +𝑦0 2=1 
                  𝑦1 =𝑦0 −𝑥0 2=0.5 
                  𝑧1 =𝑧0 +26.565=11.565>0                              K1=0.89442
Iteration 2 : 
                  𝑥2 =𝑥1 −𝑦1 4=1.375 
                  𝑦2 =𝑦1 +𝑥1 4=0.875 
                  𝑧2 =𝑧1 −14.035=−2.471<0                             K2=0.97014
Iteration 3 : 
                  𝑥3 =𝑥2 +𝑦2 8=1.48438 
                  𝑦3 =𝑦2 −𝑥2 8=0.703 
                  𝑧3 =𝑧2 +7.125=4.654>0                                  K3=0.992
Iteration 4 : 
                  𝑥4 =𝑥3 −𝑦3 16=1.44043 
                  𝑦4 =𝑦3 +𝑥3 16=0.7958 
                  𝑧4 =𝑧3 −3.576=1.078>0                                  K4=0.998

Iteration 5 : 
                   𝑥5 =𝑥4 −𝑦4 32=1.4155 
                   𝑦5=𝑦4 −𝑥4 32=0.8409 
                   𝑧5 =𝑧4 +7.125=−0.712<0                                       K5=0.999

• Ktot= K0 K1* K2* K3* K4* K5 = 0.60735

  Cos(30)= Ktot * 𝑥5 =0.85974 ≈ Cosreal(30)=0.86602

  Sin(30)= Ktot * 𝑦5 =0.510729 ≈ Sinreal(30) =0.5