布林代數
| 布林代數定理 | AND | OR |
| identify law | 1*A=A | 0+A=A |
| null law | 0*A=0 | 1+A=1 |
| idem law | A*A=A | A+A=A |
| inverse law | A*A’=0 | A+A’=1 |
| commutative law | A*B=B*A | A+B=B+A |
| associative law | (A*B)*C=A*(B*C) | (A+B)+C=A+(B+C) |
| distributive law | A+B*C=(A+B)*(A+C) | A*(B+C)=A*B+A*C |
| absorption law | A*(A+B)=A | A+A*B=A |
| demorgan’s law | (A*B)’=A’+B’ | (A+B)’=A’*B’ |
n 個輸入變數,有2^n個不同的輸入變數組合,則:
minterm(最小項),standard product(標準乘積項):將n個輸入變數用and運算結合,若輸入變數的值為0,則變數加上反相符號
maxterm(最大項),standard sum(標準和項):將n個輸入變數用or運算結合,若輸入變數的值為1,則變數加上反相符號
且(minterms)’=maxterms
最小項表示法,也稱SOP(sum-of-minterms,sum-of-products,最小項之和),積之和型式
將所有輸出為1的最小項用 or連接
最大項表示法,也稱POS(product-of-minterms,product-of-sums,最大項之積),和之積型式
將所有輸出為0的最小項用and連接
ex:設f(a,b,c)的minterms,maxterms,假設輸出結果如下
| f(a,b,c) | minterms | maxterms | 假設輸出結果 | (minterms)’=maxterms |
| 0 0 0 | a’*b’*c’ | a+b+c | 0 | (a’*b’*c’)’=a+b+c |
| 0 0 1 | a’*b’*c | a+b+c’ | 0 | (a’*b’*c)’=a+b+c’ |
| 0 1 0 | a’*b*c’ | a+b’+c | 0 | (a’*b*c’)’=a+b’+c |
| 0 1 1 | a’*b*c | a+b’+c’ | 1 | (a’*b*c)’=a+b’+c’ |
| 1 0 0 | a*b’*c’ | a’+b+c | 0 | (a*b’*c’)’=a’+b+c |
| 1 0 1 | a*b’*c | a’+b+c’ | 1 | (a*b’*c)’=a’+b+c’ |
| 1 1 0 | a*b*c’ | a’+b’+c | 1 | (a*b*c’)’=a’+b’+c |
| 1 1 1 | a*b*c | a’+b’+c’ | 1 | (a*b*c)’=a’+b’+c’ |
最小項表示法 f(a,b,c)=m3+m5+m6+m7=a’*b*c+a*b’*c+a*b*c’+a*b*c
最大項表示法 f(a,b,c)=M0*M1*M2*M4=(a+b+c)*(a+b+c’)*(a+b’+c)*(a’+b’+c)
………….
邏輯閘
nor,nand,or,and,not 為基本邏輯閘
nor,nand電路比or,and電路簡單
xor邏輯閘為奇數函數,若2個輸入變數不同則輸出為1
xnor邏輯閘為偶數函數,若2個輸入變數相同則輸出為1
| 輸入 | and | nand | or | nor | xor | xnor |
| 0 0 | 0 | 1 | 0 | 1 | 0 | 1 |
| 0 1 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 0 | 0 | 1 | 1 | 0 | 1 | 0 |
| 1 1 | 1 | 0 | 1 | 0 | 0 | 1 |
complete set of operators(運算子完全集)
可以組合出所有組合電路的一組布林運算子
3個組合的有{and,or,not}
2 個組合的有{and,not},{or,not},{and,xor},{or,xor}
1個組合的有{nand},{nor}, {minority}
nor通用閘可製作以下邏輯閘
not邏輯閘:(a+a)’=a’,需要1個nor通用閘
or邏輯閘:((a+b)’+(a+b)’)’=((a+b)’)’=a+b,需要2個nor通用閘
and 邏輯閘:((a+a)’+(b+b)’)’=(a’+b’)’=a*b,需要3個nor通用閘
適合最大項表示法製作
nand通用閘可製作以下邏輯閘
not邏輯閘:(a*a)’=a’,需要1個nor通用閘
or邏輯閘:((a*a)'(b*b)’)’= (a’*b’)’=a+b,需要3個nor通用閘
and邏輯閘:((a*b)'(a*b)’)’=((a*b)’)’=a*b,需要2個nor通用閘
適合最小項表示法製作
minority通用閘可製作以下邏輯
not邏輯閘:minority(a,a,a)=a’
or 邏輯閘:minority(a,b,1)=a+b
and邏輯閘:minority(a,b,0)=a*b
……………..
布林代數化簡
常見方法有以下：
公式化簡法
使用布林代數定理對布林函數進行化簡
適用布林函數的最小項很少時,且輸入變數多時
卡諾圖化簡法
使用卡諾圖,無固定程序
適用輸入變數小於6
表格化簡法
由卡諾圖化簡化改良而成
適用要化簡多個布林函數,且輸入變數很多時
| 卡諾圖2個變數 b’ba’ a | 卡諾圖3個變數 c’ca’b’ a’b ab ab’ | 卡諾圖4個變數 c’d’c’dcdcd’a’b’ a’b ab ab’ |
………………
組合電路設計程序
1真值表
2標準的最小項之和表示式
3標準的布林函數化簡
4畫出對應的組合電路
常見的組合電路有: 半加器,全加器,n位元加法器,bcd加法器
常見較複雜的組合電路有:decoder,multiplexer,rom,PLA,…等
half ader(半加器)
2個輸入變數:x(被加數),y(加數)
2個輸出變數:carry(進位),sum(和)
真值表如下
| x y | carry | sum |
| 0 0 | 0 | 0 |
| 0 1 | 0 | 1 |
| 1 0 | 0 | 1 |
| 1 1 | 1 | 0 |
carry(x,y)=m3=xy
sum(x,y)=m1+m2=x’y+xy’
full adder(全加器)
3 個輸入變數:x(被加數),y(加數),c(進位)
2個輸出變數:carry(進位),sum(和)
真值表如下
| x y c | carry | sum |
| 0 0 0 | 0 | 0 |
| 0 0 1 | 0 | 1 |
| 0 1 0 | 0 | 1 |
| 0 1 1 | 1 | 0 |
| 1 0 0 | 0 | 1 |
| 1 0 1 | 1 | 0 |
| 1 1 0 | 1 | 0 |
| 1 1 1 | 1 | 1 |
carry(x,y,c)=m3+m5+m6+m7=x’yc+xy’c+xyc’+xyc
sum(x,y,c)=m1+m2+m4+m7=x’y’c+x’yc’+xy’c’+xyc
decoder(解碼器)
將n個輸入線解碼成最多2^n個輸出線,也就是n-to-m decoder
encoder(編碼器)
將2^n個輸入線編碼成n個輸出線
multiplexer(多工器)
也稱為data selector(資料選擇器)
使用少數的輸出線同時傳送多個輸入線的大量資料,利用一組選擇線來選取其中一條輸入線進行傳送
若有2^n條輸入線,則需使用n條選擇線
ps:
使用3個4to1 multiplexer=1個8to1 multiplexer
使用7個2to1 multiplexer=1個8to1 multiplexer
demultiplexer(解多工器)
使用1 個2進位decoder和一條enable輸入線
是由一條線輸入線上收到訊號,再分別傳到2^n個不同輸出線的其中一條,使用n個選擇線做控制
comparator(比較器)
用來比較2個無號整數的大小關係
shifter(移位器)
可將資料往左或是往右移動一個位元
Flip-Flop(正反器)
可以儲存一個位元的電路
是計數器,暫存器,其他時序控制邏輯電路中的一個基本建構方塊