# 2017q3 Homework1 (ternary)
contributed by <`yusihlin`>
### Reviewed by `tina0405`
* 在介紹真值表，和電路實現上很清楚，只可惜缺乏實際應用的案例和對針對程式碼需求的修改
## Balanced Ternary 介紹

三位元數值系統由三種符號組成，直觀上會以 0,1,2 來表示三進制，然而 Balanced Ternary 以 -1,0,+1 三種符號代表，由於 -1 的存在不需多餘的符號即可表示負數。

### **數值轉換**

*（-1 記為 T）*

$\begin{split}193_{dec} &= 1\times2^7 + 1\times2^6 + 0\times2^5 + 0\times2^4 + 0\times2^3 + 0\times2^2 + 0\times2^1 + 1\times2^0 = 11000001_{2}\\
&= 2\times3^4 + 1\times3^3 + 0\times3^2 + 1\times3^1 + 1\times3^0 = 21011_{3}\\
&= 1\times3^5 + (-1)\times3^4 + 1\times3^3 + 0\times3^2 + 1\times3^1 + 1\times3^0 = 1T1011_{bal3}\end{split}$

* 透過觀察可知使用 2 進位表示 193 這個數字需要 8 個位元，而使用 Balanced Ternary 只需要 6 個位元，至於 $21011_{3}$ 到 $1T1011_{bal3}$ 的轉換可以參考 [zhanyangch](https://hackmd.io/s/SyEBnPzsW) 同學的共筆，根據 $2\times3^k = (3-1)\times3^k = 1\times3^{k+1} + (-1)\times3^k$ 我們可以用**1T表示2**(同理可用T1表示 -2)，在 [wikipedia](https://en.wikipedia.org/wiki/Balanced_ternary) 中對 Balanced Ternary 的介紹還有一種方法是先 +1 並允許進位，接著再 -1 不允許借位，本來範圍由 0,1,2 平移到 -1,0,1 ，以下為說明：
$21011_{3} + 11111_{3} = 102122_{3}\\
102122_{3} - 11111_{3} = 1T1011_{bal3}$

$-193_{dec} = (-1)\times3^5 + 1\times3^4 + (-1)\times3^3 + 0\times3^2 + (-1)\times3^1 + (-1)\times3^0 = T1T0TT_{bal3}$

* 由正負數的比較可以看出差別只在 +1 和 -1 的對換，優點是不用像二進位需透過補數來表示負數。

### **運算**

* 邏輯概念：如果 Ternary 的3個邏輯概念為 true, unknown, false ，則會有以下關係

|Balanced|Logic |Unsigned|
|:------:|:-----:|:------:|
|T |False |0 |
|0 |Unknown|1 |
|1 |True |2 |

* 邏輯 NOT, AND, OR, XOR
* NOT
|$a$|$\bar a$|
|:-:|:------:|
|T |1 |
|0 |0 |
|1 |T |
* Min or AND
|c |T|0|1|
|:---:|-|-|-|
|**T**|T|T|T|
|**0**|T|0|0|
|**1**|T|0|1|
$c\ =\ (a \wedge b)\ =\ min(a,b)$
* Max or OR
|c |T|0|1|
|:---:|-|-|-|
|**T**|T|0|1|
|**0**|0|0|1|
|**1**|1|1|1|
$c\ =\ (a \vee b)\ =\ max(a,b)$
:::info
$(a \vee b)\ =\ -(-a \wedge -b)\ \ or\ \ max(a,b)\ =\ -min(-a,-b)\\
(a \wedge b)\ =\ -(-a \vee -b)\ \ or\ \ min(a,b)\ =\ -max(-a,-b)$
滿足 DeMorgan's laws ，所以我們只需 max 或 min 並將符號反相即可得另一個。
:::
* XOR
|c |T|0|1|
|:---:|-|-|-|
|**T**|T|0|1|
|**0**|0|0|0|
|**1**|1|0|T|
$c\ =\ (a \oplus b)$
* 加法器
* Half-adder
|$\mathbf{a_i}$|$\mathbf{b_i}$|$\mathbf{s_i}$|$\mathbf{c_{i+1}}$|
|:------------:|:------------:|:------------:|:----------------:|
|T |T |1 |T |
|T |0 |T |0 |
|T |1 |0 |0 |
|0 |T |T |0 |
|0 |0 |0 |0 |
|0 |1 |1 |0 |
|1 |T |0 |0 |
|1 |0 |1 |0 |
|1 |1 |T |1 |
分別看 $\mathbf{s_i}$ 和 $\mathbf{c_{i+1}}$

|$\mathbf{s_i}$|T|0|1|
|:------------:|-|-|-|
|**T** |1|T|0|
|**0** |T|0|1|
|**1** |0|1|T|
$s_i\ =\ (a+b)\ =\ (\ (a=T)\wedge(b-1)\ )\vee(\ (a=0)\wedge(b))\wedge((a=1)\vee(b+1)\ )$

:::info
在二進位中我們是以 $\mathbf{s_i\ =\ a_i \oplus b_i }$ 來表示，但由真值表可看出 $\mathbf{s_i\ \neq\ a_i \oplus b_i }$
:::

當我們以 [Sum-of-products canonical form](https://courses.cs.washington.edu/courses/cse370/97au/admin/Slides/Week2Lecture3/sld003.htm) 做化簡時 T 會被消除，此時剩下 6 個 minterms ，在布林邏輯中每個 minterms 有兩個輸入，但在這裡我們增加一個輸入常數以指向最後的輸出，所以會變成
$\begin{split}s_i\ =\ (a+b)\
&=\ (\ (a=T)\wedge(b=T))\wedge 1\ )\\
&\vee\ (\ (a=T)\wedge(b=1))\wedge 0\ )\\
&\vee\ (\ (a=0)\wedge(b=0))\wedge 0\ )\\
&\vee\ (\ (a=0)\wedge(b=1))\wedge 1\ )\\
&\vee\ (\ (a=1)\wedge(b=T))\wedge 0\ )\\
&\vee\ (\ (a=1)\wedge(b=0))\wedge 1\ )\\
\end{split}$

