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

核心觀念

函數在變數轉換後保持不變，代表同一等價類中的 minterm 必須有相同函數值。先依轉換找出等價類，再用已知格子的值傳播到同類 minterm。SOP 則可用 Karnaugh map 的相鄰格分組化簡。

解題方法

原圖欄位依序為 $ab=00,01,11,10$，列依序為 $cd=00,01,11,10$；已知 $m_0=0$、$m_{13}=0$、$m_9=1$、$m_7=1$、$m_{14}=0$。題目給定交換 $a,b$ 不變，且 $(a,b,c,d)$ 換成 $(a,\bar c,\bar b,d)$ 後函數值不變。以下依這兩種轉換建立等價類。

以 $m_i$ 的索引為二進位 $abcd$ 表示。兩種轉換都不改變 $d$；對 $abc$ 的等價類如下：

$abc$ 等價類	$d=0$ 對應 minterm	$d=1$ 對應 minterm
$\{000,011,101\}$	$\{m_0,m_6,m_{10}\}$	$\{m_1,m_7,m_{11}\}$
$\{100,010,111\}$	$\{m_4,m_8,m_{14}\}$	$\{m_5,m_9,m_{15}\}$
$\{001\}$	$\{m_2\}$	$\{m_3\}$
$\{110\}$	$\{m_{12}\}$	$\{m_{13}\}$

因此，$m_0=0$ 使 $m_6,m_{10}$ 為 $0$；$m_{14}=0$ 使 $m_4,m_8$ 為 $0$。同理，$m_7=1$ 使 $m_1,m_{11}$ 為 $1$；$m_9=1$ 使 $m_5,m_{15}$ 為 $1$。$m_2,m_3,m_{12}$ 各自所在的等價類沒有其他已知值，因此尚未確定。

完整 Karnaugh map 如下；「？」表示未被唯一決定：

$cd\backslash ab$	$00$	$01$	$11$	$10$
$00$	$0\ (m_0)$	$0\ (m_4)$	$?\ (m_{12})$	$0\ (m_8)$
$01$	$1\ (m_1)$	$1\ (m_5)$	$0\ (m_{13})$	$1\ (m_9)$
$11$	$?\ (m_3)$	$1\ (m_7)$	$1\ (m_{15})$	$1\ (m_{11})$
$10$	$?\ (m_2)$	$0\ (m_6)$	$0\ (m_{14})$	$0\ (m_{10})$

(a) 唯一確定的 minterm

核心觀念

本題考查：

1. 由條件式建立四變數 Boolean function 的 Karnaugh map。
2. 利用相鄰的 $1$ 格進行圈選，化簡為 minimum SOP。
3. 判斷兩層 AND-OR 電路的 static 1-hazard。
4. 利用共識項（consensus term）補足 hazard-free SOP。

Static 1-hazard 的判斷原則是：

若兩個相鄰的 $1$ 格在 SOP 中沒有被同一個 product term 覆蓋，輸入變化時可能因閘門延遲不同而產生瞬間的 $0$。

因此，hazard-free SOP 必須使每一對相鄰的 $1$ 格至少被同一個乘積項涵蓋。

---

(a) Karnaugh map 與 minimum SOP

1. 依條件列出各情況

當 $x_1=0$ 時：

$$f=x_2'x_3+x_2x_4$$

因此：

• $x_2=0$ 時，$f=x_3$；
• $x_2=1$ 時，$f=x_4$。

當 $x_1=1$ 時：

• $x_2=0$：

$$f=x_3x_4'$$

• $x_2=1$：

$$f=x_3+x_4'$$

2. 找出輸出為 $1$ 的 minterms

依照變數順序 $x_1x_2x_3x_4$：

• $x_1=0,x_2=0$：$x_3=1$

$$m_2,m_3$$

• $x_1=0,x_2=1$：$x_4=1$

$$m_5,m_7$$

• $x_1=1,x_2=0$：$x_3x_4'=1$

$$m_{10}$$

• $x_1=1,x_2=1$：$x_3+x_4'=1$

$$m_{12},m_{14},m_{15}$$

所以：

$$f=\sum m(1,2,3,5,7,10,12,14,15)$$

3. Karnaugh map

列採用 $x_3x_4=00,01,11,10$ 的 Gray code 順序，列採用 $x_1x_2=00,01,11,10$：

