---
type: slide
---

## 計算機概論Lab-2
### Combinational logic design

<p>https://hackmd.io/@IMOK/Lab2<p>

---

<img src="https://hackmd.io/_uploads/ryUSIqnJT.jpg" width=400 style="border-radius:1000px;"/>

講師: 賴昱有

---

## 作業網站

http://140.121.197.13/tutorial

---

## Introduction
+ <font size=6>轉化logic expression為sum-of-products expression(SOP)</font>
+ <font size=6>使用布林代數(Boolean algebra)及卡諾圖(Karnaugh map)簡化SOP並設計邏輯電路(logic circuit)</font>

---

## Sum-of-products Form
<font size=5>由2個或多個and(以 * 號表示)組合而成的項透過or(以+號表示)連結而成 </font>
<img src="https://hackmd.io/_uploads/SJ-lJ731p.png" width= 300px/>
<img src="https://hackmd.io/_uploads/rJwxJQh1T.png" width= 300px/>
<font size=5>注意! 是不一樣的</font>

----

## Product-of-sums Form
<font size=5>由2個或多個or(以 + 號表示)組合而成的項透過and(以*號表示)連結而成 </font>

<font size=4>※化成標準形式的好處
標準形式布林函數屬於「雙階層執行電路」，即只經過兩層，如此可統一邏輯閘延遲時間。</font>

---

## Simplifying Logic Circuits
<font size=5>許多logic circuit在最初設計的時候過於複雜<br>簡化和最佳化數位邏輯電路<br>可以減少電路的複雜性、降低功耗、提高性能和可靠性(減少耗費的電晶體)。</font>

<font size=5>※使用真值表可以檢驗是否為等效電路</font>

----

<img src= "https://hackmd.io/_uploads/HJoRxS2ya.png" style="float : left ;margin : 100px 0px 0px 100px"/>
<font size=5 float = right>

| A | B | C | F |
| --- | --- | --- | --- |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |

</font>

<img src= "https://hackmd.io/_uploads/SyMcs72Ja.png"/>

----

<img src= "https://hackmd.io/_uploads/B1T88SnJT.png" style="float : left ;margin : 100px 0px 0px 100px"/>

<font size=5 float = right>

| A | B | C | F |
| --- | --- | --- | --- |
| 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 |

</font>
<img src= "https://hackmd.io/_uploads/HyncsXhya.png">

----

### algebraic simplification method

<font size=4>最直接的方式為使用德摩根定律（DeMorgan's Laws）、分配律（Distributive Law）等..進行代數化簡</font>

<font size=4 >※補充:須注意XOR及XNOR的展開比較特別</font>
<font size=5>缺點: 無法輕易判斷是否為最簡表達式</font>

----

## DeMorgan’s law

<font size=4>
第一定律（AND的德摩根定律）：對於任意兩個布林表達式A和B，其AND運算（與運算）的德摩根定律可以表述為：
¬(A ∧ B) = (¬A) ∨ (¬B)

第二定律（OR的德摩根定律）：對於任意兩個布林表達式A和B，其OR運算（或運算）的德摩根定律可以表述為：
¬(A ∨ B) = (¬A) ∧ (¬B)
</font>

---

#### Designing Combinational Logic Circuits
<font size=4>設計組合邏輯電路最簡單的方法是使用真值表。</font>
<font size=4>
+ 程序如下：
1. Set up the truth table.
2. Write the AND term for each case where the output is a 1.
3. Write the sum-of-products expression for the output.
4. Simplify the output expression.
5. Implement the circuit for the final expression.

</font>

----

↓
↓

---

### Karnaugh Map Method(K-Map)

<font size=4>
由貝爾實驗室的工程師 莫里斯．卡諾 發明的。 卡諾圖的圖形化表示方式，可以有效的將原始的布林判斷進行化簡。<br>缺點：當變數增加，其真值表行列數也會依照 2^n 急遽增加，導致圖形更加複雜化
<br>因此當變數大於6個時使用K-map會不易執行會選擇使用Quinn McCluskey
</font>

----

#### 每個格子(cell)內所代表的即為一個minterm

----


----

## Karnaugh Map Rule
<font size=4>1. Groupings can contain only 1s; no 0s.(翻譯:只能圈選minterm為1的cell)</font>
<font size=4>2. Groups can be formed only at right angles; diagonal groups are not allowed.(翻譯:不可以斜的)</font>
<font size=4>3. The number of 1s in a group must be a power of 2-even if it contains a single 1.<br>(翻譯:每個組要圈選到2的x次方個cell)</font>
<font size=4>4. The groups must be made as large as possible.(翻譯:越大越好)</font>
<font size=4>5. Groups can overlap and wrap around the sides of the Karnaugh map.(翻譯:可以跨過邊界)</font>

<font size=5>
※圈選後將各組互補的變數消去留下沒有互補的變數即為所求(化簡後的布林代數式)
</font>

----

↓
↓

----

<img src="https://hackmd.io/_uploads/Hy0zMvhyT.png" style="float:left;"/><img src="https://hackmd.io/_uploads/BJRNzP3k6.png" style="float:left;"/>

<br>
<br>

<img src="https://hackmd.io/_uploads/SyLLMDhkp.png"/>

---

## Lab Questions
<font size=5>For the questions below, please write down the Boolean functions,truth tables,<br> the simplification method and process, and the final circuit using LogicCircuit.
</font>

----

## Question 1
<img src="https://hackmd.io/_uploads/HJKtu80aC.png"/>

## Question 2
<img src="https://hackmd.io/_uploads/HJfhdLA60.png"/>

## Question 3
<img src="https://hackmd.io/_uploads/Skr6O806C.png"/>

----

## Question 4
<font size=5>Design a logic circuit which implements a majority voter.<br> There are 3 people A, B, and C. <br>If 2 out of the three people votes for an yes, i.e., a logic 1, then the output is 1.<br> Otherwise, output 0.</font>

----

## Question 5

<font size=5>Design a logic circuit that is to produce a 1 or HIGH <br>output when the voltage is greater than 6V.<br>(represented by a four-bit binary number ABCD) </font>