三維空間坐标的旋轉算法詳解_CORDIC算法詳解(一)CORDIC 算法之圓周系統之旋轉模式...

CORDIC算法詳解(一)- CORDIC 算法之圓周系統之旋轉模式( Rotation Mode )

文章目錄

• CORDIC算法詳解(一)- CORDIC 算法之圓周系統之旋轉模式( Rotation Mode )
• 1 CORDIC 算法之圓周系統及其數學應用
  • 1.1 圓周系統之旋轉模式( Rotation Mode )
  • 1.2 思考
  • 1.3 CORDIC算法應用
    • 1.3.1 目标旋轉角度的正、 餘弦函數值
    • 1.3.1 極坐标系向直角坐标系的轉換
  • 1.4 舉例
• CORDIC 算法之圓周系統及其數學應用結束

  網上有很多類似的介紹，但是本文會結合執行個體進行介紹，盡量以最簡單的語言進行解析。

  CORDIC ( Coordinate Rotation Digital Computer ) 是坐标旋轉數字計算機算法的簡稱，

由 Vloder• 于 1959 年在設計美國航空導航控制系統的過程中首先提出[1], 主要用于解決導航系統中三角函數、 反三角函數和開方等運算的實時計算問題。 1971 年， Walther 将圓周系統、 線性系統和雙曲系統統一到一個 CORDIC 疊代方程裡 ， 進而提出了一種統一的CORDIC 算法形式[2]。

  CORDIC 算法應用廣泛， 如離散傅裡葉變換 、 離散餘弦變換、 離散 Hartley 變換、Chirp-Z 變換、 各種濾波以及矩陣的奇異值分解中都可應用 CORDIC 算法。 從廣義上講，CORDIC 算法提供了一種數學計算的逼近方法。 由于它最終可分解為一系列的加減和移位操作， 故非常适合硬體實作。 例如， 在工程領域可采用 CORDIC 算法實作直接數字頻率合成器。 本節在闡述 CORDIC 算法三種旋轉模式的基礎上， 介紹了利用 CORDIC 算法計算三角函數、 反三角函數和複數求模等相關理論。 以此為依據， 闡述了基于 FPGA 的 CORDIC 算法的設計與實作及其工程應用。

整個系列分别從圓周系統、 線性系統和雙曲系統及硬體實作進行分析，如下：

CORDIC算法詳解(一)- CORDIC 算法之圓周系統之旋轉模式( Rotation Mode )CORDIC算法詳解(二)- CORDIC 算法之圓周系統之向量模式(Vectoring Mode)CORDIC算法詳解(三)- CORDIC 算法之線性系統及其數學應用CORDIC算法詳解(四)- CORDIC 算法之雙曲系統及其數學應用CORDIC算法詳解(五)- 統一的 CORDIC 算法形式CORDIC算法詳解(六)- CORDIC 算法的硬體實作

其中第五篇及第六篇後會放出相關參考資料及源碼。

1 CORDIC 算法之圓周系統及其數學應用

  在圓周系統下， CORDIC 算法解決了三角函數的計算問題，其中圓周系統又分旋轉模式和向量模式。

1.1 圓周系統之旋轉模式( Rotation Mode )

  如圖 3.69 所示， 在機關圓上， 向量 OP與X軸正半軸夾角為 α , 故P點坐标可表示為式(3.91):

  将向量 OP 逆 時 針 旋 轉θ角 至 向 量 OQ，此 時 OQ與X軸正半軸夾角為 α + θ ，故 Q 點坐标可以表示為：

  這裡定義 θ為目标旋轉角度。 根據三角函數公式可将式 (3.92) 展開為：

  将式 (3.91 ) 代入式 (3.93) 可得：

  提取 cosθ , 式 (3.94) 可重新表示為：

  從式 (3.95 ) 中可看出， cosθ隻是改變了目标向量OQ的模長。 如果去掉 cosθ , 如圖 3.70所示， 此時 OP旋轉θ角之後到達 OR， 這種旋轉稱之為僞旋轉( Pseudo Rotation) 。不難看出， OQ與OR 幅度 上 的 差 異， 且 可 證 明 向 量 OP 與 PR是正交的。 此時R點坐标可表示為：

  至此， 可通過對僞旋轉的輸出加以補償來獲得真實旋轉的結果。PS：對比可知每次旋轉的角度是正确的，但是模值增大了1/cosθ

