孫學(xué)

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

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

孫學(xué)

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

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

坐標(biāo)旋轉(zhuǎn)數(shù)字計(jì)算機(jī)；方向向量；補(bǔ)碼電路

1 引 言

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

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

2 CORDIC算法

2.1 CORDIC算法原理［1］

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

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

其角度θ分解方法為

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

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

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

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

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

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

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

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

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

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

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

3.2 CORDIC的補(bǔ)碼實(shí)現(xiàn)原理

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

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

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

3.3 補(bǔ)碼移位器設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.5 CORDIC補(bǔ)碼迭代單元設(shè)計(jì)

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

其中，當(dāng)δi=+1時(shí)，（δi）表示減法運(yùn)算；當(dāng)δi=-1時(shí)，（δi）表示加法運(yùn)算。代入式（23），則：

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

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

4 小 結(jié)

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

孫學(xué)（1978—），男，重慶合川人，2004年于重慶大學(xué)獲碩士學(xué)位，現(xiàn)為工程師，主要研究方向?yàn)榻粨Q式總線、分布式計(jì)算和陣列計(jì)算技術(shù)。

Email：sun8xue＠163.com

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