•          Iz ovih primera se vidi da rezultat, ako je negativan, zavisi od toga koji se komplement koristi, jer je različita interpretacija negativnih brojeva u prvom i drugom komplementu.

Množenje binarnih brojeva

•          Množenje pozitivnih binarnih brojeva svodi se na pomeranje u levo za jednu poziciju od LSB

•                      Primer: 0100*10=010002.

•          Množenje označenih brojeva, gde je negativan broj predstavljen drugim komplementom,  vrši se pomeranjem u levo i ekstenzijom odnosno dodavanjem MSB=0 za original i MSB=1 za drugi komplement. Poslednja vrednost u pomeranju je uvek original.

Primeri množenja neoznačenih i označenih brojeva

•          Neoznačeni brojevi  Označeni brojevi, neg. II kom 

Delenje binarnih brojeva

•          Deljenje neoznačenih brojeva po uzoru na decimalne.

•          Primer: 10100,12 :102 =1010,012.

•          Delenje sa 2, 4, 8, 16, ... 2k. Svodi se na pomeranje u desno za k pozicija.

•          Primer: 010101112:01000=01010.111

•          Delenje označenih brojeva vrši se po posebnom algoritmu.

Zaključak

•          Računar je osnovni uređaj informacionih tehnologija, elektronska kola i sklopovi razumeju samo binarni zapis.

•          Aritimetika u binarnom brojnom sistemu je nužna za obradu podataka, izračunavanja su sastavni deo obrade podataka i informacija.

•          Aritimetičke operacije su: sabiranje, oduzimanje, množenje i delenje

•          Komplementi se uvode radi jednostavnijeg i bržeg izračunavanja.

PREDAVANJE BROJ 5 I 6

KODOVI

Binarni kodovi decimalnih cifara

Grejov kod

Alfanumerički kodovi

Kodovi za detekciju i korekciju grešaka

Binarni kodovi decimalnih cifara

•          Kod ili šifra je skup pravila za razumevanje zapisa. Kodovanje je pravilo pridruživanja kodne reči podatku ili informaciji.

•          Niz od n binarnih cifara je kodna reč ili kod.

•          Binarno kodovane decimalne cifre nazivaju se BCD kodovi, od binary-coded decimal (BCD).

•          Cifre decimalnog brojnog sistema se mogu zapisati kodnom reči sa 4 bita (četvorkama ili tetrama).

•          Primetimo da nisu iskorišćene sve moguće kodne reči, jer je 24=16.

•          Od načina pridruživanja četvorki svakoj cifri postoji viže BCD kodova.

BCD kodovi

•          Prirodni BCD kod ili BCD kod 8421, ili NBCD kod 710=0111.

•          BCD kod 2421, samokomplementaran kod 910=1111, a prvi koplement od 910 je 0000=010 ili 72=0010.

•          Kod više 3 ili XS3 (excess-3), cifra se uveća za 3 pa se koduje, 610=1001XS3  ili 910=1100XS3.

•          Bikvinarni kod, koristi sedam bita prva dva bita  pokazuju opseg cifre (0 do 4) prva dva su  01 ili (5 do 9) oni su 10.

•          Kod jedan od deset je pomerački kod, koji koristi kodnu reč od 10 bita, za kodovanje decimalne cifre.

Kodovanje i dekodovanje BCD8421 (NBCD)

•          Kodovanje se izvodi tako što se cvaka cifra decimalnog brojnog sistema koduje tetrom.

•          Primer 38910=0011 1000 1001NBCD.

•          Dekodovanje se vrši tako što se svaka tetra pretvara u decimalnu cifru, 1001 0111 0100NBCD=97410.

•          Jednostavno kodovanje i dekodovanje ali se javlja problem kod računskih operacija u ovom kodu.

•          Primer sabiranja 3210+ 2810=6010, a u NBCD kodu imamo

            0011 0010+0010 1000=0101 1010NBCD=5 1010, ovaj broj ne postoji. Ovaj problem se rešava dodavanjem 0110=610 pa se dobije 0110 0000NBCD.

Kod veše 3 ili XS3

•          Kodovanje u BCD kodu više 3 se izvodi tako što se svaka decimalna cifra uveća za tri i pretvori u prirodni binarni kod.

•          Primer 3910=3+3109+310=0110 1100XS3

•          Dekodovanje se vrši tako što se XS3 pretvori u decimalne cifre i od svake se oduzme br. 3.

•          Primer 0110 1100xs3=(6-3)10)(12-3)10=3910.

•          Aritimetičke operacije se vrše  po pravilima binarnih brojeva samo se vodi računa o  uvećanju.

Grejov kod (Gray code)

•          U merenjima često se koriste elektromehanički pretvarači fizičkih veličina.

•          Kodovanje u Grejovom kodu se vrši prepisivanjem cifre MSB i sledeća cifra se sabere sa prethodnom, bez prenosa. Uočite da Grejov kod je u stvari kodovanje binarnog zapisa.

•          Primer 1012=510 u Grejovom kodu je 111G.

