|
1. Resavanje problema uz pomoc racunara – racunari su odavno postali nezamenljivi kod resavanje slozenih problema. Jedno od osnovnih pitanja, pri tome, jeste kako covek svoje probleme prezentira racunaru na resavanje. Pod problemom podraz. bilo kakav zahtev za obradu pod. koji dovodi do informacije koja je od znacaja za donosenje nekih odluka ili za preduzimanje nekih akcija. Nezaobilazni koraci kod resavanje problema su: analiza problema, razvoj algoritma za resavanje problema i transformacija algoritma u racunarski program. Cilj analize je da se dodje do precizne definicije i opisa problema, da se specificiraju ulazni podaci, odnosno ocekivani rezultati, kao i postupak dolazenja do tih rezultata. Za izvesne probleme ovaj korak moze biti jednostavan, dok se za neke druge on znatno komplikuje. Problemi koji se mogu opisati matematickim jezikom se mogu i precizno definisati i opisati onako kako to odgovara racunaru, dok to nije tacno za klasu nematematickih problema. Ne postoji standardan i formalizovan postupak koji bi bio pogodan za analizu bilo koje vrste problema. Preporucuje se tzv. sistem-analiza problema, odnosno sistemski pristup koji obuhvata uocavanje problema, formulisanje ciljeva resavanja, definisanje sistema, analizu, projektovanje novog sistema. Pod algoritmom podrazumevamo niz instrukcija koje tacno odredjuju redosled operacija koje ce dovesti do resenja za ma koji problem datog tipa. Sledece karakteristike su bitne za algoritme: * broj operacija koje se moraju izvrsiti za resenje konkretnog problema nije poznat unapred * ono sto je odredjeno algoritmom je deterministicki proces koji se moze ponavljati bilo kad i od strane bilo koga. * instrukcije koje cine algoritam se mogu izvrsiti na odgovarajucem skupu podataka i u svakom slucaju dovode do korektnog rezultata. * algoritem se mora okoncati posle konacnog broja koraka (konacnost). * svaki korak kod algoritma mora boto precizno definisan, operacije koje treba izvesti moraju biti rigorozno specificirane i bez bilo kakvih dvosmislenosti (definisanost). Iz tog razloga se za definisanje algoritma najcesce koriste jezici sa preciznom semantikom, kao npr. matematicki jezik ili programski jezici u kojima svaki stav (naredba) ima tacno definisano znacenje. * za izvodjenje proizvoljnog algoritma moze biti potrebno vise, ali isto tako ni jedan, ulazni podatak, kao pocetna vrednost (ulaz). * algoritam poseduje jednu ili vise izlaznih velicina. * algoritmi moraju biti efikasni, potrebno je da se maksimalno skrati vreme njihovog izvrsavanja, da su sto jednostavniji. Algoritam se formalno definise kao cetvorka (Q,U,I,F) gde je Q skup koji sadrzi kao podskupove U i I, a F je funkcija ciji je domen, kao i antidomen, skup Q. Pri tome vazi da je F(q)=q za svako q iz skupa I. Sa Q je oznaceno stanje racunara, sa U ulaz, sa I izlaz, a sa F zakon racunanja. Svaki X iz U definise racunski niz X0, X1, X2... na sledeci nacin: X0=X Xk+1 = F(Xk) za k>0. Za racunski niz se kaze da se zavrsava u k-tom koraku ako je k najmanji ceo broj za koji je Xk u I. Neki racunski nizovi se nikada ne zavrsavaju (to je slucaj racunske metode). Algoritmi za resavanje problema spadaju u klasu numerickih algoritama, za razliku od tzv. analitickih algoritama, koji dovode do analitickih resenja problema. Za predstavljanje algoritama koriste se sledece tehnike: prirodni jezici, metajezici, programski jezici, i blok-dijagrami algoritama. Algoritmi se klasifikuju u sledece osnovne alg. strukture: * linijska struktura (postoji samo jedna grana izvrsavanja algoritma, svaki korak se izvrsava samo jednom). * struktura sa grananjem (kada se u alg. pojavljuje korak odlucivanja, tj. aritmetickog ili logickog testa). * petlja ili ciklicna alg. struktura (visestruko izvrsavanje jednog ili vise koraka). * struktura sa podalgoritmima (koristi se kod slozenijih problema). 2. Brojni sistemi – ako imamo N (N je prirodan broj) kao osnovu nekog brojnog sistema, onda algebarsku vrednost ma kog konacnog realnog broja u tom sistemu zapisujemo u obliku: (X)N = Xn Xn-1 ... X0 X-1 ... X-m gde su Xi cifre tog brojnog sistema, n-broj cifara u celobrojnom delu, a m-broj cifara u razlomljenom delu. Svaki prirodan broj veci od 1 moze biti baza brojnog sistema. Za racunarsku tehniku su, pored dekadnog (osnova 10), od posebnog interesa binarni (osnova 2), oktalni (osnova 8), i heksadecimalni (osnova 16) sistemi brojeva. Broj X se moze zapisati u obliku: (X)N =X-mN-m + X –m+1N –m+1 + ... + X0N0 + X1N1 + X2N2 + XnNn gde su Xi, iÎ[-m,n] cifre tog broja u datom sistemu, tj. XiÎ{0,1,2,...,N-1}. Pri projektovanju racunara prvi korak je da se odabere pogodni brojni sistem za predstavljanje brojeva, vodeci racuna o ekonomicnosti tehnicke realizacije brojnog sistema, i o izvrsavanju aritmetickih operacija. I pored toga sto je covek navikao na dekadni sistem, skoro svi racunari interno koriste binarni brojni sistem. Uzimajuci u obzir pouzdaniji nacin realizovanja binarnih elemenata, kao i pouzdanost operacija u ovom sistemu, izabrana je osnova 2, a za reprezentaciju simbola u racunaru odabrano je binarno kodiranje. 3. Predstavljanje negativnih brojeva u racunaru – negativni brojevi se u racunaru mogu predstaviti ili preko znaka i aps. vrednosti, ili u obliku komplemenata. U svakodnevnoj upotrebi, broj bez znaka pretvaramo u broj sa znakom dopisujuci ispred broja znak “+” ili “-“. U racunaru je uobicajena konvencija da se “+” kodira u 0, a ”-“ u najvecu cifru brojevnog sistema (najcesce 1, jer se radi sa binarno zapisanim brojevima). Isto tako postoje i dva zapisa za 0, tj. +0 je 00, -0 je 99 (ako se radi o dekadnom sistemu brojeva). Ovakvo predstavljanje brojeva u racunaru zahteva posebno tretiranje znaka, a posebno tretiranja velicine brojeva. Njegov nedostatak je sto se onda znatno komplikuje izvrsavanje nekih aritmetickih operacija. Kod notacije tzv. nepotpunog komplementa broja pozitivni brojevi se zapisuju isto kao u notaciji znaka i aps. vrednosti, dok se negativni brojevi zapisuju tako sto se kodira njihova aps. vrednost, a zatim se svaka cifra dopuni do najvece cifre brojevnog sistema. Ovaj proces komplementiranja je najjednostavniji kod binarnog sistema: svaka jedinica se zameni nulom, a svaka nula jedinicom. Kod notacije potpunog kompl. broja pozitivni brojevi se zapisuju isto kao i u notaciji nepotpunog komplementa, dok se negativni brojevi prvo zapisu kao u notaciji nepotpunog komplementa, pa se onda mestu sa najmanjom tezinom doda 1. 4. Predstavljanje brojeva u racunaru – za zapis realnih brojeva se u racunaru koriste dve notacije: pokretni i nepokretni zarez. Kod nepokretnog zareza se definise koliko mesta u registru zauzima ceo, a koliko razlomljeni deo broja. Na primer, u registru oblika - - - . - - broj 321.66 se moze dobro zapisati, ali zato brojevi 2435.32 i 0.001 ne mogu. Kaze se da se kod broja 2435.32 radi o prekoracenju (overflow), dok se kod broja 0.001 radi o potkoracenju (underflow). Zarez se obicno fiksira ispred najznacajnijeg mesta, ili posle najmanje znacajnog mesta. U prvom slucaju se mogu predstavljeti brojevi koji su po modulu manji od 1, dok se u drugom slucaju predstavljaju samo celobrojni brojevi. Nepokretni zarez se retko koristi, jer prilikom izvodjenja aritmetickih operacija treba obezbediti da svi medjurezultati i rezultati budu u intervalu N-m <= |X| <= Nn+1 – N-m. Svi brojevi manji od N-m beleze se kao masinska 0, dok se svi brojevi veci od Nn+1 – N-m tretiraju kao prekoracenje. U pokretnom zarezu se brojevi predstavljaju u obliku X=XMNS gde je XM – mantisa, N-osnova brojnog sistema, S-eksponent (stepen). Mantisa i eksponent su oznaceni brojevi, i mogu biti predstavljeni u brojnom sistemu sa osnovom koja je razlicita od N. Podesavanjem N i S ovakav format dopusta prekrivanje znatno veceg opsega brojeva nego u slucaju nepokretnog zareza. Potrebno je da mantisa bude normalizovana, tj. da je N-1 <= |XM| <=1, znaci da je manja od 1 i da se iza tacke prvo javlja broj koji je razlicit od 0. Npr. 0.11 je normalizovana, 0.011 nije normalizovana mantisa. Primer: u registru od 32 bita kod koga je (standardno) 6 bita ostavljeno za predstavljanje eksponenta, dok je 24 bita predvidjeno za predstavljanje mantise, podatak se predstavlja putem reci a0 b0 b1 b2 ...b6 a1 a2 ...a24 gde je pozicija a0 predvidjena za postavljanje znaka mantise, a b0 za postavljanje znaka eksponenta. 5. Kodiranje numerickih informacija – pri pretvaranju realnih brojeva u binarni oblik nekad nije moguce do kraja izvrsiti prevodjenje razlomljenog dela broja (zbog konacnog broja mesta u registru), sto ima uticaja na tacnost dobijenih rezultata. Zbog toga je neophodno naci pogodnije resenje. Ako kod broja zapisanog u sistemu sa osnovom N (X)N= a-m a-m+1 ... a0 . a1 a2 ... an svako ai iÎ{-m, -m+1, ..., 0, 1, 2, ..., n} shvatimo kao jednu informaciju (sto je moguce jer se radi o pozicionim brojnim sistemima), onda im se moze pridruziti po jedna rec iz binarne azbuke. Za racunare je bitno da ovako dobijeni kod je ravnomeran, sto znaci da minimalna duzina reci m koja to obezbedjuje za brojeve iz sistema sa osnovom N ispunjava uslov 2m >= N, tj. m>=log 2 N. Posto je broj slova u reci ceo broj, sledi da, npr. brojevi iz oktalnog sistema treba da budu kodirani binarnim recima duzine 3 bita, a kako je 23=8, ovakav kod je potpun. Za kodiranje decimalnih brojeva potrebne su binarne reci duzine 4, ali posto je 24=16>10, ovaj kod je nepotpun. Za cifre heksadecimalnog sistema je kod sa recima duzine 4 potpun. Postoje dve grupe kodova za kodiranje decimalnih broeva. To su kodovi sa tezinom i kodovi bez tezine. Kod kodova sa tezinom se svakom od 4 bita X1, X2, X3, X4 pridruzuju decimalne vrednosti m1, m2, m3, m4 koje se zovu tezine. Tako kodiran decimalni broj ima vrednost d=m1x1+m2x2+m3x3+m4x4 . Najpoznatiji medju 80 kodova sa tezinom je NBCD kod ili BCD 8-4-2-1 kod (prirodni binarno-decimalni kod – naturaly binary coded decimal). Od kodova bez tezine najrasprostranjeniji je XS-3 kod. Pri izbori koda postuju se sledeci kriterijumi: - tezina izvodjenja racunskih operacija - ekonomicnost smestanja informacija - ekonomicnost logickih elektronskih kola koja podrzavaju dati binarno kodirani dec. broj - mogucnost otkrivanja i korekcije gresaka - jednostavnost koriscenja koda u celini 6. Kodiranje alfanumerickih operacija – Savremeni racunari obradjuju ne samo numericke, vec i alfabetske informacije, jednom recju alfanumericke podatke. Pod pojmom alfanumericki podaci podrazumevaju se i znaci koji sluze za uredjenje teksta (znaci interpunkcije i drugi specijalni simboli). Alfanumericke znake cine: 1. Numericki simboli: 0,1,2,...,9 2. Slovni simboli: A,a,B,b,C,c... 3. Znaci interpunkcikje: .,!.:,”,... 4. Specijalni simboli: -,+,*,$,... Sveukupnost svih znakova koje koristi dati racunar cini njegov alfabet. Danas se sve vise koristi predstavljanje simbola u racunaru preko binarnih reci od 8 bita. Tako kodirani simbol se cesto naziva i bajt. Ovakav sistem kodiranja koristi EBCDIC KOD (Extended Binary Coded Decimal Interchange Code) koji je standardizovala kompanija IBM, kao i ASCII KOD (American Standard Code for Information Interchange) usvojen i od strane Medjunarodne organizacije za standardizaciju (ISO-648). Alfanumericke informacije se u racunaru obicno predstavljaju recima promenljive duzine, okupirajuci tako potreban broj bajtova. Npr. kod racunara IBM serije 360 alfanumericka rec moze imati duzinu d od 1 do 256 bajtova. Proizilazi, dakle, sledeca organizacija alfanumerickih informacija |bajt|bajt|...|bajt|bajt| dok je simbol organizovan kao | zona | broj | 0 3 4 7 Cetiri prva (zonska) bita kod numerickih podataka ne igraju nikakvu ulogu. Zbog toga se obicno pre neke aritmeticke operacije ova 4 bita eliminisu i 2 binarno kodirana decimalna broja se smestaju u 1 bajt. Za tu potrebu u repertoaru instrukcija racunara postoji odgovarajuca instrukcija koja vrsi pakovanje BCD brojeva. U pakovanom obliku organizacija bajta je sledeca: | broj | broj | 0 3 4 7 U nepakovanom obliku predstavljanje brojeva sa znakom ima oblik: |zona|broj|zona|broj|...|znak|broj|. U pakovanom obliku: |broj|broj|broj|...|broj|znak|.
7. Racunske operacije u NBCD kodu – NBCD je nepotpun kod jer koristi samo 10 od ukupno 16 reci duzine 4 bita i treba naci nacin da se prevazidje ovih 6 simbola koji se u kodu ne koriste. Poznato je da se ne postavljaju problemi kod sabiranja brojeva ciji zbir ne prelazi 9. Lako se uveravamo da je to isto i ako sabiramo takve brojeve predstavljene u NBCD kodu: dekadno NBCD dekadno NBCD 2 0010 3 0011 4 0100 5 0101 ___________________ ___________________ 6 0110 8 1000 610=0110 NBCD 810=1000 NBCD Kada je zbir dekadnih brojeva veci od 9 nastaju problemi jer se dobijaju rezultati koji se u NBCD kodu ne koriste, npr. dekadno NBCD 8 1000 2 0010 ___________________ 10 1010 > rezultat koji je dobijen po pravilima sabiranja binarnih brojeva u kodu NBCD nema znacenja. Posto se NBCD kodu broju 10 pridruzuje 00010000, to je dobijeni rezultat sabiranja svakako netacan. Iz posmatranja kodne zamene za 10, i ekvivalenta broja 10 u binarnom brojnom sistemu (1010) moze se zakljuciti da se ova dva oblika razlikuju za 6 (u sistemu 10), tj. za onoliko koliko NBCD kod ne koristi reci (od mogucih 16) za predstavljanje dekadnih brojeva, buduci da je 00010000-1010=0110. Ako se na rezultat dobijen po pravilima sabiranja binarnih brojeva, u slucaju da je zbir veci od 9 (1001)2 , dobijenom NBCD broju doda broj 6 (0110)2 dobija se pravilan rezultat. dekadno NBCD 8 1000 +2 0010 ___________________ 10 1010 6 0110 ___________________ 00010000 8. Kodiranje operacija – instrukcije – proces obrade podataka u racunaru sastoji se od tacno definisanih operacija koje racunar mora da izvrsi. U memoriji racunara se nalaze podaci (koji se nekada zovu i operandi) koji se obradjuju, kao i programi koji upravljaju obradom podataka. Programe cine nizovi masinskih reci, instrukcija, pomocu kojih se definise proces obradde podataka. Svaka instrukcija, u osnovi sadrzi 4 adrese, tj. ima format: kod op. – adresa operanda – adresa operanda – adresa rez. – adresa sledece ins. Kod operacije je numericki kod, obicno od 4 do 6 bitova, koji inicira koje ce se operacije (+,-,*...) vrsiti nad operandima cije su adrese u memoriji navedene u naredna 2 polja. Potom sledi adresa memorijske jedinice gde ce se smestiti rezultat, kao i adr. memorijske lokacije na kojoj se nalazi sledeca instrukcija. Razliciti racunari poseduju razlicite skupove instrukcija (repertoar instrukcija), kao i razlicite sisteme kodiranja tih ins. Kod savremenih rac. se broj ins. krece izmedju 100 i 200. Osnovni problem kod 4-adresnih instrukcija je veliki prostor potreban da se smeste 4 adrese. Pozeljno je da instrukcija bude takve duzine da se moze zahvatiti u toku jednog obracanja memoriji, tj. da se moze citati odjednom. Troadresna instrukcija ima oblik: kod operacije – adr. operanda – adr. operanda – adr. rez. ili ins. Znacenje: izvrsiti operaciju ciji je kod smesten u prvom polju nad operandima cije su adrese u drugom i trecem polju, i rezultat smestiti u mem. lokaciju cija je adr. u 4. polju. Dvoadresna instrukcija ima oblik: kod operacije - adr.operanda – adr. operanda ili ins. Znacenje: izvrsiti operaciju nad operandima cije su adrese date u 2 adresna polja, rez. smestiti na mesto 2. operanda, i preci na izvrsavanje sledece instrukcije iz normalnog redosleda instrukcija. Medjutim, ovo je nepogodno ukoliko su oba operanda potrebna i za neke kasnije operacije. Iz tog razloga se kod racunara koji rade sa ovakvim ins. uvodi standardni registar u aritmeticku jedinicu, koji se zove akumulator, i u koga se smestaju podaci posle obavljenih operacija. Postoje i jednoadresne ins. kod kojih se adresa drugog operanda podrazumeva, i ciji je format: kod op. – adresa operanda ili ins. Znacenje: izvrsiti operaciju nad 1. operandom cija je adresa smestena u adresnom poju instrukcije i drugim operandom koji je smesten u akumulatoru, i reziltat u akumulator, a onda nastavi izvrsavanje normalnog redosleda instrukcija. Postoje i bezadresne instrukcije koje sadrze samo kod operacije, dok se potrebne adrese podrazumevaju. Proces odredjivanja fizicke (efektivne) adrese u memoriji racumara zove se modifikacija (izracunavanje) adrese. U procesu modifikacije se dobijaju efektivne adrese (EFA). 9. ASCII kod – znaci ASCII koda se mogu svrstati u 3 grupe: slovni i brojni znaci, specijalni znaci, i upravljacki znaci. Upravljacke znake cine sledece podgrupe: * znaci za upravljanje prenosom podataka – koji su namenjeni upravljanju prenosom podataka komunikacionim kanalima: ACK (acknowledge – ispravan prijem poruke) NAK (negative acknowledge – neispravan prijem poruke) SOH (start of heading – pocetak zaglavlja) STX (start of text – pocetak teksta) EOT (end of transmission – kraj prenosa) ETB (end of transmission block – kraj bloka) ENQ (enquiry – upit) – obavezni prvi znak za upit udaljenoj radnoj stanici na mrezi za prenos podataka DLE (data link escape – sledi niz sa posebnim znacenjem) SYN (synchronous idle – sinhronizacija) (predajne i prijemne radne stanice) * znaci za odvajanje podataka – koriste se da se izvrsi logicko razdvajanje podataka. Kada se ovi znaci upotrebe u hijerarhijskom kontekstu, imaju utvrdjeno znacenje. U ostalim slucajevima tacno znacenje utvrdjuje se zavisno od nacina primene. US (una separator – odvajanje polja) RS (record separator – odvajanje zapisa) GS (group separator- odvajanje blokova) FS (file separator – odvajanje datoteka) * znaci za specifikaciju formata – namenjeni za upravljanje izlaznim formatima na uredjajima za stampanje i video ekranima: BS (backspace) HT (horizontal tab) LF (line feed – nova linija) VT (vertical tabulation) FF (form feed – uvlacenje formulara) CR (carrage return – povratak glave za pisanje za pocetak reda) * znaci za upravljanje uredjajima (prikljucenim u lokalu na racunarski sistem – npr. kao periferijske jedinice) DC1 (device control 1 - upravljanje uredjajem 1) DC2 (device control 2 – prevodjenje iz standardnog u nestandardni nacin rada) DC3 (iskljucenje ili zaustavljanje rada uredjaja) DC4 (iskljucenje, zaustavljanje, ili prekid rada uredjaja) * ostali upravljacki znaci: NUL (null – prazan znak) BEL (bell – akusticni alarm) SO (shift out – pisanje malih slova) SI (shift in – pisanje velikih slova) CAN (cancel) EM (end of medium) SUB (substitute – zameniti) ESC (escape – promena) 10. Klasifikacija elemenata racunara – racunari se sastoje iz velikog broja elektronskih kola koja obradjuju elektronske signale, ili cuvaju neke brojne ili logicke podatke. Jednostavna klasifikacija delova racunara prema funkcijama koje vrse ima oblik: Osnovnu obradu signala koja rezultira nekim racunskim rezultatima vrse logicki elementi. Log. elementi bez memorije (kombinacione grupe ili primitivni automati) – izlazni signal Y, Y=f(X), signal postoji na izlazu samo dok postoji i signal na ulazu. Logicki elementi sa memorijom – izlazni signal u trenutku t je zavisan od ulaznih signala X, kao i od stanja elemenata u predhodnom trenutku, Qt-1, Y=f(Qt-1,X). Generatori signala obezbedjuju sinhroni rad svih elemenata racunara. Grupu aktivnih memorijskih elemenata cine elementi kod kojih su dva binarna stanja (0 i 1) definisana elektricnim stanjem elemenata. Vreme cuvanja informacija odredjeno je vremenom promene stanja elemenata. Grupu pasivnih elemenata cine elementi kod kojih je memorisanje informacija povezano sa promenom fizickog stanja. To su, npr. feritna jezgra. Vreme cuvanja informacija je u ovoj grupi duze neko kod prethodne grupe, i one se ovde mogu cuvati i po prestanku elektricnog napajanja. 11. Osnovni pojmovi vezani za apstraktne automate Ulazni signal X ja rec konacne duzine sastavljena iz nekog konacnog skupa slova – ulazne azbuke P={p1,...,pn}. Izlazni signal Y je rec konacne duzine sastavljena iz nekog konacnog skupa slova – azbuke S={s1,...,sk}. Najcesce se koristi binarna azbuka sa svojim slovima {0,1}. Funkcionisanje primitivnih automata je odredjeno pravilima preslikavanja ulazne reci X u izlaznu rec Y. U analitickom obliku ova pravila se iskazuju na sledeci nacin: yi=fi(x1,x2,...,xn); iÎ{1,2,...,k}. Ako xi i yi mogu uzimati samo vrednosti binarnih brojeva, onda funkcije fi predstavljaju Boole-ove (logicke, prekidacke) funkcije, a odgovarajuce tablice dobijene pri tabelarnom predstavljanju ovih funkcija se zovu tablice istinitosti. Slozenija obrada signala se vrsi putem klase konacnih automata koja poseduje konacan broj unutrasnjih stanja koja su okarakterisana azbukom Q={q1,q2,...,qm}. Funkcionisanje ovog automata je odredjeno funkcijama prelaza u novo stanje. A(Q,X), funkcijom izlaza automata B(Q,X):Q(t+1)=A(Q(t),X(t)),Y(t) =B(Q(t),X(t)), kao i pocetnim stanjem Q0. To je tzv. Milli-ev automat. Rad racunarskih uredjeja se cesto opisuje tzv. Moore-ovim automatom, koji je opisan relacijama: Q(t+1) =A(Q(t),X(t)),Y(t)=B(Q(t)), i pocetnim stanjem Q0. Pored tabela, konacni automati se pogu predstavljati i pomocu grafova. Svako stanje automata se smesta u teme grafa. Prelaz iz jednog stanja u drugo se oznacava strelicom na kojoj je naznacen izlazni signal koji je rezultat prethodnog stanja automata i ulaznog signala. 12. Elementi teorije Boole-ovih funkcija – promenljive x1,x2,...,xn nazivaju se binarnim (logickim, Boole-ovim, prekidackim) ako mogu uzimati samo dve vrednosti. funkcija f(x1,x2,...,xn) koja, kao i njeni argumenti, moze da uzima samo 2 vrednosti zove se Boole-ova funkcija. Boole-ove promenljive mogu uzimati samo dve vrednosti: 0 i 1, koje se uzajamno iskljucuju, ako je x=0, onda je x¹1; ako je x=1, onda je x¹0. Operacija komplementiranja (negacije) definise se kao 0(nadvuceno)=1, i 1(nadvuceno)=0. Logicka operacija konjunkcije (Ù) definise se kao 0Ù0 =0, 0Ù1=0, 1Ù0=0, 1Ù1=1. Ova operacija se zove i logicko mnozenje, pa se umesto x Ù y pise i xy. Logicka operacija disjunkcije (Ú) definise se kao: 0Ú0=0, 0Ú1=1, 1Ú0=1, 1Ú1=1. Ova operacija se zove i logicko sabiranje, umesto xÚy pise se i x+y. Iz navedenih postulata proizilaze odredjene osobine logicke algebre: 0+x=x, 1+x=1, 0x=0, 1x=x, ..., (x+y)(nadvuceno)=x(nadv.)y(nadv.). Ako su f(x1,...,xn) i q(x1,...,xn) proizviljne logicke funkcije, onda je to i funkcija h(f(x1,...,xn),g(x1,...,xn)). Logicke funkcije se mogu izraziti u tzv. normalnoj disjunktivnoj formi (kao suma proizvoda), ili u norm. konjunktivnoj formi (kao proizvod suma).  13. Logicki elementi bez memorije – da bi mogli da govorimo o slozenijim logickim mrezama neophodno je da se uvede skup simbola za logicke elemente koji se koriste za realizaciju osnovnih logickih funkcija. Rec je o osnovnim kolima u koja spadaju: I–kolo, koje ima vise ulaza i samo jedan izlaz putem koga se realizuje konjunkcija; ILI-kolo, takodje sa vise ulaza i jednim izlazom, kojim se realizuje disjunkcija; NE-kolo (invertor), sa jednim ulazom i jednim izlazom, kojim se realizuje komplementiranje (negacija); NI-kolo, koje nastaje invertovanjem I-kola, i realizuje funkciju Sefera; NILI-kolo (invertovano ILI), koje realizuje funkciju Pirsa, i EX-ILI-kolo (ekskluzivno ILI), koje realizuje funkciju ekskluzivne disjunkcije. Blok-sema tipicnog logickog uredjaja:
x1 x2 f(x1,x2,...,xn) : xn Ulazni i izlazni signali logickog elementa su elektricni naponi. Ovi signali se u racunarskim sistemima predstavljaju u 3 oblika: a)potencijalni b)impulsni c)dinamicki. Logicki elementi se ne ponasaju na idealan nacin. Signal koji je doveden na ulaz logickog elementa ne pojavljuje se trenutno na izlazu istog. Do njegove pojave na izlazu protekne izvesno vreme (vreme kasnjenja). Zbog kasnjenja koje prouzrokuje svaki element dolazi do kasnjenja u celokupnoj logickoj mrezi, i to kasnjenje odredjuje brzinu rada racunarskih sistema. 14. Kombinacione logicke mreze – k.l.m formiraju neka osnovna kola u racunaru. Posmatracemo jednostavna kola putem kojih se izvode operacije sabiranja i oduzimanja. Polusabirac je logicka mreza koja vrsi sabiranje dva log. broja, i generise prenos. Blok sema: a b S p 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 Analiticki izraz f-ja koje realizuju polusabirac: S=a(nadvuceno)b+ab(nadv.) p=ab. Polusabirac moze da izvrsi sabiranje samo na najmanjem znacajnom mestu, tj. na mestu gde nema prenosa sa manje znacajnog mesta. Pun sabirac se moze predstaviti pomocu polusabiraca i ILI-kola.  pi-1 Si
ai bi Pi Puni sabiraci omogucavaju sabiranje n brojeva i koriste se i za realizaciju sabiraca za decimalne brojeve kodirane u BCD 8421 kodu. 15. Memorijski elementi – kombinacione mreze, iako bitne za projektovanje digitalnih sistema, imaju za nedostatak to sto kod njih izlazni signal u datom trenutku zavisi samo od ulaznog signala u tom trenutku. Mogucnosti ovih mreza se mogu povecati ako se njima dodaju elementi koji mogu da pamte podatke, tako da onda signal na izlazu zavisi ne samo od ulaza, vec i od prethodnog rada logicke mreze. U osnovne memorijske elemente koji se srecu kod danasnjih racunara spadaju: bistabilni multivibratori (flip-flopovi) i magnetska jezgra. 16. Sekvencijalne logicke mreze – izradjene su od logickih i memorijskih elemenata (pre svega flip-flopova). Ove mraze prihvataju ulazne signale i generisu izlazne, koji su funkcije kako ulaznih signala, tako i stanja u kome se mreza nalazi. U racunarskoj tehnici su od prvenstvenog interesa sinhrone sekvencijalne log. mreze, kod kojih se sadrzaj memorijskih elemenata moze primeniti samo u toku trajanja taktnog impulsa. Jedna od osnovnih namena flip-flopova je izgradnja registara koji se obicno koriste za privremeno cuvanje podataka u procesu njihove obrade. Pored toga, registri se koriste i za transformaciju kodova iz paralelnog u serijski, i obrnuto. Pod paralelnim kodom se podraz. slucaj kada se svi binarni signali koji oznacavaju dati simbol istovremeno prenose. Pod serijskim kodom se podraz. slucaj kada se binarni signali koji oznacavaju jedan simbol u seriji prenose po jednoj liniji veze. *Registri za cuvanje podataka: za upisivanje i ocitavanje podataka kod ovog tipa registra koriste se specijalni signali (signali za upisivanje i citanje). Upis broja u registar se vrsi u dva takta. U prvom taktu se svi flip-flipovi dovode u stanje 0 pomocu taktnog impulsa i impulsa na liniji za brisanje sadrzaja registra. U drugom taktu se vrsi upis sadrzaja u registar. *Pomeracki(shift) registri: ovakav registar omogucava pomeranje ulevo i /ili desno reci smestene u registru za odredjeni broj pozicija. Takva operacija pomeranja je neophodna pri izvodjenja operacija mnozenja i deljenja. Shift registri se koriste i za pretvaranje paralelnog u serijski kod i obrnuto. ... Funkcije prelaza ovakvog shift registra su: y1(t+ t t)=x(t), y2(t+ t t)=y1(t), ..., yn(t)=yn-1(t) *Registri sa magnetnim jezgrima: za izgradnju operativne (magnetne) memorije jezgra se povezuju u matricu. Kroz svako jezgro prolaze po tri provodnika (ako postoji i provodnik za zabranu upisa onda ih ima cetiri, mada se kao provodnik za zabranu upisa moze iskoristiti i linija za citanje). To su: dva upravljacka provodnika X i Y koji sluze za odabiranje (adresiranje) jezgara Xi i Yi, i provodnik za citanje sadrzaja jezgra. *Brojaci su sekvencijalne mreze namenjene brojanju impulsa koji se pojavljuju na njihovom ulazu. Razlikuju se prema brojnom sistemu u kome vrse brojanje. Najrasprostranjeniji i najjednostavniji su binarni brojaci koji su sagradjeni od n flip-flopova. Ovakav brojac pocinje da broji od 0, pa sve do 2n–1 impulsa. Moguca je i realizacija brojaca koji broji unazad, pocev od 2n-1, pa do 0.
 |
RSS link na komentare