2017q3 Homework1 (ternary)

平衡三進位(Balanced Ternary)

平衡三進位，是一種以3為基數以(T,0,1)為基本數位的進位。
T表示-1
0表示 0
1表示 1

• 轉10進位算式
  • 其中a與c以小數點隔開
    
    $$(a_n{a}_{n-1}\cdots a_1{a}_0.c_1{c}_2{c}_3\cdots )=\sum _{k=0}^n{a}_k{b}^k+\sum _{k=1}^{\mathrm{\infty }}{c}_k{b}^{-k}$$
• 轉10進位範例
  • 整數
    
    $${10}_{bal3}=1\times 3^1+0\times 3^0=3_{dec}$$
  • 小數
    
    $${10}_{bal3}=1\times 3^1+0\times 3^0=3_{dec}$$

• 不需要額外的符號就能直接表示負數。因此平衡三進位在加減法和乘法的效率要比二進位高。

• 美國著名電腦學家高德納在《編程的藝術》一書中指出，「也許最美的進位是平衡三進位」

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

×	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多工器

• 多工器腳位介紹
  
  • 由sel決定OUTPUT的電位
• 多工器實現半加法器
  
  • 前半段先計算好結果，後半段再由B決定OUTPUT哪個結果
• 多工器實現全加法器(包含進位)
  
  • 使用兩個半加法實現全加法
• 多工器實現Consensus
  • consensus=-1 , if A=B=-1.
  • consensus= 1 , if A=B= 1.
  • consensus= 0 , otherwise.
    
  • 多工器實現Overflow
    
  • 跟前面的有點像，先配好正確的輸出再從SEL去做選擇，只是變成兩階式的

Reference

Wikipedia-Balanced ternary
Ternary computing: basics