•          Dekodovanje se izvodi tako što se MSB prepiše i prepisani bit se sabere sa narednim u Grejovom kodu, bez prenosa.

•          Primeri: 111G=1012=510 , 1210=11002=1010G.

Alfanumerički kodovi

•          Niz ili sekvenca od n bita ne predstavlja uvek brojnu vrednost nego neki logički znak ili slovo (simbol, karakter).

•          Najpoznatiji alfanumerički ko je kod ASCII (American Standard Code Information Interchange), koji koristi niz od sedam binarnih cifara.

•          ASCII koristi niz od sedam bita (binarnih cifara) za svaki karakter.

•          Primer string TRI=1010100 1010010 1001001.

•          U prilogu predavanja je data tabela coda ASCII.

Kodovi za detekciju i korekciju grešaka

•          Greška je promena vrednosti binarne cifre 1 u 0 i obrnuto. Dakle, može se javiti jedna i više grešaka u kodnoj reči.

•          Postoje povremeni i stalni uzroci grešaka.

•          Radi otklanjanja grešaka u kodnoj reči postoji tehnička disciplina zaštitnog kodovanja.

•          U principu pre korekcije pogrešne vrednosti treba  u tvrditi odnosno detektovati grešku.

•          Postoje kodovi samo za detekciju grešaka i kodovi za detekciju i korekciju.

Kodovi za detekciju grešaka

•          Bit parnosti se dodaje na informacioni niz, ako je paran broj jedinica dodaje se cifra 0, a ako je neparan dodaje se cifra 1.

•          Metod provere na parnost predložio je Heming (Hamming).

•          Niz od n+1 bit mora da ima paran broj nula ili jedinica.

•          Međutim, ako se u istoj kodnoj reči pojave dve greške neće se moći detektovati.

•          Takođe, nije poznato na kojoj je poziciji došlo do greške.

Kodovi za detekciju grešaka

•          Bit parnosti se može dodavati na kraju kodne reči sa n bita, takozvana vertikalna redundansa ili VRC (Vertical Redundancy Check). Na primer n=4, za parnost jedinica imamo 1001 0 ili 1000 1.

•          Složeniji kod za detekciju grešaka je LRC kod (Longitudinal Redundancy Check). Primer ovog koda 92410=1100 0101 0111XS3. Ako se saberu po modulu dva (bez prenosa cifre na istoj poziciju) dobije se nova tetra 1110 ili LRC kodna reč. Sada je broj predstavljen sa 16 cifara 1100 0101 0111 1110. Na prijemu se proverava sabiranjem po modulu 2. Ako je LRC=0 nema greške.

Kodovi za detekciju greške: kontrola sume

•          Na predajnoj strani niz od n binarnih cifara, kodna reč, se podeli na dva dela pa se sabiranje izvrši po pravilima prvog komplementa, prenos se sabere sa LSB. Dužina sume jednaka je polovini kodne reči. Odredi se prvi komplement sume i doda na kraju kodne reči.

•           Na prijemu, kodna reč se podeli na tri dela i izvrši sabiranje po pravilu prvog komplementa. Potom se odredi prvi komplement  zbir. Ako je prvi komplement sume na svim pozicijama 0 nije došlo do greške.

•          Na primer kodna reč je 1001001001001010→delenjem na dva dela 10010010+01001010=11011100=S pa je prvi komplement sum 00100011. Na prijemu se deli u tri grupe   10010010+01001010+00100011=11111111.Očito da je  je prvi komplement sume  00000000. Dakle ne postoji greška.

Kodovi za detekciju greške: ciklička provera

•          Metod cikličke provere bazira na delenju po modulu 2, Cyclical Redundancy Check (CRC), a VCR sabiranje po moduku 2.

•          Zasniva se na činjenici da su dva broja deljiva kada se deljeniku oduzme ostatak.

•          Originalna kodna reč se proširuje sa k-1 nula ako je delitelj sa k cifara.

•          Primer n=6 i k=4. Prvo se na kodnu reč 101011 dodaju k-1=3 nula. Potom se izvrši delenje, sa 1101. Ostatak delenja 3 cifre se unose umesto nula. Pa se šalje 101011110, jer je 110 ostatak delenja.

•          Na prijemu se nova kodna reč deli sa istim deliteljom 1101. Ako je CRC=000 nema greške, ako je CRC ima bar jednu jedinicu kodna reč je neispravna i odbacuje se.

Kodovi za korekciju grešaka

•          Da bismo ispravili greške moramo ih prvo detektovati, pa sledi da ovi kodovi unose više redundanse.

•          Kodno rastojanje je broj različitih cifara na istim pozicijama dve kodne reči

•          Sabiranje po modulu je sabiranje bez prenosa.

•          Minimalno kodno rastojanje dve kodne reči  M≥D+C+1, gde su D- broj detektovanih grešaka, C-broj korigovanih grešaka, a D≥C.

•          Za M=1 nije moguće detektovati ni ispraviti grešku (D=C=0). Za M=2, D=1 i C=0. Dakle za korekciju samo jedne greške M=3.

