2017q3 Homework1 (ternary)

tags: sysprog2017 dev_record

contributed by <HTYISABUG>

---

解釋 Balanced Ternary 原理

• 解釋 Balanced Ternary 原理

在課程中已經知道知道 Balanced Ternary 是由-, 0, +，3個狀態來表達數字的數值系統。

TODO: 詳細閱讀 Fast Ternary Addition，理解 base-3 的原理 (並且複習數位邏輯)，整理 base-3 基礎運算操作
"jserv"

考慮 136 在 Decimal，Binary，Ternary，Balanced Ternary 的情況

Decimal	Binary	Ternary	Balanced Ternary
$136$	$10001000$	$12001$	$2-00+$

Binary:
$2^7+2^3$
Ternary:
$3^4+2\times 3^3+3^0$
Balanced Ternary:
$2\times 3^4-3^3+3^0$

這樣看下來，Ternary 能用較少位數表達更多位的 binary code
稍微計算一下

• unsigned binary
  • 8 bits: $0-255$
  • 16bits: $0-65535$
• unsigned ternary
  • 5 bits: $0-243$
  • 10bits: $0-59048$

可以得知 5bits ternary 就能大約表達 8bits binary
然後 10bits 大約能表達 16bits binary

再考慮一下浮點數的狀況
以 ternary 表達浮點數
若以 9bits 表達 exponent, 18bits 表達 mantissa
這 27bits 能提供超過 8 位的小數點後精確度
相比之下, binary 32bits 只能提供 5 位

由此可以得知, 採用 ternary 表達數字能縮小所需空間及提升精確度

---

Radix economy

由 ternary 能看出採用比較大的底數能用比較少位數表達一個數
能用多少位表達一個數被稱為 radix economy
那麼是不是底數愈大, radix economy 就越好呢?

計算 radix economy 的公式如下
$E(b,N)=b\lfloor lo{g}_b(N)+1\rfloor$
$b$ 為底數, $N$ 為要表達的數字
將 $N$ 看做常數對 $b$ 微分, 結果為下圖

可以看到 $b$ 的斜率在 $e$ 為 0
所以以 $e$ 當作 base 的話 radix economy 最低

下表為其他 base 與 base-$e$ 比較的結果

base-2 和 base-3 僅次於 base-$e$，而底數越大就越差。
這應該也是採用 Ternary 當數值系統的原因之一。

TODO: 論述方式請參考 Ternary Number Systems 的手法
"jserv"

繼續研讀 What is the most efficient numerical base system?，並依據裡頭的分析，量化上述討論
"jserv"

---

那麼 Balanced Ternary 又是怎麼回事？
Balanced Ternary 的位數表達有時比 Ternary 多
但其價值在考慮到負數的情況下才會體現出來。

考慮 -108 在 Decimal，Binary，Ternary，Balanced Ternary 的情況

Decimal	Binary	Ternary	Balanced Ternary
$-108$	$-1101100$	$-11000$	$--000$

Balanced Ternary 的優點就體現出來了。其他數值系統還至少要多用一位儲存正負，而 Balanced Ternary 是在編碼時就將正負包含進去，這樣一看反而使用位數更少。

基於這樣的特性，Balanced Ternary 在正負轉換時也更簡單，只要將所有的位數都正負互換就行了。這樣的特性不只在整數，浮點數也通用。

請搭配閱讀 三生萬物，裡頭有延伸 radix economy 的思考，也提及 SQL 處理 NaN 時，用到 base-3
"jserv"

---

運算

Add, Sub, Mul, Div

+	$\overline{1}$	$0$	$1$
$\overline{1}$	$\overline{1}1$	$\overline{1}$	$0$
$0$	$\overline{1}$	$0$	$1$
$1$	$0$	$1$	$1\overline{1}$

-	$\overline{1}$	$0$	$1$
$\overline{1}$	$0$	$\overline{1}$	$\overline{1}1$
$0$	$1$	$0$	$\overline{1}$
$1$	$1\overline{1}$	$1$	$0$

