使用 DSP 加速 CORDIC 算法

數(shù)字信號(hào)處理器 (DSP) 為需要快速模擬到數(shù)字到模擬轉(zhuǎn)換的應(yīng)用處理數(shù)字，例如軟件無(wú)線電和雷達(dá)。如果您沒(méi)有使用 DSP，您可以使用 CORDIC 算法在您的 IC 上執(zhí)行類似的計(jì)算。CORDIC 算法的優(yōu)勢(shì)在于它能夠在不使用乘法器的情況下求解矢量旋轉(zhuǎn)。

盡管 CORDIC 的屬性有據(jù)可查，但您不會(huì)經(jīng)常發(fā)現(xiàn)它在 DSP 上實(shí)現(xiàn)，因?yàn)?CORDIC 是 49 年前構(gòu)思出來(lái)的，當(dāng)時(shí)乘法器硬件的成本高得令人望而卻步。（DSP 通常配備乘法器。）但是當(dāng)您將兩者混合時(shí)會(huì)發(fā)生什么情況？當(dāng)在 DSP 處理器上實(shí)現(xiàn) CORDIC 算法時(shí)，乘法器能否提高 CORDIC 的性能，還是可以閑置？

我們將通過(guò)提出一種將 CORDIC 算法映射到 DSP 硬件的新穎方法來(lái)積極回答這個(gè)問(wèn)題。這種新方法使用 DSP 的 MAC（乘法/累加）單元并消除了條件，從而保留了機(jī)器流水線。

CORDIC 是 COordinate Rotation DIgital Computer 的首字母縮寫(xiě)詞，是一類在平面中旋轉(zhuǎn)矢量的移位相加算法。CORDIC 已成為內(nèi)存和 CPU 受限嵌入式系統(tǒng)中的常用方法，因?yàn)樗怯?jì)算每個(gè)科學(xué)計(jì)算器中的雙曲函數(shù)和三角函數(shù)的簡(jiǎn)單而有效的方法。

大多數(shù)情況下，當(dāng)沒(méi)有可用的硬件乘法器時(shí)（例如在微控制器和 FPGA 中），會(huì)使用該算法，因?yàn)樗璧牟僮魇羌臃?、減法、位移位和查表。

CORDIC 由于其簡(jiǎn)單性和相對(duì)快速收斂的特性而被廣泛使用。它有很多應(yīng)用，包括計(jì)算三角函數(shù)和將笛卡爾坐標(biāo)轉(zhuǎn)換為極坐標(biāo)（反之亦然）。

基本上，CORDIC 算法會(huì)選擇特殊的旋轉(zhuǎn)角度，這樣它就可以通過(guò)簡(jiǎn)單的移位和加法來(lái)執(zhí)行旋轉(zhuǎn)操作，而不是一般情況下所需的乘法函數(shù)。因此，設(shè)計(jì)團(tuán)隊(duì)可以使用 CORDIC 算法而不是硬件乘法器，后者需要更多的門(mén)數(shù)并且構(gòu)建成本更高。

在我們?cè)敿?xì)了解如何將 CORDIC 算法映射到 DSP 引擎之前，我們將簡(jiǎn)要回顧一下 CORDIC 算法，該算法根據(jù)笛卡爾坐標(biāo)計(jì)算矢量的大小和角度。然后我們將描述該算法在 DSP 處理器上的實(shí)現(xiàn)，它僅使用加法和移位運(yùn)算。

不過(guò)，首先讓我們回顧一下實(shí)現(xiàn) CORDIC 的傳統(tǒng)方法。

令v為具有笛卡爾坐標(biāo) ( x, y ) 的向量。為了簡(jiǎn)化描述，我們只考慮單位圓的右半平面，換句話說(shuō)，我們假設(shè) 1> x >0, 1> y。

目標(biāo)是找到幅度

如果我們能以某種方式將向量v = ( x , y ) 旋轉(zhuǎn)到v e = ( x e , y e ) 使得y e = 0，則大小r 將是x坐標(biāo)x e ，角度 φ 將是旋轉(zhuǎn)后的坐標(biāo)角度。這種旋轉(zhuǎn)實(shí)際上是通過(guò)多次連續(xù)旋轉(zhuǎn)（稱為子旋轉(zhuǎn)）來(lái)實(shí)現(xiàn)的。對(duì)于每個(gè)子旋轉(zhuǎn)，正確選擇旋轉(zhuǎn)角度，以便：

