Algebra Boole'a

[ Pobierz całość w formacie PDF ]
AlgebraBoole’ailogikacyfrowa
1Aksjomatycznade
nicjaalgebryBoole’a
Doopisywanieuk“ad
ó
wcyfrowychbƒdziemyu»ywaliformalizmunazywanegoalgebr¡Boole’a.Formalnie
algebraBoole’atostrukturamatematycznaz“o»onazuniwersumBizde
niowanychnanimtrzechdzia“a«:
d
wuargumentowychandior,oznaczanychprzez·i+orazjednoargumentowegonot,oznaczanegoprzez
(poziomakreskanadargumentem).Priorytetoperator
ó
w:not,and,or.Podajemynastƒpuj¡cyzestaw
aksjomat
ó
walgebryBoole’a(spotykanes¡te»innewarianty):
1.“¡czno–¢iprzemienno–¢+i·
2.istniejeelementneutralnydzia“ania+,oznaczanyprzez0,czyli
x+0=xdladowolnegox2B;
3.istniejeelementneutralnydzia“ania·,oznaczanyprzez1,czyli
x·1=xdladowolnegox2B;
4.x+x=1
5.x·x=0
6.prawopodw
ó
jnegozaprzeczenia:x=x
7.rozdzielno–¢·wzglƒdem+,czylix·(y+z)=x·y+x·z
8.rozdzielno–¢+wzglƒdem·,czylix+(y·z)=(x+y)·(x+z)
9.xy=x+y(prawodeMorgana)
10.x+y=x·y(prawodeMorgana)
Zaksjomat
ó
wtychwynikaszeregdodatkowychw“asno–ci,m.in.:
1.0·x=0,1+x=1
2.idempotentno–¢:x+x=x,x·x=x
3.prawoabsorpcji:x(x+y)=x,x+xy=x
KlasycznymodelalgebryBoole’atorodzinapodzbior
ó
wustalonegozbioru,zdzia“aniamiprzekroju,sumy
idope“nieniazbior
ó
w.Model,kt
ó
rynasbƒdzieinteresowa“:Zbi
ó
rB={0,1}zdzia“aniamilogicznejsumy,
iloczynuinegacji.Elementy0,1s¡czasemnazywanefa“szemiprawd¡.Jaksiƒnied“ugoprzekonamywtakim
modelubardzowygodnieopisujesiƒdzia“aniecyfrowychuk“ad
ó
wkomputerowych.Taknaprawdƒnaszmodel
jestizomor
cznyzezbiorempodzbior
ó
wzbioru1-elementowego.
2Wyra»eniaifunkcjeboolowskie
Odterazbƒdziemysiƒporusza¢wnaszymmodeludwuelementowym.U»ywaj¡csymbolidzia“a«,sta“ych
0i1orazzmiennych(zazwyczajx,y,z,...)mo»emybudowa¢wyra»eniaboolowskie.Ka»dewyra»enie
wnaturalnyspos
ó
bde
niujefunkcjƒboolowsk¡.Funkcjƒtak¡mo»emyopisa¢u»ywaj¡ctabeliprawdy.
Przyk“ad:
xyzF=x+yz
000 0
001 1
010 0
011 0
100 1
101 1
110 1
111 1
1
Czasemkonstruuj¡ctablicƒprawdydodajemyjeszczedlawygodykolumnypo–rednie.Wdrug¡stronƒ,ka»da
funkcjaboolowskadasiƒopisa¢zapomoc¡wyra»eniaboolowskiego.Dow
ó
d:konstrukcjawyra»eniawdysjunk-
cyjnejpostacinormalnej(...).Dwawyra»eniaboolowskienazywamyr
ó
wnowa»nymije–liopisywaneprzez
niefunkcjeboolowskies¡identyczne.Oczywi–cieka»dewyra»eniemaniesko«czeniewielewyra»e«r
ó
wnowa»-
nych,ast¡dka»dafunkcjamo»eby¢zapisanananiesko«czeniewielesposob
ó
w.Najlepszes¡reprezentacje
mo»liwienajprostsze(wjakim–sensie).
2.1Upraszczeniewyra»e«boolowskich
U»ywaj¡caksjomat
ó
wiprawalgebryBoole’amo»emypr
ó
bowa¢upraszcza¢wyra»eniaboolows
k
ie(pr
o
c
es
ten
jestodpowie
dn
ikiemupraszcz
en
iaobwod
ó
w
c
yfrowychkomputera).Przyk“ad:F(x,y,z)=xyz+xyz+xz
Upraszamy:xy(z+z)+xz=xy(1)+xz=xy+xz.Trudniejszyprzyk“ad:
F(x,y,
z)
=xy+xz+yz
=xy+
x
z+yz(1)(
el
.neutralny)
=xy+
x
z+yz(x+x)(u
z
upe“nienie)
=xy+
x
z+(yz)x+
(y
z)x(rozdzielno–¢)
=xy+
x
z+x(yz)+x
(
yz)(przemienno–¢)
=xy+xz+(x
y)
z+(
x
z)y(“¡czno–¢)
=xy+(xy)z
+
xz+(xz)y(przemienno–¢)
=xy(1+z
)
+xz(1+y)(rozdzielno–¢)
=xy(1)
+
xz(1)
=xy+xz
Wpodobnyspos
ó
bmo»emydowodzi¢prawalgebryBoole’a(co–bƒdziena¢wiczeniach).
Upraszczaj¡cwyra»enianapodstawieprawalgebryBoole’azdajemysiƒnietylenaalgorytmconaw“asn¡
pomys“owo–¢.Cowiƒcejzauwa»my,»emywzasadzieniewiemycotoznaczynajprostszaposta¢wyra»e-
nia!Zde
nujmyzatempewnestandardowe
proste
postaciewyra»enia.Dowodz¡c,»eka»dafunkcjabo-
olowskamo»eby¢zapisanajakowyra»enieboolowskieu»yli–mywyra»e«boolowskichoszczeg
ó
lnejbudowie:
wdysjunkcyjn
ej
post
ac
inormalnej.Wyra»eniawdysjunkcyjnejpostacinormalnejtosumyiloczyn
ó
w:
F(x,y,z)=xy+xyz+yz.Ka»d¡funkcjƒboolowsk¡mo»nazapisa¢wtejpostaci.Podobniemo»emywprowa-
dzi¢koniunkcyjn¡posta¢normaln¡
posta¢iloczynusum.Iloczynywd.p.n.nazywamymintermami.
Sumywk.p.n.tomakstermy.Zauwa»,»efunkcjawci¡»mo»emie¢wielereprezentacjiwd.p.n.Dlanasnaj-
lepszebƒd¡te,kt
ó
remaj¡najmniejsz¡mo»liw¡liczbƒminterm
ó
w,aw–r
ó
dreprezentacjizjednakow¡liczb¡
minterm
ó
wpreferowa¢bƒdziemyte,kt
ó
remaj¡mniejzmi
enn
ychw
m
inter
ma
ch.Niestetytakieokre–lenie
wci¡»niede
niujejednoznacznejminimalnejpostaci.Np.xy+xy+xz=xy+xy+yz,todwieminimalne
postacitegosamegowyra»enia.
3Bramkilogiczne
Rysunkiwtymrozdzialezosta“ypobranezo
cjalnejstronypodrƒcznikaLindyNulliJuliiLobur.
ó
w,inte-
raktywnediagramy,...).
Bramkilogicznes¡podstawowymielementamizjakichbudujemykomputery.Wzale»no–ciodtypubramka
logicznazbudowanajestzjednego,dw
ó
chlubkilkutranzystor
ó
w.Napocz¡tekwprowadzamybramkiodpo-
wiadaj¡ceoperatoromalgebryBoole’a
bramkiAND,OR,NOT.Opr
ó
czbramekdwuwej–ciowychmo»emy
u»ywa¢ichnaturalnychkilkuwej–ciowychwersji.Czasami,opr
ó
czpodstawowegowyj–ciabramkidorysowujemy
jejdrugiwyj–cie,bƒd¡cenegacj¡pierwszego.Czasem,zamisatrysowa¢bramkƒnegacji,nawej–ciukolejnej
bramkirysujemypustek
ó
“eczko.
U»
ywaj¡cdiagram
ó
wlogicznychmo»emyreprezentowa¢wyra»eniaboolowskie.Przyk“adF(x,y,z)=
x+yz.
Og
ó
lniebramkiodpowiadaj¡dwu-lubkilkuagrumentowymfunkcjomlogicznym.Jestzatem2
4
typ
ó
w
bramekodw
ó
chwej–ciach.Niekt
ó
reznichsapopularniejszeodinnychimaj¡swojew“asnesymboleinazwy.
Czƒstowykorzystywan¡bramk¡jestbramkaXOR(rys.4).Kolejnebramki:NOR(rys.5)iNAND(rys.
6).
M
ó
wimy,»ezbi
ó
rbramek(lubodpowiadaj¡cychimfunkcjilogicznych)jestfunkcjonalniepe“nyje–limo»na
zajegopomoc¡wyrazi¢ka»d¡funkcjƒlogiczn¡.Pokazali–myju»,»ezbi
ó
r{AND,OR,NOT}jestfunkcjonalnie
2
Rysunek1:Symbolepodstawowychbrameklogicznych
Rysunek2:Trzywej–ciowabramkaOR
Rysunek3:Prostydiagramlogiczny
Rysunek4:BramkaXORijejtablicaprawdy
Rysunek5:BramkaNOR:tablicaprawdy,symbol,realizacjazapomoc¡ANDiNOT
Rysunek6:BramkaNAND:tablicaprawdy,symbol,realizacjazapomoc¡ORiNOT
3
pe“ny(konstrukcjawyra»eniawdysjunkcyjnejpostacinormalnej).
Š
atwowyeliminowa¢zniegobramkƒAND
lubOR(u»ywaj¡cprawadeMorganasymulujmemyjedn¡zapomoc¡drugiejinegacji).Okazujesiƒ,»ebramka
NAND(podobniejakiNOR)stanowisamawsobiezbi
ó
rfunkcjonalniepe“ny.Dow
ó
d:realizujemyAND,OR
iNOTprzezNAND(rys.7).Wynikast¡d,»ewpe“nifunkcjonalnykomputermo»nabyzbudowa¢u»ywaj¡c
tylkobramekNAND.Wpraktyceu»ywasiƒbramekr
ó
»negotypu,botopoprostupozwalabudowa¢mniej
skomplikowaneobwody.
Rysunek7:RealizacjaAND,NOTiORprzezNAND
Wiadomo,»ekonstuuj¡cobwodylogicznewartostara¢siƒu»ywa¢jaknajmniejszejliczbybramek.Zwr
ó
¢my
jeszczewtymmiejscuuwagƒnajedn¡rzeczjak¡wartobra¢poduwagƒ.Popatrzmynaprzyk“ad: F=
((ab+c)d)+e=abd+cd+e.Kt
ó
raposta¢jestlepszaidlaczego?R
ó
»nicapoleganaliczbiepoziom
ó
wbramek
(narysujobaobwody).Fizycznarealizacjadrugiejwersjibƒdziewylicza“awarto–¢wyra»enianiecoszybciej
ni»pierwszej.
Poniewa»ka»dewyra»eniemo»nazapisa¢wdysjunkcyjnejpostacinormalnej,wiƒcka»dyobw
ó
dmo»na
zrealizowa¢u»ywaj¡ctylkodw
ó
chpoziom
ó
wbramek.Nieznaczyto,»ezawszejesttopraktyczneipo»¡dane
(podstawowaniedogodno–¢:potrzebujemydotegocelubramekodu»ejliczbiewej–¢,kt
ó
resamewsobiemusz¡
by¢skomplikowane).
4Programowalnetablicelogiczne(PLA)
Dysjunkcyjnaposta¢normalnawyra»e«wykorzystywanajestwpomy–lePLA.Przygotowujemyuk“adzawie-
raj¡cyregularnyuk“adbramekAND,ORiNOTorazwszystkiepotencjalniepotrzebnepo“¡czenia(wpraktyce
u»ywasiƒte»np.bramekNAND).Nastƒpnieuk“adjestprzygotowywanydokonkretnegozastosowaniapoprzez
zlikwidowanie(przepalenie)zbƒdnychpo“¡cze«(walternatywnymrozwi¡zaniuuk“admo»eniemie¢»adnych
po“¡cze«,ajegoprogramowaniepoleganowytworzeniuw“a–ciwych).
Przyk“ad:dwiebramkiOR-ichwyj–cias¡wyj–ciamiuk“adu;6o–miowej–ciowychbramekAND.Cztery
wej–cia;ka»dewej–cieorazjegonegacjajestdoprowadzonedoka»dejbramkiAND;wyj–ciaka»dejbramkiAND
doprowadzones¡doka»dejbramkiOR.Przepalaj¡cniekt
ó
repo“¡czeniamo»emyuzyska¢uk“ad,realizuj¡cy
dwiefunkcje,kt
ó
rewsumiemaj¡maksymalniesze–¢minterm
ó
w.
Typoweuk“adyprodukowanewrzeczywisto–cimaj¡pokilkana–ciewej–¢iwyj–¢.PLAs¡przyk“adem
szerszejklasyuk“ad
ó
wnazywanychprogrammablelogicdevices.
5Uk“addodaj¡cyliczbybinarne
Spr
ó
bujemysiƒterazprzekona¢,»ekomputernaprawdƒdasiƒzbudow¡cu»ywaj¡ctylkoprostychbramek
logicznychjakiewprowadzili–my.Napocz¡tekzbudujemyuk“ad,kt
ó
rydodajedwieliczbybinarne.Uk“ady
takiegotypus¡podstawowymisk“adnikamijednostekarytmetyczno-logicznychprocesor
ó
w.
5.1P
ó
“sumator(ang.half-adder)isumator(ang.adder)
P
ó
“sumatordodajepojedynczebity,zwracate»przeniesienie(ang.carry).Sumatormatrzywej–cia:dwabity
dozsumowaniaipoprzednieprzeniesienie.Pe“nysumatorzbudujemyzdw
ó
chp
ó
“sumator
ó
wibramkiOR.
5.2Sumatorkaskadowy
Budujemysumatorwielobitowyznsumator
ó
w(ewentualnien−1ijednegop
ó
“sumatora).Uwaga:taki
uk“adwrzeczywisto–ciniejestu»ywanywpraktyce.Stosowanes¡ulepszenia,takiejakpodgl¡dprzeniesienia
4
Rysunek8:P
ó
“sumator
Rysunek9:Sumator
(carry-look-ahead),czywyb
ó
rprzeniesienia(carry-select.Poprzez
ur
ó
wnoleglenie
pewnychoperacjiizredu-
kowaniemaksymalnej–cie»kiprzeniesieniapozwalaj¡oneuzyska¢prƒdko–cio40-90procentlepszeni»sumator
kaskadowy.
Rysunek10:16-bitowysumatorkaskadowy
5
[ Pobierz całość w formacie PDF ]