CORDIC 理論
1.1、坐標鏇轉數字計算機CORDIC坐標鏇轉數字計算機CORDIC(COordinate Rotation digital computer)算法，通過移位和加減運算，能遞歸計算常用函式值，如Sin，Cos，sinh，Cosh等函式，由J. Volder於1959年提出，首先用於導航系統，使得矢量的鏇轉和定向運算不需要做查三角函式表、乘法、開方及反三角函式等複雜運算。J. Walther在1974年用它研究了一種能計算出多種超越函式的統一算法。
1.2、CORDIC原理如圖所示，初始向量（X(0)，Y(0)）鏇轉θ角度之後得到向量（X1，Y1），此向量有如下關係：
CORDIC算法Y1=Y0*cos(θ)+X0*sin(θ)=cos(θ)(Y0+X0*tan(θ))
註：θ為待求角
假設初始向量經過N次鏇轉之後得到新向量，且每次鏇轉角度δ正切值都為2的倍數，則第i次鏇轉角度為δ=arctan(2^(-i))，即cosδ=（1/（1+2^(-2i)））^0.5。
容易得到角度θ≈∑S(i)●δ(i)，其中S(i)=1或－1，表示鏇轉角度的方向，
第i步鏇轉可以表示為：
X(i+1)=(（1/（1+2^(-2i)））^0.5)●(X(i)-S(i)Y(i)2^(-i))
Y(i+1)=(（1/（1+2^(-2i)））^0.5)●(Y(i)+S(i)X(i)2^(-i))
其中（1/（1+2^(-2i)））^0.5)稱為校模因子，當鏇轉次數一定時，趨於一個常數，Π（1/（1+2^(-2i)））^0.5)≈0.6073
這樣，算法每一步就可以簡化為：
X(i+1)=(X(i)-S(i)Y(i)2^(-i))
Y(i+1)=(Y(i)+S(i)X(i)2^(-i))
從而可以看出，對於移動的角度θ，現在只需要硬體加減法器和移位器就可以算出結果。引入Z，表示i次鏇轉後相位累加的部分和，則：
Z(i+1)=Z(i)-S(i)arctan(2^(-i))
經過n次鏇轉之後，Z→0，即與目標角重合，即：
X(n)=X1=X0*cos(θ)-Y0*sin(θ)
Y(n)=Y1=Y0*cos(θ)+X0*sin(θ)1.3、三角函式的計算
以sin/cos計算為例，可利用正/餘弦的和角公式遞歸進行：
cos(a+b) = cos(a)cos(b) – sin(a)sin(b) = cos(a) [cos(b) – tan(a)sin(b)]
sin(a+b) = sin(a)cos(b) + cos(a)sin(b) = cos(a) [tan(a)cos(b) +sin(b)]
取a=arctan(2^-k), 即tan(a)=2^-k, 則cos(b) – tan(a)sin(b) 可通過移位和減法來實現。
如果角度z可以表示為z = s0 arctan(2^0) + s1 arctan(2^-1) + ... + sn arctan(2^-n), 其中s0, s1, ..., sn取+1或-1(+1可以理解為逆時針轉角，即加上一個角度； -1則相反) ，那么角度z的sin/cos計算可以通過一系列的移位和加減運算來實現。注意到cos(sk arctan(2^-k))=cos(arctan(2^-k)) 與轉角方向無關。此外，z應取第一項限角度(收斂域)，對於其他項限角度，可由其第一項限對應角度變換得到。
相類似地，sinh/cosh的計算利用以下公式：
cosh(a+b) = cosh(a)cosh(b) + sinh(a)sinh(b) = cosh(a) [cosh(b) + tanh(a)sinh(b)]
sinh(a+b) = sinh(a)cosh(b) + cosh(a)sinh(b) = cosh(a) [tanh(a)cosh(b) + sinh(b)]
取a=arctanh(2^-k), 即tanh(a)=2^-k, 則cosh(b) + tanh(a)sinh(b) 可通過移位和減法來實現。如果參數z可以表示為z = s1 arctanh(2^-1) + s2 arctanh(2^-2) + ... + sn arctanh(2^-n), 其中s1, s2, ..., sn取+1或-1 ，那么z的sinh/cosh計算可以通過一系列的移位和加減運算來實現。
z應取[-ln2, ln2]範圍內的值，否則應先預處理 z = z’– pln2, 求得cosh(z’)/sinh(z’)的值，則
cosh(z) = cosh(z’)cosh(pln2) + sinh(z’)sinh(pln2) = ½[cosh(z’) + sinh(z’)]2^p + ½[cosh(z’) – sinh(z’)]2^-p
sinh(z) = sinh(z’)cosh(pln2) + cosh(z’)sinh(pln2) = ½[cosh(z’) + sinh(z’)]2^p + ½[sinh(z’) – cosh(z’)]2^-p 。
sin/cos和sinh/cosh的計算是CORDIC算法的兩個特例，CORDIC算法可描述如下：
給定初始值x(0), y(0), z(0),
x(k+1) = x(k) – ms(k)y(k)2^-q(m,k), y(k+1) = y(k) + s(k)x(k) 2^-q(m,k), z(k+1) = z(k) – s(k)d(k),
其中m表示模式，q(m,k) 為移位序列，s(k) 取+1或-1表示鏇轉方向，d(k) 為遞進角度。
以cos(a)/sin(a)計算為例，m = 1, x(0) = 1, y(0) = 0, z(0) = a, s(k) = sign(z(k)),移位序列q(1,k): 0, 1, 2, ..., 遞進角度為d(k)=arctan(2^-q(1,k)) 。
下面是實現的Matlab程式（保存為m檔案）：
function [sin,cos] =cordic(angle);
% 初始化
x = 1;
y = 0;
z = angle;
a = 0;
d = 1;
k = 0.6073; %K 增益
x = k*x;
while abs(z)>1e-5 %判斷d的符號
if z >=0
d=1;
else
d=-1;
end
%疊代
xNew=x;
x=xNew-(y*d*(1/2^a));
y=y+(xNew*d*(1/2^a));
z=z-(d*(atan(1/2^a)));
a=a+1;
end
cos= x
sin= y
k值為cos(arctan(1)), cos(arctan(2^-1)), ..., cos(arctan(2^-K) 的連積值，收斂為0.6072529350。
以cosh(a)/sinh(a)計算為例，m = -1, x(0) = 1, y(0) = 0, z(0) = a, s(k) = sign(z(k)),移位序列q(-1,k): 1, 2, 3, 4, 4, 5, ... (3n+1重複兩次以保證收斂， 4, 13, 40, ...), 遞進角度為d(k)=arctanh(2^-q(-1,k)) 。
通過對初始值和鏇轉方向s(k) 的選擇，模式m=0可以計算乘法和除法； 模式m=1可以計算sin/cos/arcsin/arccos/arctan; 模式m=-1可直接計算sinh/cosh/exp/arctanh/ln/sqrt, 間接計算arcsinh/arccosh，參見。
MATLAB 代碼實現2：
m=1;
u=1;
K=1.6468;
a=[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ];
y0=0;
x0=1/K;
angle = 30;
z0=angle*pi/180;
for i=1:length(a)
x=x0-m*u*y0*2^(-a(i));
y=y0+u*x0*2^(-a(i));
z=z0-u*atan(2^(-a(i)));
x0=x;
y0=y;
z0=z;
u=sign(z0);
end
cosine = x;
sine = y;
現實意義
由於具有頻率精度高、轉換時間短、頻譜純度高以及頻率相位易編程等特點，數控振盪器(NCO)被廣泛套用於軟體無線電數字上、下變頻以及各種頻率和相位數字調製解調系統中。NCO傳統的實現方法主要有查表法、多項式展開法或近似法，但這些方法在速度、精度、資源方面難以兼顧。而採用CORDIC算法來實現超函式時，則無需使用乘法器，它只需要一個最小的查找表(LUT)，利用簡單的移位和相加運算，即可產生高精度的正餘弦波形，尤其適合於FPGA的實現。
數字控制振盪器（NCO，numerical controlled oscillator）是軟體無線電、直接數據頻率合成器（DDS，Direct digital synthesizer）、快速傅立葉變換（FFT，Fast Fourier Transform）等的重要組成部分，同時也是決定其性能的主要因素之一，隨著晶片集成度的提高、在信號處理、數字通信領域、調製解調、變頻調速、制導控制、電力電子等方面得到越來越廣泛的套用。
