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

## **Balanced Ternary 原理**
### 簡介
在了解 Balanced Ternary 之前，先簡單介紹什麼是 Ternary numeral system ：
:::info
三進位是以 $3$ 為基數的進位。和二進位一樣，三進位的數位，稱為三進位位（trit），每個三進位位包含 ${\displaystyle \log _{2}3} \log _{2}3$（約1.58個）二進位位的信息量。通常，三進位中使用 $0$ 、 $1$ 、 $2$ 三個數字。但在平衡三進位中，則使用 $-1$ （記作 $T$ ）、 $0$ 、 $1$ 來表達。 -- [維基百科](https://zh.wikipedia.org/wiki/%E4%B8%89%E8%BF%9B%E5%88%B6)
:::

可以知道 Balanced Ternary 是 Ternary numeral system 的其中一種數值表達方式，每個位數可以是下列三種狀態：
* $1$
* $0$
* $-1$ （記作 $T$ ）

Balanced Ternary 將各位數字和各位的權重相乘並且取總合就是其數值，
$$
\sum_{i=0}^n a_i\times3^i
$$

例如：

$10T$ 用我們日常生活所用的 base-10 數值系統表示即為 $8$：
$$-1*3^0 +0*3^1 + 1*3^2 = -1 + 0 + 9 = 8$$

---

### 運算

加法
| +| 1| 0| T|
|-----|---|---|---|
|**1**| 1T| 1| 0|
|**0**| 1| 0| T|
|**T**| 0| T| T1|
減法
| -| 1| 0| T|
|-----|---|---|---|
|**1**| 0| 1| 1T|
|**0**| T| 0| 1|
|**T**| T1| T| 0|
乘法
| *| 1| 0| T|
|-----|---|---|---|
|**1**| 1| 0| T|
|**0**| 0| 0| 0|
|**T**| T | 0| 1|
除法
| /| 1| 0| T|
|-----|---|-----------|---|
|**1**| 1| +$\infty$| T|
|**0**| 0| NaN| 0|
|**T**| T| -$\infty$| 1|

---

### Balanced Half Adder

根據 [Fast Ternary Addition](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml) 可以透過下面的真值表完成半加器實作加法運算：

| inputs|outputs
|-----|---|---|---|
| $a_i \ \ \ \ \ \ c_i$ | $c_{i+1} \ \ \ \ s_i$ |
| $T\ \ \ \ \ \ T$ | $-\ \ \ \ \ \ \ +$ |
| $T\ \ \ \ \ \ 0$ | $0\ \ \ \ \ \ \ -$ |
| $T\ \ \ \ \ \ +$ | $0\ \ \ \ \ \ \ 0$ |
| $0\ \ \ \ \ \ T$ | $0\ \ \ \ \ \ \ -$ |
| $0\ \ \ \ \ \ 0$ | $0\ \ \ \ \ \ \ 0$ |
| $0\ \ \ \ \ \ +$ | $0\ \ \ \ \ \ \ +$ |
| $+\ \ \ \ \ \ T$ | $0\ \ \ \ \ \ \ 0$ |
| $+\ \ \ \ \ \ 0$ | $0\ \ \ \ \ \ \ +$ |
| $+\ \ \ \ \ \ +$ | $+\ \ \ \ \ \ \ -$ |

$$
s_i=sums(a_i,c_i)\\
c_{i+1}=cons(a_i,c_i)
$$
$s_i=sums(a_i,c_i)$ 與 $c_{i+1}=cons(a_i,c_i)$ 都是 Ternary 的邏輯運算子，其真值表分別為

| $s_i$ | T | 0 | + |
|-----|---|---|---|
|**T**| $+$ | $T$ | $0$ |
|**0**| $T$ | $0$ | $+$ |
|**+**| $0$ | $+$ | $T$ |

| $c_{i+1}$ | T | 0 | + |
|-----|---|---|---|
|**T**| $-$ | $0$ | $0$ |
|**0**| $0$ | $0$ | $0$ |
|**+**| $0$ | $0$ | $+$ |

---

### Balanced Full Adder
透過上述的 Balanced Half Adder 可以建構出 Balanced Full Adder
$$
s_i=sums(sums(a_i,b_i),c_i)\\
c_a=cons(a_i,b_i)\\
c_b=cons(sums(a_i,b_i),c_i)\\
c_{i+1}=any(c_a,c_b)
$$
其中 $c_{i+1}=any(c_a,c_b)$ 的真值表為
| $c_{i+1}$ | T | 0 | + |
|-----|---|---|---|
|**T**| $T$ | $T$ | $0$ |
|**0**| $T$ | $0$ | $+$ |
|**+**| $0$ | $+$ | $+$ |
---

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

* $e$ 進制的編碼效率最高，而 ternary 系統本身最接近 $e$ 進制，與現在電腦用的 binary 系統相比能儲存的資料密度較高。
* 在電路實作上， binary 系統 與 ternary 系統都有其對稱性，結構上應該不會複雜太多，但 ternary 系統不需要區分有號數與無號數而省略一個位元。
* 隨著摩爾定律遇到瓶頸， ternary 系統的電路實作或許可以另闢新天地。

## **列出在 GitHub 裡頭可找到的應用案例，不僅列出程式碼，還要解說**