# 台科數位邏輯設計筆記
進制轉換:https://www.footmark.info/introduction-to-computer/digital-system-conversion/

diminished radix complement => r-1補數 (進制-1)補數
radix complement　=>　r的補數
1011000(2進制) 1的補數 -> 11111111 - 1011000 = 0100111 全部反相
r的補數 =　r-1補數　＋　１
補數再取一次補數就會回到原本的值
二進制轉２補數=>從右而左遇到第一個1，保留他，後面全部反相
例: 0101100 -> 1010100
------------------------^------第一個1，保留，後面全部反相

1的補數加法如果有進位要加回來，2的補數加法如果有進位直接丟掉即可
不夠減(結果為負數) 做完補數加法後還要再取一次補數，並加上負號
只有2補數沒有正0負0問題，且不用處理進位，2補數負的範圍較大 3bit有號2補數範圍:+7 ~ -8 => +2^n -1 ~ -2^n
BCD的加法是每個digit(4bit)分開做的，如果加完大於10，就要加6 (10的2補數) 修正，進位要丟到下一個digit。

+3碼就是BCD每個digit +3 (0011)
gray碼每2個連續數字間的bit變化都為1，適合用於計數
數位電路最耗電的時候是在狀態轉變時(0變1 1變0)

gray code:

0000 0001 0011 0010 0110 0111 0101 0100 1100 1101 1111 1110 1010 1011 1001 1000

觀察奇數項的下個數變化時，發現無論是第幾個奇數項Gray Code，下個數永遠只改變最右邊的位元。如果是1就改為0，如果是0就改為1。例如第一項0000變為0001，第三項0011變為0010，第五項0110變為 0111，依此類推。

觀察偶數項的下個數變化時，發現所改變的位元，是由右邊算來首個1的左邊位元。例如第二項0001下個數變為0011，第四項0010下個變為 0110，第六項0111變為0101，依此類推。

ascii code 大小寫互換 小寫-32變大寫 大寫+32變小寫，更好的解:將右邊數來第6個bit反相，就可換到另一邊

parity bits，用於檢測資料是否傳輸錯誤，會在最高位元補上1bit，使其成為偶數個1(even parity)或奇數個1(odd parity)
even parity : 補最高位元，補成偶數個1
odd parity : 補最高位元，補成奇數個1

對偶律(duality ) : 等號2邊0變1，1變0，or變and，and變or
https://medium.com/@invtsh/%E6%95%B8%E4%BD%8D%E9%82%8F%E8%BC%AF-%E5%B8%83%E6%9E%97%E4%BB%A3%E6%95%B8%E7%9A%84%E5%B0%8D%E5%81%B6%E5%8E%9F%E7%90%86-3eb92899bcd2
lteral:邏輯閘的輸入，不區分有無not gate
term:多個literal輸入的邏輯閘
越少literal越少term越省錢

canonical forms(another form of truth table representation):每項具有所有literal(不區分有無not gate)

minterm:把所有literal(input with complement(not閘)) and起來，相當於收集結果為1的狀況，適合表達少1較多的狀況，用m表示ex:`m0,m2,m3`，式子用Σ ex:`Σ(0,2,3)`，在卡諾圖裡，相當於是一格
例:`xy,x'y,xy',x'y'`
maxterm:把所有literal(input with complement(not閘)) or起來，相當於收集結果為0的狀況，適合表達少1較少的狀況，用M表示ex:`M0,M2,M3`，式子用π ex:`π(0,2,3)`
例:`x+y,x'+y,x+y',x'+y'`

sum of minterms:there are 2^n minterms and 2^(2^n) combinations of function with n boolean variables

standard forms:每項不再具有所有literal而是可能被化減而消失
sum of products(SOP)又稱(AND-OR) : `F1 = y'+xy+x'yz'`
products of sum(POS)又稱(OR-AND) : `F2 = x(y'+z)(x'+y+z')`


multiple inputs:
multiple nor = a complement of OR gate ，先用許多or擴充input，然後再not反相
multiple nand = a complement of NAND gate ，先用許多nand擴充input，然後再not反相

只用nand實現SOP
推泡泡法(迪摩根)

postive logic:H = 1(高電位),L = 0(低電位)
negtive logic:H = 0(低電位),L = 1(高電位)

postive logic與negtive logic互換:or變and and變or

卡諾圖的00 01 11 10是使用葛雷碼(gray code) =>確保相鄰2格只有1bit不同，才能化簡

implicant = product term = 卡諾圖裡的每個圈，不一定要最簡
prime implicant(PI):卡諾圖可圈到最大包的implicant(最簡)，一個boolean function可能有多個，因為圈法不同，但都是最簡的
essential prime implicant:有包住只被一個圈包住的格子(term)的圈圈，就稱為essential prime implicant，它是必須的，因為沒它，那個格子就沒人可包了

POS卡諾圖:用SOP的方式，但是要圈0(maxterm)，圈完得出結果後整個加not(迪摩根)
dont care:我們不在乎這個狀態是0或1，因此必要時可以調整01得到更佳解，式子用d ex`d(1,3,6)`
例:BCD code的10(1010) ~ 15(1111) ，他們是0是1，並不影響我們要的結果

nand 或 nor 可以組成所有邏輯閘，也可以實作出任何boolean function

wired logic:輸出的2條線接一起，即可形成or或and(根據前面的邏輯閘決定)，但這種電路不適用於CMOS(會燒掉)，除了SOP(AO)、POS(OA)之外的另外2種就是以下的AOI與OAI

