Logicke osnove obrade podataka

Algebra logike
Algebru logike moemo definisati kao strukturu
{S; , , }
gde je S = {>, }, binarna operacija konjunkcije, binarna operacija disjunkcije
i unarna operacija negacije.
Formule algebre logike se nazivaju i logicki izrazi.
Oznaka u matematici
Oznaka u racunarstvu

>
1

Neki od osnovnih zakona i identiteta Bulove algebre vezani za operacije negacije,

konjunkcije i disjunkcije koji se koriste u digitalnoj logici su:
AB=BA
(A B) C = A (B C)
A(B + C) = (AB) + (AC)
1A=A
A A= 0

A0=0
AA=A
A=A
(A B) C = A B C
AB=A+B

Osnovni zakoni
A+B=B+A
(A + B) + C = A + (B + C)
A + (BC) = (A + B)(A + C)
0+A=A
A + A= 1

Zakon komutacije
Zakon asocijacije
Zakon distribucije
Neutralni element
Inverzni element

Identiteti i pravila
A+1=1
A+A=A
(A + B) + C = A + B + C
A+B=AB

Dvostruka negacija
Brisanje zagrada
De Morganove teoreme

Logicke funkcije
Oznacimo sa A1 , A2 , ..., An logicke promenljive. Svaka funkcija
f : (A1 , A2 , ..., An ) {0, 1}
se naziva logicka funkcija.
Argument
A
Funkcija
f10
f11
f12
f13

Vrednost

Naziv

0
0
1
1

0
1
0
1

Oznaka

nula funkcija
identitet
negacija
jedinicna funkcija

Tabela 1: Logi
cke funkcije sa jednim argumentom

Argument
A
B
Funkcija
f20
f21
f22
f23
f24
f25
f26
f27
f28
f29
f2A
f2B
f2C
f2D
f2E
f2F

0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1

Vrednost
0 1 1
1 0 1
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1

0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1

0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1

Naziv

nula funkcija
konjunkcija
negacija implikacije od A ka B
prva projekcija
negacija implikacije od B ka A
druga projekcija
ekskluzivna disjunkcija
disjunkcija
Pirsova (Lukaieviceva) funk.
ekvivalencija
negacija druge projekcije
implikacija od B na A
negacija prve projekcije
implikacija od A na B
eferova funkcija
Jedinicna funkcija

Tabela 2: Logi
cke funkcije sa dva argumenta

Oznaka

AB
AB = (AB)
AB = (BA)
(AB)(AB)
AB
AB
(AB)
BA
AB
AB

Pun sistem funkcija

Skup F={f1 , f2 , ..., fn } funkcija se naziva pun sistem funkcija ako se proizvoljna
funkcija algebre logike moe predstaviti pomocu funkcija iz ovog skupa.
F je minimalan ako skup G = F { fi } (za neko i) ne predstavlja pun sistem funkcija.
Neki od minimalnih punih sistema funkcija:
1. F = { , }.
2. F = { , +}.
3. F={ }:
A= (A A)
A B = (A B) (A B)
A + B = (A A) (B B)
4. F={ }:
A= (A A)
A B = (A A) (B B)
A + B = (A B) (A B)

Savrene normalne forme funkcija

Primer: neka se od skupa promenljivih {A, B, C} grade logicki izrazi.
Elementarne konjunkcije su: A B, A C, A B, A C, ...
Elementarne disjunkcije su: A + B, A + C, A + B, A + C, ...
Savreno elementarne konjunkcije su: A B C, A B C, A B C, A B C,
...
Savreno elementarne disjunkcije su: A + B + C, A + B + C, A + B + C, A
+ B + C, ...
Konjunktivne forme su (A + B) (A + C), (A + B) (A + C),
Disjunktivne forme su A B + A C, A B + A C, ...
Savrene konjunktivne normalne forme su (A + B + C) (A + B + C),
(A + B + C) (A + B + C), ...
Savrene disjunktivne normalne forme su (A B C) + (A B C),
(A B C) + (A B C), ...

