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

## 作業要求
* [x]解釋 Balanced Ternary 原理
* [x]Balanced Ternary 的設計要解決什麼類型的問題，需要詳述實際應用案例 (如 IOTA/Tangle)。提示：從算術表達的精準度和空間使用效率去探討
* [ ]針對特定的領域 (如加密貨幣)，列出在 GitHub 裡頭可找到的應用案例，不僅列出程式碼，還要解說
* [ ]在研究的過程中，應該會對既有工具進行修改或者重新開發 (不限程式語言)，也該一併指出，程式碼應該維護在 GitHub 上

## Balanced Ternary 定義
Ternary 是以三為基底的進位，使用 0,1,2 三個數表示，而 Balanced Ternary 使用 T(-1),0,1 來表示數值，這樣可以省去使用額外的負號表示負數

* Ternary 的表示法：
* 正數：
| Dec | Ternary |
| -------- | -------- |
||| 0 | 000 |
||| 1 | 001 |
||| 2 | 002 |
||| 3 | 010 |
* 負數：在位數前加負號表示
| Dec | Ternary |
| -------- | --------|
||| -0 | -000 |
||| -1 | -001 |
||| -2 | -002 |
||| -3 | -010 |

由此發現，需要使用額外的負號表示負數

* Balanced Ternary 的表示法:
* 正數：
| Dec | Bal3 | Expansion |
| -------- | -------- | -------- |
||| 0 | 0 | 0 |
||| 1 | 1 | 1 |
||| 2 | 1T | 3-1 |
||| 3 | 10 | 3 |
||| 4 | 11 | 3+1 |
||| 5 | 1TT | 9-3-1 |
||| 6 | 1T0 | 9-3 |
||| 7 | 1T1 | 9-3+1 |
||| 8 | 10T | 9-1 |
||| 9 | 100 | 9 |
||| 10 | 101 | 9+1 |
* 負數：
| Dec | Bal3 | Expansion |
| -------- | -------- | -------- |-------- |
||| 0 | 0 | 0 | 0 | |
||| -1 | T | -1 |
||| -2 | T1 | -3+1 |
||| -3 | T0 | -3 |
||| -4 | TT | -3-1 |
||| -5 | T11 | -9+3+1 |
||| -6 | T10 | -9+3 |
||| -7 | T1T | -9+3-1 |
||| -8 | T01 | -9+1 |
||| -9 | T00 | -9 |
||| -10 | T0T | -9-1 |
由此發現，不需要使用額外的負號表示負數。這使得 balanced ternary 在加減法和乘法方面的效率要比二進位高。

