---
title: Multi-Level Gate 和 Hazards|第六週
tags: 數位系統與實驗
---
:::info
有時候 level 低但是 input 很大，不是一件好事，會增加延遲等等
:::

# 特殊題目

有些題目會要求限制 input 的數量，像是必須要小於等於 3 之類的

此時你可以用 factoring ，也就是以前的boolean algebra 來化簡

如果是 Multiple output 的， K-Map 可能會幫上一些忙，最後再搭配 Factoring

## NAND 或 NOR

如果題目要求全部的 Gates 都是 NAND 或 NOR

只要記得跟 SOP 和 POS 的關係，其實就可以發現，只要呈現 AND OR AND OR...的樣子，就可以很容易轉成NAND

不管是有成對，還是有一個落單都行，因為落單的可以把 NOT 移到 Input

相對的，OR AND OR AND...也是

---

# Gate Delay

## Propagation delay

每次的 Input 跟 output，是對齊的嗎？
並不是，畢竟電子還是有一定的速度


>上面是 Input 下面是 Output

而這之間的差距就是 Propagation delay

假設下圖每個 Gate 延遲各為 20ns


上面情況是 B = 1, C = 0

因此在邏輯上 G~1~ 是 A, G~2~ 是 A'；這在邏輯上是對的
但是如果你考量了延遲，那麼這幾個人的值就不會同步更新，也就不保證上面的邏輯是對的
所以可以發現在中間有一段時間， A = 1，並且 G~2~ 也是 1

# Hazards

就是因為上面延遲的關係，導致實際情形跟原本預想的設計不一樣

## Static 1-Hazards

**原本應該永遠是 1 ，卻突然變 0，然後又變回 1**


### 例子

假設每個閘的延遲都是 10ns

當 A = C = 1 的時候，F = B(E) + B'(D)

觀察一下會發現，當 B 從 1 移動到 0 的時候，會發生 Static 1-Hazards


上面可以觀察到

- E 的移動等同 B，畢竟在 C = 1 的時候那個 AND 閘情況等同 B
- D 的情況同理
- D 閘因為比 E 閘多經過一個 NOT 閘，所以延遲多了 10 ns
- 因此原本一正一反的交接處，就出現了縫隙


來看看這在卡諾圖上發生甚麼事


也就是說我們「跨過了」，「兩團 1」的邊緣
由於上面的例子中，因為跟卡諾圖得到的 SOP 一模一樣，這裡剛好可以用卡諾圖解釋

- 「兩團 1」其實對應的就是 Level 2 的 Gates
- 不要忘記 Level 的階層是從 Output 開始往回算
- 但是兩個閘，在「一個情況下」的值並不同，只不過因為最後 OR 起來才導致結果一樣
- 也就是說一個值為 1，一個值為 0
- 因此跨過這兩個閘的時候，加上延遲的影響，就會產生 Static 1-hazards

### 怎麼解決？

既然原因是跨過了兩個閘，使得 Level 1 的 OR 閘，兩個輸入一個為 1 一個為 0
那麼，我們就不要跨過閘就好了
**也就是說，我們把兩團 1 的交接處接起來**

這樣就可以確保 Level 1 的 OR 閘，一定有一個輸入恆為 1，那麼結果就一定是 1


這樣子我們在 A = C = 1 的時候，將 B 從 1 移動到 0
雖然會跨過另外兩個閘，但是等同在我們新建立的閘裡面移動，因此就可以消除掉 Static 1-hazards


從上面的電路圖也可以發現， F = B' + B + 1 = 1

:::warning
所以可以發現，如果你今天是探討特定情形，像是上面的從 {111|ABC} → {101|ABC}
在化簡的時候，遇到像是 X + X' 的，或是 XX' 的，都不能輕易忽略
>XX' 下面會舉例
:::

### 小結論

由於到底會不會發生 hazard，跟「每條路的延遲」有很大的關係
如果以 Two Level Gate 為例的話，假設在不知道各個閘延遲的情況下
任何兩個相鄰的 1 都要被框在一起，否則就有可能會有 Static 1-hazards

所以我們這裡來看看，**上面是 B 從 1 到 0，如果是從 0 到 1 會發生甚麼事**