AOI:(SOP)' SOP外層包一個not
OAI:(POS)' POS外層包一個not

| SOP | POS | AOI | OAI |
| ----------- | ----------------------------- | ----------- | ----------------------------- |
| 圈1化簡即可 | 圈0化簡後整個用迪摩根反相(complement) | 圈0化簡即可，式子最外層記得加反相(不要用迪摩根)| 圈1化簡後整個用迪摩根反相(complement)，式子最外層記得加反相 |

XOR:奇數個輸入為1，輸出就為1
XNOR:偶數個輸入為1，輸出就為1
用nand實現XOR:
XOR與XNOR的卡諾圖:
用XOR實現偶同位檢查(因為xor奇數為1，奇數+1變偶數)，奇同位用XNOR(因為xnor偶數為1，偶數+1變奇數)
multi-level在電路設計上優於two-level，成本低面積小，但設計multi-level較困難且不直覺

半加器:

全加器:
Binary (Ripple-Carry) Adder:漣波加法器，缺點是要等待前一級進位算完後才能算出這一級進位
Carry Look-ahead Adder:前瞻進位加法器，進位不再是由前一級進位算出，而是用輸入的AB去做xor、and來產生P、G，進而透過強行展開，來直接算出進位。
使用Carry Look-ahead Adder時，因為整個邏輯都被展開了，所以其實不用再實作全加器了，直接用2個xor接到A、B、Ci就可得到sum

減法其實與加法的概念相同，只是在正負號有所變動，因此在電路中做減法時，通常會避免額外再設計出減法器，而是傾向於用現有的加法器來完成減法，這樣的電路就必須使用前面提到的補數概念來完成。
下面的是2的補數加/減法器，M=0時加法，M=1時減法，使用xor來模擬可開啟或關閉的not閘，因為2的補數是1的補數(全部反相的B)+1，所以剛好就直接把M接到C0，就達到+1的效果
要檢測有無overflow的方法就是對最後2個進位去做XOR，若為1則溢位，可以這樣做的原因其實是透過觀察後發現，會溢位的狀況只有正+正與負+負，然後正數溢位導致倒數第二個進位會是1，又因正數的有號數都是0，所以最後一個進位就是0，負+負也是相同概念，反正就有點像巧合的感覺吧?

上面的例子是有號數，如果是無號數，判斷有無溢位的方式就要改變，原本XOR接到的倒數第二進位要改為接到M(加/減開關)。
BCD加法器，如果超過9，就要+6修正，如何判斷大於9，透過觀察發現大於9的數只有以下3種可能
1. carry進位為1
2. 輸出為11××
3. 輸出為1×1×

所以電路就去偵測這3種狀況，然後OR起來，結果送到專門處理+6的adder
乘法可以用and閘來完成，而多bit的乘法就可使用and後的結果去相加來得到結果，類似我們日常使用的直式加法
1bit乘法器:
看起來很複雜的乘法器:
比較器:會有三種情形:
1. \>
2. =
3. <
首先將A、B進行XNOR，可判斷該AB在該bit是否相同，然後也是用類似暴力展開的方法來得出式子

decoder:簡單明瞭，其實就是minterm產生器，這是active high
active low 就是active high再加上一個not閘即可
用decoder再加上OR閘，就可以組成SOP，但這不是一個好方法
enable:類似電路的總開關，運用到controlling value的概念，簡單來說就是有某個值可以使邏輯閘輸出固定，像or、nor就是1，and、nand就是0，xor、xnor則沒有controlling value
disable後，所有輸出狀態都為active的反相(not active)
有了enable後，就可以再擴充更多輸入輸出，例:
還可以再更多，只需在前面加上另一個decoder:

encoder:以下的不是真值表，因為並沒有把所有輸入狀態都考慮進去
有瑕疵的encoder:
這樣的電路僅限於輸入只有一個為1的情形，但只要超過一個為1，輸出就不是我們預期看到的，因此encoder視必做出修正，來使其合理

Priority Encoder:每個輸入都有優先順序，輸出就不會陷入混淆狀態
上圖中，優先權由大而小為:D3 D2 D1 D0，要注意的是輸入的dont care與輸出的dont care是不同的東西
* 輸入的dont care:會展開成所有可能的狀況 ex: x100 -> 0100,1100
* 輸出的dont care:這個狀態下，輸出可以是0或1


Multiplexers:多對1，可視為資料選擇器，輸出是其中一條輸入，透過選擇線來選
Multiplexer的select線接到的其實是一個decoder，所以多工器是由decoder與許多輸出組成的，詳細如下:
2^n-to-1 multiplexer:
* n-to-2n decoder
* Add the 2n input lines to each AND gate
* OR (all AND gates)
* n selection lines
* An enable input (optional)

多工器可以組成n個input的boolean function，只需把輸入接到選擇線即可，而且甚至不需要n to 1也能組成，要注意的是，選擇線放高的位元，不接選擇線的低位元input要透過計算(卡諾圖)，得出每個多工器輸入與input的關係，例:得出每個多工器輸入與z的關係
4-to-1 MUX實現4 input例子:
Three-state (Tri-state) Gates:三態閘，三種狀態:0、1、高阻抗(斷路)，用這種閘可以大幅度減少電晶體使用量，Z為高阻抗
實現多工器:
Demultiplexe:解多工器，其實就是具有enable腳位的decoder，然後把enable當成輸入，decoder的AB當成選擇線，可視為資料分配器
期中考古題:
補充:
卡諾圖化簡線上工具:http://www.32x8.com/index.html