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

> 筆誤! 正確書寫方式為 ==balanced== ternary ，注意到 balance 後面接著 "d" 字母
> [name="jserv"][color=red]

## Ternary (三進位)
Ternary 如同我們熟悉的 10 進位、2 進位方式，它是一種以 3 為基數 (3-base,($x\times 3^0 + x\times 3^1 + x\times 3^2$...)) 的進位，逄 3 進位，以 ==0,1,2== 為表示的進位方式
其表示如下:

| Dec | Ternary |
| -------- | -------- |
| 0 | 000 |
| 1 | 001 |
| 2 | 002 |
| 3 | 010 |
| 4 | 011 |
| 5 | 012 |
| 6 | 020 |
| 7 | 021 |
| 8 | 022 |
| 9 | 100 |

而其負數型態則是在位數前加一負號表示
其表示如下:
| Dec | Ternary |
| -------- | --------|
| -0 | -000 |
| -1 | -001 |
| -2 | -002 |
| -3 | -010 |

可以發現 ternary 在負數表示上仍需要多一位元做為負數型態的表示

接下來我們將介紹來自蘇聯的黑科技 Balance ternary
>英文、數字與中文字間請以空白隔開
>[name=課程助教][color=red]

----

# Balanced ternary (平衡三進位)

對於 balanced ternary 最令人難忘的描述是來自 Donald Knuth 於其著作 The Art of Programming 中的一段:

> Perhaps the prettiest number system of all... is the balanced ternary notation.

相較 Ternary 以 0,1,2 表示不同的地方在於 Ternary以-1(以下用==T==表示）,==0==,==1==為基本數位(trit)的表示。
(==Balanced ternary在下面將縮寫Bal3做表示==)

| 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 |

### Balanced ternary 的負數表示

Balanced trinary 最令人讚嘆的地方之一在於其負數表示及運算，其負數型態可以將原本正值的地方用-1(T)直接取代，即可得到負數型態(如$2_{Dec}$=$1T_{Bal3}$ ,而$-2_{Dec}$ =$T1_{Bal3}$)，==這種進位不需要額外的符號就能直接表示負數==。使得 balanced ternary 在加減法和乘法方面的效率要比二進位高。

| Dec | Bal3 | Dec | Bal3 |
| -------- | -------- | -------- |-------- |
| 0 | 0 | 0 | 0 | |
| -1 | T | 1 | 1 |
| -2 | T1 | 2 | 1T |
| -3 | T0 | 3 | 10 |
| -4 | TT | 4 | 11 |
| -5 | T11 | 5 | 1TT |
| -6 | T10 | 6 | 1T0 |
| -7 | T1T | 7 | 1T1 |
| -8 | T01 | 8 | 10T |
| -9 | T00 | 9 | 100 |
| -10 | T0T | 10 | 101 |

其轉換公式表示如下:
($a_n$$a_{n−1}$...$a_2$$a_1$.$c_1$$c_2$$c_3$...$)_{b}$=$\sum_{k=1}^{n}$$a_k$$b^k$+$\sum_{k=1}^\infty$$c_k$$b^{-k}$

==b is the original radix. b is 10 if converting from decimal.==
> <s>EX</s>:
e.g.
>> example 的縮寫是 `e.g.`，而非 "ex"，後者是「前」女友、「前」雇主用語，不要誤用
>> [name="jserv"][color=red]

>
> $−25.4_{dec}$
> $= −(1T×101^1 + 1TT×101^0 + 11×101^{−1})$
> $= −(1T×101 + 1TT + 11÷101)$ ==->參考Bal3的四則運算==
> $= −10T1.\overline{11TT}$
> $= T01T.\overline{TT11}$

----

### Balance ternary 的四則運算

而 Balance 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
|× |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|

我們舉一簡單的例子:
$0.5_{dec}=0.\overline 1_{bal3}$ or $1.\overline T_{bal3}$

1).

0.111111111…
-----------------
1T )1
1T
-----
10
1T
---
10
.
.
......(LOOP)

故我們可得 $0.5_{dec}=0.\overline 1_{bal3}$

2).

1.TTTTTTTTT…
-----------------
1T )1
1T
-----
T0
T1
---
T0
.
.
......(LOOP)

我們可得到 0.5 可表示為 $0.5_{dec} = 1.\overline T_{bal3}$

----
### Balance ternary 的邏輯運算及加法器

#### Min / AND
當兩個輸入都為+時則輸出為+,若任何輸入為-或0(unknown)時則否;同時此運算可看作為最小值輸出
[圖片來源](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml)

#### Max / OR

當兩個輸入其中有一者為+時則輸出為+,若兩個輸入皆為-或0(unknown)時則否;同時此運算可看作為最大值輸出
[圖片來源](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml)
#### Exclusive OR / XOR
若輸入相同則為+,否則輸出為-(若輸入為0/unknown則輸出0)
[圖片來源](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml)

