関数電卓コラム

10/02/24 関数電卓のしくみ(CORDICアルゴルズム)

またまた「理系人のための関数電卓パーフェクトガイド」の話題．先日，読者の方からメールを頂いた．内容を抜粋すると，

P.244-245　CORDICアルゴリズムの項

図C-8　CORDICの図解

「図C-8の要領で三平方の定理を使えば掛け算と足し算の組み合わせだけでxとyが求まります」と記されています．

しかし私はこの図C-8を穴の開くほど見つめてもxとyを求める方法が解りません．
どこかに補助線を引くと閃くのかと思い，図を横から見たり，逆さまから見たりと
何度も見直しましたが閃きません．

何かとんでもない勘違いをしているような気もしています．

もし宜しければ教えて頂けないでしょうか．

とのこと．実は，このページを書いているときはCORDICのわかりやすい説明が思いつかなかったことと，コラムという限られたスペースであることから，実際の計算アルゴリズムを示すよりむしろ表引きと加減乗除のみで任意の角度の三角関数値が原理的に求められることを示すにとどめたのだった．

原理的には図C-8の方法でも任意の角度の三角関数を求めることができるが，これは概念的なものを図示したもので，実際には関数電卓は余計な計算を省いた，もっと賢い方法で計算を行っている．今回はこれを説明しよう．題して，

「サルでも分かるCORDICアルゴリズム」

はじめにちょっと蘊蓄を垂れてみよう．CORDICとはCOordinate Rotation DIgital Computerの略で，関数の値を足し算，引き算のみで求めてしまう優れたアルゴリズムだ．発明したのはアメリカのコンベア社に勤めるJ. E.. Volderというエンジニアで1959年のこと．はじめは爆撃機のアナログ式ナビゲーションシステムをデジタル回路に置き換える目的で開発されたというのだが，その天才的発想は見事と言うしかない．計算速度は早くはないのだが，非常に小規模な電子回路にハードウェア的に組み込めるため，関数電卓や組み込みICチップなどに好んで使われる．求められる関数は三角関数，指数，対数など多岐にわたるが，アルゴリズムの原理上，三角関数の値を求める方法がもっともわかりやすい．

Web上の情報源を下記に挙げておく．

関数電卓アルゴリズムの検証　Design Wave Magazine Vol. 20記事
CORDICアルゴリズムによる三角関数計算モデル　MathWorks社資料
How Do Calculators Calculate?　Helmut Knaust
CORDIC FAQ　Iowegian International
CORDIC　Wikipedia
The secret of the algorithms　Jacques Laporte's Home on the Web

ではこれから，任意の角度のsinθ，cos，tanθを求める方法を考えよう．CORDICでは，計算に必要な定数のテーブルをあらかじめ計算して持っておく点が特徴．必要なデータ数は，有効数字10桁としても高々30だから，大きなメモリを必要とするわけではない．

三角関数の場合，持つべきデータは

となる角度
下で説明する「変換ベクトル」の絶対値

である．これをまず計算しておこう．Fig. 1(a)の様に，底辺と高さの比率が1，，．．．と半分になっていく一連の直角三角形を考える．これらの三角形の鋭角の値が，となる角度だ．これらは関数電卓でもなんでも，適当な方法を使って幾らでも高い精度で知ることができる．ここではi=17までの計算を行い，表1に示した．続いて変換ベクトルだが，これは次のようなものである．i=0の直角三角形を考える．斜辺の長さはだ．これをとしよう．ここに，Fig. 1(b)の様にi=1の直角三角形を貼り付けるが，このとき底辺がi=0の斜辺の長さに一致するよう拡大する．この三角形は底辺と高さの比率が2:1になるよう選ばれているから，斜辺の長さは，簡単な計算でとわかる(がどう定義されているかを思い出そう)．これをとする．これを17回くり返したときの斜辺の長さ，が変換ベクトルの絶対値だ．この値はi→∞では1.64760258．．．に収束する．

表1: CORDICアルゴリズムによる三角関数(sin，cos，tan)の計算に必要なデータ

i	θi=atan(1/2^i)	ベクトル絶対値ri
0	45	1.414213562	=
1	26.56505118	1.58113883	=
2	14.03624347	1.629800601	=
3	7.125016349	1.642484066	・
4	3.576334375	1.645688916	・
5	1.789910608	1.646492279	・
6	0.89517371	1.646693254
7	0.447614171	1.646743507
8	0.2238105	1.64675607
9	0.111905677	1.646759211
10	0.055952892	1.646759996
11	0.027976453	1.646760193
12	0.013988227	1.646760242
13	0.006994114	1.646760254
14	0.003497057	1.646760257
15	0.001748528	1.646760258
16	0.000874264	1.646760258
17	0.000437132	1.646760258

