# 2017q3 Homework1 (ternary)
contributed by <`louis222220`>

### Reviewed by`vonchuang`
* 在 Balanced Ternary 的壞處中列了一項："目前的電腦架構幾乎為Binary"，然此並非其壞處，只是結果
* "老實說目前雖然瀏覽過了這些文章，還是不了解 Balanced Ternary 解決了什麼問題"，可參考 [The Balanced Ternary Machines of Soviet Russia](https://dev.to/buntine/the-balanced-ternary-machines-of-soviet-russia) 及 [THE TECH BEHIND IOTA EXPLAINED](http://www.tangleblog.com/2017/01/25/the-tech-behind-iota-explained/)
* 文中部分內容的中英文未以空白相隔
* "這樣就能實現Balanced Ternary 半加法器，進一步完成全加法器"，可對全加器詳述之

## 作業要求
- [ ]研讀 Balanced Ternary，並依據 課前測驗參考解答: Q1 的風格和探討方式，涵蓋以下:
- [ ] 解釋 Balanced Ternary 原理;
- [ ] Balanced Ternary 的設計要解決什麼類型的問題，需要詳述實際應用案例 (如 IOTA/Tangle)。提示：從算術表達的精準度和空間使用效率去探討;
- [ ] 針對特定的領域 (如加密貨幣)，列出在 GitHub 裡頭可找到的應用案例，不僅列出程式碼，還要解說;
- [ ] 在研究的過程中，應該會對既有工具進行修改或者重新開發 (不限程式語言)，也該一併指出，程式碼應該維護在 GitHub 上;
- [ ] 建立新的 HackMD 頁面，並列於 作業區。撰寫數學式應該全部用 LaTeX 表示，不該用圖片
- [ ]在 GitHub 上 fork balanced-ternary，針對你的分析需求，進行必要的修改
- [ ]提交修改前，務必確認詳讀 如何寫好 Git Commit Message

---
---

## 解釋 Balanced Ternary 原理

### Ternary簡介
Ternary 三進位是以3為基數的進位數字系統，以`0`,`1`,`2`來表示每一位數，相較於 Binary 二進位以`0`,`1`來表示的數字系統。用 Ternary 來表示同一個數字，能比 Binary 使用更少的位數。
example:
10~10~ = (1 * 10^1^) + (0 * 10^0^) = 10~10~ + 0
1010~2~ = (1 * 2^3^) + (0 * 2^2^) + (1 * 2^1^) + (0 * 2^0^) = 8~10~ + 2~10~
101~3~ = (1* 3^2^) + (0 * 3^1^) + (1 * 3^0^) = 9~10~ + 1~10~

|Decimal|Binary|Ternary|
|:-:|:-:|:-:|
|0|0|0|
|1|1|1|
|2|10|02|
|10|1010|101|

### Balanced Ternary 簡介

- 每一個位元(trit)使用`-1`, `0`, `1`作為值，取代原本 Ternary 的`0`, `1`, `2`
- 可用`-`, `0`, `+` 或 `T`, `0`, `1` 來表示

#### 數字表示方式^[6]^
將三進位數值表示成十進位數值算法為 ： $\displaystyle
\sum_{k=1}^{i} a_k \times 3^{k-1} + \displaystyle \sum_{n=1}^{j} a_n \times 3^{-n}$
其中 $i$ 為三進位數值整數部分的trit， $j$ 為三進位數值小數部分的trit
$a_k$ 及 $a_n$ 為 $T$、$0$ 或 $1$

- 負數的轉換只要將 Balanced Ternary 中的每個trit做Bitwise NOT處理
- 整數
e.g. $1T1T_{bal3} = 1 \times 3^3 + (-1) \times 3^2 + 1 \times 3^1 + (-1) \times 3^0 = 27-9+3-1 = 20_{dec}$
e.g. $T1T1_{bal3} = (-1) \times 3^3 + 1 \times 3^2 + (-1) \times 3^1 + 1 \times 3^0 = -27+9-3+1 = -20_{dec}$

- 分數(小數)
e.g. $\dfrac{1}{3} = 1 \times 3^{-1} = 0.1_{bal3}$
e.g. $\dfrac{1}{2} = 0. \overline 1_{bal3}$
$\frac{1}{2} \times 3 = 1 + \frac{1}{2}$
$\frac{1}{2} \times 3 = 1 + \frac{1}{2}$ (循環...)

### Logic
#### 定義
Kleene 從 Binary 的 `true`, `false` 延伸出 Ternary 的布林代數^[3,4,7]^

| truth value | ternary | balanced ternary |
|-|-|-|
| false | 0 | - |
| unknown | 1 | 0 |
| true | 2 | + |

#### 邏輯運算

- NOT

|NOT|value|
|-|-|
|-|+|
|0|0|
|+|-|

- - AND (相當於是MIN)

|AND|-|0|+|
|-|-|-|-|
|-|-|-|-|
|0|-|0|0|
|+|-|0|+|

- OR (相當於是MAX)

|OR|-|0|+|
|-|-|-|-|
|-|-|0|+|
|0|0|0|+|
|+|+|+|+|

- SUM
相加

|SUM|-|0|+|
|-|-|-|-|
|-|+|-|0|
|0|-|0|+|
|+|0|+|-|

- Consensus

|CONS|-|0|+|
|-|-|-|-|
|-|-|0|0|
|0|0|0|0|
|+|0|0|+|


### Balanced Ternary Operation
利用 Balanced Ternary 的邏輯運算
- 半加法器
Input: $a_i$、 $c_i$
Output: $c_{i+1}$、$s_i$

**真值表:**
|$a_i$|$c_i$|$c_{i+1}$|$s_i$|
|-|-|-|-|
|-|-|-|+|
|-|0|0|-|
|-|+|0|0|
|0|-|0|-|
|0|0|0|0|
|0|+|0|+|
|+|-|0|0|
|+|0|0|+|
|+|+|+|-|

可分別整理成
|$c_{i+1}$|-|0|+|
|-|-|-|-|
|-|-|0|0|
|0|0|0|0|
|+|0|0|+|
$c_{i+1}$ = CONS($a_i$, $c_i$)

|$s_i$|-|0|+|
|-|-|-|-|
|-|+|-|0|
|0|-|0|+|
|+|0|+|-|
$s_i$ = SUM($a_i$, $c_i$)
因此完整的半加法器邏輯圖表示為

### 電路
Balanced Ternary 加法器可以透過多個3-to-1 Multiplexer 來實現^[5]^
如下圖，Selector 針腳的`-1`, `0`, `1`決定輸出哪一個輸入的電位

首先藉由 Mux，改變Input腳位的值，做出`A+1`及`A-1`, `MIN(A,0)`, `MAX(A,0)`
舉例`A+1`

透過A-1, A, A+1，以B當作Selector腳位，就可以完成SUM(A,B)

MIN(A,0), 0, MAX(A,0)則可以完成CONS(A,B)
.png)
這樣就能實現Balanced Ternary 半加法器，進一步完成全加法器

