# 2017q3 Homework1 (ternary)
contributed by <`function86437`>
## Ternary numeral system
Ternary 是一個三進制的系統，又稱為 (base-3) ，儲存資料的位元稱為 __trit__ (trinary digit) ，對比二進制的 bit ，在 ternary 中因表示法的不同又分為 unsigned ternary 與 balanced ternary ，對應的表示法為 `0, 1, 2` 與 `-1, 0, +1` (`T, 0, 1`) 。

* [[wikipedia-Balanced ternary]](https://en.wikipedia.org/wiki/Balanced_ternary)中討論在二進制中 n bits 能表示的最大數字為$2^n$ -1，那 ternary n bits 能表示的最大數字是否為$3^n$-1呢？
*給定一個數字為 $N(b,d)$ ,其中 b 為基底 d 為次方，給個單位能表示最大數為 b-1 。*
$N(b,d)=(b-1)b^{d-1}+(b-1)^{d-2}+...+(b-1)^1+(b-1)^0,$
$N(b,d)=(b-1)(b^{d-1}+b^{d-2}+...+b^1+1),$
$N(b,d)=(b-1)M.$
$bM=b^d+b^d-1+...+b^2+b^1,and$
$-M=-b^{d-1}-b^{d-2}-...-b^1-1,so$
$bM-M=b^d-1,or$
$M=(b^d-1)/(b-1). Then$
$N(b,d)=(b-1)M,$
$N(b,d)=(b-1)(b^d-1)/(b-1), and$
$N(b,d)=b^d-1.$
例如：$N(3,3)=3^3-1=26=2\times3^2+2\times3^1+2\times3^0=18+6+2$

## Balanced Ternary
balanded ternary 的表示法為 `-1, 0, 1`，可以表示所有的整數，而且不需要額外的位元儲存正負號。

*例如：$-9_{dec}=T00_{bal3}$*
*最左邊的第一個非零項本身就包含正負號。*
$-9_{dec}=-1\times3^2+0\times3^1+0\times3^0=T00_{bal3}$

我們舉幾個例子：
$10_{bal3}=1\times3^1+0\times3^0=3_{dec}$
$10T_{bal3}=1\times3^2+0\times3^1+(-1)\times3^0=8_{dec}$
$8_{dec}=1\times3^2+0\times3^1+(-1)\times3^0=10T_{bal3}$

${-2\over3}_{dec}=-1+{1\over3}=-1\times3^0+1\times3^{-1}=T.1_{bal3}$
但在遇到某些浮點數的時候，會出現有不只一種表示法。
*例如：$-0.5_{dec}=-1\times{1\over3}+-1\times{1\over9}...=0.\overline{T}_{bal3}$*
*又可表示為*
$-0.5_{dec}=-1+0.5_{dec}=T+0.\overline{1}_{bal3}=T.\overline{1}_{bal3}$

## Ternary 基本運算
在真值表上 Ternary 相較於 Bianry 多了一個 unknown 的值，對應`-1,0,1` 如下表：
|truth value||
|-|-|
|true|+|
|unknown|0|
|false|-|

在[Ternary computing](https://github.com/ssloy/tutorials/wiki/Ternary-computing:-basics)介紹中，下圖的 ternary multiplexer 取決於輸入 A 的訊號，輸出相對應值，例如：當 A=-1 輸出 pin腳 N ， A=0 輸出 pin腳 O， A=1 輸出 pin腳 P ，會根據 N,O,P數值不同，而有不同的功能，是一個[unary functions](https://en.wikipedia.org/wiki/Unary_function)
<img src="https://raw.githubusercontent.com/ssloy/tutorials/master/ternary/doc/multiplexer.png" height="200">

這是一個輸出 A = A + 1 與 A = A - 1 的功能
<div>
<img style="display:inline-block;white-space:normal;" src="https://raw.githubusercontent.com/ssloy/tutorials/master/ternary/doc/A%2B1.png" height="150">

<img style="display:inline-block;white-space:normal;" src="https://raw.githubusercontent.com/ssloy/tutorials/master/ternary/doc/A-1.png" height="150">
</div>

計算 A 與 0 的最大值、最小值
<div>
<img style="display:inline-block;white-space:normal;" src="https://raw.githubusercontent.com/ssloy/tutorials/master/ternary/doc/max(A%2C0).png" height="150">

<img style="display:inline-block;white-space:normal;" src="https://raw.githubusercontent.com/ssloy/tutorials/master/ternary/doc/min(A%2C0).png" height="150">
</div>
<br><br>

三個 multiplexer 可以實做出一個 half adder，這邊可以發現第二層的 N,O,P 數值是由前面運算完後的結果決定的。

<img src="https://raw.githubusercontent.com/ssloy/tutorials/master/ternary/doc/A%2BB.png" height="">

從右邊真值表不難看出只有在 A,B同時為-1時輸出-1與 A,B同時為1時輸出1，其餘為0，這個電路可作為之後判斷進位的功能。
<img src="https://raw.githubusercontent.com/ssloy/tutorials/master/ternary/doc/cons(A%2CB).png" height="">

全加器類似二元運算中的全加器，都是由兩個半加器組成
<img src="https://raw.githubusercontent.com/ssloy/tutorials/master/ternary/doc/A%2BB%2BCin.png" height="">

overflow 的電路看起來很複雜，但以 Cout 的結果回推回來就比較容易理解，考慮進位 Cin 的輸入:
* 若 Cin=-1，A, B三種狀況
* A=-1且 B=0
* A=0 且 B=-1
* A=-1 且 B=-1
* 若 Cin=0， A,B必同時為-1或1
* 若 Cin=1， A, B三種狀況
* A=1 且 B=0
* A=0 且 B=1
* A=1 且 B=1

<img src="https://raw.githubusercontent.com/ssloy/tutorials/master/ternary/doc/overflow.png">

## Balanced Ternary 實際應用：

重點
* b3k 可接受10 進位輸入範圍
* 實驗對照程式碼
* [balanced ternary](https://scholar.google.com.tw/scholar?hl=zh-TW&as_sdt=0%2C5&q=%22balanced+ternary%22+&btnG=&oq=%22ba)

## 參考資料
* [wikipedia-Ternary numeral system](https://en.wikipedia.org/wiki/Ternary_numeral_system)
* [wikipedia-Balanced ternary](https://en.wikipedia.org/wiki/Balanced_ternary)
* [Standard Ternary Logic](http://homepage.divms.uiowa.edu/~jones/ternary/logic.shtml)