2017q3 Homework1 (ternary)

contributed by <timedieyoung>

Balanced Ternary

平衡三進位，以 -、0、+ 作為基本數位，基底為三進位制。(因為指令問題，以下內文以 T、0、1 表示)

- 表示 -1
0 表示 0
+ 表示 1

由於 -1 的引入，這種進位不需要額外的符號就能直接表示負數，也因此在加、減、乘的效率比二進位要好。

數的表示方法

平衡三進位和其他進位法相同，將各位的數字與位權相乘疊加即可表示任一整數部分與小數部分，兩者用 . 分隔。

將十進位的 -9 ~ +9 以平衡三進位轉換為以下表格

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

從表格可以觀察出

第一個非0位是T 的為負數，是 1 的為正數。
將任一數的所有 T 與 1 作互換即可變號(乘上-1)。

因此，欲將

- {25.4}_{d e c}

、

{1010.1}_{b i n}

表現為平衡三進位，可透過以下步驟轉換:

任何進位系統都可以表示成以下形式:

(a_{n} a_{n - 1} \cdot \cdot \cdot a_{1} a_{0} . c_{1} c_{2} c_{3} \cdot \cdot \cdot \cdot)_{b} = \sum_{k = 0}^{n} a_{k} b^{k} + \sum_{m = 1}^{\infty} c_{m} b^{- m}

$a_{n} a_{n - 1} \cdot \cdot \cdot a_{1} a_{0} . c_{1} c_{2} c_{3} \cdot \cdot \cdot \cdot$ 系統的表現形式

$b$ 系統的底數

$a_{k}$ 、
$c_{m}$ 小數點左側第K位數字、小數點右側第m位數字

\begin{aligned} - {25.4}_{d e c} & = - (1 T \times 101^{1} + 1 T T \times 101^{0} + 11 \times 101^{- 1}) \\ = - (1 T \times 101 + 1 T T + 11 \div 101) \\ = - 10 T 1. \overset{―}{11 T T} \\ = T 01 T . \overset{―}{T T 11} \end{aligned}

\begin{aligned} {1010.1}_{b i n} & = 1 T^{100} + 1 T^{1} + 1 T^{- 1} \\ = 10 T + 1 T + 0. \overset{―}{1} \\ = 101. \overset{―}{1} \end{aligned}

算數運算

單位數的加、減、乘運算可以化作以下表格

+	T	0	1
T	T1	T	0
0	T	0	1
1	0	1	1T

-	T	0	1
T	0	T	T1
0	1	0	T
1	1T	1	0

$\times$	T	1
T	1	T
0	0	0
1	T	1

加法和乘法有交換律

邏輯運算

與 Unsigned and 3's-complement ternary 作比較

truth value	unsigned	balanced
false	0	T
unknown	1	0
true	2	1

基於以上定義，真值表表現如下:

Not	T	0	1
	1	0	T

Not logic 的 unknown 表現依舊是 unknown

And	T	0	1
T	T	T	T
0	T	0	0
1	T	0	1

And logic 又可以看作將輸入取最小值(min)

Or	T	0	1
T	T	0	1
0	0	0	1
1	1	1	1

Or logic 又可以看作將輸入取最大值(MAX)

Xor	T	1
T	T	1
0	0	0
1	1	T

Sum	T	0	1
T	1	T	0
0	T	0	1
1	0	1	T

Cons	T	1
T	T	0
0	0	0
1	0	1

合意邏輯(Consensus logic)，等義於將0和T視作相同意義的 And logic。

ternary multiplexer

在討論加法器前，先了解 ternary multiplexer 的構造

下圖為一 ternary multiplexer的腳位

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

腳位分為三組 JP1、JP2、JP3

Connector JP1:

S1 - select input of the 1st ternary multiplexer
N1 - connected to C1 if S1=N ("negative" or -5V)
O1 - connected to C1 if S1=O ("zero" or 0V)
P1 - connected to C1 if S1=P ("positive" or +5V)
C1 - common signal of the 1st ternary multiplexer

Connector JP2:

S2 - select input of the 2nd ternary multiplexer
N2 - connected to C2 if S2=N ("negative" or -5V)
O2 - connected to C2 if S2=O ("zero" or 0V)
P2 - connected to C2 if S2=P ("positive" or +5V)
C2 - common signal of the 2nd ternary multiplexer

Connector JP3:

V-NEG - negative voltage (typically -5V)
GND - ground wire
V-POS - positive voltage (typically +5V)

簡單來說，是透過輸入端 S 的電位來決定 C 的輸出值 (N、O、P)，如下表

S(in)	C(out)
-5V	N
0V	O
5V	P

Balanced Half Adder

用以下電路為例，為一個半加器

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

分為 Sum、Consensus 兩部分
-5V、0、5V 分別以 T、0、1 代替

Sum:(左上晶片 JP1、JP2 & 右晶片 JP1)

左上 JP1 的 S、N、O、P 分別為 A、1、T、0
左上 JP2 的 S、N、O、P 分別為 A、0、1、T
右 JP1 的 S、N、O、P 分別為 B、C1(左上JP1)、A、C2(左上JP2)

整理成真值表可得

A	B	C1	C2	Sum
T	T	1	0	1
T	0	1	0	T
T	1	1	0	0
0	T	T	1	T
0	0	T	1	0
0	1	T	1	1
1	T	0	T	0
1	0	0	T	1
1	1	0	T	T

Consensus:(左下晶片 JP1、JP2 & 右晶片 JP2)

左下 JP1 的 S、N、O、P 分別為 A、T、0、0
左下 JP2 的 S、N、O、P 分別為 A、0、0、1
右 JP2 的 S、N、O、P 分別為 B、C3(左下JP1)、0、C4(左下JP2)