2017q3 Homework1 (ternary)

contributed by <jeff60907>

tags: jeff60907

作業要求

C01: Ternary
研讀 Balanced Ternary，並依據 課前測驗參考解答: Q1 的風格和探討方式，涵蓋以下:

• 解釋 Balanced Ternary 原理;
• Balanced Ternary 的設計要解決什麼類型的問題，需要詳述實際應用案例 (如 IOTA/Tangle)。提示：從算術表達的精準度和空間使用效率去探討;
• 針對特定的領域 (如加密貨幣)，列出在 GitHub 裡頭可找到的應用案例，不僅列出程式碼，還要解說;
• 在研究的過程中，應該會對既有工具進行修改或者重新開發 (不限程式語言)，也該一併指出，程式碼應該維護在 GitHub 上;

Latex 參照來源

Balanced ternary

閱讀Fast Ternary Addition理解 base-3 的原理

Balanced Ternary 是一個屬於(base 3)的數值系統，他的值為 -1, 0, +1 不需要額外的符號位元表示正負即可代表整數系，而在 standard unsigned (unbalanced) ternary 中表達方式為 0, 1 , 2，Balanced Ternary 的邏輯電路實現相較於一般的 unsigned ternary 更為複雜。在內文提到 base-b 的 single digit 為

$lo{g}_{2}b$ bits 的訊息量，在 ternary number system 中存放的訊息量為

$lo{g}_{2}3$ 是二進制的 1.58 倍，十進制的 3.32倍

在 Kleene邏輯中，Ternary 被分為三種 true , false , unknown，真值表的內容為以下

truth value	unsigned	balanced
false(F)	0	-
unknown(U)	1	0
true(T)	2	+

使用 Bal3 表示 -3 ~ +3
-3 , -2 , -1 , 0 , 1 , 2 , 3
0-0,0-+,00-,000,00+,0+-,0+0

Balanced Ternary 數值轉換 (bal3 / dec)

參考 Balanced ternary wikipedia
數值的轉換與過去所學二進制/十進制的概念相同，其中-1, 0, +1 代表T, 0, 1 也代表是false , unknown , true，若數值 1-T = 1T，(3¹-1)，反之 T1 ((-1)x3¹+1)

dec 與 bal3轉換

${10}_{bal3}=1\times 3^1+0\times 3^0=3_{dec}$

$10T_{bal3}=1\times 3^2+0\times 3^1+(-1)\times 3^0=8_{dec}$

$-9_{dec}=(-1)\times 3^2+0\times 3^1+0\times 3^0=T{00}_{bal3}$

$T0T{0}_{bal3}=(-1)\times 3^3+0\times 3^2+(-1)\times 3^1+0\times 3^0=-{30}_{dec}$

浮點數的運算

$1.{\overline{T11T}}_{bal3}=1\times 3^0+(-1)\times 3^{-1}+1\times 3^{-2}+1\times 3^{-3}+(-1)\times 3^{-4}={0.8}_{dec}$

${0.2}_{dec}=1\times 3^{-1}+(-1)\times 3^{-2}+(-1)\times 3^{-3}+1\times 3^{-4}=0.{\overline{1TT1}}_{bal3}$

Balanced Ternary 四則運算

Addition

+	T	0	1
T	T1	T	0
0	T	0	1
1	0	1	1T

Subtraction

−	T	0	1
T	0	T	T1
0	1	0	T
1	1T	1	0

Multiplication

x	T	0	1
T	1	0	T
0	0	0	0
1	T	0	1

Division

÷	T	0	1
T	1	NaN	T
0	0	NaN	0
1	T	NaN	1

了解一些 Balanced Ternary Logic Functions

參考Ternary-computing:-basics
使用 ternary multiplexer 進行邏輯電路

當multiplexer sel 輸入依序為-1,0,1時，output為 inN, inO, inP

當multiplexer sel 輸入依序為-1,0,1時，input 0, 1, -1，對照 output為 0, 1, -1，可當成 (A+1)

當multiplexer sel 輸入依序為-1,0,1時，input 1, -1, 0，對照 output為 1, -1, 0，可當成 (A-1)

當multiplexer sel 輸入依序為-1,0,1時，input 0, 0, 1，對照 output為 0, 0, 1，可當成 max(A,0)

當multiplexer sel 輸入依序為-1,0,1時，input -1, 0, 0，對照 output為 -1, 0, 0，可當成 min(A,0)

• 使用基本邏輯單元進行 半加器 half-adder A+B
  

  
  A + B 的結果
  B=-1 選擇輸出為 A-1，等於A+(-1)=A-1
  B=0 選擇輸出為 A，等於A+(0) = A
  B=1 選擇輸出為 A+1，等於A+(1) = A+1

• consensus function consensus
  如果 A,B=-1 輸出 -1, A,B=1 輸出 1，其他皆為 0
  

  
  A=-1 min(A,0)=-1 , A=1 max(A,0)=1 ,otherwise = 0
  當 B =-1, A=-1時 , 輸出為-1
  當 B =1, A=1時, 輸出為1