2017q3 Homework1 (ternary)

contributed by <function86437>

Ternary numeral system

Ternary 是一個三進制的系統，又稱為 (base-3) ，儲存資料的位元稱為 trit (trinary digit) ，對比二進制的 bit ，在 ternary 中因表示法的不同又分為 unsigned ternary 與 balanced ternary ，對應的表示法為 0, 1, 2 與 -1, 0, +1 (T, 0, 1) 。

• [wikipedia-Balanced ternary]中討論在二進制中 n bits 能表示的最大數字為
  $2^n$ -1，那 ternary n bits 能表示的最大數字是否為
  $3^n$-1呢？
  給定一個數字為
  $N(b,d)$ ,其中 b 為基底 d 為次方，給個單位能表示最大數為 b-1 。
  
  $N(b,d)=(b-1)b^{d-1}+(b-1{)}^{d-2}+...+(b-1{)}^1+(b-1{)}^0,$
  
  $N(b,d)=(b-1)(b^{d-1}+b^{d-2}+...+b^1+1),$
  
  $N(b,d)=(b-1)M.$
  
  $bM=b^d+b^d-1+...+b^2+b^1,and$
  
  $-M=-b^{d-1}-b^{d-2}-...-b^1-1,so$
  
  $bM-M=b^d-1,or$
  
  $M=(b^d-1)/(b-1).Then$
  
  $N(b,d)=(b-1)M,$
  
  $N(b,d)=(b-1)(b^d-1)/(b-1),and$
  
  $N(b,d)=b^d-1.$
  例如：
  $N(3,3)=3^3-1=26=2\times 3^2+2\times 3^1+2\times 3^0=18+6+2$

Balanced Ternary

balanded ternary 的表示法為 -1, 0, 1，可以表示所有的整數，而且不需要額外的位元儲存正負號。

例如：

$-9_{dec}=T{00}_{bal3}$
最左邊的第一個非零項本身就包含正負號。

$-9_{dec}=-1\times 3^2+0\times 3^1+0\times 3^0=T{00}_{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}$

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

${\frac{-2}{3}}_{dec}=-1+\frac{1}{3}=-1\times 3^0+1\times 3^{-1}=T{.1}_{bal3}$
但在遇到某些浮點數的時候，會出現有不只一種表示法。
例如：

$-{0.5}_{dec}=-1\times \frac{1}{3}+-1\times \frac{1}{9}...=0.{\bar{T}}_{bal3}$
又可表示為

$-{0.5}_{dec}=-1+{0.5}_{dec}=T+0.{\bar{1}}_{bal3}=T.{\bar{1}}_{bal3}$

Ternary 基本運算

在真值表上 Ternary 相較於 Bianry 多了一個 unknown 的值，對應-1,0,1 如下表：

truth value
true	+
unknown	0
false	-

在Ternary computing介紹中，下圖的 ternary multiplexer 取決於輸入 A 的訊號，輸出相對應值，例如：當 A=-1 輸出 pin腳 N ， A=0 輸出 pin腳 O， A=1 輸出 pin腳 P ，會根據 N,O,P數值不同，而有不同的功能，是一個unary functions

這是一個輸出 A = A + 1 與 A = A - 1 的功能

計算 A 與 0 的最大值、最小值

三個 multiplexer 可以實做出一個 half adder，這邊可以發現第二層的 N,O,P 數值是由前面運算完後的結果決定的。

從右邊真值表不難看出只有在 A,B同時為-1時輸出-1與 A,B同時為1時輸出1，其餘為0，這個電路可作為之後判斷進位的功能。

全加器類似二元運算中的全加器，都是由兩個半加器組成

overflow 的電路看起來很複雜，但以 Cout 的結果回推回來就比較容易理解，考慮進位 Cin 的輸入:

• 若 Cin=-1，A, B三種狀況
  • A=-1且 B=0
  • A=0 且 B=-1
  • A=-1 且 B=-1
• 若 Cin=0， A,B必同時為-1或1
• 若 Cin=1， A, B三種狀況
  • A=1 且 B=0
  • A=0 且 B=1
  • A=1 且 B=1

Balanced Ternary 實際應用：

重點

• b3k 可接受10 進位輸入範圍
• 實驗對照程式碼
• balanced ternary

參考資料

• wikipedia-Ternary numeral system
• wikipedia-Balanced ternary
• Standard Ternary Logic