2017q3 Homework1 (ternary)

contributed by <kevin550029>

Introduction to Balanced Ternary

簡介

Balanced Ternary

• 以3為基數,使用 -1(T)、0、1 基本數位的進位
  亦可表示為 -、0、+

  	32	31	30
  5 =	+	-	-
  	9	+(-3)	+(-1)

• Ternary encoding of base-3 digits

  在 Balanced Ternary 當中表示整數的方法同樣可以想成一個式子
  $a_0\times 3^0+a_1\times 3^1+a_2\times 3^2+...+a_i\times 3^i+...+a_n\times 3^n$，
  其中：

  • $n$ 為用於給 Balanced Ternary 表示正數的位元數
  • $a_i$ 為 Balanced Ternary 中第i個位元中的係數

  在討論要怎把十進位直接轉成Balanced Ternary表示時,
  碰到了些問題,最後找到相對應的演算法,如下

  ​​​​    String output="";
  ​​​​    while (n>0) {
  ​​​​       rem = n%3;
  ​​​​       n = n/3;
  ​​​​       if (rem == 2) {
  ​​​​           rem = -1;
  ​​​​           n++;
  ​​​​       }
  ​​​​       output = (rem==0?'0':(rem==1)?'+':'-') + output;
  ​​​​    }
  

  解讀為當某位元餘數為2時 output 會輸出 -
  並將其左邊的位元加1,再繼續進行轉換

• Counting Proceeds: 0, +, + -, + 0, + +, + - -, + - 0, + - +, + 0 - (from 0 to 8)

  Decimal	balance base-3
  0	0 0 0
  1	0 0 +
  2	0 + -
  3	0 + 0
  4	0 + +
  5	+ - -

• 藉由-1的引入,不須額外位元能直接表示負數

  Decimal	balance base-3
  -1	0 0 -
  -2	0 + -
  -3	0 + 0
  -4	0 + +
  -5	+ - -

運算

• ternary multiplexer

  • black box with five pins
  • selector pin receives a ternary signal (either -1, 0 or 1)
  • output pin, switch, three input pins inN, inO or inP

  

  設定selector可得到相對應的輸出

• unary functions

  • 給予input pin不同的值,可以達成各種功能的unary functions

  A unary function is a function that takes one argument
  From wikiedipa

  

  可以用來實做A+1的功能

  

  可以用來實做A-1的功能

• half-adder

  • To compute a function of two arguments we need to use three or four multiplexers

  

Balanced Ternary 要解決的問題

GitHub 中的應用案例

Reference

Balanced ternary numeral system
Wikipedia-平衡三進位
zhanyangch 共筆
Wikipedia-Balanced ternary