? 計(jì)算可以僅通過(guò)加法和移位運(yùn)算來(lái)完成（避免使用乘法）。

? 子旋轉(zhuǎn)集將向量v驅(qū)動(dòng) 到x軸，換句話說(shuō)，使坐標(biāo)y 等于0；如果當(dāng)前旋轉(zhuǎn)是前一個(gè)旋轉(zhuǎn)的一半，則可以保證這一點(diǎn)。

在數(shù)學(xué)上，CORDIC 算法可以描述如下：

初讓：

x 0 = x

y 0 = y

φ 0 =0

個(gè)操作會(huì)將 v 0 = ( x 0 , y 0 ) 旋轉(zhuǎn) α 0 =45° 以獲得 v 1 = ( x 1 , y 1 )。

x 1 = x 0 cos(α 0 ) – d 0 y 0 sin(α 0 ) (1.3)

y 1 = y 0 cos(α 0 ) + d 0 x 0 sin(α 0 ) (1.4)

φ 1 = φ 0 – d 0 α 0         (1.5)

其中d 0 是旋轉(zhuǎn)方向：

d 0 =1 如果y 0 <0 (1.6)

d 0 =-1 如果y 0 ≥0 (1.7)

等式 1.3 和 1.4 與以下相同：

x 1 = cos(α 0 )[ x 0 – d 0 y 0 tan(α 0 )] (1.8)

y 1 = cos(α 0 )[ y 0 + d 0 x 0 tan(α 0 )] (1.9)

一般來(lái)說(shuō)，第i次旋轉(zhuǎn)是：

x i +1 = cos(α i )[ x i – d i y i tan(α i ) (1.10)

y i +1 = cos(α i )[ y i + d i x i tan(α i )] (1.11)

φ i +1 = φ i – d i α i                          (1.12)

其中d i 是旋轉(zhuǎn)方向：

d i =1 如果y i <0（向上旋轉(zhuǎn)） (1.13)

d i =-1 如果y i ≥0（向下旋轉(zhuǎn)） (1.14)

因?yàn)槲?0,1,…

如果選擇 a i 使得 tan(a i )= 2 -i ，則方程 1.10 到 1.12 變?yōu)椋?/p>

x i +1 = K i [ x i – d i y i 2 -i ] (1.15)

y i +1 = K i [ y i + d i x i 2 -i ] (1.16)

φ i +1 = φ i – d i α i                           (1.17)

在哪里：

K i = cos(arctan(2 -i )) (1.18)

α i = arctan(2 -i ) (1.19)

由于稍后可以去除常數(shù)K i 的影響 （參見(jiàn)公式 1.23），公式 1.15 到 1.17 中的 CORDIC 算法可以實(shí)現(xiàn)為：

xi +1 = xi – d i y i 2 -i         ( 1.20 ) 

y i +1 = y i + d i x i 2 -i         (1.21)

φ i +1 = φ i – d i α i         (1.22)

其中d i 和 α i 在方程 1.13、1.14 和 1.19 中定義。

假設(shè)經(jīng)過(guò)N 次旋轉(zhuǎn)后，達(dá)到了所需的精度，則 可以通過(guò)以下方式近似找到 大小r和角度 φ：

其中K = K N -1 ? …? K 0 = cos(arctan(2 -( N -1) ))?... ?cos(arctan(2 -0 ))，可以地預(yù)先計(jì)算。

等式 1.20 到 1.24 中 CORDIC 的典型偽代碼是：

如果 ( y < 0) (1.25)

    x i +1 = x i – y i ' (1.26)

    y i +1 = y i + x i ' (1.27)

    φ i +1 = φ i – α i         (1.28)

如果 ( y i ≥ 0) (1.29)

    x i +1 = x i + y i ' (1.30)

    y i +1 = y i – x i ' (1.31)

    φ i +1 = φ i + α i         (1.32)

在哪里：

x i '= x i 2 -i = x i >> i         (1.33)

y i '= y i 2 -i = y i >> i         (1.34)

我=0,1,…

符號(hào)“ z >> i ”表示z中的位 將向下移動(dòng)i 位（本文檔中的移位始終是算術(shù)移位，而不是邏輯移位）。