$$
D = B, E = B'
$$


會發現，跨過兩個閘造成延遲的情形依舊存在，只不過從「同時為 0」變成了「同時為 1」
這對於 OR 閘的輸出結果並沒有影響，也就是說 {101|ABC} → {111|ABC} 並沒有 Static 1-hazards

:::info
也就是說， D 閘，這個跟 B 相反的閘，他的延遲快慢，會影響到底是哪種情形有 Hazard
要注意，這只是 Two Level Gate 的一個簡單例子，更複雜的情況是都有可能會發生
實際到底是什麼情形導致 Hazards ，要分析的話會非常複雜
:::

:::success
總之要記住的就是，在不清楚各個延遲的情況下
跨過「兩團 1」，或者說兩個閘的時候，相鄰的 1 沒有框起來就有機會發生 Hazards
:::

## Static 0-Hazards

**原本應該永遠是 0 ，卻突然變 1，然後又變回 0**


### 例子

代入 A = 0, B = 1, D = 0

$$
Z=(A+C)(A'+D')(B'+C'+D)=CC'
$$

所以可以發現化簡後，出現了 $CC'$，這就是造成 hazards 的壞份子


化簡後長得像這樣


於是敏銳的我們就會發現，有 C' 的那一條路，或者說與原輸出相反的閘，他的延遲比較高
此時回想上面的那個交接錯開的圖

$$
D = C', E=C
$$


就知道，他們有了同時有 1 的情況

:::warning
可以下個小結論
- 如果與輸入相反的 Path 延遲「較高」
- 則 1 → 0 會產生「同時為 0」
- 則 0 → 1 會產生「同時為 1」
- 如果與輸入相反的 Path 延遲「較低」
- 則 1 → 0 會產生「同時為 1」
- 則 0 → 1 會產生「同時為 0」

這個結論其實不用背，只要畫出上面的圖就知道了
:::


所以這個讓原本應該持續輸出為 0 的電路，輸出跑出了 1 ，就是 **Static 0-harzards**

所以放到卡諾圖上也是同一回事，就是我們跨過了「兩團 0」，或者說兩個閘

所以解決的方式也一樣，就是把會跨過兩個閘的地方圈起來，**「要記得圈大」**


### 1-hazards 發生在 SOP，0-hazards 發生在 POS？

其實上面這兩個例子會發現有照著這個邏輯，因為這對於 SOP 跟 POS 這兩種 Two-Level Circuit 是對的

並且，**0-hazards 不會發生在 SOP，1-hazards 不會發生在 POS**

### 推導 0-hazards 不會發生在 Two-Level Circuit SOP

如果要這種電路產生出 0，代表第 2 Level 的 AND 全部輸出都要是 0
也就代表不管是哪種 0 的情形，路都是不通的，或者說 AND 閘的結果都是 0

### 推導 1-hazards 不會發生在 Two-Level Circuit POS

如果要這種電路產生出 1，代表第 2 Level 的 OR 全部輸出都要是 1
也就代表不管是哪種 1 的情形，路都是通的，或者說 OR 閘的結果都是 1

---

# Dynamic Hazards 和 Multilevel Circuit

**原本應該只要「 0 變成 1」「一次」**
**但是變成 1 後又變成 0，然後又變成 1，可能這種情形很多次**


Multilevel Circuit，也就是說情形不再像上面 Two-Level Circuit 這麼親切

# 基本找法

