tags: homework sysprog2017

2017q3 Homework1 (ternary)

contributed by <Jetudie>

---

題目： C01: Ternary

Balanced Ternary 簡介

What's Ternary ?

也可稱為 three-valued logic。Ternary 用三個真值 (truth value) 表示

$true$ 和

$false$ ，還有第三個「不確定值」(indeterminate value)。

Ternary 中又有各種不同的數值表示法 (Representation of values)，例如：

truth value	unsigned	balanced
false	0	-
unknown	1	0
true	2	+

–from Fast Ternary Addition

---

Efficiency

ternary 與 binary 相比

Fast Ternary Addition 寫道 "A single digit in number base

$b$ carries

$lo{g}_{2}b$ bits of information. Thus, each ternary digit or trit carries about 1.58 bits, as compared to 3.32 bits per decimal digit."

試著算算看 ternary (base 3)

$2^b=3^t$

$b\times log2=t\times log3$

$b/t=lo{g}_{2}3\approx 1.58$

decimal (base 10) 作法也相仿

$b/d=lo{g}_{2}10\approx 3.32$

但這又代表著什麼？ base 越大就表示起來就越有效率？

Base

$e$ 最「經濟」

• 以下，是根據 What is the most efficient numerical base system? 解釋，為何在 Non-integer representation 中提到，以
  $e$ 作為基數 (base/radix) 是比 1 大的基數中最「經濟」的選擇：

1. 假設有 V 個獨立狀態 (independent state) 的資訊， 可以 base-N 表示成
   $V/N$ 個位元 (digit)
2. 可表示的資訊量為
   $I=N^{V/N}$
3. 最「經濟」的 base 就是能使
   $I$ 最大的
   $N$ 值
4. 對等號兩邊取自然對數
   $ln(I)=(V/N)ln(N)$
5. 等號兩邊對
   $N$ 微分
   $(ln(I){)}^{\prime }=(V/N^2)(1-ln(N))$
6. 做第二次對
   $N$ 微分
   $(ln(I){)}^{″}=(V/N^3)(2ln(N)-3)$
7. 當
   $N=e$ ,
   $ln(I)$ 為極值，
   $(ln(I){)}^{\prime }=0$
8. 當
   $N=e$ ,
   $(ln(I){)}^{″}=-1/N^3$ 為負
9. 因此，
   $N=e$ 時，
   $I$ 有最大值(最為「經濟」)

• radix economy 中定義在給定的 base b 對於數值 N 的 radix economy
  
  $E(b,N)=b\lfloor {\log }_b(N)+1\rfloor$ 即
  
  $E(b,N)=b\times (\mathrm{表}\mathrm{示}N\mathrm{所}\mathrm{需}\mathrm{的}\mathrm{位}\mathrm{元}\mathrm{數})$
  
  $E(b,N)$ 愈小，代表以 base b 表示 N 的效率越高

---

Balanced Ternary

Balanced ternary 用 "trit" ， 也就是 -1 , 0 , 1 表示數值，也常以- , 0 , + 或 T , 0 , 1 代替，其特點在於不須另外加負號就能表示所有整數。

與十進位之間的轉換

$$\begin{gathered} \mathsf{10}{\mathsf{T}}_{\mathsf{bal}\mathsf{3}}\mathsf{=}\mathsf{1}\times {\mathsf{3}}^{\mathsf{2}}\mathsf{+}\mathsf{0}\times {\mathsf{3}}^{\mathsf{1}}\mathsf{+}\mathsf{(}\mathsf{-}\mathsf{1}\mathsf{)}\times {\mathsf{3}}^{\mathsf{0}}\mathsf{=}{\mathsf{3}}_{\mathsf{dec}} \\ \mathsf{-}{\mathsf{9}}_{\mathsf{dec}}\mathsf{=}\mathsf{-}\mathsf{1}\times {\mathsf{3}}^{\mathsf{2}}\mathsf{+}\mathsf{0}\times {\mathsf{3}}^{\mathsf{1}}\mathsf{+}\mathsf{0}\times {\mathsf{3}}^{\mathsf{0}}\mathsf{=}\mathsf{T}{\mathsf{00}}_{\mathsf{bal}\mathsf{3}} \\ \mathsf{-}\mathsf{2}\mathsf{/}{\mathsf{3}}_{\mathsf{dec}}\mathsf{=}\mathsf{-}\mathsf{1}\mathsf{+}\mathsf{1}\mathsf{/}\mathsf{3}\mathsf{=}\mathsf{-}\mathsf{1}\times {\mathsf{3}}^{\mathsf{0}}\mathsf{+}\mathsf{1}\times {\mathsf{3}}^{\mathsf{-}\mathsf{1}}\mathsf{=}\mathsf{T}{\mathsf{.1}}_{\mathsf{bal}\mathsf{3}} \end{gathered}$$

