2017q3 Homework1 (ternary) === contributed by <`Lihikoka`> # Balanced Ternary (平衡三進位) 介紹 Balanced ternary 是一種三進位 (Ternary) 的數值表示法，在三進位中，一個十進位的數 $n$ 可以表示為 $n=\sum\limits_na\cdot3^n, a = 0, 1, 2$ ，但 balanced ternary 與一般 ternary 不同的是 $a = T(-1), 0, 1$ ，其整數與分數的表示法都跟二進位一樣，但是在表示一個數的負數時較二進位方便。詳見以下： * 二進位： $(6)_{10} = (0110)_2$ $(-6)_{10} = (1010)_2$ * 平衡三進位： $(6)_{10} = (1T0)_{bal3} = 1 \cdot 3^2 + (-1) \cdot 3^1 + 0$ $(-6)_{10} = (T10)_{bal3} = (-1) \cdot 3^2 + (1) \cdot 3^1 + 0$ 由以上可知在 balanced ternary 中要取一個數的負數只要將全部的位元乘以 $-1$ 即可，比二進位的負數操作快速、簡單。 ## 運算真值表 以下使用 - 代表 $T$ ，+ 代表 1 ，看起來較直覺。 * Inverter | in | out | |:--:|:---:| | **-** | + | | **0** | 0 | | **+** | - | * Min or And $c = (a$ ∧ $b) = min(a, b)$ | c | - | 0 | + | |:-----:|:-:|:-:|:-:| | **-** | - | - | - | | **0** | - | 0 | 0 | | **+** | - | 0 | + | * Max or Or $c = (a$ ∨ $b) = max(a, b)$ | c | - | 0 | + | |:-:|:-:|:-:|:-:| | **-** | - | 0 | + | | **0** | 0 | 0 | + | | **+** | + | + | + | # Hardware Implementation * 最基本的 building block： ternary multiplexer ![ternary multiplexer](https://raw.githubusercontent.com/ssloy/tutorials/master/ternary/doc/A%2B1.png) ## Unary functions * Increment ![Ternary increment](https://raw.githubusercontent.com/ssloy/tutorials/master/ternary/doc/A%2B1.png) * Decrement ![Ternary decrement](https://raw.githubusercontent.com/ssloy/tutorials/master/ternary/doc/A-1.png) * max(A, 0) ![Ternary max](https://raw.githubusercontent.com/ssloy/tutorials/master/ternary/doc/max(A%2C0).png) * min(A, 0) ![Ternary min](https://raw.githubusercontent.com/ssloy/tutorials/master/ternary/doc/min(A%2C0).png) ## 加法器 終於要進入最重要的加法器了，關於二進位 half adder 和 full adder 的部份可參考 [Wikipedia](https://en.wikipedia.org/wiki/Adder_(electronics)#Half_adder)。 ### Half adder 在建構 half adder 之前，我們首先需要寫出 `sum` 和 `carry` 的 truth table，再使用 basic building block (ternary multiplexer) 做出我們要的電路。 * Sum Truth table 很直覺，跟二進位較不同的地方為 `A = -1, B = -1` 以及 `A = 1, B = 1` 的地方。 ![Ternary half adder sum](https://raw.githubusercontent.com/ssloy/tutorials/master/ternary/doc/A%2BB.png) * Carry 可用 Consensus 來實現，中文為「共識」的意思，也就是只有在兩個輸入都是 `-1` 或 `+1` 時輸出才不為 0 ，其他的輸入值組合輸出都是 0，正好符合 carry 的性質：「沒進位時為 0 ，須進位時為高一位的值」。 ![Ternary consensus](https://raw.githubusercontent.com/ssloy/tutorials/master/ternary/doc/cons(A%2CB).png) ### Full adder 做出 half adder 之後，接下來當然要往 full adder 作延伸 * Sum 圖中綠色範圍框起來的是 half adder 的 sum。 ![Ternary full adder sum](https://raw.githubusercontent.com/ssloy/tutorials/master/ternary/doc/A%2BB%2BCin.png) * Carry 圖中綠色範圍框起來的是 consensus。 ![Ternary full adder carry](https://raw.githubusercontent.com/ssloy/tutorials/master/ternary/doc/overflow.png) # 應用案例 ## IOTA / Tangle * 加密貨幣之爭 Blockchain v.s. Tangle | | Blockchain | Tangle | |:--------:|:----------:|:------:| | Miners | O | X | | Fees | O | X | | Blocks | O | X | | Hard/Soft Fork | O | X | | Distributed Consensus | O | O | | HashCash | O | O | * Tangle 的優勢 Scalability Quantum Security Offline Capability * Tangle # Reference [The Ternary Manifesto](http://homepage.divms.uiowa.edu/~jones/ternary/) [Ternary-computing: basics](https://github.com/ssloy/tutorials/wiki/Ternary-computing:-basics) [IOTA BREAKDOWN: The Tangle Vs. Blockchain Explained](https://www.youtube.com/watch?v=I_jNH9BlEEo)