$\times$	$\overline{1}$	$0$	$1$
$\overline{1}$	$1$	$0$	$\overline{1}$
$0$	$0$	$0$	$0$
$1$	$\overline{1}$	$0$	$1$

$÷$	$\overline{1}$	$0$	$1$
$\overline{1}$	$1$	$NaN$	$\overline{1}$
$0$	$0$	$NaN$	$0$
$1$	$\overline{1}$	$NaN$	$1$

Ternary Truth Table

Ternary 有三種數值, 在真值表中以:- = false, 0 = unknown, + = true 標記

NOT
F	T
U	U
T	F

AND	F	U	T
F	F	F	F
U	F	U	U
T	F	U	T

OR	F	U	T
F	F	U	T
U	U	U	T
T	T	T	T

3 張真值表分別可以對應到 NEG, MIN, MAX 操作

---

Ternary 電路實作

Ternary computing: basics 的作者設計了以 balanced ternary 運作的計算電路
以 3 個輸入的 multiplexer 為基礎

藉由改變輸入訊號能得到不同的結果

Unary Function

作者先定義了幾個單一輸入元的 function

• increment
• decrement
• max(x, 0)
• min(x, 0)

Half Adder

再來要以 ternary multiplexer 與以上 function 實作出 half adder
half adder 真值表如下

A \ B	$\overline{1}$	$0$	$1$
$\overline{1}$	$1$	$\overline{1}$	$0$
$0$	$\overline{1}$	$0$	$1$
$1$	$0$	$1$	$\overline{1}$

先代入把情況列出來看看: A+-1, A+0, A+1
可以化簡成 A-1, A, A+1
所以至少有個以 B 為選擇訊號的 mux (mux B) 對應這三種狀況
再把這三種狀況以定義好的 function 代入就能得到下圖

Consensus

若要兜成 full adder, 除了 half adder 還需要計算 carry
carry 真值表如下

A \ B	$\overline{1}$	$0$	$1$
$\overline{1}$	$\overline{1}$	$0$	$0$
$0$	$0$	$0$	$0$
$1$	$0$	$0$	$1$

用思考 half adder 的方式來看
對應 mux B 的三種情況為 min(A, 0), 0, max(A, 0)
同樣以 function 代入得下圖

Full Adder

Binary 的 full adder 是由兩個 half adder 組合成的
Ternary full adder 不太一樣
Full adder 分層運作:

1. 以 A 為 selector 計算
2. 以 B 為 selector 計算
3. 以 C 為 selector 計算
   每一層的 input 都會取自前一層的結果, 第一層是常數
   
   綠色部份是一個 half adder
   不只這一部份, 其實每層之間都是幾個 half adder 交錯排列

至於為什麼不像 binary adder 那樣用 xor, and 來實作
列出真值表就知道了…
And 前面已列出

xor	$\overline{1}$	$0$	$1$
$\overline{1}$	$\overline{1}$	$0$	$1$
$0$	$0$	$0$	$0$
$1$	$1$	$0$	$\overline{1}$

xor 跟 add, and 跟 carry 所需的數值完全不同
所以 $sum=x\oplus y,carry=x\mathrm{\&}y$ 這套在 ternary 行不通

Overflow

跟 full adder 一樣是分層運作

綠色部份同樣是一個取進位的電路, 每層也都是交錯排列

請閱讀 Ternary computing: basics，關注於 ternary multiplexer, Unary functions, half-adder, Consensus, full adder, Overflow
"jserv

---

Balanced Ternary 的設計要解決什麼類型的問題

• Balanced Ternary 的設計要解決什麼類型的問題，需要詳述實際應用案例 (如 IOTA/Tangle)。提示：從算術表達的精準度和空間使用效率去探討

---

在 GitHub 裡頭可找到的應用案例

• 針對特定的領域 (如加密貨幣)，列出在 GitHub 裡頭可找到的應用案例，不僅列出程式碼，還要解說

---

參考資料

• Balanced ternary (wikipedia)
• Radix economy (wikipedia)
• Ternary Number Systems
• Ternary computing: basics