基于FPGA的Cordic算法實(shí)現(xiàn)的設(shè)計(jì)與驗(yàn)證

基于FPGA的Cordic算法實(shí)現(xiàn)的設(shè)計(jì)與驗(yàn)證CORDIC（CoordinateRotationDigitalComputer）算法即坐標(biāo)旋轉(zhuǎn)數(shù)字計(jì)算方法，是J.D.Volder1于1959年首次提出，主要用于三角函數(shù)、雙曲線、指數(shù)、對(duì)數(shù)的計(jì)算。該算法通過(guò)基本的加和移位運(yùn)算代替乘法運(yùn)算，使得矢量的旋轉(zhuǎn)和定向的計(jì)算不再需要三角函數(shù)、乘法、開(kāi)方、反三角、指數(shù)等函數(shù)。本文是基于FPGA實(shí)現(xiàn)Cordic算法的設(shè)計(jì)與驗(yàn)證，使用VerilogHDL設(shè)計(jì)，初步可實(shí)現(xiàn)正弦、余弦、反正切函數(shù)的實(shí)現(xiàn)。將復(fù)雜的運(yùn)算轉(zhuǎn)化成FPGA擅長(zhǎng)的加減法和乘法，而乘法運(yùn)算可以用移位運(yùn)算代替。Cordic算法有兩種模式，旋轉(zhuǎn)模式和向量模式?？梢栽趫A坐標(biāo)系、線性坐標(biāo)系、雙曲線坐標(biāo)系使用。本文線初步實(shí)現(xiàn)在圓坐標(biāo)系下的兩種模式的算法實(shí)現(xiàn)。Cordic算法簡(jiǎn)化旋轉(zhuǎn)模式，迭代位移算法。假設(shè)有一點(diǎn)P0（x0，y0），經(jīng)過(guò)逆時(shí)針旋轉(zhuǎn)角度θ，到達(dá)點(diǎn)Pm（xm，ym），我們根據(jù)數(shù)學(xué)運(yùn)算可以得到公式如下：xm=x0cosθ-y0sinθ=cosθ（x0–y0tanθ）ym=y0cosθ+x0sinθ=cosθ（y0–x0tanθ）如果不考慮旋轉(zhuǎn)后的向量模值，只考慮旋轉(zhuǎn)角度，即去掉cosθ，得到如下方程式。這里旋轉(zhuǎn)的角度的正確的，但x和y的值增加。cosθ值是小于等于1的，值大于等于1，所以模值應(yīng)該增大。我們不能通過(guò)適當(dāng)?shù)臄?shù)學(xué)計(jì)算去掉cosθ，但是去掉cosθ項(xiàng)可以方便我們后面的坐標(biāo)平面旋轉(zhuǎn)的計(jì)算。這里稱(chēng)為偽旋轉(zhuǎn)。xm=x0–y0tanθym=y0–x0tanθCordic的方法核心就是偽旋轉(zhuǎn)，將旋轉(zhuǎn)角θ細(xì)化成若干個(gè)大小固定的角度θi，規(guī)定θi滿足tanθi=2^-i，通過(guò)一系列的迭代旋轉(zhuǎn)，每次旋轉(zhuǎn)θi，i為迭代次數(shù)，規(guī)定∑θi的范圍即旋轉(zhuǎn)角度θ的范圍為［-99.7，99.7］。如果θ的大于這個(gè)范圍則可通過(guò)三角運(yùn)算操作轉(zhuǎn)化到該范圍的角度。我們通過(guò)事先將所有每次旋轉(zhuǎn)的角度計(jì)算出來(lái)，由于每次旋轉(zhuǎn)的角度是固定的，所以經(jīng)過(guò)i次旋轉(zhuǎn)的∑θi可能會(huì)超過(guò)θ，所以就必須設(shè)置一個(gè)方向值di，如果旋轉(zhuǎn)角度之和已經(jīng)小于θ，則di為1，下次旋轉(zhuǎn)繼續(xù)為順時(shí)針旋轉(zhuǎn)，如果旋轉(zhuǎn)角度之和大于θ，則di為-1，下次旋轉(zhuǎn)為逆時(shí)針。設(shè)置zi+1為旋轉(zhuǎn)剩余角度，zi+1=z0–dizi，z0=θ，隨著i值得增大，zi+1會(huì)趨向于0時(shí)，即旋轉(zhuǎn)結(jié)束。di與zi的符號(hào)位相同。采用偽旋轉(zhuǎn)的方法，每次提出一個(gè)cosθi，旋轉(zhuǎn)結(jié)束后會(huì)產(chǎn)生一個(gè)∏cosθi的累乘，一旦我們確定了迭代次數(shù)，∏cosθi就是一個(gè)常數(shù)，迭代公式可寫(xiě)為。這是將cosθi提出、tanθi替換成2^-i后的結(jié)果。di與zi的符號(hào)位相同。xi+1=xi-di*yi*2^-iyi+1=yi+di*xi*2^-izi+1=z0-di*θi設(shè)迭代i=n-1，那么旋轉(zhuǎn)n次后得到Pm的坐標(biāo)應(yīng)該為（xn*∏cosθi，yn*∏cosθi）。應(yīng)為每次迭代都會(huì)提出一個(gè)cosθi，旋轉(zhuǎn)n次后的xn和yn就會(huì)少乘一個(gè)∏cosθi，所以實(shí)際上最終的Pm坐標(biāo)角度近似于（xn*∏cosθi，yn*∏cosθi）。xn*∏cosθi=x0cosθ-y0sinθyn*∏cosθi=y0cosθ+x0sinθxn=1/∏cosθi（x0cosθ–y0sinθ）yn=1/∏cosθi（y0cosθ–x0sinθ）伸縮因子，KN=1/∏cosθi，已知迭代次數(shù)，我們可以預(yù)先計(jì)算KN的值。如下這是博主使用MATLAB計(jì)算出的迭代結(jié)果數(shù)值。xn=KN（x0cosθ–y0sinθ）yn=KN（y0cosθ–x0sinθ）從上表可以得出，我們預(yù)先計(jì)算出KN的值，然后令x0=∏cosθi，y0=0，則上述公式可化簡(jiǎn)為xn=cosθyn=sinθ即可實(shí)現(xiàn)正弦、余弦操作了。旋轉(zhuǎn)模式總結(jié)一下，Cordic算法旋轉(zhuǎn)模式使用VerilogHDL的實(shí)現(xiàn)流程（1）確定迭代次數(shù)，將每次迭代的角度計(jì)算出來(lái)，預(yù)先定義為參數(shù)，為了避免浮點(diǎn)運(yùn)算，將角度值向左移位16位，取整數(shù)部分。（2）根據(jù)迭代公式進(jìn)行迭代計(jì)算，本設(shè)計(jì)取16次迭代，從上表可以看出，當(dāng)?shù)螖?shù)越大時(shí)，1/∏cosθi會(huì)趨向于一個(gè)確定值。如果對(duì)結(jié)果精度要求更高，可以設(shè)置更高的迭代次數(shù)，根據(jù)迭代次數(shù)，可以將伸縮因子KN=1/∏cosθi計(jì)算出來(lái)。同樣將其左移16位。xi+1=xi-di*yi*2^-iyi+1=yi+di*xi*2^-izi+1=z0-di*θi（3）設(shè)置x0=∏cosθi，y0=0，則求出x16=cosθ，y16=sinθ。這里需要注意的是，我們?cè)谶M(jìn)行迭代運(yùn)算的時(shí)候，將2^-i變成移位運(yùn)算，對(duì)于正余弦來(lái)說(shuō)是有正負(fù)的，所以在一開(kāi)始定義的時(shí)候，就應(yīng)該定義成有符號(hào)數(shù)，Verilog中也可以定義有符號(hào)數(shù)，最高位表示符號(hào)位，定義如下迭代寄存器定義為有符號(hào)數(shù)，那么我們移位運(yùn)算就不能用》》邏輯右移《《邏輯左移或來(lái)移位了，而是用》》》算術(shù)右移和《《《算術(shù)左移。邏輯左移也就相當(dāng)于算數(shù)左移，右邊統(tǒng)一添0，邏輯右移，左邊統(tǒng)一添0，算數(shù)右移，左邊添加的數(shù)和符號(hào)有關(guān)。例如1010_1010，［］是添加的位邏輯左移一位：0101_010［0］算數(shù)左移一位：0101_010［0］邏輯右移一位：［0］101_0101算數(shù)右移一位：［1］101_0101迭代運(yùn)算采用16級(jí)流水線，進(jìn)行運(yùn)算，最終需要判斷輸出的正余弦值在哪個(gè)象限，前面講旋轉(zhuǎn)角度θ的范圍為［-99.7，99.7］，不在這個(gè)范圍我們要進(jìn)行三角運(yùn)算使其滿足這個(gè)范圍，當(dāng)輸入的角度小于90度即可進(jìn)行計(jì)算，當(dāng)輸入角度大于90度小于180度，將輸入角度減去90度并設(shè)定當(dāng)前角度處于第二象限，然后進(jìn)行計(jì)算，當(dāng)輸入角度大于180度小于270度，將輸入的角度減去180度設(shè)置當(dāng)前角度處于第三象限，進(jìn)行計(jì)算，當(dāng)輸入的角度大于270度，減去270設(shè)置當(dāng)前角度處于第四象限，進(jìn)行計(jì)算。象限的設(shè)定通過(guò)quarant寄存器實(shí)現(xiàn)。如果角度在第一象限，sin（x）=sin（a），cos（x）=sin（a）最后的結(jié)果x16=cosθ，y16=sinθ，這里我想起了那句口訣，一全正，二正弦，三正切，四余弦如果角度在第二象限，sin（x）=sin（a+90）=cos（a），cos（x）=cos（a+90）=-sin（a）如果角度在第三象限，sin（x）=sin（a+180）=-sin（a），cos（x）=cos（a+180）=-cos（a）如果角度在第四象限，sin（x）=sin（a+270）=cos（a），cos（x）=cos（a+270）=-sin（a）對(duì)于正數(shù)，我們直接賦值輸出，負(fù)數(shù)，這里使用有符號(hào)數(shù)表示，將其取反加1即可。最終使用modelsim對(duì)算法進(jìn)行仿真，從波形圖上看已經(jīng)初步實(shí)現(xiàn)了sin，cos函數(shù)。向量模式Cordic算法在向量模式下的計(jì)算方法和旋轉(zhuǎn)模式基本上是類(lèi)似的，設(shè)有一點(diǎn)P0（x0，y0），經(jīng)過(guò)順時(shí)針旋轉(zhuǎn)角度到與軸重合，得到點(diǎn)Pm（xm，ym），即ym=0。xm=x0cosθ-y0sinθ=cosθ（x0–y0tanθ）ym=y0cosθ+x0sinθ=cosθ（y0–x0tanθ）=0我們?cè)O(shè)置x0=x，y0=y，z0=0，迭代次數(shù)為16，經(jīng)過(guò)16次迭代后得到zn=θ=arctan（y/x）和坐標(biāo)所代表的向量的模值d=xm=xn*∏cosθi，di與yi方向相反，即當(dāng)時(shí)結(jié)束運(yùn)算。實(shí)現(xiàn)方法為判斷yi的符號(hào)位，符號(hào)位為1，di為1，符號(hào)位為0，di為-1。xi+1=xi-di*yi*2^-iyi+1=yi+di*xi*2^-izi+1=z0-di*θi關(guān)于反正切函數(shù)，由于在［-99.7°，99.7°］范圍內(nèi)，所以我們輸入向量P0（