再來看看 3-trit ternary numbers

$$\begin{array}{clcl}decimal& bal3& decimal& bal3\\ -13& ---& 13& +++\\ -12& --0& 12& ++0\\ -11& --+& 11& ++-\\ -10& -0-& 10& +0+\\ -9& -00& 9& +00\\ -8& -0+& 8& +0-\\ -7& -+-& 7& +-+\\ -6& -+0& 6& +-0\\ -5& -++& 5& +--\\ -4& 0--& 4& 0++\\ -3& 0-0& 3& 0+0\\ -2& 0-+& 2& 0+-\\ -1& 00-& 1& 00+\\ & & 0& 000\end{array}$$

觀察一下會發現：
如果要知道一個數的負數的相反數(opposite number)只要把 bal3 表示的 + 跟 - 反過來即可

–from Hackaday 10th Anniversary: Non-Binary Computing

---

Half Adder and Full Adder

Sum

回顧一下，在 Boolean Logic 中，我們以 xor 來表示兩個 1-bit binary 相加和 (sum)；但在 Balanced ternary 的 xor 則不會算出 sum。
但有另外定義一個 sum operator 表示如下：

$\begin{array}{ccccc}& & & b& \\ & c& T& 0& 1\\ & T& 1& T& 0\\ a& 0& T& 0& 1\\ & 1& 0& 1& T\end{array}$

說明：
0 加任何數，就等於此數本身
1 跟 T 相加為 0
T 加 T 會是 T1 ( carry = T, sum = 1 )
1 加 1 會是 1T ( carry = 1, sum = T )

Consensus

若兩者皆為 T 則為 T ，兩者皆為 1 則為 1 ，其餘皆為 0 。類似於 binary 中的 and 。

$\begin{array}{ccccc}& & & b& \\ & c& T& 0& 1\\ & T& T& 0& 0\\ a& 0& 0& 0& 0\\ & 1& 0& 0& 1\end{array}$

Accept Anything

和 consensus 相對應的 operator 為 accept anything (或 gullibility)。 consensus 除了接收到兩個相同的

$true$ 或

$false$ 才能確定為其一，其餘皆輸出

$unknown$ ； accept anything 則只會在都是

$unknown$ 或是一個

$true$ 和一個

$false$ 時，才輸出

$unknown$ 。

$\begin{array}{ccccc}& & & b& \\ & c& T& 0& 1\\ & T& T& T& 0\\ a& 0& T& 0& 1\\ & 1& 0& 1& 1\end{array}$

Balanced Half Adder

半加器的真值表 (truth table)

$\begin{array}{ccc}input& & output\\ a_i& c_i& c_{i+1}& s_i\\ T& T& T& 1\\ T& 0& 0& T\\ T& 1& 0& 0\\ 0& T& 0& T\\ 0& 0& 0& 0\\ 0& 1& 0& 1\\ 1& T& 0& 0\\ 1& 0& 0& 1\\ 1& 1& 1& T\end{array}$

Balanced Full Adder

若依照 binary 的方法，以兩個 half adder 建構一個 full adder

會發現 c_a 跟 c_b 不會出現同時為 T 或同時為 1 的情況

$\begin{array}{ccccc}& & & c_b& \\ & c& T& 0& 1\\ & T& & T& 0\\ c_a& 0& T& 0& 1\\ & 1& 0& 1& \end{array}$

必須進行優化 (optimization)，但優化後會變成複雜的形式。若我們只考慮複雜度，並且使用 ripple-carry logic ， balanced ternary 並非做一個三進位 ALU 的首選。

–from Standard Ternary Logic

---

Application on Solving Problems

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