2017q3 Homework1 (ternary)

contributed by <Lihikoka>

Balanced Ternary (平衡三進位) 介紹

Balanced ternary 是一種三進位 (Ternary) 的數值表示法，在三進位中，一個十進位的數

$n$ 可以表示為

$n=\sum _{n}a\cdot 3^n,a=0,1,2$ ，但 balanced ternary 與一般 ternary 不同的是

$a=T(-1),0,1$ ，其整數與分數的表示法都跟二進位一樣，但是在表示一個數的負數時較二進位方便。詳見以下：

• 二進位：
  
  $(6{)}_{10}=(0110{)}_2$
  
  $(-6{)}_{10}=(1010{)}_2$
• 平衡三進位：
  
  $(6{)}_{10}=(1T0{)}_{bal3}=1\cdot 3^2+(-1)\cdot 3^1+0$
  
  $(-6{)}_{10}=(T10{)}_{bal3}=(-1)\cdot 3^2+(1)\cdot 3^1+0$

由以上可知在 balanced ternary 中要取一個數的負數只要將全部的位元乘以

$-1$ 即可，比二進位的負數操作快速、簡單。

運算真值表

以下使用 - 代表

$T$ ，+ 代表 1 ，看起來較直覺。

• Inverter

in	out
-	+
0	0
+	-

• Min or And
  
  $c=(a$ ∧
  $b)=min(a,b)$

c	-	0	+
-	-	-	-
0	-	0	0
+	-	0	+

• Max or Or
  
  $c=(a$ ∨
  $b)=max(a,b)$

c	-	0	+
-	-	0	+
0	0	0	+
+	+	+	+

Hardware Implementation

• 最基本的 building block： ternary multiplexer
  

Unary functions

• Increment
  

• Decrement
  

• max(A, 0)
  

• min(A, 0)
  

加法器

終於要進入最重要的加法器了，關於二進位 half adder 和 full adder 的部份可參考 Wikipedia。

Half adder

在建構 half adder 之前，我們首先需要寫出 sum 和 carry 的 truth table，再使用 basic building block (ternary multiplexer) 做出我們要的電路。

• Sum
  Truth table 很直覺，跟二進位較不同的地方為 A = -1, B = -1 以及 A = 1, B = 1 的地方。

• Carry
  可用 Consensus 來實現，中文為「共識」的意思，也就是只有在兩個輸入都是 -1 或 +1 時輸出才不為 0 ，其他的輸入值組合輸出都是 0，正好符合 carry 的性質：「沒進位時為 0 ，須進位時為高一位的值」。

Full adder

做出 half adder 之後，接下來當然要往 full adder 作延伸

• Sum
  圖中綠色範圍框起來的是 half adder 的 sum。

• Carry
  圖中綠色範圍框起來的是 consensus。
  

應用案例

IOTA / Tangle

• 加密貨幣之爭 Blockchain v.s. Tangle

	Blockchain	Tangle
Miners	O	X
Fees	O	X
Blocks	O	X
Hard/Soft Fork	O	X
Distributed Consensus	O	O
HashCash	O	O

• Tangle 的優勢
  Scalability
  Quantum Security
  Offline Capability

• Tangle

Reference

The Ternary Manifesto
Ternary-computing: basics
IOTA BREAKDOWN: The Tangle Vs. Blockchain Explained