2017q3 Homework1 (ternary)

contributed by <yang196569>

Balanced Ternary

定義

Ternary是標準三進制(Standard ternary system)，使用的數值是0, 1 , 2，而Balanced Ternary的數值則是 -1 (記作"T") , 0, +1 ,也可以計為

-

, 0 ,

+

。

數值系統轉換

三進位轉十進位:
給定一個數
$A_{n} A_{n - 1} A_{. . .} A_{1} A_{0} . B_{0} B_{1} B_{. . .} B_{m - 1} B_{m}$ ，其中A是整數部份，B是小數部份，則轉換為十進位
$X_{d e c 10}$ 可表示為 :　
$X_{d e c 10} = \sum_{k = 0}^{n} A_{k} \times 3^{k} + \sum_{l = 0}^{m} B_{l} \times 3^{- (l + 1)}$ ,

$A_{k}, B_{l}$ 為 1, 0或-1(T)，
如：
- $10 T_{b a l 3} = 1 \times 3^{2} + 0 \times 3^{1} + (- 1) \times 3^{0} = 8_{d e c 10}$
- $T 01_{b a l 3} = (- 1) \times 3^{2} + 0 \times 3^{1} + 1 \times 3^{0} = - 8_{d e c 10}$
- $1.0 T_{b a l 3} = 1 \times 3^{0} + 0 \times 3^{- 1} + (- 1) \times 3^{- 2} = {\frac{8}{9}}_{d e c 10}$
- $T {.01}_{b a l 3} = (- 1) \times 3^{0} + 0 \times 3^{- 1} + (- 1) \times 3^{- 2} = - {\frac{8}{9}}_{d e c 10}$
  三進位時，若將每個位的數字倒過來(1變T, T變1, 0不變)，那麼轉換為十進位後只需要加負號即可。
十進位轉三進位:
先找到距離
$X_{d e c}$ 最近的整數，然後分別對整數部分和小數部分進行連除法和連乘法即可。
以下的例子，在 | 的左邊是整數部份，右邊是小數部份。

如：
- ${9.2}_{d e c 10}$ 最近的整數是
  $9$ ,餘
  $0.2$
  
  $9 \div 3 = 3$ 餘
  $0$
  $|$
  $0.2 \times 3 = 0.6, 最近的整數是 1 ，餘 - 0.4$
  
  $3 \div 3 = 1$ 餘
  $0$
  $|$
  $- 0.4 \times 3 = - 1.2, 最近的整數是 - 1, 餘 - 0.2$
  整數部份已結束
  $|$
  $- 0.2 \times 3 = - 0.6, 最近的整數是 - 1, 餘 0.4$
  整數部份已結束
  $|$
  $0.4 \times 3 = 1.2, 最近的整數是 1, 餘 0.2$
  整數部份已結束
  $|$
  $0.2 \times 3 = 0.6, 最近的整數是 1, 餘 0.4, 進入循環$
  轉換過後，
  ${9.2}_{d e c 10} = 1 \times 3^{2} + 0 \times 3^{1} + 0 \times 3^{0} + 1 \times 3^{- 1} + . . . = 100.1 \overset{―}{T T 11}$

加法器

邏輯真值表

And
(
$a$ ^
$b$ )
$=$ min (
$a$ ,
$b$ )

^	T	0	1
T	T	T	T
0	T	0	0
1	T	0	1

OR
(
$a$ ∨
$b$ )
$=$ max (
$a$ ,
$b$ )

∨	T	1
T	T	1
0	0	1
1	1	1

⊕	T	1
T	T	1
0	0	0
1	1	T

半加器(Balanced Half Adder)

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

$i n p u t a$	$i n p u t c_{i}$	$o u t 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

觀察後可看出

Carry
$c_{i + 1} = (a_{i} ⊠ c_{i})$ ，可以參考 Consensus
Sum
$s_{i} = (a_{i} + c_{i})$ ，可以參考 Sum

另外，也有人使用多工器實現全加器以及半加器，可以參考。

實際應用

找應用的過程中，我找到歷史故事，文章的應用歷史部分有寫到關於三進位計算機的誕生與衰落。

關於區塊鏈的內容，這裡有簡單的說明可以參考，這裡不贅述。
IOTA簡單來說並不是以區塊鏈為根基，有幾項不同之處:

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

簡單介紹完IOTA後，到底跟Balanced Ternary有何關聯呢?
在The Tech Behind IOTA Explained提到，透過ternary JINN processor運行，會讓交易紀錄保持著穩定與平衡。

(原句:These 3 states perform transaction very balanced, which is quite helpful to build a self-organizing and self-sustaining network like the tangle.)

參考資料

Balanced Ternary
三進位
 Adder Implementation
Ternary Computing
The Tech Behind IOTA Explained