CORDIC 算法的一種補碼實現結構設計?

孫學

（中國西南電子技術研究所，成都610036）

CORDIC 算法的一種補碼實現結構設計?

孫學

（中國西南電子技術研究所，成都610036）

根據CORDIC算法原理，分析了該算法角度旋轉范圍缺陷，提出360°覆蓋的角度旋轉算法結構；推導出利用補碼實現CORDIC算法的迭代運算單元結構，并根據該補碼運算原理設計了CORDIC補碼迭代運算單元和方向向量發生器的實現結構。

坐標旋轉數字計算機；方向向量；補碼電路

1 引 言

CORDIC是Coordinate Rotation Digital Computer（坐標旋轉數字計算機）的首字母縮寫，該數值逼近迭代算法由J.E.Volder于1959年提出［1］。其主要優點在于用簡單的移位和加減運算取代查三角函數表和乘法運算，實現二維矢量的旋轉運算，特別適合于大規模集成電路的實現。另外，CORDIC算法用于估算平方根、正余弦、指對數等初等函數的特點［2］，被廣泛應用于導航解算、頻偏估計、調制解調和頻率合成等矢量運算場合［3-5］。

本文第2節基于CORDIC算法原理分析了該算法實現角度旋轉存在覆蓋范圍缺陷，提出一種360°角度覆蓋的CORDIC旋轉算法結構。第3節基于該算法結構，創新性地推導出CORDIC迭代運算單元的一種補碼實現結構，是本文的描述重點。

2 CORDIC算法

2.1 CORDIC算法原理［1］

通過旋轉一系列小角度的以偏擺逼近所需的角度、開方以及反三角函數等復雜運算邏輯，復數P=

x+j y旋轉θ角度得到Q的過程就是復數P與復指數ejθ進行復乘得到Q的過程。如果旋轉角度θ可以分解成N個小角度φi之和，那么旋轉角度θ就等效于旋轉這N個小角度φi。

其角度θ分解方法為

圖1 CORDIC算法迭代結構框圖Fig.1 Circuit of original form CORDIC iteration operator

2.2 角度旋轉范圍缺陷及補償設計

由于φi=arctg 2-i在i=0，1，…，N-1時小于等于π／4且單調遞減，（N趨于無窮大）收斂，下面證明θ收斂范圍。

因此，用CORDIC算法實現數據的相位旋轉時，需要擴大CORDIC算法的角度旋轉范圍，從（-99.883°，+99.883°）擴展到［-180°，180°］，在實際工程應用中，通常把［-180°，180°］表達為［0°，360°］或［-360°，0°］的角度旋轉，設計如下。

+369.883°），覆蓋360°的角度旋轉范圍。取N=16時，則

該方法是在CORDIC移位序列前加上6個φi= arctg2-i（i=0）迭代，在270°范圍內實現旋轉步進為粗定位，在此基礎上通過不斷減小角度旋轉步進搖擺逼的精確定位。式（11）設計旋轉角度粗定位方法，導致復數P每旋轉45°后幅度放大1.414倍，使得式（5）中校正因子K放大8倍。在實現式（11）的CORDIC處理器時，為了減小旋轉過程中對復數P實部和虛部表達范圍的影響，在這6個迭代的每兩級旋轉后，實部和虛部各右移一位，縮小一倍以免數值溢出。

3 C ORDIC補碼實現結構設計

3.1 CORDIC的原碼實現原理

根據CORDIC算法迭代結構框圖，設計其原碼實現結構，如圖2所示。

圖2 CORDIC的原碼實現原理Fig.2PrincipleoforiginalformCORDIC

CORDIC算法的原碼實現結構優點在于原碼移位簡單，缺點在于補碼方式實現二進制加減法前后，都需要進行求補運算，原碼實現結構中每一級迭代運算都需要4個補碼器并導致2級求補運算時延。采用流水線結構實現式（11）的CORDIC需要88個補碼器，導致44級求補運算時延，不但會導致器件資源的大量消耗，在高實時矢量運算場合還將帶來嚴重的時延問題。為此，本文設計了一種補碼實現結構的CORDIC處理器，能夠有效解決以上技術問題。

3.2 CORDIC的補碼實現原理

補碼實現CORDIC處理器的基本思想是：原碼數據在輸入CORDIC運算器之前進行補碼運算，在CORDIC運算器的運算過程中全部采用補碼運算，CORDIC運算結果進行求補運算，輸出原碼數據，如圖3所示。

圖3 CORDIC的補碼實現原理Fig.3PrincipleofcomplementaryformCORDIC

該實現方法的關鍵在于補碼移位算法和CORDIC補碼迭代單元設計。

3.3 補碼移位器設計

假設輸入的整數X的原碼數據為

其中，BS為符號位，“1”表示負數，“0”表示正數，0≤i≤N表示數據的數值位。需要說明的是：十進制0的原碼表示為符號位BS=0，即只有正“零”，不允許負“零”的出現。

定義負整數X的反碼為

即符號位不變，數值位進行取反運算；正整數X的反碼為它的原碼本身。

定義數據的補碼為

式中，n為二進制整數數值位的位數。由定義可以推出，補碼的求補運算結果為數據的原碼。為了得到一個數的補碼表示，當然可以通過補碼的定義求得，但更簡便的辦法如下。

