Logičke osnove obrade podataka
Kada smo govorili o apstrakcijama u projektovanju kompjutera, videli smo da se na najnižem
hardverskom nivou – nivou eletronike, projektuju moduli poput gejtova i flip-flopova. Za gejtove se kod
nas koriste i nazivi logička kola, logički elementi ili prekidači. Definišemo ih kao fizičke objekte koji
implementiraju neku od funkcija algebarske logike. Povezivanje logičkih elemenata dobijamo
kombinatorne mreže – implementaciju složenih logičkih funkcija. Pomoću kombinatornih mreža mogu se
implementirati samo one funkcije računara koje ne zahtevaju memorisanje podataka ili informacije o
prethodnom stanju. Pri implementaciji funkcija koje zahtevaju osobine memorisanja, koriste se
sekvencijalne mreže. Sekvencijalne mreže predstavljaju skup povezanih logičkih elemenata, čiji izlaz u
sledećem vremenskom trenutku zavisi od tekućeg stanja elemenata mreže, kao i novih vrednosti ulaza. Pri
tome treba imati na umu da je tekuće stanje mreže nastalo kao rezultat logičkih operacija nad vrednostima
ulaza u prethodnom vremenskom trenutku. Dakle, sekvencijalna mreža za razliku od kombinatorne mora
da poseduje i memorijske elemente. Flip-flop je najjednostavniji oblik sekvencijalne mreže. Za flip-flop
koristi se i naziv multivibrator. Svi flip-flop elementi poseduju jednu od sledeće dve osobine:
• To je bistabilni element, koji se može naći u dva stabilna stanja i u slučaju nepostojanja ulaza ostaje u
trenutnom stanju. Zbog ove osobine flip-flop može da se koristi za implementaciju jedne memorijske
ćelije (koja čuva jedan bit).
• Flip-flop ima dva izlaza koji su međusobno komplementarni.
Gejtovi i flip-flopovi prave se od aktivnih komponenti – tranzistora i pasivnih – na primer
otpornika, komdenzatora.
Na sledećem nivou – nivou logike, logički moduli predstavljaju gradivne elemente od kojih se
grade složenije celine. Tako se od gejtova prave razne kombinatorne mreže , na primer dekoderi, a od flipflopova sekvencijalne mreže, na primer brojači i registri.
Mi ćemo se u okviru ovog predmeta baviti višim nivoima apstrakcije, ali da bi se oni bolje
razumeli, predstavićemo vam u najkraćim crtama nivo logike. Na kraju ove lekcije nalaze se pitanja i
zadaci koje ne morate odmah da rešavate, ali koji su korisni dasagledate praktične primene digitalnog
projektovanja.
Digitalna logička kola
C.E. Šanon je 1938. godine otkrio vezi između tablica istinitosti i električnih kola. Na sledećoj slici dato je
prekidačko kolo u kome postoje komponente koje predstavljaju bateriju i sijalicu.
Vrednost 1 dodeljuje se prekidačima p i q kada su zatvoreni (to jest , ukoliko kroz njih protiče struja). U
suprotnom, dodeljuje im se vrednost 0.
Kolu se dodeljuje vrednost 1 kada je sijalica uključena (to jest, ukoliko kroz nju protiče struja). Kada su
prekidači p i q redno vezani što je slučaj u prethodnom kolu, sijalica svetli i kolo ima vrednost 1 samo
ukoliko su oba prekidača p i q zatvorena, to jest oba prekidača p i q imaju vrednost 1. Dakle, ovo kolo
odgovara izrazu p·q, gde · je simbol za logičku operaciju I. Ovo kolo se zato naziva I kolo.
- 203 -
Logičke funkcije koje se realizuju u računaru: I, ILI, NE, NI, NILI i pun sistem funkcija
Procesor radi pomoću reagovanja na ulaz od više 0 i 1 na određene načine i vraćanja izlaza zasnovanog na odluci. Sama odluka se dešava u elektronskim sklopovima koji se zovu logička kola (od kojih
svako zahteva najmanje jedan tranzistor), čiji su ulazi i izlazi različito uređeni pomoću različitih operacija.
Činjenica da današnji procesori sadrže milione tranzistora ukazuje na to koliko je složen takav logički
sistem. Logička kola u procesoru rade zajedno na stvaranju odluka koristeći Bulovu logiku, koja se
zasniva na algebarskom sistemu koji je osnovao George Boole. Glavni Boole-ovi operatori su I, ILI, NE i
NI (ne-I); moguće su i njihove mnogobrojne kombinacije. Izlaz I kola je 1 samo ako su oba njegova ulaza
1. ILI kolo na izlazu daje 1 ako je bar jedan od njegovih ulaza 1. NE kolo ima samo jedan ulaz i daje njegovu suprotnu vrednost na izlazu, odnosno 1 ako je na ulazu bila 0 i obrnuto. NI kola su veoma popularna,
jer koriste samo dva tranzistora umesto tri kao u I kolu, a ipak imaju isto toliko funkcionalnosti. Pored
toga, procesor koristi kola u kombinaciji da bi izvršavao aritmetičke funkcije; on ih takođe koristi da
pobudi smeštanje podataka u memoriji.
Logička kola rade putem hardvera koji se naziva prekidač - posebno digitalni prekidač. U vreme
računara veličine oveće prostorije, to su stvarno bili fizički prekidači, ali danas se više ništa ne kreće
izuzev same struje. Najuobičajeniji tip prekidača u današnjim računarima je tranzistor poznat kao
MOSFET (metal-oksid poluprovodnički tranzistor sa efektom polja). Ova vrsta tranzistora izvodi
jednostavnu, ali suštinski bitnu funkciju: kada mu se dovede napon, on reaguje uključujući ili isključujući
kolo. Većina PC procesora danas radi na 3,3V, ali raniji procesori (do pojave, pa i uključujući neke od
Pentijuma) radili su na 5V. Sa uobičajenim tipom MOSFET tranzistora, ulazni signal na maksimalnoj
vrednosti naponskog opsega, ili blizu nje - uključuje kolo, dok ga pnaj koji je blizu 0 isključuje.
Milioni MOSFET tranzistora rade zajedno, prema instrukcijama programa, da bi upravljali tokom
elektriciteta kroz logička kola i proizveli zahtevani rezultat. Svako logičko kolo sadrži jedan ili više
tranzistora i svaki tranzistor mora da kontroliše struju tako da se kolo uključuje, isključuje ili ostaje u
trenutnom stanju.
I logičko kolo
IlI logičko kolo
Slika 1: Jednostavna logička I i ILI kola
Ako brzo pogledamo na jednostavna I i ILI logička kola na slici 1, videćemo kako ona rade. Svako
od ovih logičkih kola ima dva ulaza koji proizvode jedan izlazni signal.
Logičko I znači da oba ulaza moraju da budu 1 da bi izlaz bio 1 (zapisujemo A·B); logičko ILI znači da
bilo koji ulaz može da bude 1 da bi izlaz bio 1 (zapisujemo A+B); Logičko NE znači da je izlaz uvek
suprotan od ulaza (zapisujemo A );
Tok elektriciteta kroz svako kolo se kontroliše pomoću tranzistora u tom kolu. Međutim, ovi tranzistori nisu pojedinačne i diskretne jedinice. Umesto toga, njihov veliki broj se proizvodi od jednog
komada silicijuma (ili nekog drugog poluprovodničkog materijala) i međusobno povezuje pomoću
- 204 -
metalnih provodnika ili nekog drugog spoljašnjeg materijala. Ovakve jedinice se zovu integrisana kola
(IC) i njihov razvoj je, u osnovi, učinio ostvarivom složenost mikroprocesora. Integracija kola se nije
zaustavila na prvim rezultatima. Baš kao što su prva integrisana kola povezala više tranzistora, tako su se
kasnije povezivala i višestruka integrisana kola, u procesu koji je poznat kao visok stepen integracije
(Large Scale Integration - LSI); na kraju su i ovakvu skupovi integrisanih kola bili povezivani, u procesu
koji se zove veoma visok stepen integracije (Very Large Scale Integration - VLSI).
Savremeni mikroprocesori sadrže na desetine miliona mikroskopski malih tranzistora. Upotrebljeni
u kombinaciji sa otpornicima, kondenzatorima i diodama, oni čine logička kola. Logička kola grade
integrisana kola, a integrisana kola - elektronske sisteme. Prvi slavan rezultat firme Intel bio je integracija
visokog nivoa svih logičkih kola u jedinstven složeni procesorski čip - Intel 4004 - koji se pojavio krajem
1971. godine. To je bio 4-bitni mikroprocesor, namenjen za upotrebu u kalkulatoru. On je obrađivao
podatke od 4 bita, ali su mu instrukcije bile dužine od 8 bita. Memorije za program i podatke bile su
razdvojene. Intel 4004 je imao 46 instrukcija, koristio je svega 2300 tranzistora u 16-pinskom pakovanju
sa dvojnim priključnim sklopom (Dual in Line Package - DIP) i imao je brzinu generatora takta od 740
kHz (osam ciklusa generatora takta po ciklusu centralne procesorske jedinice od 10,8 mikrosekundi).
Logički elementi
Osnovni postulati Bulove algebre, kao i neki osnovni identiteti su dati u sledećoj tablici:
A⋅B=B⋅A
A⋅(B+C)=(A⋅B)+(A⋅C)
1⋅A=A
A+B=B+A
A+(B·C)=(A+B) · (A+C)
0+A=A
A⋅ A = 0
A+ A =1
- 205 -
Zakoni komutacije
Zakoni distributivnosti
Jednakost elemenata
Inverznost elemenata
0·A=0
A·A=A
A·(B·C)=(A·B) ·C
1+A=1
A+A=A
A+(B+C)=(A+B)+C
A⋅ B = A + B
A + B = A⋅ B
Zakon asocijativnosti
DeMorganove teoreme
Fizički modeli logičkih funkcija – logičke mreže
Skup logičkih elemenata međusobno povezanih u cilju realizovanja logičkih funkcija zove se
logička ili kombinatorna mreža. Karakteristika informacija dobijenih pomoću kombinatornih mreža jeste
da rezultat obrade zavisi isključivo od ulaznih veličina i vreme se ne javlja kao nezavisna promenljiva u
rezultatima. Primeri kombinatornih kola su sabirači, multiplekseri, dekoderi.
Osim kombinatornih mreža, u računaru se koriste i sekvencijalne mreže, kod kojih vrednost na izlazu
mreže zavisi kako od trenutnih vrednosti ulaznih promenljivih, tako i od prethodnog stanja u kojima se
kolo nalazilo – rezultati rada kola su zavisni od vremena. Primer sekvencijalnih kola su bistabilni
multivibratori.
Proizvoljna logička mreža L može imati n ulaza i m izlaza. Označimo ulaze redom sa x1, x2, …,
xn, a izlaze sa z1,…,zm.
Rezultat rada logičke mreže se može zapisati u obliku:
Zi=f(x1,x2,…,xn) i=1,…m
Ovakav sistem funkcija zove se sistem sopstvenih funkcija.
Pun sistem funkcija
- 206 -
Analiza i sinteza logičke mreže
Pri izučavanju logičkih mreža javljaju se problem analize i problem sinteze logičke mreže. Problem
analize podrazumeva postupak za određivanje sopstvenih funkcija date logičke mreže.
Problem sinteze je postupak generisanja logičke mreže na osnovu sopstvenih funkcija i rešava se u
tri faze:
1. formiraju se zahtevi koje treba da zadovolji logička mreža
2. formira se sistem sopstvenih funkcija i vrši se minimizacija sistema
3. formira se funkcionalna logička mreža
Bilo koja logička funkcija se može predstaviti tablicom istinitosti ili Bulovim jednačinama. Pri
sintezi logičkih kola najčešće polazimo od tablica istinitosti, iz kojih zatim pokušavamo da odredimo
bulovu jednačinu. Na primer, u sledećoj tabeli data je tablica istinitosti gde su A,B,C ulazne logičke
promenljive, a R očekivani rezultat:
A
0
0
0
0
1
1
1
1
B
0
0
1
1
0
0
1
1
C
0
1
0
1
0
1
0
1
R
0
1
0
0
0
1
0
1
Data tablica istinitosti se može predstaviti ekvivalentnom Bulovom jednačinom koja je
predstavljena kao suma proizvoda. Tako formirana suma proizvoda uključuje sve kombinacije ulaza iz
tablice istinitosti koje daju rezultat 1.
R = A⋅ B ⋅C + A⋅ B ⋅C + A⋅ B ⋅C
Na osnovu izvedene formule se može formirati logička mreža od komponenti I, ILI i NE logičkih
kola, kao na sledećoj slici.
Nakon formiranja logičke mreže, projektant mrežu realizuje uz pomoć potrebnog broja gotovih
čipova koji sadrže željena logička kola. Primer čipa koji se može naći na tržištu za formiranje logičkih
kola dat je na sledećoj slici (čip sa 4 NI kola):
- 207 -
Kako nam je želja da uvek optimizujemo dizajn i upotrebimo što manje čipova, sprovodi se
postupak optimizacije-minimizacije sistema. Primer moguće optimizacije za funkciju R iz gornjeg
primera, kojim ćemo doći do minimalne forme sopstvene funkcije, bi se mogao predstaviti na sledeći
način:
R = A⋅ B ⋅C + A⋅ B ⋅C + A⋅ B ⋅C + A⋅ B ⋅C
R = ( A + A) ⋅ B ⋅ C + A ⋅ C ⋅ ( B + B)
R = B ⋅C + A⋅C
R = ( B + A) ⋅ C
Logička mreža u ovom slučaju ima mnogo jednostavniju strukturu i realizuje se sa mnogo manjim
brojem komponenti:
Drugi standardni vid primene fizičkog dizajna logičkih kola je dizajn uz pomoć Programabilnog
Logičkog Polja (PLA- Programmable Logic Arrays). PLA se sastoji od I, ILI i NE kola složenih u
strukturu programabilne mreže. PLA je izgrađen tako da se jednostavnim pravljenjem kratkih spojeva na
potrebnim mestima formira suma proizvoda koja odgovara logičkoj funkciji. Prikaz PLA čipa sa 12 ulaza
i 6 izlaza dat je na sledećoj slici:
Sinteza logičke mreže sa više izlaza razlikuje se od sinteze logičke mreše sa jednim izlazom, jer
minimalna forma pojedinih sopstvenih funkcija logičke mreže ne obezbeđuje minimalnu formu sistema
sopstvenih funkcija mreže u celini. Pri sintezi logičke mreže sa više izlaza trudimo se da izdvojimo celine
koje su zajedničke za dve ili više sopstvenih funkcija i zatim ovaj deo realizujemo samo jednom.
Za ilustraciju rečenog pokazaćemo kako se formira logička mreža polusabirača i punog sabirača.
- 208 -
Sabirači
Potuni sabirač (full adder) je logička mreža koja sabira dva bita, plus prenosa nastao sabiranjem
bita manje težine. Može se pokazati da se logička mreža sabirača može formirati od dva polusabirača i
jednog ILI kola.
- 209 -
Pitanja i zadaci
1. Definišite pun sabirač preko polusabirača.
2. Po čemu se razlikuju kombinatorne od sekvencijalnih mreža?
3. Navedite primere kombinatornih mreža.
4. Navedite primere sekvencijalnih mreža.
Zadaci i vežbe za Blok
I Analiza
1. Za kombinatorno kola prikazana na slici formiraj tablice istinitistosti izlaza C i P:
b.
a.
2.Za kombinatorno kola prikazana na slici formiraj tablice istinitistosti izlaza P i Q:
a.
b.
- 210 -
II Sinteza
1. Ako vam je na raspolaganju proizvoljan broj kola logičke funkcije NI (Šeferova funkcija), uz pomoć datih
logičkih kola projektujte kombinatornu mrežu koja na izlazu (R) daje logičku funkciju:
a.
b.
c.
d.
2.
Ako vam je na raspolaganju proizvoljan broj kola logičke funkcije NILI (Pirsova funkcija), uz pomoć datih
logičkih kola projektujte kombinatornu mrežu koja na izlazu (R) daje logičku funkciju:
a.
b.
c.
d.
3.
4.
5.
_
A
A*B
A+B
A⊕B
_
A
A*B
A+B
A⊕B
Formirati kombinatornu mrežu koja realizuje funkciju binarnog polusabirača (za binarne ulaze A i B
izračunati rezultat R i prenos C).
Formirati kombinatornu mrežu punog binarnog sabirača, kao sumu proizvoda (koristiti algoritam
uprošćavanja sa Karnoovim mapama).
Uprostiti izraze (pronaći minimalnu logičku implementaciju):
_ _
_
_
a. A*B+B*A+C*D*E+C*D*E+E*C*D=
b.
A*B+A*C+B*A=
c.
(L*M*N)*(A*B)*(C*D*E)*(M*N*L)=
d.
_
_
F*(K+R)+K*F+F*R+F*K+R*F+(R+K)*F=
6.
Rad nekog uređaja kontroliše se sa 4 promenljiva napona. Uređaj ispravno funkcioniše ako su prisutna bar 2
kontrolna napona. Da bi se indicirao pogrešan rad uređaja, treba projektovati logičku mrežu koja će u
slučaju neispravnog rada paliti alarmnu sijalicu. Odrediti logički izraz za funkciju koju ta mreža treba da
realizuje. Projektovati kombinatornu mrežu koja realizuje datu funkciju.
7.
Kartica sa 5 zona (A;B;C;D;E) na kojima mogu da se izbuše otvori za propuštanje svetlosti, može da
posluži kao šifra za otvaranje brave na kasi. Odredi logiku mreže koja će upravljati uređajem za otvaranje
brave tako da se brava otvori na šifru 11001 i da se aktivira alarm pri ubacivanju bilo koje druge kartice.
8.
Projektovati kombinatornu mrežu koja će omogućiti paljenje motora automobila pod sledećim uslovima: da
je ključ za paljenje motora u bravi, da je vozač seo na svoje sedište i da je prikopčao pojas, da je sedište
suvozača prazno ili da suvozač sedi na svom sedištu sa prikopčanim pojasom.
9.
Kombinatorno kolo se koristi za upravljanje sedmosegmentnog displeja decimalnih brojeva (kao na slici).
Kolo ima četiri ulaza, koji obezbeđuju četvorobitni kod koji se koristi u pakovanom predstavljanju
decimalnih brojeva (0000-0, 0001-1, 0010-2, ..., 1000-8, 1001-9).Sedam izlaza definišu koji se segment
uključuje za prikazivanje datog decimalnog broja. (Obratite pažnju da neke kombinacije ulaza i izlaza nisu
potrebne).
a. Razvijte tablicu istinitosti za ovo kolo.
b. Izrazite tu tablicu u obliku sume proizvoda.
c. Napravite uprošćen izraz.
d. Projektujte kombinatornu mrežu za ovaj izraz.
10. Projektujte multiplekser sa 8 ulaza i jednim izlazom.
- 211 -
Download

Припрема и задаци за Блок 1