FPGA數(shù)字信號(hào)處理之CORDIC算法

CORDIC（Coordinate Rotation Digital Computer）算法即坐標(biāo)旋轉(zhuǎn)數(shù)字計(jì)算方法。該算法通過基本的加和移位運(yùn)算代替乘法運(yùn)算，用于三角函數(shù)、雙曲線、指數(shù)、對(duì)數(shù)的計(jì)算。CORDIC算法的思想是：反復(fù)迭代，逐次逼近終值，計(jì)算結(jié)果達(dá)到一定精度即可終止。比如下邊圖中任意坐標(biāo)0 [10,20]，計(jì)算它的角度值，使用cordic算法就是三角函數(shù)不斷的旋轉(zhuǎn)坐標(biāo)系，做法就是：1、將該點(diǎn)0順時(shí)針旋轉(zhuǎn)π/2，得到點(diǎn)1；
2、由于點(diǎn)1位于第四象限，說明轉(zhuǎn)多了，再往逆時(shí)針方向轉(zhuǎn)π/4，得到點(diǎn)2；3、點(diǎn)2位置象限，順時(shí)針旋轉(zhuǎn)π/8，得到點(diǎn)3，
4、由于點(diǎn)3位于第四象限，說明轉(zhuǎn)多了，再往逆時(shí)針方向轉(zhuǎn)π/16，得到點(diǎn)4；5、點(diǎn)4位置象限，順時(shí)針旋轉(zhuǎn)π/32，得到點(diǎn)5....（根據(jù)所需精度，確定旋轉(zhuǎn)次數(shù)即可）

終把旋轉(zhuǎn)的角度求和就得到了任意坐標(biāo)[10,20]的角度值，其中坐標(biāo)旋轉(zhuǎn)用的三角函數(shù)公式為：

X1=cos(θ)(X0-Y0*tan(θ))

Y1=cos(θ)(Y0+X0*tan(θ))

上邊的例子能說明cordic算法的思想，在確定旋轉(zhuǎn)次數(shù)之后，每次旋轉(zhuǎn)的cos(θ)和tan(θ)值是確定的，這樣我們就可以用提前存儲(chǔ)的cos(θ)和tan(θ)值去計(jì)算任意坐標(biāo)的角度值。

但是上面角度旋轉(zhuǎn)過程中用到了乘法運(yùn)算，并沒有簡(jiǎn)化運(yùn)算量。接下來對(duì)cordic進(jìn)一步優(yōu)化，將上式中的cos(θ)舍棄，得到如下的結(jié)果：

循環(huán)過程中Y的正負(fù)判斷象限，決定旋轉(zhuǎn)方向，但是X/Y坐標(biāo)會(huì)向外無限循環(huán)，這時(shí)候旋轉(zhuǎn)得到的X/Y坐標(biāo)會(huì)擴(kuò)展很多倍，如下圖，注意下圖中的坐標(biāo)軸刻度是1E17。

上述旋轉(zhuǎn)過程的計(jì)算變化成了：

X1=(X0-Y0*tan(θ))

Y1=(Y0+X0*tan(θ))每次旋轉(zhuǎn)減少了兩個(gè)乘法，在需要知道正確坐標(biāo)值的情景下，比如要知道該信號(hào)的幅度，由于cordic算法的旋轉(zhuǎn)測(cè)試是確定的，所以cos(θ)確定的，所以cos(θ1)*cos(θ2)*cos(θ3)*...*cos(θn)是一個(gè)定值，只需要在旋轉(zhuǎn)之后將的X/Y值與cos(θ1)*cos(θ2)*cos(θ3)*...*cos(θn)這個(gè)定值相乘即可。上面的旋轉(zhuǎn)過程還是用到了乘法，乘法依然是FPGA/IC中的緊俏資源，下一篇文章介紹如何不用乘法的在FPGA中實(shí)現(xiàn)CORDIC。