2017q3 Homework1 (ternary)

contributed by < maskashura >

筆誤! 正確書寫方式為 balanced ternary ，注意到 balance 後面接著 "d" 字母
"jserv"

Ternary (三進位)

Ternary 如同我們熟悉的 10 進位、2 進位方式，它是一種以 3 為基數 (3-base,(

$x\times 3^0+x\times 3^1+x\times 3^2$…)) 的進位，逄 3 進位，以 0,1,2 為表示的進位方式
其表示如下:

Dec	Ternary
0	000
1	001
2	002
3	010
4	011
5	012
6	020
7	021
8	022
9	100

而其負數型態則是在位數前加一負號表示
其表示如下:

Dec	Ternary
-0	-000
-1	-001
-2	-002
-3	-010

可以發現 ternary 在負數表示上仍需要多一位元做為負數型態的表示

接下來我們將介紹來自蘇聯的黑科技 Balance ternary

英文、數字與中文字間請以空白隔開
課程助教

---

Balanced ternary (平衡三進位)

對於 balanced ternary 最令人難忘的描述是來自 Donald Knuth 於其著作 The Art of Programming 中的一段:

Perhaps the prettiest number system of all… is the balanced ternary notation.

相較 Ternary 以 0,1,2 表示不同的地方在於 Ternary以-1(以下用T表示）,0,1為基本數位(trit)的表示。
(Balanced ternary在下面將縮寫Bal3做表示)

Dec	Bal3	Expansion
0	0	0
1	1	1
2	1T	3-1
3	10	3
4	11	3+1
5	1TT	9-3-1
6	1T0	9-3
7	1T1	9-3+1
8	10T	9-1
9	100	9
10	101	9+1

Balanced ternary 的負數表示

Balanced trinary 最令人讚嘆的地方之一在於其負數表示及運算，其負數型態可以將原本正值的地方用-1(T)直接取代，即可得到負數型態(如

$2_{Dec}$=

$1T_{Bal3}$ ,而

$-2_{Dec}$ =

$T{1}_{Bal3}$)，這種進位不需要額外的符號就能直接表示負數。使得 balanced ternary 在加減法和乘法方面的效率要比二進位高。

Dec	Bal3	Dec	Bal3
0	0	0	0
-1	T	1	1
-2	T1	2	1T
-3	T0	3	10
-4	TT	4	11
-5	T11	5	1TT
-6	T10	6	1T0
-7	T1T	7	1T1
-8	T01	8	10T
-9	T00	9	100
-10	T0T	10	101

其轉換公式表示如下:
(

$a_n$

$a_{n-1}$…

$a_2$

$a_1$.

$c_1$

$c_2$

$c_3$…

${)}_b$=

$\sum _{k=1}^n$

$a_k$

$b^k$+

$\sum _{k=1}^{\mathrm{\infty }}$

$c_k$

$b^{-k}$

b is the original radix. b is 10 if converting from decimal.

EX:
e.g.

example 的縮寫是 e.g.，而非 "ex"，後者是「前」女友、「前」雇主用語，不要誤用
"jserv"

$-{25.4}_{dec}$

$=-(1T\times {101}^1+1TT\times {101}^0+11\times {101}^{-1})$

$=-(1T\times 101+1TT+11÷101)$ ->參考Bal3的四則運算

$=-10T1.\overline{11TT}$

$=T01T.\overline{TT11}$

---

Balance ternary 的四則運算

而 Balance 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

我們舉一簡單的例子:

${0.5}_{dec}=0.{\bar{1}}_{bal3}$ or

$1.{\bar{T}}_{bal3}$

1).

​​​​                0.111111111… 
​​​​                -----------------
​​​​           1T  )1                   
​​​​                1T
​​​​                -----
​​​​                 10                      
​​​​                 1T
​​​​                 ---
​​​​                  10 
​​​​                   .
​​​​                   .
​​​​                   ......(LOOP) 

故我們可得

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

2).

​​​​                1.TTTTTTTTT… 
​​​​                -----------------
​​​​           1T  )1                   
​​​​               1T
​​​​               -----
​​​​                T0                      
​​​​                T1
​​​​                ---
​​​​                 T0 
​​​​                   .
​​​​                   .
​​​​                   ......(LOOP)

