108 年國立臺灣大學電子工程學研究所丁組《邏輯設計》考古題與詳解

Question 1

Consider the following logic circuit. According to the specification, with applying the input vector (A, B, C, D) = (0, 0, 1, 1), the output value at F should be 0. However, the actual simulation result is 1. Assume the error is caused by using wrong gate types, and only three possibilities are considered: AND↔NAND, OR↔NOR, Inverter↔Buffer (one buffer equals two cascaded inverters). If a single error occurs, please write down the possible gate instance names where the error may occur.
🖼️【此處有附圖，請對照原卷】

Accepted Answer

核心觀念 本題考查： - AND 與 NAND 的互換 - OR 與 NOR 的互換 - Inverter 與 Buffer 的互換 - 由輸入值逐級推導電路輸出，判斷哪一個單一閘門故障會使 $F$ 由規格值 $0$ 變成實際值 $1$ 由圖可得電路關係： $$ X1=G1(A,B),\qquad X2=G2(C,D) $$ $$ X3=G3(X1,X2),\qquad X4=G4(X3) $$ $X4$ 分別輸入 $G5$ 與 $G6$，而 $X2$ 也是 $G5$ 的另一個輸入，因此： $$ X5=G5(X4,X2) $$ $$ F=G6(X5,X4) $$ 圖中正確閘門類型為： - $G1,G2,G5$：AND - $G3,G6$：OR - $G4$：Inverter --- 正常電路計算 輸入為： $$ (A,B,C,D)=(0,0,1,1) $$ 因此： $$ G1=AB=0\cdot 0=0 $$ $$ G2=CD=1\cdot 1=1 $$ $G3$ 為 OR 閘： $$ G3=G1+G2=0+1=1 $$ $G4$ 為反相器： $$ X4=\overline{G3}=\overline{1}=0 $$ $G5$ 為 AND 閘： $$ X5=X4\cdot G2=0\cdot 1=0 $$ $G6$ 為 OR 閘： $$ F=X5+X4=0+0=0 $$ 這與題目給定的規格值相同。 --- 逐一分析單一閘門錯誤

Question 2

Consider a 4-input function.
$f(A, B, C, D) = AC + AB'C' + BC'D$ .
(a) (8%) Apply Shannon expansion theorem to iteratively expand $f$ on $A, B, C, D$ (in order). Write down the fully expanded function $f$ .
(b) (6%) Use 2-to-1 multiplexors to implement $f$ obtained in (a), where $A, B, C, D$ can only be select signals.
(c) (2%) Redo (b) with the minimum number of 2-to-1 multiplexors.

Accepted Answer