#### Sum
如同布林運算中用XOR計算二個二進位值的和;但在些和XOR不同處在於其輸入有0(unknown)時的狀態
[圖片來源](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml)

#### Consensus
當輸入狀態一致時則輸出輸入狀態值,否則輸出0(unknown)
[圖片來源](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml)

#### Accept Anything
當輸入一端為+/-另一端為0時則輸出對應輸入值的+/-,若輸入相同時則輸出同輸入值;而當輸入兩端一端+一端-時則輸出0(unknown)
[圖片來源](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml)

有了上述幾組balanced ternary的運算後我們開始可以組合出半加器及全加器

#### Balanced ternary half adder
很類似在布林運算中看的到半加器, 和為$s_i$=$c_i$+ $a_i$ , 進位值為$c_{i+1}$ = ( $a_i$ ⊠ $c_i$ )
半加器真值表如下:
[圖片來源](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml)
#### Balanced Full Adder
全加器二個半加器組合而成,最後再用一個Accept anything做進位值輸出
全加器真值表如下:
如同布林運算一般,完成全加器後可以組全成 4 trit ripple-carry adder

[圖片來源](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml)

----

# 思考問題:

Balance trinary看起來在空間利用率(==參考[HTYISABUG同學共筆](https://hackmd.io/s/B1OGeR7s-)中所提及的Radix Economy==)及運算的靈活性，但...如何在目前電腦架構中用logic gate實作High, low, NaN出來呢?
>> 出處呢？ [name="jserv"][color=red]
>
> 參考["Suggestions for Ternary Computer Parts"](https://electronics.stackexchange.com/questions/116502/suggestions-for-ternary-computer-parts),我們可以得知如何以MOS組成出基本的 ternary logic gate , 我們列出 NAND 及 NOR Gate 如下:
>
> **A Ternary NOR
> Truth Table:**
>
> |A|B|out|
> |-|-|-|
> |0|+|-|
> |0|-|+|
> |+|-|0|
> |+|+|-|
> |-|-|+|
> 
>
> **A Ternary NAND
> Truth Table:**
>
> |A|B|out|
> |-|-|-|
> |0|+|0|
> |0|-|0|
> |+|-|0|
> |-|-|+|
> |+|+|-|
> 
>[name=Bruce Ke]

----

在[wikipedia](https://zh.wikipedia.org/wiki/%E5%B9%B3%E8%A1%A1%E4%B8%89%E8%BF%9B%E5%88%B6)中有關"三進位電腦中資訊的表示"有下面這一段描述:

> 三進位電腦中，以平衡三進位為資訊進行編碼。
我們可以以12位元為單位，對文字進行編碼作為標準資訊交換碼（STUCII，Standard Ternary Unified Code for Information Interchange）。其容量為53'1441個字元，約是16bits容量的8.1倍。
>> 如何計算出來呢？請用繁體中文和台灣慣用術語書寫 [name="jserv"][color=red]
>>
>$比較二進位及平衡三進位之資料編碼容量, 3^{12}/2^{16}=8.11..., 即為文中提及的8.1倍$ [name=Bruce Ke]

----

針對上面幾個問題, 在網路上其實己經有不少答案及教學, 我將內容摘要並附上連結如下:

1).
有解說Balanced ternary的基本原理 , 其中有及 Ternary 在當時為何被開發出來(==相較二進位元, 同樣的位元數,三進位可表示的範圍較廣==)及它當能在真空管時代所佔的優勢! 及到了電晶體時代, 這種電腦為何又被淘汰(==電晶體相較真空管穩定且在半導體製程上實現及微縮==)
> 由於網路上找不太到有關真空管應用在ternary上的文獻,故我整理我的推論如下:
> 1. Balanced ternary 較 binary 在設計上以相同邏輯運算,能以相同的真空管數完成較多的位元運算([Suggestions for Ternary Computer Parts](https://electronics.stackexchange.com/questions/116502/suggestions-for-ternary-computer-parts)) ,故在真空管的時代三進制計算機能有較低的耗能及較快的運算能力。
>
> 2. 此時有另一個問題,為什麼這樣低的耗能及較快的運算能力的 ternary 為何沒被用在電晶體,整理幾個可能如下:
> * 在 MOS 上要實現 3種電壓 level 狀態 由於 drain 極上需再串電阻分壓而造成靜態功耗額外的能耗, 且因為輸出電阻不再接近0,fin-out能力下降
>
> * 由於 ternary 需要3種電壓 level 做為位元狀態, 會造成雜訊容忍度下降( threshold level 範圍更窄)
>
> * 抗共模雜訊能力較差
>
> * 資料,介面,指令集集需重新編制( binary 轉 ternary ), 由於目前計算機普遍由binary資料組成, 這轉換將會是最大障礙
>
> * IC layout 佈局由於需多一組電壓,會造成layout難度上昇及電晶體空間密度下降

[參考來源](https://www.zhihu.com/question/35937929/answer/110629363)

<iframe width="854" height="480" src="https://www.youtube.com/embed/TFTK074nG_M" frameborder="0" allowfullscreen></iframe>

2).
在這部影片中更清楚的可以看到在, 在表達一 6-bit equivalent full ripple adder 時， Balanced Ternary 如何以==較少的位元表示及較短邏輯運算時間完成同樣的算數運算==!

<iframe width="854" height="480" src="https://www.youtube.com/embed/TfJxAb0owj8" frameborder="0" allowfullscreen></iframe>

----
# 作業問題:

- [x] Balanced Ternary 的設計要解決什麼類型的問題，需要詳述實際應用案例 (如 IOTA/Tangle)。
提示：從算術表達的精準度和空間使用效率去探討;

總結上述 Balanced ternary 的優點, 我們可歸結出下面幾點

### 1.用較少的位數表示較大的數值範圍

由IOTA的介紹,我們可以知道, Balanced ternary 在相同位元下, 能較 binary 表示的範圍大, 以IOTA來說, 如要表示其發行貨幣量, ==在 Balanced ternary 僅需33位元, 但以 binary 表示則需要高達52位元==,大大的節省了儲存空間的位元量.
> 它目前的主要功能是 無需手續費的微支付 和 安全的資料轉移以及資料錨定 ，具有良好的擴充套件性和分割槽容錯特性。其總供應量約為 2780萬億 個（確切數字是（3 ^ 33-1）/ 2 =2,779,530,283,277,761個），並且都是在初始塊建立的，沒有挖礦新增的幣。因為其供應量如此之大，單個的價格非常小，所以交易都是以百萬IOTA為單位的，即 MIOTA 原文網址：https://itw01.com/38CESJ6.html

### 2.正負號表示僅需交換位元中的正負(1->T,T->1),無需多一位元做有號數表示

若我們想把一個 Ternary 數值作正負號的轉換，只需==交換每個位元中的正負(1->T,T->1)==，如同做一個 NOT 的邏輯運算，而我們也可以很容易的由數值的最高有效位知道它的正負號，所以可以==節省一個位元的空間去表示==

|**Dec.**| 1 | -1 | 2 | -2 |
|--------| ---| --- | ---| --- |
|**Bal3**| 1 | T | T1 | 1T |

### 3.運算速度較快

Balanced Ternary 除了減法運算只需對減數做 Not 後相加, 在運算上較 binary 快速外; 以下圖的 ripple adder 可看出，在相同的運算值在 6 bit 的 binary ripple adder 運算, 而 3-valued ripple adder 在運算上較快上許多; 在IOTA的交易驗證上, 我想運算時間也是個被重視的重點


### 浮點數表示較 Binary 的 IEEE754 精確
以32位元的浮點數表示, 在 IEEE754 中表示準度的位元為23bits ($2^{23}$), 而若以相同位數在 Balanced ternary 表示精度則為 $3^{23}$ , 相比之下二者精度差了11222倍. 再者 Balanced ternary 因表示式而不會產生單精數運算時因指數過大(e.g. 1e20 * (1e20 - 1e20) 為 0.0),而造成運算精度被忽略的問題, 這點我想也是在加密貨幣中, blanced ternary 被委以重任的原因之一


- [ ] 待辦針對特定的領域 (如加密貨幣)，列出在 GitHub 裡頭可找到的應用案例，不僅列出程式碼，還要解說;
- [ ] 待辦在研究的過程中，應該會對既有工具進行修改或者重新開發 (不限程式語言)，也該一併指出，程式碼應該維護在 GitHub 上;

----

# 參考專案與文獻
* [平衡三進制 (wikipedia)](https://zh.wikipedia.org/wiki/%E5%B9%B3%E8%A1%A1%E4%B8%89%E8%BF%9B%E5%88%B6)
* [Balanced ternary (wikipedia)](https://en.wikipedia.org/wiki/Balanced_ternary)
* [三生萬物 (數學文化)](http://www.global-sci.org/mc/issues/5/no4/freepdf/79s.pdf )
* [HTYISABUG同學共筆](https://hackmd.io/s/B1OGeR7s-)
* [Ternary simulator](http://trinary.ru/)
* [The Balanced Ternary Machines of Soviet Russia](https://dev.to/buntine/the-balanced-ternary-machines-of-soviet-russia)
* [Tangle 白皮書](https://hackmd.io/c/rkpoORY4W/https%3A%2F%2Fhackmd.io%2Fs%2FB1YKzhbLb%23)
* [Suggestions for Ternary Computer Parts](https://electronics.stackexchange.com/questions/116502/suggestions-for-ternary-computer-parts)
* [苏联三进制计算机Сетунь到底是怎样一个计算机](https://www.zhihu.com/question/35937929)
* [化学计算、湿件计算、流体计算和三元计算](http://oicwx.com/detail/221560)
* [[Ternac (wikipedia)]](https://en.wikipedia.org/wiki/Ternac)