(グリーンのセルのみ必要)


(a) になる直角三角形	(b) (a)で作成した直角三角形を互いに重ねる

　Fig. 1: CORDICアルゴリズムで必要な直角三角形群と変換ベクトルの絶対値

さて，続いて，実際に与えられた角度の三角関数を計算する方法について述べる．具体的な角度があった方がいいので，ここはθ=30°とする．また，説明を簡単にするため，ここでは角度は0°から90°の範囲に限ることとしよう．

CORDICアルゴリズムでは，角度は常に45°を出発点とする．ここで，証明はしないが一つの定理を示す．

定理：0°から90°の任意の角度は，充分な精度で，，．．．全ての足し算と引き算の組み合わせで表せる．

例えば，30°は

　　　(1)

である．具体的に，を足すのか，引くのかは次のような簡単なアルゴリズムで求められる．

の符号は無条件にプラス．
-30°>0なのでは引き算でなくてはならない．符号はマイナス．
--30°<0なのでは足し算でなくてはならない．符号はプラス．
以下同様．

これを認めたところで，次のステップ．まず，斜辺が=45°の直角三角形を描き，その斜辺を底辺とする，斜辺が=26.56．．．°の直角三角形を重ねる．このとき，三角形の向きをどちらにするかは，式(1)の符号に従う．の符号はマイナスだから，Fig. 2に示されるように，斜辺の角度が引き算になるように置こう．

Fig2: CORDICの第一ステップ．i=1の三角形(青)をi=0の三角形(黒)に裏返して重ねる．

幾何の定理を使い，i=1の直角三角形(青)の短い方の辺を斜辺とする，赤の直角三角形はi=0の直角三角形と相似であることが示せる．そして，i=1の直角三角形(青)の斜辺でない2辺の大きさの比は2:1になるようには選ばれているから，赤い三角形の大きさはi=0の三角形の1/2となる．

いま，図のように直角三角形の頂点をベクトルを，，．．の様に名付け，そのx座標，y座標をとする．ベクトルの座標は当然(1，1)，そしての座標はFig. 2から(3/2，1/2)と求められる．各々のベクトルの長さは，三角形をどちらの向きに重ねても同じで，表1に示される値となる．

今の計算を下のように書き直す．

　　　(2)

続いて，i=1の三角形に，ベクトルが底辺になるようにi=2の三角形を重ねよう．今度は，式(1)のの符号がプラスだから，足し算になるように重ねる．

Fig3: CORDICの第二ステップ．i=2の三角形(緑)をi=1の三角形(青)に重ねる．

今度は，赤い三角形は，図で黄色く示したベクトルを頂点とする直角三角形と相似形である．比率は，i=2の緑の三角形の二辺の比率が4:1であることから4:1と直ちにわかる．従って今度は以下の計算が成り立つだろう．

　　　(3)

続いて，i=2の三角形に，ベクトルが底辺になるようにi=3の三角形を重ねよう．今度は，式(1)のの符号がマイナスだから，引き算になるように重ねる．

Fig4: CORDICの第三ステップ．i=3の三角形(ピンク)をi=2の三角形(緑)に重ねる．

今度は，赤い三角形は，図で黄色く示したベクトルを頂点とする直角三角形と相似形である．比率は，i=3のピンクの三角形の二辺の比率が8:1であることから8:1と直ちにわかる．従って今度は以下の計算が成り立つだろう．

　　　(4)

ここからは，三角形がどんどん小さくなっていくので図示しないが，要領はもう分かるだろう．のx，y座標は，同じ理屈で行けば

　　　(5)

となるに違いない．これを一般化すると以下の様に表現できる．

　　　(6)

ここで，は式(1)での前に付く符号で，+1か-1をとる．

この計算をi=17まで実行した結果をFig. 5に示す．もはや，三角形は一本の線にしか見えない．

Fig5: CORDICの第17ステップ終了後の状態．

ここまでくれば，賢明な諸兄ならsin30°，cos30°，tan30°の値が既に求まっていることに気づくだろう．斜辺の長さ，1.64760258はあらかじめ計算しておいたで，，は今までの17回のステップで最終的に求められたのx，y座標．そしてsin30°，cos30°，tan30°は

　　　(6)

により求められる．注目するべきは，最後のステップまで掛け算，割り算を一切使わず，テーブルを引くだけで三角関数が求められた，ということだ．なぜなら，2進数においてはの掛け算は10進数でいうところの「10で割る」演算に相当する「ビットシフト演算」に過ぎないためだ．また，ハードウェア的な実装では割り算すら嫌い，をあらかじめ計算しておいてそれを掛ける手法を取る．