我們可得到 0.5 可表示為

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

---

Balance ternary 的邏輯運算及加法器

Min / AND

當兩個輸入都為+時則輸出為+,若任何輸入為-或0(unknown)時則否;同時此運算可看作為最小值輸出

圖片來源

Max / OR

當兩個輸入其中有一者為+時則輸出為+,若兩個輸入皆為-或0(unknown)時則否;同時此運算可看作為最大值輸出

圖片來源

Exclusive OR / XOR

若輸入相同則為+,否則輸出為-(若輸入為0/unknown則輸出0)

圖片來源

Sum

如同布林運算中用XOR計算二個二進位值的和;但在些和XOR不同處在於其輸入有0(unknown)時的狀態

圖片來源

Consensus

當輸入狀態一致時則輸出輸入狀態值,否則輸出0(unknown)

圖片來源

Accept Anything

當輸入一端為+/-另一端為0時則輸出對應輸入值的+/-,若輸入相同時則輸出同輸入值;而當輸入兩端一端+一端-時則輸出0(unknown)

圖片來源

有了上述幾組balanced ternary的運算後我們開始可以組合出半加器及全加器

Balanced ternary half adder

很類似在布林運算中看的到半加器, 和為

$s_i$=

$c_i$+

$a_i$ , 進位值為

$c_{i+1}$ = (

$a_i$ ⊠

$c_i$ )

半加器真值表如下:

圖片來源

Balanced Full Adder

全加器二個半加器組合而成,最後再用一個Accept anything做進位值輸出

全加器真值表如下:

如同布林運算一般,完成全加器後可以組全成 4 trit ripple-carry adder

圖片來源

---

思考問題:

Balance trinary看起來在空間利用率(參考HTYISABUG同學共筆中所提及的Radix Economy)及運算的靈活性，但…如何在目前電腦架構中用logic gate實作High, low, NaN出來呢?

出處呢？ "jserv"

參考"Suggestions for Ternary Computer Parts",我們可以得知如何以MOS組成出基本的 ternary logic gate , 我們列出 NAND 及 NOR Gate 如下:

A Ternary NOR
Truth Table:

A	B	out
0	+	-
0	-	+
+	-	0
+	+	-
-	-	+

A Ternary NAND
Truth Table:

A	B	out
0	+	0
0	-	0
+	-	0
-	-	+
+	+	-
Bruce Ke

---

在wikipedia中有關"三進位電腦中資訊的表示"有下面這一段描述:

三進位電腦中，以平衡三進位為資訊進行編碼。
我們可以以12位元為單位，對文字進行編碼作為標準資訊交換碼（STUCII，Standard Ternary Unified Code for Information Interchange）。其容量為53'1441個字元，約是16bits容量的8.1倍。

如何計算出來呢？請用繁體中文和台灣慣用術語書寫 "jserv"

$\mathrm{比}\mathrm{較}\mathrm{二}\mathrm{進}\mathrm{位}\mathrm{及}\mathrm{平}\mathrm{衡}\mathrm{三}\mathrm{進}\mathrm{位}\mathrm{之}\mathrm{資}\mathrm{料}\mathrm{編}\mathrm{碼}\mathrm{容}\mathrm{量},3^{12}/2^{16}=8.11...,\mathrm{即}\mathrm{為}\mathrm{文}\mathrm{中}\mathrm{提}\mathrm{及}\mathrm{的}8.1\mathrm{倍}$ Bruce Ke

---

針對上面幾個問題, 在網路上其實己經有不少答案及教學, 我將內容摘要並附上連結如下:

1).
有解說Balanced ternary的基本原理 , 其中有及 Ternary 在當時為何被開發出來(相較二進位元, 同樣的位元數,三進位可表示的範圍較廣)及它當能在真空管時代所佔的優勢! 及到了電晶體時代, 這種電腦為何又被淘汰(電晶體相較真空管穩定且在半導體製程上實現及微縮)

由於網路上找不太到有關真空管應用在ternary上的文獻,故我整理我的推論如下:

1. Balanced ternary 較 binary 在設計上以相同邏輯運算,能以相同的真空管數完成較多的位元運算(Suggestions for Ternary Computer Parts) ,故在真空管的時代三進制計算機能有較低的耗能及較快的運算能力。