Funkcija je zapisana u obliku savreno konjunktivne normalne forme (skraceno

SKNF) ako je logicki izraz koji je predstavlja zapisan kao savreno konjunktivna
normalna forma pri cemu svaka od savrenih elementarnih konjunkcija koja ulazi
u njen sastav sadri sve promenljive koje su argumenti funkcije.
Funkcija je zapisana u obliku savreno disjunktivne normalne forme (skraceno
SDNF) ako je logicki izraz koji je predstavlja zapisan kao savreno disjunktivna
normalna forma pri cemu svaka od savrenih elementarnih disjunkcija koja ulazi
u njen sastav sadri sve promenljive koje su argumenti funkcije.

Primer: neka je funkcija F zadata preko tabele istinitosnih vrednosti predstavljene

u tabeli 3.

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

F
0
0
1
1
0
0
1
0

Tabela 3: Logi
cka funkcija sa tri promenljive

SDNF:
F = ABC + ABC + ABC
SKNF:
F = (ABC) (ABC) (ABC) (ABC) (ABC)
Primenom generalizovane De Morganove teoreme:
(X Y Z) = X + Y + Z
dobija se SKNF:
F

=
=

(A + B + C) (A + B + C) (A + B + C) (A + B + C) (A + B + C)
(A + B + C) (A + B + C) (A + B + C) (A + B + C) (A + B + C)

Logicki elementi
su fizicki objekti koji implementiraju neku od funkcija algebre logike
predstavljaju osnovne komponente svih elektronskih kola racunara
argumenti funkcija odgovaraju ulaznim velicinama logickih elemenata, a
vrednosti funkcija njihovim izlaznim velicinama.

Funkcija algebre logike

Negacija
Konjunkcija
Disjunkcija
eferova funkcija
Pirsova funkcija

Naziv logickog elementa

NEelement
Ielement
ILIelement
NIelement
NILIelement

Naziv na engleskom
NOTelement
ANDelement
ORelement
NANDelement
NORelement

Tabela 4: Osnovne logi

cke funkcije i logicki elementi

A
F

B
Ielement

ILIelement

Identitet

A
F

B
NIelement

NILIelement

NEelement

Slika 1: Osnovni logi

cki elementi

A
D

B
C

F=ABCD

a) Ielement sa cetiri ulaza

b) Isti signal na svim ulazima

Slika 2: Logi
cki elementi (nastavak)

Minimizacija logickih funkcija

Postoje tri nacina za minimizaciju funkcija:
1. Algebarske transformacije
2. Karnoove (Karnaugh) mape
3. Tablicna metoda Kvin-MekKlaskog (Quine-McKluskey)

Slika 3: Implementacija SDNF funkcije iz tabele 3

Slika 4: Implementacija SKNF funkcije iz tabele 3

10

Algebarske transformacije
Algebarske transformacije ukljucuju primenu osnovnih zakona i identiteta na logicki izraz. Na primer, na SDNF funkcije prikazane u tabeli 3
F = ABC + ABC + ABC
se mogu primeniti sledece transformacije:
1. Identitet 1 + A = 1. Kako SDNF funkcije ima vrednost 1 to mu se vrednost
nece promeniti ako dodamo izraz ABC
F = ABC + ABC + ABC + ABC
2. Zakon distribucije:
F = AB(C + C) + (A + A)BC
3. Zakon o inverznom elementu (A + A = 1) i identitetu (A1 = A)
F = AB + BC
4. Zakon distribucije:
Fmin = B(A + C)

11

Za prethodnu funkciju F:
Fmin = B(A + C) = (AB) + (BC) = (AB) + (BC)
Primenom De Morganove teoreme dobija se oblik sastavljen od tri NI izraza
FNImin = (AB) (BC)

A
B

Fmin

Fmin

Slika 5: Implementacija funkcije Fmin

B
C
Slika 6: NI implementacija funkcije Fmin

12

Karnoove mape
Minimizacija logickih funkcija sa malim brojem (oko 46) promenljivih.
Koristi se SDNF funkcije.

AB
00

01

BC
11

10

00

1
A

a) F=AB + AB

01

11

10

1
1

b) F=ABC + ABC + ABC

CD
00

11

10

00
AB

01

01
11
10

B
1
A
1

c) F=ABCD + ABCD + ABCD

D
d) Uproceno oznacavanje mapa

