2017q3 Homework1 (ternary)

contributed by < poyushen >

Balanced Ternary

Balanced Ternary 是一套以

3

為基底 (base-3)，使用

- 1

(以下記做

T

)、

0

、

1

來表示的數值系統。

將三進位數值表示成十進位數值算法為：

\sum_{k = 1}^{i} a_{k} \times 3^{k - 1} + \sum_{n = 1}^{j} a_{n} \times 3^{- n}

其中

i

為三進位數值整數部分的位元數，

j

為三進位數值小數部分的位元數

a_{k}

及

a_{n}

為

T

、

0

或

1

整數

"example" 的簡寫是 e.g.，不是 "ex"，後者是「前」雇主一類用語
"jserv"
知道了！謝謝老師！
Amy Shen

e.g.
$1 T 0_{b a l 3} = 1 \times 3^{2} + (- 1) \times 3^{1} + 0 \times 3^{0} = 9 - 3 + 0 = 6_{d e c}$
* e.g.
$T 10_{b a l 3} = (- 1) \times 3^{2} + 1 \times 3^{1} + 0 \times 3^{0} = - 9 + 3 + 0 = - 6_{d e c}$
* e.g.
$23_{d e c} = 1 \times 3^{3} + 0 \times 3^{2} + (- 1) \times 3^{1} + (- 1) \times 3^{0} = 10 T T_{b a l 3}$
* e.g.
$- 23_{d e c} = (- 1) \times 3^{3} + 0 \times 3^{2} + 1 \times 3^{1} + 1 \times 3^{0} = T 011_{b a l 3}$

分數（小數）

