2017q3 Homework1 (ternary)

contributed by <river85511>

tags: sysprog2017

---

Homework Requirements

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

Balanced Tenary

Introduction to Balanced Ternary

相較於以 0 和 1 來表示數值的二進位 (Binary)，三進位 (Ternary) 則是以 0、1、2 來表示數值。而在 Balanced Ternary 中，Ternary 的 0，1，2 則是改以 -1、0、1 或是更簡略的以 T、0、+ 來表示。

中英文字間請記得空白
課程助教

謝謝助教提醒!
David Kuo

除此之外，在二進位的電腦中的 bit 和 byte， 在三進位的電腦中則變為 trit 和 tryte。一個 trit 能夠表達三種數值 T、0、+，而一個 tryte 有 6 個 trits。

Conversion to Balanced Ternary Representation

接著，透過以下的公式就能將不同整數基底 (integer base) 的數字以 Balanced Ternary 表示：

$(a_n{a}_{n-1}\cdots a_1{a}_0.c_1{c}_2{c}_3\cdots {)}_b=\sum _{k=0}^n{a}_k{b}^k+\sum _{k=0}^n{c}_k{b}^{-k}$，其中

• $a_n{a}_{n-1}\cdots a_1{a}_0.c_1{c}_2{c}_3\cdots istherepresentationintheoriginalnumericalsystem$
• $bistheoriginalradix$
• $a_{k}and{c}_{k}arethedigitsplacestotheleftorrightoftheradixpointrespectively$

舉例來說， 若以 Balanced Ternary 來表示整數，如：${20}_{dec}$ 和 $-{20}_{dec}$ 時，其表示法為：

• $1T1T_{bal3}=1\cdot 3^3+(-1)\cdot 3^2+1\cdot 3^1+(-1)\cdot 3^0={20}_{dec}$
• $T1T{1}_{bal3}=(-1)\cdot 3^3+1\cdot 3^2+(-1)\cdot 3^1+1\cdot 3^0=-{20}_{dec}$

由此例子可以發現，若想要用 Balanced Ternary 表達負數，只需要將正數的 $+$ 和 $T$ 對調即可。

若以 Balanced Ternary 來表示小數，如: ${(\frac{1}{20})}_{dec}$ 、${(\frac{-1}{20})}_{dec}$ 、${(\frac{19}{20})}_{dec}$，其表示法為：

• $0.0\overline{1T}=0\cdot 3^0+0\cdot 3^{-1}+1\cdot 3^{-2}+(-1)\cdot 3^{-3}+\cdots =\frac{1}{20}$
• $0.0\overline{T1}=0\cdot 3^0+0\cdot 3^{-1}+(-1)\cdot 3^{-2}+1\cdot 3^{-3}+\cdots =\frac{-1}{20}$
• $1.0\overline{T1}=1\cdot 3^0+0\cdot 3^{-1}+(-1)\cdot 3^{-2}+1\cdot 3^{-3}+\cdots =\frac{19}{20}$

由此例子可以發現，若想要從 $\frac{1}{20}$ 得到 $\frac{19}{20}$，只需要在 $\frac{1}{20}$ 小數點前的第一位改成 $1$ 然後小數點後的 $1$ 和 $T$ 對調即可。

參考資料：Wikipedia: Balanced Ternary、Number Systems 3: Ternary

Balanced Ternary Arithmetic

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

1_bal3 + 1_bal3 可以表示成 1T_bal3 = 3_dec - 1_dec
T_bal3 + T_bal3 可以表示成 T1_bal3 = -3_dec + 1_dec

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

需要特別注意的是，減法和除法是不符合交換律(communicative)的

基於上述四則運算規則，接著我們來談 multi-trits 的加減乘除。

multi-trits addition

以 ${11}_{dec}+4_{dec}={15}_{dec}$ 或 $11T_{bal3}+{11}_{bal3}=1TT{0}_{bal3}$ 為例：

​​​​           11T      
​​​​     +      11         
​​​​    --------------          
​​​​           1T0   
​​​​     +     1                 
​​​​     --------------         
​​​​           TT0          
​​​​     +    1                  
​​​​     --------------         
​​​​          1TT0 

