2017q3 Homework1 (ternary)

contributed by < emoboy13 >

Balanced Ternary原理

• Balanced Ternary是透過三種狀態-1(用t表達)、0、1，並以3為基數來表達數字，例如10=
  $1\times 3^2$ +
  $0\times 3^1$ +
  $1\times 3^0$即表達為101,而-10=
  $-1\times 3^2$+
  $0\times 3^1$-
  $1\times 3^0$即表達為t0t，可以看出Balanced Ternary在表達數字上能直接做正負的轉換，比起2進制需要補數顯得更為直觀。
• 真值表

sum	t	0	1
t	1	t	0
0	t	0	1
1	0	1	t

11之所以為t是因為在balanced ternary中，只有1,0,t三種狀態，而三進制加法中進一位表示運算完後的值在這個位元至少為3，但因為balanced ternary沒有2這個表示法，一旦值大於1便需要進位，因此透過進位後的數字在減去一些來表示這個數，例如:1+1=2=3-1。
而tt為1也是同樣的概念，直接進位後是一個大的負數，所以透過加回一點正數來表達實際的大小。

carry	t	0	1
t	t	0	0
0	0	0	0
1	0	0	1

tt進位值為也t因為進位後要帶進更大的負值

Balanced Ternary computing

multiplexer

• sel為控制訊號線，sel有-1,0,1三種狀態，依sel的值不同，multiplexer會有不同的output(對應n,o,p三種input)
  

increment:

• 是multiplexer，將input A作為訊號控制線，並將input N,O,P分別定義為0,1,-1，因此當A為-1時會輸出0，A為0時會輸出1，A為1時會輸出-1(依據SUM的真值表)，由此可看出，increasement output的值為A+1
  

decrement:

• 同樣也是multiplexer，只是N,O,P改為定義成1,-1,0，這樣的output值為A-1。
  

max(A,0)

• N,O,P定義為0,0,1，output將當於輸出A跟0間較大者，也意味著當A為1時輸出1，其餘皆輸出0。
  

min(A,0)

• N,O,P定義為-1,0,0，output相當於輸出A跟0間較小者，也意味著當A為-1時輸出-1，其餘皆輸出0。
  

half-adder:

• 利用兩層共三個 multiplexer 做出 half-adder。第一層的兩個 multiplexer，訊號控制為 intput A，上面的是 decrement，下面的是increment。將第一層的兩個 multiplexer output以及A,分別做為第二層 multiplexer 的input，這個 multiplexer 的N,O,P 會定義為A-1,A,A+1,input B為訊號控制，這樣的 output會是 A+B，因為當B為-1時候，output會是N，即為A-1，而O,P也是同樣的意思。
  

Consensus:

• 同樣也是兩層 multiplexer，第一層上面的 multiplexer 是min(A,0),下面是max(A,0)。將第一層min,max的 out put作為第二層 multiplexer 的input,以N來看，當A為-1時，N也會是-1，其餘皆為0,O=0,P在A=1時為1，其餘為0，B作為訊號訊號控制，這樣一來Consensus 的output在A=B=-1時輸出-1,A=B=1時輸出1，其餘輸出0，可用來比對A,B是否相等(1 or -1)。
  

full-adder:

• 由三層的 multiplexer 組成，第一層跟half-adder相同，這層會有A-1,A,A+1來作為第二層各個 multiplexer 的input。第二層最上面的 multiplexer ，N,O,P分別為A+1,A-1,A，B作為訊號控制，這樣的輸出會等價於A+B-1，中間的 multiplexer則跟half-adder相同，輸出A+B，最下面的 multiplexer N,O,P分別為A,A+1,A-1,B作為訊號控制，輸出會等價於A+B+1，這一層三個 multiplexer 的output作為第三層multiplexer的N,O,P，分別為A+B-1,A+B,A+B+1，而從上一個(低位元)的full-adder送來的C(carryin)作為訊號控制，這樣最後的輸出就會是A+B+C(進位)。
  

overflow

• 由三層 multiplexer 組成，可以從第三層的 multiplexer N,O,P input來看出這三層的對應關係。
• 首先看第三層N的input，是由第二層最上面的 multiplexer，以及第一層最上面及第二個multiplexer提供，下表表示的是第二層最上面的 multiplexer在對應不同 A,B值而有不同的carry out，因為這個 multiplexer 的output是對應到第三層 multiplexer 的 N，訊號控制是carry in，因此下表中的carry in固定為-1，從表中可以看出當B值為-1時候，只有在A為1時，carry out是0，其餘都是-1，這可以等價為max(A,0)-1;當B為0時，只有在A為-1時，carry out是-1，其餘皆為0，這可以等價為min(A,0);而當B為1時，carry out皆為0，因此藉此定義第二層最上面的multiplexer 的N,O,P分別是max(A,0)-1,min(A,0),0，並透過第一層的 multiplexer來達成。
• 第三層O的input，由第二層中間的 multiplexer，以及第一層中間兩個 multiplexer提供，而這三個 multiplexer就是構成一個 Consensus，因為O在carry in為0時輸出，表示A,B的值就能決定carry out的值，而 carry out 在 A=B=1時為1;A=B=-1時為-1，其餘狀況皆為0，這樣的運作就等同於Consensus的輸出，因此第三層O的input就是透過Consensus的output。
• 第三層P的input概念類似於N，P表示carry in為1時的狀況。

N	$A$	$B$	$C_{in}$	$C_{out}$	O	$A$	$B$	$C_{in}$	$C_{out}$	P	$A$	$B$	$C_{in}$	$C_{out}$
	-1	-1	-1	-1		-1	0	-1	-1		-1	1	-1	0
	0	-1	-1	-1		0	0	-1	0		0	1	-1	0
	1	-1	-1	0		1	0	-1	0		1	1	-1	0

參考

1.Ternary computing: basics

Balanced Ternary應用

• 比較
  1. 數值正負轉換:因為包含1,T這兩種狀態，因此在balance ternary中對一個數值做正負轉換非常容易，而binary需要補數來做正負轉換。
  2. 空間使用:同樣的digit數目下balanced ternary能表達的數值比binary多