Cordic Algorithm

Cordic 全名為Coordinate Rotation Digital Computer
Cordic主要被應用在三角學(Trigonometric)的硬體運算，
像是DCT、DFT、降/升頻..etc
好處是在硬體上只要用加法器和移位器並搭配iteration的方式來實現，省掉一個乘法器。

Cordic 有兩種mode可以被選擇，一是rotation mode，另一vector mode
差別將於後面會介紹，先說明它的物理意義與推導

figure ()
我們可以想像在一個座標圓上，要從A點轉動一個角度Φ到B點，如上圖
因此B點和A點的關係可以被表示為:
x'=x*cos(Φ)-y*sin(Φ) x'=cos(Φ)[x-y*tan(Φ)]
=>換個表示式
y'=y*cos(Φ)+x*sin(Φ) y'=cos(Φ)[y+x*tan(Φ)]

如果今天我限制轉動角度使得 tan(Φ)=+/- 2^(-i)，i:iteration的次數
這樣的好處是和tan(Φ)相乘的數只要向前或向後做一位shift的動作，
即可把和tan(Φ)相乘的結果表示出來(所以是省掉一個乘法器)
但相對地，我們從A轉到B點，就無法一次轉，而是需要分段去轉到B

x(i+1)=K(i)*[ x(i)- y(i)*d(i)*2^(-i) ]
y(i+1)=K(i)*[ y(i)+ x(i)*d(i)*2^(-i) ]
where K(i)=cos(atan(2^(-i)))=1/sqrt(1+2^(-2i))
d(i)=+/- 1
當iteration num->∞,(連續乘積的K(i))最後會近似於0.6073
其倒數會近似於:An=Πn(sqrt(1+2^(-2i)))=1.647

在Cordic轉的過程中，也會去紀錄角度旋轉的變化
z(i+1)=z(i)-d(i)*atan(2^(-i))
在電路中atan(2^(-i))可以由查表法將它實現

在一開始有提到Cordic主要有Rotation跟Vector兩種mode
1.Rotation mode
一開始角度z初始值要設定成我們想要轉到的角度
每次iteration，轉的角度會慢慢變小，
一直到達我們所要轉到的位置(此時z為0)或是規定的iteration的次數

The cordic equation for rotation mode

x(i+1)=x(i)-y(i)*d(i)*2^(-i)
y(i+1)=y(i)+x(i)*d(i)*2^(-i)
z(i+1)=z(i)-d(i)*atan(2^(-i))
if z(i)<0=>d(i)=-1 ,z(i)>0 =>d(i)=1
最後x,y轉到我們想要的位置，角度z=0
x(n)=An[x(0)cos(z(0))-y(0)sin(z(0))]
y(n)=An[y(0)cos(z(0))+x(0)sin(z(0))]
z(n)=0
An=Πn(sqrt(1+2^(-2i)))=1.647


2.Vector mode
Vector mode是用於計算x,y之間夾的角度以及相對於原點的長度
所以會把y旋轉到y=0的地方,此時的x軸很自然的為相對於原點的長度
在這裡角度初始值設為0

x(i+1)=x(i)-y(i)*d(i)*2^(-i)
y(i+1)=y(i)+x(i)*d(i)*2^(-i)
z(i+1)=z(i)-d(i)*atan(2^(-i))
if y(i)<0=>d(i)=1 ,y(i)>0 =>d(i)=-1

轉完結果如下
x(n)=An*sqrt(x(0)^2+y(0)^2)
y(n)=0
z(n)=z(0)+atan(y(0)/x(0))
An=Πn(sqrt(1+2^(-2i)))=1.647