2017q3 Homework1 (ternary)

contributed by <jackyhobingo>

reviewed by Jetudie

• 在 "Balanced Ternary 的設計要解決的問題類型" 中，已從空間使用效率去探討，但未詳述實際應用，缺乏呼應題目的結論：建議對於能解決問題的類型做個舉例。

• 在 "想法 & 思考" 中:

  • "經由測試結果猜測"，"猜測"適用於測試之前無規則依循的時候，而此時已有測試及參考，可用"推測"。
  • 對測試出來的結果缺乏描述，建議把推測的想法過程表達出來。
  • 有 typo, 是四個邊四個"角"而非"腳"，是依"照"而非"造"。
  • 四個邊角分別為
    $3^0,3^1,3^2$…未說明邊角的順序，表達可再更明確。

---

Balanced Ternary 原理

Ternary System

相較於一般常見 base2 的進位模式， Ternary System 是一種 base3 的進位系統。Ternary System 計算模式類似 binary system ， 影片一中舉

${45}_{10}\to {1200}_3$ 為例子。
e.g.

$45÷3=15\dots 0$

$15÷3=5\dots 0$

$5÷3=1\dots 2$

$2÷3=0\dots 1$

${1200}_3=1\times 3^3+2\times 3^2+0\times 3^3+0\times 3^0={45}_{10}$

Balanced Ternary

Balanecd Ternary 是以 -, 0, + 表示的 Ternary System
可以用

$\sum _i^n{c}_i{3}^i$ 來表示換算成十進位大小

e.g.
基本十進位與 Balanced Ternary 轉換例子

	$3^2$	$3^1$	$3^0$
$5$	$+$	$-$	$-$	$+1\times 3^2-1\times 3^1-1\times 3^0=+9-3-1=5$
$-5$	$-$	$+$	$+$	$-1\times 3^2+1\times 3^1+1\times 3^0=-9+3+1=-5$
$7$	$+$	$-$	$+$	$+1\times 3^2-1\times 3^1+1\times 3^0=+9-3+1=7$
$-7$	$-$	$+$	$-$	$-1\times 3^2+1\times 3^1-1\times 3^0=-9+3-1=-7$
$2$	$0$	$+$	$-$	$0\times 3^2+1\times 3^1-1\times 3^0=0+3-1=2$

Balanced Ternary logic table

影片二提到一些 balanced ternary logic table

sum	$-$	$0$	$+$
$-$	$+$	$-$	$0$
$0$	$-$	$0$	$+$
$+$	$0$	$+$	$-$

carry	$-$	$0$	$+$
$-$	$-$	$0$	$0$
$0$	$0$	$0$	$0$
$+$	$0$	$0$	$+$

$\times$	$-$	$0$	$+$
$-$	$+$	$0$	$-$
$0$	$0$	$0$	$0$
$+$	$-$	$0$	$+$

$÷$	$-$	$0$	$+$
$-$	$+$	$-\mathrm{\infty }$	$-$
$0$	$0$	$NAN$	$0$
$+$	$-$	$\mathrm{\infty }$	$+$

ternary multiplexer

在文章Ternary computing: basics中，設計一種 ternary 的多工器，如圖二，可以藉由 pin sel 來決定可以輸出哪一個 pin 的值，並且可以藉由設定 inN, inO, inP 值的不同來設計出如A+1, A-1, max(A,0), min(A,0) 不同 Function ， 進而設計出半加器(圖三、圖四)，再組合成全加器(圖五、圖六)。

(圖二)

(圖三 半加器 S)

(圖四 半加器 C)

(圖五 全加器 Sum)

(圖六 全加器 Carry)

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

資料數值

$N_{10}$ 可以在 base 為 b 的計算系統中，使用

$\lfloor lo{g}_{b}N+1\rfloor$ 個digits 來做表示，例如

${50}_{10}$ 可以在 base 10 的計算系統中用

$\lfloor lo{g}_{10}50+1\rfloor =2$

The radix economy E(b,N) for any particular number N in a given base b is defined as

$E(b,N)=b\lfloor lo{g}_{b}N+1\rfloor$
其中在

$b=e$ 時，radix economy 可以達到 minimal ，但是並沒有辦法做出

$digits=e$ 的處理器，而在

$b\in N$ 的情況下，minimal 在

$N=3$ 。

測試 Balanced Ternary

測試環境：Ubuntu 16.04.3 LTS

$ make check
echo  27 | ./b3k
├───┐
│   │
└───┘
echo -27 | ./b3k
┌┬──┐
│   │
└───┘
echo   9 | ./b3k
┌───┐
┤   │
└───┘
echo  -9 | ./b3k
┌───┐
├   │
└───┘

想法 & 思考

經由測試結果，及參考圖猜測 - 往內 + 往外 0 則不變，四個邊四個腳分別為

$3^0,3^1,3^2,3^3,3^4,3^5,3^6,3^7$ 能表示的最大值為

$\sum _{i=0}^7{3}^i=3280$ ，最小值為

$\sum _{i=0}^7-3^i=-3280$。
此外依造圖上的計算模式可以來表示 balanced ternary 進位退位的運算

$ echo 1 | ./b3k
┌───┐
│   │
└─┬─┘
$ echo 0 | ./b3k
┌───┐
│   │
└───┘
$ echo -1 | ./b3k
┌───┐
│   │
└─┴─┘
$ echo 3281 | ./b3k
├─┴─┤
┤   ├
├─┬─┤
$ echo 3280 | ./b3k
├─┴─┤
┤   ├
├─┬─┤
$ echo 3279 | ./b3k
├─┴─┤
┤   ├
├───┤
$ echo -3279 | ./b3k
┌┬┬┬┐
├   ┤
└┴─┴┘
$ echo -3280 | ./b3k
┌┬┬┬┐
├   ┤
└┴┴┴┘
$ echo -3281 | ./b3k
┌┬┬┬┐
├   ┤
└┴┴┴┘

測試結果

經由程式結果知道，目前能表示的範圍為

$-3280$~

$3280$

參考資料

影片一
影片二
Ternary computing: basics
IOTA - isnt it the perfect Cryptocurrency?
wikipedia Radix_economy