TopCoder

Adrien Wu
$ \begin{align} AC \times 2^9 \\ \text{New TIOJ ?} \end{align} $

User's AC Ratio

96.8% (30/31)

Submission's AC Ratio

64.0% (48/75)

Tags

Description

敘述一

二進位加法運算與布林代數不同的地方在於其結果包含了一個進位值。不過,加法還是可以用布林函數處理,如下面真值表中

A B Sum CarryOut
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

我們展示了將兩個一位元的輸入相加,並產生一位元的總和與一個進位的邏輯。這個真值表可以輕易地由數位邏輯實行,但是我們並非只是對於進行兩個單獨一位元的加法感到興趣,更恰當的說,我們希望可以將兩個n位元的數值將加;這個動作可以由建立一個加法器的組合,達到將來自於一個加法器的進位輸出(CarryOut)當做提供給下一個加法器的進位輸入(CarryIn),在下圖中

我們描繪了一個四位元的加法器。為了使多位元的加法器能夠運作,每個單一位元的加法器都需要三個輸入,包含了來自於前一位元的進位輸入,修正過的真值表如下表

CarryIn A B Sum CarryOut
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1

所示,如果用C來代表CarryIn,兩個輸出可以表示成:

總和 Sum = A’B’C+A’BC’+ABC+AB’C’
進位輸出 CarryOut = AB+AC+BC
 

敘述二

當我們在設計加法器電路時,如果每一位運算都必須等待前一位數是否進位將造成速度的降低,於是我們需要設計邏輯電路來快速產生是否進位的訊息。給定一正整數 $n$,傳回第 $n$ 位進位的布林函數。但是因為每個 bit 在計算時必須等待前一個 bit 計算得到的 carry,這樣的 delay 雖然短暫,但是一旦 bit 數一多,傳遞進位值造成的 delay 時間就會增加到無法接受的地步。
如果每一位元的進位值可以不依賴前一位元的傳遞,而直接由原始輸入的數值運算,那就可以大大減少運算的時間。於是我們使用邏輯運算的方式來減少時間的負擔,這種方法稱為前瞻進位CarryLookahead,由上面觀點我們可以導出一個遞迴想法的邏輯運算式:
$$C_n = A_n B_n + A_n C_{n-1} + B_n C_{n-1}$$
以下是一個 4bit 加法器 CarryLookahead 的範例:
A0~A3及B0~B3代表第1~4個bit的輸入,C0~C2代表第1~3個bit的carryout,也是第2~4個bit的carryin。(參照上圖)
C0=A0B0
C1=A1B1+A1 C0+B1C0或是C1=A1B1+A1A0B0+B1A0B0
C2=A2B2+A2A1B1+A2A1A0B0+A2B1A0B0+B2A1B1+B2A1A0B0+B2B1A0B0
如此一來,就可以用SOP(積之和)的形式表示各個bit,而延遲時間不會超過兩個delay,但是當bit數太多時(如32位元),SOP的形式就會變得太複雜,而在電路設計上難以實行,因此一般取每8bit為一組,進行CarryLookahead,以8bit加法器作為運算的基本元素,一般是再以4個8bit加法器連接在一起,組成一個32-bit的加法器,取速度和精簡的平衡點。

除了使用SOP的形式,另一個方法是我們全部要用sheffer stroke(二輸入一輸出之反及閘Nand Gate,用 | 符號表示)邏輯來完成前瞻進位(Carry LookAhead)的工作,使得加法器可以由欲求位數之前的每一位數來直接判斷其是否有CarryOut bit,便得以分別獨立進行各個位數的運算,以提高效能。
方法是利用ans1(尚未化簡)以及ans2(已化簡)兩個函數求解:
兩個函數的基本精神就是利用到一個遞迴式,透過遞迴的方式可以得到解答。
ans1與ans2的差別在於產生答案的方式:

ans1產生答案的方式是直接利用A'=(A|A)B'=(B|B)AB=((A|B)|(A|B))以及A+B=((A|A)|(B|B))再代入Cn= AnBn+(An+Bn)Cn-1,因此產生的答案長度較長。

ans2是利用式子Cn =((An|Bn)|(Cn-1|((An|An)|(Bn|Bn)))),也是像上面透過遞迴的方法,但是因為這是有化簡過的式子,因此長度會短少許多。

請你寫一程式來處理以上的題目。

Input Format

輸入一個正整數 $n (0 \le n \le 6)$,以求出 $C_n$。

Output Format

對於 ans1ans2 兩種 $C_n$ 的 NAND 表示法,請分別印出其完整的表示法展開為何,再印出總共使用了幾個 NAND。

請依照筆試題的遞迴式子撰寫你的程式。

Sample Input 1

0

Sample Output 1

ans1:
((A0|B0)|(A0|B0))
3 NAND(s) used.
ans2:
((A0|B0)|(A0|B0))
3 NAND(s) used.

Hints

Problem Source

原TIOJ1024 / 96建中校內資訊能力競賽(prob1)

Subtasks

No. Testdata Range Score
1 0 20
2 1 20
3 2 20
4 3 20
5 4 20

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 1000 65536 262144 1
1 1000 65536 262144 2
2 1000 65536 262144 3
3 1000 65536 262144 4
4 1000 65536 262144 5