Slika 7: Upotreba Karnoovih mapa za prikaz logi

ckih funkcija

13

00

CD
01 11

10

00

00
AB

AB
1

11

AB
1

10

00

11

11

10

10

AB

CD
01 11

c) ABD
10

00

1
AB

CD
01 11

10

00

01

10

11

10

00

CD
01 11

f) BD
10

00

01

11

11

10

10

AB

CD
01 11

01

e) BC

00

00

01

01

g) A

10

00

d) AB

AB

01

b) BCD

CD
01 11

10

11

10

00

CD
01 11

00

01

a) ABD

AB

00

11

10

00

10

00

01

CD
01 11

00

CD
01 11

10

00

01

11

10

AB

h) D
Slika 8: Ozna
cavanje grupa kod Karnoovih mapa

i) C

14

00
0

BC
01 11
1

10

00

10

00

A
1

CD
01 11

1
AB
a) F = AB + BC

01

11

1
1

10

b) F = BCD + ACD
Slika 9: Preklapanje grupa kod Karnoovih mapa

Primer: nalaenje logicke funkcije koja realizuje sabiranje pakovane dekadne cifre
sa jedinicom. Cifra je kodirana u kodu 8421 kao 4-bitni binarni broj. Kombinacije
koje se ne koriste u kodu 8421 (10101111) su oznacene kao nebitno.

Dekadna
cifra
0
1
2
3
4
5
6
7
8
9
n
n
n
n
n
n

Ulaz
kod 8421
A B C
0 0 0
0 0 0
0 0 1
0 0 1
0 1 0
0 1 0
0 1 1
0 1 1
1 0 0
1 0 0
1 0 1
1 0 1
1 1 0
1 1 0
1 1 1
1 1 1

D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1

Dekadna
cifra
1
2
3
4
5
6
7
8
9
0

Izlaz
kod 8421
W X Y
0 0 0
0 0 1
0 0 1
0 1 0
0 1 0
0 1 1
0 1 1
1 0 0
1 0 0
0 0 0
n n n
n n n
n n n
n n n
n n n
n n n

Z
1
0
1
0
1
0
1
0
1
0
n
n
n
n
n
n

Tabela 5: Tabela istinitosnih vrednosti za jednocifreni BCD sabira

c

15

00

CD
01 11

10

00

00
AB

01

AB

11

10

01

11

10

CD
01 11

10

00

01

00

11
10

00

CD
01 11

10

00

01

11

10

c) Y = ACD + ACD

b) X = BD + BC + BCD

AB
n

10

00

a) W = AD + BCD

AB

CD
01 11

d) Z = D

Slika 10: Karnoove mape za BCD jednocifreni sabira

c

16

Metoda Kvin-Mekklaskog
A
0
0
0
0
0
0
0
0

B
0
0
0
0
1
1
1
1

C
0
0
1
1
0
0
1
1

D
0
1
0
1
0
1
0
1

F
0
1
0
0
0
1
1
1

A
1
1
1
1
1
1
1
1

B
0
0
0
0
1
1
1
1

C
0
0
1
1
0
0
1
1

D
0
1
0
1
0
1
0
1

F
0
0
0
1
1
1
0
1

Tabela 6: Funkcija F na koju se primenjuje metoda KvinMekKlaskog

Na osnovu tabele, SDNF funkcije F je

F = ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD + ABCD
U prvoj fazi minimizacije se konstruie tabela u kojoj svaki red odgovara jednoj
od konjunkcija iz SDNF. Redovi u tabeli ce biti grupisani prema broju komplementiranih promenljivih. Prva grupa sadri term iz SDNF koji ne sadri ni jednu
komplementiranu promenljivu, druga grupa sadri sve terme koji imaju jednu, itd.

Term

ABCD

ABCD
ABCD
ABCD

0
0
1

1
1
1

0
1
0

1
0
0

ABCD
ABCD
ABCD

0
1
1

1
0
1

1
1
0

1
1
1

ABCD

Tabela 7: I faza primene metode KvinMekKlaskog na funkciju iz tabele 6 (1/3)

17

Sledeci korak je pronalaenje svih parova terma koji se medjusobno razlikuju