multi-trits subtraction

以 ${11}_{dec}-4_{dec}=7_{dec}$ 或 $11T_{bal3}-{11}_{bal3}=10T_{bal3}$ 為例：

​​​​           11T      
​​​​     -      11         
​​​​    --------------          
​​​​           101   
​​​​     +      T                 
​​​​     --------------         
​​​​           1T1          

multi-trits multiplication

以 ${11}_{dec}\times 4_{dec}=7_{dec}$ 或 $11T_{bal3}\times {11}_{bal3}=1TT0T_{bal3}$ 為例：

​​​​           11T      
​​​​     x      11         
​​​​    --------------          
​​​​           11T   
​​​​     +    11T                 
​​​​     --------------         
​​​​          1T0T          
​​​​     +    1                  
​​​​     --------------         
​​​​          TT0T 
​​​​     +   1                  
​​​​     --------------         
​​​​         1TT0T

multi-trits division

以 ${30}_{dec}÷6_{dec}=5_{dec}$ 或 ${1010}_{bal3}÷1T{0}_{bal3}=1T{T}_{bal3}$ 為例：

根據 Wikipedia: Balanced Ternary，若
被除數 > (除數/2) -> 商 = 1
被除數 < -(除數/2) -> 商 = T
-(除數/2) <= 被除數 <= (除數/2) -> 商 = 0

​​​​               01TT
​​​​              -------
​​​​Divisor  1T0  )1010            T0<1<10, set 0
​​​​             - 0
​​​​              -------
​​​​               1010            10 = 10, but 10.1 > 10, set 1
​​​​             -1T0    
​​​​              -------
​​​​               TT0             
​​​​             + 1   
​​​​              -------
​​​​               0T01            T01<T0, set T
​​​​             -  T10
​​​​              ------
​​​​                0T10           T10=T10, set T
​​​​             -   T10
​​​​              ------
​​​​                   0

上述的規則其實我想了很久，後來我的想法是：除法的目的在於，使被除數扣掉除數的某個倍數後，能使餘數為0(整除)，若不為零則得最接近0。另外，在 Balanced Ternary 中，除數能夠除的倍數只有 -1、0、1。因此，若以上面的例子來解釋的話，第一次的商為0的原因是因為，1 這個數字不管 - (1 * 6) 或是 - (-1 * 6)都會使 1 遠離 0，只有 - (0 * 6) 才能使餘數最接近 0。同理類推第二次的商為1 的原因是因為 10.1 - (1 * 6) 比 -(0 * 6) 和 -(-1 * 6)更能讓餘數接近零。

Ternary Logic

In logic, a three-valued logic (also ternary logic or 3VL) is a logic systems in which there are three truth values indicating true, false and some indeterminate third value. – Wikipedia: Three-valued logic

根據維基百科的定義，三元邏輯就是一種有三種可能值(正、負、中間值)的邏輯系統。而在 Balanced Ternary 中，此三種可能值就是 -1、0、1。

Ternary Logic Operators in True Tables

下表彙整了 Balanced Ternay 的 OR、AND、XOR、NEG 的邏輯運算子(Logic Operator)

A	B	A ∨ B	A ∧ B	A ⊕ B	¬ A
1	1	1	1	-1	-1
1	0	1	0	0	-1
1	-1	1	-1	T	-1
0	1	1	0	0	0
0	0	0	0	0	0
0	-1	0	-1	0	0
-1	1	1	-1	T	1
-1	0	0	-1	0	1
-1	-1	-1	-1	-1	1

接著，我們來談應該要怎麼實做這些邏輯運算子，並延伸到半加器及全加器的設計上。首先，下圖列出了一個多工器(multiplexer)，這個多工器上有五個 pin，其中4個 pin (sel、N、0、P) 為 input pin，剩下的一個 pin 為 output，其功能為：

• 當 sel 的輸入值為 -1 時，out 就會為 N 的輸入值；
• 當 sel 的輸入值為 0 時，out 就會為 0 的輸入值；
• 當 sel 的輸入值為 1 時，out 就會為 P 的輸入值；

空白!!
課程助教

