2017q3 Homework1 (ternary)

contributed by <xr2439>

Review by `williamchangTW`

作者文中對 ternary 有初步的了解，希望能對該技術做更深入的了解，能慢慢地完成作業需求

小弟坐井觀天，如有冒犯請見諒"williamchangTW"

Balanced Ternary 簡介

此處的 Ternary 是指 Ternary Numeral System，即以三進制的方式記數。在 N 進制的數字系統中，我們常以數字 0, 1, ..., N-1 搭配基數 N 來表示數值。

若於三進制系統中，選用 0, 1, 2 搭配基數 3 來表示數值，則此系統稱為不平衡三進制 (Unbalanced Ternary)。若改採用 -1, 0, 1 搭配基數 3 來表示數值，則可以發現 -1, 0, 1 三個數字於數線上的原點對稱，故稱平衡三進制 (Balanced Ternary)。

平衡進制系統由於具有小於零的數字，故不須像其他進制系統，如日常所用的十進制，需要正負號 (sign) 來標記數值的正負。

Notation

為了能夠更簡潔地表達，文章採用下列的標記法：

對於不平衡 N 進制系統的數字，採用 (數字)_N 表示
對於平衡 N 進制系統的數字，採用 (數字)_balN 表示
對於十進位系統，採用 Dec 表示
對於平衡三進制系統，採用 Bal3 表示
於平衡三進制系統中，採用 T 表示 -1

Balanced Ternary 表達式

本節將描述下列兩個主題：

如何轉成十進位數字
如何從 Unbalanced Ternary 轉換成 Balanced Ternary

轉換為十進位數字

對於任何 N 進制數字，

(a_{n} a_{n - 1} \dots a_{1} a_{0} . b_{1} b_{2} b_{3} \dots)_{N} = \sum_{k = 0}^{n} a_{k} N^{k} + \sum_{k = 1}^{\infty} b_{k} N^{- k} (1)

依照上述公式能將平衡三進制的數字轉為十進位。

下表列出 -4~4 (Dec) 所對應的平衡三進制數字

Dec	Bal3	Expansion	Dec	Bal3	Expansion
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

發現於 Bal3 中，若要改變一個數字的正負號，僅需將表達式中 1 置換為 T，T 置換 1。

若欲改變一個數字的正負號，則 (1) 式中的
$a_{k}$ 及
$b_{k}$ 係數，應加上負號。而在平衡三進制系統中，於係數加上負號等同於做 1 與 T 置換的動作。xr2439

如何從 Unbalanced Ternary 轉換成 Balanced Ternary

有兩種轉換方式

第 1 種方式為從數字最左方的非零數字加一連串的 1，接著再減去同樣的數字，但不做借位。以 210₃ 為例：

\begin{aligned} 210_{3} & + 111_{3} & = 1021_{3} \\ 1021_{3} & - 111_{3} & = 1 T 10_{b a l 3} \end{aligned}

第 2 種方式為將 2 替換為 1T 來表示。以 220₃ 為例：

220_{3} = 0220_{3} = 1 T 00_{b a l 3} + 01 T 0_{b a l 3} = 10 T 0_{b a l 3}

第 1 種方式的原理為，某一個數字若加上 A 這個數，再減去 A 則會變為原來的數字。此方法的 A 為一連串的 1，其用意為將(數值)₃中原本的 2 消除。最後再透過不借位減去的方法轉換成 Bal3 的數值

第 2 種方法的原理很直覺，由於 2₃ = 1T_bal3，將式子中的 2₃ 拆項以 1T_bal3 表示。
xr2439

Balanced Ternary 的數值運算

Logic Tables

Sum	T	0	1
T	1	T	0
0	T	0	1
1	0	1	T

Carry	T	1
T	T	0
0	0	0
1	0	1

參考資料

Wikipedia - 進位制
 Wikipedia - Ternary numeral system
Wikipedia - Balanced ternary
Youtube - Non-Binary Computing