# 2017q3 Homework1 (ternary)
contributed by <`jeff60907`>
###### tags: `jeff60907`
## 作業要求
[C01: Ternary](https://hackmd.io/s/Sym0UAk9Z)
研讀 Balanced Ternary，並依據 課前測驗參考解答: Q1 的風格和探討方式，涵蓋以下:
* 解釋 Balanced Ternary 原理;
* Balanced Ternary 的設計要解決什麼類型的問題，需要詳述實際應用案例 (如 IOTA/Tangle)。提示：從算術表達的精準度和空間使用效率去探討;
* 針對特定的領域 (如加密貨幣)，列出在 GitHub 裡頭可找到的應用案例，不僅列出程式碼，還要解說;
* 在研究的過程中，應該會對既有工具進行修改或者重新開發 (不限程式語言)，也該一併指出，程式碼應該維護在 GitHub 上;

[Latex 參照來源](https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference)

## Balanced ternary
[閱讀Fast Ternary Addition](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml)理解 base-3 的原理

Balanced Ternary 是一個屬於(base 3)的數值系統，他的值為 `-1, 0, +1` 不需要額外的符號位元表示正負即可代表整數系，而在 standard unsigned (unbalanced) ternary 中表達方式為 `0, 1 , 2`，Balanced Ternary 的邏輯電路實現相較於一般的 unsigned ternary 更為複雜。在內文提到 base-b 的 single digit 為 $log_2b$ bits 的訊息量，在 ternary number system 中存放的訊息量為 $log_23$ 是二進制的 1.58 倍，十進制的 3.32倍

在 Kleene邏輯中，Ternary 被分為三種 true , false , unknown，真值表的內容為以下

|truth value|unsigned|balanced|
| -------- | -------- | -------- |
|false(F)| 0 | - |
|unknown(U)| 1 | 0 |
|true(T) | 2 | + |

使用 Bal3 表示 -3 ~ +3
`-3` , `-2` , `-1` , `0` , `1` , `2` , `3`
`0-0`,`0-+`,`00-`,`000`,`00+`,`0+-`,`0+0`

### Balanced Ternary 數值轉換 (bal3 / dec)
[參考 Balanced ternary wikipedia](https://en.wikipedia.org/wiki/Balanced_ternary)
數值的轉換與過去所學二進制/十進制的概念相同，其中`-1, 0, +1` 代表`T, 0, 1` 也代表是`false , unknown , true`，若數值 1-T = 1T，(3^1^-1)，反之 T1 ((-1)x3^1^+1)

dec 與 bal3轉換

$10_{bal3} = 1 \times 3 ^ 1 + 0 \times 3 ^ 0 = 3_{dec}$
$10T_{bal3} = 1 \times 3 ^ 2 + 0 \times 3 ^ 1 + (-1) \times 3 ^ 0 = 8_{dec}$
$-9_{dec} = (-1) \times 3 ^ 2 + 0 \times 3 ^ 1 + 0 \times 3 ^ 0 = T00_{bal3}$
$T0T0_{bal3} = (-1) \times 3 ^ 3 + 0 \times 3 ^ 2 + (-1) \times 3 ^ 1 + 0 \times 3 ^ 0 = -30_{dec}$

浮點數的運算

$1.\overline{T11T}_{bal3} = 1 \times 3 ^ 0 + (-1) \times 3 ^ {-1} + 1 \times 3 ^ {-2} + 1 \times 3 ^ {-3} + (-1) \times 3 ^ {-4} = 0.8_{dec}$
$0.2_{dec} = 1 \times 3 ^ {-1} + (-1) \times 3 ^{-2} + (-1) \times 3 ^{-3} + 1 \times 3 ^ {-4} = 0.\overline{1TT1}_{bal3}$

### Balanced Ternary 四則運算

Addition
| + | T | 0 | 1 |
| -- | -- | -- | --|
|T |T1 |T |0|
|0 |T |0 |1|
|1 |0 |1 |1T|

Subtraction
| − | T | 0 | 1 |
| -- | -- | -- | --|
| T | 0 |T | T1
| 0 | 1 |0 | T
| 1 | 1T |1 | 0

Multiplication
| x | T | 0 | 1 |
| -- | -- | -- | --|
| T | 1 | 0 | T
| 0 | 0 | 0 | 0
| 1 | T | 0 | 1

Division
| ÷ | T | 0 | 1 |
| -- | -- | -- | --|
|T | 1 | NaN | T
|0 | 0 | NaN | 0
|1 | T | NaN | 1

### 了解一些 Balanced Ternary Logic Functions
[參考Ternary-computing:-basics](https://github.com/ssloy/tutorials/wiki/Ternary-computing:-basics)
使用 ternary multiplexer 進行邏輯電路
當multiplexer sel 輸入依序為-1,0,1時，output為 inN, inO, inP
當multiplexer sel 輸入依序為-1,0,1時，input 0, 1, -1，對照 output為 0, 1, -1，可當成 (A+1)
當multiplexer sel 輸入依序為-1,0,1時，input 1, -1, 0，對照 output為 1, -1, 0，可當成 (A-1)
當multiplexer sel 輸入依序為-1,0,1時，input 0, 0, 1，對照 output為 0, 0, 1，可當成 max(A,0)
當multiplexer sel 輸入依序為-1,0,1時，input -1, 0, 0，對照 output為 -1, 0, 0，可當成 min(A,0)

* 使用基本邏輯單元進行 半加器 half-adder A+B
A + B 的結果
B=-1 選擇輸出為 A-1，等於A+(-1)=A-1
B=0 選擇輸出為 A，等於A+(0) = A
B=1 選擇輸出為 A+1，等於A+(1) = A+1

* consensus function consensus
如果 A,B=-1 輸出 -1, A,B=1 輸出 1，其他皆為 0
A=-1 min(A,0)=-1 , A=1 max(A,0)=1 ,otherwise = 0
當 B =-1, A=-1時 , 輸出為-1
當 B =1, A=1時, 輸出為1