samo za jednu jedinicu, tj. svih parova koji se razlikuju samo za vrednost jedne
promenljive.
Kad god se termi upare oznacicemo (npr. sa ) vrstu svakog od njih, kombinovati pronadjeni par eliminacijom promenljive koja se razlikuje i dobijeni
term prikljuciti novoj tabeli. Na primer, termi ABCD i ABCD se kombinuju
i daju term ACD. Postupak se nastavlja sve dok se pocetna tabela u potpunosti ne iscrpi. Redovi u tabeli formiranoj od novodobijenih terma su grupisani na isti nacin. Dobijena tabela je ulaz u naredni korak. U narednom
koraku se tabela obradjuje na isti nacin kao i tabela u prethodnom koraku.
Term

ACD

ABC
ABD
ABC
BCD

0
0
1

ABD
ACD
BCD

1
1

1
1
1
1

1
1

0
0

1
1
1

1
1

1
1

Tabela 8: I faza primene metode KvinMekKlaskog na funkciju iz tabele 6 (2/3)

U optem slucaju, proces se nastavlja sve dok se ne dobije tabela u kojoj ne mogu
da se pronadju upareni termi. U ovom primeru to je slucaj sa trecom tabelom koja
sadri samo term BD.
Term
BD

B
1

D
1

Tabela 9: I faza primene metode KvinMekKlaskog na funkciju iz tabele 6 (3/3)

18

ABCD
BD

ABCD

ABCD

ACD

ABCD

ABCD

ABCD

ABCD

ABCD

ABC

ABC
ACD

Tabela 10: II faza primene metode KvinMekKlaskog za funkciju F iz tabele 6

Postupak rada u drugoj fazi je sledeci:

1. Od preostalih terma konstruie se tabela ciji redovi odgovaraju termima koji
nisu eliminisani, dok kolone predstavljaju terme iz SDNF funkcije koja je bila
ulaz u proces minimizacije.
2. Sa X se oznaci svaka pozicija u tabeli koja se nalazi na preseku vrste i kolone
ako vai da term koji oznacava vrstu predstavlja deo terma koji oznacava
kolonu.
3. Ako kolona sadri samo jednu vrednost X, tada se to X zaokrui.
4. U svim redovima koji sadre neko od zaokruenih X-eva oko svih ostalih
X-eva se opie kvadrat.
5. Ako svaka od kolona sadri ili zaokrueno X ili X upisano u kvadrat tada je
postupak odredjivanja minimalne forme funkcije zavren. Minimalni oblik
cine termi koji oznacavaju one redove koji sadre X koje je oznaceno.
6. U slucaju kada postoji kolona koja ne sadri niti zaokrueno X niti X upisano
u kvadrat tada treba sprovesti dodatni postupak koji se sastoji u dodavanju
redova sve dok ne budu obuhvacene sve kolone.
U ovom slucaju, minimalni oblik funkcije F je
F= ABC + ACD + ABC + ACD

19

Kombinatorne mree
Kombinatorne mree predstavljaju skup medjusobno povezanih logickih elemenata ciji je izlaz u nekom vremenskom trenutku funkcija koja zavisi samo od vrednosti ulaza u tom istom vremenskom trenutku.
Kombinatorne mree se u literaturi nazivaju jo i kombinatorna kola. U optem
slucaju, kombinatorne mree se sastoje od n binarnih ulaza i m binarnih izlaza i
mogu biti definisane na tri nacina:
1. Preko tabele istinitosnih vrednosti koja sadri kombinacije za svaku od 2n
mogucih ulaznih vrednosti.
2. Preko povezanog skupa grafickih simbola.
3. Preko logickih funkcija koje izraavaju vezu izmedju ulaznih i izlaznih promenljivih (signala).

20

Multipleksori
Multipleksori su kombinatorne mree koje povezuju vie ulaznih signala u jedan
izlazni signal. U bilo kom trenutku bira se tacno jedan od ulaznih signala i proputa na izlaz.
D0

4na1

D1

MUX

D2
D3

S1 S2
Slika 11: Predstavljanje multipleksora 4na1

S1
0
0
1
1

S2
0
1
0
1

F
D0
D1
D2
D3