|$\mathbf{c_{i+1}}$|T|0|1|
|:----------------:|-|-|-|
|**T** |T|0|0|
|**0** |0|0|0|
|**1** |0|0|1|
$c_{i+1}\ =\ a⊠b\ =\ (a\wedge b)\vee(\ (a\neq T)\wedge 0\ )\vee(\ (b\neq T)\wedge 0\ )$

同理 $\mathbf{c_{i+1}}$ 也不像二進位為 a & b ，用前面的方法化簡的話會有 8 個 minterms ，這裡就不再列出。
雖說 Balanced Ternary 的空間使用度較佳，但也因為多狀態的存在使得電路設計複雜的多。
:::info
有了真值表後我們需要構建一個基本構件以實現半加法器，參考 [Ternary computing: basics](https://github.com/ssloy/tutorials/wiki/Ternary-computing:-basics) 設計了一個多工器，輸入一個進行基本運算的變數輸出對應的功能 ( [unary function](https://en.wikipedia.org/wiki/Unary_function) ) ， 5 個引腳中一個接收三位元的輸入， inN, inO, inP 根據多工器所需功能而設定以產生相應的輸出。
:::
透過上面的真值表設計 4 個不同功能的多工器 A+1, A+1, max(A,0), min(A,0) ，以下拿 max(A,0) 做說明
.png)
前面已推導出 max 的真值表，這邊我們輸入 A 做引數，另一個輸入 B 為 0 ，則由真值表截取 B = 0 那行應有的輸出為 (0,0,1)，所以如果我們要做出有 max(A,1) 的多工器，則產生的輸出應為 (1,1,1) 當作 inN, inO, inP 的輸入。
接下來就能透過多工器實現 $\mathbf{s_i}$ 和 $\mathbf{c_{i+1}}$
這邊看會比較複雜一點，首先看真值表，不看 A 當 B 的輸入 (-1,0,1) 各會產生三個輸出，當 B 為 -1 時，需傳入的輸入為 (1,-1,0) ，所以在前一層我們須使用功能為 A-1 的多工器傳入第二層的 inN ，依此類推 inO 傳入 (-1,0,1) 也就是 A ， inP 傳入 (0,1,-1) 也就是 A+1。
.png)
$\mathbf{c_{i+1}}$ 的部分由真值表也可以知道分別需傳入 ( min(A,0),0,max(A,0) ) 以產生對應的真值表。

* Full-adder

