かねてより温めていた計画である自作3進CPU計画の第1弾として、まずは基本的な論理回路を作ってみました。
2進数といえばコンピュータ、コンピュータといえば2進数というのが常識となっていますが、そんな常識を打ち破りたいと思っています。
なぜ3進法なのか
ほとんどの人が最もよく使う記数法は10進法でしょう。（なにしろこの10という数字も10進法で書かれていますからね。）
コンピュータ及びプログラミングに馴染みのある人にとっては2進法、8進法、16進法も馴染み深いかもしれません。
あまり意識していないかもしれませんが、時間などでは12進法や60進法が使われていることにも気が付くでしょう。これらは3をはじめ多くの約数を持つのが長所と言えるでしょう。
ところで、最も効率のいい記数法は何か考えたことがあるでしょうか。当然「効率」をどう定義するかは非自明ではありますが、次のように考えてみましょう。
まずある値Nを用意してN種類の値をn進法で表現することを目標とします。
n進法で1桁を表現するのに必要なコストがnであると仮定します。ここでいうコストは例えば記憶素子の数なんかだと思ってください。
Nをn進法で表現するには lognN 桁が必要になります。（整数への丸めは気にしない。）よってN種類の値をn進法で表現するのに必要なコストは n lognN となります。
nについて微分することでコストが最小となるnを求めると、n = e = 2.718.. となります。
大胆な仮定のもとではありますが、数学的に裏付けられた理想の記数法はe進法となります。基数は整数の方が嬉しいのでeに最も近い整数を探してみましょう。
そう、3ですね。（2 log2N > 3 log3N であることを確認した方が適切でしょう。）
なお以上の話は建前で、本音を言うと「2進法以外でコンピュータ作ったら面白そうじゃね？じゃあ3進法で作るか！」と思い立っただけです。
平衡3進法
3進法には 0, 1, 2 の値を用いる通常の3進法のほかに、0, 1, -1 を用いる平衡3進法というものが存在します。
まずは平衡3進法でいくつかの数をどのように表現するのか見てみましょう。-1は 1 と表記するのが一般的なようですが、ここでは # で表記します。
例えば 7 について、普通の3進法では
21 (2 × 3 + 1 × 1)
と表記しますが、平衡3進法では
1#1 (1 × 9 + -1 × 3 + 1 × 1)
と表記することになります。
これだけ見ても何がいいのか分からないと思いますが、平衡3進法の真価は負の数の表現で発揮されます。以下が負の数の例です。
10進法の欄は符号付絶対値と呼ばれる表記方法で、0~9の数字のほかに-の記号を用いて負の数を表現します。この方法では 0 と -0 という同じ数字に対して2通りの表現ができてしまう問題があります。
普通の3進法の欄は4桁の3の補数表現で負の数を表しています。例えば 2220 (-3) は 10 (3) と足したら 10000 となり、下4桁だけ考えるとすれば 0 となります。ちなみに一般のコンピュータは2の補数表現を用いて負の数を扱っています。
3の補数表現の場合、符号付絶対値のときに生じた表現の一意性の問題は解決できますが、値の範囲の非対称性が問題となります。
符号なし3進数4桁では 0 ~ 80 の値が表現できますが、最上位桁が 2 の場合は負の数と解釈すると -27 ~ 53 の値が表現できることになります。3進法なので正負の割合が1:1になりません。（2進法の場合でも4桁だと -8 ~ 7 となり完全な対称にはなりません。）
このように負の数の記法には欠点がしばしば伴うのですが、平衡3進法はこれらの問題を完全に解決してしまいます。
平衡3進法では最初から -1 があることにより負の数を自明に表現することができます。また正の値と比較すると、値を-1倍することは各桁の 1 と -1 を反転させることに対応していることが分かります。すなわち完全な対称性が実現されているのです。
そのほかの平衡3進法の特徴として、
- 最上位桁が1なら正、-1なら負で、0になるのは値が0の場合に限る。
- 値を丸めるときは切り捨てにより最近接丸めができる。（四捨五入のような概念が不要）
などがあります。
丸めについて、例えば 7.66.. を8に丸める場合、通常の3進法だと 21.2 → 22 となりますが、平衡3進法だと 10#.# → 10# となります。
このように平衡3進法は嬉しい性質をいくつも持っており、コンピュータサイエンスにおけるバイブル的な存在である The Art of Computer Programminng において著者のKnuth先生は「おそらく、あらゆる記数法の中で最も美しいものは平衡三進法である」と述べています。
私の自作3進CPUにおいても平衡3進法を用います。
3値論理
記数法としての平衡3進法を紹介しましたが、次に {-1, 0, 1} という3つの値の集合の上での論理について考えます。
一般的な論理は {0, 1} あるいは {T, F} という2元集合上での ∧, ∨, ￢, → （それぞれ かつ、または、否定、ならば）の意味を定義しています。
3元集合における論理の1つとして、T、F に U (Undefined) を加えてその ∧, ∨, ￢, → の意味を定義する方法がありますが、今は論理学に興味があるわけではないので代数的な考え方を取りたいと思います。
代数的に考えると普通の2値論理はブール束という代数系になります。束というのは2項演算の∧と∨が束の公理を満たすように定義されている集合のことです。束の公理は省略しますが、その集合に順序（不等号） < が定義されているなら、
a ∧ b = min(a, b)
a ∨ b = max(a, b)
となります。（より一般的には半順序、sup、infで考えます。）
束とか小難しい話はさておき、2値論理の AND と OR を確認してみましょう。
見慣れた真理値表だと思いますが、確かに AND が min、OR が max になっています。
それではこれを3値論理に拡張してみましょう。AND と OR を min と max として定義します。また NOT も図のように定義するのが自然でしょう。
3値論値に関してその意味には深入りしないことにしますが、1つ注意点を挙げておくと、a ∨ ￢a は必ずしも 1 になりません。a = 0 のときこれは 0 となります。
回路での実装
3値論理の基本演算を定義しましたが、私がやりたいのは3進CPUの作成なので物理的な回路として実装しなければ意味がありません。
論理回路を実現するためにどんな電子部品を使用するかをまず決めないといけませんが、今回は一般的なロジックICなどで用いられる CMOS を用いることにしました。
CMOS とは Complementary MOS の略で NMOS と PMOS のセットのことです。MOS あるいは MOSFET は Metal Oxide Semiconductor Field Effect Transistor の略で、電圧で制御できるスイッチの役割を果たします。
NMOSはG(ゲート)にS(ソース)よりも高い電圧をかけるとONとなりD(ドライバ)とSが導通します。
PMOSはGにSよりも低い電圧をかけるとONとなりDとSが導通します。
まずは一般的な2値論理の NOT, NAND, NOR がCMOSでどのように実装されるのかを見てみましょう。なおCMOSによる実装ではANDよりもNANDの方が基本的になります。
画像をクリックするとこの回路のシミュレーションができる外部サイトを開きます。
NANDの動作について考えてみましょう。上側にはPMOSが並列に、下側にはNMOSが直列に入っています。
AとBの両方が1のとき、PMOSはどちらもOFFになり、NMOSはどちらもONとなるので0が出力されます。
それ以外のとき、すなわちAとBの少なくとも一方が0のとき、PMOSは少なくとも一方がONとなりNMOSは少なくとも一方がOFFになるので1が出力されます。
なお、ここでの0と1は0Vと5V(5Vである必要性はない)の電圧に対応します。
次にここまでの知識を踏まえて3値論理回路について考えていきます。
まず -1, 0, 1 の値をどう表現するかですが、-5V, 0V, 5V の3つの電圧に対応させることとします。負電源が必要になりますが、これについては後述します。
続いて3値論理の NOT, NAND, NOR についてですが、以下のような回路を考案しました。
画像をクリックするとこの回路のシミュレーションができる外部サイトを開きます。
先ほどの2値論理回路とほぼ同じ回路であることが分かると思います。違う点は出力の手前に抵抗が入っていることと、下側の電圧が0ではなく-1になっている点だけです。
まず上側のPMOSについてですが、Sの電圧が1なのでGの電圧が0または-1のときにONとなります。同様に下側のNMOSについてはGの電圧が0または1のときにONになります。
またNANDを例に動作を考えてみると、AとBの両方が0または1のときNMOSがONとなり、AとBの少なくとも一方が0または-1のときPMOSがONとなります。
そしてNMOSとPMOSのうち片方だけがONの場合はその電圧が出力されますが、両方がONになる場合は抵抗で分圧されて0が出力されます。図にすると以下の通りです。
NOT, NORについても同様です。
CMOSに加えて抵抗を用いることによって3値論理回路を構成することができました。この構成の特徴としては次のようなものがあります。
- 〇 2値論理と比較してMOSの数が変わらない。
- △ 出力インピーダンスが大きい。
- △ CMOSなのにスタティック電流が発生する。
出力インピーダンスに関して、抵抗を通して出力するので出力から電流を取ろうとすると電圧降下が発生してしまいます。そのため出力に直接LEDをつけるといったことはできません。
スタティック電流は特定の値を出力し続けるときに必要な電流のことで、2値論理のCMOS論理回路ではスタティック電流がゼロという特徴があります。この構成では0を出力するときにNMOSとPMOSの両方がONになるのでスタティック電流が発生してしまいます。
補助回路
3値論理回路の設計はできましたが、いくつかの補助回路を用意して実験を効率化したいと思います。
電源
先ほど説明した通り、±5Vの電源を用意する必要があります。
今回は10Vの電源を用意してオペアンプで仮想グランドを生成することにしました。10V電源さえ用意できればとても簡単に±5Vを生成できます。
オペアンプの出力を－入力に直接フィードバックすることで＋入力の電圧をコピーして出力するボルテージフォロワという回路になります。
LED出力
電圧は目に見えないので回路の入出力の値をLEDによって確認したいです。しかし先ほど説明した通り3値論値回路の出力インピーダンスが大きいので直接LEDを繋ぐことはできません。
また2値の場合はLEDのONとOFFで値を表現できますが、3値の場合はLEDを2個以上用いることになります。
これらの点を踏まえて、コンパレータと2色LEDを用いてLED表示回路を作ることにしました。
コンパレータはオープンコレクタの NJM2903 を用いました。コンパレータの電源には±5Vを供給します。こうするとコンパレータの出力は＋入力の方が電圧が高いときはHi-Z、－入力の方が電圧が高いときは-5Vとなります。
上のコンパレータの－入力には1.6Vが入力されているので、inputが0Vまたは-5Vのとき-5Vを出力しRedのLEDが点灯します。
同様に下のコンパレータの＋入力には-1.6Vが入力されているので、inputが0Vまたは5Vのとき-5Vを出力してGreenのLEDが点灯します。
結果として、inputが5Vのときは緑、-5Vのときは赤、そして0Vのときは緑と赤が混ざって橙が点灯します。
2色LEDの極性にはよく注意しましょう。（1敗）
実際に作ってみた
というわけで実際に3値論理回路をユニバーサル基板で実装してみました。
NMOSは BS170、PMOSは MTB060P06I3 を使用しました。
続いて先のLED表示回路にスライドスイッチをつけて入出力を便利にできるコントローラ基板を作りました。
ジャンパピンで入力と出力を選択できるようになっています。
この基板は PCBGOGO さんの提供で作成しました。注文から僅か4日で届きました。（配送業者はDHL）
品質についても申し分ないと思います。新規特典もあるので皆さんもプリント基板を作る際はぜひ PCBGOGO を検討してみてください。
ということで作成したNORとNOTをつなげてORを作ってみました。
実験結果がこちらになります。左2つが入力、右が出力です。
入力のうち大きい方が出力されて、きちんとORの計算ができていることが確認できました。
最後までご覧いただきありがとうございました。
次は加算器を作ってみようと思います。次の更新をお待ちください。