圖 1 顯示了 CORDIC 算法的圖示。公式 1.25 到 1.32 中的偽代碼很簡(jiǎn)單，只需要加法和移位運(yùn)算。由于不需要乘法函數(shù)，硬件實(shí)現(xiàn)也很簡(jiǎn)單，因此CORDIC算法在ASIC（專用集成電路）和FPGA（現(xiàn)場(chǎng)可編程門(mén)陣列）中得到廣泛應(yīng)用。

查看全尺寸圖像

現(xiàn)代架構(gòu)的新 CORDIC 實(shí)現(xiàn) 
人們普遍認(rèn)為 DSP 處理器無(wú)法提高 CORDIC 算法的性能。乍一看，這似乎是合理的，因?yàn)樵诖蠖鄶?shù)實(shí)現(xiàn)中 CORDIC 的主要優(yōu)勢(shì)是它避免了乘法函數(shù)。但是，如果有一個(gè)乘法器，是否可以提高 CORDIC 算法的性能呢？我們建議重新制定 CORDIC，以利用 DSP 的硬件架構(gòu)。

在 DSP 架構(gòu)上實(shí)現(xiàn) CORDIC 時(shí)還有另一個(gè)重要的考慮因素——即流水線。為了提高性能，現(xiàn)代處理器通常采用多達(dá) 10 個(gè)階段的流水線。這種流水線設(shè)計(jì)允許處理器以時(shí)間片的方式執(zhí)行任務(wù)。 只要代碼不會(huì)用分支破壞指令流，流水線就是一種有效的方法。傳統(tǒng)的 CORDIC 算法需要條件執(zhí)行（參見(jiàn)方程 1.25 到 1.32 中的偽代碼），這通常會(huì)破壞流水線并導(dǎo)致停頓。因此，CORDIC 算法的性能在現(xiàn)代流水線架構(gòu)中可能很慢。

我們的新方法主要通過(guò)在 DSP 處理器中使用乘法單元來(lái)解決這個(gè)困難；它還消除了條件執(zhí)行的需要。我們首先重新制定算法，使其更適合使用乘法器。

x i +1、y i +1和 φ i +1的迭代公式 （參見(jiàn)方程 1.25 至 1.32）可寫(xiě)為：

x i +1 = φ i ( x i – y i ')+(1- f i ) ( x i + y i ') (2.1)

y i +1 = fi ( y i + x i ')+(1- f i ) ( y i – x i ') ( 2.2) 

f i +1 = φ i (φ i – a i )+(1- f i ) (φ i + α i ) (2.3)

在哪里：

f i =1 如果y i <0 (2.4)

f i =0 如果y i ≥0 (2.5)

x i '= x i 2 -i = x i >>i (2.6)

y i '= y i 2 -i = y i >>i (2.7)

公式 2.1 中的迭代可寫(xiě)為：