注意：并不能通過數學方法去除cosθ，但是去除cosθ可以簡化坐标平面旋轉的計算操作。

  對于僞旋轉， 可将 θ分解為一系列的微小角度的和， 即：

  這樣， 将一次旋轉分解成為一系列的微旋轉。 由式 (3.96) 可知， 第i+1 次旋轉後的結果為:

  下一步至關重要， 正是它使得該算法非常易于硬體實作， 即令：

  這裡di∈{-1,1}， 結合式( 3.99)， 式 (3.98) 可重新改寫為：

  由式(3.100)， 不難看出， 每次微旋轉隻需要加法 、 減法和移位操作即可完成。為了确定di的值，引入一個新的變量z，定義為：

z 初 始 化 為θ，即z0=θ，根據條件，對zi執行加或者減tan-12-i操作，使得z的最終值為0 ，該條件由di決定，即：

  di為+1時表示逆時針旋轉，為-1時表示順時針旋轉 。z的疊代過程是将z收斂于零的過程，也正是将θ分解為一系列θi的過程， 故zi可認為是第i次旋轉剩餘的角度。至此 ，CORDIC 算法之圓周系統的旋轉模式疊代過程可表示為：

1.2 思考

• (1 ) 由式 (3.99) 所确定的目标旋轉角度的範圍；

• (2) 如何确定僞旋轉到真實旋轉的模長補償因子。

  (1)根據式 (3.99 ) 可确定一系列θi的值， 如表 3.17 所示， 還可确定目标旋轉角度θ的最大值 θmax 和 最 小 值 θmin , 如式( 3.104 ) 所示。

  以目标旋轉角度 55° 為例， 它可分解為

          55° = 45.0° + 26.6° -14.0°- 7.1° + 3.6° + 1.8° - 0.9°

  其疊代過程中角度的變化狀況如表 3.18 所示。 假設初始向量位于X軸 正 半 軸， 前 3 次 的 微旋轉如圖 3.71 所示。

  (2)在很多場合中需要目标旋轉角度可以覆寫[-180°，180°], 這就需要預處理。 預處理的機制如表 3.19 所示， 不難看出， 隻有當目标旋轉角度|θ|>π/2 時需要預旋轉 π/2 , 用公式表示如式 (3.105) 所示。

  據此， 旋轉過程可如圖 3.72 所示。

  由圖 3.71 可以看出， 每次微旋轉都導緻向量模長發生了變化。以Ki表示第 i次微旋轉模長補償因子， 故第 i次微旋轉真實旋轉的結果應為:

其中，由于在僞旋轉中，去掉了cosθi，是以Ki=cosθi 由式 (3.99) 可知:

  若總的旋轉次數為n， 則總的模長補償因子K可表示為:

  當n趨于無窮大時，K 逼近 0.607252935。

  這部分計算，可以由matlab進行疊代計算：

  具體如下：

  從上表也可以看出，當疊代次數為16，i=15時，cosθi的值已經非常趨近于1了，∏cosθi的值則約等于0.607253，1/∏cosθi為1.64676。是以當疊代次數等于16時，通過疊代得到的點坐标已經非常接近之前假設中的點坐标。

1.3 CORDIC算法應用

1.3.1 目标旋轉角度的正、 餘弦函數值

  經過 n(n–>∞)次微旋轉， 得到的最終結果可表示為：

  式中， 當 n 趨于無窮大時， An逼近 1.646760258。 根據式 (3.109 ) 可知， 令 x0=1/An且y0 = 0 可得目标旋轉角度的正、 餘弦函數值， 如圖 3.73 所示。 此時， 初始化 z0 即為目标旋轉角度 。 需要注意的是當目标旋轉角度|θ|>π/2 時應先預處理 。

1.3.1 極坐标系向直角坐标系的轉換

  同樣地， 由式 ( 3.109 ) 出發， 令 x0=r且y0 = 0，z0 =θ，則可以實作極坐标系向直角坐标系的轉換， 如圖 3.75 所示。 顯然， 這裡x0代表了極徑， z0 代表了極角。

1.4 舉例

  利用CORDIC算法，計算cosθ和sinθ，其中θ=π/4(疊代次數16)

  解析：

  相關參數轉換如下：

• x0=1/An=1/1.646760258=0.607253；
• y0 = 0；
• z0=π/4(由于|θ|

• 經過16次疊代計算後，得到的x16 和y16分别為cosθ和sinθ。

  相關程式如下：

  最後得到的結果：

• x16=0.707095876358217
• y16=0.707117836980767

  證明算法思路正确。

CORDIC 算法之圓周系統及其數學應用結束