### Balanced Ternary 好處與壞處
**好處:**
- 相比於 Binary 可以用較少的位數表示相同精度的值
- 處理速度較快 (e.g. ripple-carry adder能用更少的階層計算完)

**壞處:**
- Balanced Ternary 相較於 Binary 的電路設計更為複雜
- 目前的電腦架構幾乎為Binary

---

## Balanced Ternary 的設計要解決什麼類型的問題
老實說目前雖然瀏覽過了這些文章，還是不了解 Balanced Ternary 解決了什麼問題，
利用 Ternary 可以在相同位數內儲存更大的數字，在資料或運算空間需求大的應用上會有用處，例如需要體積小低供耗的 IoT 設備上、金融系統的數字儲存，但應該還有其他因素，形成 Ternary 逐漸受到重視

---

## 測試 Balanced Ternary
[balanced-ternary](https://github.com/sysprog21/balanced-ternary) 程式的功能是將輸入的十進位數字轉換成 Balanced Ternary，並以圖形呈現

方形的4個面及4個角落，各自表示一個 trit，依順時針從正下方開始是最小的 trit，每個 trit 向外的分支表示+，向內表示-

┌───┐  
│   │ = 0
└───┘
┌───┐
┤   │ = 3^2 + 1 = 10
└─┬─┘
┌┬──┐
│   │ = -3^3 = -27
└───┘
├─┴─┤
┤   ├ = 3^7 + 3^6 + 3^5 + 3^4 + 3^3 + 3^2 + 3 + 1 = 3280
├─┬─┤
┌┬┬┬┐
├   ┤ = -3^7 - 3^6 - 3^5 - 3^4 - 3^3 - 3^2 - 3 - 1 = -3280
└┴┴┴┘

此圖形共能表示8 trit，因此能表示的最大數字範圍為:
$\pm\dfrac{(3^8-1)}{2}$ , `-3280`~`3280`
(在此程式中，若輸入超過最大或最小值，則分別以最大或最小值取代)

程式中共有 3 個階段
1. 將輸入的數字轉成 Ternary 的3補數表示
1. 從3補數轉換成 balanced ternary
每一 trit 中
$0_{3's} = 0_{bal3}$
$1_{3's} = 1_{bal3}$
$2_{3's} = 1T_{bal3}$
依照 trit 從小到大依序轉換
1. 根據每個 trit 的 `1`, `0`, `-1`，在相對應的位置輸出向內或向外的分支

---

## Reference

1. [Wikipedia: Ternary numeral system](https://en.wikipedia.org/wiki/Ternary_numeral_system)
1. [Wikipedia: Balanced ternary](https://en.wikipedia.org/wiki/Balanced_ternary)
1. [Fast Ternary Addition](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml)
1. [Standard Ternary Logic](http://homepage.divms.uiowa.edu/~jones/ternary/logic.shtml)
1. [Ternary computing: basics](https://github.com/ssloy/tutorials/wiki/Ternary-computing:-basics)
1. [poyushen HackMD 共筆](https://hackmd.io/s/BkEIqfHob)
1. [Wikipedia: Three-valued logic](https://en.wikipedia.org/wiki/Three-valued_logic)