2. 此時有另一個問題,為什麼這樣低的耗能及較快的運算能力的 ternary 為何沒被用在電晶體,整理幾個可能如下:

• 在 MOS 上要實現 3種電壓 level 狀態 由於 drain 極上需再串電阻分壓而造成靜態功耗額外的能耗, 且因為輸出電阻不再接近0,fin-out能力下降

• 由於 ternary 需要3種電壓 level 做為位元狀態, 會造成雜訊容忍度下降( threshold level 範圍更窄)

• 抗共模雜訊能力較差

• 資料,介面,指令集集需重新編制( binary 轉 ternary ), 由於目前計算機普遍由binary資料組成, 這轉換將會是最大障礙

• IC layout 佈局由於需多一組電壓,會造成layout難度上昇及電晶體空間密度下降

參考來源

2).
在這部影片中更清楚的可以看到在, 在表達一 6-bit equivalent full ripple adder 時， Balanced Ternary 如何以較少的位元表示及較短邏輯運算時間完成同樣的算數運算!

---

作業問題:

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

總結上述 Balanced ternary 的優點, 我們可歸結出下面幾點

1.用較少的位數表示較大的數值範圍

由IOTA的介紹,我們可以知道, Balanced ternary 在相同位元下, 能較 binary 表示的範圍大, 以IOTA來說, 如要表示其發行貨幣量, 在 Balanced ternary 僅需33位元, 但以 binary 表示則需要高達52位元,大大的節省了儲存空間的位元量.

它目前的主要功能是 無需手續費的微支付 和 安全的資料轉移以及資料錨定 ，具有良好的擴充套件性和分割槽容錯特性。其總供應量約為 2780萬億 個（確切數字是（3 ^ 33-1）/ 2 =2,779,530,283,277,761個），並且都是在初始塊建立的，沒有挖礦新增的幣。因為其供應量如此之大，單個的價格非常小，所以交易都是以百萬IOTA為單位的，即 MIOTA 原文網址：https://itw01.com/38CESJ6.html

2.正負號表示僅需交換位元中的正負(1->T,T->1),無需多一位元做有號數表示

若我們想把一個 Ternary 數值作正負號的轉換，只需交換每個位元中的正負(1->T,T->1)，如同做一個 NOT 的邏輯運算，而我們也可以很容易的由數值的最高有效位知道它的正負號，所以可以節省一個位元的空間去表示

Dec.	1	-1	2	-2
Bal3	1	T	T1	1T

3.運算速度較快

Balanced Ternary 除了減法運算只需對減數做 Not 後相加, 在運算上較 binary 快速外; 以下圖的 ripple adder 可看出，在相同的運算值在 6 bit 的 binary ripple adder 運算, 而 3-valued ripple adder 在運算上較快上許多; 在IOTA的交易驗證上, 我想運算時間也是個被重視的重點

浮點數表示較 Binary 的 IEEE754 精確

以32位元的浮點數表示, 在 IEEE754 中表示準度的位元為23bits (

$2^{23}$), 而若以相同位數在 Balanced ternary 表示精度則為

$3^{23}$ , 相比之下二者精度差了11222倍. 再者 Balanced ternary 因表示式而不會產生單精數運算時因指數過大(e.g. 1e20 * (1e20 - 1e20) 為 0.0),而造成運算精度被忽略的問題, 這點我想也是在加密貨幣中, blanced ternary 被委以重任的原因之一

• 待辦針對特定的領域 (如加密貨幣)，列出在 GitHub 裡頭可找到的應用案例，不僅列出程式碼，還要解說;
• 待辦在研究的過程中，應該會對既有工具進行修改或者重新開發 (不限程式語言)，也該一併指出，程式碼應該維護在 GitHub 上;

---

參考專案與文獻

• 平衡三進制 (wikipedia)
• Balanced ternary (wikipedia)
• 三生萬物 (數學文化)
• HTYISABUG同學共筆
• Ternary simulator
• The Balanced Ternary Machines of Soviet Russia
• Tangle 白皮書
• Suggestions for Ternary Computer Parts
• 苏联三进制计算机Сетунь到底是怎样一个计算机
• 化学计算、湿件计算、流体计算和三元计算
• [Ternac (wikipedia)]