---
title: Multi-Level Gate|第六週
tags: 數位系統與實驗
---

# Level

**從「輸出 Output」到「輸入 Input」，「最多」通過幾個 Gate，並且不算 Inverter (NOT)**

第幾個 Level 是**從輸出往輸入算**，例如 SOP，OR 就是第 1 個 Level，AND 就是第 2 個 Level

## 在意的參數

- Levels
- 就是上面提到的，從輸入到輸出，「最多」經過多少個 Gate
- Gates
- 就是你整張圖總共的 Gate 數目
- Gate Inputs
- 把所有的 Gate，他所擁有的 Input 給他加起來

在描述的時候，就會說第幾個 Level 有幾個 Gate inputs

### 表示方法

雖然 Level 的編號是從 output 往 input 的方向，但是標記各個 Gate 種類時則保持由 input 往 output

像 SOP 從 input 的話是先 AND 再 OR，所以會寫成 AND-OR Gate

### 例子


## Cost 跟 Delay

- 如果 Gate、Input 越多：花的錢(Cost)就越多
- Input 越多就代表拉的線要越長，會讓面積變大，造成很多影響
- 像是時間方面的
- 如果 Level、Input 越多：延遲(Delay)就越高
- Level 自然就不用講，而 Input 的話是在物理上，越多 Input 的反應會比較慢

### 通常

通常 Level 變高，可能可以降低 Cost，但會使 Delay 上升

但這只是個大概的趨勢，沒有真正的公式可以計算他們的關係

---

# 畫出多種 Level

不外乎就是先前學的 POS 跟 SOP，然後再用「Factoring」，把相同的部分用分配律弄起來

## 比較

比較常會去比較相同 Level 的電路，然後通常，是通常， Gates 和 Gate Input 比較少的會是比較好的

但是實際上到底好不好是交由系統設計師 System Designer 去決定的

---

# NAND 跟 NOR

雖然這兩個 Gate 都可以用 NOT AND OR 以等價的方式組合，也就是說他們在我們的式子中都是等價的

但是在實際上的物理意義中，NAND 跟 NOR 這兩種 Gate 的實現方式，比起 AND 跟 OR 用了更少的 switches

也因此「延遲較小」以及「花費較低」，所以在數位設計上，其實是比較喜歡 NAND 跟 NOR 的

# Functionally Complete Set

:::info
任何的/任意的 Boolean Function ，都可以用「這組 Set」來表示
:::

之提到的，對於 n 個變數的 Boolean Function，總共有 $2^{2^{n}}$ 種可能

而 Functionally Complete Set 就是可以表示出那些全部組合的 Set

## {AND OR NOT} Set 是 FCS

你只要把所有的可能都用 minterm expansion 都列出來，就會形成一個 SOP

那麼很明顯的就可以用上面的三種 Gate 實現

## {AND NOT} Set 是 FCS

是的，因為你其實可以根據迪摩根定律，只用 AND NOT 表示出 OR

也就是說

$$
(A+B)'' = (A'B')'
$$

## {OR NOT} Set 是 FCS

是的，因為你其實也一樣可以根據迪摩根定律，只用 OR NOT 表示出 AND

也就是說

$$
(AB)'' = (A'+B')'
$$

## 只有 AND 或 只有 OR 不是 FCS

畢竟你少了 NOT 就不能做那些反過來的操作

## NAND 是 FCS

由於你可以用 NAND 弄出 NOT AND 跟 OR，所以 NAND 這個單獨一個 Gate 是 FCS


## NOR 是 FCS

同理，你也可以用 NOR 弄出 NOT AND 跟 OR，所以，NOR 這個單獨一個 Gate 也是 FCS

## AND 跟 NOT 不是 FCS

跟上面很像，你少了 NOT 就不能做那些反過來的操作

---

# NAND 跟 NOR 的 Two-Level Circuits

就是將 SOP 或 POS 結果在兩個 Gate 中間補上兩次 NOT，然後往各自方向推泡泡，也因此有了所謂的 8 Basic Forms

因為泡泡可以選擇四種位置，加上又有 SOP 跟 POS 兩種前後位置，所以才有八種

- 只往右邊推
- SOP 的右邊的 OR 變為 NAND
- POS 的右邊的 AND 變為 NOR
- 只往左邊推
- POS 的左邊的 OR 變為 NAND
- 但是會因為有個卡在中間的 NOT
- 所以會是 AND
- SOP 的左邊的 AND 變為 NOR
- 但是會因為有個卡在中間的 NOT
- 所以會是 OR
- 往左右邊推
- 同上
- 保持原位
- 就是原本的形式

所以你會發現， 第 1 Level 的 OR 跟 NAND 是綁在一起的， AND 跟 NOR 是綁在一起的
所以如果題目要求哪個 Level 要甚麼 Gate，可以先想想要從 SOP 還是 POS 下手

>舉例來說，如果要 NOR-NOR 的 Circuit
>你會發現，NOR 跟 AND 是一夥的，所以這個就要用 SOP 來做

## Degenerated Forms

既然我有 AND NAND OR NOR，四種 Gate，也就是說每個 Level 有四種選擇，兩個 Level 就有 16 種選擇

那剩下的 8 種去哪了？答案是他們並不能用來表示原先的式子，所以才沒有出現在上面

- AND-AND,AND-NAND
- OR-OR,OR-NOR
- NAND-OR,NAND-NOR
- NOR-AND,NOR-NAND

## 一些特性

- Gate 的數量 $\le$ terms 的數量 +1
- 因為一個 terms 有可能就是一個 AND；如果有兩個 terms 中間一定會有一個 OR
- Gate input 的數量 $\le$ literals + terms 的數量
- terms 的數量反映了 gate 數量，而 gate 數量則會影響各 level gate 的 input 數量
- < 發生在，當有個 terms 是單一個變數的時候

用 SOP 的觀點去想會比較好

---

# NAND 跟 NOR 的 Multi-Level Circuits

沒有比較有系統性的做法

## Multi-Level NAND-Gate Circuits

就是每個 Gate 都是 NAND

:::warning
但是允許 NOT 的存在，因為可以用 NAND 表達出 NOT
:::

---

# Two-Level, Multiple-Output Circuits

如果同時有多個 Boolean Function 要拉成一個...電路組合，那其實他們之間是可以有共用的 Input 和 Gate

## 方法一

就是直接土法煉鋼， K-Map 化簡完後，看看那些可以拆出來給其他人用，或是多補一些東西等等


## 方法二

在 K-Map 上看出一點端睨



也就是從 K-Map 中找到可以共用的部分 / Common Case

## EPI 需要重新定義

因為你可以獲得 Input 的來源變多了，所以在單個 Equation 是 EPI 的情況，到了多個 Equation 就可能不是 EPI

反之，有些 PI 會變成 EPI


## 有些時候，不要有 Common Case 比較好


:::success
所以最好的方法可以去畫 K-map，然後從圖上看可以共用的有哪些
:::

---

# Multiple-Output NAND and NOR Circuit

假如一個電路全都是 OR 跟 AND

那麼有機會可以直接轉換成 NAND-gate circuit 或 NOR-gate circuit