2017q3 Homework1 (Ternary)

contributed by < BreezeDa >

作業要求

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

Wed, Oct 2, 2017 1:52 PM 1st version

Ternary

在講到 Balanced Ternary 之前我們先簡介一下 ternary，ternary 是以 3 為基數的進位方式，中文稱為三進制，我們知道 binary 使用 0,1 表示一個數字，而在 ternary 中我們則使用 0,1,2 來表示一個數字。下方是個 10 進位轉三進位的說明。

Balanced Ternary

簡介

Balanced Ternary 與 ternary 不同，數值表示不使用 0, 1, 2 ， 而是 -1, 0, 1 ( 亦可標示為 T, 0, 1 或 -, 0, + )。而且由於 -1 的引入，這種進位不需要額外的符號就能直接表示負數。下方我們 基數符號使用 b3 表示 balanced ternary

數值表示

整數

decimal	balanced ternary
-7	T1T , -+-
-5	T11 , -++
-2	T1 , -+
2	1T , +-
5	1TT , +--
7	1T1 , +-+

解析

$-7_{10}=T1T_{b3}=-1\times 3^2+1\times 3^1+-1\times 3^0$

$5_{10}=T1T_{b3}=1\times 3^2+-1\times 3^1+-1\times 3^0$

小數

decimal	balanced ternary
-0.5	$\overline{0.T}$ or $\overline{T.1}$
-0.4	$\overline{0.TT11}$
-0.1	$\overline{0.0T01}$
0.1	$\overline{0.010T}$
0.4	$\overline{0.11TT}$
0.5	$\overline{0.1}$ or $\overline{1.T}$

解析

• 一開始看到

  ${0.5}_{10}={\overline{0.1}}_{b3}$，還沒搞明白這兩個是怎麼個相等法，後來看到benson326用等比級數的公式算一遍才頓悟。以下則是計算
  ${0.4}_{10}=\overline{0.11TT}$ :
  $$\begin{gathered} {\overline{0.11TT}}_{b3}=1\times 3^{-1}+1\times 3^{-2}-1\times 3^{-3}-1\times 3^{-4}+1\times 3^{-5}+1\times 3^{-6}-1\times 3^{-7}-1\times 3^{-8}+... \\ =3^{-1}+3^{-5}+3^{-9}+... \\ {3}^{-2}+3^{-6}+3^{-10}+... \\ -(3^{-3}+3^{-7}+3^{-11}+...) \\ -(3^{-4}+3^{-8}+3^{-12}+...) \end{gathered}$$
  $={\displaystyle \frac{3^{-1}}{1-{\displaystyle \frac{1}{3^4}}}}+{\displaystyle \frac{3^{-2}}{1-{\displaystyle \frac{1}{3^4}}}}-{\displaystyle \frac{3^{-3}}{1-{\displaystyle \frac{1}{3^4}}}}-{\displaystyle \frac{3^{-4}}{1-{\displaystyle \frac{1}{3^4}}}}={0.4}_{10}$

• 由以上整數與小數的表示中可以看出正數與負數之間的轉換，其實只要將 1 轉成 T ，T 轉成 1 就可

運算

latex 表格參考 as23041248 並增加減法，並分別給予一個計算範例

加法

$$\begin{array}{cccc}ADD& T& 0& 1\\ T& T1& T& 0\\ 0& T& 0& 1\\ 1& 0& 1& 1T\end{array}$$

e.g.

$T1TT+1T1$

$$\begin{array}{cccc}& & & T\\ & & T& 1& T& T\\ & +& & 1& T& 1\\ & & T& 1& 1& 0\end{array}$$

$T+T=T1$ 我將 T 寫下一位上方

減法

$$\begin{array}{cccc}SUB& T& 0& 1\\ T& 0& T& T1\\ 0& 1& 0& T\\ 1& 1T& 1& 0\end{array}$$

左欄減頂列

e.g.

$T11T-11TT$

$$\begin{array}{cccccc}& & & & & T\\ & & & T& 1& 1& T\\ & -& & 1& 1& T& 1\\ & & T& 1& 0& 1& 1\end{array}$$

$T-1=T1$ 我將T寫在第二位的上方 => 第二位(由右往左數)

$T+1-T=1$

乘法

$$\begin{array}{cccc}MUL& T& 0& 1\\ T& 1& 0& T\\ 0& 0& 0& 0\\ 1& T& 0& 1\end{array}$$

e.g.

$T1T\times 1T$

$$\begin{array}{cccccc}& & & T& 1& T\\ & \times & & & 1& T\\ & & & 1& T& 1\\ & +& & T& 1& T\\ & & T& 1& 1& 1\end{array}$$

效率

由 Ripple Adder in Binary and Ternary Logic 可以看出在 ripple adder 中同樣的運算，ternary logic 比標準 binary 來得快

「所以應該」？這是理工人說的話嗎？

參考資料

wikipedia: blanced ternary
Ternary numeral system