Ispravljanje jednog bita

•          Dužina kodne reči n=ni+nk binarnih cifara, gde je ni informacionih bita i nk korekcionih bita (cifara).

•          Kontrolni bitovi određuju poziciju na kojoj se pojavila greška. Broj kontrolnih bitova se određuje iz relacije

•          Najpoznatiji kod za ispravljanje jedne  grešaka je Hemingov kod. Heming (Hamming) je 1950 predložio  metod konstrukcije kodova sa minimalnim kodnim rastojanjem M=3 i nazvan je Hemingovim kodom.

Hemingov koder

1.       Listu poruka napisati sa rednim brojem poruke (1,2…)

2.        Broj informacionih bita ni se određuje u odnosu na ukupan broj poruka. Broj kontrolnih bita nk zavisi od  broja informacionih bita 2nk≥ni+nk+1.

3.       Formiramo sume po osnovi 2 za poruke 1,3,5,7,9, jer ovi redni brojevi imaju jedinicu na mestu LSB. Ova suma je S1. Na drugoj poziciju imaju jedinicu redni brojevi poruke 2,3,6. Formiramo sumu po osnovi 2 i ova suma je S2. Na trećoj poziciji jedinice imaju poruke sa rednim brojevima 4, 6, 7,12 i.t.d. To je suma S3. Sve dok ne dobijemo k jednačina. Iz suma se odrede kontrolni bitovi.

4.        Označimo pozicije svake cifre u  kodnoj reči (xn, xn-1,…x2, x1) sa informacionim i kontrolnim bitovima. Kontrolni bitovi su na pozicijama 2i , i=0,1,2,3... . Uočiti da je xn cifra MSB, a x1 je LSB.

Hemingov dekoder

1.       Na prijemnoj strani odredimo sume, po istom algoritmu,                                                                        S1, S2, S3  itd.. i formiramo kodnu reč od Sk,, Sk-1...S1=Nk, Nk pokazuje poziciju greške.

2.       Ako je Nk=0000 nema greške u prenosu.

3.        Ako je Nk različito od nule došlo je do greške u prenosu,

4.        Na primer Nk=0010 to znači da je došlo do greške na drugoj poziciji u kodnoj reči, odnosno da je x2 pogrešno primljeno.

5.       Izvrši se ispravka x2 i to ako je primljena 0 koriguje se u 1 i obrnuto ako je primljna 1 koriguje se u 0.

Primer Hemingovog kodovanja-dekodovanja

1.       Potrebno je preneti 10 poruka, za ovih deset poruka treba nam najmanje 4 bita, jer je 24=16, a 23=8. Dakle ni=4 iako sve kombinacije nisu iskorišćene.

2.       Za 4 informaciona bita treba odrediti nk. Broj  kontrolnih bitova se određuje iz relacije 2nk≥ni+nk+1. Za ni=4 nk=3.

3.       Nezaštićene poruke u BCD kodu X1=0001; X2=0010, itd.

4.       Zaštićene poruke imaju po sedam cifara x7,x6,x5,x4,x3,x2,x1. Sada treba odrediti kontrolne bitove ili cifre, koji su  K1, K2  i K3, koji su na pozicijama K1=x1,K2=x2 i K3=x4.

Određivanje vrednosti kontrolnih bitova

5. Kontrolni bitovi se određuju iz relacije za sume:

6. Ako se prenosi poruka X2=0010, sa kontrolnim bitovima je 001K31K2K1= x7,x6,x5,x4,x3,x2,x1. Iz uslova za sume, S1=0 , S2 =0 i S3=0, sledi: K1=0,   K2=1 i K3=0

7. Poruka sa zaštitnim ili kontrolnim bitovima (podvučeni) je X2k=0010110.

8. Na prijemu se proveri pristigla poruka. Odrede se  sume. Za pristiglu poruku X2k su S1 =S2= S3=0.

9. Ako je pristigla pogrešna poruka na primer X2k=0110110. Vrednosti suma su S1=0 S2=1 i  S3=1. Nk=110=610, pa je na poziciji  šest došlo do greške.

10. Treba korigovati 1 u 0, pa je ispravna poruka X2k=0010110.

PREDAVANJE BROJ 7

BULOVA ILI PREKIDAČKA  ALGEBRA

Aksiomi i teoreme

Osnovne logičke operacije i simboli

Predstavljanje logičkih funkcija

Analiza i sinteza kombinacionih kola

Aksiomi Bulove algebre

•          Bulova ili prekidačka algebra je pogodna za analizu i sintezu digitalnih kola.

•          Engleski matematičar George Bool je 1854. postavio temelje logičke algebre, a tek 1938. Claude Shenon pokazuje da je ova matematička forma pogodna za   praktičnu primenu kod proučavanja prekidača i releja.

•          Aksiom je minimalan skup osnovnih definicija koje se smatraju istinitim,  koji se ne dokazuje. Bulove algebre su:

1.       Binarna variabla ima oblast definisanosti u dve tačke x=0, ako je x≠1 i obrnuto, aksiom isključivosti.