核心觀念 本題考查三項重點： 1. Shannon expansion theorem： $$f=Xf{X=1}+X'f{X=0}$$ 2. 以 Shannon 展開建立多工器（MUX）電路。 3. 利用布林代數重新分解函數，以減少 2-to-1 MUX 數量。 以下約定： $$\operatorname{MUX}(S,I1,I0)=SI1+S'I0$$ 其中 $S$ 為 select signal。 --- (a) 依序對 $A,B,C,D$ 做 Shannon 展開 原函數為 $$ f(A,B,C,D)=AC+AB'C'+BC'D $$ 第一次：對 $A$ 展開 令 $A=1$ 與 $A=0$： $$ f{A=1}=C+B'C'+BC'D $$ $$ f{A=0}=BC'D $$ 因此 $$ f=A(C+B'C'+BC'D)+A'BC'D $$ 第二次：對 $B$ 展開 對 $f{A=1}$： $$ f{A=1,B=1}=C+C'D $$ $$ f{A=1,B=0}=C+C'=1 $$ 對 $f{A=0}$： $$ f{A=0,B=1}=C'D $$ $$ f{A=0,B=0}=0 $$ 所以 $$ f=A\left[B(C+C'D)+B'(1)ight] +A'\left[B(C'D)+B'(0)ight] $$ 第三次：對 $C$ 展開 各 cofactors 為： $$ f{1,1,C=1}=1,\qquad f{1,1,C=0}=D $$ $$ f{1,0,C=1}=1,\qquad f{1,0,C=0}=1 $$ $$ f{0,1,C=1}=0,\qquad f{0,1,C=0}=D $$ $$ f{0,0,C=1}=0,\qquad f{0,0,C=0}=0 $$ 第四次：對 $D$ 展開並寫成完全展開式 將所有輸入組合列出後，函數為 $$ \boxed{ \begin{aligned} f={}&A'BC'D\ &+AB'C'D' + AB'C'D\ &+ABC'D\ &+ABCD' + ABCD \end{aligned} } $$ 亦可合併同類項寫成 $$ \boxed{ f=A'BC'D+AB'C'+ABC'D+AC } $$ 其中第一個式子是依序對 $A,B,C,D$ 展開後的完整 minterm 形式。 --- (b) 依照完全 Shannon 展開使用 2-to-1 MUX 直接依照 $Aightarrow Bightarrow Cightarrow D$ 的展開順序建立 MUX 樹： - 第 1 層：8 個以 $D$ 為 select signal 的 MUX - 第 2 層：4 個以 $C$ 為 select signal 的 MUX - 第 3 層：2 個以 $B$ 為 select signal…

Question 3

Consider a 4-input function.
$f(A, B, C, D) = AC + AB'C' + BC'D$ .
(a) (8%) Apply Shannon expansion theorem to iteratively expand $f$ on $A, B, C, D$ (in order). Write down the fully expanded function $f$ .
(b) (6%) Use 2-to-1 multiplexors to implement $f$ obtained in (a), where $A, B, C, D$ can only be select signals.
(c) (2%) Redo (b) with the minimum number of 2-to-1 multiplexors.

Accepted Answer

核心觀念 本題考查三項重點： 1. Shannon expansion theorem： $$f=Xf{X=1}+X'f{X=0}$$ 2. 以 Shannon 展開建立多工器（MUX）電路。 3. 利用布林代數重新分解函數，以減少 2-to-1 MUX 數量。 以下約定： $$\operatorname{MUX}(S,I1,I0)=SI1+S'I0$$ 其中 $S$ 為 select signal。 --- (a) 依序對 $A,B,C,D$ 做 Shannon 展開 原函數為 $$ f(A,B,C,D)=AC+AB'C'+BC'D $$ 第一次：對 $A$ 展開 令 $A=1$ 與 $A=0$： $$ f{A=1}=C+B'C'+BC'D $$ $$ f{A=0}=BC'D $$ 因此 $$ f=A(C+B'C'+BC'D)+A'BC'D $$ 第二次：對 $B$ 展開 對 $f{A=1}$： $$ f{A=1,B=1}=C+C'D $$ $$ f{A=1,B=0}=C+C'=1 $$ 對 $f{A=0}$： $$ f{A=0,B=1}=C'D $$ $$ f{A=0,B=0}=0 $$ 所以 $$ f=A\left[B(C+C'D)+B'(1)ight] +A'\left[B(C'D)+B'(0)ight] $$ 第三次：對 $C$ 展開 各 cofactors 為： $$ f{1,1,C=1}=1,\qquad f{1,1,C=0}=D $$ $$ f{1,0,C=1}=1,\qquad f{1,0,C=0}=1 $$ $$ f{0,1,C=1}=0,\qquad f{0,1,C=0}=D $$ $$ f{0,0,C=1}=0,\qquad f{0,0,C=0}=0 $$ 第四次：對 $D$ 展開並寫成完全展開式 將所有輸入組合列出後，函數為 $$ \boxed{ \begin{aligned} f={}&A'BC'D\ &+AB'C'D' + AB'C'D\ &+ABC'D\ &+ABCD' + ABCD \end{aligned} } $$ 亦可合併同類項寫成 $$ \boxed{ f=A'BC'D+AB'C'+ABC'D+AC } $$ 其中第一個式子是依序對 $A,B,C,D$ 展開後的完整 minterm 形式。 --- (b) 依照完全 Shannon 展開使用 2-to-1 MUX 直接依照 $Aightarrow Bightarrow Cightarrow D$ 的展開順序建立 MUX 樹： - 第 1 層：8 個以 $D$ 為 select signal 的 MUX - 第 2 層：4 個以 $C$ 為 select signal 的 MUX - 第 3 層：2 個以 $B$ 為 select signal…

Question 4

Given the following map of cell locations, we want to group the eight cells, a, b, ..., h, into two sets, so that adjacent cells belong to different sets. Two cells, i and j, are adjacent if $|x_i-x_j| \leq 1$ and $|y_i-y_j| \leq 1$ , where $x_i$ and $y_i$ are the x-coordinate and y-coordinate of cell i, respectively. Let $g_i=0$ and $g_i=1$ denote cell i belonging to groups 1 and 2, respectively.
🖼️【此處有附圖，請對照原卷】
(a) (8%) Express the above cell grouping problem in terms of a product-of-sums (POS) formula (Boolean Expression without simplification) such that the formula can be satisfied if and only if the cells in the given map can be grouped as desired.
(b) (6%) How many solutions are there to the formula of (a)? Write down all the solutions if there is any.
(c) (4%) Rewrite the formula of (a) in a minimum sum-of-products (SOP) expression.

Accepted Answer

核心觀念 兩個相鄰格子必須分屬不同群，因此每條相鄰邊都要求兩個變數值不同： $$ gi
e gj $$ 對布林變數而言，這等價於 XOR 條件，也可寫成 POS 形式： $$ (gi+gj)(\overline{gi}+\overline{gj}) $$ 解題方法 依圖讀出各格座標： | 格子 | 座標 | 格子 | 座標 | |---|---:|---|---:| | $a$ | $(1,4)$ | $b$ | $(4,4)$ | | $c$ | $(2,3)$ | $d$ | $(3,3)$ | | $e$ | $(1,2)$ | $f$ | $(4,2)$ | | $g$ | $(2,1)$ | $h$ | $(3,1)$ | 套用相鄰條件 $|xi-xj|\le 1$ 且 $|yi-yj|\le 1$，相鄰格子對為： $$ (a,c),\ (b,d),\ (c,d),\ (c,e),\ (d,f),\ (e,g),\ (f,h),\ (g,h) $$ 每一對相鄰格子各自形成一個「兩變數不同」的 POS 因子。 (a) POS 公式 將八組相鄰條件逐一相乘，得到未化簡的 POS 公式：

Question 5

An M-N flip-flop has two inputs {M, N} and two outputs {Q, Q'}. It behaves as follows:
If MN = 11, the next state of output (Q+) is 0.
If MN = 10, the next state of output is the same as the present state.
If MN = 01, the next state of output is 1.
If MN = 00, the next state of output is the complement of the present state.
(a) (4%) Complete the following table for M, N.

Present state	Next state
Q	Q+	M	N
0	0
0	1
1	0
1	1
(b) (4%) Use your answer in (a) to derive the characteristic (next state) equation for this flip-flop. (i.e., express Q+ in terms of M, N and Q).
(c) (4%) Implement an M-N flip-flop based on T flip-flop.
(d) (4%) Write down the minimum SOPs of the next-state equations for both flip-flops in the following circuit. A+=? B+=?
🖼️【此處有附圖，請對照原卷】

Accepted Answer

核心觀念 本題考查： - M-N flip-flop 的狀態轉移規則。 - 由狀態表推導 characteristic equation。 - T flip-flop 的特性方程式： $$Q^+=T\oplus Q$$ - 以 T flip-flop 模擬其他型態 flip-flop。 - 最小和項式（minimum SOP）的化簡。 其中 $Q'$ 表示 $Q$ 的反相，並非另一個獨立狀態變數。 --- (a) 完成狀態表 已知： | $MN$ | 動作 | $Q^+$ | |:---:|:---|:---:| | $11$ | Reset | $0$ | | $10$ | 保持 | $Q$ | | $01$ | Set | $1$ | | $00$ | Complement | $Q'$ | 逐列判斷： 1. $Q=0,\ Q^+=0$ 必須是 $MN=11$ 或 $MN=10$。 2. $Q=0,\ Q^+=1$ 必須是 $MN=01$ 或 $MN=00$。 3. $Q=1,\ Q^+=0$ 必須是 $MN=11$ 或 $MN=00$。 4. $Q=1,\ Q^+=1$ 必須是 $MN=10$ 或 $MN=01$。 因此： | Present state $Q$ | Next state $Q^+$ | $M$ | $N$ | |:---:|:---:|:---:|:---:| | $0$ | $0$ | $1$ | $1$ | | $0$ | $0$ | $1$ | $0$ | | $0$ | $1$ | $0$ | $1$ | | $0$ | $1$ | $0$ | $0$ | | $1$ | $0$ | $1$ | $1$ | | $1$ | $0$ | $0$ | $0$ | | $1$ | $1$ | $1$ | $0$ | | $1$ | $1$ | $0$ | $1$ | --- (b) 推導 characteristic equation 依照 $MN$ 的四種情況，可直接寫成： - $MN=01$ 時，$Q^+=1$，對應項為 $M'N$。 - $MN=00$ 時，$Q^+=Q'$，對應項為 $M'N'Q'$。 - $MN=10$ 時，$Q^+=Q$，對應項為 $MN'Q$。 - $MN=11$ 時，$Q^+=0$，沒有輸出項。 所以： $$ Q^+=M'N+M'N'Q'+MN'Q $$ 這就是 M-N flip-flop 的 characteristic equation。 亦可由完整 minterm 表示為： $$ Q^+=\sum m(0,2,3,4,6) $$ 其中變數順序採用 $(M,N,Q)$。 --- (c) 以 T flip-flop 實現 M-N flip-flop T flip-flop 的特性為： $$ Q^+=…

Question 6

Consider the following state graph.

🖼️【此處有附圖，請對照原卷】

(a) Simplify the given state graph with input $X$ and output $Z$ . Draw the simplified state graph with minimum states.

(b) Implement the state graph in (a) using D flip-flops based on one-hot state assignment, which allocates one flip-flop for each state. Give the output function and all flip-flop input equations.

Accepted Answer

核心觀念 本題考查 Moore 狀態機的狀態等價與最小化，以及以 one-hot 編碼實作狀態機。 兩個 Moore 狀態等價，必須具有相同輸出，且對每一種輸入，其轉移到的狀態也等價。狀態合併後，若任一輸入的轉移仍落在同一組等價狀態內，分組便達到穩定，可得到最少狀態數。 解題方法 圖中有五個狀態：$S1$、$S2$、$S3$、$S4$、$S5$；輸出標示在狀態內，因此是 Moore 機。讀圖得到的轉移是：$S1$ 在 $X=0$ 時留在 $S1$、在 $X=1$ 時到 $S2$；$S2$ 依序轉到 $S1$、$S3$；$S3$ 轉到 $S4$、$S2$；$S4$ 轉到 $S5$、$S3$；$S5$ 轉到 $S4$、$S2$，其中每組目的地依序對應 $X=0,1$。 先依輸出分組： $$ \{S1,S2,S4\}: Z=1,\qquad \{S3,S5\}: Z=0 $$ 再檢查各狀態在 $X=0,1$ 下所到達的分組： | 狀態 | $Z$ | $X=0$ 到達的分組 | $X=1$ 到達的分組 | |---|---:|---|---| | $S1$ | 1 | $Z=1$ | $Z=1$ | | $S2$ | 1 | $Z=1$ | $Z=0$ | | $S4$ | 1 | $Z=0$ | $Z=0$ | | $S3$ | 0 | $Z=1$ | $Z=1$ | | $S5$ | 0 | $Z=1$ | $Z=1$ | $S1,S2,S4$ 的轉移特徵互不相同，因此不能再合併；$S3$ 與 $S5$ 輸出相同，且兩個輸入下都分別轉到 $S4$ 與 $S2$，所以可合併。合併後的狀態分組為： $$ A=\{S1\},\quad B=\{S2\},\quad C=\{S4\},\quad D=\{S3,S5\} $$ 最小狀態機的轉移如下： | 現態 | $Z$ | $X=0$ 次態 | $X=1$ 次態 | |---|---:|---|---| | $A$ | 1 | $A$ | $B$ | | $B$ | 1 | $A$ | $D$ | | $C$ | 1 | $D$ | $D$ | | $D$ | 0 | $C$ | $B$ |

Question 7

Sophie is designing a digital padlock for her treasure case. The padlock has two buttons (‘0’ and ‘1’) that, when pressed, cause the finite state machine (FSM) controlling the padlock to advance to a new state. In addition to advancing the FSM, each button press is encoded on the $B$ signal ($B=0$ for button ‘0’, $B=1$ for button ‘1’). The padlock unlocks when the FSM sets the Unlock output signal to 1, which it does whenever the last $N$ button presses are the same as the preset $N$-digit code. (a) Unfortunately, the design notes for the padlock are incomplete. Using the specification above and clues gleaned from the partially completed graphs below, please help Sophie to complete the state graph and its transition table. (Fill in the missing information.) Please note that when done, (1)…

Accepted Answer

核心觀念 本題考查有限狀態機的狀態轉移，以及 Moore 與 Mealy 機器的判別。狀態用來記錄目前輸入序列中，與密碼前綴相符的部分；每次輸入後，依仍匹配的最長前綴決定次狀態。Moore 機器的輸出只由目前狀態決定，Mealy 機器的輸出則由目前狀態與輸入共同決定。 解題方法 圖中可讀到：狀態 $00$ 的 Unlock 為 $0$，輸入 $B=0$ 時留在 $00$、輸入 $B=1$ 時轉至 $10$；狀態 $10$ 的 Unlock 為 $0$，輸入 $B=1$ 時留在 $10$。圖中另有狀態 $11$ 的 Unlock 為 $1$，而 $01$ 在 $B=0$ 時轉至 $11$。依這些線索補齊轉移。 從初始狀態 $00$ 開始，輸入 $1$ 轉至 $10$，再輸入 $0$ 轉至 $01$，再輸入 $0$ 轉至 $11$。因此，狀態 $10$、$01$、$11$ 分別代表目前序列末尾匹配密碼前綴 $1$、$10$、$100$。 逐一補齊轉移： - 狀態 $00$：輸入 $0$ 後仍沒有匹配的密碼前綴，留在 $00$；輸入 $1$ 後進入 $10$。 - 狀態 $10$：輸入 $0$ 後匹配到 $10$，進入 $01$；輸入 $1$ 後末尾仍匹配前綴 $1$，留在 $10$。 - 狀態 $01$：輸入 $0$ 後匹配到 $100$，進入 $11$；輸入 $1$ 後末尾重新以 $1$ 開始匹配，進入 $10$。 - 狀態 $11$：輸入下一個按鈕後，最近三次輸入不再是 $100$。輸入 $0$ 後沒有可保留的密碼前綴，轉至 $00$；輸入 $1$ 後保留前綴 $1$，轉至 $10$。 完整轉移表如下：

108 年國立臺灣大學電子工程學研究所丁組《邏輯設計》

第 1 題16 分

第 2 題16 分

核心觀念

(a) 依序對 $A,B,C,D$ 做 Shannon 展開

第一次：對 $A$ 展開

第二次：對 $B$ 展開

第三次：對 $C$ 展開

第四次：對 $D$ 展開並寫成完全展開式

(b) 依照完全 Shannon 展開使用 2-to-1 MUX

$D$ 層的輸入

第 2 題16 分

核心觀念

(a) 依序對 $A,B,C,D$ 做 Shannon 展開

第一次：對 $A$ 展開

第二次：對 $B$ 展開

第三次：對 $C$ 展開

第四次：對 $D$ 展開並寫成完全展開式

(b) 依照完全 Shannon 展開使用 2-to-1 MUX

$D$ 層的輸入

第 3 題18 分

核心觀念

解題方法

(a) POS 公式

第 4 題16 分

核心觀念

(a) 完成狀態表

(b) 推導 characteristic equation

(c) 以 T flip-flop 實現 M-N flip-flop

第 5 題16 分

核心觀念

解題方法

第 6 題18 分

其他考古題

108 年臺灣大學的其他科目

臺灣大學《邏輯設計》其他年度

其他學校的電子系考古題

108 年 國立臺灣大學電子工程學研究所丁組《邏輯設計》

第 1 題16 分

第 2 題16 分

核心觀念

(a) 依序對 A,B,C,DA,B,C,DA,B,C,D 做 Shannon 展開

第一次：對 AAA 展開

第二次：對 BBB 展開

第三次：對 CCC 展開

第四次：對 DDD 展開並寫成完全展開式

(b) 依照完全 Shannon 展開使用 2-to-1 MUX

DDD 層的輸入

第 2 題16 分

核心觀念

(a) 依序對 A,B,C,DA,B,C,DA,B,C,D 做 Shannon 展開

第一次：對 AAA 展開

第二次：對 BBB 展開

第三次：對 CCC 展開

第四次：對 DDD 展開並寫成完全展開式

(b) 依照完全 Shannon 展開使用 2-to-1 MUX

DDD 層的輸入

第 3 題18 分

核心觀念

解題方法

(a) POS 公式

第 4 題16 分

核心觀念

(a) 完成狀態表

(b) 推導 characteristic equation

(c) 以 T flip-flop 實現 M-N flip-flop

第 5 題16 分

核心觀念

解題方法

第 6 題18 分

其他考古題

108 年臺灣大學的其他科目

臺灣大學《邏輯設計》其他年度

其他學校的電子系考古題

108 年國立臺灣大學電子工程學研究所丁組《邏輯設計》

(a) 依序對 $A,B,C,D$ 做 Shannon 展開

第一次：對 $A$ 展開

第二次：對 $B$ 展開

第三次：對 $C$ 展開

第四次：對 $D$ 展開並寫成完全展開式

$D$ 層的輸入

(a) 依序對 $A,B,C,D$ 做 Shannon 展開

第一次：對 $A$ 展開

第二次：對 $B$ 展開

第三次：對 $C$ 展開

第四次：對 $D$ 展開並寫成完全展開式

$D$ 層的輸入