reference: [Ternary numeral system](https://en.wikipedia.org/wiki/Ternary_numeral_system)

## 解釋 Balanced Ternary 原理

### Number Systems: Ternary
* 影片:[Number Systems: Ternary](https://www.youtube.com/watch?v=vOyiHMa-mtQ)
* 影片介紹： 利用除法來進行 ternary 和 10 進位和的轉換
* 影片範例： $45_{10}$
$45/3 = 15 R 0$
$15/3 = 5 R 0$
$5/3 = 1 R 2$
$1/3 = 0 R 1$
乘法驗證
$45 = 1\times3^3 + 2\times3^2+0\times3^1+0\times3^0$

### Non-Binary Computing
* 影片: [Non-Binary Computing](https://www.youtube.com/watch?v=TFTK074nG_M)
* 影片介紹： 談論非二進制計算的歷史，以及創建三元計算機的過程
* 正負數轉換：
Balanced Ternary 是利用-1,0,1來做三進位的運算（下面 T 是代表-1的值）
* T10~B3~=(-1)X3^2^+1X3^1^+0X3^0^=-6~10~
* 1T0~B3~=1X3^2^+(-1)X3^1^+0X3^0^=6~10~

由上方式子可見，6 與 -6 的表示法分別為 T10 和 1T0 ，這兩數的三個位元的值剛好是相反的，而他們的加總和為 0 ，這也表示著 Balanced Ternary 以0為原點平衡的特點。

這是一個 Balanced Ternary 正負數表示法的比較圖，可以清楚看到正數(1)和負數(T)只是符號的差異
reference:[Balanced ternary](https://en.wikipedia.org/wiki/Balanced_ternary)
* 影片中提到的 [Ternary Truth Table：](http://homepage.divms.uiowa.edu/~jones/ternary/logic.shtml) + :True ; - :False ; 0 :unkown
* And or Minimum

* Or or Maximum

* Nand or Antimin

* Nor or Antimax

* Ternary Exclusive Or
* the modulo-3 半加法器:
* Modulo-3 Sum:
注意到T與T相加時會產生一個T的進位 -3+1(sum:1)，而1與1相加時，和會變成T，並產生一個1的進位 3-1(sum:-1)
* Consensus:
如果兩者都為 T 則 T，兩者都為 F 則 F，如果有 0 (unknown) 則 unknown

### Full Adder
* 影片:[Full Adder](https://www.youtube.com/watch?v=v7XxIjv_mUc)
* 影片內容： Seven dual ternary multiplexers may be used to create a full ternary adder (A+B+C=S with C')

三個元素的相加（A+B+C），每種元素有 3 種可能性（-,0,+），因此有27種情況。
### Modulo 3 Sum and Product Functions
* 影片: [Modulo 3 Sum and Product Functions](https://www.youtube.com/watch?v=cgcXoCnyZhQ)
* 影片內容： Continuing the Binary Implemented Ternary Logic Circuits Theme. The Modulo 3 Sum and Product Functions are presented. Also the Squared Function is presented for completeness.

在影片的一開始，說明用 binary 去實作 ternary logic output network，並呈現以下表格
|F|F2|F1|
|-|-|-|
|0|0|0|
|1|0|1|
|2|1|X|
這個表格是在說明，如何把3進位 (0,1,2) 換成2進位，0和1的轉換皆為其本身，而 2 的轉換為 1X，這樣的轉換是可以減少對 F1 的判斷，當判斷 F2 為 1 時，就可以得到此數為 2
### Ripple Adder in Binary and Ternary Logic
* 影片: [Ripple Adder in Binary and Ternary Logic](https://www.youtube.com/watch?v=TfJxAb0owj8)
* 影片內容：6-bit equivalent full ripple adder in standard binary and in ternary or 3-valued logic. Demonstrates the ripple effect and why the ternary ripple adder is faster.

影片中說明在 6-bit 情況下， 31+1 時有二進位的 maximum ripple，4-bit 情況下 26+1 有三進位的 maximum ripple

## Balanced Ternary 的設計要解決什麼類型的問題
### Sign digit

Balanced ternary 相對於 binary 和 ternary 可以節省一個 digit 的空間去紀錄 sign

### Digit 的數值範圍

在相同 digit 中， balanced ternary 可以表示的數值比 binary 可以表示的數值多，像是在 8 個 digit 中，binary 可以表現的數字為 256 個，而 balanced ternary 可以表現的數字則有 6561 個

### IOTA
IOTA是一個開源的分佈式賬戶（cryptocurrency），專注於在物聯網上的機器之間提供安全的通信和支付。使用有向無環圖（DAG）技術代替傳統的區塊鏈，無論交易規模大小，確認時間快，系統可同時處理的交易數量無限，系統可以輕鬆擴展，IOTA的交易都是免費的。IOTA由DavidSønstebø，Sergey Ivancheglo，Dominik Schiener和Serguei Popov博士於2015年創立。

reference: [IOTA_(technology)](https://en.wikipedia.org/wiki/IOTA_(technology))

* IOTA 機制：這個新穎的加密貨幣最主要的特點就是 tangle，以一個有向無環圖 (DAG) 存放交易資訊。

* 通過節點發出的所有交易構成了這個 Tangle（存所有交易的帳本）的集合。
* 這個圖的邊(edge:每筆交易之間的驗證關係)是這樣形成的：`當一個新的交易(vertex:一筆交易)產生，它必須驗證之前的兩個交易，這些驗證關係就通過有向的邊來表示`，如圖 1 所示（在圖中，時間走向總是從左到右）。
* 間接驗證：在交易（vertex） A 到交易（vertex） B 之間沒有直接連接的有向邊，但有至少兩個有向邊的路徑存在，我們就稱交易 A 間接地驗證了交易 B。
* 創世交易 (genesis trasaction)：被所有交易直接或間接驗證，如圖 2。
* 在最一開始有一個地址 (address) 擁有全部的 token，接著創世交易會把金錢轉給其他 founder 的地址。我們強調所有的 token 皆是創世交易所產生的（不會再產生新的 token），而且不會再有「挖礦」就可以收到金錢獎勵的概念了。
圖 1 權重的（重新）計算
圖 2 關於交易的積分計算（帶圓圈的數字）
* 權重：
交易的權重與發送這筆交易的節點所投入的工作量成正比；在實踐中，權重可以假定為 3^n^ 的一些數值，其中 n 屬於有限區間內的正整數。事實上，這與權重是如何增加的並不相干; 重要的是，每一筆交易都有一個正整數的權重。總之，權重愈高該筆交易在 tangle 中也就愈「重要」。我們假設，為了避免各式攻擊，沒有任何角色 (entity) 可以在短時間內產生大量的「可接受」權重的交易。
* 一個交易的累積權重：
它被定義為這個交易的自身權重與其他直接以及間接驗證這個交易的所有交易的自身權重之和。
* 累積權重的計算方法:
如圖 1 所示。其中方框代表交易，方框右下角較小的數位表示這個交易的自身權重，而字體較大且加粗的數字是這筆交易的累積權重。例如，交易 F 經交易 A, B, C, E 直接或者間接被驗證。交易 F 的累積權重就是交易 A, B, C 和 E 的各自自身權重之和，即 9= 3 + 1 + 3 + 1 + 1。
* 在圖 1 中沒有被驗證的交易（即 “tips”）只有交易 A 和交易 C。
* 圖 1 說明，若一個新的交易 X 進入系統並且驗證交易 A 和 C，那麼交易 X 就是系統中唯一的 tip 了，同時系統中其他所有的交易的權重增加 3（即交易 X 的自身權重）。

reference: [IOTA 白皮書](http://www.tangleblog.com/wp-content/uploads/2016/11/IOTA_Whitepaper.pdf)

* Why does IOTA use a ternary number system?

Citing response of the IOTA's Co-founder David,

  Ternary is the optimal radix, actually Base E (2.71....) is, but you can't make processors like that. So it comes down to Base Binary (2) vs Base Ternary (3). 3 is closer to the universal optimum 2.71 than is 2. That is the absolute most simple elevator pitch for ternary.

  There are plenty of great articles on this, if you find computer science fascinating. The one already posted is a good high level historic overview. For a more math intensive one you can check out this article or if you are really into computer science you should check out this video, it goes from fundamentals of logic to hardware and software engineering in a binary vs ternary context. To be sure, we use balanced ternary +1 0 -1 or as we prefer + 0 -
 
  The benefits of ternary go beyond mere computational performance in a parochial 1:1 comparison versus binary. Another area where ternary shines is Artificial Neural Networks, Artifical Neurons and Artificial Intelligence Logic. In fact this is actually how our brain also computes. Other areas where ternary shines is in graphical processing, cryptography and search, among other things.

  A last point I want to raise regarding ternary is that it almost inevitably is the future of computing. Spintronics got 3 values natively: Spin Up, Down and No Spin. Same goes for Photonics/Optical Computing; use the two orthogonal polarizations of light to represent + and - and lack of light/darkness as 0.

  To clarify we are not doing ternary for the sake of doing ternary/something exotic. Ternary is simply the superior technological solution. Nor are we attempting to replace the cemented legacy of Intel and AMD in the desktop realm or ARM, Synopsys etc. in the current mobile market. Our processors are a new kind of processing unit for the new realm of computation in new fields such as IoT, AI, Massively Distributed Computing etc.

提到 Ternary is the optimal radix ， radix economy 是三進位的一個好處。
* radix economy: 同一個 N 時，所需要的 E 越小，則其表現越好
* 公式： $E（b,N）=b ⌊ log b ⁡ ( N ) + 1 ⌋$
* b為數字基底
* N為被運算的目標數字
* 以轉換100為例

| |decimal | binary | ternary |
| :--------: | :--------: | :--------: | :--------:|
| b: base | 10 | 2 | 3 |
| N | 100 | 100 | 100 |
| E（b,N） | $10\times3$ | $2\times7$|$3\times5$|
從此表格中，可以發現同樣是 100 ，10 進位會需要 30 個 bits 來儲存，3 進位需要 15 個 bits ，而 2 進位只需要 14 個 bits
* 不同 N 範圍的平均 E（b,N）表格

* 在這我們可以計算為什麼 "e has the lowest radix economy"
* $E(b,N)$ 趨近於 ${b\ {\log _{b}(N)}}={b{\ln(N) \over \ln(b)}}$
* ln(N) 為變數，我們將尋求 ${b \over \ln(b)}$ 的最小值
* 最後得到 ${e \over \ln(e)}$ 有 minimum

reference: [Radix_economy](https://en.wikipedia.org/wiki/Radix_economy)

reference: [IOTA_Whitepaper](http://www.tangleblog.com/wp-content/uploads/2016/11/IOTA_Whitepaper.pdf)

## 列出在 GitHub 裡頭可找到的應用案例
### Kerl
* IOTA is adding an additional hashing function, based on Keccak, with conversion to ternary.
* code:

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
        }

可以看出 Kerl 使用 balanced ternary

* Kerl is used in IOTA for the following

| Functionality |Curl-P-27 | Curl-P-81 | Kerl |
| ------------- |:--------:|:--------:| :-----:|
|Address generation | | | V^ |
|Signature generation| | | V |
|Signature verification| | | V |
|Essence calculation (bundleHash)| | | V |
|Proof of Work | | V | |
|Transaction Hash | | V | |
|Milestone verification| V | | |

* Curl-P-N: N number of rounds
* ^ CheckSums are calculated using the last 9 trytes.

* Kerl implementation:
Kerl implements the same interface as Curl: Trits are absorbed by the sponge function. And later squeezed to provide message digest, derive keys etc.

reference: [Kerl](https://github.com/iotaledger/kerl)