# 2017q3 Homework1 (ternary)

contributed by <`yang196569`>

## Balanced Ternary

### 定義

Ternary是標準三進制(Standard ternary system)，使用的數值是0, 1 , 2，而Balanced Ternary的數值則是 -1 (記作"T") , 0, +1 ,也可以計為$-$, 0 , $+$。

### 數值系統轉換
* 三進位轉十進位:
給定一個數$A_nA_{n-1}A_{...}A_1A_0.B_0B_1B_{...}B_{m-1}B_m$ ，其中A是整數部份，B是小數部份，則轉換為十進位$X_{dec10}$可表示為 :　$X_{dec10}= \displaystyle \sum_{k=0}^nA_k\times\ 3^k\ + \displaystyle \sum_{l=0}^m\ B_l\times\ 3^{-(l+1)}$ ,
$A_k,B_l$為 1, 0或-1(T)，
如：
* $10T_{bal3}=1\times 3^2\ +\ 0\times 3^1\ +\ (-1)\times 3^0=\ 8_{dec10}$
* $T01_{bal3}=(-1)\times 3^2\ +\ 0\times 3^1\ +\ 1\times 3^0=-8_{dec10}$
* $1.0T_{bal3}=1\times 3^0\ +\ 0\times 3^{-1}\ +\ (-1)\times 3^{-2}=\dfrac{8}{9}_{dec10}$
* $T.01_{bal3}=(-1)\times 3^0\ +\ 0\times 3^{-1}\ +\ (-1)\times 3^{-2}=-\dfrac{8}{9}_{dec10}$
三進位時，若將每個位的數字倒過來(1變T, T變1, 0不變)，那麼轉換為十進位後只需要加負號即可。
* 十進位轉三進位:
先找到距離 $X_{dec}$ 最近的整數，然後分別對整數部分和小數部分進行連除法和連乘法即可。
以下的例子，在 ==|== 的左邊是整數部份，右邊是小數部份。

如：
* $9.2_{dec10}$最近的整數是$9$,餘$0.2$
$9 \div3=3$ 餘$\ 0$$\ \ |$ $\ \ 0.2\times3=0.6\ ,最近的整數是1，餘-0.4$
$3 \div3=1$ 餘$\ 0$$\ \ |$ $-0.4\times3=-1.2\ ,最近的整數是-1,餘-0.2$
整數部份已結束 $|$ $-0.2\times3=-0.6\ ,最近的整數是-1,餘\ 0.4$
整數部份已結束 $|$ $\ 0.4\times3=1.2\ ,最近的整數是1 ,餘\ 0.2$
整數部份已結束 $|$ $0.2\times3=0.6\ ,最近的整數是1,餘\ 0.4,進入循環$
轉換過後，$9.2_{dec10}=1\times3^2+0\times3^1+0\times3^0+1\times3^{-1}+\ ...=100.1\overline{TT11}$
### 加法器
#### 邏輯真值表
* And
( $a$ ^ $b$ ) $=$ min ($a$, $b$)

| ^ | T | 0 | 1 |
| - | - | - | - |
| T | T | T | T |
| 0 | T | 0 | 0 |
| 1 | T | 0 | 1 |

* OR
( $a$ ∨ $b$ ) $=$ max ($a$, $b$)

| ∨ | T | 0 | 1 |
| - | - | - | - |
| T | T | 0 | 1 |
| 0 | 0 | 0 | 1 |
| 1 | 1 | 0 | 1 |

* XOR

| ⊕ | T | 0 | 1 |
| - | - | - | - |
| T | T | 0 | 1 |
| 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | T |

#### 半加器(Balanced Half Adder)

| $input\ a$ | $input\ c_i$ | $output\ c_{i+1}$ | $output\ s_{i}$ |
| - | - | - | - |
| T | T | T | 1 |
| T | 0 | 0 | T |
| T | 1 | 0 | 0 |
| 0 | T | 0 | T |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 |
| 1 | T | 0 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | T |

觀察後可看出
* `Carry` $c_{i+1}=(a_i⊠c_i)$ ，可以參考 [Consensus](http://homepage.divms.uiowa.edu/~jones/ternary/logic.shtml#cons)
* `Sum` $s_i=(a_i+c_i)$ ，可以參考 [Sum](http://homepage.divms.uiowa.edu/~jones/ternary/logic.shtml#sum)

另外，也有人使用[多工器](https://github.com/ssloy/tutorials/wiki/Ternary-computing:-basics)實現全加器以及半加器，可以參考。

### 實際應用
找應用的過程中，我找到[歷史故事](http://www.twword.com/wiki/%E4%B8%89%E9%80%B2%E4%BD%8D)，文章的`應用歷史`部分有寫到關於三進位計算機的誕生與衰落。

* 關於[區塊鏈](https://www.lightblue.asia/q-n-a-for-blockchain/)的內容，這裡有簡單的說明可以參考，這裡不贅述。
* [IOTA](http://www.tangleblog.com/what-is-iota-what-is-the-tangle/)簡單來說並不是以區塊鏈為根基，有幾項不同之處:

簡單介紹完IOTA後，到底跟Balanced Ternary有何關聯呢?
在[The Tech Behind IOTA Explained](http://www.tangleblog.com/2017/01/25/the-tech-behind-iota-explained/)提到，透過`ternary JINN processor`運行，會讓交易紀錄保持著穩定與平衡。
`(原句:These 3 states perform transaction very balanced, which is quite helpful to build a self-organizing and self-sustaining network like the tangle.)`

### 參考資料

[Balanced Ternary](https://en.wikipedia.org/wiki/Balanced_ternary)
[三進位](http://www.twword.com/wiki/%E4%B8%89%E9%80%B2%E4%BD%8D)
[Adder Implementation](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml#halfbalanced)
[Ternary Computing](https://github.com/ssloy/tutorials/wiki/Ternary-computing:-basics)
[The Tech Behind IOTA Explained](http://www.tangleblog.com/2017/01/25/the-tech-behind-iota-explained/)

###### tags: `MISC`