# 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。
.png)
### min(A,0)
* N,O,P定義為-1,0,0，output相當於輸出A跟0間較小者，也意味著當A為-1時輸出-1，其餘皆輸出0。
.png)
### 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)。
.png)
### 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](https://github.com/ssloy/tutorials/wiki/Ternary-computing:-basics)

## Balanced Ternary應用

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