（1）BS=0時，正整數數據的補碼等于它的原碼本身：

（2）BS=1時，負整數數據的補碼等于它的反碼加“1”：

由于正數的補碼等于它的原碼本身，所以正數的補碼移位和它的原碼移位規律相同，真值除以2i的補碼實現和真值除以2i的原碼實現方式相同，不用討論，現在要研究的是負數的補碼實現真值除以2i運算規律。負數的原碼表示為

ˉBi-1orˉBi-2or…orˉB1orˉB0=0時，則D2+1=D5，即B′i-1or B′i-2or…or B′1or B′0=1時，補碼右移i位的結果再加上“1”才實現真值除以2i的功能。

綜上所述，補碼實現真值除以2i功能的實現主要是靠補碼右移i位來實現，其實現方法是：

（1）BS=0，則真值除以2i的補碼實現和真值除以2i的原碼實現方式相同，都是直接右移i位，高位補“0”來實現真值除以2i；

（2）BS=1，如果B′i-1or B′i-2or…or B′1or B′0=1為假，真值除以2i的補碼實現方式是右移i位，高位補“1”；如果B′i-1or B′i-2or…or B′1or B′0=1為真，真值除以2i的補碼實現方式是右移i位，高位補“1”的基礎上再加上“1”。

綜合以上兩種方法得到二進制數的真值除以2i的補碼表達式為

式（23）的實現結構如圖4所示。

圖4 補碼移位器結構設計Fig.4 Complementary form shifting

3.4 方向向量發生器設計

設旋轉因子WkN相位旋轉通過N次CORDIC迭代實現，則方向向量δi集合中的元素個數為N。實現該算法的一種運算結構是預先計算好δi后存儲在ROM中，這種方案僅適合固定角度的旋轉運算，不可能為每一種旋轉角度取值進行預先的旋轉向量計算。為此，本文提出方向向量δi實時發生器的設計方案解決了該問題。

圖5 方向向量δi發生器Fig.5 Direction vector generator

3.5 CORDIC補碼迭代單元設計

根據［x±y］補碼=［x］補碼±［y］補碼，也就是說，x±y真值的補碼等于［x］補碼和［y］補碼二進制加減法的運算結果。結合圖3的CORDIC補碼實現原理，使用補碼加減法器實現CORDIC迭代運算過程中的加減法，設計式（4）的補碼迭代運算單元。

其中，當δi=+1時，（δi）表示減法運算；當δi=-1時，（δi）表示加法運算。代入式（23），則：

因此，設計CORDIC補碼迭代運算單元的實現結構如圖6所示。

圖6 CORDIC補碼運算單元實現結構Fig.6 CORDIC iteration operator based on complementary form shifting

4 小 結

CORDIC作為一種計算向量旋轉的迭代算法，算法結構簡單，易于并行化處理和VLSI實現，因而在實時信號處理方面有廣泛的應用前景。本文提出一種補碼實現CORDIC的流水線電路結構，與其源碼實現結構比較，省去每級迭代運算單元的2次求補運算過程，運算時延減少了一半，有效緩解了CORDIC算法固有收斂速度與高實時矢量運算場合低時延要求的矛盾。該設計可以作為CORDIC算法實現的一種技術參考。

［1］Volder J E.The CORDIC Trigonometric Computing Technique［J］.IRE Transactions on Electronic Computers，1959，8（3）：330-334.

［2］Walther JS.A Unified Algorithm for Elementary Functions［C］／／Proceedings of American Federation of Information Processing Societies Spring Joint Computer Conference.New York：ACM，1971：379-385.

［3］Stephan W Mondwurf.Benefits of the CORDIC Algorithm in a Versatile Cofdm Modulator／Demodulator Design［C］／／Proceedingsof the Fourth IEEE International Caracas Conference on Devices，Circuits and Systems.Aruba：IEEE，2002：117-119.

［4］Despain A M.Fourier Transform Computers Using CORDIC Iterations［J］.IEEE Transactions on Computers，1993，23（10）：993-1001.

［5］Hu Y H.The quantization effects of the CORDIC algorithm［J］.IEEE Transactions on Signal Processing，1992，40（4）：705-707.

Circuit Design of Com plementary Form CORDIC Algorithm

SUN Xue
（Southwest China Institute of Electronic Technology，Chengdu 610036，China）

This paper analyses the limitation of angle rotation range in CORDIC（Coordinate Rotation Digital Computer）algorithm according to its principle，and proposes an angle rotation structure covering 360 degree，and designs the pipeline circuit architecture of direction vector generator.The mathematical deduction of CORDIC operator is given based on complementary form shifting and the circuit design of CORDIC iterations.

CORDIC；direction vector；complementary circuit

the M.S.degree from Chongqing University in 2004.He is now an engineer.His research concerns switch fabric，distributed computing and array computing.

1001-893X（2011）08-0085-05

2011-03-01；

2011-06-10

TN919.3；TP301

A

10.3969／j.issn.1001-893x.2011.08.018

孫學（1978—），男，重慶合川人，2004年于重慶大學獲碩士學位，現為工程師，主要研究方向為交換式總線、分布式計算和陣列計算技術。

Email：sun8xue＠163.com

SUN Xue was born in Hechuan，Chongqing，in 1978.He