2017q3 Homework1 (ternary)

contributed by<zhanyangch>

tags:sysprog2017

TODO: 詳細閱讀 Fast Ternary Addition，理解 base-3 的原理 (並且複習數位邏輯)，整理 base-3 基礎運算操作
"jserv"

---

Review by williamchangTW

• 根據電路的分析應該可以得出相關好處，比如運算較快或其餘能推導出來的想法
• 了解三位元的好處後，可以順利的把接下來的作業完成，電路分析的還滿詳細，受教了

小弟坐井觀天，如有冒犯請見諒"williamchangTW"

---

Ternary 介紹

Ternary 以三為底，每個 ternary digit(trit) 有三個符號表示 0,1,2 ，Balanced Ternary 則是 +,0,- 或 1,0,T，一個無號整數 N，可以用 log₃(N+1)(無條件進位) 位三進位表示，與二進位需要 log₂(N+1) 相比，三進位只須 log₃N/log₂N(0.63) 倍的位數，除了用來代表數字以外，也對應的 Kleene logic

truth value	unsigned	balanced
false(F)	0	-
unknown(U)	1	0
true(T)	2	+
Kleene logic 運算，參考 Three-valued logic(wikipedia)
NOT(A)：¬A
A	¬A
-	–
F	T
U	U
T	F
AND(A,B)：A∧B
A\B	F	U
:-:	:-:	:-:
F	F	F
U	F	U
T	F	U
OR(A,B)：A∨B
A\B	F	U
:-:	:-:	:-:
F	F	U
U	U	U
T	T	T

b3k 程式

• 下載及編譯

$ git clone https://github.com/sysprog21/balanced-ternary
$ cd balanced-ternary
$ make

作業要求頁面已更新，請注意。重新 git clone 並依據裡頭的程式碼，對下方程式碼做對應的縮排 (4 個空白，而不是 tab)
"jserv"

以修正
"zhanyangch"

• digit 的數量為8，可表示的數為 -3280~3280

$3280={\displaystyle \frac{1(3^8-1)}{3-1}}$

    p = &digit[SZD - 1];
    r = 3 * p->exp / 2;
    if (src > r)
        src = r;
    else
        r = src;

• 此段為十進位轉為三進位 (Ternary)，以減法代替除法，注意 ++p->val 的運算順序是 ++(p->val)

// Like 'echo "obase=3; $src" | bc'.
    do {
        while (r < p->exp)
            --p;
        r -= p->exp;
        ++p->val;
    } while (r);

• 加入一段程式碼查看三進位的輸出

    for(p = &digit[SZD-1]; p >= &digit[0]; --p)
        printf("%d",p->val);
    printf("\n");

$ echo 25 | ./b3k
00000221
├───┐
│   │
└┴┬─┘

$25=(2\times 3^2+2\times 3^1+1\times 3^0)$

• 轉換成 Balanced Ternary，當 val 為 2 將其轉換為 1T (在此 T 表是-，與減號區別，與老師上課講義的表示法稍有不同)，並且將正負號補上。

$3^k\times 2=3^{k+1}-3^k$
例如：

$\begin{array}{rl}{25}_{dec}& ={221}_3\\ & =1T{00}_{bal3}+1T{0}_{bal3}+1_{bal3}\\ & =10T{1}_{bal3}\\ {25}_{dec}& =3^3+(-1)\times 3^1+1\end{array}$

// Convert to the balanced form.
    while (p < &digit[SZD]) {
        if (r)
            ++p->val;
        r = p->val > 1;
        if (r)
            p->val -= 3;
        p->val *= inv;
        ++p;
    }

運算

請閱讀 Ternary computing: basics，關注於 ternary multiplexer, Unary functions, half-adder, Consensus, full adder, Overflow
"jserv

• balance teneray multiplexer
  當 sel 分別是 -1,0,1 時輸出為 inN,inO,inP
  
• 如果將 sel 設為 A 則可以得到幾個跟 A 有關的 unary functions
  
  
  
  
• half-adder ：首先算出 A,A+1,A-1 的值，利用 B 作為 multiplexer 的 sel

B	-1	0	1
S	A-1	A	A+1

A+B

A\B	-1	0	1
-1	1	-1	0
0	-1	0	1
1	0	1	-1

• 進位則是當 A,B 為(1,1)時 C為-1，A,B 為(-1,-1)時時 C為1

B	-1	0	1
C	min(A,0)	0	max(A,0)

• full adder:利用上面的半加器算出 A+B-1,A+B,A+B+1 後，由 Cin 決定 S
• A+B-1 可以先計算出 A-1 對 B 相加的真值表inN,inO,inP的順序即可，A+B+1亦同。

(A-1)+B

B	-1	0	1
A+B-1	A+1	A-1	A
(A+1)+B
B	-1	0	1
:-:	:-:	:-:	:-:
A+B+1	A	A+1	A-1

*Cout:比較難直接看懂，用 Cin 回推各種情形
Cin:0　與半加器相同
Cin:1,A+B>0 Cout:1
Cin:1,A+B<0 Cout:0
Cin:-1,A+B>0 Cout:0
Cin:-1,A+B<0 Cout:1