---
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

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

## 一些定義

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 最常用的方法
1. 對於每行找到一個Minterm

>也就是 AND 起來

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

### POS/Product-of-Sums 不是很常用

>上面應該是(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往回推或是往前推
很像泡泡浮來浮去
> AND(上) 和 OR(下) 閘

而如果一個NODE出現兩個泡泡就可以消掉
同理 你也可以自己生出兩個泡泡 然後一個拿去改變閘

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

### 畫電路的一些規則 Circuit Schematics Rules
1. 輸入在左邊 或 上面
2. 輸出在右邊 或 下面
3. 整體線路的流動是由左到右
4. 直的電線最好
5. 電線只在 T 路口相接
6. 電線在十字路口相接時要有點
7. 沒有點的十字路口代表電線不相接