關(guān)于FPGA設(shè)計(jì)中使用CORDIC算法的教程分享

雖然CORDIC 是實(shí)現(xiàn) DSP 和數(shù)學(xué)函數(shù)最重要的算法之一，但許多設(shè)計(jì)人員并不熟悉。

大多數(shù)工程師在碰到需要在 FPGA 中實(shí)現(xiàn)諸如正弦、余弦或開平方這樣的數(shù)學(xué)函數(shù)時(shí)，首先會(huì)想到的是用查找表，可能再結(jié)合線性內(nèi)插或者冪級(jí)數(shù)（如果有乘法器可用）。不過對(duì)這種工作來說，CORDIC 算法是工具庫中最重要的工具之一，只是鮮有工程師知曉。

CORDIC 的意思是坐標(biāo)旋轉(zhuǎn)數(shù)字計(jì)算機(jī)， 是 JackVolder 在 1959 年為康維爾公司 (Convair) B-58A“盜賊”項(xiàng)目設(shè)計(jì)新的導(dǎo)航計(jì)算機(jī)時(shí)發(fā)明的。這是一種設(shè)計(jì)用于計(jì)算數(shù)學(xué)函數(shù)、三角函數(shù)和雙曲函數(shù)的簡(jiǎn)單算法。

這種算法的真正優(yōu)勢(shì)在于只需要采用極小型的 FPGA封裝就可以實(shí)現(xiàn)它。CORDIC 只需要一個(gè)小型查找表，加上用于執(zhí)行移位和加法的邏輯。重要的是這種算法不需要專門的乘法器或除法器。

這種算法是 DSP 以及工業(yè)與控制應(yīng)用最有用的工具之一，其最為常見的用途是實(shí)現(xiàn)如表 1 所示的傳統(tǒng)數(shù)學(xué)函數(shù)，可在器件缺少專用乘法器或 DSP 模塊的情況下提供器件所需的乘法器、除法器或更有意義的函數(shù)。舉例來說，設(shè)計(jì)人員在眾多小型工業(yè)控制器中使用 CORDIC 來實(shí)現(xiàn)數(shù)學(xué)傳遞函數(shù)和真正的 RMS 測(cè)量。工程師也在生物醫(yī)學(xué)應(yīng)用中使用 CORDIC 來進(jìn)行快速傅里葉變換 (FFT) 計(jì)算，以分析多種生理信號(hào)的頻譜。在本應(yīng)用中，結(jié)合傳統(tǒng)的數(shù)學(xué)函數(shù)，設(shè)計(jì)人員使用 CORDIC 實(shí)現(xiàn) FFT 旋轉(zhuǎn)因子。

CORDIC 詳解
CORDIC 算法可以采用線性、圓或雙曲線三種配置中的任何一種進(jìn)行運(yùn)算。而對(duì)于每種配置，算法又可以在旋轉(zhuǎn)或向量任一模式下執(zhí)行。在旋轉(zhuǎn)模式下，輸入向量按一定的角度旋轉(zhuǎn)，而在向量模式下，算法將輸入向量旋轉(zhuǎn)到 X 軸，同時(shí)記錄旋轉(zhuǎn)角度。

另外，可以從 CORDIC 的輸出求出其它函數(shù)。許多情況下，甚至可以使用另一個(gè)配置截然不同的 CORDIC來實(shí)現(xiàn)這些函數(shù)，如下所示：

下面的統(tǒng)一算法涵蓋了 CORDIC 的所有三種配置。該算法有 X、Y 和 Z 三種輸入。表 2 是根據(jù)配置預(yù)先計(jì)算的查找表值，表 3 則是根據(jù)運(yùn)算模式（向量或旋轉(zhuǎn)）在啟動(dòng)時(shí)的初始化方式。

其中m表示雙曲線（m=-1），線性（m=0）或旋轉(zhuǎn)（m=1）配置。ei 值則為不同配置下的對(duì)應(yīng)的旋轉(zhuǎn)角度。ei 值一般在FPGA 中通過小查找表實(shí)現(xiàn)，如表 2 所示。

在這個(gè)等式中，di 為旋轉(zhuǎn)方向，這取決于運(yùn)算模式。在旋轉(zhuǎn)模式下，如果 Zi < 0，則 di = -1，否則 di = +1；在向量模式，如果 Yi < 0，則 di = +1，否則 di = -1。

在圓函數(shù)旋轉(zhuǎn)模式或雙曲線旋轉(zhuǎn)模式下，輸出結(jié)果將有增量，這部分增量可以通過下面等式中定義的旋轉(zhuǎn)次數(shù)來預(yù)先求得。