Tabela 11: Istinitosna tabela za multipleksor 4na1

21

S1

S2

D0

D1

D2

D3

Slika 12: Implementacija multipleksora 4na1

22

Dekoderi
Dekoderi predstavljaju kombinatorne mree sa vie izlaza pri cemu je istovremeno
aktivan samo jedan izlaz koji prepoznaje (dekodira) vrednost signala na ulazu. U
optem slucaju, dekoder ima n ulaza i najvie 2n izlaza.
Primer 1: dekodiranje adresa. Pretpostavimo da elimo da konstruiemo memoriju velicine 1KB koricenjem cetiri 2568-bitnih RAM cipova.
Adrese
000000FF
010001FF
020002FF
030003FF

Cip
0
1
2
3

A0

A7
2568

2568

2568

2568

RAM

RAM

RAM

RAM

A8
A9
2na4 dekoder

Slika 13: Dekoder adresa

23

Primer 2: dekoder kao demultipleksor. Ako se u dekoder uvedu dodatne ulazne

linije on tada moe da poslui kao demultipleksor. Demultipleksor vri inverznu
funkciju multipleksora, tj. razvodi jedan ulaz na vie izlaza.

nbitna
adresa

nna2n

2n izlaza

dekoder
linija sa
podacima
Slika 14: Implementacija demultipleksora pomo
cu dekodera

Primer 3: dekodiranje BCD cifre. Pretpostavka je da elimo da konstruiemo

dekoder koji koji vri dekodiranje (prevodjenje) binarno kodirane dekadne cifre iz
koda 8421 u dekadnu vrednost. Dekoder ce imati 4 ulaza i 16 izlaza.

24

F0
F1
F2
F3
F4
F5
F6
F7
F8
F9
F10
F11
F12
F13
F14
F15

Slika 15: Dekoder dekadnih cifara iz BCD zapisa

B
0
0
0
0
1
1
1
1
0
0
0
0
1
1
1
1

C
0
0
1
1
0
0
1
1
0
0
1
1
0
0
1
1

F0 =ABCD
F1 =ABCD
F2 =ABCD
F3 =ABCD

A
0
0
0
0
0
0
0
0
1
1
1
1
1
1
1
1

Ulaz
D
0
1
0
1
0
1
0
1
0
1
0
1
0
1
0
1

F0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0

F2
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0

F8
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0

F8 =ABCD
F9 =ABCD
F10 =ABCD
F11 =ABCD

F7
0
0
0
0
0
0
0
1
0
0
0
0
0
0
0
0

Izlaz
F9
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0
0

F10
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
0

Greka
F12 F13
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
1
0
0
0
0

F12 =ABCD
F13 =ABCD
F16 =ABCD
F15 =ABCD

F11
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0

Tabela 12: Zahtevi za dekoder dekadnih cifara iz BCD zapisa

F4 =ABCD
F5 =ABCD
F6 =ABCD
F7 =ABCD

F1
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0

Dekadne cigre
F3 F4 F5 F6
0
0
0
0
0
0
0
0
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
F14
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
0

F15
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1

25

26

Programibilni niz logickih elemenata

Programibilni niz logickih elemenata (eng. PLA, Programmable Logic Array) je cip
opte namene koji jednostavno moe da se prilagodi raznim specificnim potrebama.
Upotreba PLA je zasnovana na cinjenici da se svaka logicka funkcija moe izraziti
u obliku SDNF.

27

?
Izlaz1

?
Izlaz2

Slika 16: Izgled PLA sa tri ulaza i dva izlaza

ABC

AB

AC

?
Izlaz1
ABC + AB

?
Izlaz2
AB + AC

Slika 17: Dizajniranje veza u PLA sa tri ulaza i dva izlaza

28

Sabiraci
Sabiraci su kombinatorne mree koje se koriste pri realizaciji sabiranja. Sabiraci
mogu biti binarni i dekadni.
Binarni polusabirac je kombinatorna mrea koja vri sabiranje jednocifrenih binarnih brojeva.
A
0
0
1
1

B
0
1
0
1

C
0
1
1
0

P
0
0
0
1

Pp
0
0
0
0
1
1
1
1

Tabela 13: Istinitosne vrednosti za