x i +1 = f i (– 2 y i ')+ ( x i + y i ')

  = 2[- f i y i '+ x i /2+ y i '/2]

  = 2[(- f i + 1 / 2) y i '+ x i /2] (2.8)

  = 2[(- f i + 1 / 2)' y i + x i /2]

在哪里：

(- f i + 1 / 2)' = (- f i + 1 / 2)2 -i = (- f i + 1 / 2)>> i         (2.9)

同樣，方程 2.2 和 2.3 中的迭代可寫(xiě)為：

y i +1 = 2[-(- f i + 1 / 2)' x i + y i /2] (2.10)

φ i +1 = 2 i [(- f i + 1 / 2)α i +φ i /2] (2.11)

綜合以上，我們有實(shí)現(xiàn)的算法：

x i +1 = 2[(- f i + 1 / 2)' y i + x i /2] (2.12)

y i +1 = 2[-(- f i + 1 / 2)' x i + y i /2] (2.13)

φ i +1 = 2 i [(- f i + 1 / 2)α i +φ i /2] (2.14)

在哪里：

f i =1 如果y i <0 (2.15)

f i =0 如果y i ≥ 0 (2.16)

(- f i + 1 / 2)' = (- f i + 1 / 2)2 – i = (- f i + 1 / 2)>>i (2.17)

公式 2.12 到 2.17 相對(duì)于公式 1.25 到 1.32 的優(yōu)點(diǎn)如下：

1. 方程 2.12 到 2.17 的執(zhí)行是無(wú)條件的；因此，它解決了管道破裂的困難，這是在執(zhí)行方程式 1.25 到 1.32 時(shí)的情況。

2. 方程式 2.12 到 2.17 中的移位操作只會(huì)進(jìn)行（以獲得修改后的標(biāo)志 (- f i + 1 / 2)' ），而在方程式 1.25 到 1.32 中，需要兩次移位操作（以獲得x i '和y i ')，因此它節(jié)省了操作。

3. 標(biāo)志已被選擇為具有兩個(gè)可能的值，1 / 2 或 –1 / 2。公式 1.15 小數(shù)格式中的這些值分別以十六進(jìn)制表示法表示為 0x4000 和 0xC000。由于特定值的選擇，標(biāo)志常量在向下移動(dòng)時(shí)不會(huì)丟失精度。

4. 新的CORDIC公式在迭代過(guò)程中不會(huì)下移x i 和y i坐標(biāo)值。 因此，原始 ( x , y ) 坐標(biāo)值的精度不會(huì)丟失。

5. 標(biāo)志 (- f i +1 / 2)' 與x i 或y i 坐標(biāo)值的乘積存儲(chǔ)在 40 位累加器中。參見(jiàn)公式 2.8 和 2.10。

6. 作為改進(jìn) 3、4 和 5 的結(jié)果，新的 CORDIC 公式實(shí)現(xiàn)了約 0.5 位的更高精度。

公式 2.12 到 2.17 中的公式特別適合在流水線 DSP 架構(gòu)上實(shí)現(xiàn)。當(dāng)在 Analog Devices 的 Blackfin BF533 DSP 處理器上實(shí)現(xiàn)時(shí)，每次迭代需要四個(gè)周期，而公式 1.25 到 1.32 中的傳統(tǒng)實(shí)現(xiàn)每次迭代需要七個(gè)周期。例如，在軟件無(wú)線電應(yīng)用中，我們需要為 240 kHz 的兩個(gè)信道實(shí)現(xiàn) CORDIC 算法。迭代次數(shù)（子旋轉(zhuǎn)）為 13。我們的新方法將消耗 2×240,000x13x4 = 25 mips（每秒百萬(wàn)條指令），而 2×240,000x13x7 = 44 mips。

這表示在 mips 方面節(jié)省了 43%。此外，對(duì)于相同的迭代次數(shù)，方程式 2.12 到 2.17 中新方法的結(jié)果平均比方程式 1.25 到 1.32 中的傳統(tǒng)方法的精度高 0.5 位。

CORDIC 的 C 和匯編代碼 
在本節(jié)中，我們提供三個(gè)代碼示例：

? 清單 1： 實(shí)現(xiàn)原始 CORDIC 的 C 代碼。

? 清單 2：實(shí)現(xiàn)重新編寫(xiě)的 CORDIC 的 Blackfin 匯編代碼。

? 清單 3： 實(shí)現(xiàn)原始 CORDIC 的 Blackfin 匯編代碼。

可以使用 ADI 的 VisualDSP++ 工具編譯和執(zhí)行清單 1中的代碼和清單 2 中的完整代碼。請(qǐng)注意，清單 2中的代碼 是一個(gè)摘錄——完整的代碼代碼假定 | x |, | y |<1 格式為 1.15；換句話說(shuō)，x , y在[0x8000, 0x7fff] 范圍內(nèi)。輸出相位為1.31格式的32位；換句話說(shuō)，-p 由0x80000000 表示 ，p 由0x7fffffff 表示。匯編代碼可能有一些特殊要求，可以在注釋中看到。

清單 3中的代碼 只是展示原始 CORDIC 如何在 ADI 匯編上實(shí)現(xiàn)的一部分。在清單 3中，我們僅顯示了迭代的代碼（總共七行代碼，花費(fèi)了七個(gè)周期）。ITER_NUM=i 是一個(gè)變量i =0,…,14 是迭代次數(shù)。它應(yīng)該在一個(gè)寄存器中，可以從內(nèi)存中加載。為了清楚起見(jiàn)，我們將其保留原樣。寄存器 r2 = φ i +1 , i =0,1,…,14 初始時(shí) r2=φ 0 =0（見(jiàn) 1.32）。除了以下實(shí)現(xiàn)的緩慢性能外，由于行r1 = r0>>> ITER_NUM (v) ，它的精度較低，它移動(dòng)了x i y i 向下坐標(biāo)，失去精度。數(shù)字信號(hào)處理器 (DSP) 為需要快速模擬到數(shù)字到模擬轉(zhuǎn)換的應(yīng)用處理數(shù)字，例如軟件無(wú)線電和雷達(dá)。如果您沒(méi)有使用 DSP，您可以使用 CORDIC 算法在您的 IC 上執(zhí)行類似的計(jì)算。CORDIC 算法的優(yōu)勢(shì)在于它能夠在不使用乘法器的情況下求解矢量旋轉(zhuǎn)。

盡管 CORDIC 的屬性有據(jù)可查，但您不會(huì)經(jīng)常發(fā)現(xiàn)它在 DSP 上實(shí)現(xiàn)，因?yàn)?CORDIC 是 49 年前構(gòu)思出來(lái)的，當(dāng)時(shí)乘法器硬件的成本高得令人望而卻步。（DSP 通常配備乘法器。）但是當(dāng)您將兩者混合時(shí)會(huì)發(fā)生什么情況？當(dāng)在 DSP 處理器上實(shí)現(xiàn) CORDIC 算法時(shí)，乘法器能否提高 CORDIC 的性能，還是可以閑置？

我們將通過(guò)提出一種將 CORDIC 算法映射到 DSP 硬件的新穎方法來(lái)積極回答這個(gè)問(wèn)題。這種新方法使用 DSP 的 MAC（乘法/累加）單元并消除了條件，從而保留了機(jī)器流水線。

CORDIC 是 COordinate Rotation DIgital Computer 的首字母縮寫(xiě)詞，是一類在平面中旋轉(zhuǎn)矢量的移位相加算法。CORDIC 已成為內(nèi)存和 CPU 受限嵌入式系統(tǒng)中的常用方法，因?yàn)樗怯?jì)算每個(gè)科學(xué)計(jì)算器中的雙曲函數(shù)和三角函數(shù)的簡(jiǎn)單而有效的方法。

大多數(shù)情況下，當(dāng)沒(méi)有可用的硬件乘法器時(shí)（例如在微控制器和 FPGA 中），會(huì)使用該算法，因?yàn)樗璧牟僮魇羌臃?、減法、位移位和查表。

CORDIC 由于其簡(jiǎn)單性和相對(duì)快速收斂的特性而被廣泛使用。它有很多應(yīng)用，包括計(jì)算三角函數(shù)和將笛卡爾坐標(biāo)轉(zhuǎn)換為極坐標(biāo)（反之亦然）。

基本上，CORDIC 算法會(huì)選擇特殊的旋轉(zhuǎn)角度，這樣它就可以通過(guò)簡(jiǎn)單的移位和加法來(lái)執(zhí)行旋轉(zhuǎn)操作，而不是一般情況下所需的乘法函數(shù)。因此，設(shè)計(jì)團(tuán)隊(duì)可以使用 CORDIC 算法而不是硬件乘法器，后者需要更多的門(mén)數(shù)并且構(gòu)建成本更高。

在我們?cè)敿?xì)了解如何將 CORDIC 算法映射到 DSP 引擎之前，我們將簡(jiǎn)要回顧一下 CORDIC 算法，該算法根據(jù)笛卡爾坐標(biāo)計(jì)算矢量的大小和角度。然后我們將描述該算法在 DSP 處理器上的實(shí)現(xiàn)，它僅使用加法和移位運(yùn)算。

