# 2017q3 Homework1 (ternary)
contributed by <`HMKRL`>
---
>**TODO**:
>* 為甚麼 IOTA seed 是 81 characters?
>* IOTA 為甚麼使用 tryte?
>[color=red]
## 解釋 Balanced Ternary 原理
- [x] 解釋 Balanced Ternary 原理
Balanced ternary 是一種數值表示系統,每個位數可以有三種狀態:
- `-`
- `0`
- `+`
將 $n$ 位 Balanced Ternary 數值 $T$ 轉為 Base10 的方法如下 (`T[0]` is the least significant digit):
$$
\sum_{i=0}^n T[i]\times3^i
$$
考慮以下 Ternary 加法運算真值表:
| sum| +| 0| -|
|:--:|:--:|:--:|:--:|
| +| -| +| 0|
| 0| +| 0| -|
| -| 0| -| +|
|carry| +| 0| -|
|:---:|:--:|:--:|:--:|
| +| +| 0| 0|
| 0| 0| 0| 0|
| -| 0| 0| -|
參考 [Fast Ternary Addition](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml), Balanced ternary 加法運算可以透過以下半加器實作:
![](https://i.imgur.com/HBRdtRk.png)
$$
s_i=(a_i+c_i)\\
c_{i+1}=cons(a_i,c_i)
$$
其中 $cons(a,b)$ 為 [Ternary Logic](http://homepage.divms.uiowa.edu/~jones/ternary/logic.shtml) 的一種邏輯運算子,其真值表如下
| cons| +| 0| -|
|:---:|:--:|:--:|:--:|
| +| +| 0| 0|
| 0| 0| 0| 0|
| -| 0| 0| -|
再以此為基礎完成全加器:
![](https://i.imgur.com/aOkXeDy.png)
其中 ANY 為 另一種邏輯運算子,其真值表如下
| cons| +| 0| -|
|:---:|:--:|:--:|:--:|
| +| +| +| 0|
| 0| +| 0| -|
| -| 0| -| -|
---
## Balanced Ternary 的設計要解決的問題類型
考慮 4 bit unsigned integer 能表達的數值範圍:
binary: 0 ~ 15 共 $2^4$ 個不同數值
ternary: 0 ~ 80 共 $3^4$ 個不同數值
由於每個位元能儲存的資料量較多,因此 ternary 系統本身能儲存的資料量較多
此時再考慮 4 bit signed integer, 比較 ternary 及 balanced ternary 的差異:
ternary: -27 ~ 26 共 54 個不同數值
balanced ternary: -40 ~ 40 共 81 個不同數值
可以發現在考慮正負的情況下,比起 balanced ternary, ternary 系統僅能提供 $\frac{2}{3}$ 的數值範圍,原因是表示正負號必須佔用一位,但正負僅有兩種狀態,因此一部份空間無法使用
在使用 balanced ternary 時,每個位元儲存各自的正負資料,可以帶來兩個優點:
1. 方便運算: 不需額外處理正負,直接取 not 即可完成變號:
$$
39_{10}=+++0_{bt}\\
-39_{10}=---0_{bt}
$$
2. 節省空間,增加儲存密度
現代硬體採用"開"與"關"兩種狀態代表 `0` 與 `1`
但若能製造一種硬體能儲存 `+` `-` `0` 三種狀態(猜想:利用電壓具有正負或磁極做儲存),即能更有效率的利用空間
---
## 在 GitHub 裡頭可找到的應用案例
在 [iotaledger](https://github.com/iotaledger)/[kerl](https://github.com/iotaledger/kerl) 專案的說明中敘述:
```
IOTA Kerl:
IOTA is adding an additional hashing function, based on Keccak, with conversion to ternary.
The following document describes the functionality and specification to be implemented.
```
觀察[此段程式碼](https://github.com/iotaledger/kerl/blob/7ca94d3e8bc7b8223fe10e25c853b01273735968/python3/conv.py#L7)
```
tryte_table = {
'9': [ 0, 0, 0], # 0
'A': [ 1, 0, 0], # 1
'B': [-1, 1, 0], # 2
'C': [ 0, 1, 0], # 3
'D': [ 1, 1, 0], # 4
'E': [-1, -1, 1], # 5
'F': [ 0, -1, 1], # 6
'G': [ 1, -1, 1], # 7
'H': [-1, 0, 1], # 8
'I': [ 0, 0, 1], # 9
'J': [ 1, 0, 1], # 10
'K': [-1, 1, 1], # 11
'L': [ 0, 1, 1], # 12
'M': [ 1, 1, 1], # 13
'N': [-1, -1, -1], # -13
'O': [ 0, -1, -1], # -12
'P': [ 1, -1, -1], # -11
'Q': [-1, 0, -1], # -10
'R': [ 0, 0, -1], # -9
'S': [ 1, 0, -1], # -8
'T': [-1, 1, -1], # -7
'U': [ 0, 1, -1], # -6
'V': [ 1, 1, -1], # -5
'W': [-1, -1, 0], # -4
'X': [ 0, -1, 0], # -3
'Y': [ 1, -1, 0], # -2
'Z': [-1, 0, 0], # -1
}
```
可以發現採用 3-bit balanced ternary 來表示 hash 結果
參考 [Creating a new Seed / Wallet](https://iotasupport.com/gui-newseed.shtml)
`A - Z` + `9` 就是組成 `seed` 的字元
而 `convertBaseToBigint(array, base)` 則用於計算一開始提到轉換為十進位的方法:
```
def convertBaseToBigint(array, base):
bigint = 0
for i in range(len(array)):
bigint += array[i] * (base ** i)
return bigint
```