A
0
0
1
1
0
0
1
1

B
0
1
0
1
0
1
0
1

C
0
1
1
0
1
0
0
1

Pt
0
0
0
1
0
1
1
1

Tabela 14: Istinitosne vrednosti za

binarni polusabirac

binarni sabirac

Na osnovu tabele se lako formira SDNF za funkcije C i P:

C = AB + AB
P = AB

C
P
P

PS

?
C

Slika 18: Implementacija polusabira

ca

Slika 19: Oznaka za polusabira

c

29

Kombinatorna mrea koja realizuje sabiranje dve binarne cifre viecifrenog binarnog broja uz uzimanje u obzir prenosa sa prethodnog mesta se naziva (pun)
sabirac.
Tabela istinitosnih vrednosti sabiraca je prikazana na prethodnoj strani.
Na osnovu tabele se formira SDNF za funkcije C i Pt :
C
Pt

=
=

ABP p + ABP p + ABP p + ABP p

ABP p + ABP p + ABP p + ABP p

SDNF za Pt moe da se minimizuje jednostavnom algebarskom transformacijom:

Pt

=
=
=

ABP p + ABP p + ABP p + ABP p + ABP p + ABP p

AB(P p + P p ) + BP p (A+ A) + AP p (B + B)
AB + BP p + AP p

A B Pp

?
Pt

Pt

?
C

Slika 20: Implementacija sabira

ca

Slika 21: Oznaka za sabira

c

Pp

30

Viecifreni sabiraci
Sabiranje viecifrenih binarnih brojeva se realizuje pomocu jednog sabiraca za
svako binarno mesto. U ovom slucaju se zbog akumulacije kanjenja javlja znacajno kanjenje izmedju bita najmanje i najvece teine kod sabiraca sa vecim brojem mesta.

Signal za
prekoracenje

A3

B3

A2

P3

B2

P2

?
C3

A1

B1

P1

?
C2

A0

B0

P0

?
C1

Slika 22: 4-bitni sabira

c

?
C0

31

Tehnikom nazvanom odredjivanje buducih prenosa (eng. carry lookahead) se kanjenje najvecim delom eliminie. Ova tehnika se primenjuje na sledeci nacin:
Oznacimo sa Pi prenos koji se dobija sabiranjem binarnih cifara na poziciji i i koji
se prenosi u sabirac koji sabira cifre na poziciji i + 1. Cilj je da definiemo Pi pomocu logickog izraza koji ne zavisi od P j , ij. U tabeli 14, uzimimo da je P p =
Pi1 i Pt = Pi . Takodje ocigledno vai P1 = 0. Tada vae sledece jednakosti:
P 0 = A0 B 0
P1 = A1 B1 + (A1 + B1 )P0
Zamenom prve jednakosti u drugoj dobija se
P 1 = A1 B 1 + A1 A 0 B 0 + B 1 A 0 B 0
Koristeci istu proceduru dobija se
P2 = A2 B2 + A2 A1 B1 + A2 A1 A0 B0 + A2 B1 A0 B0 + B2 A1 B1 + B2 A1 A0 B0 + B2 B1 A0 B0
Na slican nacin se dobijaju vrednosti Pi za proizvoljno velike sabirace.
Ovakav pristup je prakticno neprimenljiv za dugacke brojeve zbog glomaznosti dobijenih logickih izraza. Zbog toga se u realnim situacijama odredjivanje buducih
prenosa radi za sabirace koji sabiraju od 4 do 8 bitova istovremeno.
A31 B31

A24 B24 A23 B23

??
P31

8-bitni

??
P23

sabirac

A16 B16 A15 B15

??
8-bitni

??
P15

sabirac

A8 B 8

A7 B7

A0 B 0

??

??

??

??
8-bitni

P7

sabirac

C31

C24

C23

C16

C15

8-bitni

P1 = 0

sabirac

?
C8

?
C7

Slika 23: Konstrukcija 32-bitnog pomo

cu 8-bitnih sabiraca

?
C0

32

Sekvencijalne mree
Sekvencijalne mree predstavljaju skup povezanih logickih elemenata ciji je izlaz
u nekom vremenskom trenutku funkcija koja zavisi od tekuceg stanja elemenata
mree i vrednosti ulaza u tom istom vremenskom trenutku.