透過這個多工器，我們就能先實作出一些 Balanced ternary 的單元運算子(unary operator)，包括： increment、decrement、 max(A,0) (或稱為 OR )、min(A,0) (或稱為 AND )。如下列圖片所示：

increment

decrement

max(A,0) (或是 OR)

min(A,0) (或是 AND)

有了這些單元運算子(Unary Operator)以後，就能夠將半加器(Half Adder) 和全加器(Full Adder)實現，如下列圖片所示：

Half Adder and Full Adder

半加器 (Half Adder)

Sum of two trits

從這個電路得到的結果，就如同上面在 Balanced Ternary Arithmics 中介紹的 Addition 部份相同，至於紀錄進位(carry)的部份，則會由下面的 Consensus 來實現

Consensus

全加器 (Full Adder)

Sum of three trits

可以特別注意到的地方是：若 Carry (Cin)為0的話，從全加器得到的結果就會如同半加器一樣，也就是圖中的綠色部份。至於若要檢查是否在加的過程中有 overflow 發生，則是由下面的電路實現。

Overflow - carry flag

Application of Ternary Logic

SQL(NULL)

參考資料：Wikipedia: Three-valued logic、 Wikipedia: 三值邏輯、
Ternary logic、Ternary Computing Basics

Balanced Ternary 的設計要解決什麼類型的問題

Setun - A Balanced Ternary Based Computer

在1956年的蘇聯，由 S. L. Sobolev 帶領的團隊希望能夠創造出一台便宜、便於學校、實驗室、設計機構、或製造場使用的電腦，但由於電晶體在當時非常難取得，而真空管又非常容易損毀，促使他們重新檢視了電腦的架構，並討論了未來電腦的雛型。在這個背景下誕生的電腦就是一台 Balanced Ternary 的電腦 Setun。

透過在當時取得容易的微型鐵氧極線圈(miniature ferrite cores) 和半導體二極體(semiconductor diodes) 來當作變流器(controlled current transform) 能夠輕易的實現 Balanced Ternary 中的邏輯運算，同時，Balanced Ternary 的邏輯運算比二進位的邏輯運算還快，耗能也較少。這些都是促使他們打造一台 Balanced Ternary 電腦的原因之一。

在1960年的4月，這台電腦通過測試，並展現了驚人的可靠度和不同環境的適應性(例如溫差)。同時，Setun 由於便於製造及使用，不只被列入建議生產的清單上，還接收到國外的訂單。然而，即使在以上種種優點下，在1965年，Setun 仍在蘇聯電腦生產局官員的反對下，被迫停止生產。而後用來取代 Setun 的則是一台擁有同等效能但比 Setun 還貴的2.5倍的二進位的電腦。

參考資料：Development of ternary computers at Moscow State University

與其他數值系統的比較

透過分析不同底數的底數經濟(Radix Economy)，就能夠比較以不同底數來表示數值的效率，根據Wikipedia: Radix Economy，用一個底數 $b$ 來表達數值 $N$ 的底數經濟之計算公式為：

$E(b,N)=b\lfloor {\log }_b(N)+1\rfloor$

從這個公式，可以得知若以自然常數 $e$ 當底數來表達數值時，其底數經濟最低，也就代表，理論上自然常數 $e$ 才是用來表達數值時最理想的底數。若是整數的話，$3$ 則是最有效率的底數，其次則是以 $2$。下表列出了我們常見的底數，以及他們各自在表達不同數值範圍大小時的平均底數經濟。

若就以這張圖表中的 $\frac{E(b)}{E(e)}$ 來看的話，可以發現其實以 $3$ 為 底數來表達數值的底數經濟比以 $2$ 為底數還要低，也就是以 $3$ 為底數來表達數值其實比以 $2$ 還有效率。但值得注意的是，在表達數值的範圍為 $1-43$ 時，以 $2$ 為底數來表達數字，其實也比以 $3$ 還要來的有效率的。但在表達更大的數字範圍時，以 $3$ 為底數還是比以 $2$ 為底數有效率。

那為什麼現代的電腦系統仍以 $2$ 為底數(二進位)來表達數值呢？ 原因如下：

