---
# System prepended metadata

title: 第三週
tags: [計概]

---

---
title: 第三週
tags: 計概
---


老師講了Netflix 在傳影片資料時一定會壓縮
且會有buffering避免各種資料的問題
>所以有專門的公司提供Content delivery service

壓縮還有用在機器學習的兩個矩陣相乘
但如果兩個矩陣太大，可以改用逼近的方法
改成以另外兩個矩陣相乘的值去逼近
而這另外的矩陣就是靠壓縮得來的
>可以去查Lower rank

影像壓縮時常用的不是RGB
而是 Y Cb Cr
Y是完整灰階影像 Cb是藍色色度 Cr是紅色色度
阿人對Y比較敏感 其他兩個不敏感 所以就可以對那兩個做壓縮

但是老師居然是快速帶過
以後遇到不會的，老師也很有可能會快速跳過，要準備

# 邏輯門

老師介紹一個判斷式子
```
if 判斷式1
    a = a + 1
else
    a = a + 1
```
這個程式一執行 需要的機器碼都會存在記憶體裡
像是 if else 這些動作都有對應的碼
機器碼也就是組語；由於每個動作跟每個變數其實都是對應到一個位置
例如
```
add a 1
```
是在變數 a 的地方加1
對應到的binary code就是
| 動作的碼 | 變數位置 | 值 |
|-|-|-|
| add | a | 1 |
| 1001     | 0101     | 0001     |

就是因為有對應關係 才因此可以反組譯
然後這三個碼傳給cpu當input
CPU會把線路做切換(準確來說不是切換 有更細的細節)
去做相對應的運算

---

# 電路圖

Input, Output的箭頭有寫數字代表是幾個bit
沒有的話就是一個bit

input, output跟中間產生的輸出輸入
也就是線的部分 都是==Node==
而中間的大方塊 叫做==Element==或==gate==

### Combinational Logic

Output跟上一個值沒有關係
也就是沒有記憶性
:::info
1. 線路不會一個疊在另一個的上面
    不然會不知道怎麼處理
2. **不會有環**
3. 每個Node代表著某個輸入或同時代表某個輸出
:::
### Sequential Logic

Outputs跟上一次的資料有關
也就是有記憶性

>也就是之後講到的flip flop部分

# Boolean equation

就是用邏輯式子表達出真值表的結果

## 一些定義