Flip-flop elementi
Flip-flop je najjednostavniji oblik sekvencijalne mree. Svi flip-flop elementi poseduju sledece dve osobine:
1. Flip-flop je bistabilni element. Poseduje dva stabilna stanja i u slucaju nepostojanja ulaza ostaje u trenutnom stanju. Na taj nacin flip-flop moe da
memoriadraj jednog bita.
2. Flip-flop ima dva izlaza koji su medjusobno komplementarni. Ovi izlazi se
obicno oznacavaju sa Q i Q.

33

R-S element

Q
Slika 24: RS flip-flop element

34

Ulaz
RS
00
00
10
10
01
01
11
11

Karakteristicna tabela
Tekuce
Naredno
stanje Qn
stanje Qn+1
0
0
1
1
0
0
1
0
0
1
1
1
0

Uprocen oblik
R
0
1
0
1

S
0
0
1
1

Tabela 15: Karakteristi

cna tabela R-S flip flop elementa

Qn+1
Qn
0
1

35

RS flip-flop sa casovnikom za sinhronizaciju

casovnik
Q

Slika 25: R-S flip-flop sa

casovnikom sa sinhronizaciju

D flip-flop element

casovnik

Slika 26: D flip-flop sa

casovnikom sa sinhronizaciju

Qn+1

36

JK flip-flop

Q
casovnik

Qn+1

Qn

Qn

Slika 27: JK flip-flop sa

casovnikom sa sinhronizaciju

1. J=0, K=0: izlaz je nepromenjen, stanje elementa je stabilno.

2. J=1, K=0: izlaz se postavlja na 1, bez obzira na prethodnu vrednost.
3. J=0, K=1: izlaz se postavlja na 0, bez obzira na prethodnu vrednost.
4. J=1, K=1: prethodna vrednost izlaza se invertuje. Npr. ako je prethodno Q
bilo 0 sada postaje 1 i obratno.

- Ck
R

- Ck
Q

RS flip-flop

- Ck
Q

JK flip-flop

Q
D flip-flop

Slika 28: Oznake za flip-flop elemente u sloenijim mreama

37

Registri
Registri su digitalna kola koja se koriste unutar CPU-a za cuvanje jednog ili vie
bitova podataka. Dva osnovna tipa registara koja se najcece koriste su paralelni
i pomeracki registri. Obe vrste se realizuju u obliku sekvencijalnih mrea u cijoj
izgradnji se koriste flip-flop elementi.

Paralelni registri
Paralelni registar se sastoji od skupa 1-bitnih memorijskih jedinica ciji sadraj
moe istovremeno da se cita/upisuje.

Izlazni
kontrolni
signal

Signal za
anuliranje

Ulazni
kontrolni
signal

D18

D08

S Q

S Q

D17

D07

S Q

D06

D05
Izlazne linije

S Q

D14

Linije podataka
D15

S Q

Slika 29: 8-bitni paralelni registar

D16

D04

D13

S Q

D03

D12

S Q

D02

D11

S Q

D01

38

39

Pomeracki registri
Pomeracki registri prihvataju i prenose informacije serijski. Sadraj registra se
moe pomerati na dva nacina:
1. Logicki, pri cemu se sadraj registra posmatra kao binarna rec. Logicko pomeranje moe biti linijsko ili ciklicko.
2. Aritmeticki, pri cemu se sadraj registra posmatra kao broj, i pri pomeranju
se vodi racuna o znaku. Aritmeticko pomeranje moe biti binarno (kada je
sadraj binarni broj) ili dekadno (kada je sadraj BCD broj). Pri aritmetickom pomeranju BCD brojeva istovremeno se pomeraju grupe od po 4 bita.

S1

Q1

- Ck
R1 Q 1

S2

Q2

- Ck
R2 Q 2

S3

Q3

- Ck
R3 Q 3

S4

Q4

- Ck
R4 Q 4

Casovnik
Slika 30: 4-bitni pomera
cki registar (logicko linijsko pomeranje)

an

an

an

Logicko ciklicko
ulevo

Logicko ciklicko
udesno

