2017q3 Homework1 (ternary)
===
contributed by < `poyushen` >

## Balanced Ternary
Balanced Ternary 是一套以 $3$ 為基底 (base-3)，使用 $-1$ (以下記做$T$ )、$0$、$1$ 來表示的數值系統。

將三進位數值表示成十進位數值算法為 ： $\displaystyle \sum_{k=1}^{i} a_k \times 3^{k-1} + \displaystyle \sum_{n=1}^{j} a_n \times 3^{-n}$
其中 $i$ 為三進位數值整數部分的位元數， $j$ 為三進位數值小數部分的位元數
$a_k$ 及 $a_n$ 為 $T$、$0$ 或 $1$

### 整數
>> "example" 的簡寫是 [e.g.](https://en.wikipedia.org/wiki/List_of_Latin_phrases_(E)#exempli_gratia)，不是 "ex"，後者是「前」雇主一類用語
>> [name="jserv"][color=red]
>> 知道了！謝謝老師！
>> [name=Amy Shen]

* e.g. $\ 1T0_{bal3} =1 \times 3^2 + (-1) \times 3^1 + 0 \times 3^0\ = 9-3+0=6_{dec}$
* e.g. $\ T10_{bal3} =(-1) \times 3^2 + 1 \times 3^1 + 0 \times 3^0\ =-9+3+0=-6_{dec}$
* e.g. $\ 23_{dec}=1 \times 3^3 + 0 \times 3^2 + (-1) \times 3^1 + (-1) \times 3^0=10TT_{bal3}$
* e.g. $\ -23_{dec}=(-1) \times 3^3 + 0 \times 3^2 + 1 \times 3^1 + 1 \times 3^0=T011_{bal3}$

### 分數（小數）

* e.g. $\ 1.T0_{bal3}=1 \times 3^0 + (-1) \times 3^{-1} + 0 \times 3^{-2}={\dfrac{2}{3}}_{dec}$
* e.g. $\ T.10_{bal3}=(-1)\times 3^0 + 1 \times 3^{-1} + 0 \times 3^{-2}=-{\dfrac{2}{3}}_{dec}$
* e.g. $\ {\dfrac{1}{6}} \times 3=0.5=1-0.5\\\ -0.5 \times 3=-1.5=-1-0.5\\\ -0.5 \times 3=-1.5=-1-0.5\\\ ....(循環)\\\ {\dfrac{1}{6}}_{dec}=0.\overline {1T}_{bal3}$
* e.g. $\ -{\dfrac{1}{6}} \times 3=-0.5=-1+0.5\\\ 0.5 \times 3=1.5=1+0.5\\\ 0.5 \times 3=1.5=1+0.5\\\ ...(循環)\\\ -{\dfrac{1}{6}}_{dec}=0.\overline {T1}_{bal3}$
==由以上例子可知，Balanced Ternary 在表示負數的方式較二進位來的容易，==
==只要將全部位元都 $\times\ (-1)$ 即可。==

## Balanced Ternary 基本原理
1. AND

| $c$ | $\textbf T$ | $\textbf 0$ | $\textbf 1$ |
| ------- | --------| ------- | ------- |
| $\textbf T$ | $T$ | $T$ | $T$ |
| $\textbf 0$ | $T$ | $0$ | $0$ |
| $\textbf 1$ | $T$ | $0$ | $1$ |
==$c=a∧b=min\ (\ a,\ b\ )$==

2. OR

| $c$ | $\textbf T$ | $\textbf 0$ | $\textbf 1$ |
| ------- | --------| ------- | ------- |
| $\textbf T$ | $T$ | $0$ | $1$ |
| $\textbf 0$ | $0$ | $0$ | $1$ |
| $\textbf 1$ | $1$ | $1$ | $1$ |
==$c=a∨b=max\ (\ a,\ b\ )$==

3. XOR

| $c$ | $\textbf T$ | $\textbf 0$ | $\textbf 1$ |
| ------- | --------| ------- | ------- |
| $\textbf T$ | $T$ | $0$ | $1$ |
| $\textbf 0$ | $0$ | $0$ | $0$ |
| $\textbf 1$ | $1$ | $0$ | $T$ |
==$c=a⊕b=xor\ (a,\ b)=(\ \bar a\ ∧\ b)\ ∨\ (\ a∧\ \bar b\ )$==

## Balanced Ternary Half Adder

| $input \ a$ | $input \ b$ | $ouput \ c_{i+1}$| $output \ s_i$|
| --- | --- | --- | --- |
| $T$ | $T$ | $T$ | $1$ |
| $T$ | $0$ | $0$ | $T$ |
| $T$ | $1$ | $0$ | $0$ |
| $0$ | $T$ | $0$ | $T$ |
| $0$ | $0$ | $0$ | $0$ |
| $0$ | $1$ | $0$ | $1$ |
| $1$ | $T$ | $0$ | $0$ |
| $1$ | $0$ | $0$ | $1$ |
| $1$ | $1$ | $1$ | $T$ |
觀察後發現

* Sum
| $s_i$ | $\textbf T$ | $\textbf 0$ | $\textbf 1$ |
| ------- | --------| ------- | ------- |
| $\textbf T$ | $1$ | $T$ | $0$ |
| $\textbf 0$ | $T$ | $0$ | $1$ |
| $\textbf 1$ | $0$ | $1$ | $T$ |

==$s_i=a+b=(\ (\ a=-1\ )\ ∧\ (\ b-1\ )\ )\ ∨\ \ (\ (\ a=0\ )\ ∧\ (\ b\ )\ )\ ∨\ (\ (\ a=1\ )\ ∧\ (\ b+1\ )\ )$==

* Consensus
| $c_{i+1}$ | $\textbf T$ | $\textbf 0$ | $\textbf 1$ |
| ------- | --------| ------- | ------- |
| $\textbf T$ | $T$ | $0$ | $0$ |
| $\textbf 0$ | $0$ | $0$ | $0$ |
| $\textbf 1$ | $0$ | $0$ | $1$ |
==$c_{i+1}=a⊠b=cons\ (\ a,\ b\ )=(\ a\ ∧\ b\ )\ ∨\ (\ (\ a≠-1\ )\ ∧0\ )\ ∨\ (\ (\ b≠-1\ )\ ∧\ 0\ )$==

## Balanced Ternary 運算
### 加法
e.g. $T1_{bal3}+TT_{bal3}=2_{dec}+(-4)_{dec}=(-2)_{dec}=T1_{bal3}$

==粗體為進位值==

\begin{align*}
&T &1\\
+&T &T\\\hline
&0 &1\\
&\textbf T\\\hline
&T &1
\end{align*}

### 減法
減法運算只要先將加數$\ \times (-1)$ 再相加即可
e.g.$\begin{split}\ 1T_{bal3}-TT_{bal3}&=2_{dec}-(-4)_{dec}&=6_{dec}&=1T0_{bal3}\\1T_{bal3}+11_{bal3}&=2_{dec}+4_{dec}&=6_{dec}&=1T0_{bal3}\end{split}$

==粗體為進位值==

\begin{align*}
& &1 & &T\\
+& &1 & &1\\\hline
& &T & &0\\
&\textbf 1\\\hline
&1 &T & &0
\end{align*}

### 乘法
e.g. $1T_{bal3} \times TT_{bal3}=2_{dec} \times (-4)_{dec}=(-8)_{dec}=T01_{bal3}$

==$T\times T=1$==
==$1\times 1=1$==
==$T\times 1=1\times T=T$==

\begin{align*}
& &1 & &T\\
\times & &T & &T\\\hline
& &T & &1\\
&T &1\\\hline
&T &0 & &1
\end{align*}

### 除法
e.g.$\ TT_{bal3}\div 1T_{bal3}=(-4)_{dec}\div 2_{dec}=(-2)_{dec}=T1_{bal3}$

$\qquad \qquad \qquad \ \ \ T\\\qquad \quad \underline {\qquad \quad \ \ \ T}\\1\quad T \ \ \big) \quad T \qquad T\\\qquad \quad \underline{+\ 1 \qquad T\ }\qquad Ans:T+T=T1\\\qquad \qquad T \qquad 1\\\qquad \quad \underline{+\ \ 1 \qquad T}\\\qquad \qquad \qquad \ \ 0$