$x_1x_2\backslash x_3x_4$	00	01	11	10
00	0	1	1	1
01	0	1	1	0
11	1	0	1	1
10	0	0	0	1

4. 圈選

可作以下圈選：

圈選一：四格

涵蓋 $m_1,m_3,m_5,m_7$：

$$x_1'x_4$$

圈選二：兩格

涵蓋 $m_2,m_{10}$：

$$x_2'x_3x_4'$$

圈選三：兩格

涵蓋 $m_{10},m_{14}$：

$$x_1x_3x_4'$$

圈選四：兩格

涵蓋 $m_{12},m_{14}$：

$$x_1x_2x_4'$$

圈選五：兩格

涵蓋 $m_{14},m_{15}$：

$$x_1x_2x_3$$

因此 minimum SOP 為：

$$\boxed{ f=x_1'x_4+x_2'x_3x_4'+x_1x_3x_4'+x_1x_2x_4'+x_1x_2x_3 }$$

其中：

• $m_1,m_5,m_7$ 主要由 $x_1'x_4$ 覆蓋；
• $m_2$ 需要 $x_2'x_3x_4'$；
• $m_{12}$ 需要 $x_1x_2x_4'$；
• $m_{15}$ 需要 $x_1x_2x_3$；
• $m_{10}$、$m_{14}$ 可由相鄰圈選共同覆蓋。

---

核心觀念

令開關閉合時為 $1$，斷開時為 $0$。左、右端點相連的條件，是存在一條由左端點到右端點的「全閉合路徑」。

• 串聯：所有開關都閉合，使用 AND。
• 並聯：任一路徑成立即可，使用 OR。
• SOP：列出所有可能的導通路徑。
• POS：列出所有能切斷電路的最小割集。

圖中的五個開關形成兩條水平支路，並由 $C$ 連接上下兩支路的中點。

(a) 最小 SOP

由左端點到右端點共有四條最小導通路徑：

1. 上方路徑：$A$、$B$ 串聯，條件為 $AB$。
2. 下方路徑：$D$、$E$ 串聯，條件為 $DE$。
3. 經由中央開關的左上至右下路徑：$A$、$C$、$E$，條件為 $ACE$。
4. 經由中央開關的左下至右上路徑：$D$、$C$、$B$，條件為 $BCD$。

因此連接函數為

$$F=AB+DE+ACE+BCD$$

這已是最小 SOP。四個乘積項分別對應四個必要的最小導通路徑，無法再以吸收律刪除。

(b) 最小 POS

改以「切斷左、右端點連接」來找最小割集。

最小割集一：$A$ 與 $D$

若 $A$、$D$ 同時斷開，左端點無法進入電路，因此對應最大項

$$(A+D)$$

最小割集二：$B$ 與 $E$

核心觀念

此題考查同步循序電路的時序分析，包含：

• 暫存器的 clock-to-Q 延遲 $t_{CQ}$
• 組合邏輯延遲
• D 觸發器的 setup time $t_{setup}$
• hold time $t_{hold}$
• clock skew 對資料傳遞時間的影響

由電路圖可得：

$$D_1=\overline{RESET+Q_0}$$

$Q_1$ 經過兩個反相器後送至 $D_0$，因此：

$$D_0=Q_1$$

其中 $Q_1=S_1$、$Q_0=S_0$。

---

(a) 最小 clock period

同步電路的 setup time 約束為：

$$T_{clk}\geq t_{CQ}+t_{logic}+t_{setup}$$

$Q_0$ 到 $D_1$ 的路徑

此路徑經過 NOR gate：

$$T_{Q_0\to D_1} =2+2+3 =7\text{ ns}$$

$Q_1$ 到 $D_0$ 的路徑

此路徑經過兩個 inverter：

$$T_{Q_1\to D_0} =2+2+2+3 =9\text{ ns}$$

必須滿足所有資料路徑的 setup time，因此取較大值：

$$T_{clk,\min}=\max(7,9)=9\text{ ns}$$

hold time 亦符合，因為最早資料變化至少在 clock edge 後 $2\text{ ns}$ 才發生，而 hold time 只有 $1\text{ ns}$。

---

(b) 移除兩個 inverter 後的電路

移除兩個 inverter 後，邏輯功能仍為：

$$D_0=Q_1$$

因此功能上仍可正常運作。

此時 $Q_1$ 到 $D_0$ 的路徑只剩下觸發器本身的 clock-to-Q 延遲：

$$T_{Q_1\to D_0}=2+3=5\text{ ns}$$

而 $Q_0$ 到 $D_1$ 的路徑仍需：

$$2+2+3=7\text{ ns}$$

所以最佳化後的最小 clock period 為：

$$T_{clk,\min}=\max(5,7)=7\text{ ns}$$

因此，最佳化電路可以正常運作，但 clock period 必須由原本至少 $9\text{ ns}$ 調整為至少 $7\text{ ns}$。

---

(c) RESET 設為 $1$

當 $RESET=1$ 時，NOR gate 輸出必定為 $0$：

核心觀念

本題考查：

• Moore 型有限狀態機：輸出只由「目前狀態」決定。
• 序列偵測器：狀態代表目前輸入序列與目標序列前綴的最長匹配部分。
• 狀態最小化：不同狀態若能被某段輸入序列產生不同輸出，就不能合併。
• 未使用狀態的處理：D 觸發器上電值不定，因此所有狀態編碼都必須定義後續行為。

目標序列為：

$$0110$$

要求最後四次按鍵恰為 $0110$ 時，輸出 $U=1$。

---

(a) 最少狀態 Moore FSM

狀態定義

令各狀態代表目前輸入序列與 $0110$ 的最長前綴匹配結果：

狀態	意義	Moore 輸出
$A$	沒有匹配到有效前綴	$0$
$B$	最近輸入為 $0$	$0$
$C$	最近輸入為 $01$	$0$
$D$	最近輸入為 $011$	$0$
$E$	最近四次輸入為 $0110$	$1$

狀態轉移推導

• $A$：

  • 輸入 $0$：形成前綴 $0$，到 $B$
  • 輸入 $1$：沒有任何有效前綴，留在 $A$

• $B$：

  • 輸入 $0$：最近仍可視為前綴 $0$，留在 $B$
  • 輸入 $1$：形成 $01$，到 $C$

• $C$：

  • 輸入 $0$：序列為 $010$，尾端仍有前綴 $0$，到 $B$
  • 輸入 $1$：形成 $011$，到 $D$

• $D$：

  • 輸入 $0$：形成 $0110$，到 $E$
  • 輸入 $1$：序列尾端沒有有效前綴，回到 $A$

• $E$：

  • 輸入 $0$：序列為 $01100$，尾端的有效前綴為 $0$，到 $B$
  • 輸入 $1$：序列為 $01101$，尾端的有效前綴為 $01$，到 $C$

狀態轉移表如下：

目前狀態	輸入 $0$	輸入 $1$	輸出
$A$	$B$	$A$	$0$
$B$	$B$	$C$	$0$
$C$	$B$	$D$	$0$
$D$	$E$	$A$	$0$
$E$	$B$	$C$	$1$

文字狀態圖可表示為：

• $A \xrightarrow{0} B,\ A \xrightarrow{1} A$
• $B \xrightarrow{0} B,\ B \xrightarrow{1} C$
• $C \xrightarrow{0} B,\ C \xrightarrow{1} D$
• $D \xrightarrow{0} E,\ D \xrightarrow{1} A$
• $E \xrightarrow{0} B,\ E \xrightarrow{1} C$

其中 $E$ 的輸出為 $1$，其餘狀態輸出皆為 $0$。

此設計可以正確處理重疊序列。例如輸入 $0110110$ 時，第二次出現的 $0110$ 仍能被偵測。

---

(b) 是否可能少於 5 個狀態？

不可能。

五個狀態分別代表：

$$\varnothing,\quad 0,\quad 01,\quad 011,\quad 0110$$

這些狀態兩兩皆可由某段後續輸入區分。例如：

• $A$ 與 $B$：輸入 $110$ 時，$B$ 可到達解鎖狀態，而 $A$ 不會。
• $B$ 與 $C$：輸入 $10$ 時，$C$ 可到達 $E$，而 $B$ 不會。
• $C$ 與 $D$：輸入 $0$ 時，$D$ 到 $E$，而 $C$ 到 $B$。
• $D$ 與 $E$：空輸入即可區分，因為 $E$ 的輸出為 $1$，$D$ 的輸出為 $0$。
• 其他狀態間也可利用適當後續輸入，使其中一個到達 $E$ 而另一個不到達 $E$。

根據有限狀態機最小化原理，若兩個狀態存在某段輸入序列會產生不同輸出，兩者便不可合併。因此最少需要：

$$\boxed{5\text{ 個狀態}}$$

---

(c) 未使用狀態的處理

五個狀態至少需要 $3$ 個 D 觸發器，因為：

$$2^2<5\leq 2^3$$

三個 D 觸發器共有 $8$ 種狀態，其中有三種未使用狀態。

核心觀念

本題考的是 Moore 狀態機的狀態等價與電路等價。圖中圓圈內的「狀態／數字」表示狀態名稱與該狀態的輸出，箭線上的數字表示輸入。

兩個狀態等價，必須滿足：

1. 目前輸出相同。
2. 對每一種輸入，其後繼狀態仍然等價。

因此，可以先依輸出分組，再依後繼狀態反覆細分，直到分組不再改變。若某個輸入序列使兩電路的輸出不同，該序列就是區分序列。

解題方法：讀圖與轉移表

原圖中，$C_1$ 只有 $S_3$ 的輸出為 $1$，$C_2$ 只有 $T_2$ 的輸出為 $1$。但 $T_1$ 的自迴圈與 $T_1\to T_2$ 向下箭線都標示為 $0$，因此 $T_1$ 在輸入 $0$ 時有兩個後繼狀態，不符合確定性 Moore 狀態機的定義。

原題缺少的是 $T_1$ 在輸入 $0$ 時唯一的正確轉移。以下採用明確的修正假設：保留向下箭線 $T_1\xrightarrow{0}T_2$，將 $T_1$ 的自迴圈視為多畫的箭線。此假設下的轉移表如下：

電路	現態	輸出	輸入 $0$ 的次態	輸入 $1$ 的次態
$C_1$	$S_0$	$0$	$S_2$	$S_1$
$C_1$	$S_1$	$0$	$S_0$	$S_3$
$C_1$	$S_2$	$0$	$S_0$	$S_1$
$C_1$	$S_3$	$1$	$S_3$	$S_2$
$C_2$	$T_0$	$0$	$T_0$	$T_3$
$C_2$	$T_1$	$0$	$T_2$	$T_0$
$C_2$	$T_2$	$1$	$T_2$	$T_0$
$C_2$	$T_3$	$0$	$T_0$	$T_2$

(a) $C_1$ 的等價狀態

先依輸出分組：

$$P_0=\bigl\{\{S_0,S_1,S_2\},\{S_3\}\bigr\}.$$

輸入 $1$ 時，$S_1$ 進入輸出為 $1$ 的 $S_3$；$S_0$ 與 $S_2$ 都進入輸出為 $0$ 的 $S_1$，所以 $S_1$ 必須獨立成組：

$$P_1=\bigl\{\{S_0,S_2\},\{S_1\},\{S_3\}\bigr\}.$$

對 $S_0$ 與 $S_2$：

• 輸入 $0$：兩者的次態都落在 $\{S_0,S_2\}$。
• 輸入 $1$：兩者的次態都是 $S_1$。

分組不再改變，故

$$S_0\equiv S_2.$$

因此，$C_1$ 有 $3$ 個非等價狀態類別。

(b) $C_2$ 的等價狀態

在上述修正假設下，初始分組為

$$P_0=\bigl\{\{T_0,T_1,T_3\},\{T_2\}\bigr\}.$$

比較輸出為 $0$ 的三個狀態：

• $T_1$ 與 $T_0$：輸入 $0$ 後，分別到達 $T_2$ 與 $T_0$，輸出為 $1$ 與 $0$。
• $T_1$ 與 $T_3$：輸入 $0$ 後，分別到達 $T_2$ 與 $T_0$，輸出為 $1$ 與 $0$。
• $T_0$ 與 $T_3$：輸入 $1$ 後，分別到達 $T_3$ 與 $T_2$，輸出為 $0$ 與 $1$。

三者彼此都不等價；$T_2$ 的目前輸出又與三者不同。因此，$C_2$ 有 $4$ 個非等價狀態，沒有等價狀態對。

(c) 從 $S_0$ 與 $T_0$ 出發是否等價？

等價。 從 $T_0$ 出發只能到達 $T_0,T_3,T_2$，不會到達 $T_1$，所以本小題不受 $T_1$ 的圖面歧義影響。

將 $C_1$ 的等價狀態合併，定義

$$A=\{S_0,S_2\},\qquad B=\{S_1\},\qquad C=\{S_3\}.$$

其轉移與 $C_2$ 的對應如下：