2017q3 Homework1 (ternary)

contributed by < vasv75182366 >

Balanced Ternary 原理

簡介

在了解 Balanced Ternary 之前，先簡單介紹什麼是 Ternary numeral system ：

三進位是以

$3$ 為基數的進位。和二進位一樣，三進位的數位，稱為三進位位（trit），每個三進位位包含

${\displaystyle {\log }_{2}3}{\log }_{2}3$（約1.58個）二進位位的信息量。通常，三進位中使用

$0$ 、

$1$ 、

$2$ 三個數字。但在平衡三進位中，則使用

$-1$ （記作

$T$ ）、

$0$ 、

$1$ 來表達。 – 維基百科

可以知道 Balanced Ternary 是 Ternary numeral system 的其中一種數值表達方式，每個位數可以是下列三種狀態：

• $1$
• $0$
• $-1$ （記作
  $T$ ）

Balanced Ternary 將各位數字和各位的權重相乘並且取總合就是其數值，

$$\sum _{i=0}^n{a}_i\times 3^i$$

例如：

$10T$ 用我們日常生活所用的 base-10 數值系統表示即為

$8$：

$$-1\ast 3^0+0\ast 3^1+1\ast 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	+ $\mathrm{\infty }$	T
0	0	NaN	0
T	T	- $\mathrm{\infty }$	1

---

Balanced Half Adder

根據 Fast Ternary Addition 可以透過下面的真值表完成半加器實作加法運算：

| inputs|outputs
|––-|–-|–-|–-|
|

$a_i{c}_i$ |

$c_{i+1}{s}_i$ |
|

$TT$ |

$-+$ |
|

$T0$ |

$0-$ |
|

$T+$ |

$00$ |
|

$0T$ |

$0-$ |
|

$00$ |

$00$ |
|

$0+$ |

$0+$ |
|

$+T$ |

$00$ |
|

$+0$ |

$0+$ |
|

$++$ |

$+-$ |

$$\begin{gathered} s_i=sums(a_i,c_i) \\ {c}_{i+1}=cons(a_i,c_i) \end{gathered}$$

$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

$$\begin{gathered} 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) \end{gathered}$$
其中

$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 裡頭可找到的應用案例，不僅列出程式碼，還要解說