與半加法器相較全加法器有三個輸入 $\mathbf{A, B, C_{in}}$ 及兩個輸出 $\mathbf{S, C_{out}}$
**S** 的部分有三層，第一層輸入 **A** ，第二層輸入 **B** ，第三層輸入 $\mathbf{C_{in}}$ ，因此 function 為 $\mathbf{(A+B+C_{in})}$ ，將各層展開為圖中紅色字體，綠色區域為原本的半加法器，當 $\mathbf{C_{in}=0}$ 時會退化成半加法器。
前面 **S** 的部分可以直接看出，在看 $\mathbf{C_{out}}$ 要搭配 [真值表](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml)，然後將 $\mathbf{C_{in} = (T,0,1)}$ 的部分取出來看
|$\mathbf{C_{in} = T}$|T|0|1|
|:-------------------:|-|-|-|
|**T** |T|T|0|
|**0** |T|0|0|
|**1** |0|0|0|
當 $\mathbf{C_{in} = T}$ 時有三個組合對應 (A,B) 分別為 (T,T),(T,0),(0,T)
|$\mathbf{C_{in} = 0}$|T|0|1|
|:-------------------:|-|-|-|
|**T** |T|0|0|
|**0** |0|0|0|
|**1** |0|0|1|
當 $\mathbf{C_{in} = 0}$ 時與半加法器的 $\mathbf{c_{i+1}}$ 相同
|$\mathbf{C_{in} = 1}$|T|0|1|
|:-------------------:|-|-|-|
|**T** |0|0|0|
|**0** |0|0|1|
|**1** |0|1|1|
當 $\mathbf{C_{in} = 1}$ 時有三個組合對應 (A,B) 分別為 (0,1),(1,0),(1,1)

## Balanced Ternary 的設計要解決甚麼類型的問題

### Radix Economy

基需 (Radix Economy) 的概念是指在一個固定基數下表示一個數需要的開銷。在表示一個數時同時考慮到基數與位數，例如要表示 0~9 時在基數為 2 下需要 4 位數，在基數為 10 下只需要 1 位數，綜合考量下對基需有明確定義，對於任意數 N，在基數為 R 下表示數字需要 $log_rN+1$ 位數，也就是
$E(r,N)\ =\ r\times(log_rN+1)$
把上式看成連續函數的極值問題
$E(r,N)\ =\ r\times(log_rN+1)\ \approx\ r\times(log_rN)\ =\ (r/ln(r))\times ln(N)$
則可以發現當 r = e 時值最小，再來是 3, 2, 4
透過數學證明在整數上三進制是最經濟的進制，可是為何如今的計算機結構仍採用二進制？在 [The most efficient radix is not e](http://hummusandmagnets.tumblr.com/post/48664858476/the-most-efficient-radix-is-not-e) 中對於 Radix Economy 有其他的看法
:::info
要判斷哪個基數比另一個更有效取決於你想表達的數字，這意味著如果你想要表示 $N$ 個值的範圍，則可以最有效地表示這些值的基數 $R$ 是對於某些 $k$， $R^k$ 最接近於 $N$ 的基數 $R$ ，他們可能是 2,3 或是 10，這一切都取決於 $N$ ，當 $N=10$ 為 radix-10 因為 $10=10^1$，當 $N=64$，則有 $64=2^6=4^3=8^2$。
:::
如果這樣不就意味著最好的基數總會是想表達的數字 N 本身嗎？事實上的確是如此，但當你要使用它時必須先構建出可以與其搭配的硬體，基數越大難以量化，這表示為了實際目的 R 不能太大。
來比較 radix-2 [2, 4, 8, 16, 32, 64...]和 radix-3 [3, 9, 27, 81, 243, 729...]，選擇一個隨機數 N，你可以預期 N 到下一個 $2^k$ 的距離較 $3^k$ 小，隨著基數增長差距越來越大。

### **參考文獻**

* [Douglas W. Jones on Ternary Logic](http://homepage.divms.uiowa.edu/~jones/ternary/logic.shtml)
* [三生萬物](http://www.global-sci.org/mc/issues/5/no4/freepdf/79s.pdf)
* [Brian Hayes_Third Base](http://bit-player.org/wp-content/extras/bph-publications/AmSci-2001-11-Hayes-ternary.pdf)(待閱讀)
* [【獨家】化學計算、濕件計算、流體計算和三元計算,這些「非常規計算」將挑戰摩爾定律](http://oicwx.com/detail/221560)(待整理)