不過(guò)，首先讓我們回顧一下實(shí)現(xiàn) CORDIC 的傳統(tǒng)方法。

令v為具有笛卡爾坐標(biāo) ( x, y ) 的向量。為了簡(jiǎn)化描述，我們只考慮單位圓的右半平面，換句話說(shuō)，我們假設(shè) 1> x >0, 1> y。

目標(biāo)是找到幅度

如果我們能以某種方式將向量v = ( x , y ) 旋轉(zhuǎn)到v e = ( x e , y e ) 使得y e = 0，則大小r 將是x坐標(biāo)x e ，角度 φ 將是旋轉(zhuǎn)后的坐標(biāo)角度。這種旋轉(zhuǎn)實(shí)際上是通過(guò)多次連續(xù)旋轉(zhuǎn)（稱為子旋轉(zhuǎn)）來(lái)實(shí)現(xiàn)的。對(duì)于每個(gè)子旋轉(zhuǎn)，正確選擇旋轉(zhuǎn)角度，以便：

? 計(jì)算可以僅通過(guò)加法和移位運(yùn)算來(lái)完成（避免使用乘法）。

? 子旋轉(zhuǎn)集將向量v驅(qū)動(dòng) 到x軸，換句話說(shuō)，使坐標(biāo)y 等于0；如果當(dāng)前旋轉(zhuǎn)是前一個(gè)旋轉(zhuǎn)的一半，則可以保證這一點(diǎn)。