e.g.
$1. T 0_{b a l 3} = 1 \times 3^{0} + (- 1) \times 3^{- 1} + 0 \times 3^{- 2} = {\frac{2}{3}}_{d e c}$
* e.g.
$T {.10}_{b a l 3} = (- 1) \times 3^{0} + 1 \times 3^{- 1} + 0 \times 3^{- 2} = - {\frac{2}{3}}_{d e c}$
* e.g.
$\frac{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 . . . . (循環) {\frac{1}{6}}_{d e c} = 0. {\overset{―}{1 T}}_{b a l 3}$
* e.g.
$- \frac{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 . . . (循環) - {\frac{1}{6}}_{d e c} = 0. {\overset{―}{T 1}}_{b a l 3}$
由以上例子可知，Balanced Ternary 在表示負數的方式較二進位來的容易，
只要將全部位元都
$\times (- 1)$ 即可。

Balanced Ternary 基本原理

AND

$c$
$T$
$0$
$1$

$T$
$T$
$T$
$T$

$0$
$T$
$0$
$0$

$1$
$T$
$0$
$1$

$c = a \land b = m i n (a, b)$
OR

$c$
$T$
$0$
$1$

$T$
$T$
$0$
$1$

$0$
$0$
$0$
$1$

$1$
$1$
$1$
$1$

$c = a \lor b = m a x (a, b)$
XOR

$c$
$T$
$0$
$1$

$T$
$T$
$0$
$1$

$0$
$0$
$0$
$0$

$1$
$1$
$0$
$T$

$c = a \oplus b = x o r (a, b) = (\bar{a} \land b) \lor (a \land \bar{b})$

$c$	$T$	$0$	$1$
$T$	$T$	$T$	$T$
$0$	$T$	$0$	$0$
$1$	$T$	$0$	$1$
$c = a \land b = m i n (a, b)$

$c$	$T$	$0$	$1$
$T$	$T$	$0$	$1$
$0$	$0$	$0$	$1$
$1$	$1$	$1$	$1$
$c = a \lor b = m a x (a, b)$

$c$	$T$	$0$	$1$
$T$	$T$	$0$	$1$
$0$	$0$	$0$	$0$
$1$	$1$	$0$	$T$
$c = a \oplus b = x o r (a, b) = (\bar{a} \land b) \lor (a \land \bar{b})$

Balanced Ternary Half Adder

$i n p u t a$	$i n p u t b$	$o u p u t c_{i + 1}$	$o u t p u t 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}$
$T$
$0$
$1$

$T$
$1$
$T$
$0$

$0$
$T$
$0$
$1$

$1$
$0$
$1$
$T$

$s_{i} = a + b = ((a = - 1) \land (b - 1)) \lor ((a = 0) \land (b)) \lor ((a = 1) \land (b + 1))$
Consensus

$c_{i + 1}$
$T$
$0$
$1$

$T$
$T$
$0$
$0$

$0$
$0$
$0$
$0$

$1$
$0$
$0$
$1$

$c_{i + 1} = a ⊠ b = c o n s (a, b) = (a \land b) \lor ((a \neq - 1) \land 0) \lor ((b \neq - 1) \land 0)$

$s_{i}$	$T$	$0$	$1$
$T$	$1$	$T$	$0$
$0$	$T$	$0$	$1$
$1$	$0$	$1$	$T$

$c_{i + 1}$	$T$	$0$	$1$
$T$	$T$	$0$	$0$
$0$	$0$	$0$	$0$
$1$	$0$	$0$	$1$
$c_{i + 1} = a ⊠ b = c o n s (a, b) = (a \land b) \lor ((a \neq - 1) \land 0) \lor ((b \neq - 1) \land 0)$

Balanced Ternary 運算

加法

e.g.

T 1_{b a l 3} + T T_{b a l 3} = 2_{d e c} + (- 4)_{d e c} = (- 2)_{d e c} = T 1_{b a l 3}

粗體為進位值

\begin{aligned} T & 1 \\ + & T & T \\ 0 & 1 \\ T \\ T & 1 \end{aligned}

減法

減法運算只要先將加數

\times (- 1)

再相加即可
e.g.

\begin{aligned} 1 T_{b a l 3} - T T_{b a l 3} & = 2_{d e c} - (- 4)_{d e c} & = 6_{d e c} & = 1 T 0_{b a l 3} \\ 1 T_{b a l 3} + 11_{b a l 3} & = 2_{d e c} + 4_{d e c} & = 6_{d e c} & = 1 T 0_{b a l 3} \end{aligned}

粗體為進位值

\begin{aligned} 1 & T \\ + & 1 & 1 \\ T & 0 \\ 1 \\ 1 & T & 0 \end{aligned}

乘法

e.g.

1 T_{b a l 3} \times T T_{b a l 3} = 2_{d e c} \times (- 4)_{d e c} = (- 8)_{d e c} = T 01_{b a l 3}

T \times T = 1

1 \times 1 = 1

T \times 1 = 1 \times T = T

\begin{aligned} 1 & T \\ \times & T & T \\ T & 1 \\ T & 1 \\ T & 0 & 1 \end{aligned}

除法

e.g.

T T_{b a l 3} \div 1 T_{b a l 3} = (- 4)_{d e c} \div 2_{d e c} = (- 2)_{d e c} = T 1_{b a l 3}

T \underset{―}{T} 1 T) T T \underset{―}{+ 1 T} A n s : T + T = T 1 T 1 \underset{―}{+ 1 T} 0

將

T T - (1 T \times T) = T T - T 1

換成

T T + 1 T

。加完結果為

T 1

，因為餘數的首位非0，因此再除一次時商數必須放在同一個位數而非下一個位數，最後再將兩次的商相加。

e.g.

1 T T T_{b a l 3} \div 1 T_{b a l 3} = 14_{d e c} \div 2_{d e c} = 7_{d e c} = 1 T 1_{b a l 3}

T \underset{―}{1 0 T} 1 T) 1 T T T \underset{―}{+ T 1} 0 T A n s : T \underset{―}{+ 0 0} \underset{―}{+ 1 0 T} T T 1 T 1 \underset{―}{+ 1 T} T 1 \underset{―}{+ 1 T} 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 中以模擬程序運作。