![](https://drive.google.com/uc?id=1Wwu1I6cq-TSsqalS09Fv6DLAa6cr43ea&export=download)
Literal：Node的值以及其補值(Complement)
>例如 $A$是一個Node，則$A$跟$\bar{A}$都叫做Literal

Implicant：Literal的乘積
>例如 $ABC,\bar{A}B$ 都是Implicant

Minterm：全部Node或其補值的乘積(AND)
>例如 $ABC,\ \bar{A}B\bar{C}$

Maxterm：全部Node或其補值的加總(OR)
>例如 $A+\bar{B}+C,\ \bar{A}+B+\bar{C}$

## 從一個真值表找到Boolean equation
:::info
思緒：
真質表給你輸入AB的值，然後你要想你給的minterm或maxterm在那個值的情況下會輸出甚麼
最後在對回去他應該要有的輸出
:::
### SOP/Sum-of-Products 最常用的方法
![](https://drive.google.com/uc?id=136cLonhtN5cJqznPEKfn-EJq0s95tsHs&export=download)
1. 對於每行找到一個Minterm 

     >也就是 AND 起來

3. 使得該minterm只有該行為`True`其餘為`False`
4. 把輸出為1的行or起來

### POS/Product-of-Sums 不是很常用
![](https://drive.google.com/uc?id=1WfFWDvsDL8mKocEwuYiMvPzMXsQxF7JO&export=download)

>上面應該是(A+B)(~A+B)

1. 對於每行找到一個Maxterm 
2. 使得該Maxterm只有該行為`False`其餘為`True`
    
4. 把輸出為0的行and起來

但是這個不是很直覺

# Boolean Algebra 

簡化boolean equation 的方法

## axiom公理

0跟1的AND和OR操作


|   | 公理 Axiom |  | Dual(?) | 名字    |
| -------- | -------- |--- | -------- | -     |
| A1     | B = 0 if B ≠ 1    | A1'     |B = 1 if B ≠ 0     | Binary Field     |
| A2     | $\bar{0}=1$     |A2'     | $\bar{1}=0$     | Not     |
| A3     | 0﹡0 = 0     | A3'     |1 + 1 = 1     | AND/OR     |
| A4     | 1﹡1 = 1     |A4'     | 0 + 0 = 0     | AND/OR     |
| A5     | 1﹡0 = 0﹡1 = 0     |A5'     | 1 + 0 = 0 + 1 = 1     | AND/OR     |

## Theorem理論
|     | 理論 Theorem                                                                  |      | Dual(?)                                                                       | 名字                |
| --- | ----------------------------------------------------------------------------- | ---- | ----------------------------------------------------------------------------- | ------------------- |
| T1  | B﹡1 = B                                                                      | T1'  | B + 0 = B                                                                     | Identity            |
| T2  | B﹡0 = 0                                                                      | T2'  | B + 1 = 1                                                                     | Null Element        |
| T3  | B﹡B = B                                                                      | T3'  | B + B = B                                                                     | Idempotency         |
| T4  | $\bar{\bar{B}} = B$                                                           |      |                                                                               | Involution          |
| T5  | $\bar{B}$﹡$B$ = 0                                                            | T5'  | $\bar{B}$ + $B$ = 1                                                           | Complements         |
| T6  | B﹡C = C﹡B                                                                   | T6'  | B + C = C + B                                                                 | Commutativity       |
| T7  | (B﹡C)﹡D = B﹡(C﹡D)                                                         | T7'  | (B + C) + D = B + (C + D)                                                     | Associativity       |
| T8  | (B﹡C)+(B﹡D) = B﹡(C + D)                                                    | T8'  | (B+C)﹡(B+D) = B + (C﹡D)                                                     | Distributivity      |
| T9  | B﹡(B+C)=B                                                                    | T9'  | B+(B﹡C)=B                                                                    | Covering            |
| T10 | (B﹡$C$)+(B﹡$\bar{C}$) = B                                                   | T10' | (B+$C$)﹡(B+$\bar{C}$) = B                                                    | Combining           |
| T11 | (B﹡C)+($\bar{B}$﹡D)+(C﹡D)=(B﹡C)+($\bar{B}$﹡D)                            | T11' | (B+C)﹡($\bar{B}$+D)﹡(C+D)=(B+C)﹡($\bar{B}$+D)                              | Consensus           |
| T12 | $\overline{B_0﹡B_1﹡B_2...}=\overline{B_0}+\overline{B_1}+\overline{B_2}...$ | T12' | $\overline{B_0+B_1+B_2...}=\overline{B_0}﹡\overline{B_1}﹡\overline{B_2}...$ | De Morgan's Theorem |

就是邏輯課的那一張大表
但其實可以跟四則運算是一樣的
:::success
一些技巧
1. 可以藉由 AND 1 然後再把 1 以其他邏輯等式替換 例如
    1. Consensus 的證明 - - 搭配 $\bar{B}$ + $B$ = 1
    $xy \vee \bar{x}z \vee yz = xy \vee \bar{x}z \vee ( 1 )yz \\
            = xy \vee \bar{x}z \vee (x \vee \bar{x})yz \\
            =  xy \vee \bar{x}z \vee xyz \vee \bar{x}yz \\
            =  (xy \vee xyz) \vee (\bar{x}z \vee \bar{x}yz) \\
            = xy(1\vee z)\vee\bar{x}z(1\vee y) \\
            =  xy \vee \bar{x}z$ 
    2. 消去用 - - 搭配 ${B}$ + 1 = 1
    $\overline{B} + \overline{A}B = \overline{B} + \overline{A} \\
    \overline{B} + \overline{A}B = 1﹡\overline{B} + \overline{A}B \\
    = (1 + \overline{A})﹡\overline{B} + \overline{A}B \\
    = \overline{B} + \overline{A}﹡\overline{B} + \overline{A}B \\
    = \overline{B} + \overline{A}$
3. 或者在 AND/OR 的時候多補一個自己 因為 A ﹡ A = A / A + A = A
:::

---

老師講了shift比乘法有效率非常多
要注意這種小細節

老師說他們都會去看那個人的github
看他的code 就可以知道他的風格
所以可以去看好的open source 
去學他的風格 寫法

mySQL用了一堆資料結構
可以去看他們的code

老師又提了 IEEE spectrum 雜誌
Signal processing magazine
當然natural跟science也可以

# Bubble pushing
把NOT看成是泡泡
根據==迪摩根定律 DeMorgan’s Theorem==
只要改變閘的類型 就可以把NOT往回推或是往前推
很像泡泡浮來浮去
![](https://drive.google.com/uc?id=1U6xtCYr2eqRLN73FmyUyRnc3LolVcYCb&export=download)
> AND(上) 和 OR(下) 閘


而如果一個NODE出現兩個泡泡就可以消掉
![image alt](https://drive.google.com/uc?id=1cyAcuW1WuY3ABPJ3ntUqnU_qDHG40Nbz&export=download)
同理 你也可以自己生出兩個泡泡 然後一個拿去改變閘

<!-- :::warning
由於 **Bubble Pushing** 是建立於**迪摩根定律**
當結果可以表示成 SOP 或 POS 時
假如結果是 POS，SOP 應該是表示不出來的
因為要把 POS 拆成 SOP 用到的是分配律 不是迪摩根
::: -->

### 畫電路的一些規則 Circuit Schematics Rules
1.  輸入在左邊 或 上面
2.  輸出在右邊 或 下面
3.  整體線路的流動是由左到右
4.  直的電線最好
5.  電線只在 T 路口相接
6.  電線在十字路口相接時要有點
7.  沒有點的十字路口代表電線不相接
![](https://drive.google.com/uc?id=1sPcjK5ZfOOJdGiHLEMl2hchJzx36qMuM&export=download)