孫學

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

CORDIC 算法的一種補碼實現(xiàn)結(jié)構(gòu)設(shè)計?

孫學

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

根據(jù)CORDIC算法原理，分析了該算法角度旋轉(zhuǎn)范圍缺陷，提出360°覆蓋的角度旋轉(zhuǎn)算法結(jié)構(gòu)；推導(dǎo)出利用補碼實現(xiàn)CORDIC算法的迭代運算單元結(jié)構(gòu)，并根據(jù)該補碼運算原理設(shè)計了CORDIC補碼迭代運算單元和方向向量發(fā)生器的實現(xiàn)結(jié)構(gòu)。

坐標旋轉(zhuǎn)數(shù)字計算機；方向向量；補碼電路

1 引 言

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

本文第2節(jié)基于CORDIC算法原理分析了該算法實現(xiàn)角度旋轉(zhuǎn)存在覆蓋范圍缺陷，提出一種360°角度覆蓋的CORDIC旋轉(zhuǎn)算法結(jié)構(gòu)。第3節(jié)基于該算法結(jié)構(gòu)，創(chuàng)新性地推導(dǎo)出CORDIC迭代運算單元的一種補碼實現(xiàn)結(jié)構(gòu)，是本文的描述重點。

2 CORDIC算法

2.1 CORDIC算法原理［1］

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

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

其角度θ分解方法為

圖1 CORDIC算法迭代結(jié)構(gòu)框圖Fig.1 Circuit of original form CORDIC iteration operator

2.2 角度旋轉(zhuǎn)范圍缺陷及補償設(shè)計

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

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

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

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

3 C ORDIC補碼實現(xiàn)結(jié)構(gòu)設(shè)計

3.1 CORDIC的原碼實現(xiàn)原理

根據(jù)CORDIC算法迭代結(jié)構(gòu)框圖，設(shè)計其原碼實現(xiàn)結(jié)構(gòu)，如圖2所示。

圖2 CORDIC的原碼實現(xiàn)原理Fig.2PrincipleoforiginalformCORDIC

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

3.2 CORDIC的補碼實現(xiàn)原理

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

圖3 CORDIC的補碼實現(xiàn)原理Fig.3PrincipleofcomplementaryformCORDIC

該實現(xiàn)方法的關(guān)鍵在于補碼移位算法和CORDIC補碼迭代單元設(shè)計。

3.3 補碼移位器設(shè)計

假設(shè)輸入的整數(shù)X的原碼數(shù)據(jù)為

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

定義負整數(shù)X的反碼為

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

定義數(shù)據(jù)的補碼為

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

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

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

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

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

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

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

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

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

式（23）的實現(xiàn)結(jié)構(gòu)如圖4所示。

圖4 補碼移位器結(jié)構(gòu)設(shè)計Fig.4 Complementary form shifting

3.4 方向向量發(fā)生器設(shè)計

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

圖5 方向向量δi發(fā)生器Fig.5 Direction vector generator

3.5 CORDIC補碼迭代單元設(shè)計

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

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

因此，設(shè)計CORDIC補碼迭代運算單元的實現(xiàn)結(jié)構(gòu)如圖6所示。

圖6 CORDIC補碼運算單元實現(xiàn)結(jié)構(gòu)Fig.6 CORDIC iteration operator based on complementary form shifting

4 小 結(jié)

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

［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年于重慶大學獲碩士學位，現(xiàn)為工程師，主要研究方向為交換式總線、分布式計算和陣列計算技術(shù)。

Email：sun8xue＠163.com

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