# 2017q3 Homework1 (ternary)
contributed by <timedieyoung>

## Balanced Ternary

平衡三進位，以 `-、0、+` 作為基本數位，基底為三進位制。(因為指令問題，以下內文以 T、0、1 表示)

`-` 表示 `-1`
`0` 表示 `0`
`+` 表示 `1`

由於 -1 的引入，這種進位不需要額外的符號就能直接表示負數，也因此在==加、減、乘==的效率比二進位要好。

---

### 數的表示方法

平衡三進位和其他進位法相同，將各位的數字與位權相乘疊加即可表示任一整數部分與小數部分，兩者用 `.` 分隔。

---
將十進位的 -9 ~ +9 以平衡三進位轉換為以下表格

|Dec |Bal3 |Cal | |Dec |Bal3 |Cal |
| --:| --: | -: |-| --:| ---:| --: |
|0 |0 |0 | | | | |
|1 |1 |+1 | |−1 |T |−1 |
|2 |1T |+3−1 | |−2 |T1 |−3+1 |
|3 |10 |+3 | |−3 |T0 |−3 |
|4 |11 |+3+1 | |−4 |TT |−3−1 |
|5 |1TT |+9−3−1 | |−5 |T11 |−9+3+1|
|6 |1T0 |+9−3 | |−6 |T10 |−9+3 |
|7 |1T1 |+9−3+1 | |−7 |T1T |−9+3−1|
|8 |10T |+9−1 | |−8 |T01 |−9+1 |
|9 |100 |+9 | |−9 |T00 |−9 |

從表格可以觀察出
* 第一個非0位是`T` 的為==負數==，是 `1` 的為==正數==。
* 將任一數的所有 `T` 與 `1` 作互換即可變號(乘上-1)。

因此，欲將 $−25.4_{dec}$ 、 $1010.1_{bin}$ 表現為平衡三進位，可透過以下步驟轉換:

:::info
任何進位系統都可以表示成以下形式:

$(a_{n}a_{n-1}···a_1a_0.c_1c_2c_3····)_b=\displaystyle\sum_{k=0}^{n}a_kb^k+\displaystyle\sum_{m=1}^{\infty}c_mb^{-m}$

> $a_{n}a_{n-1}···a_1a_0.c_1c_2c_3····$ 系統的表現形式
$b$ 系統的底數
$a_k$、$c_m$ 小數點左側第K位數字、小數點右側第m位數字

$\begin{split} −25.4_{dec} &= −(1T×101^1 + 1TT×101^0 + 11×101^{−1}) \\&= −(1T×101 + 1TT + 11÷101) \\&= −10T1.\overline{11TT} \\&= T01T.\overline{TT11} \end{split}$

$\begin{split} 1010.1_{bin} &= 1T^{100} + 1T^1 + 1T^{−1} \\&= 10T + 1T + 0.\overline{1} \\&= 101.\overline{1} \end{split}$
:::

---

### 算數運算

單位數的加、減、乘運算可以化作以下表格

|+ |T |0 |1 |
|:-: |:-: |:-: |:-: |
|**T** |T1 |T |0 |
|**0** |T |0 |1 |
|**1** |0 |1 |1T |

|- |T |0 |1 |
|:-: |:-: |:-: |:-: |
|**T** |0 |T |T1 |
|**0** |1 |0 |T |
|**1** |1T |1 |0 |

|$\times$ |T |0 |1 |
|:-: |:-: |:-: |:-: |
|**T** |1 |0 |T |
|**0** |0 |0 |0 |
|**1** |T |0 |1 |

加法和乘法有交換律

---
### 邏輯運算
與 Unsigned and 3's-complement ternary 作比較

| truth value | unsigned | balanced |
| :---------: | :------: | :------: |
| *false* | 0 | T |
| *unknown* | 1 | 0 |
| *true* | 2 | 1 |

---

基於以上定義，真值表表現如下:

|Not |T |0 |1 |
|:-: |:-: |:-: |:-: |
| |1 |0 |T |

> Not logic 的 unknown 表現依舊是 unknown

|And |T |0 |1 |
|:-: |:-: |:-: |:-: |
|**T** |T |T |T |
|**0** |T |0 |0 |
|**1** |T |0 |1 |

> And logic 又可以看作將輸入取最小值(min)

|Or |T |0 |1 |
|:-: |:-: |:-: |:-: |
|**T** |T |0 |1 |
|**0** |0 |0 |1 |
|**1** |1 |1 |1 |

> Or logic 又可以看作將輸入取最大值(MAX)