在數(shù)學(xué)上，CORDIC 算法可以描述如下：

初讓：

x 0 = x

y 0 = y

φ 0 =0

個(gè)操作會(huì)將 v 0 = ( x 0 , y 0 ) 旋轉(zhuǎn) α 0 =45° 以獲得 v 1 = ( x 1 , y 1 )。

x 1 = x 0 cos(α 0 ) – d 0 y 0 sin(α 0 ) (1.3)

y 1 = y 0 cos(α 0 ) + d 0 x 0 sin(α 0 ) (1.4)

φ 1 = φ 0 – d 0 α 0         (1.5)

其中d 0 是旋轉(zhuǎn)方向：

d 0 =1 如果y 0 <0 (1.6)

d 0 =-1 如果y 0 ≥0 (1.7)

等式 1.3 和 1.4 與以下相同：

x 1 = cos(α 0 )[ x 0 – d 0 y 0 tan(α 0 )] (1.8)

y 1 = cos(α 0 )[ y 0 + d 0 x 0 tan(α 0 )] (1.9)

一般來(lái)說(shuō)，第i次旋轉(zhuǎn)是：

x i +1 = cos(α i )[ x i – d i y i tan(α i ) (1.10)

y i +1 = cos(α i )[ y i + d i x i tan(α i )] (1.11)

φ i +1 = φ i – d i α i                          (1.12)

其中d i 是旋轉(zhuǎn)方向：

d i =1 如果y i <0（向上旋轉(zhuǎn)） (1.13)

d i =-1 如果y i ≥0（向下旋轉(zhuǎn)） (1.14)

因?yàn)槲?0,1,…

如果選擇 a i 使得 tan(a i )= 2 -i ，則方程 1.10 到 1.12 變?yōu)椋?/p>

x i +1 = K i [ x i – d i y i 2 -i ] (1.15)

y i +1 = K i [ y i + d i x i 2 -i ] (1.16)

φ i +1 = φ i – d i α i                           (1.17)

在哪里：

K i = cos(arctan(2 -i )) (1.18)

α i = arctan(2 -i ) (1.19)

由于稍后可以去除常數(shù)K i 的影響 （參見(jiàn)公式 1.23），公式 1.15 到 1.17 中的 CORDIC 算法可以實(shí)現(xiàn)為：

xi +1 = xi – d i y i 2 -i         ( 1.20 ) 

y i +1 = y i + d i x i 2 -i         (1.21)

φ i +1 = φ i – d i α i         (1.22)

其中d i 和 α i 在方程 1.13、1.14 和 1.19 中定義。

假設(shè)經(jīng)過(guò)N 次旋轉(zhuǎn)后，達(dá)到了所需的精度，則 可以通過(guò)以下方式近似找到 大小r和角度 φ：

其中K = K N -1 ? …? K 0 = cos(arctan(2 -( N -1) ))?... ?cos(arctan(2 -0 ))，可以地預(yù)先計(jì)算。

等式 1.20 到 1.24 中 CORDIC 的典型偽代碼是：

如果 ( y < 0) (1.25)

    x i +1 = x i – y i ' (1.26)

    y i +1 = y i + x i ' (1.27)

    φ i +1 = φ i – α i         (1.28)

如果 ( y i ≥ 0) (1.29)

    x i +1 = x i + y i ' (1.30)

    y i +1 = y i – x i ' (1.31)

    φ i +1 = φ i + α i         (1.32)

在哪里：

x i '= x i 2 -i = x i >> i         (1.33)

y i '= y i 2 -i = y i >> i         (1.34)

我=0,1,…

符號(hào)“ z >> i ”表示z中的位 將向下移動(dòng)i 位（本文檔中的移位始終是算術(shù)移位，而不是邏輯移位）。

