平衡3進法～BitとTrit ByteとTryt～

3進法って何

2進法は、皆さんよくご存じ0,1で表す表記法ですが、これにもう１つの数字を足したものを3進法と呼びます。
この3進法には0,1,2と2進法を素直に拡張した通常3進法と、-1,0,+1とマイナスを持った体系の平衡3進法の2種類が存在します。
面白いのがこの平衡3進法で、今までの2進法に慣れた身からすると、目から鱗の発見がいくつもあって非常に興味深いものとなっています。

平衡3進法　Trit と Tryt

まずは3進法の最小単位Tritについてですが、2進法でいうところのBitに相当します。
じゃByteはというとTrytと言います。このTrytですが、1Tryt=6Tritと1Tryt=9Tritの２系統あってこの辺統一感がありません。決めておかないと話がややこしくなるので、今回は1Tryt=9Tritとします。
平衡3進法の表記方法ですが、こちらも統一されたものは特に存在しないようです。0,1は良いとして-1を表すのをどうするか。ここがポイントになります。
-1=Tとしたり素直に-1としたり、-,0,+としたりこちらも統一感がありません。ここでは#,0,+で表記するとします。（-はデータ無しに見えるので避けます）
当然ですが、3進法だと2桁目は3の重み、3桁目は9の重みと重み付けが3の倍数で増えていきます。
例
3trit(#0+) = -8(-9+0+1)
3trit(+##) = 5(9-3-1) と表記します。
面白いのは2進数で存在していた、符号付きと符号なしという区別が無いことです。というか全て符号付きになります。なので、メモリアドレスもマイナス側にメモリを持つことができます。アドレス -208番地　みたいな表現ができることになります。

単位について

trit とか tryt とか単位が出てきましたが、これからの説明で27進法とか出てくるので少し整理します。
trit(トリット):2進法でいうところのbit
hepta(へプタ)=3trit:2進法でいうところの4bit単位のnibbleこれは私が勝手に作った単位です。27進法表記1桁で表します
tryt(トライト)=3hepta=9trit:2進法でいうところのbyte
tri word(トライワード)=3tryt=9hepta=27trit:2進法でいうところのword

論理演算

3進法にも当然AND OR NOTなどの論理演算が存在します。それぞれ説明します。

AND A/Bの最小値を出力します

A	B	X
#	#	#
#	0	#
#	+	#
0	#	#
0	0	0
0	+	0
+	#	#
+	0	0
+	+	+

OR A/Bの最大値を出力します

A	B	X
#	#	#
#	0	0
#	+	+
0	#	0
0	0	0
0	+	+
+	#	+
+	0	+
+	+	+

NOT これは説明要らないでしょう

A	X
#	+
0	0
+	#

XORですが、目的によって何種類かあります。

この時点でXORではなくなっていますが、良い言葉が思いつかないのでXORにしています。

Tritマスクと反転型   特定のTritをマスクor反転させる目的で使います

具体的には、Tritを残したい位置に+、反転させたい位置に#を設定して演算します
例 A=#0+ B=++# X=+0#

A	B	X
#	#	+
#	0	0
#	+	#
0	#	0
0	0	0
0	+	0
+	#	#
+	0	+
+	+	+

Trit同値検出型   特定のTritが指定した値か検出する目的で使います

2進法なら、検知したいビットパターンでANDを取れば検出できますが、3進法はANDではうまくできません。
具体的には、検出したいTrit位置に+or#を設定して演算します
同値の場合は+or#が設定されます
例 A=#0+ B=#00 X=#00

A	B	X
#	#	#
#	0	0
#	+	0
0	#	0
0	0	0
0	+	0
+	#	0
+	0	0
+	+	+

Tritローテーション型   Tritを120度づつのベクトルと見立てた場合、それを120度回転させます。

イメージとしては、特定のtritを+なら時計回り、#なら反時計回りに回転させます
実はこれ、この後の半加算器のXと同じです

A	B	X
#	#	+
#	0	#
#	+	0
0	#	#
0	0	0
0	+	+
+	#	0
+	0	+
+	+	#

半加算器 桁上げを伴った加算器になります。

桁上げもTritなので3値(マイナス、ゼロ、プラス)あってマイナスの桁上げがあります。
1+(-1)=0となったり、2の表現が3+(-1)で表現しているところもポイントです。

A	B	Co	X
#	#	#	+
#	0	0	#
#	+	0	0
0	#	0	#
0	0	0	0
0	+	0	+
+	#	0	0
+	0	0	+
+	+	+	#

全加算器 これは、半加算器の拡張ですね。

Ci	A	B	Co	X
#	#	#	#	0
#	#	0	#	+
#	#	+	0	#
#	0	#	#	+
#	0	0	0	#
#	0	+	0	0
#	+	#	0	#
#	+	0	0	0
#	+	+	0	+
0	#	#	#	+
0	#	0	0	#
0	#	+	0	0
0	0	#	0	#
0	0	0	0	0
0	0	+	0	+
0	+	#	0	0
0	+	0	0	+
0	+	+	+	#
0	#	#	#	+
+	#	0	0	0
+	#	+	0	+
+	0	#	0	0
+	0	0	0	+
+	0	+	+	#
+	+	#	0	+
+	+	0	+	#
+	+	+	+	0

引き算

2進数で引き算をしようとすると、2の補数を作って足すということをしますが、3進法ではNOTでプラスとマイナスが反転するので単純にNOTを通して足すだけです。

掛け算

掛け算は、左シフトしながら足し算するという2進数の掛け算と基本的には同じです。
ただ、マイナスがあった場合は反転して足すということをします。
当然ですが、左シフトすると3倍したことになります。
例として10進5x8の場合を考えてみましょう
A=5:+##
B=8:+0#

1. Bの3桁目を見て+なのでAをそのまま代入X=+##
2. Xは左シフトして　Bの2桁目を見て0なので何もしない
3. Xは左シフトして　Bの1桁目を見て#なのでAを符号反転させて足す
   X=(+##00) + (#++) = (0++++)
   最後の+##に#を足す部分ですが、桁下がりが伝搬して最上位桁が0になります。
   \# + # = #+ この#が次の桁に伝搬
   \# + # = #+ さらに伝搬
   \+ + # = 0 結果 (0++++) 27+9+3+1=40

割り算

割り算は、2進法の時のように、引いてマイナスだったらやめるができないので、絶対値比較ということをします。

1. A÷Bの場合、Bの有効桁を調べてAと桁を揃える。桁が合うまで左シフトする
   この時、シフトした数を覚えておく
2. AとBを [引き算] [何もしない] [足し算] これらの結果のうち絶対値が一番小さいものを採用する
   その時に[引き算]を採用だったら+、[何もしない]だったら0、[足し算]だったら#を商Xに代入する
3. 商Xを左シフト、Bを右シフトして、1でシフトした回数+1、2から繰り返す

• 42÷8=5…2を例に説明します
  A=42:+###0
  B=8:+0#
  BをAと桁を合わせるため左に2桁シフトします
  B=72:+0#00

ループ1回目 A-B A+B を実行

• A-B=+###0 + NOT(+0#00)=#0+00 = 0#0#0(-30)
• A+B=+###0 + +0#00 = 0+++#0(114)
• A =+###0(42)
  絶対値でA-Bのパターンが一番小さいので、+を採用、商X=+ Aは引き算後の値を格納
  A=-30:#0#0
  B=24:+0#0

ループ2回目 A-B A+B を実行

• A-B=#0#0 + NOT(+0#0)=#0+0 = #+000(-54)
• A+B=#0#0 + +0#0 = 0#+0(-6)
• A =#0#0#(-30)
  絶対値でA+Bのパターンが一番小さいので、#を採用、商X=+# Aは引き算後の値を格納
  A=-6:#+0
  B=8:+0#

ループ3回目 A-B A+B を実行

• A-B=#+0 + NOT(+0#)=#0+ =#+++(-14)
• A+B=#+0 + +0# = 0+#(2)
• A =#+0(-6)
  絶対値でA+Bのパターンが一番小さいので、#を採用、商X=+## Aは引き算後の値を格納
  A=2:+#(これが余り)
  X=5:+##

27進法 ヘプタ表記

2進法だと4Bitをまとめて16進数で表記しますが、これも何か無いとtritの羅列だけだと長すぎて良く分からくなるので、3tritをまとめて表記する方法を考えました。これをへプタ(Hepta)表記と名付けました。7=Heptaですね。
3trit:27進法の表記(3の3乗なので27通りです)

10進	3進	27進
-13	#,#,#	n
-12	#,#,0	m
-11	#,#,+	k
-10	#,0,#	j
-9	#,0,0	i
-8	#,0,+	h
-7	#,+,#	g
-6	#,+,0	f
-5	#,+,+	e
-4	0,#,#	d
-3	0,#,0	c
-2	0,#,+	b
-1	0,0,#	a
0	0,0,0	0
1	0,0,+	1
2	0,+,#	2
3	0,+,0	3
4	0,+,+	4
5	+,#,#	5
6	+,#,0	6
7	+,#,+	7
8	+,0,#	8
9	+,0,0	9
10	+,0,+	J
11	+,+,#	K
12	+,+,0	M
13	+,+,+	N

小文字のl(エル)は1と見間違えるので避けました。
マイナス側は小文字、プラス側は大文字としました。数字に小文字は無いのでabcdと割り付けて、10から先は大文字と小文字が反転するように割り当てました。
10:J -10:j
11:K -11:k

これでCPUを作るとどうなる？

3進法の説明は大体終わりました。この平衡3進法を使ってCPUを組むとどういうものになるか？興味がわいてきませんか。
次回からは、CPUの設計に入っていきたいと思います。（構想中）