2.       Binarna varijabla ima svoju invertovanu vrednost x‘=1, ako je x=0 i obrnuto.

3.       Logičko sabiranje i množenje: 3.1 1+1=1  i 0•0=0

3.2 0+0=0 i 1•1=1, 3.3 1+0=0+1=1 i 1•0=0•1=0. gde “+” nema veze sa binarnim sabiranjem nego ima funkciju ili, a simbol “• “ funkciju i.

Teoreme Bulove algebre

•          Teoreme se dokazuju na osnovu aksioma.

•          Teoreme za jednu promenljivu:

T1        x+0=x, x•1=x, neutralni elementi (0 i 1).

T2        x+1=1, x•0=0, dominantni elementi.

T3        x+x=x,             x•x=x, redukcija istih elemenata.

T4        (x')'=x, komplement komplementa je original.

T5        x+x‘=1,            x•x‘=0.

•            Teoreme za dve i tri promenljive

T6        x+y=y+x,                     x•y=y•x, komutativnost

T7        x+(y+z)=(x+y)=z,        x•(y•z)=(x•y) •z, asocijativnost

T8        x•(y+z)=x•y+x•z,         (x+y) •(x+z)=x+y•z, distributivnost

Teoreme za dve i tri i više promenljivih

T9        x+x•y=x,                                 x•(x+y)=x.

T10       x•y+x•y’=x,                 (x+y) •(x+y’)=x

T11  x•y+x’•z+y•z=xy+x’z,  (x+y)•(x.+z)=(x+y)•(x’+z)

T12 x+x+x…=x,                        x•x•x•…=x

T13 (x1+x2+x3+…+xn)’=(x’1•x’2•x’3•…•x’n)

             (x1 • x2 • x3 • … • xn)’=(x’1+x’2+x’3+…+x’n)

T14 Svaki iskaz ostaje istinit ako se zamene “1” i “0” i operatori   “+” i “•”, primer 1+0+0=1  0 • 1•1=0.

Osnovne logičke operacije i simboli

•          Osnovna kola: ILI, I, invertor i bafer

Predstavljanje logičkih funkcija

•          Logička prekidačka funkcija se predstavlja: analitički (algebarski) i tabelarno.

•          Algebarski zapis funkcije F(x,y)=x+y ili F(x,y,z)=xy+z.

•          Tabelarno predstavljanje podrazumeva sve tačke definisanosti funkcije, 2n tačaka, redni broj tačke definisanosti (indeks) u NBCD kodu i  vrednosti funkcije.

•          Primer

Potpuni proizvod i potpuna suma

•          Potpuni proizvod od n promenljivih je logički proizvod dužine n, u kojem se svaka promenljiva javlja samo jedanput, kao original ili kao komplement.

•          Potpuni proizvod je jednak 1 samo u jednoj tački oblasti definisanosti funkcije (2n tačaka).

•          Stoga se  logička funcija zapisuje kao suma potpunih proizvoda, za tačke gde je vrednost funkcije jednaka 1.

•          Potpuna suma od n promenljivih je logička suma dužine n, u kojem se svaka promenljiva javlja samo jedanput, kao original ili kao komplement. Potpuna suma ima vrednost 0 samo u jednoj tački od ukupno 2n tačaka oblasti definisanosti.

•          Proizvod potpunih suma daju vrednost funkcije nula (0).

Primer-zapis funkcije preko potpunih proizvoda i potpunih suma

•          Zapisati funkciju  datu u tabel, pomoću sume potpunih proizvoda i proizvoda potpunih suma. Pokazati da se u oba slučaja dobije isti rezultat.

•          Funkcija F1(x,y)=x’y’+xy ili F0(x,y)=(x+y’)(x’+y)=x’y’+xy.

Uprošćavanje logičkih funkcija

•          Minimizacija logičkih funkcija se vrši u cilju što prostije realizacije logičke funkcije pomoću elektronskih logičkih kola.

•          Minimizacija se zasniva na teoremi T10.

            (proizvod promenljivih)•x+(proizvod promenljivih)•x’=

proizvod promenljivih. Primer: x(yz)+x’(yz)=yz.

Dualno (suma promenljivih +x)•(suma promenljivih+x’)=

=suma prom. Primer: (x+y+z) • (x’+y+z)=y+z.

Metode uprošćavanja (minimizacije)

•          Metodi minimizacije su:

1.      Algebarski, pomoću teorema Bulove algebre, ne postoji kriterijum za najprostiju formu.

2.      Tabelarno, tablično predstavljena logička funkcija i posebni programi za uprošćavanje zapisa funkcije. Najpoznatiji program je Kvin-Mekklaski.

3.      Grafički, tabelarno se predstave jedna do druge  tačke definisanosti funkcije, susedne tačke se razlikuju samo za jednu promenljivu. Poznat je kao metod Karnoovih (Karnaugh) mapa (karta).

Uprošćavanje  zapisa funkcije algebarski

•          Uprošćavanje zapisa vrši se primenom teorema Bulove algebre. Uprošćavanjem se dobiju sume  nepotpunih proizvoda ili proizvodi nepotpunih suma. Primeri:

•           Za sume proizvoda F(x,y,z)= xy’z+xyz=xz(y’+y)=xz, rezultat je nepotpuni proizvod.

•          Za proizvod suma F(x,y,z)=(x+y’+z)(x’+y+z)=x’y’+x’z+

+xy+yz+xz+y’z+z=x’y’+z+xy+z+z=x’y’+xy+z, rezultat je suma nepotpunih proizvoda.

•          Međutim, postavlja se pitanje da li je moguće dalje redukovati izraz? Nema kriterijuma za minimalnu formu.

Minimizacija pomoću Karnoove mape

•          Karnoova (Karnaugh) mapa ili karta je tablična predstava logičke funkcije, koja vizuelno postavlja jednu pored druge susedne tačke u oblasti definisanosti funkcije.

•          Dve tačke, iz oblasti definisanosti funkcije, su susedne ako su sve promenljive u tim tačkama imaju iste vrednosti  osim jedne, koja se sa originalom i komplementom pojavljuje u susednim tačkama.

•          Primer: xyzw i xy’zw, ako funkcija ima vrednost 1 u ove dve susedne tačke tada je zapisujemo samo sa jednim nepotpunim proizvodom umesto sa dva potpuna proizvooda, jer je xyzw+xy’zw=xzw(y+y’)=xzw.

Primeri predstavljanja funkcija

•          Funkcije F1(x,y) i  F2(x,y,z)  tabelarno predstavljaju tako da su date sve tačke oblasti definisanosti.

Nepotpuno definisana funkcija

•          Nepotpuno definisana prekidačka funkcija ima jednu ili više tačaka u oblasti definisanosti, za koje funkcija ima bilo koju vrednost, što se obično označava sa “b” (blanck) ili sa “x”. To u praksi znači da ulazne promenljive ne mogu imati neki skup vrednosti ili da je za primenu nevažna vrednost funkcije u tim tačkama.

•          Obično se zadaje F(x,y,z,w)=F1(x,y,z,w)=F1(2,5,8,10,13) i Fb(3,4,6), ovakav zapis funkcije pokazuje da funkcija ima vrednost jedan u tačkama, binarno zapisani decimalni brojevi, 2,5,8,10,13 i nije definisana u tačkama 3,4,6.

Postupak minimizacije pomoću sume proizvoda

•          Teoretski osnov je teorema T10, alat je Karnoova mapa.

•          Cilj je da se sve jedinice prekriju  grupama (kubovima) veličine 2k, gde je k=0,1,2,3...Teži se da broj kubova bude minimalan a veličina kuba maksimalna. Tačke (slogovi) sa “b” ili “x” mogu se priključiti kubu ako su susedi i ako povećavaju kub.

•          Dakle, kubovi su pravougaonog oblika sa k slogova. Slogovi unutar kuba se sažimaju. Broj kubova je broj proizvoda.

•          Pravilo, ide se duž dve susedne  stranice pravougaonika, koji predstavlja kub, i pišu se promenljive koje ne menjaju vrednost duž  stranice pravougaonika. Ako je promenljiva ima vrednost jedan piše se original, a ako ima vrednost nula piše se komplement.

PREDAVANJE BROJ 8

KOMBINACIONA KOLA

Analiza i sinteza kombinacionih kola

Analiza kombinacionih kola

•          Prekidačka ili Bulova algebra je osnov za kombinaciona i sekvencijalna logička kola.

•          Kod kombinacionih logičkih kola izlaz zavisi samo od ulaza u datom vremenskom trenutku. Kod sekvencijalnih kola izlaz zavisi od trenutnog ulaza i od prethodnog stanja na izlazu.

•          U analizi kombinacionih kola polazi se od šeme električnog kombinacionog kola.

•          Kombinaciono kolo može da ima k ulaza i l izlaza.

•          Nacrta se tabela sa k+l+1 kolonom i 2k vrsta (tačaka definisanosti funkcije). Broj kolona uvećana za jednu kolonu koja je indeks.

Primer analize

•          Postave se vrednosti ulaza za prvi slog (i=0) i odredi se vrednost izlaza, postupak se nastavlja za sve vrednosti indeksa (i=1,2,3...).

•          Izvršiti analizu kola sa slike. Potrebno je odrediti funkcije F1 i F2.

  Minimizacija logičke funkcije F1

•          Iz tabele se vidi dafunkcija F2 ima vrednost jedan samo za jedan slog. Pa je napisana preko potpunog proizvoda F2=x’1x2x3. Ovo je i njena minimalna forma.

•          Funkcija F1 ima vrednost jedan na 6 slogova i vrednost  nula na dva sloga. Pošto ima manje nula predstavićemo je pomoću proizvoda potpunih suma.

            F1=(x’1+x’2+x3)(x’1+x’2+x’3)=x’1+x’2=(x1x2)’.

•           Rezultat se dobija u minimalnoj formi korišenjem Karnove mape. Dakle, moguće je realizovati funkcije i sa drugim logičkim kolima.

Sinteza kombinacionih kola

•          Sinteza podrazumeva iznalaženje algebarskog zapisa prekidačke funkcije i njenu realizaciju sa logičkim elementima.

•          Primer: Projektovati kombinaciono kolo koje izdvaja proste brojeve iz skupa prirodnih brojeva 1,2,3...14,15.

•          Rešenje: Po definiciji prost broj je deljiv samo sam sa sobom i  sa jedinicom. To su brojevi 3,5,7,11,13.

Postupak sinteze

•          Uočimo da se na ulazu može pojaviti prirodni brojevi [1,15]. Dakle, treba najmanje 4 binarne cife za njihov binarni zapis. Funkcija ima vrednost jedan samo za one indekse koji odgovaraju prostom broju.

•           Indeks predstavlja decimalni zapis broja, promenljive D,C,B,A (A je LSB) binarni zapis indeksa.

•          Formiramo tabelu sa indeksom, ulaznim promenljivim i vrednosti funkcije.

Tabelarne
vrednosti

Zapis funkcije pomoću sume proizvoda

•          Pošto imamo samo 5 jedinica koristimo sume proizvoda.

F1(D,C,B,A)=D’C’BA+D’CB’A+D’CBA+DC’BA+ +DCB’A.

•          Da li je zapisana funkcija u minimalnoj formi? Vidi se da prvi i treći potpuni proizvod mogu biti redukovani. Međutim, nema kriterija za analitičku redukciju. Zato ćemo iskoristiti Karnovu mapu.

Minimizacija zapisa funkcije

•          Karnova mapa za četiri promenljive sa vrednostima iz tabele

            Po pravilu upisa slogova po označenim pravougaonicima, ali samo oneih  koji se ne menjaju duž stranice dobijamo samo tri sume nepotpunih proizvoda F1=CB’A+D’BA+C’BA

            Realizacija funkcije

•          Minimalna forma funkcije se realizuje sa četiri troulazna standardna logička kola, ne računajući invertore.

•          Međutim, funkcija bez minimizacije se realizuje sa pet četveroulazna i jednim petoulaznim logičkim kolom, ne računajući invertore. 

•          Minimizaciju treba izvršiti u cilju pojednostavljenja logičke šeme koja realizuje funkciju.

Binarni sabirač

Tipovi kombinacionih kola

•          Koder, dekoder, multiplekser, demultiplekser, komparator, sabirač, kombinaciona programabilna logičke komponente (PLD), kao što su PROM, PLA , PAL.

•          PROM je dekodersko-koderska struktura, programiranje vrši korisnik ili proizvođač (ROM). Ako se moće brisati isprogramirani sadržaj nazivaju se EPROM. Elektronsko brisanje E2PROM, a posebna vrsta E2PROM je FLASH (FLEŠ).

•          PROM komponente se koriste za čuvanje podataka, a ređe za realizaciju prekidačke funkcije.

PREDAVANJE BROJ 9

STRUKTURA RAČUNARA

Komponente računara

Princip rada

Funkcionalni delovi hardvera računara

•          U funkcionalnom smislu računar ima tri osnovne celine:

•          Procesor (processor)

•          Operativna memorija (main memory)

•          Ulazno-izlazni uređaji (input-output devices).

•          Povezivanje navedena tri modula se realizuje preko magistrale (bus), koja ima tri podmagistrale (adresna, podataka i upravljačka).

•          Procesor i operativna memorija su smešteni na jednoj ploči sa štampanim vezama (mother board)

•          Ulazni i izlazni uređaji se nazivaju periferne jedinice.

Šematski prikaz

1.Procesor

•          Procesor je osnovni uređaj (komponenta) svakog računara u kojoj se obavlja obrada informacija i upravljanje svim modulima. Često se naziva centralna procesorska jedinica Central Processing Unit (CPU). Procesor ima tri osnovna dela:

1.       Operacione ili procesne jedinice (aritimetičke i logičke operacije) ili aritimetičko-logička jedinica

2.       Kontrolne jedinice,

3.       Skupa registara.

Blok šema procesora

Izvršenje operacije

•          Svaka operacija u računaru se izvršava pomoću aritimetičko-logičke i kontrolne jedinice.Registri služe za upis podatka ili naredbe, a mogu da služe za neke računske operacije.

•          Dakle, u operacionoj jedinici se izvršavaju aritimetičko-logičke operacije nad podacima koji se uzimaju iz operativne memorije.

•          Pre izvršenja operacija se razlaže na niz elementarnih koraka, čiji redosled zavisi od logičkih uslova.

•          Uređeni niz koraka na koje je operacija rastavljena i niz logičkih uslova koji određuju redosled izvršenja koraka naziva se algoritam operacije.

Upravljačka jedinica procesora

•          Upravljačka jedinica procesora ispituje uslove koju u nju dolaze i određuje redosled koraka u izvršenju operacije.

•          U upravljačkoj jedinici procesora generiše se takt za izvršenje koraka algoritma.

•          Kada se kaže da računar radi sa taktom 1 GHz to znači da generiše milijardu impulsa u sekundi. U svakom taktu računar može da izvrši jednu operaciju (mikrooperaciju). U jednom taktu može se izvršiti više mikrooperacija ako su nezavisne (a+b i c+d).

•          Upravljačka jedinica organizuje i usaglašava rad svih jedinica u računaru, a ne samo u procesoru.

•          Računari sa dva i više procesora mogu rade paralelno i nazivaju se multiprocesorski  računarski sistem.

2. Operativna memorija

•          Operativna memorija je deo računara u kojem se u toku obrade nalaze programi, na osnovu kojih računar vrši određenu obradu nad podacima, podaci, međurezultati i rezultati obrade.

•          Osnovni parametri operativne memorije su:

1.       Kapacitet memorije,

2.       Vreme pristupa ćeliji, vreme za koje se upiše ili pročita sadržaj celije. i

3.       Dužina ćelije, broj bitova koji se mogu u nju smestiti..

Blok šema operativne memorije

•          Dužina adresabilne ćelije se izražava brojem bita n (8, 16, 32, 64, 128), odnosno sa reči dužine n.

•          Kapacitet operativne memorije je broj adresabilnih ćelija m. Dakle, kapacitet zavisi od dužine adresabilnih ćelija i broja tih ćelija.

•          Na primer 1MR=1024 kR=210R(reči), a reč može da ima više bajtova (B=8 binarnih cifara).

•          Organizacija memorije

Tipovi memorija u operativnoj memoriji

•          Memorija za upis i čitanje (Read Write Memory- RWM). Često se ovaj tip memorije naziva memorija sa slučajnim pristupom (Random Access Memory). U ovoj memoriji je cache memorija velike brzine i relativno malog kapaciteta.

•          U ovoj memoriji se čuvaju međurezultati i rezultati operacija i popravke i izmene programa.

•           Ova memorija gubi sadržaj pri nestanku napajanja računara, gube se svi podaci koji nisu arhivirani u neku drugu memoriju.

•          Druga vrsta memorije u operativnoj memoriji je memorija samo za čitanje (Read Onli Memory-ROM). U ovu mrmoriju se upisuju podaci u toku proizvodnje. Sadržaj jedanput upisan ostaje nepromenjen. (PROM, EPROM i EEPROM).

3.Ulazno-izlazni uređaji

•          Komunikacija računara sa čovekom i sa drugim uređajima ostvaruje se preko ulazno-izlaznih jedinica.

•          Ulazno izlazna jedinica ima dva dela:

1.       Kontroler (controller) ili interfejs

2.       Periferal (peripheral) uređaj za određenu namenu, tastatura, miš, štampač i dr.

•          Kontroler ili interfejs realizuje vezu između periferala i procesora.

•          Svaki periferal mora imati kontroler, koji se sastoji iz upravljačkog bloka i registara.

Registi kontrolera

•          Registri kontrolera se dele u tri grupe:

1.       Registri naredbi, u ovaj registar procesor upisuje naredbe za početak rada periferala, završetak rada periferala i režim rada.

2.       Registri stanja, u ovaj registar upravljački blok kontrolera ili interfejsa upisuje stnje, na primer da je uređaj speman da primi novi podatak i sl.

3.       Registri podataka, u ovaj registar se upisuje ulazni podaci koji se prenose od interfeisa ka procesoru i obrnuto izlazni podaci.

•          Registrima se pristupa pomoću adrese kao i u slučaju pristupa ćeliji operativne memorije.

Fizičko povezivanje ulazno-izlaznih uređaja

•          Povezivanje periferala sa računarom vrši se pomoću standardnih priključaka ili portova (port).

•          Povezivanje računara sa drugim računarom ili na mrežu vrši se sa posebnim karticama koja ima drajvere i softver za upravljanje.

•          Dakle sem standardnih računarskih periferala danas se koriste i mnogi uređaji za multimedijalni prikaz informacija.

PREDAVANJE BROJ 10

KOMUNIKACIJA I PRENOS PODATAKA I INFORMACIJA

1.Fizička predstava podatka i komunkacionih linija

2.Uslovi komuniciranja

3. Osnovni pojmovi računarskih mreža

Prenos podataka i komandi

•          Iz blok šeme se vidi da centralni procesor komunicira u jednom smeru sa ulaznim i izlaznim (simpleks) i dvosmerno sa ulazno-izlaznim i memorijama (dupleks).

•          Podatke i komande fizički predstavljaju inpulsi, koji se generišu u elektronskim kolima jedinica računara.

•          Osnovni podatak je binarna cifra predstavljena nulom ili jedinicim. Nula predstavlja niski naponski nivo  i jedinica visoki naponski nivo, ili obrnuto u negativnoj logici

2. Uslovi za komunikaciju

•          Da bi se ostvarila razmena podataka između dva i više uređaja potrebno je ispuniti dva uslova:

1.       Fizička povezanost dva uređaja (metalnim provodnikom, optičkim kablom ili bežična veza (wireless),

2.       Dogovoren način komunikacije ili jezik komunikacije, što se naziva protokol.

•          Protokol je skup pravila koja upravljaju prenosom podataka, odnosno komunikacijom.

Serijski prenos

•          Prenos podataka se može obaviti serijski i paralelno.

•          Ako se između dva uređaja obavlja prenos samo po jednom kanalu i bitovi se šalju sukcesivno jedan za drugim reč je o serijskom prenosu. U jednom taktu se prenosi samo jedna binarna cifra (bit). Dakle, tp=8Ti

Paralelan prenos

•          U slučaju paralelnog prenosa postoji n kanala, to omogućava da se istovremeno prenesu svih n bitiva. U slučaju prenosa jednog bajta (8 bita) postoji osam kanala.

•          Paralelni prenos traje n puta manje od serijskog prenosa podataka. Sad se svi bitovi prenesu u jednom impulsnom intervalu Ti.

•          Dakle, brzina prenosa podataka je važan parametar kanala.

Brzina prenosa i greške u prenosu

•          Pod brzinom prenosa se podrazumeva broj bitova (binarnih cifara) u sekundi. Brzina se izražava u b/s. Ona zavisi od vremena propagacije signala, dužine linije za vezu i kapaciteta kanala.

•           Naravno predajnik može da generiše više simbola u sekundi nego što može kanal da primi i obrnuto.

•          Zbog toga se definiše i kapacitet kanala, koji se takođe izražava u b/s.

•          Zbog neusklađenosti brzina i šuma u kanalu javljaju se greške u prenosu. Greške su nula primljena posle poslate  jedinice ili jedinica primljena posle poslate nule. Pe=P(1)P(0/1)+P(0)P(1/0), gde je P verovatnoća događaja.

Asihron i sihron prenos podataka

•          Potreba za sinhronizacijom se javlja zbog toga da se izbegne kašnjenje prijemnika u odnosu na predajnik, ovo kašnjenje bi dovelo do pogrešnih podataka.

•          Na primer ako ukucamo na tastaturi reč RAD, u ASCII kodu 1101010=R, 0100001=A, 01000010=D. Ako ne bi počelo čitanje na vreme pročitali bi neka druga slova.

•          Asihron prenos podrazumeva start bit na početku i stop bit na kraju  kodne reči. Start bit je obično logička nula a stop bit logička jedinica. Vidi se da se povećava broj impulsa 2/8=25% .

Primer sinhronog prenosa

•          Videli smo da kod asihronog prenosa predajnik obaveštava prijemnik o početku i kraju poruke. Kod sinhronog prenosa predaja i prijem su stalno u sinhronizaciji.

•          Sinhronizacija se obavlja stalnim slanjem sinhronizacione reči. Na primer u ASCII kodu šalje se bajt za sinhronizaciju 10010110.

•           Prijemnik podesi svoj takt pošto zna da treba da primi kodnu reč dužine 8 cifara.

•          Sinhroni prenos je efikasniji od asihronog, a oba su serijski tip prenosa podataka.

3. Komunikacije između dva računara

•          Povezivanjem dva i više računara u cilju korišćenja zajedničkih resursa naziva se mreža (network). Elementi mreže su dati na slici.

Klient-server (client-server) model

•          U ovom modelu klienti (mušterije) su vezani za vršioca usluga (server). Server ima dva osnovna zadatka:

1.       Da pruža usluge klient računaru

2.       Da nadgleda funkcionisanje mreže.

•          Server računar je znatno brži i ima veći kapacitet memorije od klijent računara.

•          Komunikacija uvek počinje sa zahtevom klienta. Server čeka zahtev klienta, kada ga dobije obavlja posao i šalje odgovor.

Komunikacioni softver

•          Uslov za komunikaciju pored fizičke linije, medijuma za prenos, potrebno je da postoje pravila za komunikaciju.

•          Skup pravila se predstavlja u obliku programa, softvera, za komunikaciju.

•          Komunikacioni softver obuhvata mrežni operativni sistem i protokol.

•          Mrežni operativni sistem (Network operating system) omogućava da dva umrežena računara koriste iste resurse (štampač, fajlove i dr.).

•          Poznati su Microsoft WindowsNT/2000, NovelNetWare, IBM OS/2 Warp Server i dr.

•          Mrežni operativni sistemi se dele u dve grupe, ravnopravnih računara u mreži ili klient-server orijentisani  mrežni operativni sistemi.

Osnovni slojevi mreže

•          Da bi komunicirala dva računara mora postojati:

1.        Hardver, linija veze i uređaj koji prilagođava signal liniji veze.

2.       Softver, koji predstavlja skup pravila za komunikaciju, naziva se komunikacioni softver

•          U mrežama se razlikuju tri sloja:

1.       Fizički sloj (Physical layer), omogućava prenos signala.

2.       Sloj veze (Data link layer), razume poruke.

3.       Sloj aplikacije (Application layer).

•          Između susednih slojeva postoji interfeiz za prenos podataka.

•            Mesta na kojima hierarhijski viši sloj pristupa uslugama nazivaju se tačke pristupa (Service Access Point- SAP).