圖 1 顯示了 CORDIC 算法的圖示。公式 1.25 到 1.32 中的偽代碼很簡(jiǎn)單，只需要加法和移位運(yùn)算。由于不需要乘法函數(shù)，硬件實(shí)現(xiàn)也很簡(jiǎn)單，因此CORDIC算法在ASIC（專用集成電路）和FPGA（現(xiàn)場(chǎng)可編程門(mén)陣列）中得到廣泛應(yīng)用。

現(xiàn)代架構(gòu)的新 CORDIC 實(shí)現(xiàn) 
人們普遍認(rèn)為 DSP 處理器無(wú)法提高 CORDIC 算法的性能。乍一看，這似乎是合理的，因?yàn)樵诖蠖鄶?shù)實(shí)現(xiàn)中 CORDIC 的主要優(yōu)勢(shì)是它避免了乘法函數(shù)。但是，如果有一個(gè)乘法器，是否可以提高 CORDIC 算法的性能呢？我們建議重新制定 CORDIC，以利用 DSP 的硬件架構(gòu)。

在 DSP 架構(gòu)上實(shí)現(xiàn) CORDIC 時(shí)還有另一個(gè)重要的考慮因素——即流水線。為了提高性能，現(xiàn)代處理器通常采用多達(dá) 10 個(gè)階段的流水線。這種流水線設(shè)計(jì)允許處理器以時(shí)間片的方式執(zhí)行任務(wù)。 只要代碼不會(huì)用分支破壞指令流，流水線就是一種有效的方法。傳統(tǒng)的 CORDIC 算法需要條件執(zhí)行（參見(jiàn)方程 1.25 到 1.32 中的偽代碼），這通常會(huì)破壞流水線并導(dǎo)致停頓。因此，CORDIC 算法的性能在現(xiàn)代流水線架構(gòu)中可能很慢。

我們的新方法主要通過(guò)在 DSP 處理器中使用乘法單元來(lái)解決這個(gè)困難；它還消除了條件執(zhí)行的需要。我們首先重新制定算法，使其更適合使用乘法器。

x i +1、y i +1和 φ i +1的迭代公式 （參見(jiàn)方程 1.25 至 1.32）可寫(xiě)為：

x i +1 = φ i ( x i – y i ')+(1- f i ) ( x i + y i ') (2.1)

y i +1 = fi ( y i + x i ')+(1- f i ) ( y i – x i ') ( 2.2) 

f i +1 = φ i (φ i – a i )+(1- f i ) (φ i + α i ) (2.3)

在哪里：

f i =1 如果y i <0 (2.4)

f i =0 如果y i ≥0 (2.5)

x i '= x i 2 -i = x i >>i (2.6)

y i '= y i 2 -i = y i >>i (2.7)

公式 2.1 中的迭代可寫(xiě)為：