$$
F=(A'C'+B'C)(C+D)=A'C'C+B'C+A'C'D
$$

## 將式子乘開，但保留 Complementation Law 的結果

像上面 $CC'$ 就是要保留起來的結果

## 分析出 $XX'\alpha$ 和 $X+X'+\beta$

這兩個分別對應到的是 static 0 跟 static 1，因為：

- 當 $\alpha = 1$ 的時候，$XX'$ 就有機會讓 AND Gate 產生出 1 的結果，也就是 Static 0 hazard
- 當 $\beta = 0$ 的時候，$X+X'$ 就有機會讓 OR Gate 產生出 0 的結果，也就是 Static 1 hazard

## 電路設計的影響

實際上，每個閘的延遲各有不同，所以各種電路的 hazard 情形也會不一樣，但假如我們假設各個閘的延遲都一樣的話，我們可以用迪摩根定律改變電路的樣子來分析，下面的例子就是用迪摩根定律全都改為 NOR 閘進行分析

:::warning
還是要記得，各種電路的延遲情形都不一樣
:::

## 例子分析 Static 1 hazard

$$
F=(A'C'+B'C)(C+D)=A'C'C+B'C+A'C'D
$$

根據上面的步驟，就是要找出 $X+X'+\beta$ 的情形，所以很明顯的可以知道：

- $A'=1 \Rightarrow A=0$
- $B'=1 \Rightarrow B=0$
- $D=1$

這樣子的話上面就會剩下 $C'C+C+C'$，然後 hazard 發生時就是 $C$ 跟 $C'$ 同時為 0
而 $C'C$ 在這個情況也會是 0，所以並不影響，可以先不理他。

這時候對照一下卡諾圖


情況也符合我們需要的，從 1 移動到另一個 1。

於是我們就來看電路會發生甚麼事：

$$
ABCD←→ABCD\\
0\ 0\ 0\ 1\ ←→\ 0\ 0\ 1\ 1\
$$


可以發現，Level 2 的上面那個 NOR 閘，在邏輯上應該是恆為 0，但是由於 input 的下路延遲比較高，所以那個閘的交接處會錯開，使得 NOR 閘的輸出會出現 1(兩個輸出 0 的情況交疊在一起)

這樣就導致最後的輸出本應該恆為 1，卻突然出現了 0。

:::warning
如果 C 是從 1 變成 0，則後面會變成兩個輸出 1 的情況交疊在一起，這樣並不影響結果
所以並不會有 Hazard
:::

## 例子分析 Static 0 hazard

$$
F=(A'C'+B'C)(C+D)=A'C'C+B'C+A'C'D
$$

根據上面的步驟，就是要找出 $XX'\alpha$ 的情形，所以很明顯的可以知道：

- $A'=1 \Rightarrow A=0$
- $B'=0 \Rightarrow B=1$
- $D=0$

這樣子的話上面就會剩下 $C'C$，然後 hazard 發生時就是 $C$ 跟 $C'$ 同時為 0
而 $C'C$ 在這個情況也會是 0，所以並不影響，可以先不理他。

這時候對照一下卡諾圖


情況也符合我們需要的，從 0 移動到另一個 0。

:::info
這只是沿用上一張的圖，不要裡那個紅色箭頭 \_(:3｣L)_
:::

來看看電路發生了甚麼事

$$
ABCD←→ABCD\\
0\ 1\ 0\ 0\ ←→\ 0\ 1\ 1\ 0\
$$


可以發現，Level 的 NOR 閘，在邏輯上應該是恆為 0，但是由於 input 的上路延遲比較高，所以那個閘的交接處會錯開，使得 NOR 閘的輸出會出現 1(兩個輸出 0 的情況交疊在一起)

這樣就導致最後的輸出本應該恆為 0，卻突然出現了 1。

而也可以知道，如果是 C 從 1 變成 0，交疊的就是 0 的部分，那麼就不會有 hazard 了

## 例子分析 Dynamic hazard

$$
F=(A'C'+B'C)(C+D)=A'C'C+B'C+A'C'D
$$

Dynamic 根據定義就是原本只要一次的變化，卻多了很多次；是由於**電路內有 Static hazard 造成的**
像下面的例子，原本應該輸出只會是 0 變成 1，卻因為 Level 2 出現了 Static 0 hazard，所以導致結果從 0 變成 1 變化了兩次

:::success
說實在用 NOR 閘表示電路，情形都會反過來一次，大腦就要多轉一次有點不方便...
:::


### 分析 1 -- 保留 Static Hazard

既然要保留 Static hazard，可以知道

$$
A'=1 \Rightarrow A=0
$$

這是一定要保留的

### 分析 2 -- 卡諾圖

接下來翻開覆蓋的魔法卡，卡諾圖


Dynamic 就是要輸出從 1 到 0 或 0 到 1，所以搭配上面已知 $A=0$，可以知道有四種可能

### 分析 3 -- 電路圖

要產生 Dynamic Hazard，最後一個重點就是

**改變的那個輸出，在那個情形下一定要通過 3 條路以上**


所以很明顯的，唯一有可能通過三條路的，就只有輸入 $C$，所以卡諾圖推得出的情形，就剩 2 種了。

### 情形 1

$$
ABCD←→ABCD\\
0\ 0\ 0\ 0\ ←→\ 0\ 0\ 1\ 0\
$$

這個就是上面舉的例子，所以當 C 從 0 變成 1，會使得 Level 2 產生 Static 0 hazard，進而影響結果
但是當 C 從 1 變成 0，就不會有 Static 0 hazard，所以也就沒有 Dynamic hazard

### 情形 2

$$
ABCD←→ABCD\\
0\ 1\ 0\ 1\ ←→\ 0\ 1\ 1\ 1\
$$


會發現，由於 $C$ 只剩下一條路可走，所以可以知道就不會產生任何 hazard，也就沒有了 Dynamic Hazard

---

# 換個想法

我們從最前面一開始討論 Static 的時候知道一件事，如果要有 Static hazard，改變的那個輸入，必須要經過兩條路以上，這樣才有機會造成前面所提到的 $XX'\alpha$ 跟 $X+X'+\beta$

所以如果我們不將上面的電路圖轉換成 NOR 閘，直接看原圖：

$$
F=(A'C'+B'C)(C+D)=A'C'C+B'C+A'C'D
$$


---

## Static 1 hazard

原本應該要一直為 1，卻突然出現 0；當初在討論 Two Level 的時候，只有最後一個閘是 OR 閘的時候才有可能發生，而現在電路的 Level 1 閘卻是 AND 閘，所以，**真相，只有一個**：

**Level 1 AND 原本兩條 Input 都是 1，卻突然有一路短暫的變成 0**

**也就是某條路出現了 Static 1 Hazard**

這時候來分段討論一下。

### 下路

仔細一看，下路的 OR 閘就只有各自一個輸入，並沒有出現甚麼一個輸入控制兩條路的情形
所以可以知道下路就是恆為 1 的那條路，於是我們便知道：

$$
C+D=1
$$

那這時候到底上下輸入誰是 1，還是都是 1？我們可以先放著，先看看上路

### 上路

由剛剛的推論可以知道，這個閘必須要發生 Static 1 Hazard，也就是說這個 OR 閘的兩個輸入
**必須一個是 1 一個是 0**

所以這時候看看上路的輸入中，誰控制了兩條路；很明顯的，只有輸入 C 辦的到這件事
於是我們知道，如果要讓 C 可以控制兩條路，那麼：

$$
A=0,B=0
$$

而且剛剛下路的問題也解決了，因為我們知道 C 是要變動的輸入，所以：

$$
D = 1
$$

**這個結論跟上面的推導是一樣的**

所以接下來就是看 C 究竟是 1 到 0 還是 0 到 1；但是在前面 Two Level 的地方，我們有做個小結論
那些小結論可以知道，想要產生 Static 1 hazard，錯開交接處時重疊的部分一定要是 0


也就是說

- 上方輸入 $A'C'=1→0$，下方輸入 $B'C=0→1$
- 要讓 0 交疊在一起的話，就是要下方輸入延遲比較高
- 上方輸入 $A'C'=0→1$，下方輸入 $B'C=1→0$
- 要讓 0 交疊在一起的話，就是要上方輸入延遲比較高

所以也就是說，不能再假設每個閘的延遲一樣；當然，如果每個閘延遲一樣的話，因為 NOT 閘在上方輸入，所以就是 C 從 1 變成 0 的時候才會有 Static 1 hazard

而這也跟上面的推論...不一樣，因為上面轉成 NOR 閘了，所以 NOT 閘跑到下面輸入去了...

$$
ABCD→ABCD\\
0\ 0\ 0\ 1\ →\ 0\ 0\ 1\ 1\
$$

---

## Static 0 hazard

:::warning
有了上面的基礎後，下面開始飆車
:::

$$
F=(A'C'+B'C)(C+D)=A'C'C+B'C+A'C'D
$$


原本應該要一直為 0，卻突然出現 1，而且 Level 是 AND 閘，所以兩個輸入一個為 1 另一個為 0

然後要控制多條路的一樣只有 C 可以，所以可以知道

$$
D = 0
$$

而且要產生 C 一條路為 1 一條路為 0，可以知道一定要通過有 NOT 閘的路

$$
A=0,B=1
$$

**這個結論跟上面的推導是一樣的**

所以跟以前一樣

- 上方輸入 $C'=1→0$，下方輸入 $C=0→1$
- 要讓 1 交疊在一起的話，就是要上方輸入延遲比較高
- 上方輸入 $C'=0→1$，下方輸入 $C=1→0$
- 要讓 1 交疊在一起的話，就是要下方輸入延遲比較高

所以一樣如果假設每個閘延遲都一樣，很明顯的上面經過比較多閘，也就是上面延遲比較高
所以就是 $C=0→1$

而這跟上面的推論一樣，因為上面經過了兩次 NOR 閘，所以就又換回來了

$$
ABCD→ABCD\\
0\ 1\ 0\ 0\ →\ 0\ 1\ 1\ 0\
$$

---

## Dynamic hazard

$$
F=(A'C'+B'C)(C+D)=A'C'C+B'C+A'C'D
$$


**原本應該要只從 1 變成 0 或 0 變成 1 一次，但是卻變了很多次**

- 1 變成 0
- 也就是 Level 1 的 AND 閘，兩路從原本都是 1，變成一條路是 0，或兩條路都變成 0
- 但是要發生 Dynamic，只有**一路恆為 1，並且發生 Static 1 才有可能**
- 假設 A 路恆為 1，B 路從 1 變成 0
- 首先 A 發生 Static 1 hazard，使得輸出從 1 變成 0 再變成 1
- 再來 B 路從 1 變成 0，則輸出則也從 1 再變成 0
- 兩條路最終都會變成 0 的話並不會有 Dynamic hazard，因為誰先變成 0，結果依舊是 0
- 0 變成 1
- 也就是 Level 1 的 AND 閘，原本一條路是 0，或兩條路都是 0，變成兩條路都是 1
- 但是要發生 Dynamic，只有**一路恆為 1，並且發生 Static 1 才有可能**
- 假設 A 路恆為 1，B 路從 0 變成 1
- 首先 B 路從 0 變成 1，則輸出也從 0 變成 1
- 再來 A 發生 Static 1 hazard，使得輸出從 1 變成 0 再變成 1
- 兩條路都從 0 變成 1 的話並不會有 Dynamic hazard，因為要兩者同時為 1，輸出才會是 1

:::warning
上面的推論，如果 Level 1 的閘是 OR 閘，情況就會相反
:::

所以我們知道，不管是哪種方向，Level 2 的閘都要有個恆為 1，然後另一個從 0 變 1 或從 1 變 0
而且恆為 1 的那個閘，是要可以發生 Static hazard 的

所以唯一符合情況的例子，就是上方的 Level 2 閘恆為 1，下方 Level 2 閘是變化的閘

而這些條件判定下來，可以知道：

$$
D = 0
$$

這樣下方 Level 2 的 OR 閘才可以被 C 控制。然後：

$$
A = 0, B = 0
$$

這樣上方 Level 2 的 OR 閘，他的兩個 Input 才可以被 C 控制

**而這跟我們上面的推論結果一樣**

- 如果 $C:1→0$，代表 Level 2 下方 OR 閘是從 1 到 0
- 而 Level 2 上方 OR 閘，必須要發生 Static 1 hazard
- 也就是說 Level 3 的兩個 AND 閘，經過延遲的錯開後，交疊的部分必須為 0
- 而 Level 3 下路是 1 變成 0，上路是 0 變成 1
- 也就是說必須要上路的延遲比較高，才會發生
- 如果 $C:0→1$，代表 Level 2 下方 OR 閘是從 0 到 1
- 而 Level 2 上方 OR 閘，必須要發生 Static 1 hazard
- 也就是說 Level 3 的兩個 AND 閘，經過延遲的錯開後，交疊的部分必須為 0
- 而 Level 3 下路是 0 變成 1，上路是 1 變成 0
- 也就是說必須要下路的延遲比較高，才會發生

假設每個閘延遲一樣的話，可以看出應該是 Level 3 上路的延遲比較高，也就是說 C 是從 1 變成 0

然後，C 的方向跟上面的推論是相反的，因為經過了三個 NOR 閘，所以如果假設每個閘延遲一樣，則情況就會顛倒。


### 補充推論 Dynamic 的 Level 1 閘為 OR 閘

- 1 變成 0
- 也就是 Level 1 的 OR 閘，原本一條路是 1，或兩條路都是 1，變成兩條路都是 0
- 但是要發生 Dynamic，只有**一路恆為 0，並且發生 Static 0 才有可能**
- 假設 A 路恆為 0，B 路從 1 變成 0
- 首先 B 路從 1 變成 0，則輸出則也從 1 變成 0
- 再來 A 發生 Static 0 hazard，使得輸出再從 0 變成 1 再變成 0
- 兩條路都從 1 變成 0 的話並不會有 Dynamic hazard，因為要兩者同時為 0，輸出才會是 0
- 0 變成 1
- 也就是 Level 1 的 OR 閘，原本兩條路都是 0，變成一條路是 1，或兩條路都是 1
- 但是要發生 Dynamic，只有**一路恆為 0，並且發生 Static 0 才有可能**
- 假設 A 路恆為 0，B 路從 0 變成 1
- 首先 A 發生 Static 1 hazard，使得輸出從 0 變成 1 再變成 0
- 然後 B 路從 0 變成 1，則輸出也從 0 變成 1
- 兩條路最終都會從 0 變成 1 的話並不會有 Dynamic hazard，因為誰先變成 1，結果依舊是 1

:::warning
小結論

- Level 1 是 AND 閘
- 要有一個輸入恆為 1，並且該輸入發生 Static 1 hazard 才會有 Dynamic hazard
- Level 1 是 OR 閘
- 要有一個輸入恆為 0，並且該輸入發生 Static 0 hazard 才會有 Dynamic hazard
:::

:::warning
小結論2
其實如果兩個輸入都從 0 變成 1 或都從 1 變成 0，只要有一路會發生 Dynamic hazard，那麼 Level 1 閘的結果依然會有 Dynamic hazard \(汗
:::

---

# 避免 Hazard

一樣就是把會產生 Static hazard 的地方，不要讓那個閘的輸入會有一個 1 一個 0；或者更普遍的說

- 如果是 AND 閘的話，不要讓所有的 Input，同時地從 1 翻轉成 0，和從 0 翻轉成 1
- 方法就是保持某個 Input 恆為 0
- 如果是 OR 閘的話，不要讓所有的 Input，同時地從 1 翻轉成 0，和從 0 翻轉成 1
- 方法就是保持某個 Input 恆為 1

更消極的方法，就是把 K-Map 能夠圈起來的都給他圈起來

# 模擬 Simulation 和 EDA

## 4 logic value

多了兩個新夥伴，Z 和 X

- Z 代表輸入是「斷路」，或者「高電阻」
- 而 Z 的情形其實在真值表上也是以「X 未知」表示
- X 代表「未知」

然後搭配以前的 AND OR 閘，任何人跟 0 做 AND 一定是 0，任何人跟 1 做 OR 一定是 1
可以有下面的真值表

## Simulation 跟 Testing

老師說這兩者的差異，可以用給 TSMC 製作的前後區別

- 給 TSMC 製造前
- 要進行的就是 Simulation，看輸入跟預期的輸出有沒有一樣
- 跑模擬就是每層逐一去看結果，如果改變某個輸入，對某個輸出的影響是怎樣
- 如果不一樣的話有可能是本身的邏輯就是錯的
- 或是跑模擬的時候拉線拉錯了
- 或是輸入給錯了
- 給 TSMC 製造後
- 要進行的就是 Testing
- 在抓的就是 Gate 沒做好
- 或是接線沒接好

## EDA 產業

透過 Simulation 軟體來輔助晶片的設計，會分成幾大項

- Simulation
- 大概是一學期的課
- Testing
- 大概也是一學期的課
- Physical Design
- Logic Synthesis
- Verification
- 藉由布林邏輯的推導，保證結果正確

這些之後都還會再介紹