這部分增量一般反饋到算法的初始設(shè)置中，以免對(duì)結(jié)果進(jìn)行后縮放。

設(shè)計(jì)人員在工作時(shí)必須牢記 CORDIC 算法只能在嚴(yán)格收斂域內(nèi)運(yùn)算?？赡苄枰M(jìn)行一定的預(yù)縮放，以確保其能夠按預(yù)期執(zhí)行。需要指出的是，決定執(zhí)行的迭代（串行）或級(jí)數(shù)（并行）的次數(shù)越多，得到的運(yùn)算結(jié)果就越準(zhǔn)確。經(jīng)驗(yàn)法則告訴我們，如果需要 n 位的精度，就需要進(jìn)行 n 次迭代或 n 個(gè)級(jí)數(shù)。不過在橫切代碼前，所有這些都可以采用諸如 Excel 或 MATLAB? 等簡(jiǎn)易工具輕松完成建模，從而確保能夠用選定的迭代次數(shù)得到精確的結(jié)果。

根據(jù)定義，CORDIC 算法只能在有限的輸入值范圍內(nèi)收斂（工作）。對(duì)采用圓函數(shù)配置的 CORDIC 算法而言，只要角度不大于查找表中的角度之和（即在 -99.7°到99.7°之間）即可保證收斂。對(duì)大于這個(gè)范圍的角度，必須使用三角恒等式將其轉(zhuǎn)換為這個(gè)范圍內(nèi)的角度。采用線性配置時(shí)，其收斂亦如此。但是，要實(shí)現(xiàn)雙曲線配置下的收斂，必須重復(fù)進(jìn)行一定數(shù)量的迭代（4、13、40、K…3K+1）。在這種情況下最大輸入值 θ 約為 1.118 弧度。

CORDIC 應(yīng)用
設(shè)計(jì)人員在從數(shù)字信號(hào)處理和圖像處理到工業(yè)控制等多種應(yīng)用中采用CORDIC 算法。最基本的用法是將CORDIC 與相位累加器結(jié)合，以生成正弦波和余弦波，供 I 調(diào)制和 Q 調(diào)制使用。使用該算法生成這些波形，如果生成正確，可以實(shí)現(xiàn)高度的無雜散動(dòng)態(tài)范圍 (SFDR)。對(duì)大多數(shù)信號(hào)處理應(yīng)用而言，需要良好的無雜散動(dòng)態(tài)范圍。

在機(jī)器人技術(shù)領(lǐng)域，CORDIC 被用于運(yùn)動(dòng)學(xué)領(lǐng)域，對(duì)判斷機(jī)器人的關(guān)節(jié)、四肢的位置和運(yùn)動(dòng)非常有用。在該應(yīng)用中，可以使用圓函數(shù)向量模式的 CORDIC 算法輕松將坐標(biāo)值與新坐標(biāo)值相加。在圖像處理領(lǐng)域，像光照和向量旋轉(zhuǎn)這樣的三維運(yùn)算最好選用該算法來實(shí)現(xiàn)。

在 EXCEL 中建模
在橫切代碼前，建立 CORDIC 算法模型最直觀的方法之一是填制簡(jiǎn)單的Excel 數(shù)據(jù)表。這樣可以先用浮點(diǎn)數(shù)系統(tǒng)，再用可擴(kuò)展的定點(diǎn)數(shù)系統(tǒng)為迭代次數(shù)和增量（An）建模，以便為仿真過程中的代碼驗(yàn)證提供參考。

從表 4 的 Excel 模型中可以看到，將初始的 X 輸入設(shè)為 An，可以減少結(jié)果后處理工作量。初始自變量設(shè)為 Z，單位為弧度，和結(jié)果一樣。

實(shí)現(xiàn) CORDIC
如果沒有其他更好的選擇，在 FPGA中實(shí)現(xiàn) CORDIC 算法的最簡(jiǎn)單方法就是使用像賽靈思 CORE Generator?這樣的工具。CORE Generator 提供了全面的接口，供用戶定義 CORDIC的確切功能（旋轉(zhuǎn)、向量等），如圖1 所示。