x i +1 = f i (– 2 y i ')+ ( x i + y i ')

  = 2[- f i y i '+ x i /2+ y i '/2]

  = 2[(- f i + 1 / 2) y i '+ x i /2] (2.8)

  = 2[(- f i + 1 / 2)' y i + x i /2]

在哪里：

(- f i + 1 / 2)' = (- f i + 1 / 2)2 -i = (- f i + 1 / 2)>> i         (2.9)

同樣，方程 2.2 和 2.3 中的迭代可寫(xiě)為：

y i +1 = 2[-(- f i + 1 / 2)' x i + y i /2] (2.10)

φ i +1 = 2 i [(- f i + 1 / 2)α i +φ i /2] (2.11)

綜合以上，我們有實(shí)現(xiàn)的算法：

x i +1 = 2[(- f i + 1 / 2)' y i + x i /2] (2.12)

y i +1 = 2[-(- f i + 1 / 2)' x i + y i /2] (2.13)

φ i +1 = 2 i [(- f i + 1 / 2)α i +φ i /2] (2.14)

在哪里：

f i =1 如果y i <0 (2.15)

f i =0 如果y i ≥ 0 (2.16)

(- f i + 1 / 2)' = (- f i + 1 / 2)2 – i = (- f i + 1 / 2)>>i (2.17)

公式 2.12 到 2.17 相對(duì)于公式 1.25 到 1.32 的優(yōu)點(diǎn)如下：

1. 方程 2.12 到 2.17 的執(zhí)行是無(wú)條件的；因此，它解決了管道破裂的困難，這是在執(zhí)行方程式 1.25 到 1.32 時(shí)的情況。

2. 方程式 2.12 到 2.17 中的移位操作只會(huì)進(jìn)行（以獲得修改后的標(biāo)志 (- f i + 1 / 2)' ），而在方程式 1.25 到 1.32 中，需要兩次移位操作（以獲得x i '和y i ')，因此它節(jié)省了操作。

3. 標(biāo)志已被選擇為具有兩個(gè)可能的值，1 / 2 或 –1 / 2。公式 1.15 小數(shù)格式中的這些值分別以十六進(jìn)制表示法表示為 0x4000 和 0xC000。由于特定值的選擇，標(biāo)志常量在向下移動(dòng)時(shí)不會(huì)丟失精度。

4. 新的CORDIC公式在迭代過(guò)程中不會(huì)下移x i 和y i坐標(biāo)值。 因此，原始 ( x , y ) 坐標(biāo)值的精度不會(huì)丟失。

5. 標(biāo)志 (- f i +1 / 2)' 與x i 或y i 坐標(biāo)值的乘積存儲(chǔ)在 40 位累加器中。參見(jiàn)公式 2.8 和 2.10。

6. 作為改進(jìn) 3、4 和 5 的結(jié)果，新的 CORDIC 公式實(shí)現(xiàn)了約 0.5 位的更高精度。

公式 2.12 到 2.17 中的公式特別適合在流水線 DSP 架構(gòu)上實(shí)現(xiàn)。當(dāng)在 Analog Devices 的 Blackfin BF533 DSP 處理器上實(shí)現(xiàn)時(shí)，每次迭代需要四個(gè)周期，而公式 1.25 到 1.32 中的傳統(tǒng)實(shí)現(xiàn)每次迭代需要七個(gè)周期。例如，在軟件無(wú)線電應(yīng)用中，我們需要為 240 kHz 的兩個(gè)信道實(shí)現(xiàn) CORDIC 算法。迭代次數(shù)（子旋轉(zhuǎn)）為 13。我們的新方法將消耗 2×240,000x13x4 = 25 mips（每秒百萬(wàn)條指令），而 2×240,000x13x7 = 44 mips。

這表示在 mips 方面節(jié)省了 43%。此外，對(duì)于相同的迭代次數(shù)，方程式 2.12 到 2.17 中新方法的結(jié)果平均比方程式 1.25 到 1.32 中的傳統(tǒng)方法的精度高 0.5 位。

CORDIC 的 C 和匯編代碼 
在本節(jié)中，我們提供三個(gè)代碼示例：

? 清單 1： 實(shí)現(xiàn)原始 CORDIC 的 C 代碼。

? 清單 2：實(shí)現(xiàn)重新編寫(xiě)的 CORDIC 的 Blackfin 匯編代碼。

? 清單 3： 實(shí)現(xiàn)原始 CORDIC 的 Blackfin 匯編代碼。

可以使用 ADI 的 VisualDSP++ 工具編譯和執(zhí)行清單 1中的代碼和清單 2 中的完整代碼。請(qǐng)注意，清單 2中的代碼 是一個(gè)摘錄——完整的代碼可以從www.embedded.com/code/2008code.htm 獲得。代碼假定 | x |, | y |<1 格式為 1.15；換句話說(shuō)，x , y在[0x8000, 0x7fff] 范圍內(nèi)。輸出相位為1.31格式的32位；換句話說(shuō)，-p 由0x80000000 表示 ，p 由0x7fffffff 表示。匯編代碼可能有一些特殊要求，可以在注釋中看到。

清單 3中的代碼 只是展示原始 CORDIC 如何在 ADI 匯編上實(shí)現(xiàn)的一部分。在清單 3中，我們僅顯示了迭代的代碼（總共七行代碼，花費(fèi)了七個(gè)周期）。ITER_NUM=i 是一個(gè)變量i =0,…,14 是迭代次數(shù)。它應(yīng)該在一個(gè)寄存器中，可以從內(nèi)存中加載。為了清楚起見(jiàn)，我們將其保留原樣。寄存器 r2 = φ i +1 , i =0,1,…,14 初始時(shí) r2=φ 0 =0（見(jiàn) 1.32）。除了以下實(shí)現(xiàn)的緩慢性能外，由于行r1 = r0>>> ITER_NUM (v) ，它的精度較低，它移動(dòng)了x i y i 向下坐標(biāo)，失去精度。