==將$TT-(1T \times T)=TT-T1$ 換成 $TT+1T$。加完結果為 $T1$，因為餘數的首位非0，因此再除一次時商數必須放在同一個位數而非下一個位數，最後再將兩次的商相加。==

e.g. $1TTT_{bal3}\div 1T_{bal3}=14_{dec}\div 2_{dec}=7_{dec}=1T1_{bal3}$

$\qquad \qquad \qquad \quad \ \ \ \qquad \qquad T\\\qquad \quad \underline {\qquad \quad \ \ \ 1\qquad 0\qquad T}\\1\quad T \ \ \big) \quad 1 \qquad T\qquad T \qquad T\\\qquad \quad \underline{+\ T \qquad 1\ \qquad \qquad \quad }\\\qquad \qquad \qquad \ \ 0\qquad T \qquad \qquad \qquad Ans:\qquad \qquad \qquad \ \ T\\\qquad \quad \qquad \ \ \underline{+\ \ 0 \qquad 0\qquad \ \ \ }\qquad \qquad \qquad \ \underline{+\ 1\qquad 0\qquad T}\\\qquad \qquad \qquad \ \qquad \ \ \ T\qquad T \qquad \qquad \qquad \quad 1\qquad T\qquad 1\\\qquad \qquad \quad \quad \quad \ \ \ \underline {\ +1\qquad T}\\\qquad \qquad \qquad \qquad \ \ \ \ T\qquad 1\\\quad \qquad \qquad \qquad \ \ \ \ \ \underline{+\ 1\qquad T}\\\qquad \qquad \qquad \qquad \qquad \quad \ \ 0$

## Balanced Ternary 優點

根據 Radix Economy，在所有進位制中，以 $e$ 為基底(base-$e$) 的效能最佳，其次則是 ternary，接下來才是 binary 。
balanced ternary 表示負數的方式極為簡單，只需將所有位元都 $\times (-1)$ 即可，這樣的方式可以節省不少運算時間。另外，因為 ternary 是以 3 為基底 (base-3) ，在表達數值時所需用到的位元數相對也比較少。
因此，ternary 可以說是將數值儲存在記憶體中最有效率的一種進位制。

## Balanced Ternary 應用
* Ternary Computer
第一台電子 Ternary Computer - `Setun` 在1958年發明，利用 Balanced Ternary 實作，在當時被莫斯科大學所使用。後來因成本考量而改用 Binary Computer，雖然 Binary Computer 所花費的時間是 Ternary Computer 的2.5倍。在1970年開發出新架構的 Ternary Computer - `Setun-70`，只在 Binary Computer 中以模擬程序運作。