|Xor |T |0 |1 |
|:-: |:-: |:-: |:-: |
|**T** |T |0 |1 |
|**0** |0 |0 |0 |
|**1** |1 |0 |T |

|Sum |T |0 |1 |
|:-: |:-: |:-: |:-: |
|**T** |1 |T |0 |
|**0** |T |0 |1 |
|**1** |0 |1 |T |

|Cons |T |0 |1 |
|:-: |:-: |:-: |:-: |
|**T** |T |0 |0 |
|**0** |0 |0 |0 |
|**1** |0 |0 |1 |

> 合意邏輯(Consensus logic)，等義於將0和T視作相同意義的 And logic。

---
#### ternary multiplexer

在討論加法器前，先了解 ternary multiplexer 的構造

下圖為一 `ternary multiplexer`的腳位

腳位分為三組 `JP1`、`JP2`、`JP3`

Connector JP1:

1) S1 - select input of the 1st ternary multiplexer

2) N1 - connected to C1 if S1=N ("negative" or -5V)

3) O1 - connected to C1 if S1=O ("zero" or 0V)

4) P1 - connected to C1 if S1=P ("positive" or +5V)

5) C1 - common signal of the 1st ternary multiplexer

Connector JP2:

1) S2 - select input of the 2nd ternary multiplexer

2) N2 - connected to C2 if S2=N ("negative" or -5V)

3) O2 - connected to C2 if S2=O ("zero" or 0V)

4) P2 - connected to C2 if S2=P ("positive" or +5V)

5) C2 - common signal of the 2nd ternary multiplexer

Connector JP3:

1) V-NEG - negative voltage (typically -5V)

2) GND - ground wire

3) V-POS - positive voltage (typically +5V)

簡單來說，是透過輸入端 S 的電位來決定 C 的輸出值 (N、O、P)，如下表

|S(in) |C(out) |
|:-: |:-: |
|-5V |**N** |
|0V |**O** |
|5V |**P** |

#### Balanced Half Adder

用以下電路為例，為一個半加器

分為 `Sum`、`Consensus` 兩部分
-5V、0、5V 分別以 T、0、1 代替

---

Sum:(左上晶片 JP1、JP2 & 右晶片 JP1)

左上 JP1 的 S、N、O、P 分別為 A、1、T、0
左上 JP2 的 S、N、O、P 分別為 A、0、1、T
右 JP1 的 S、N、O、P 分別為 B、C1(左上JP1)、A、C2(左上JP2)

整理成真值表可得

|A |B |C1 |C2 |Sum |
|:-: |:-: |:-: |:-: |:-: |
|**T** |**T** |1 |0 |**1** |
|**T** |**0** |1 |0 |**T** |
|**T** |**1** |1 |0 |**0** |
|**0** |**T** |T |1 |**T** |
|**0** |**0** |T |1 |**0** |
|**0** |**1** |T |1 |**1** |
|**1** |**T** |0 |T |**0** |
|**1** |**0** |0 |T |**1** |
|**1** |**1** |0 |T |**T** |

---

Consensus:(左下晶片 JP1、JP2 & 右晶片 JP2)

左下 JP1 的 S、N、O、P 分別為 A、T、0、0
左下 JP2 的 S、N、O、P 分別為 A、0、0、1
右 JP2 的 S、N、O、P 分別為 B、C3(左下JP1)、0、C4(左下JP2)

整理成真值表可得

|A |B |C3 |C4 |Consensus |
|:-: |:-: |:-: |:-: |:-: |
|**T** |**T** |T |0 |**T** |
|**T** |**0** |T |0 |**0** |
|**T** |**1** |T |0 |**0** |
|**0** |**T** |0 |0 |**0** |
|**0** |**0** |0 |0 |**0** |
|**0** |**1** |0 |0 |**0** |
|**1** |**T** |0 |1 |**0** |
|**1** |**0** |0 |1 |**0** |
|**1** |**1** |0 |1 |**1** |

---

## Reference
* [Wikipedia: Balanced Ternary](https://en.wikipedia.org/wiki/Balanced_ternary)
* [Fast Ternary Addition by Douglas W. Jones](http://homepage.divms.uiowa.edu/~jones/ternary/arith.shtml#addahead)
* [Standard Ternary Logic](http://homepage.divms.uiowa.edu/~jones/ternary/logic.shtml#shorthand)
* [Ternary computing: basics](https://github.com/ssloy/tutorials/wiki/Ternary-computing:-basics)
* [Dual balanced ternary multiplexer/demultiplexer](https://www.tindie.com/products/TRC/dual-balanced-ternary-multiplexerdemultiplexer/)