令人遺憾的是，CORE Generator 不提供 CORDIC 在線性模式下工作的選項(xiàng)（該工具確實(shí)提供有執(zhí)行這些功能的獨(dú)立內(nèi)核）。不過只需要幾行就可以編寫出實(shí)現(xiàn)該算法：
LIBRARY ieee;
USE ieee.std_logic_1164.all;
USE ieee.numeric_std.all;
ENTITY synth_cordic IS PORT(
clk : IN std_logic;
resetn : IN std_logic;
z_ip : IN std_logic_vector(16 DOWNTO
0); --1,16
x_ip : IN std_logic_vector(16 DOWNTO 0);
--1,16
y_ip : IN std_logic_vector(16 DOWNTO 0);
--1,16
cos_op : OUT std_logic_vector(16 DOWNTO
0); --1,16
sin_op : OUT std_logic_vector(16 DOWNTO
0)); --1,16
END ENTITY synth_cordic;
ARCHITECTURE rtl OF synth_cordic IS

TYPE signed_array IS ARRAY (natural RANGE
<> ) OF signed(17 DOWNTO 0);

--ARCTAN Array format 1,16 in radians
CONSTANT tan_array : signed_array(0 TO 16)
:= (to_signed(51471,18),
to_signed(30385,18),
to_signed(16054,18),to_signed(8149,18),
to_signed(4090,18), to_signed(2047,18),
to_signed(1023,18), to_signed(511,18),
to_signed(255,18), to_signed(127,18),
to_signed(63,18), to_signed(31,18),

to_signed(15,18),
to_signed(7,18),to_signed(3,18),
to_signed(1,18), to_signed(0, 18));
SIGNAL x_array : signed_array(0 TO 14) :=
(OTHERS => (OTHERS =>'0'));
SIGNAL y_array : signed_array(0 TO 14) :=
(OTHERS => (OTHERS =>'0'));
SIGNAL z_array : signed_array(0 TO 14) :=
(OTHERS => (OTHERS =>'0'));
BEGIN
--convert inputs into signed format
PROCESS(resetn, clk)

BEGIN
IF resetn = '0' THEN
x_array <= (OTHERS => (OTHERS =>
'0'));
z_array <= (OTHERS => (OTHERS =>
'0'));
y_array <= (OTHERS => (OTHERS =>
'0'));
ELSIF rising_edge(clk) THEN
IF signed(z_ip)< to_signed(0,18)
THEN
x_array(x_array'low) <=
signed(x_ip) + signed('0' & y_ip);
y_array(y_array'low) <=
signed(y_ip) - signed('0' & x_ip);
z_array(z_array'low) <=
signed(z_ip) + tan_array(0);
ELSE
x_array(x_array'low) <=
signed(x_ip) - signed('0' & y_ip);
y_array(y_array'low) <=
signed(y_ip) + signed('0' & x_ip);
z_array(z_array'low) <=
signed(z_ip) - tan_array(0);
END IF;
FOR i IN 1 TO 14 LOOP
IF z_array(i-1) < to_signed(0,17)
THEN
x_array(i) <= x_array(i-1) +
(y_array(i-1)/2**i);
y_array(i) <= y_array(i-1) -
(x_array(i-1)/2**i);
z_array(i) <= z_array(i-1) +
tan_array(i);
ELSE
x_array(i) <= x_array(i-1) -
(y_array(i-1)/2**i);
y_array(i) <= y_array(i-1) +
(x_array(i-1)/2**i);
z_array(i) <= z_array(i-1) -
tan_array(i);
END IF;
END LOOP;
END IF;
END PROCESS;
cos_op <=
std_logic_vector(x_array(x_array'high)(16
DOWNTO 0));
sin_op <=
std_logic_vector(y_array(y_array'high)(16
DOWNTO 0));
END ARCHITECTURE rtl;

在 FPGA 中實(shí)現(xiàn) CORDIC 有兩種基礎(chǔ)拓?fù)?，一種是狀態(tài)機(jī)法，一種是流水線法。

如果對(duì)處理時(shí)間要求不是特別嚴(yán)格，可以使用狀態(tài)機(jī)實(shí)現(xiàn)該算法，每周期計(jì)算一次 CORDIC 迭代，直到完成要求的周期次數(shù)。如果需要高計(jì)算速度，并行架構(gòu)則更合適。上述代碼采用15 級(jí)并行旋轉(zhuǎn)模式 CORDIC 計(jì)算。它使用如表 2 所示的簡(jiǎn)單圓函數(shù)模式 ArtTan(2-i) 查找表，結(jié)合簡(jiǎn)單的陣列結(jié)構(gòu)實(shí)現(xiàn)并行級(jí)。

在五花八門的各種方法中，CORDIC 算法證明自己是一種簡(jiǎn)單且功能強(qiáng)大的算法，值得所有 FPGA 設(shè)計(jì)人員關(guān)注。更值得一提的是，使用內(nèi)核生成工具或手動(dòng)編碼可以輕松實(shí)現(xiàn) CORDIC。