• 只需要透過開關，就能夠輕易表達兩個不同數值(0,1)。因此，相對來說，區分三個不同電壓區間，以表達三個數值就相對困難
• 二進位的系統比較不會因為電壓的隨機震盪產生錯誤的訊號(數值) (greater noise immunity)
• 二進位電腦的歷史發展悠久，若想把電腦的數值表達系統改變成以 $3$ 為底數，將會是十分浩大的工程…

但是從底數經濟的分析中我們可以得知，在表達數字時，以 $3$ 為底數反而會是更好的選擇。

參考資料：How efficient is Binary system compared to other number systems for use in computers?、What is the most efficient numerical base system?、Wikipedia: Radix Economy

IOTA / Tange 之應用

IOTA介紹

首先，我們來看看 IOTA 和 其他加密貨幣(如 Bitcoin)之間的差異是什麼。根據 IOTA BREAKDOWN: The Tangle Vs. Blockchain Explained，可以知道 IOTA 是基於 Tangle 的結構而其他加密貨幣則是基於 Blockchain 的結構，而這兩種不同結構的差異，以下列出比較：

	Blockchain	Tangle
Miners	Yes	No
Fee	Yes	No
Blocks	Yes	No
Hard/Soft fork capability	Yes	No
Hashcash	Yes	Yes (Lite)
Distributed consensus	Yes	Yes
Quantum security	No	Yes
Scalability	No	Yes
Offline capability	No	Yes

從這個比較表中，可以得知使用 IOTA 交易時，由於免手續費(Fee)，也沒有 Block，所以也不需要礦工。除此之外，IOTA 同時也能處理使用者大幅增加時的情況 (Scalable)，還可以避免量子電腦的威脅。那是什麼樣的條件，使得 IOTA 能夠擁有這些能力呢？根據 IOTA 白皮書，可以了解到 Tangle 的底層其實是一種稱為 Directed Acyclic Graph (DAG) 的結構，如下圖所示：

在這種結構底下，每次新的交易產生時(如圖中的灰色方塊)，都得先驗證兩個根據 Monte Carlo 演算法隨意取出的交易，該次交易才能成立。而此設定，不只使 IOTA 免除了如 Bitcoin 需要礦工幫忙驗證交易並支付手續費必要，同時也確保 IOTA 在使用者增加時的仍能順利進行交易。同時，IOTA 也提供了一個稱為 Masked Authenticated Messaging 的功能，來保護並加密傳遞的訊息。

這些優點實際上為 Internet of Thing (IOT) 提供了相當好的環境。而從 IOTA 的發展歷史，如下所示：

• 第一階段
  • IOTA core live
  • establishing the IOTA Foundation
  • moving the community’s chat over to Slack
  • completing some partnerships
  • IOTA on exchange market
  • spreading into the world
• 第二階段
  • extending IOTA’s utillity
  • open IOTA to anyone that want to build on top of the IOTA network
• 第三階段
  • development of hardware (project's name is Jinn project), a brand new type of microprocessor for IoT, a hardware implementation hasher for IOTA’s ‘Curl hash function’

也可以得知 IOTA 希望能與 IOT 的發展結合。從 IOTA 已經公開釋出程式碼，到目前正在打造一個專門處理 IOTA 的 Hashcash 所需要的運算的微型處理器，稱為 Jinn Processor，都可以發現 IOTA 對於 IOT 的野心。

值得特別注意的是，IOTA 正在開發的 Jinn Processor 內部並不是以二進位來表達數值，而是以 Balanced Ternary 來表示數值，以及進行運算。正是因為以 Balanced Ternary 來表達數值的 Radix Economy 較二進位低、同樣的空間下能表達的數值範圍也比二進位來的更廣、操作起來也更快更直觀、耗能也較小等優點。

參考資料：How IOTA makes bright future for Internet of Things、IOTA BREAKDOWN: The Tangle Vs. Blockchain Explained、The Tech Behind IOTA Explained、IOTA Development Roadmap、OUR FIRST INVESTMENT IN TOKENS IS.. IOTA

Balanced Ternary 在 GitHub 裡頭可找到的應用案例

IOTA_kerl

• IOTA is adding an additional hashing function, based on Keccak, with conversion to ternary.
• CheckSums are calculated using the last 9 trytes.