Aritmeticko
binarno ulevo

Aritmeticko
binarno udesno

an

Logicko linijsko
udesno

an

an

an

Logicko linijsko
ulevo

Vrsta pomeranja

an1

an1

an1

an1

an1

an1

a1

a1

a1

a1

a1

a0

a0

a0

a0

a0

a0

an

an

an

an

an

an1 an2

a0

an1 an2

a0

a2

a0

a2

a0

a2

bit za otkrivanje prekoracenja

Sadraj registra posle pomeranja

an1 an2

Slika 31: Vrste pomeranja sadraja registra

a1

bit za otkrivanje prekoracenja

Sadraj registra pre pomeranja

a1

a1

an

a1

40

41

Brojaci
Brojaci su registri koji imaju mogucnost jednostavnog uvecanja ili umanjenja vrednosti za 1. Vrednost brojaca se uvecava (ili umanjuje) po modulu jednakom kapacitetu registra. Maksimalna vrednost koju brojac od n flip-flopova moe da
registruje je 2n -1. Kada se brojac koji ima maksimalnu vrednost poveca za 1, njegova vrednost se menja na 0.

Asinhroni brojaci
Kod asinhronih brojaca se ulazni signal prenosi kroz brojac u obliku talasa.

Casovnik

- Ck
K

- Ck
Q

K
Q0

- Ck
Q

- Ck
Q

Q1
a) Sekvencijalna mrea

Casovnik
Q0
Q1
Q2
Q3
b) Vremenski dijagram
Slika 32: 4-bitni asinhroni broja
c

K
Q2

Q
Q3

42

Sinhroni brojaci
Kod sinhronih brojaca se izlazi svih flip-flop elemenata koji ih sacinjavaju menjaju
istovremeno.
Primer 3-bitni binarni brojac. U implementaciji ce biti koricena tri JK flipflop elementa, oznacena sa A, B, C. Neka element A predstavlja bit najvece, a
element C bit najmanje teine. Oznacimo J i K ulaze u svaki od elemenata sa
odgovarajucim indeksom; Ja , Ka , Jb , Kb , Jc i Kc ; izlaze i njihove komplemente
oznacimo prema oznakama samih brojaca: A, A, B, B, C i C.
Qn
0
0
1
1

J
0
1
n
n

K
n
n
1
0

Qn+1
0
1
0
1

Na osnovu karakteristicne tabele vidi se da brojac moe da ima sledece vrednosti:

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

Odavde se vidi da ako je vrednost brojaca A=0, B=0, C=0 tada u narednom uvecanju vrednosti brojaca treba zadrati vrednosti A=0, B=0 i promeniti vrednost
C na 1. Iz modifikacije karakteristicne tabele se vidi da je za odravanje izlaza na
nuli potrebno da bude J=0 dok je vrednost K
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

Ja
0
0
0
1
n
n
n
n

Ka
n
n
n
n
0
0
0
1

Jb
0
1
n
n
0
1
n
n

Kb
n
n
0
1
n
n
0
1

Jc
1
n
1
n
1
n
1
n

Kc
n
1
n
1
n
1
n
1

Tabela 16: Tabela istinitosnih vrednosti 3-bitnog sinhronog broja

ca

43

nebitna. Slicno, za promenu vrednosti sa 0 na 1 (za flip-flop C) potrebno je da

bude J=1 dok je vrednost K nebitna. Time su odredjene odgovarajuce vrednosti
za Ja , Ka , Jb , Kb , Jc i Kc u tom redu tabele istinitosnih vrednosti. Na slican nacin
se formiraju i ostali redovi. Dobijena tabela istinitosnih vrednosti je prikazana u
tabeli 16.
Naredni korak predstavlja minimizacija funkcija koje predstavljaju ulazne velicine
u flip-flop elemente. Npr. pomocu Karnoovih mapa dobija se
Ja =BC

Ka =BC

Jb =C

Kb =C

Jc =1

Kc =1

Na osnovu minimizovanih vrednosti se konstruie sinhroni brojac ciji je izgled

prikazan na slici 33.

casovnik

- Ck
K

- Ck
C

- Ck
B

Slika 33: 3-bitni sinhroni broja

c