BETA

3で割った商を求める論理回路を考えて証明してみた

投稿日:2019-07-28
最終更新:2019-07-29

はじめに

コンピュータの内部では2進数で計算しています。最近、3進数の半導体(3進法半導体)の研究も進んでいるようです。
半導体の微細化も限界が近づいてきたため3進数にすることでチップ面積を小さくしたり、低消費電力にする方向が考えられるようになった。という理解を僕はしています。
2進数のコンピュータと接続するためには2進数を3進数に変換する効率のいい回路が必要になる。そこで3で割った商を求める論理回路を考えて証明してみました。

考えた回路の特長

回路が小さいこと。比較的、高速。一般的な除算は最上位ビットから商予測をしながら2bit/cyc程度の性能です。
この回路は最下位ビットから予測なしに直線的に解を求めます。

計算方法の説明と証明

まず3で割り切れる場合を考えます。わかりやすくするため5bitの数、X={x4 x3 x2 x1 x0}で説明します。3は2よりも大きいので商は必ず4bit以下の数になります。商をQ= {d c b a}で表します。
X は2Q + Q で表せます。つまりQを1bit左シフトした値と、Qを加算した値がXになる。1bitの全加算器(フルアダー)を FAとします。
FAのサムをFAs(m,n,cy)、キャリーをFAc(m,n,cy)とすると、2Q + Q の加算は、次のようになる。
(1) x0 = FAs(a,0,0) , cy0 = FAc(a,0,0)
(2) x1 = FAs(b,a,cy0) , cy1 = FAc(b,a,cy0)
(3) x2 = FAs(c,b,cy1) , cy2 = FAc(c,b,cy1)
(4) x3 = FAs(d,c,cy2) , cy3 = FAc(d,c,cy2)
(5) x4 = FAs(0,d,cy3)

これはQからXを求める計算方法ですが、Xはわかっている数なので、XからQを求めます。排他論理和を^の記号とすると全加算器の定義からFAs = m^n^cy です。
またFAc = (m&n) | (m&cy) | (n&cy) です。
よって(1)から a = x0 , cy0 = 0
次に(2)のFAsを考えます。
x1 = b^a^cy0 = b^a
aは既知なので、b = x1^a で計算されます。bが既知になったのでcy1も計算され既知になります。

次に(3)のFAsを考えます。
x2 = c^b^cy1
b,cy1は既知なので、c = x2^b^cy1 で計算されます。cが既知になったのでcy2も計算され既知になります。

次に(4)のFAsを考えます。
x3 = d^c^cy2
c,cy2は既知なので、d = x3^c^cy2 で計算されます。

したがってXからQ = { d c b a} が計算できます。

余りがある場合は

3で割った余りを計算する方法は、良く知られています。僕のブログでも解説しています。
余りは1か2なので2の補数にして加算して3で割れる数にしておきます。商を求める計算とパイプライン的にすれば、もっと高速になります。

おわりに

5bitでの証明でしたが、一般化したn bitでも最下位bitからの計算を繰り返していくだけなので自明です。
3で割った商と余りが計算できれば2進数の値を3進数に変換することは、できると思います。

2019年7月29日 5:30AM 誤字修正 FAは1bitフルアダーでFAのs側の出力をFAs、c側の出力をFAcで表現しているので、入力は同じでないといけない。(2)(3)(4)のFAcの3番目のパラメータが0になっていました。誤字です。

技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
駆け出しエンジニアからエキスパートまで全ての方々のアウトプットを歓迎しております!
or 外部アカウントで 登録 / ログイン する
クランチについてもっと詳しく

この記事が掲載されているブログ

なにか思いついたことを不定期に更新。

よく一緒に読まれる記事

0件のコメント

ブログ開設 or ログイン してコメントを送ってみよう
目次をみる
技術ブログをはじめよう Qrunch(クランチ)は、プログラマの技術アプトプットに特化したブログサービスです
or 外部アカウントではじめる
10秒で技術ブログが作れます!