Priprave na vaje za predmet Osnove digitalnih vezij Miha Moškon 2017 Univerza v Ljubljani Fakulteta za računalništvo in informatiko Kataložni zapis o publikaciji (CIP) pripravili v Narodni in univerzitetni knjižnici v Ljubljani COBISS.SI-ID=292687616 ISBN 978-961-6209-94-6 (pdf) Copyright c 2017 Založba UL FRI. All rights reserved. Elektronska izdaja knjige je na voljo na URL: http://zalozba.fri.uni-lj.si/moskon2017.pdf Recenzenta: doc. dr. Mira Trebar, prof. dr. Nikolaj Zimic Založnik: Založba UL FRI, Ljubljana Izdajatelj: UL Fakulteta za računalništvo in informatiko, Ljubljana 1. izdaja, 2017 Urednik: prof. dr. Franc Solina Kazalo 1 Priprava na 1. laboratorijske vaje 5 1.1 Boolova algebra in preklopne funkcije . . . . . . . . . . . . . . . . . 5 1.1.1 Postulati Boolove algebre . . . . . . . . . . . . . . . . . . . 5 1.1.2 Lastnosti Boolove algebre . . . . . . . . . . . . . . . . . . . 6 1.2 Podajanje preklopnih funkcij . . . . . . . . . . . . . . . . . . . . . . 7 1.3 Osnovne preklopne funkcije . . . . . . . . . . . . . . . . . . . . . . 7 1.3.1 Disjunkcija . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3.2 Konjunkcija . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.3.3 Negacija . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3.4 Peircov operator . . . . . . . . . . . . . . . . . . . . . . . . 9 1.3.5 Shefferjev operator . . . . . . . . . . . . . . . . . . . . . . . 9 1.3.6 Ekskluzivni ali . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3.7 Ekvivalenca . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.3.8 Implikacija . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4 Analiti no reöevanje preklopnih funkcij . . . . . . . . . . . . . . . . 11 2 Priprava na 2. laboratorijske vaje 13 2.1 Zapis preklopnih funkcij . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2 Analiti ni zapis in popolne normalne oblike zapisa preklopnih funkcij 13 2.2.1 Popolna disjunktivna normalna oblika (PDNO) . . . . . . . 13 2.2.2 Popolna konjunktivna normalna oblika (PKNO) . . . . . . . 14 2.2.3 Relaciji med makstermi in mintermi . . . . . . . . . . . . . . 16 2.2.4 Pretvarjanje med PDNO in PKNO . . . . . . . . . . . . . . 17 3 Priprava na 3. laboratorijske vaje 19 3.1 Zapis preklopnih funkcij z Veitchevim diagramom . . . . . . . . . . 19 3.2 Funkcijsko poln sistem . . . . . . . . . . . . . . . . . . . . . . . . . 20 4 Priprava na 4. laboratorijske vaje 21 4.1 Zaprti razredi in preverjanje funkcijske polnosti sistema . . . . . . . 21 5 Priprava na 5. laboratorijske vaje 27 5.1 Minimalne oblike zapisa preklopnih funkcij . . . . . . . . . . . . . . 27 iii iv Kazalo 5.2 Veitchev postopek minimizacije . . . . . . . . . . . . . . . . . . . . 28 5.2.1 Dolo anje minimalne normalne oblike z Veitchevim diagramom 30 6 Priprava na 6. laboratorijske vaje 35 6.1 Simetri ne preklopne funkcije . . . . . . . . . . . . . . . . . . . . . 35 6.2 Quineova metoda minimizacije . . . . . . . . . . . . . . . . . . . . . 36 6.2.1 Dolo anje MDNO . . . . . . . . . . . . . . . . . . . . . . . . 36 6.2.2 Dolo anje MKNO . . . . . . . . . . . . . . . . . . . . . . . . 37 7 Priprava na 7. laboratorijske vaje 39 7.1 Lo enje preklopnih funkcij . . . . . . . . . . . . . . . . . . . . . . . 39 7.2 Multiplekser . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 7.3 Realizacija preklopnih funkcij z multiplekserji . . . . . . . . . . . . 41 7.3.1 ätevilo vhodnih spremenljivk je enako ötevilu naslovnih vho- dov multiplekserja . . . . . . . . . . . . . . . . . . . . . . . 42 7.3.2 ätevilo vhodnih spremenljivk je za 1 ve je od ötevila naslovnih vhodov multiplekserja . . . . . . . . . . . . . . . . . . . . . 42 7.3.3 ätevilo vhodnih spremenljivk je za ve kot 1 ve je od ötevila naslovnih vhodov multiplekserja . . . . . . . . . . . . . . . . 44 8 Priprava na 8. laboratorijske vaje 47 8.1 Sekven na vezja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 8.2 Sploöna pomnilna ena ba . . . . . . . . . . . . . . . . . . . . . . . . 47 8.3 Enostavne pomnilne celice . . . . . . . . . . . . . . . . . . . . . . . 48 8.3.1 RS pomnilna celica ( Reset Set) . . . . . . . . . . . . . . . . 48 8.3.2 JK pomnilna celica ( Jump Kill) . . . . . . . . . . . . . . . . 49 8.3.3 T pomnilna celica ( Trigger) . . . . . . . . . . . . . . . . . . 50 8.3.4 D pomnilna celica (Delay) . . . . . . . . . . . . . . . . . . . 51 8.4 Realizacija sekven nih vezij s pomnilnimi celicami . . . . . . . . . . 51 9 Priprava na 9. laboratorijske vaje 55 9.1 Moorov in Mealyjev kon ni avtomat . . . . . . . . . . . . . . . . . . 55 9.2 Pretvorbe med avtomati . . . . . . . . . . . . . . . . . . . . . . . . 59 10 Priprava na 10. laboratorijske vaje 63 10.1 Realizacija kon nih avtomatov s pomnilnimi celicami (Moorov avto- mat) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 11 Priprava na 11. laboratorijske vaje 69 11.1 Realizacija kon nih avtomatov s pomnilnimi celicami (Mealyjev avtomat) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 12 Dodatna vaja 73 Kazalo v 12.1 Realizacija preprostega procesorja . . . . . . . . . . . . . . . . . . . 73 12.2 Osnovno delovanje procesorja . . . . . . . . . . . . . . . . . . . . . 73 12.2.1 Prevzem ukaza . . . . . . . . . . . . . . . . . . . . . . . . . 73 12.2.2 Izvedba ukaza . . . . . . . . . . . . . . . . . . . . . . . . . . 74 12.3 Osnovna arhitektura procesorja . . . . . . . . . . . . . . . . . . . . 74 12.3.1 Sploöno namenski registri . . . . . . . . . . . . . . . . . . . 74 12.3.2 Programski ötevec . . . . . . . . . . . . . . . . . . . . . . . . 75 12.3.3 Ukazni register . . . . . . . . . . . . . . . . . . . . . . . . . 75 12.3.4 Kontrolna enota . . . . . . . . . . . . . . . . . . . . . . . . . 75 12.3.5 Aritmeti no logi na enota . . . . . . . . . . . . . . . . . . . 77 12.3.6 Ukazni pomnilnik . . . . . . . . . . . . . . . . . . . . . . . . 78 12.3.7 Podatkovni pomnilnik . . . . . . . . . . . . . . . . . . . . . 78 12.3.8 Ostala kombinatorna logika . . . . . . . . . . . . . . . . . . 78 12.4 Nabor ukazov . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 12.4.1 Load A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 12.4.2 Load B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 12.4.3 Store A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 12.4.4 Add . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 12.4.5 Sub . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 12.5 Razlaga uporabljenih gradnikov . . . . . . . . . . . . . . . . . . . . 79 12.5.1 Register . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 12.5.2 Programski ötevec . . . . . . . . . . . . . . . . . . . . . . . . 80 12.5.3 Seötevalnik . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 12.5.4 Odötevalnik . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 12.5.5 Read Only Memory (ROM) . . . . . . . . . . . . . . . . . . 82 12.5.6 Random Access Memory (RAM) . . . . . . . . . . . . . . . 83 12.6 Realizacija opisanega procesorja . . . . . . . . . . . . . . . . . . . . 83 12.7 Zgled delovanja procesorja . . . . . . . . . . . . . . . . . . . . . . . 84 A Slovensko-angleöki slovar osnovnih pojmov 87 Literatura 91 Predgovor Pred vami je skripta priprav na laboratorijske vaje pri predmetu Osnove digitalnih vezij, ki se izvaja na 1. stopnji univerzitetnih ötudijskih programov Ra unalniötvo in informatika in Ra unalniötvo in matematika na Fakulteti za ra unalniötvo in informatiko Univerze v Ljubljani. Skripta sluûi obveznim pripravam, ki jih morajo sluöatelji predmeta opraviti pred vsako laboratorijsko vajo. Vsaka priprava je sestavljena iz kratkega povzetka teoreti nih osnov in enega ali ve prakti nih zgledov. Na podlagi tako pridobljenega znanja lahko ötudent pristopi k reöevanju kviza, katerega oddaja je obvezna za pristop k naslednji laboratorijski vaji. Upam, da bo skripta sluûila svojemu namenu in bo ötudentom omogo ila laûje osvajanje znanja s podro ja osnov digitalnih vezij, ki ga v dolo eni meri potrebuje vsak ra unalni ar. Teoreti ne osnove lahko ötudenti najdejo v prosojnicah na spletni u ilnici in dodatni literaturi kot je [4] (v slovenskem jeziku) in [2] (v angleökem jeziku), dodatne vaje pa so na voljo v [1, 3]. doc. dr. Miha Moökon, 2017 1 Zahvala Najprej bi se zahvalil svojim predhodnikom, tj. asistentom pri predmetu Preklopne strukture in sistemi, za zasnovo vaj, ki jih je evolucija ötudijskih programov pripeljala v stanje, v katerem so danes. Prav tako bi se rad zahvalil prof. dr. Nikolaju Zimicu, za sodelovanje pri prenovi vaj po bolonjski reformi. Zahvaljujem se asistentoma Primoûu Pe arju in Domnu äoberlu, ki sta sodelovala pri nastajanju osnutka skripte, ki jo imate pred seboj. Zahvaljujem se tudi asistentoma Juretu Demöarju in Mattiji Petroniju za dolo ene popravke in dopolnitve tekom izvajanja vaj v ötudijskih letih 2014/2015 in 2015/2016. Rad bi se zahvalil vsem sodelavcem Laboratorija za ra unalniöke strukture in sisteme, predvsem pa Miranu Koprivcu, za pomo pri izvajanju vaj in iskanju ter popravljanju napak. Za slednje bi se zahvalil tudi obema recenzentoma, prof. dr. Nikolaju Zimicu in doc. dr. Miri Trebar. Nenazadnje se zahvaljujem vsem ötudentom za njihove kritike, pohvale in predloge glede izvajanja vaj pri predmetu Osnove digitalnih vezij. 3 1 Priprava na 1. laboratorijske vaje 1.1 Boolova algebra in preklopne funkcije Preklopne (tudi logi ne) funkcije so funkcije nad preklopnimi (tudi logi nimi) spremenljivkami (spremenljivke, ki lahko zavzamejo vrednosti iz mnoûice {0 , 1}) in nad katerimi temelji procesiranje podatkov z uporabo digitalnih vezij. Preklopne funkcije (operatorji), elementi nad katerimi operirajo (operandi) in pravila po katerih operirajo so definirani z Boolovo algebro. Boolovo algebro lahko definiramo kot troj ek { X, O, P}, kjer je X mnoûica ele- mentov Boolove algebre (operandov), O mnoûica osnovnih funkcij (operatorjev), ki vsebuje disnjunkcijo (‚) in konjunkcijo (·), in P mnoûica postulatov oziroma pravil, ki so opisana v nadaljevanju. 1.1.1 Postulati Boolove algebre Zaprtost P1: x, y œ X; x ‚ y œ X P1ú: x, y œ X; x · y œ X Nevtralni element P2: x, 0 œ X; x ‚ 0 = x P2ú: x, 1 œ X; x · 1 = x Komutativnost P3: x, y œ X; x ‚ y = y ‚ x P3ú: x, y œ X; x · y = y · x 5 6 Poglavje 1 Priprava na 1. laboratorijske vaje Distributivnost P4: x, y, z œ X; x ‚ ( y · z) = ( x ‚ y) · ( x ‚ z) P4ú: x, y, z œ X; x · ( y ‚ z) = ( x · y) ‚ ( x · z) Inverzni element P5:’ x œ X, ÷ x œ X; x ‚ x = 1 P5ú:’ x œ X, ÷ x œ X; x · x = 0 ätevilo elementov P6:÷ x, y œ X; x ”= y 1.1.2 Lastnosti Boolove algebre Iz postulatov izhajajo dolo ene lastnosti, ki jih lahko uporabimo pri poenostavljanju logi nih izrazov. V nadaljevanju je naötetih nekaj bolj uporabnih lastnosti. Idempotenca x ‚ x ‚ · · · ‚ x = x x · x · · · · · x = x Absorpcija x ‚ x · y = x x · ( x ‚ y) = x Asociativnost ( x ‚ y) ‚ z = x ‚ ( y ‚ z) = x ‚ y ‚ z ( x · y) · z = x · ( y · z) = x · y · z DeMorganovo pravilo ( x 1 ‚ x 2 ‚ · · · ‚ x ) = n x 1 · x 2 · · · · · xn ( x 1 · x 2 · · · · · x ) = n x 1 ‚ x 2 ‚ · · · ‚ xn 1.2 Podajanje preklopnih funkcij 7 1.2 Podajanje preklopnih funkcij Vsako preklopno funkcijo lahko podamo na razli ne na ine, pri emer so osnovni na ini slede i: • Logi ni izraz funkcijo podaja analiti no, tj. kot ena bo, v kateri nastopajo logi ne spremenljivke (operandi), ki so med seboj povezane preko preklopnih funkcij (operatorji). • Logi na shema funkcijo podaja grafi no, tj. s shemo njene realizacije. Vhodi v shemo opisujejo vhodne spremenljivke, izhodi iz sheme pa izhodne. V shemi uporabljamo logi ne simbole, ki predstavljajo osnovne logi ne operatorje (opozorilo: v razli ni literaturi boste sre ali razli ne logi ne simbole). • Pravilnostna tabela funkcijo podaja tabelari no, tj. podaja vse moûne kombi- nacije vhodnih vektorjev in funkcijske vrednosti pri posamezni kombinaciji. Pri tem na levi strani tabele nastopajo vhodne (neodvisne) spremenljivke, ki dolo ajo vhodni vektor, na desni pa izhodne (odvisne) spremenljivke. Po- ljubno preklopno funkcijo z n vhodnimi spremenljivkami lahko opiöemo s pravilnostno tabelo, ki ima 2 n vrstic. • Veitchevega diagrama zaenkrat öe ne bomo podrobneje obravnavali. 1.3 Osnovne preklopne funkcije Boolova algebra definira osnovna logi na operatorja, tj. disjunkcijo (or) in ko- njunkcijo (and). Preko postulata Inverzni element vpeljemo öe negacijo (not). V nadaljevanju podajamo osnovne logi ne operatorje, s katerimi lahko zapiöemo poljubno preklopno funkcijo in so realizirani tudi znotraj druûine logi nih ipov 7400. 1.3.1 Disjunkcija Disjunkcija (ALI, OR) vrne logi no 1, ko je na logi no 1 postavljena vsaj ena izmed njenih vhodnih spremenljivk. V logi nem izrazu jo ozna ujemo s simbolom ‚. Slika 1.1 podaja logi ni izraz (a), logi ni simbol (b) in pravilnostno tabelo (c) za disjunkcijo z dvema vhodnima spremenljivkama. 1.3.2 Konjunkcija Konjunkcija (IN, AND) vrne logi no 1, ko so na logi no 1 postavljene vse vhodne spremenljivke. V logi nem izrazu jo ozna ujemo s simbolom · ali ·, v asih pa simbol celo izpustimo (podobno kot pri mnoûenju). Slika 1.2 podaja logi ni izraz 8 Poglavje 1 Priprava na 1. laboratorijske vaje x 1 x 2 y 0 0 0 y = x 1 ‚ x 2 0 1 1 1 0 1 1 1 1 (a) (b) (c) Slika 1.1 Logi ni izraz (a), logi ni simbol (b) in pravilnostna tabela (c) za disjunkcijo z dvema vhodnima spremenljivkama. (a), logi ni simbol (b) in pravilnostno tabelo (c) za konjunkcijo z dvema vhodnima spremenljivkama. x 1 x 2 y 0 0 0 y = x 1 · x 2 = x 1 x 2 0 1 0 1 0 0 1 1 1 (a) (b) (c) Slika 1.2 Logi ni izraz (a), logi ni simbol (b) in pravilnostna tabela (c) za konjunkcijo z dvema vhodnima spremenljivkama. 1.3.3 Negacija Negacija (NE, NOT) invertira vhodno logi no spremenljivko. V logi nem izrazu jo ozna ujemo s rto nad vhodno spremenljivko. Slika 1.3 podaja logi ni izraz (a), logi ni simbol (b) in pravilnostno tabelo (c) za negacijo. x y y = x 0 1 1 0 (a) (b) (c) Slika 1.3 Logi ni izraz (a), logi ni simbol (b) in pravilnostna tabela (c) za negacijo. 1.3 Osnovne preklopne funkcije 9 1.3.4 Peircov operator Peircov operator (NE ALI, NOR) predstavlja invertirano (negirano) disjunkcijo. Operator vrne logi no 1, ko so na logi no 0 postavljene vse vhodne spremenljivke. V logi nem izrazu ga ozna ujemo s simbolom ¿. Slika 1.4 podaja logi ni izraz (a), logi ni simbol (b) in pravilnostno tabelo (c) za Peircov operator z dvema vhodnima spremenljivkama. x 1 x 2 y 0 0 1 y = x 1 ¿ x 2 = ( x 1 ‚ x 2) 0 1 0 1 0 0 1 1 0 (a) (b) (c) Slika 1.4 Logi ni izraz (a), logi ni simbol (b) in pravilnostna tabela (c) za Peircov operator z dvema vhodnima spremenljivkama. Opozorilo: asociativnost za Peircov operator ne velja: x 1 ¿ x 2 ¿ x 3 ”= ( x 1 ¿ x 2) ¿ x 3 ”= x 1 ¿ ( x 2 ¿ x 3)! 1.3.5 Shefferjev operator Shefferjev operator (NE IN, NAND) predstavlja invertirano (negirano) konjunkcijo. Operator vrne logi no 0, ko so na logi no 1 postavljene vse vhodne spremenljivke. V logi nem izrazu ga ozna ujemo s simbolom ø. Slika 1.4 podaja logi ni izraz (a), logi ni simbol (b) in pravilnostno tabelo (c) za Shefferjev operator z dvema vhodnima spremenljivkama. x 1 x 2 y 0 0 1 y = x 1 ø x 2 = ( x 1 x 2) 0 1 1 1 0 1 1 1 0 (a) (b) (c) Slika 1.5 Logi ni izraz (a), logi ni simbol (b) in pravilnostna tabela (c) za Shefferjev operator z dvema vhodnima spremenljivkama. Opozorilo: asociativnost za Shefferjev operator ne velja: x 1 ø x 2 ø x 3 ”= ( x 1 ø x 2) ø x 3 ”= x 1 ø ( x 2 ø x 3)! 10 Poglavje 1 Priprava na 1. laboratorijske vaje 1.3.6 Ekskluzivni ali Ekskluzivni ali (XOR, tudi vsota po modulu 2) dveh vhodnih spremenljivk vrne logi no 1, ko logi no vrednost 1 ekskluzivno zavzema ena vhodna spremenljivka. Pri ve vhodnih spremenljivkah funkcija vrne logi no 1, ko je na logi no vrednost 1 postavljenih liho ötevilo vhodnih spremenljivk, kar si lahko interpretiramo tudi kot vsota po modulu 2 (opozorilo: v Logisimu XOR privzeto ne deluje na tak na in – pod lastnostmi XOR vrat moramo nastaviti polje Multiple-Input Behavior na vrednost When an odd number are on). V logi nem izrazu ekskluzivni ALI ozna ujemo s simbolom Ò ali ü. Slika 1.6 podaja logi ni izraz (a), logi ni simbol (b) in pravilnostno tabelo (c) za ekskluzivni ali z dvema vhodnima spremenljivkama. x 1 x 2 y 0 0 0 y = x 1Ò x 2 = x 1 x 2 ‚ x 1 x 2 0 1 1 1 0 1 1 1 0 (a) (b) (c) Slika 1.6 Logi ni izraz (a), logi ni simbol (b) in pravilnostna tabela (c) za ekskluzivni ali z dvema vhodnima spremenljivkama. 1.3.7 Ekvivalenca Ekvivalenca (XNOR) dveh vhodnih spremenljivk vrne logi no 1, ko sta vhoda enaka in je tako enaka negiranemu ekskluzivnemu ali. Enakost pa ne velja za ve vhodnih spremenljivk. V logi nem izrazu ekvivalenco ozna ujemo s simbolom ©. Slika 1.7 podaja logi ni izraz (a), logi ni simbol (b) in pravilnostno tabelo (c) za ekvivalenco z dvema vhodnima spremenljivkama. x 1 x 2 y 0 0 1 y = x 1 © x 2 = x 1 x 2 ‚ x 1 x 2 0 1 0 1 0 0 1 1 1 (a) (b) (c) Slika 1.7 Logi ni izraz (a), logi ni simbol (b) in pravilnostna tabela (c) za ekvivalenco z dvema vhodnima spremenljivkama. 1.4 Analiti no reöevanje preklopnih funkcij 11 1.3.8 Implikacija Implikacija (IMP) dveh vhodnih spremenljivk, tj. x 1 æ x 2 vrne logi no 0 le v primeru, da je operand na levi strani (tj. x 1) enak 1, operator na desni strani (tj. x 2) pa enak 0. Implikacija nima elektronske implementacije znotraj druûine 7400. Prav tako operator nima logi nega simbola. Slika 1.8 podaja logi ni izraz (a), in pravilnostno tabelo (b) za implikacijo. x 1 x 2 y 0 0 1 y = x 1 æ x 2 = x 1 ‚ x 2 0 1 1 1 0 0 1 1 1 (a) (b) Slika 1.8 Logi ni izraz (a) in pravilnostna tabela (b) za implikacijo. Opozorilo: komutativnost za implikacijo ali ne velja: x 1 æ x 2 ”= x 2 æ x 1! 1.4 Analiti no reöevanje preklopnih funkcij Pri analiti nemu reöevanju preklopnih funkcij preko postulatov in lastnosti Boolove algebre funkcijo podano z logi nim izrazom preoblikujemo v ûeleno obliko. Kadar ûelimo dolo eno lastnost formalno dokazati, se moramo pri spreminjanju oblike analiti nega izraza striktno drûati postulatov Boolove algebre, pri emer uporabimo le en postulat naenkrat, pri vsakem koraku izpeljave pa pripiöemo postulat, ki smo ga uporabili. Zgled 1 Z uporabo postulatov dokaûi enakost x ‚ x = x! Reöitev 1 x ‚ x = ( x ‚ x) · 1 ( P 2ú) =( x ‚ x) · ( x ‚ x) ( P 5) = x ‚ ( x · x) ( P 4ú) = x ‚ 0 ( P 5ú) = x ( P 2) Navadno pri poenostavljanju izrazov korake izpuö amo in nad izrazom neposredno uporabljamo lastnosti, ki sledijo iz postulatov. e naloga od nas eksplicitno ne zahteva uporabe postulatov, jo reöujemo na tak na in. Ker so postulati in lastnosti 12 Poglavje 1 Priprava na 1. laboratorijske vaje definirani nad osnovnimi logi nimi operatorji (konjunkcija, disjunkcija in negacija), vse funkcije v izrazu najprej izrazimo s temi. 1 2 Zgled 2 Poenostavi izraz x 2 æ ( x 1 ‚ x 3) ( x 1 ‚ x 3) ! Reöitev 2 x 2 æ ( x 1 ‚ x 3) ( x 1 ‚ x 3) = x 2 ‚ ( x 1 ‚ x 3) ( x 1 ‚ x 3) = x 2 ‚ ( x 1 ‚ x 3) ‚ ( x 1 ‚ x 3) = x 2 ‚ x 1 x 3 ‚ x 1 x 3 = x 2 ‚ ( x 1 ‚ x 1) x 3 = x 2 ‚ x 3 2 Priprava na 2. laboratorijske vaje 2.1 Zapis preklopnih funkcij Analiti ni zapis podajamo z logi nim izrazom oziroma logi no ena bo. Pogosto se uporabljajo tri posebne oblike analiti nega zapisa, in sicer normalna, popolna in minimalna. Preklopna funkcija je podana v normalni obliki, e je sestavljena iz najve dveh nivojev logi nih operatorjev. Oblika je popolna, e na prvem nivoju logi nih operatorjev v vseh izrazih nastopajo vse vhodne spremenljivke. Minimalna oblika je najkrajöa moûna oblika zapisa preklopne funkcije. 2.2 Analiti ni zapis in popolne normalne oblike zapisa pre- klopnih funkcij Pogledali si bomo popolno disjunktivno normalno obliko (PDNO) in popolno konjunktivno normalno obliko (PKNO) zapisa preklopne funkcije. 2.2.1 Popolna disjunktivna normalna oblika (PDNO) • Disjunktivna: operator 2. nivoja je disjunkcija (‚). • f( x 1 , x 2 , ..., x ) = ) n ‚2 n≠1 i=0 mif ( ˛ wi • f( ˛ w ) ... vrednost funkcije pri i i-tem vhodnem vektorju (vrstici) • minterm je konjunktiven izraz - vse vhodne spremenljivke so povezane preko konjunkcije • m ... minterm = i i; mi xw 1 ,i 1 · xw 2 ,i 2 · ... · xwn,i n ; i = 0 , 1 , 2 , ..., 2 n ≠ 1 I x,w = 1 • xw = x, w = 0 • w ... j,i j-ti bit binarnega zapisa ötevila i • PDNO lahko zapiöemo v krajöi obliki kot f( x 1 , x 2 , ..., x ) = ), n ‚ n( i 1 , i 2 , ..., ik kjer i 1 , i 2 , ..., i dolo ajo indekse mintermov, ki nastopajo v PDNO. k 13 14 Poglavje 2 Priprava na 2. laboratorijske vaje Recept: pri dolo anju PDNO disjunktivno veûemo tiste minterme, pri katerih je funkcijska vrednost 1. Pri tem se i-ti minterm nanaöa na funkcijsko vrednost f( ˛w ) i (glej tabelo 2.1). x 1 x 2 x 3 f( x 1, x 2, x 3) minterm 0 0 0 f ( ˛ w 0) m 0 0 0 1 f ( ˛ w 1) m 1 0 1 0 f ( ˛ w 2) m 2 0 1 1 f ( ˛ w 3) m 3 1 0 0 f ( ˛ w 4) m 4 1 0 1 f ( ˛ w 5) m 5 1 1 0 f ( ˛ w 6) m 6 1 1 1 f ( ˛ w 7) m 7 Tabela 2.1 Primer pravilnostne tabele in zaporedja mintermov za preklopno funkcijo treh vhodnih spremenljivk. Zgled 3 Zapiöi minterm 9, pri 4-ih vhodnih spremenljivkah: Reöitev 3 Velja torej: • n = 4 , • i = 9[10] = 1001[2] , • m 9 = x 11 x 02 x 03 x 14 = x 1 x 2 x 3 x 4 . 2.2.2 Popolna konjunktivna normalna oblika (PKNO) • Konjunktivna: operator 2. nivoja je konjunkcija (&). • f( x 1 , x 2 , ..., x ) = &2 n≠1 )) n i=0 ( M 2 n≠1≠ i ‚ f( ˛wi • maksterm je disjunktiven izraz - vhodne spremenljivke so povezane preko disjunkcije • M 2 n ... maksterm 2 n = ≠1≠ i ≠ 1 ≠ i; M 2 n≠1≠ i xw 1 ,i 1 ‚ xw 2 ,i 2 ‚ ... ‚ xwn,i n ; i = 0 , 1 , 2 , ..., 2 n ≠ 1 • PKNO lahko zapiöemo v krajöi obliki: f( x 1 , x 2 , ..., x ) = & n( n im, im≠1 , ..., i 1), kjer im, im≠1 , ..., i 1 dolo ajo indekse makstermov, ki nastopajo v PKNO. Recept: pri dolo anju PKNO konjunktivno veûemo tiste maksterme, pri katerih je funkcijska vrednost 0. Pri tem se (2 n ≠ 1 ≠ i)-ti maksterm nanaöa na funkcijsko vrednost f( ˛w ) (glej tabelo 2.2). i 2.2 Analiti ni zapis in popolne normalne oblike zapisa preklopnih funkcij 15 x 1 x 2 x 3 f( x 1, x 2, x 3) maksterm 0 0 0 f ( ˛ w 0) M 7 0 0 1 f ( ˛ w 1) M 6 0 1 0 f ( ˛ w 2) M 5 0 1 1 f ( ˛ w 3) M 4 1 0 0 f ( ˛ w 4) M 3 1 0 1 f ( ˛ w 5) M 2 1 1 0 f ( ˛ w 6) M 1 1 1 1 f ( ˛ w 7) M 0 Tabela 2.2 Primer pravilnostne tabele in zaporedja makstermov za preklopno funkcijo treh vhodnih spremenljivk. Zgled 4 Zapiöi maksterm 9 pri 4-ih vhodnih spremenljivkah. Reöitev 4 Velja torej: • n = 4 , • 2 n ≠ 1 ≠ i = 15 ≠ 9 = 6 , • 2 n ≠ 1 ≠ i = 6[10] = 0110[2] , • M 9 = x 01 ‚ x 12 ‚ x 13 ‚ x 04 = x 1 ‚ x 2 ‚ x 3 ‚ x 4 . Zgled 5 Podano funkcijo pretvori v popolno disjunktivno normalno obliko na dva na ina: • s pomo jo pravilnostne tabele, • analiti no z razöiritvijo. Reöitev 5 Funkcija: f ( x 1 , x 2 , x 3) = x 1 ‚ x 1 x 2 ‚ x 2 x 3 je ûe zapisana v disjunktivni normalni obliki, ki pa ni popolna. Pretvorba s pomo jo pravilnostne tabele Zapiöimo pravilnostno tabelo, s pomo jo katere lahko zapiöemo PDNO, tako da prepiöemo tiste minterme, pri katerih je vrednost funkcije enaka 1. e izpiöemo samo indekse teh mintermov, dobimo skrajöano obliko PDNO: f ( x 1 , x 2 , x 3) = ‚3(0 , 4 , 5 , 6 , 7) . 16 Poglavje 2 Priprava na 2. laboratorijske vaje x 1 x 2 x 3 f( x 1, x 2, x 3) minterm maksterm 0 0 0 1 m 0 M 7 0 0 1 0 m 1 M 6 0 1 0 0 m 2 M 5 0 1 1 0 m 3 M 4 1 0 0 1 m 4 M 3 1 0 1 1 m 5 M 2 1 1 0 1 m 6 M 1 1 1 1 1 m 7 M 0 Tabela 2.3 Pravilnostna tabela funkcije f( x 1 , x 2 , x 3) = x 1 ‚ x 1 x 2 ‚ x 2 x 3. Zapiöimo PDNO öe v eksplicitni obliki: f ( x 1 , x 2 , x 3) = x 1 x 2 x 3 ‚ x 1 x 2 x 3 ‚ x 1 x 2 x 3 ‚ x 1 x 2 x 3 ‚ x 1 x 2 x 3 . Analiti na pretvorba z razöiritvijo Funkcijo razöirimo v popolno (na prvem nivoju morajo nastopati vse vhodne spre- menljivke): x 1 ‚ x 1 x 2 ‚ x 2 x 3 = x 1( x 2 ‚ x 2)( x 3 ‚ x 3) ‚ x 1 x 2( x 3 ‚ x 3) ‚ ( x 1 ‚ x 1) x 2 x 3 = x 1 x 2 x 3 ‚ x 1 x 2 x 3 ‚ x 1 x 2 x 3 ‚ x 1 x 2 x 3 ‚ x 1 x 2 x 3 ‚ x 1 x 2 x 3 ‚ x 1 x 2 x 3 ‚ x 1 x 2 x 3 = x 1 x 2 x 3 ‚ x 1 x 2 x 3 ‚ x 1 x 2 x 3 ‚ x 1 x 2 x 3 ‚ x 1 x 2 x 3 = ‚3 (7 , 6 , 5 , 4 , 0) = ‚3 (0 , 4 , 5 , 6 , 7) 2.2.3 Relaciji med makstermi in mintermi Med mintermi in makstermi zaradi DeMorganovega pravila veljata slede i relaciji: • m = i M 2 n≠1≠ i, • M = i m 2 n≠1≠ i. Relaciji lahko uporabimo pri pretvarjanju funkcije iz PDNO v PKNO in obratno. Pri podanem zapisu najprej pogledamo kateri termi manjkajo: • e je funkcija podana v PDNO, izpiöemo manjkajo e minterme - v pravilnostni tabeli so soleûni z enicami. • e je funkcija podana v PKNO, izpiöemo manjkajo e maksterme - v pravil- nostni tabeli so soleûni z ni lami. 2.2 Analiti ni zapis in popolne normalne oblike zapisa preklopnih funkcij 17 S tem smo dobili pozicije termov, ki nastopajo v iskani obliki zapisa preklopne funkcije. Indekse iskanih termov dobimo tako, da nad izpisanimi mintermi oziroma makstermi uporabimo zgoraj navedeni relaciji. 2.2.4 Pretvarjanje med PDNO in PKNO Dva moûna na ina reöevanja: 1. zapiöemo pravilnostno tabelo in iz nje razberemo reöitev, 2. z upoötevanjem relacij med mintermi in makstermi. Zgled 6 Funkcijo podano v PDNO pretvori v PKNO: • s pomo jo pravilnostne tabele, • z upoötevanjem relacij med mintermi in makstermi. Reöitev 6 Demonstrirajmo oba na ina pretvorbe. Pretvorba iz PDNO v PKNO: s pomo jo pravilnostne tabele Glej tabelo v prejönjem zgledu! Prepiöemo maksterme, pri katerih je vrednost funkcije enaka 0. PKNO: &3(6 , 5 , 4) Eksplicitna PKNO: PKNO: ( x 1 ‚ x 2 ‚ x 3)( x 1 ‚ x 2 ‚ x 3)( x 1 ‚ x 2 ‚ x 3) . Pretvorba iz PDNO v PKNO: z upoötevanjem relacij med mintermi in makstermi Pretvorimo ‚3(0 , 4 , 5 , 6 , 7) v PKNO: 1. zapiöemo manjkajo e minterme: m 1 , m 2 , m 3 . 2. izra unamo indekse makstermov: M 6 , M 5 , M 4 . 3. reöitev: &3(6 , 5 , 4) . Na podoben na in, bi lahko pretvarjali tudi iz PKNO v PDNO. 3 Priprava na 3. laboratorijske vaje 3.1 Zapis preklopnih funkcij z Veitchevim diagramom Veitchevi diagrami igrajo pomembno vlogo pri minimizaciji preklopnih funkcij. Veitchev diagram pri n vhodnih spremenljivkah je sestavljen iz 2 n polj, pri emer posamezno polje vsebuje funkcijsko vrednost pri posameznem mintermu. Postopek zapisovanja Veitchevega diagrama je razmeroma preprost, in sicer izhajamo iz diagrama za eno spremenljivko (glej sliko 3.1(a)). Diagram za dve spremenljivki dobimo tako, da podvojimo diagram za eno spremenljivko. Ozna iti je potrebno tudi pokritja, in sicer tako, da posamezna spremenljivka pokriva polovico Veitchevega diagrama. Pokritja lahko izbiramo na razli ne na ine. V sploönem dobimo diagram za n spremenljivk tako, da podvojimo diagram za n ≠ 1 spremenljivk in na novo dodani del pokrijemo z dodano spremenljivko. x x 1 1 x x m m x m m m m 2 3 1 2 6 7 3 2 m m m m m m 1 0 m m 2 0 4 5 1 0 x3 (a) (b) (c) x x x 1 1 1 m m m m m m m m m m m m 12 14 x 6 4 25 29 x 13 9 24 28 12 8 2 2 m m m m m m m m m m m m 13 15 7 5 x 27 31 15 11 26 30 14 10 x 4 4 m m m m m m m m m m m m 9 11 3 1 19 23 7 3 18 22 6 2 m m m m m m m m m m m m 8 10 2 0 17 21 5 1 16 20 4 0 x x x 3 3 3 x5 (d) (e) Slika 3.1 Slika (a) prikazuje Veitchev diagram za eno vhodno spremenljivko, slika (b) za dve, slika (c) za tri, slika (d) za ötiri, slika (e) pa za pet. 19 20 Poglavje 3 Priprava na 3. laboratorijske vaje Zgled 7 Funkcijo f( x 1 , x 2 , x 3 , x 4) = ‚4(5 , 7 , 9 , 11 , 13 , 15) zapiöi v Veitchev diagram. Reöitev 7 V polja, ki se nanaöajo na minterme, pri katerih je funkcijska vrednost enaka 1, vpiöemo enice, ostala polja pa pustimo prazna (glej sliko 3.2). x1 x2 1 1 1 1 x4 1 1 x3 Slika 3.2 Veitchev diagram funkcije f( x 1 , x 2 , x 3 , x 4) = ‚4(5 , 7 , 9 , 11 , 13 , 15). 3.2 Funkcijsko poln sistem Funkcijsko poln sistem je nabor logi nih funkcij, s katerimi lahko izrazimo katerokoli logi no funkcijo. Iz definicije Boolove algebre sledi, da je {‚ , · , ¬} funkcijsko poln sistem (operator ¬ predstavlja negacijo). Funkcijsko polnost ugotavljamo na dva na ina: • s pretvorbo na nek znan funkcijsko poln sistem, • s preverjanjem pripadnosti osnovnim zaprtim razredom. Zgled 8 S pretvorbo na negacijo, konjunkcijo in disjunkcijo pokaûi, da je Shefferjev operator funkcijsko poln sistem. Reöitev 8 S Shefferjevim operatorjem izrazimo negacijo. x = xx = x ø x S Shefferjevim operatorjem izrazimo konjunkcijo. x 1 x 2 = x 1 x 2 = x 1 ø x 2 = ( x 1 ø x 2) ø ( x 1 ø x 2) S Shefferjevim operatorjem izrazimo disjunkcijo. x 1 ‚ x 2 = x 1 ‚ x 2 = x 1 x 2 = ( x 1 ø x 1) ø ( x 2 ø x 2) Podobno bi se dalo pokazati za Peircov operator. 4 Priprava na 4. laboratorijske vaje 4.1 Zaprti razredi in preverjanje funkcijske polnosti sis- tema Funkcijo polnost nabora logi nih funkcij lahko preverjamo s pripadnostjo nabora osnovnim zaprtim razredom logi nih funkcij (Postov teorem). Osnovni zaprti razredi so slede i: • T 0 – razred preklopnih funkcij, ki ohranjajo ni lo ( f(0 , 0 , . . . , 0) = 0) • T 1 – razred preklopnih funkcij, ki ohranjajo enico ( f(1 , 1 , . . . , 1) = 1) • S – razred sebidualnih funkcij ( f( x 1 , x 2 , . . . , x ) = )) n f ( x 1 , x 2 , . . . , xn • L – razred linearnih funkcij ( f( x 1 , x 2 , ..., x ) ) = n œ L, f( x 1 , x 2 , ..., xn = a 0Ò a 1 x 2Ò ... Ò a ) nxn • M – razred monotonih funkcij ( f( x 1 , x 2 , ..., x ) n œ M, ’ i, j : ˛ w ) )) i < ˛ wj æ f( ˛ wi Æ f( ˛ wj e nabor odpira vse osnovne razrede, je poln. Nabor odpira nek osnovni razred, e vsaj ena izmed funkcij v podanem naboru ne pripada izbranemu razredu. Zgled 9 S pomo jo zaprtih razredov preveri funkcijsko polnost nabora {‚ , æ , 1} . Reöitev 9 Cilj: Pri vsakem osnovnem razredu ûelimo najti vsaj eno funkcijo iz podanega nabora, ki temu razredu ne pripada. 1. Razred T 0 : • ‚ : f(0 , 0) = 0 ‚ 0 = 0 ; pripada razredu. • 1 : 1 ”= 0 ; ne pripada razredu. 2. Razred T 1 : • ‚ : f(1 , 1) = 1 ‚ 1 = 1 ; pripada razredu. 21 22 Poglavje 4 Priprava na 4. laboratorijske vaje • æ: f(1 , 1) = 1 æ 1 = 1 ; pripada razredu. • 1 : 1 = 1 ; pripada razredu Nabor {‚ , æ , 1} ne odpira razreda T 1 , torej nabor ni poln. Vseeno nadaljujmo s postopkom. 3. Razred S: Pripadnost lahko dokazujemo na dva na ina: • analiti no: ali velja f( x 1 , x 2 , ..., x ) = ) , n f ( x 1 , x 2 , ..., xn • tabelari no: ali velja f( ˛ w ) ) . i ”= f( ˛ w 2 n≠1≠ i Postopek: • 1 : (analiti no) 1 = 1 0 = 1 protislovje Funkcija ne pripada razredu S. Vseeno nadaljujmo. • ‚ : (analiti no) f ( x 1 , x 2) = f( x 1 , x 2) x 1 ‚ x 2 = x 1 ‚ x 2 (desno stran dopolnimo do PDNO) x 1 x 2 = x 1( x 2 ‚ x 2) ‚ x 2( x 1 ‚ x 1) x 1 x 2 = x 1 x 2 ‚ x 1 x 2 ‚ x 1 x 2 ‚ x 1 x 2 x 1 x 2 = x 1 x 2 ‚ x 1 x 2 ‚ x 1 x 2 ‚2(3) ”= ‚2(1 , 2 , 3) æ ‚ / œ S • æ: (tabelari no) x 1 x 2 x 1 æ x 2 0 0 1 0 1 1 1 0 0 1 1 1 f ( w 0) = f( w 3) – funkcija ne pripada S. 4.1 Zaprti razredi in preverjanje funkcijske polnosti sistema 23 4. Razred L : Funkcija f( x 1 , x 2 , . . . , x ) spada v razred linearnih funkcij, e jo lahko zapi-n öemo kot f ( x 1 , x 2 , . . . , x ) = n a 0Ò a 1 x 1Ò a 2 x 2Ò · · · Ò anxn. Pripadnost lahko preverjamo: • analiti no, • z Veitchevim diagramom. Analiti no preverjanje: • predpostavimo, da funkcija f( x 1 , x 2 , . . . , x ) spada v razred linearnih n funkcij, • dolo imo koeficiente a 0 , a 1 , · · · , a , n • preverimo, e se dobljena funkcija a 0Ò a 1 x 1Ò a 2 x 2Ò · · · Ò a ujema s nxn podano funkcijo f( x 1 , x 2 , . . . , x ) . n Postopek: • ‚ : Predpostavimo, da je disjunkcija linearna funkcija, tedaj jo lahko zapi- öemo kot: f ( x 1 , x 2) = L x 1 ‚ x 2 = a 0Ò a 1 x 1Ò a 2 x 2 f (0 , 0) = L a 0Ò a 10Ò a 20 = a 0 = 0Ò0 = 0 ( a 0 = 0) f (0 , 1) = 0 L Ò a 10Ò a 21 = a 2 = 0Ò1 = 1 ( a 2 = 1) f (1 , 0) = 0 L Ò a 11Ò a 20 = a 1 = 1Ò0 = 1 ( a 1 = 1) f ( x 1 , x 2) = 0 L Ò1 x 1Ò1 x 2 = x 1Ò x 2 Preverimo za vse preostale vhodne vektorje (v primeru protislovja posto- pek ustavimo): f (1 , 1) = 1 ‚ 1 = 1 f (1 , 1) = L x 1Ò x 2 = 1Ò1 = 0 Protislovje. Funkcija ne pripada razredu. Preverjanje z Veitchevim diagramom: • Preklopna funkcija spada v razred L, e pri primerjavi pokritij velja popolna enakost ali popolna razli nost vrednosti funkcije. 24 Poglavje 4 Priprava na 4. laboratorijske vaje Postopek: • ‚ : Preverimo pokritja: – x 1 x 2 : x 1 x 2 (popolnoma razli na), – x 1 : x 1 (niti popolnoma razli na niti popolnoma enaka). Funkcija ne pripada razredu. 5. Razred M: Funkcija pripada M, e pri vseh vhodnih vektorjih velja, da je pri manjöem vektorju vrednost funkcije manjöa ali enaka vrednosti pri ve jem vektorju. Relacija je manjöi je definirana na slede i na in: • Za vhodna vektorja w in velja , e za vsako mesto i wj wi < wj k velja w . Primer: (1 k,i Æ wk,j , 0 , 0 , 1 , 0 , 1 , 0 , 0) < (1 , 1 , 0 , 1 , 0 , 1 , 0 , 1) . Pri preverjanju pripadnosti je dovolj, da preverimo le sosedne vhodne vektorje. Vhodna vektorja sta sosedna, e se razlikujeta le na enem mestu. Primer: (1 , 0 , 0 , 1 , 0) in (1 , 0 , 1 , 1 , 0) . Postopek: • æ: x 1 x 2 x 1 æ x 2 0 0 1 0 1 1 1 0 0 1 1 1 Preverjamo samo sosedne vektorje. Sosedni vhodni vektorji so ( w 0 , w 1) , ( w 0 , w 2) , ( w 1 , w 3) in ( w 2 , w 3) . Hitro najdemo protislovje, in sicer w 0 < w 2 , f( w 0) > f( w 2) . Funkcija torej ne pripada M. Zgled 10 Analiti no preveri ali preklopna funkcija f( x 1 , x 2 , x 3 , x 4) = &4(0 , 1 , 6 , 8 , 9 , 14) pripada razredu linearnih funkcij. 4.1 Zaprti razredi in preverjanje funkcijske polnosti sistema 25 x 1 x 2 x 3 x 4 f( x 1 , x 2 , x 3 , x 4) f( x 1 , x 2 , x 3 , x 4) L 0 0 0 0 1 1 0 0 0 1 0 0 0 0 1 0 1 1 0 0 1 1 1 0 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 0 0 1 0 1 1 1 0 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 0 0 1 1 1 1 0 1 1 0 1 1 1 0 0 1 1 1 1 1 0 0 Reöitev 10 Postopek: Predpostavimo, da dana funkcija pripada razredu linearnih funkcij, tedaj jo lahko zapiöemo kot: f ( x 1 , x 2 , x 3 , x 4) = L a 0Ò a 1 x 1Ò a 2 x 2Ò a 3 x 3Ò a 4 x 4 f (0 , 0 , 0 , 0) = L a 0Ò a 10Ò a 20Ò a 30Ò a 40 = 1 ( a 0 = 1) f (0 , 0 , 0 , 1) = 1 L Ò a 10Ò a 20Ò a 30Ò a 41 = 1Ò a 4 = 0 ( a 4 = 1) f (0 , 0 , 1 , 0) = 1 L Ò a 10Ò a 20Ò a 31Ò a 40 = 1Ò a 3 = 1 ( a 3 = 0) f (0 , 1 , 0 , 0) = 1 L Ò a 10Ò a 21Ò a 30Ò a 40 = 1Ò a 2 = 1 ( a 2 = 0) f (1 , 0 , 0 , 0) = 1 L Ò a 11Ò a 20Ò a 30Ò a 40 = 1Ò a 1 = 1 ( a 1 = 0) f ( x 1 , x 2 , x 3 , x 4) = 1 L Ò0 x 1Ò0 x 2Ò0 x 3Ò1 x 4 = 1Ò x 4 = x 4 Preverimo za vse preostale vhodne vektorje (v primeru protislovja postopek usta- vimo): f (0 , 0 , 1 , 1) = 1 f (0 , 0 , 1 , 1) = 1 L Ò1 = 0 Protislovje. Funkcija ne pripada razredu. 5 Priprava na 5. laboratorijske vaje 5.1 Minimalne oblike zapisa preklopnih funkcij Minimalna oblika zapisa preklopne funkcije podaja najkrajöi moûen zapis te funkcije. Poznamo ve minimalnih oblik zapisa. Pogledali si bomo slede e: • minimalna disjunktivna normalna oblika (MDNO): dolo a najkraöo disjunk- tivno normalno obliko zapisa preklopne funkcije, • minimalna konjunktivna normalna oblika (MKNO): dolo a najkraöo konjunk- tivno normalno obliko zapisa preklopne funkcije, • minimalna normalna oblika (MNO): dolo a nakrajöo normalno obliko zapisa preklopne funkcije. Pri dolo anju minimalne disjunktivne normalne oblike (MDNO) izhajamo iz iska- nja glavnih vsebovalnikov. Glavni vsebovalnik predstavlja najkrajöi konjunktivni izraz, ki je skupen podmnoûici mintermov, ki sestavljajo PDNO podane funkcije. Najmanjöa mnoûica glavnih vsebovalnikov, ki skupaj pokrijejo celotno mnoûico mintermov v PDNO, predstavlja minimalno disjunktivno normalno obliko. Pri dolo anju minimalne konjunktivne normalne oblike (MKNO) izhajamo iz dolo- anja MDNO negirane funkcije, ki jo z uporabo DeMorganovega pravila pripeljemo do konjunktivne oblike. Pri dolo anju minimalne normalne oblike (MNO) upoötevamo dejstvo, da MNO predstavlja krajöo izmed MDNO in MKNO. Glavne vsebovalnike iö emo na podlagi sosednosti med konjunktivni izrazi. Dva konjunktivna izraza sta sosedna, e se razlikujeta po natanko eni negaciji: • izraza xw 1 1 · xw 2 2 · ... · xwi in sta sosedna, i · ... · xwn n xw 1 1 · xw 2 2 · ... · xwi i · ... · xwn n ker se razlikujeta le po negaciji nad vhodno spremenljivko z indeksom i. V sploönem velja, da ima izraz, ki vsebuje n vhodnih spremenljivk, n sosednih izrazov. 27 28 Poglavje 5 Priprava na 5. laboratorijske vaje Zgled 11 Zapiöi vse izraze, ki so sosedni izrazu x 1 x 2 x 4 . Reöitev 11 V sosednih izrazih nastopajo enake spremenljivke kot v izhodiö nem izrazu. Od izhodiö nega izraza se sosedni razlikujejo po natanko eni negaciji. Sosedni izrazi so torej: • x 1 x 2 x 4 , • x 1 x 2 x 4 in • x 1 x 2 x 4 . Glavni vsebovalnik dveh sosednih izrazov dolo imo z upoötevanjem lastnosti, da je disjunkcija dveh termov, ki se razlikujeta natanko po negaciji nad eno spremenljivko, neodvisna od vrednosti te spremenljivke. Glavni vsebovalnik dveh sosednih izrazov xw 1 1 · xw 2 2 · ... · xwi≠1 in i≠1 · xwi i · xwi+1 i+1 · ... · xwn n xw 1 1 · xw 2 2 · ... · xwi≠1 i≠1 · xwi i · xwi+1 i+1 · ... · xwn n je torej izraz xw 1 1 · xw 2 2 · ... · xwi≠1 . i≠1 · xwi+1 i+1 · ... · xwn n Zgled 12 Dolo i glavni vsebovalnik izrazov x 1 x 2 x 3 x 4 in x 1 x 2 x 3 x 4 . Reöitev 12 Izraza se razlikujeta le po negaciji nad spremenljivko x 1 . Disjunkcija med izrazoma je torej neodvisna od vrednosti te spremenljivke, zato je njun glavni vsebovalnik x 2 x 3 x 4 . 5.2 Veitchev postopek minimizacije Veitchev postopek minimizacije izkoriö a lastnosti Veitchevega diagrama. Sosednost mintermov je namre neposredno povezana s sosednostjo celic v diagramu. Pri celicah, ki se nahajajo na robovih diagrama se sosednost prenaöa na zrcalno stran (glej sliko 5.1). Zgled 13 V Veitchevem diagramu za 4 spremenljivke ozna i izraze, ki so sosednji izrazu m 14 ‚ m 15 . Reöitev 13 Izraz zapiöimo v razöirjeni obliki: m 14 ‚ m 15 = x 1 x 2 x 3 x 4 ‚ x 1 x 2 x 3 x 4 = x 1 x 2 x 3 Sosedni izrazi so torej: • x 1 x 2 x 3 = x 1 x 2 x 3 x 4 ‚ x 1 x 2 x 3 x 4 = m 6 ‚ m 7 5.2 Veitchev postopek minimizacije 29 x1 x x2 1 x x2 x3 (a) (b) (c) x1 x2 x4 x3 (d) (e) Slika 5.1 Slika (a) prikazuje sosednost v Veitchevem diagramu za 1 vhodno spremenljivko, slika (b) za 2, slika (c) za 3, slika (d) za 4, slika (e) pa za 5. • x 1 x 2 x 3 = x 1 x 2 x 3 x 4 ‚ x 1 x 2 x 3 x 4 = m 12 ‚ m 13 • x 1 x 2 x 3 = x 1 x 2 x 3 x 4 ‚ x 1 x 2 x 3 x 4 = m 10 ‚ m 11 Veitchev diagram z ozna emi sosednimi izrazi prikazuje slika 5.2. x1 x2 x4 x3 Slika 5.2 Izrazi, ki so sosedni izrazu m 14 ‚ m 15. Zgled 14 V Veitchevem diagramu za 5 spremenljivk ozna i izraze, ki so sosednji izrazu m 22 ‚ m 30 . Reöitev 14 Izraz zapiöimo v razöirjeni obliki: m 22 ‚ m 30 = x 1 x 2 x 3 x 4 x 5 ‚ x 1 x 2 x 3 x 4 x 5 = x 1 x 3 x 4 x 5 Sosedni izrazi so torej: 30 Poglavje 5 Priprava na 5. laboratorijske vaje • x 1 x 3 x 4 x 5 • x 1 x 3 x 4 x 5 • x 1 x 3 x 4 x 5 • x 1 x 3 x 4 x 5 Veitchev diagram z ozna emi sosednimi izrazi prikazuje slika 5.3. x x 1 1 x2 x4 x x 3 3 x5 Slika 5.3 Izrazi, ki so sosedni izrazu m 22 ‚ m 30. 5.2.1 Dolo anje minimalne normalne oblike z Veitchevim diagramom Za minimalno normalno obliko (MNO) velja, da predstavlja krajöo izmed minimalne disjunktivne normalne oblike (MDNO) in minimalne konjunktivne normalne oblike (MKNO). Za dolo itev MNO moramo torej najprej dolo iti MDNO in MKNO. Dolo anje minimalne disjunktivne normalne oblike z Veitchevim diagramom Postopek dolo anja je slede : 1. Funkcijo predstavimo z Veitchevim diagramom. 2. Poiö emo glavne vsebovalnike, tako da med seboj zdruûujemo im ve je ötevilo sosednih mintermov, pri katerih je funkcijska vrednost enaka 1. Zdruûujemo lahko 1,2,4,8,16,... mintermov. Iö emo najmanjöi nabor pokritij, s katerim pokrijemo vse enice. V vsakem koraku poskuöamo dobiti im ve je pokritje, saj s tem izlo imo ve je ötevilo vhodnih spremenljivk. 3. Zapiöemo MDNO na podlagi glavnih vsebovalnikov. 5.2 Veitchev postopek minimizacije 31 Dolo anje minimalne konjunktivne normalne oblike z Veitchevim diagramom 1. Negirano funkcijo predstavimo z Veitchevim diagramom. 2. Poiö emo MDNO negirane funkcije. 3. Negiramo MDNO negirane funkcije, s imer dobimo izhodiö no funkcijo. 4. Z upoötevanjem DeMorganovega pravila funkcijo prevedemo v MKNO. Dolo anje minimalne normalne oblike 1. Dolo imo ötevilo operatorjev (logi nih vrat) in operandov (vhodov) za MDNO in za MKNO posebej. Negacij ne ötejemo. 2. Minimalna oblika je tista, ki ima manjöe ötevilo operatorjev. e je öte- vilo operatorjev pri obeh enako, je minimalna tista, ki ima manjöe ötevilo operandov. Zgled 15 Za funkcijo f( x 1 , x 2 , x 3 , x 4) = ‚4(0 , 4 , 8 , 9 , 10 , 11 , 12) dolo i minimalno normalno obliko. Reöitev 15 Najprej dolo imo MDNO: 1. Nariöemo Veitchev diagram funkcije in ozna imo glavne vsebovalnike (Slika 5.4). x1 1 1 x2 x4 1 1 1 1 1 x3 Slika 5.4 Glavni vsebovalniki funkcije ‚4(0 , 4 , 8 , 9 , 10 , 11 , 12). 2. Izpiöemo glavne vsebovalnike in s tem MDNO: f ( x 1 , x 2 , x 3 , x 4) = x 1 x 2 ‚ x 3 x 4 Potem dolo imo MKNO: 32 Poglavje 5 Priprava na 5. laboratorijske vaje x x x x 1 1 1 1 1 1 1 1 1 1 1 1 x x x x 2 2 2 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 x x x x 4 4 4 4 1 1 1 1 1 1 1 1 1 1 1 1 x x x x 3 3 3 3 (a) (b) (c) (d) Slika 5.5 Glavni vsebovalniki funkcije ‚4(1 , 2 , 3 , 5 , 6 , 7 , 13 , 14 , 15). Slika (a) prikazuje glavni vsebovalnik x 1 x 3, slika (b) x 2 x 3, slika (c) x 1 x 4, slika (d) pa x 2 x 4. 1. Nariöemo Veitchev diagram negirane funkcije f( x 1 , x 2 , x 3 , x 4) = ‚4(1 , 2 , 3 , 5 , 6 , 7 , 13 , 14 , 15) in ozna imo glavne vsebovalnike (Slika 5.5). 2. Izpiöemo glavne vsebovalnike, ki dolo ajo negirano funkcijo: f( x 1 , x 2 , x 3 , x 4) = x 1 x 3 ‚ x 2 x 3 ‚ x 1 x 4 ‚ x 2 x 4 . S tem dobimo MDNO negirane funkcije. 3. Dobljeno MDNO negiramo, uporabimo DeMorganovo pravilo in dobimo MKNO: f( x 1 , x 2 , x 3 , x 4) = x 1 x 3 ‚ x 2 x 3 ‚ x 1 x 4 ‚ x 2 x 4 = ( x 1‚ x 3)( x 2‚ x 3)( x 1‚ x 4)( x 2 ‚ x 4) . Sedaj lahko dolo imo MNO: 1. Dolo imo ötevilo operatorjev pri MDNO (za realizacijo potrebujemo dvoja AND vrata in ena OR vrata): 2 + 1 = 3 . 2. Dolo imo ötevilo operandov pri MDNO (2 vhoda v prva AND vrata, 2 vhoda v druga AND vrata, 2 vhoda v OR vrata): 2 + 2 + 2 = 6 . 3. Zapiöemo par ötevilo operatorjev/ötevilo operandov za MDNO: [3 , 6] . 4. Dolo imo ötevilo operatorjev pri MKNO (za realizacijo potrebujemo ena AND vrata in ötiri OR vrata): 1 + 4 = 5 . 5. Dolo imo ötevilo operandov pri MKNO (AND vrata so 4-vhodna, vsa OR vrata pa 2-vhodna): 4 + 4 · 2 = 12 . 6. Zapiöemo par ötevilo operatorjev/ötevilo operandov za MKNO: [5 , 12] . 7. Para leksikografsko primerjam med seboj. Ker ima MDNO manjöe ötevilo operatorjev predstavlja MNO funkcije. MNO je torej f( x 1 , x 2 , x 3 , x 4) = x 1 x 2 ‚ x 3 x 4 . 5.2 Veitchev postopek minimizacije 33 Zgled 16 Minimiziraj nepopolno preklopno funkcijo f 4 = ‚4(5 , 7 , 9 , 13)‚4?(8 , 11 , 12 , 15) . Opomba: preklopna funkcija je nepopolna, e funkcijskih vrednosti nima dolo enih pri vseh vhodnih vektorjih. Reöitev 16 Dolo imo MDNO: 1. Nariöemo Veitchev diagram funkcije in ozna imo glavne vsebovalnike (slika 5.6) Pri tem vpraöaje pokrijemo po potrebi. x1 ? x2 1 ? 1 1 x4 1 ? ? x3 Slika 5.6 Glavni vsebovalniki funkcije f 4 = ‚4(5 , 7 , 9 , 13) ‚4? (8 , 11 , 12 , 15). 2. Izpiöemo MDNO: f 4 = x 1 x 4 ‚ x 2 x 4 . 3. Dolo imo ötevilo operatorjev in operandov: [3 , 6] . Dolo imo MKNO: 1. Nariöemo Veitchev diagram negirane funkcije (kjer so bila prej prazna polja piöemo enice, kjer so bile prej enice pustimo prazno, kjer so bili prej vpraöaji, pustimo vpraöaje - slika 5.7). Ozna imo glavne vsebovalnike. x1 ? 1 1 1 x2 ? x4 ? 1 1 ? 1 1 1 x3 Slika 5.7 Glavni vsebovalniki funkcije f 4 = ‚4(0 , 1 , 2 , 3 , 4 , 6 , 10 , 14) ‚4? (8 , 11 , 12 , 15). 2. Izpiöemo MDNO negirane funkcije: f 4 = x 4 ‚ x 1 x 2 . 34 Poglavje 5 Priprava na 5. laboratorijske vaje 3. Dolo imo MKNO: f 4 = x 4 ‚ x 1 x 2 = x 4( x 1 ‚ x 2) . 4. Dolo imo ötevilo operatorjev in operandov: [2 , 4] . Dolo imo MNO: • Ker ima MKNO manjöe ötevilo operandov je MNO zapis:f 4 = x 4( x 1 ‚ x 2) . 6 Priprava na 6. laboratorijske vaje 6.1 Simetri ne preklopne funkcije Funkcija je popolnoma simetri na, e lahko zamenjamo poljubni dve vhodni spre- menljivki in se funkcijska vrednost ne spremeni. Naj ima funkcija f izhodno vrednost 1 pri vsakem tistem vhodnem vektorju, pri katerem ima natanko a vhodnih spremenljivk vrednost 1. ätevilo a tedaj imenujemo simetrijsko ötevilo funkcije f. e za funkcijo f obstaja neprazna mnoûica simetrijskih ötevil, je funkcija popolnoma simetri na. Zgled 17 Zapiöi PDNO funkcije f ( {0 , 2} x 1 , x 2 , x 3) . Reöitev 17 Pomagamo si s pravilnostno tabelo: x 1 x 2 x 3 f ( {0 , 2} x 1 , x 2 , x 3) 0 0 0 1 0 0 1 0 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 PDNO lahko preberemo neposredno iz tabele: f ( x 1 , x 2 , x 3) = ‚3(0 , 3 , 5 , 6) . Zgled 18 Zapiöi PDNO funkcije f ( {0 , 2} x 1 , x 2 , x 3) . Reöitev 18 Pomagamo si s pravilnostno tabelo: 35 36 Poglavje 6 Priprava na 6. laboratorijske vaje x 1 x 2 x 3 x 1 x 2 x 3 f ( {0 , 2} x 1 , x 2 , x 3) 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 1 0 0 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 1 1 0 1 1 1 1 0 1 1 0 1 0 0 0 1 1 1 1 0 1 1 PDNO lahko preberemo neposredno iz tabele: f ( x 1 , x 2 , x 3) = ‚3(1 , 2 , 4 , 7) . 6.2 Quineova metoda minimizacije Medtem, ko so Veitchevi diagrami zelo primerni za ro no minimizacijo funkcij z manjöim ötevilom vhodnih spremenljivk (do vklju no 5), je za ve je ötevilo vhodnih spremenljivk zelo zaûelena avtomatizacija iskanja minimalne oblike. Pri tem se zelo dobro obnese Quineova (tudi Quine–McCluskey) metoda, ki za minimizacijo uporablja tabelari en postopek, ki ga je enostavno sprogramirati. Metoda temelji na iskanju potrebnih glavnih vsebovalnikov na podalgi podobnega postopka kot Veitcheva metoda, le da pri tem uporablja druga na orodja. 6.2.1 Dolo anje MDNO • Preklopno funkcijo zapiöemo v popolni disjunktivni normalni obliki (PDNO). • Poiö emo vse sosednje minterme in njihove glavne vsebovalnike: 1. Nariöemo tabelo z n stolpci, pri emer je n ötevilo vhodnih spremenljivk. V prvega vpiöemo vse minterme, ki dolo ajo preklopno funkcijo. 2. Izraze v stolpcu medsebojno primerjamo in ugotavljamo sosednost. Primerjamo vsakega z vsakim. 3. Sosedna izraza pre rtamo in v naslednji stolpec vpiöemo njun glavni vsebovalnik. 4. Ponavljamo koraka 2 in 3, dokler ne gremo ez vse kombinacije. Pri tem upoötevamo tudi ûe pre rtane izraze. 5. e v predhodnem koraku nismo naöli nobenega vsebovalnika ali pa smo priöli v zadnji stolpec zaklju imo. • Izpiöemo samo potrebne glavne vsebovalnike: 6.2 Quineova metoda minimizacije 37 1. Nariöemo tabelo pokritij z vrsticami, ki predstavljajo glavne vsebovalnike (samo tiste, ki niso pre rtani) in stolpci, ki predstavljajo minterme. 2. Za vsak glavni vsebovalnik ozna imo minterme, ki jih pokriva. 3. Poiö emo najmanjöo mnoûico glavnih vsebovalnikov, ki skupaj pokrijejo vse minterme. Zgled 19 Preklopno funkcijo f = ‚4(1 , 4 , 6 , 7 , 8 , 9 , 10 , 11 , 15) zapiöi v MDNO s Quineovo metodo minimizacije. Reöitev 19 S pomo jo Quineove metode zgradimo slede o tabelo: 4 3 2 1 (1) x 1 x 2 x 3 x 4 (1,6) x 2 x 3 x 4 (5,8) x 1 x 2 (2) x 1 x 2 x 3 x 4 (2,3) x 1 x 2 x 4 (6,7) (3) x 1 x 2 x 3 x 4 (3,4) x 1 x 2 x 3 (4) x 1 x 2 x 3 x 4 (4,9) x 2 x 3 x 4 (5) x 1 x 2 x 3 x 4 (5,6) x 1 x 2 x 3 (6) x 1 x 2 x 3 x 4 (5,7) x 1 x 2 x 4 (7) x 1 x 2 x 3 x 4 (6,8) x 1 x 2 x 4 (8) x 1 x 2 x 3 x 4 (7,8) x 1 x 2 x 3 (9) x 1 x 2 x 3 x 4 (8,9) x 1 x 3 x 4 Zgradimo tabelo pokritij: m 1 m 4 m 6 m 7 m 8 m 9 m 10 m 11 m 15 X x 2 x 3 x 4 X X X x 1 x 2 x 4 X X x 1 x 2 x 3 X X X x 2 x 3 x 4 X X x 1 x 3 x 4 X X X x 1 x 2 X X X X Iz tabele dolo imo potrebne glavne vsebovalnike: fMDNO( x 1 , x 2 , x 3 , x 4) = x 1 x 2 ‚ x 2 x 3 x 4 ‚ x 1 x 2 x 4 ‚ x 2 x 3 x 4 . 6.2.2 Dolo anje MKNO Postopek je podoben kot pri Veitchevi minimizaciji: 1. funkcijo negiramo, 2. s Quineovo metodo izra unamo MDNO negirane funkcije, 3. rezultat negiramo in z DeMorganovim pravilom pretvorimo v MKNO. 38 Poglavje 6 Priprava na 6. laboratorijske vaje Zgled 20 Preklopno funkcijo f = ‚4(1 , 4 , 6 , 7 , 8 , 9 , 10 , 11 , 15) zapiöi v MKNO s Quineovo metodo minimizacije. Reöitev 20 Funkcijo najprej negiramo: f = ‚4(0 , 2 , 3 , 5 , 12 , 13 , 14) . S Quineovo metodo zgradimo slede o tabelo: 4 3 (1) x 1 x 2 x 3 x 4 (1,2) x 1 x 2 x 4 (2) x 1 x 2 x 3 x 4 (2,3) x 1 x 2 x 3 (3) x 1 x 2 x 3 x 4 (4,6) x 2 x 3 x 4 (4) x 1 x 2 x 3 x 4 (5,6) x 1 x 2 x 3 (5) x 1 x 2 x 3 x 4 (5,7) x 1 x 2 x 4 (6) x 1 x 2 x 3 x 4 (7) x 1 x 2 x 3 x 4 Zgradimo tabelo pokritij: m 0 m 2 m 3 m 5 m 12 m 13 m 14 X x 1 x 2 x 4 X X X x 1 x 2 x 3 X X X x 2 x 3 x 4 X X x 1 x 2 x 3 X X X x 1 x 2 x 4 X X Iz tabele dolo imo potrebne glavne vsebovalnike: f MDNO( x 1 , x 2 , x 3 , x 4) = x 1 x 2 x 4 ‚ x 1 x 2 x 3 ‚ x 2 x 3 x 4 ‚ x 1 x 2 x 4 Funkcijo ponovno negiramo in jo preko DeMorganovega pravila pretvorimo v ko- njunktivno normalno obliko: f MDNO( x 1 , x 2 , x 3 , x 4) = fMKNO( x 1 , x 2 , x 3 , x 4) = x 1 x 2 x 4 ‚ x 1 x 2 x 3 ‚ x 2 x 3 x 4 ‚ x 1 x 2 x 4 = ( x 1 ‚ x 2 ‚ x 4)( x 1 ‚ x 2 ‚ x 3)( x 2 ‚ x 3 ‚ x 4)( x 1 ‚ x 2 ‚ x 4) 7 Priprava na 7. laboratorijske vaje 7.1 Lo enje preklopnih funkcij Lo enje preklopne funkcije po spremenljivki x je definirano z izrazom i f ( x 1 , x 2 , ..., x ) = i≠1 , xi, xi+1 , ..., xn f ( x 1 , x 2 , ..., x ) ) i≠1 , 0 , xi+1 , ..., xn xi ‚ f ( x 1 , x 2 , ..., xi≠1 , 1 , xi+1 , ..., xn xi za lo enje konjunktivnih izrazov in z izrazom f ( x 1 , x 2 , ..., x ) = i≠1 , xi, xi+1 , ..., xn ( f( x 1 , x 2 , ..., x ) )( ) ) i≠1 , 0 , xi+1 , ..., xn ‚ xi f ( x 1 , x 2 , ..., xi≠1 , 1 , xi+1 , ..., xn ‚ xi za lo enje disjunktivnih izrazov. Pri tem funkcijama, ki nastopata v izrazu, pravimo funkcijska ostanka: f 0( x 1 , x 2 , ..., x ) = ) i≠1 , xi+1 , ..., xn f ( x 1 , x 2 , ..., xi≠1 , 0 , xi+1 , ..., xn , f 1( x 1 , x 2 , ..., x ) = ) i≠1 , xi+1 , ..., xn f ( x 1 , x 2 , ..., xi≠1 , 1 , xi+1 , ..., xn . Za realizacijo preklopnih funkcij z multiplekserji uporabljamo konjunktivno lo eva- nje izrazov, zato bomo v nadaljevanju obravnavali le tega. Zgled 21 Funkcijo f( x 1 , x 2 , x 3) = ‚3(0 , 2 , 5 , 6 , 7) lo i preko spremenljivke x 1 . Reöitev 21 Funkcijo lahko zapiöemo kot: f ( x 1 , x 2 , x 3) = x 1 x 2 x 3 ‚ x 1 x 2 x 3 ‚ x 1 x 2 x 3 ‚ x 1 x 2 x 3 ‚ x 1 x 2 x 3 = (0 x 2 x 3 ‚ 0 x 2 x 3 ‚ 0 x 2 x 3 ‚ 0 x 2 x 3 ‚ 0 x 2 x 3) x 1‚ ‚(1 x 2 x 3 ‚ 1 x 2 x 3 ‚ 1 x 2 x 3 ‚ 1 x 2 x 3 ‚ 1 x 2 x 3) x 1 = ( x 2 x 3 ‚ x 2 x 3) x 1 ‚ ( x 2 x 3 ‚ x 2 x 3 ‚ x 2 x 3) x 1 39 40 Poglavje 7 Priprava na 7. laboratorijske vaje Pri tem dobimo funkcijska ostanka: f 0( x 2 , x 3) = x 2 x 3 ‚ x 2 x 3 f 1( x 2 , x 3) = x 2 x 3 ‚ x 2 x 3 ‚ x 2 x 3 Lo imo funkcijski ostanek f 0( x 2 , x 3) öe po x 2 : f 0( x 2 , x 3) = (0 x 3 ‚ 0 x 3) x 2 ‚ (1 x 3 ‚ 1 x 3) x 2 = x 3 x 2 ‚ x 3 x 2 Pri tem dobimo funkcijska ostanka: f 00( x 3) = x 3 f 01( x 3) = x 3 Lo imo funkcijski ostanek f 1( x 2 , x 3) öe po x 2 : f 1( x 2 , x 3) = (0 x 3 ‚ 0 x 3 ‚ 0 x 3) x 2 ‚ (1 x 3 ‚ 1 x 3 ‚ 1 x 3) x 2 = x 3 x 2 ‚ ( x 3 ‚ x 3) x 2 = x 3 x 2 ‚ 1 x 2 Pri tem dobimo funkcijska ostanka: f 10( x 3) = x 3 f 11( x 3) = 1 7.2 Multiplekser Multiplekser spada v druûino strukturalnih preklopnih vezij. Multiplekser ima dva niza vhodnih spremenljivk, in sicer naslovne spremenljivke na naslovnih vhodih ( An, An≠1 , ..., A 0) in podatkovne spremenljivke na podatkovnih vhodih ( I 0 , I 1 , ..., I 2 n≠1). Na podlagi vrednosti naslovnih spremenljivk se izbere podatkovni vhod, ki se bo preslikal na izhod multiplekserja. Multiplekser v kombinaciji s konstanto 0 ali 1 predstavlja funkcijsko poln sistem - z njim oziroma s kombinacijo ve multiplekserjev lahko realiziramo poljubno logi no funkcijo. Multiplekser v odvisnosti od vrednosti naslovnih vhodov na izhod preslika enega izmed podatkovnih vhodov. Natan neje, na izhod se preslika podatkovni vhod z indeksom, ki je enak desetiökemu zapisu vrednosti na naslovnih vhodih. Sploöno delovanje multiplekserja prikazuje tabela 7.1. Multiplekser z n naslovnimi spremenljivkami ozna ujemo kot MUX 2 n/ 1. Reali- zacijo funkcije z multiplekserjem praviloma podajamo z logi no shemo. Sploöno logi no shemo za multiplekser MUX 2 n/ 1 prikazuje slika 7.1. 7.3 Realizacija preklopnih funkcij z multiplekserji 41 An≠1 An≠2 ... A 0 f 0 0 ... 0 I 0 0 0 ... 1 I 1 . . ... . . . . ... . . . . ... . . 1 1 ... 0 I 2 n≠2 1 1 ... 1 I 2 n≠1 Tabela 7.1 Sploöno delovanje multiplekserja MUX 2 n/ 1. Slika 7.1 Sploöna logi na shema za multiplekser MUX 2 n/ 1. 7.3 Realizacija preklopnih funkcij z multiplekserji Z uporabo konstant 0 in 1 in multiplekserja MUX 2 n/ 1 lahko realiziramo poljubno preklopno funkcijo z n+1 vhodnimi spremenljivkami. Realizacija funkcij z uporabo multiplekserjev z manjöim ötevilom naslovnih vhodov poteka z drevesno oziroma kaskadno vezavo multiplekserjev. Realizacija preklopnih funkcij z multiplekserji poteka na podlagi lo enja. Funkcijo lo imo preko vhodnih spremenljivk, ki jih veûemo na naslovne vhode, na podatkov- nih vhodih pa realiziramo funkcijske ostanke. V nadaljevanju bomo demonstrirali realizacijo funkcije f( x 1 , x 2 , x 3) = ‚3(0 , 2 , 5 , 6 , 7) 42 Poglavje 7 Priprava na 7. laboratorijske vaje z multiplekserji razli nih velikosti. 7.3.1 ätevilo vhodnih spremenljivk je enako ötevilu naslovnih vhodov multiplekserja Na razpolago imamo konstanti 0 in 1 in multiplekser, ki ima enako ötevilo naslovnih vhodov, kot je ötevilo vhodnih spremenljivk preklopne funkcije. V tem primeru na naslovne vhode veûemo funkcijske vrednosti v enakem vrstnem redu kot ti nastopajo v pravilnostni tabeli, na naslovne vhode pa vhodne spremenljivke - prav tako v enakem vrstnem redu kot nastopajo v pravilnostni tabeli. Funkcijo torej lo imo preko vseh vhodnih spremenljivk, zato lahko vse funkcijske ostanke izrazimo s konstantami 0 in 1. Zgled 22 Realiziraj funkcijo ‚3(0 , 2 , 5 , 6 , 7) z MUX 8 / 1 . Reöitev 22 V prvem koraku zapiöemo pravilnostno tabelo funkcije. x 1 x 2 x 3 f( x 1 , x 2 , x 3) 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 1 V drugem koraku na podatkovne vhode veûemo funkcijske vrednosti v enakem vrstnem redu kot ti nastopajo v pravilnostni tabeli, na naslovne vhode pa vhodne spremenljivke - prav tako v enakem vrstnem redu kot nastopajo v pravilnostni tabeli (glej sliko 7.2). 7.3.2 ätevilo vhodnih spremenljivk je za 1 ve je od ötevila naslovnih vhodov multiplekserja Na razpolago imamo konstanti 0 in 1 in multiplekser, ki ima ötevilo naslovnih vhodov za 1 manjöe, kot je ötevilo vhodnih spremenljivk preklopne funkcije. Funkcijo lo imo po spremenljivkah glede na njihov vrstni red od leve proti desni. Iz tega sledi, da skrajno leve vhodne spremenljivke veûemo na naslovne vhode multiplekserja (najbolj levo spremenljivko na naslovni vhod z najviöjim indeksom). Na podatkovnih vhodih realiziramo funkcijski ostanek, ki ga lahko vedno izrazimo z najmanj pomembno vhodno spremenljivko, njeno negacijo, konstanto 0 in konstanto 1. 7.3 Realizacija preklopnih funkcij z multiplekserji 43 Slika 7.2 Realizacija 3-vhodne funkcije z multiplekserjem MUX 8 / 1. Zgled 23 Realiziraj funkcijo ‚3(0 , 2 , 5 , 6 , 7) z MUX 4 / 1 . Reöitev 23 V prvem koraku zapiöemo pravilnostno tabelo funkcije. x 1 x 2 x 3 f( x 1 , x 2 , x 3) 0 0 0 1 I 0 = x 3 0 0 1 0 0 1 0 1 I 1 = x 3 0 1 1 0 1 0 0 0 I 2 = x 3 1 0 1 1 1 1 0 1 I 3 = 1 1 1 1 1 V drugem koraku na naslovne vhode veûemo najpomembnejöe spremenljivke (v naöem primeru x 1 in x 2 ). V naöem primeru na vhod A 1 veûemo x 1 , na vhod A 2 pa x 2 . S tem funkcijo lo imo preko spremenljivk x 1 in x 2 . S pomo jo spremenljivke, ki je ostala, uporabe negacij, konstante 0 in 1, realiziramo funkcijske ostanke lo enja, ki jih veûemo na podatkovne vhode (glej sliko 7.3). 44 Poglavje 7 Priprava na 7. laboratorijske vaje Slika 7.3 Realizacija 3-vhodne funkcije z multiplekserjem MUX 4 / 1. 7.3.3 ätevilo vhodnih spremenljivk je za ve kot 1 ve je od ötevila naslovnih vhodov multiplekserja e je ötevilo vhodnih spremenljivk funkcije za ve kot za 1 ve je od ötevila naslovnih vhodov multiplekserja, moramo za realizacijo uporabiti ve je ötevilo multiplekserjev, ki jih med seboj veûemo v drevesno (kaskadno) vezavo. Ponavadi funkcijo lo imo po najpomembnejöih spremenljivkah, ni pa to pravilo. V tem primeru za nemo z vezavo najpomembnejöih spremenljivk na naslovne vhode zadnjega multiplekserja v kaskadi. Zgled 24 Realiziraj funkcijo ‚3(0 , 2 , 5 , 6 , 7) z MUX 2 / 1 . Reöitev 24 V prvem koraku zapiöemo pravilnostno tabelo in funkcijo • najprej lo imo po x 1 , • zgornji del (funkcijski ostanek pri x 1 = 0 ) lahko izrazimo z x 3 , • spodnji del (funkcijski ostanek pri x 1 = 1 ) lo imo öe po x 2 (zgornji del, t.j. funkcijski ostanek pri x 2 = 0 , lahko izrazimo z x 3 , spodnji del, t.j. funkcijski ostanek pri x 2 = 1 , pa s konstanto 1). Ostanke pri lo enju smo izra unali ûe v zgledu 21. 7.3 Realizacija preklopnih funkcij z multiplekserji 45 x 1 x 2 x 3 f( x 1 , x 2 , x 3) 0 0 0 1 0 0 1 0 x 3 0 1 0 1 0 1 1 0 1 0 0 0 x 3 1 0 1 1 1 1 0 1 1 1 1 1 1 V drugem koraku nariöemo shemo realizacije. Ker smo tabelo najprej lo ili po x 1 , x 1 uporabimo kot naslovni vhod zadnjega multiplekserja v kaskadi. Funkcijski ostanek f 0 po x 1 lahko izrazimo z x 3 – x 3 veûemo na podatkovni vhod I 0 multiplekserja. Spodnjega dela, ki predstavlja funkcijski ostanek f 1 po x 1 , ne moremo izraziti na enostaven na in, zato ga lo imo öe po spremenljivki x 2 in za njegovo realizacijo uporabimo dodaten multiplekser MUX 2 / 1 . Le-tega veûemo na vhod I 1 zadnjega multiplekserja v kaskadi. Na naslovni vhod dodatnega multiplekserja veûemo spremenljivko x 2 . Funkcijski ostanek f 0 lo enja po x 2 lahko izrazimo z x 3 , ostanek f 1 pa s konstanto 1 - razvidno iz tabele. Na podatkovni vhod I 0 dodatnega multiplekserja torej veûemo x 3 , na vhod I 1 pa konstanto 1 . Realizacijo prikazuje slika 7.4. Slika 7.4 Realizacija 3-vhodne preklopne funkcije z dvema multiplekserjema MUX 2 / 1. 8 Priprava na 8. laboratorijske vaje 8.1 Sekven na vezja Do zdaj smo obravnavali kombinatorna vezja, ki ne omogo ajo pomnjenja. Po- mnjenje je (obi ajno) realizirano z uporabo sinhronih pomnilnih celic (z uporabo n pomnilnih celic lahko realiziramo pomnjenje 2 n razli nih vrednosti). Izhod sinhro- nih pomnilnih celic se spreminja ob dolo eni (pozitivni ali negativni) fronti urinega signala (angl. clock) – sinhronizacija z urinim signalom (glej sliko 8.1). Sekven na vezja so vezja, ki so sestavljena iz kombinatornega dela in pomnilnih celic (glej sliko 8.2). Slika 8.1 asovni potek vzor nega primera urinega signala. Puö ica navzgor ozna uje pozitivno (prehod iz 0 v 1), puö ica navzdol pa negativno fronto (prehod iz 1 v 0). Slika prikazuje tri periode urinega signala. x y kombinatorno y vezje D y -1 pomnilne celice Slika 8.2 Struktura sekven nih vezij. 8.2 Sploöna pomnilna ena ba Vsako sekven no vezje lahko zapiöemo s sploöno pomnilno ena bo: D 1 q = i qigi, 1 ‚ qigi, 2 , 47 48 Poglavje 8 Priprava na 8. laboratorijske vaje pri emer je • q : ena izmed preklopnih spremenljivk, ki opisuje notranje stanje sekven nega i vezja • Dkq : vrednost spremenljivke po i qi k asovnih korakih • gi, 1 in gi, 2: preklopni funkciji, odvisni od vhodnih spremenljivk x = { x 1 , x 2 , ..., xn}. Novo notranje stanje sekven nega vezja je torej dolo eno s trenutnim notranjim stanjem vezja in s stanjem zunanjih vhodov. Notranje stanje se spremeni ob pozitivni ali negativni fronti urinega signala. Izbrana fronta je za celotno vezje vedno enaka, s imer sekven ne komponente v vezju med seboj sinhroniziramo. 8.3 Enostavne pomnilne celice 8.3.1 RS pomnilna celica ( Reset Set) RS pomnilna celica je najenostavnejöa celica, katere delovanje lahko opiöemo z ena bo D 1 q = qr ‚ s, pri emer r in s predstavljata zunanja vhoda v celico. Kot nakaûejo ûe imena vhodov, vhod r ( reset) izhod pomnilne celice postavi na 0, vhod s ( set) pa na 1. e sta oba vhoda enaka 0, se izhod pomnilne celice ohranja (pomni). Za pravilno delovanje celice mora veljati pogoj rs = 0 (vhoda ne smeta biti isto asno 1). Delovanje RS pomnilne celice lahko ponazorimo s Tabelo 8.1. r s D 1 q q D 1 q r s 0 0 q 0 0 ? 0 0 1 1 0 1 0 1 1 0 0 1 0 1 0 1 1 x 1 1 0 ? (a) (b) Tabela 8.1 Tabela (a) prikazuje izhod RS pomnilne celice v naslednjem asovnem koraku v odvisnosti od trenutnih vhodov, (b) pa stanja vhodov, s katerimi pridemo do ûelenega izhoda v naslednjem asovnem koraku (vzbujevalna tabela). Pri tem x prikazuje nedefiniran izhod oziroma nedovoljeno kombinacijo vhodov. Logi na simbola RS pomnilne celice sta prikazana na sliki 8.3. 8.3 Enostavne pomnilne celice 49 r q q r Clock RS Clock RS s q s q (a) (b) Slika 8.3 Logi na simbola RS pomnilne celice, pri emer je celica na sliki (a) sinhronizi- rana s pozitivno fronto urinega signala, celica na sliki (b) pa z negativno fronto. 8.3.2 JK pomnilna celica ( Jump Kill) JK pomnilna celica predstavlja razöiritev RS pomnilne celice. Njeno delovanje lahko opiöemo z ena bo D 1 q = qk ‚ qj, kjer sta j in k zunanja vhoda. e je vsaj eden izmed vhodnih signalov j in k enak 0, je njeno delovanje enako delovanju RS pomnilne celice. Pri tem ima signal j ( jump) enako vlogo kot signal s, signal k ( kill) pa enako vlogo kot signal r RS pomnilne celice. Pri JK pomnilni celici je kombinacija vhodov jk = 1 dovoljena. e postavimo oba vhoda na 1, se izhod pomnilne celice ( q) ob urini fronti zamenja ( q). Delovanje JK pomnilne celice lahko ponazorimo s Tabelo 8.2. k j D 1 q q D 1 q k j 0 0 q 0 0 ? 0 0 1 1 0 1 ? 1 1 0 0 1 0 1 ? 1 1 q 1 1 0 ? (a) (b) Tabela 8.2 Tabela (a) prikazuje izhod JK pomnilne celice v naslednjem asovnem koraku v odvisnosti od trenutnih vhodov, (b) pa stanja vhodov, s katerimi pridemo do ûelenega izhoda v naslednjem asovnem koraku (vzbujevalna tabela). Logi na simbola JK pomnilne celice sta prikazana na sliki 8.4. 50 Poglavje 8 Priprava na 8. laboratorijske vaje k q k q Clock JK Clock JK j q j q (a) (b) Slika 8.4 Logi na simbola JK pomnilne celice, pri emer je celica na sliki (a) sinhronizi- rana s pozitivno fronto urinega signala, celica na sliki (b) pa z negativno fronto. 8.3.3 T pomnilna celica ( Trigger) T pomnilna celica ob fronti urinega signala spreminja izhod v primeru, da je zunanji vhod t postavljen na 1, sicer pa se vrednost izhoda ohranja. Njeno delovanje lahko opiöemo z ena bo D 1 q = qt ‚ qt, kjer je t zunanji vhod. Delovanje T pomnilne celice lahko ponazorimo s Tabelo 8.3. q D 1 q t t D 1 q 0 0 0 0 q 0 1 1 1 q 1 0 1 1 1 0 (a) (b) Tabela 8.3 Tabela (a) prikazuje notranje izhod T pomnilne celice v naslednjem asovnem koraku v odvisnosti od vrednosti vhoda, (b) pa vrednost vhoda, s katero pridemo do ûelenega izhoda v naslednjem asovnem koraku (vzbujevalna tabela). Logi na simbola T pomnilne celice sta prikazana na sliki 8.5. 8.4 Realizacija sekven nih vezij s pomnilnimi celicami 51 t q q t Clock T Clock T q q (a) (b) Slika 8.5 Logi na simbola T pomnilne celice, pri emer je celica na sliki (a) sinhronizirana s pozitivno fronto urinega signala, celica na sliki (b) pa z negativno fronto. 8.3.4 D pomnilna celica (Delay) D pomnilna celica ob fronti urinega signala postavi svoj izhod na vrednost vhodnega signala. Njeno delovanje si lahko torej interpretiramo kot zakasnitev vhodnega signala d. Opiöemo ga lahko z ena bo D 1 q = d. Delovanje D pomnilne celice lahko ponazorimo s Tabelo 8.4. q D 1 q d d D 1 q 0 0 0 0 0 0 1 1 1 1 1 0 0 1 1 1 (a) (b) Tabela 8.4 Tabela (a) prikazuje izhod D pomnilne celice v naslednjem asovnem koraku v odvisnosti od vrednosti vhoda, (b) pa vrednost vhoda, s katero pridemo do ûelenega izhoda v naslednjem asovnem koraku (vzbujevalna tabela). Logi na simbola D pomnilne celice sta prikazana na sliki 8.6. 8.4 Realizacija sekven nih vezij s pomnilnimi celicami Podano imamo sekven no vezje in tip pomnilnih celic, ki jih lahko uporabimo za njegovo realizacijo. Naö cilj je dolo itev kombinatornega dela vezja, ki bo vhodne spremenljivke prilagodil delovanju danih pomnilnih celic na tak na in, da bo izhod 52 Poglavje 8 Priprava na 8. laboratorijske vaje d q q d Clock D Clock D q q (a) (b) Slika 8.6 Logi na simbola D pomnilne celice, pri emer je celica na sliki (a) sinhronizirana s pozitivno fronto urinega signala, celica na sliki (b) pa z negativno fronto. pomnilnih celic odraûal delovanje podanega sekven nega vezja. Postopek realizacije bomo demonstirali na zgledu. Zgled 25 S pomo jo JK pomnilne celice realiziraj M celico, ki deluje po ena bi D 1 q = q( x © y) ‚ q y. Reöitev 25 Osnutek sheme realizacije prikazuje slika 8.7. Dolo iti je torej po- trebno kombinatorni del vezja: k( x, y, q) in j( x, y, q) . x k(x,y,q) k q y Clock JK j(x,y,q) j M Slika 8.7 Shema realizacije celice M, pri emer k( x, y, q) dolo a kombinatorno vezje na vhodu k, j( x, y, q) pa kombinatorno vezje na vhodu j JK pomnilne celice. V prvem koraku v tabeli zapiöemo funkcijo, ki dolo a delovanje sekven nega vezja. Pri tem so neodvisne spremenljivke x, y in q, odvisna spremenljivka pa je D 1 q: 8.4 Realizacija sekven nih vezij s pomnilnimi celicami 53 x y q D 1 q 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 Na podlagi prehodov iz q v D 1 q in na podlagi vzbujevalne tabele JK pomnilne celice (glej Tabelo 8.2 (b)) lahko dolo imo vrednosti, ki morajo biti na vhodih k in j pri posamezni kombinaciji: x y q D 1 q k j 0 0 0 1 ? 1 0 0 1 1 0 ? 0 1 0 0 ? 0 0 1 1 0 1 ? 1 0 0 1 ? 1 1 0 1 0 1 ? 1 1 0 0 ? 0 1 1 1 1 0 ? Funkciji k( x, y, q) in j( x, y, q) izrazimo z vhodnimi spremenljivkami x, y in q. Pri tem si lahko pomagamo z Veitchevim diagramom: x x y ? 0 1 ? y 0 ? ? 0 ? 1 0 ? 1 ? ? 1 q q k( x, y, q) = x y ‚ x y j( x, y, q) = y Funkciji realiziramo v shemi, ki jo prikazuje slika 8.7. 9 Priprava na 9. laboratorijske vaje 9.1 Moorov in Mealyjev kon ni avtomat Kon ni avtomat (angl. Finite State Machine) je dolo en s peterico A = { X, S, Z, ”, ⁄} , kjer je • X – vhodna abeceda: kon na neprazna mnoûica moûnih vhodov v avtomat oziroma mnoûica vhodnih rk, • S – notranja abeceda: kon na neprazna mnoûica moûnih stanj avtomata, • Z – izhodna abeceda: kon na neprazna mnoûica moûnih izhodov avtomata oziroma izhodnih rk, • ” – funkcija prehajanja notranjih stanj: funkcija, ki v odvisnosti od trenutnega stanja in vhodne rke dolo a naslednje stanje avtomata, • ⁄ – izhodna funkcija: funkcija, ki dolo a izhodno rko avtomata v odvisnosti od trenutnega stanja avtomata (Moorov avtomat) oziroma v odvisnosti od trenutnega stanja in vhodne rke avtomata (Mealyjev avtomat). Avtomate navadno podajamo tabelari no s tabelo prehajanja stanj ali grafi no z diagramom prehajanja stanj. V tabeli prehajanja stanj podajamo naslednje stanje in izhodno rko avtomata v odvisnosti od trenutnega stanja (zgornja vrstica tabele) in vhodne rke avtomata (levi stolpec tabele) kot prikazuje spodnja tabela. izhodna rka (Moore) trenutno stanje naslednje stanje dna rka vho + izhodna rka (Mealy) 55 56 Poglavje 9 Priprava na 9. laboratorijske vaje Diagram prehajanja stanj je podan z usmerjenim grafom, katerega vozliö a do- lo ajo stanja avtomata, povezave med vozliö i pa opisujejo prehode med stanji ob prisotnosti vhodnih rk. V primeru Moorovega avtomata stanjem pripiöemo izhodno rko, ki pa je v primeru Mealyjevega avtomata vezana na prehode med stanji. Zgled 26 Nariöi diagram prehajanja stanj za Moorov avtomat, ki je podan s slede o tabelo prehajanja stanj z 1 z 1 z 2 S 1 S 2 S 3 x 1 S 1 S 2 S 1 x 2 S 2 S 3 S 1 Kaköno je zaporedje izhodnih rk (izhodna beseda), ki jo avtomat vrne pri zaporedju vhodnih rk (vhodni besedi) x 1 x 1 x 2 x 2 x 2 x 2 x 1 in za etnem stanju S 1 ? Reöitev 26 Najprej zapiöimo vse tri abecede avtomata: • X = { x 1 , x 2} , • S = { S 1 , S 2 , S 3} , • Z = { z 1 , z 2} . Diagram prehajanja stanj ima torej tri vozliö a, iz vsakega vozliö a pa vodita najve dve povezavi (za vsako vhodno rko ena): x 1 x 1 S 1 S 2 x 2 z 1 z 1 x 1 , x 2 x 2 S 3 z 2 Simulirajmo öe delovanje avtomata pri vhodni besedi x 1 x 1 x 2 x 2 x 2 x 2 x 1 in za etnem stanju S 1 z uporabo spodnje tabele: 9.1 Moorov in Mealyjev kon ni avtomat 57 vhodna rka x 1 x 1 x 2 x 2 x 2 x 2 x 1 stanje S 1 S 1 S 1 S 2 S 3 S 1 S 2 S 2 izhodna rka z 1 z 1 z 1 z 2 z 1 z 1 z 1 Izhodna beseda je torej z 1 z 1 z 1 z 2 z 1 z 1 z 1. Zgled 27 Nariöi diagram prehajanja stanj in zapiöi tabelo prehajanja stanj Moo- rovega avtomata, ki nadzira odpiranje kroûnih vrat. Mehanizem drûi vrata zaprta, dokler avtomat ne zazna, da je bil vstavljen kovanec. V tem primeru avtomat mehanizmu javi, da lahko sprosti zaporo vrat. Ko avtomat zazna prehod skozi vrata, ta javi mehanizmu, naj zapre vrata. Reöitev 27 Avtomat bo imel dve stanji, in sicer stanje, v katerem drûi vrata zaprta (S 1 ) in ima tako izhodno rko close, in stanje, v katerem so vrata odprta (S 2 ) in ima tako izhodno rko open. Prehod iz S 1 v S 2 bomo izvedli, ko avtomat detektira, da je bil vstavljen kovanec (vhodna rka coin), prehod iz S 2 v S 1 pa, ko avtomat detektira prehod skozi vrata (vhodna rka push). coin push S 1 S 2 coin close open push Zapiöimo öe tabelo prehajanja stanj avtomata: close open S 1 S 2 coin S 2 S 2 push S 1 S 1 Zgled 28 Za Mealyjev avtomat podan z diagramom prehajanja stanj zapiöi tabelo prehajanja stanj. x 1 /z 1 x 1 /z 1 S 1 S 2 x 2 /z 1 x 1 /z 1 , x 2 /z 1 x 2 /z 2 S 3 58 Poglavje 9 Priprava na 9. laboratorijske vaje Kaköno je zaporedje izhodnih rk (izhodna beseda), ki jo avtomat vrne pri zaporedju vhodnih rk (vhodni besedi) x 1 x 1 x 2 x 2 x 2 x 2 x 1 in za etnem stanju S 1 ? Reöitev 28 Abecede avtomata so enake kot pri Moorovem avtomatu iz zgleda 26. Zapiöimo tabelo prehajanja stanj: S 1 S 2 S 3 x 1 S 1 /z 1 S 2 /z 1 S 1 /z 1 x 2 S 2 /z 1 S 3 /z 2 S 1 /z 1 Simulirajmo öe delovanje avtomata pri vhodni besedi x 1 x 1 x 2 x 2 x 2 x 2 x 1 in za etnem stanju S 1 z uporabo spodnje tabele: vhodna rka x 1 x 1 x 2 x 2 x 2 x 2 x 1 stanje S 1 S 1 S 1 S 2 S 3 S 1 S 2 S 2 izhodna rka z 1 z 1 z 1 z 2 z 1 z 1 z 1 Izhodna beseda je torej z 1 z 1 z 1 z 2 z 1 z 1 z 1 . Avtomat pri enakih pogojih generira enako izhodno abecedo kot Moorov avtomat iz zgleda 26. Podrobnejöa analiza bi pokazala, da sta si avtomata ekvivalentna. Zgled 29 Nariöi öe Mealyjev avtomat v skladu z navodili iz zgleda 27. Reöitev 29 V primeru Mealyjevega avtomata lahko avtomat z enim samim stanjem generira obe izhodni rki ( open in close ). Diagram prehajanja stanj ima tako slede o obliko: coin/open S 1 push/close Zapiöimo öe tabelo prehajanja stanj avtomata: S 1 coin S 1 /open push S 1 /close 9.2 Pretvorbe med avtomati 59 9.2 Pretvorbe med avtomati Kot smo videli ûe v prejönjih zgledih imata lahko dva avtomata razli nega tipa (Moore in Mealy) popolnoma enako delovanje in sta si tako ekvivalentna (izjema je za etna izhodna rka, saj Mealyjev avtomat le-to zgenerira öele pri prvem prehodu, pri Moorovem avtomatu pa je izhodna rka vedno prisotna). V sploönem velja, da za vsak Moorov avtomat obstaja vsaj en njegov Melyjev ekvivalent in obratno. Pretvorbo iz Melyjevega avtomata v Moorovega lahko izvedemo po slede em postopku: 1. Mealyjev avtomat zapiöemo tabelari no. 2. Zapiöemo vse tri abecede Moorovega avtomata, pri emer se vhodna in izhodna abecedi ohranjata, notranjo abeceda pa tvorimo s pari notranje stanje/izhodna rka, ki se pojavijo znotraj tabele Mealyjevega avtomata. 3. Zapiöemo tabelo Moorovega avtomata, v kateri nastopajo vsa stanja, ki smo jih definirali v prejönjem koraku. Izhodna rka za stanje je dolo ena z izhodno rko, katere oznaka nastopa pri posameznem stanju. Prehodi med stanji so dolo eni s prehodi med ekvivalentimi stanji v Mealyjevem avtomatu, Zgled 30 Mealyjev avtomat, podan s spodnjim diagramom, pretvori v Moorov avtomat. x 2 /z 1 x 1 /z 1 S 1 S 2 x 2 /z 1 x 1 /z 2 Reöitev 30 Podan Mealyjev avtomat zapiöemo tabelari no: S 1 S 2 x 1 S 1 /z 1 S 1 /z 2 x 2 S 2 /z 1 S 2 /z 1 Notranjo abecedo Moorovega avtomata tvorijo pari naslednje stanje/izhodna rka Mealyjevega avtomata, ki se pojavijo znotraj tabele prehajanja stanj. Notranja abeceda je torej: S 1 /z 1 , S 1 /z 2 , S 2 /z 1 (opomba: stanje S 2 /z 2 lahko izpustimo, ker se v tabeli ne pojavi – predpostavljamo, da to stanje ni za etno stanje avtomata). Zaradi laûjega zapisa stanja preimenujemo v: S 11 , S 12 , S 21 . Vhodna in izhodna abeceda ostaneta enaki. 60 Poglavje 9 Priprava na 9. laboratorijske vaje Na podlagi delovanja Melyjevega avtomata lahko tako zapiöemo tabelo Moorovega avtomata: z 1 z 2 z 1 S 11 S 12 S 21 x 1 S 11 S 11 S 12 x 2 S 21 S 21 S 21 In ga nariöemo. x 1 S 11 x 1 x z 2 1 x 2 S 12 S 21 x 2 z 2 z 1 x 1 Po podobnem postopku lahko izvedemo pretvorbo Moorovega v Mealyjev avtomat: 1. Moorov avtomat zapiöemo tabelari no. 2. Zapiöemo vse tri abecede Mealyjevega avtomata, ki so kar enake abecedam Moorovega avtomata. 3. Zapiöemo tabelo Mealyjevega avtomata, pri emer je naslednje stanje enako kot pri Moorovem avtomatu, izhodna rka pa je dolo ena z izhodno rko stanja Moorovega avtomata, v katerega bo avtomat z dolo eno kombinacijo stanje/vhodna rka priöel. Zgled 31 Moorov avtomat, ki predstavlja reöitev prejönjega zgleda, pretvori v Mealyjev avtomat. Reöitev 31 Pretvorimo dobljeni Moorov avtomat nazaj v Mealyjevega. Vse tri abecede se ohranjajo. Zapiöimo tabelo prehajanja stanj: 9.2 Pretvorbe med avtomati 61 S 11 S 12 S 21 x 1 S 11 /z 1 S 11 /z 1 S 12 /z 2 x 2 S 21 /z 1 S 21 /z 1 S 21 /z 1 Dobili smo avtomat s tremi notranji stanji, ki je enakovreden prvotnemu Mealy- jevemu avtomatu z dvema stanjema. Stanji S 11 in S 12 sta enaki tako po izhodnih rkah kot tudi po prehodih. Stanji lahko tako zakodiramo zgolj z enim notranjim stanjem – recimo mu stanje S 1 . Stanje S 21 preimenujmo, da bo zapis avtomata bolj pregleden – recimo mu stanje S 2 . Nad stanji avtomata tako izvedemo slede o preslikavo: S 11 æ S 1 S 12 æ S 1 S 21 æ S 2 Tako dobimo avtomat, ki je enak izhodiö nemu: S 1 S 2 x 1 S 1 /z 1 S 1 /z 2 x 2 S 2 /z 1 S 2 /z 1 10 Priprava na 10. laboratorijske vaje 10.1 Realizacija kon nih avtomatov s pomnilnimi celicami (Moorov avtomat) Z uporabo logi nih vrat in pomnilnih celic ûelimo realizirati Moorov avtomat. Postopek realizacije je sestavljen iz slede ih korakov: 1. Zapis kodirnih tabel: vhodna abeceda, notranja abeceda in izhodna abeceda so predstavljene z abstraktnim zapisom. Za realizacijo s preklopnimi funkcijami moramo le-te predstaviti s preklopnimi spremenljivkami. Pri tem upoötevamo dejstvo, da lahko z i vhodnimi spremenljivkami zakodiramo 2 i vhodnih rk, z j izhodnimi spremenljivkami 2 j izhodnih rk, s k pomnilnimi celicami pa 2 k notranjih stanj. S kodiranimi tabelami poveûemo posamezne spremenljivke oziroma notranja stanja pomnilnih celic s posameznimi rkami oziroma stanji avtomata. 2. Zapis pravilnostne tabele avtomata: na podlagi diagrama prehajanja stanj oziroma tabele prehajanja stanj in kodirnih tabel, lahko zapiöemo pravilnostno tabelo avtomata. Pri tem na levi strani tabele nastopajo spremenljivke, ki dolo ajo vhodne rke in trenutna notranja stanja avtomata (neodvisne spremenljivke), na desni strani pa spremenljivke, ki dolo ajo notranje stanje avtomata v naslednjem asovnem koraku in spremenljivke, ki dolo ajo izhodne rke avtomata (odvisne spremenljivke). 3. Dolo itev vhodov v pomnilne celice: na podlagi prehodov med spremenljiv- kami, ki dolo ajo trenutno stanje avtomata in stanje avtomata v naslednjem asovnem koraku ter vzbujevalnih tabel pomnilnih celic, ki jih imamo na raz- polago, lahko dolo imo potrebne vhode v pomnilne celice v posamezni vrstici (tabelo dopolnimo na podoben na in kot smo jo pri realizaciji sekven nih vezij s pomnilnimi celicami). 4. Izpis in minimizacija izhodne funkcije in funkcije prehajanja stanj: na podlagi pravilnostne tabele lahko s pomo jo Veitchevega diagrama izpiöemo preklopne funkcije, ki dolo ajo izhodne rke avtomata (izhodna funkcija) in preklopne 63 64 Poglavje 10 Priprava na 10. laboratorijske vaje funkcije, ki nastopajo na vhodih pomnilnih celic in tako dolo ajo prehode med stanji avtomata (funkcija prehajanja stanj) Zgled 32 Z uporabo T pomnilnih celic in poljubnih logi nih vrat realiziraj Moorov avtomat, ki je podan z diagramom prehajanja stanj. x 1 x 2 S 1 S 2 x 1 z 2 z 1 x 2 Reöitev 32 Postopek je slede : 1. Zapiöemo kodirne tabele, ki dolo ijo kodiranje vhodne abecede, notranje abecede in izhodne abecede. Za zapis vseh rk vhodne abecede je dovolj ena vhodna spremenljivka (x); prav tako je za zapis vseh rk izhodne abecede dovolj ena izhodna spremenljivka (y). Ker imamo zgolj dve notranji stanji avtomata, je za njegovo realizacijo potrebna ena pomnilna celica T z notranjim stanjem q. Kodirne tabele so torej x q y x 1 0 S 1 0 z 1 0 x 2 1 S 2 1 z 2 1 2. Na podlagi kodirnih tabel in podanega diagrama prehajanja stanj lahko zapi- öemo pravilnostno tabelo avtomata. Pri tem na levi strani tabele nastopajo spremenljivke, ki dolo ajo trenutno notranje stanje avtomata (q) in vhodno rko (x), na desni pa spremenljivke, ki dolo ajo notranje stanje avtomata v naslednjem asovnem koraku (D 1 q) in izhodno rko (y): q x D 1 q y 0 0 1 1 0 1 0 1 1 0 1 0 1 1 0 0 10.1 Realizacija kon nih avtomatov s pomnilnimi celicami (Moorov avtomat) 65 3. Na podlagi prehodov med spremenljivkami q in D 1 q in vzbujevalne tabele za T pomnilno celico, lahko dolo imo vrednosti, ki morajo biti na vhodu t pri posamezni kombinaciji vhodnih spremenljivk: q x D 1 q y t 0 0 1 1 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 4. Na podlagi pravilnostne tabele lahko s pomo jo Veitchevega diagrama izpiöemo funkcijo, ki nastopa na vhodu T pomnilne celice in izhodno funkcijo avtomata: q q x 1 0 x 0 1 0 1 0 1 t = x q ‚ xq = x © q y = q e funkcijo na vhodu T pomnilne celice vstavimo v ena bo T pomnilne celice (D 1 q = tq ‚ tq), dobimo funkcijo prehajanja stanj avtomata: D 1 q = ( x © q) q ‚ ( x © q) q = ( x © q) q ‚ ( xÒ q) q Po definiciji velja, da je izhodna rka Moorovega avtomata dolo ena s trenutnim stanjem avtomata. Velja torej, da je izhodno rko pri Moorovem avtomatu vedno mogo e izraziti zgolj s spremenljivkami, ki dolo ajo trenutno stanje avtomata (v naöem primeru y = q). Realizacijo avtomata v Logisimu prikazuje slika 10.1. 66 Poglavje 10 Priprava na 10. laboratorijske vaje Slika 10.1 Realizacija avtomata iz zgleda v Logisimu. Zgled 33 Z uporabo D pomnilnih celic realiziraj Moorov avtomat, podan s tabelo z 1 z 2 z 3 S 1 S 2 S 3 x 1 S 1 S 1 S 1 x 2 S 2 S 3 S 2 Reöitev 33 Postopek je slede : 1. Za zapis dveh rk vhodne abecede je dovolj ena vhodna spremenljivka (x). Ker ima izhodna abeceda tri rke, za njen zapis potrebujemo dve spremenljivki (y 1 in y 2 ). Ker imamo tri notranja stanja avtomata, sta za njegovo realizacijo potrebni dve pomnilni celici D z notranjimi stanji q 1 in q 2 . Kodirne tabele so torej q y x 1 q 2 1 y 2 S z x 1 0 0 1 0 0 1 0 S z x 2 0 1 2 0 1 2 1 S 3 1 0 z 3 1 0 2. Zapiöemo pravilnostno tabelo avtomata (ko je q 1 = 1 in q 2 = 1 , funkcijska vrednost ni dolo ena): q 1 q 2 x D 1 g 1 D 1 g 2 y 1 y 2 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 1 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 1 1 0 1 1 0 ? ? ? ? 1 1 1 ? ? ? ? 10.1 Realizacija kon nih avtomatov s pomnilnimi celicami (Moorov avtomat) 67 3. Na podlagi prehodov iz spremenljivke q 1 v D 1 q 1 ter prehodov iz spremenljivke q 2 v D 1 q 2 , lahko dolo imo vrednosti, ki morajo biti na vhodu D pomnilnih celic (pomnilna celica z vhodom d 1 bo hranila notranje stanje q 1 , celica z vhodom d 2 pa q 2 ): q 1 q 2 x D 1 g 1 D 1 g 2 y 1 y 2 d 1 d 2 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 1 1 0 0 1 1 0 1 0 0 0 0 1 0 0 0 1 0 1 0 1 1 0 0 1 1 1 0 ? ? ? ? ? ? 1 1 1 ? ? ? ? ? ? 4. Dolo imo funkcije za realizacijo: q q 1 1 q q 2 ? ? 1 0 2 ? ? 0 0 0 0 0 0 0 1 1 0 x x d 1 = q 2 x d 2 = q 2 x q q 1 1 q q 2 ? ? 0 0 2 ? ? 1 1 1 1 0 0 0 0 0 0 x x y 1 = q 1 y 2 = q 2 Realizacijo avtomata v Logisimu prikazujejo slike 10.2, 10.3(a) in 10.3(b). 68 Poglavje 10 Priprava na 10. laboratorijske vaje Slika 10.2 Realizacija avtomata iz zgleda v Logisimu. Zaradi sploönosti sheme sta funkciji, ki vstopata v pomnilni celici D, umeö eni v lo ena modula (glej sliki 10.3(a) in 10.3(b)). (a) (b) Slika 10.3 Realizacija preklopne funkcije, ki vstopa v D pomnilno celico z vhodom d 1 (a) in preklopne funkcije, ki vstopa v D pomnilno celico z vhodom d 2 (b). 11 Priprava na 11. laboratorijske vaje 11.1 Realizacija kon nih avtomatov s pomnilnimi celicami (Mealyjev avtomat) Obnaöanje Moorovega avtomata je ûe v osnovi sinhrono. Stanje avtomata se v odvisnosti od vhodne rke spremeni le ob urini fronti. Ker je izhodna rka neposre- dno odvisna le od njegovega stanja, se ta sinhrono spremeni ob spremembi stanja avtomata. Za razliko od Moorovega avtomata je pri Mealyjevem avtomatu izhodna rka neposredno odvisna od stanja avtomata in vhodnih spremenljivk. To pomeni, da se v primeru spremembe vhodne spremenljivke, izhodna rka lahko spremeni asinhrono (spremeni se v trenutku spremembe vhodne spremenljivke in ne le ob urini fronti oziroma spremembi stanja avtomata). Tako obnaöanje ni dovoljeno in zahteva eksplicitno sinhronizacijo izhodne rke. To najenostavneje doseûemo tako, da izhodno vezje (realizacijo izhodne funkcije) veûemo na vhode D pomnilnih celic (pri realizaciji Mealyjevega avtomata z n izhodnimi rkami torej potrebujemo öe Álog2( n)Ë dodatnih D pomnilnih celic). S tem doseûemo, da se izhodna rka spremeni ob urini fronti, torej sinhrono s spremembo stanja avtomata. Realizacija Mealyjevega avtomata je zelo podobna realizaciji Moorovega avtomata. Ponazorili jo bomo z zgledom, ki sledi. Zgled 34 Realiziraj Mealyjev avtomat, ki je podan s tabelo prehajanja stanj. Za realizacijo notranjih stanj imaö na voljo T pomnilne celice, za generiranje izhodne rke pa D pomnilne celice. S 1 S 2 S 3 x 1 S 2 /z 1 S 2 /z 2 S 1 /z 1 x 2 S 1 /z 2 S 3 /z 1 S 3 /z 2 Reöitev 34 Postopek je slede : 1. Zapiöemo kodirne tabele, ki dolo ijo kodiranje vhodne abecede, notranje abecede in izhodne abecede. Za zapis vseh rk vhodne abecede je dovolj 1 vhodna 69 70 Poglavje 11 Priprava na 11. laboratorijske vaje spremenljivka (x); prav tako je za zapis vseh rk izhodne abecede dovolj 1 izhodna spremenljivka (y). Ker imamo tri notranja stanja avtomata, za njegovo realizacijo potrebujemo 2 pomnilni celici T z notranjimi stanji q 1 in q 2 . Kodirne tabele so torej q x 1 q 2 y S x 1 0 0 1 0 z S 1 0 x 2 0 1 2 1 z S 2 1 3 1 0 2. Na podlagi kodirnih tabel in podanega diagrama prehajanja stanj lahko zapi- öemo pravilnostno tabelo avtomata. Pri tem na levi strani tabele nastopajo spremenljivke, ki dolo ajo trenutno notranje stanje avtomata (q 1 in q 2 ) in vhodno rko (x), na desni pa spremenljivke, ki dolo ajo notranje stanje (D 1 q 1 in D 1 q 2 ) in izhodno rko (D 1 y) v naslednjem asovnem koraku. Vrednosti izhodne rke dolo amo na podlagi prehodov med stanji. q 1 q 2 x D 1 q 1 D 1 q 2 D 1 y 0 0 0 0 1 0 0 0 1 0 0 1 0 1 0 0 1 1 0 1 1 1 0 0 1 0 0 0 0 0 1 0 1 1 0 1 1 1 0 ? ? ? 1 1 1 ? ? ? 3. Na podlagi prehodov med spremenljivkami q 1 in D 1 q 1 ter q 2 in D 1 q 2 in vzbujevalne tabele za T pomnilno celico, lahko dolo imo vrednosti, ki morajo biti na vhodih T pomnilnih celic (t 1 in t 2 ). Poleg tega dolo imo tudi vhode v D pomnilno celico, ki sluûi sinhronizaciji izhodne rke. 11.1 Realizacija kon nih avtomatov s pomnilnimi celicami (Mealyjev avtomat) 71 q 1 q 2 x D 1 q 1 D 1 q 2 D 1 y t 1 t 2 d 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 0 1 0 1 0 0 1 1 0 0 1 0 1 1 1 0 0 1 1 0 1 0 0 0 0 0 1 0 0 1 0 1 1 0 1 0 0 1 1 1 0 ? ? ? ? ? ? 1 1 1 ? ? ? ? ? ? 4. Na podlagi pravilnostne tabele lahko s pomo jo Veitchevega diagrama izpiöemo funkciji, ki nastopata na vhodih T pomnilnih celic in D pomnilne celice avtomata: q q 1 1 q q 2 ? ? 1 0 2 ? ? 1 0 1 0 0 0 0 0 0 1 x x t 1 = q 1 x ‚ q 2 x t 2 = xq 2 ‚ x q 1 q 2 q1 q2 ? ? 0 1 0 1 1 0 x d = xq 2 ‚ xq 2 = xÒ q 2 Pri tem izhod iz D pomnilne celice realizira izhodno rko avtomata. Po definiciji velja, da je izhodna rka Mealyjevega avtomata dolo ena s trenutnim stanjem in vhodno rko avtomata. Velja torej, da za realizacijo funkcije izhodne rke (funkcija, ki vstopa na vhodu D pomnilne celice) v sploönem potrebujemo tako spremenljivke, ki dolo ajo trenutno stanje avtomata kot tudi spremenljivke, ki dolo ajo vhodne rke avtomata. Realizacijo avtomata v Logisimu prikazujejo slike 11.1, 11.2(a), 11.2(b) in 11.2(c). 72 Poglavje 11 Priprava na 11. laboratorijske vaje Slika 11.1 Realizacija avtomata v Logisimu. Zaradi preglednosti sta funkciji, ki vstopata v pomnilni celici T in izhodna funkcija realizirane v lo enih modulih (glej slike 11.2(a), 11.2(b) in 11.2(c). (a) (b) (c) Slika 11.2 Realizacija preklopne funkcije, ki vstopa v T pomnilno celico z vhodom t 1 (a), preklopne funkcije, ki vstopa v T pomnilno celico z vhodom t 2 (b) in izhodne funkcije avtomata (c). 12 Dodatna vaja 12.1 Realizacija preprostega procesorja Z gradniki, ki smo jih spoznali, se bomo lotili izdelave preprostega procesorja. Procesor je hipoteti en in izjemno poenostavljen, v osnovi pa je njegovo delovanje vseeno enako, kot delovanje kompleksnejöih procesorjev. 12.2 Osnovno delovanje procesorja Predpostavljamo, da naö procesor vsak ukaz izvröi v dveh urinih periodah. Procesor torej deluje v dveh stopnjah, in sicer: • prevzem ukaza (angl. Instruction Fetch, IF), • izvedba ukaza (angl. Execute, EX). V nadaljevanju je opisana posamezna stopnja. Procesor lahko postavimo v za etno stanje (t.j. prevzem ukaza) z Reset vhodom. 12.2.1 Prevzem ukaza V prvi urini periodi se iz pomnilnika, ki vsebuje sekvenco ukazov, t.i. ukaznega pomnilnika, prebere ukaz. Pomnilnik vsebuje ve ukazov, pri emer se vsak ukaz nahaja na svojem naslovu. Naslov iz katerega se bere trenutni ukaz je shranjen v registru, ki ga imenujemo programski ötevec (angl. Program Counter). Prebrani ukaz se shrani v ukazni register (angl. Instruction Register), kjer po aka na izvedbo, ki se izvröi v naslednji urini periodi - v stopnji izvedba ukaza. Ko je ukaz zapisan v ukazni register, se lahko programski ötevec pove a. S tem doseûemo, da bo v naslednji stopnji, t.j. prevzem ukaza, prevzet naslednji ukaz iz ukaznega pomnilnika. Zaporedje ukazov v ukaznem pomnilniku tako sestavlja program, ki ga naö procesor izvaja. 73 74 Poglavje 12 Dodatna vaja 12.2.2 Izvedba ukaza Stopnja izvedba ukaza izvede ukaz, ki je zapisan v ukaznem registru. Pri naöem procesorju je to lahko branje ali pisanje v pomnilnik ali aritmeti no-logi ni operaciji: seötevanje in odötevanje. Izvedba ukaza se izvröi tako, da kontrolna enota ukaz, ki je zapisan v ukaznem registru najprej dekodira (posamezen ukaz ima svojo kodo, ki je enoli no dolo ena s sekvenco bitov). V skladu z dekodiranim ukazom kontrolna enota dolo i vrednosti t.i. kontrolnih signalov, ki sluûijo kot vhodi v ostale komponente, ki opravijo dejansko izvedbo ukaza. V naöem primeru lahko kontrolno enoto predstavimo z Mealyjevim avtomatom z dvema stanjema in sedmimi razli nimi prehodi med njima (glej Sliko 12.1). Avtomat v vsaki urini periodi preide iz stanja IF v stanje EX (razen v primeru aktivnosti vhoda Reset). Medtem, ko je iz stanja IF v stanje EX moûen le en prehod (prevzem ukaza), lahko prehod iz stanja EX v stanje IF kontrolna enota izvede preko petih prehodov – izbira prehoda je odvisna od ukaza, ki ga je procesor prevzel pri prehodu kontrolne enote iz stanja IF v stanje EX. 12.3 Osnovna arhitektura procesorja Procesor je v naöem primeru sestavljen iz slede ih komponent: • sploöno namenski registri ( A in B), • programski ötevec (angl. Program Counter, PC ), • ukazni register (angl. Instruction Register, IR), • kontrolna enota (angl. Control Unit, CU ), • aritmeti no logi na enota (angl. Arithmetic Logic Unit, ALU ), • ukazni pomnilnik (angl. Instruction Memory, IM ), • podatkovni pomnilnik (angl. Data Memory, DM ), • ostala kombinatorna logika. Posamezna komponenta je podrobneje opisana v nadaljevanju. 12.3.1 Sploöno namenski registri Aritmeti no logi na enota izvaja aritmeti no logi ne operacije (oziroma v naöem primeru zgolj aritmeti ne operacije) nad podatki, ki so shranjeni v pomnilniku. Rezultati teh operacij se morajo slej ko prej zapisati nazaj v pomnilnik. Sploöno 12.3 Osnovna arhitektura procesorja 75 namenski registri sluûijo kot vmesnik med pomnilnikom in aritmeti no logi no enoto, saj aritmeti no logi na enota ne more neposredno dostopati do podatkov zapisanih v pomnilniku. Sploöno namenski registri se torej uporabljajo za shranjevanje vmesnih rezultatov aritmeti no logi nih operacij. V naöem primeru bomo imeli 2 2-bitna sploöno namenska registra. Imenujemo ju register A in register B. Aritmeti ne operacije (seötevanje in odötevanje) lahko torej delamo nad dvema 2-bitnima podatkoma. 12.3.2 Programski ötevec V stopnji prevzem ukaza se iz ukaznega pomnilnika prebere ukaz. Ukaz se zatem shrani v ukazni register. Pomnilniöki naslov iz katerega se prebere ukaz, je zapisan v registru, ki mu re emo programski ötevec. V naöem primeru je programski ötevec 2-bitni register. Naslavljamo lahko torej 4 pomnilniöke lokacije - maksimalna dolûina programa v ukaznem pomnilniku so 4 ukazi. 12.3.3 Ukazni register V ukazni register se shrani ukaz, ki je bil prebran iz ukaznega pomnilnika v stopnjo prevzem ukaza. Na podlagi vsebine ukaznega registra v stopnji izvedba ukaza kontrolna enota dolo i vrednosti kontrolnih signalov. Kontrolni signali sluûijo kot vhodi v ostale komponente, ki opravijo dejansko izvedbo ukaza. V naöem primeru je ukazni register 4-bitni register. Naö procesor torej podpira 4-bitne ukaze. 12.3.4 Kontrolna enota Kontrolna enota skrbi za izvedbo prevzema naslednjega ukaza in njegovo izvedbo. V skladu s trenutno stopnjo izvedbe ukaza in trenutnim ukazom dolo i vrednosti kontrolnih signalov, ki sluûijo kot vhodi v ostale komponente, ki opravijo dejanski prevzem in izvedbo ukaza. Kontrolno enoto lahko predstavimo z Mealyjevim avtomatom z dvema stanjema in sedmimi razli nimi prehodi med njima (glej Sliko 12.1). Kontrolna enota ima torej dve stanji, tj. stanje IF, ki je aktivno, ko je procesor v stopnji prevzem ukaza in stanje EX, ki je aktivno, ko je procesor v stopnji izvedba ukaza. Kot vhodne rke procesor sprejema Reset vhod in vsebino ukaznega registra (IR). Kontrolna enota dolo a vrednosti izhodnih signalov, ki so hkrati njene izhodne rke, na slede na in: • IF: izhodna rka je aktivna pri prehodu iz stanja IF v stanje EX. V tem primeru kontrolna enota sproûi nalaganje naslednjega ukaza v ukazni register ( IR Ω IM[ PC]) in pove anje vrednosti programskega ötevca ( PC Ω PC+1). 76 Poglavje 12 Dodatna vaja ≠ /IF Reset/≠ IR = LOAD A/LOAD A IF EX IR = LOAD B/LOAD B IR = ST ORE A/ST ORE A IR = ADD/ADD IR = SU B/SU B Slika 12.1 Mealyjev avtomat kontrolne enote procesorja. • LOAD A: izhodna rka je aktivna pri prehodu iz stanja EX v stanje IF pri pogoju, da je v ukaznem registru ukaz LOAD A. V tem primeru kontrolna enota sproûi nalaganje podatka iz podatkovnega pomnilnika (DM) v register A. Pri tem je pomnilniöki naslov dolo en s spodnjima bitoma ukaznega pomnilnika ( A Ω DM[ IR[1 .. 0]]). • LOAD B: izhodna rka je aktivna pri prehodu iz stanja EX v stanje IF pri pogoju, da je v ukaznem registru ukaz LOAD B. V tem primeru kontrolna enota sproûi nalaganje podatka iz podatkovnega pomnilnika (DM) v register B. Pri tem je pomnilniöki naslov dolo en s spodnjima bitoma ukaznega pomnilnika ( B Ω DM[ IR[1 .. 0]]). • STORE A: izhodna rka je aktivna pri prehodu iz stanja EX v stanje IF pri pogoju, da je v ukaznem registru ukaz STORE A. V tem primeru kontrolna enota sproûi nalaganje vsebine registra A v podatkovni pomnilnik (DM), in sicer na naslov, ki je dolo en s spodnjima bitoma ukaznega pomnilnika ( DM[ IR[1 .. 0]] Ω A). • ADD: izhodna rka je aktivna pri prehodu iz stanja EX v stanje IF pri pogoju, da je v ukaznem registru ukaz ADD. V tem primeru kontrolna enota 12.3 Osnovna arhitektura procesorja 77 sproûi seötevanje vsebine registra A in vsebine registra B, pri emer se rezultat shrani v register A ( A Ω A + B). • SUB: izhodna rka je aktivna pri prehodu iz stanja EX v stanje IF pri pogoju, da je v ukaznem registru ukaz SUB. V tem primeru kontrolna enota sproûi odötevanje vsebine registra B od vsebine registra A, pri emer se rezultat shrani v register A ( A Ω A ≠ B). Realizacijo avtomata kontrolne enote v Logisimu prikazuje slika 12.2. Slika 12.2 Realizacija kontrolne enote v Logisimu s T-pomnilno celico, pri emer moduli LDA, LDB, ST A, ADD in SUB predstavljajo kombinatorno logiko za dolo itev posameznega kontrolnega signala, Instruction pa ukaz, zapisan v ukaznem registru. Simbol, ki se v shemi nahaja pred komponento Instruction, predstavlja komponento, ki ve enobitnih signalov zdruûi v ve bitni vektor. 12.3.5 Aritmeti no logi na enota Aritmeti no logi na enota (angl. Arithmetic Logic Unit, ALU) izvaja aritmeti no logi ne operacije nad sploöno namenskimi registri kot so seötevanje, mnoûenje, deljenje, logi ni pomik itd. V naöem primeru ALU podpira samo dve artimeti ni operaciji, in sicer seötevanje in odötevanje vsebine registrov A in B. Operacija, ki se bo izvedla, je dolo ena s kontrolnim signalom, katerega vrednost na podlagi dekodiranega signala dolo i kontrolna enota. Realizacija ALU v Logisimu je prikazana na sliki 12.3, pri emer sta vhoda A in B izhoda iz sploöno namenskih registrov, vhod SUB pa izhod iz kontrolne enote, ki ima vrednost 1, e je trenutni ukaz odötevanje. Izhod iz aritmeti no logi ne enote dolo a rezultat izvedene operacije. 78 Poglavje 12 Dodatna vaja Slika 12.3 Realizacija aritmeti no logi ne enote v Logisimu, pri emer ADD 2 predstavlja modul za izra un vsote 2-bitnih vhodov, C 2 pa modul za izra un dvojiökega komplementa 2-bitnega vhoda (glej razdelek 12.5.4). Naslovni vhod v multiplekser ( SUB) dolo i ali se bo izra unala vsota ötevil A in B ali vsota ötevila A in dvojiökega komplementa ötevila B. 12.3.6 Ukazni pomnilnik V ukaznem pomnilniku so shranjeni ukazi za izvedbo. Na podlagi podanega naslova se iz ukaznega pomnilnika prebere ukaz za izvedbo. Na sekvenco ukazov v ukaznem pomnilniku lahko tako gledamo kot na program, ki ga bo naö procesor izvajal. V naöem primeru je ukazni pomnilnik realiziran z ROM pomnilnikom, v katerega zapiöemo program pred zagonom procesorja. Na voljo imamo 4 lokacije (program je lahko dolg 4 ukaze). Pomnilnik torej naslavljamo z 2-bitnim naslovom. Ukazi v pomnilniku so dolgi 4 bite. 12.3.7 Podatkovni pomnilnik Podatkovni pomnilnik vsebuje podatke nad katerimi procesor izvaja aritmeti no logi ne operacije. Branje iz podatkovnega pomnilnika poteka preko registrov A in B. V pomnilnik lahko zapisujemo zgolj preko registra A. Prav tako kot pri ukaznem pomnilniku, tudi pri podatkovnem pomnilniku vedno podajamo naslov na katerega zapisujemo podatek oziroma s katerega beremo. V podatkovni pomnilnik lahko shranimo 4 podatke velikosti 2 bita. Naslavljamo ga torej z 2-bitnim naslovom. 12.3.8 Ostala kombinatorna logika To so multiplekserji in ostala kombinatorna logi na vrata. 12.4 Nabor ukazov Procesor podpira izvedbo 5 razli nih ukazov (glej Tabelo 12.1). Posamezen ukaz je dolo en s 4-bitno kodo, ki je shranjena v ukaznem pomnilniku oziroma ukaznem 12.5 Razlaga uporabljenih gradnikov 79 registru. Pri nekaterih ukazih se del te kode uporabi kot naslov za podatkovni pomnilnik. IR(3) IR(2) IR(1) IR(0) ukaz pomen 0 0 x y Load A DM [( x, y)] A Ω DM[( x, y)] 0 1 x y Load B DM [( x, y)] B Ω DM[( x, y)] 1 0 x y Store A DM [( x, y)] DM [( x, y)] Ω A 1 1 0 ? Add A Ω A + B 1 1 1 ? Sub A Ω A ≠ B Tabela 12.1 Seznam in pomen ukazov, ki jih podpira naö procesor. Pri tem DM[( x, y)] predstavlja lokacijo v podatkovnem pomnilniku na 2-bitnem naslovu ( x, y). V nadaljevanju so ukazi podrobneje opisani. 12.4.1 Load A Ukaz Load A v register A naloûi vrednost iz pomnilniökega naslova, ki je dolo en z bitoma IR(1) in IR(0) ukaznega registra. 12.4.2 Load B Ukaz Load B v register B naloûi vrednost iz pomnilniökega naslova, ki je dolo en z bitoma IR(1) in IR(0) ukaznega registra. 12.4.3 Store A Ukaz Store A naloûi vsebino registra A na pomnilniöki naslov, ki je dolo en z bitoma IR(1) in IR(0) ukaznega registra. 12.4.4 Add Ukaz Add seöteje vsebino registrov A in B in jo shrani v register A. 12.4.5 Sub Ukaz Sub odöteje vsebino registra B od vsebine registra A in jo shrani v register A. 12.5 Razlaga uporabljenih gradnikov 12.5.1 Register Register je sinhroni pomnilni element, kar pomeni da omogo a pomnjenje (v n-bitni register lahko shranimo n-bitni podatek), njegova vsebina pa se spreminja sinhrono 80 Poglavje 12 Dodatna vaja – nov podatek lahko v register zapisujemo samo ob dolo eni fronti ure. Registri imajo v naöem primeru slede e vhode • Reset: ob aktivnosti vhoda se vsebina registra postavi na vrednost 0. • Data_in: podatkovni vhod v register. • WE ( Write Enable): e je vhod aktiven se podatek na vhodu Data_in ob urini fronti zapiöe v register. Vsebina registra je na izhodu Data_out. Realizacija 4-bitnega registra v Logisimu je prikazana na sliki 12.4. Slika 12.4 Realizacija 4-bitnega registra v Logisimu z D-pomnilnimi celicami. e so naslovni vhodi v multiplekserje aktivni (z drugimi besedami, e je W E = 1), se stanje registra v naslednji urini periodi zamenja z vhodnim signalom data_in. V nasprotnem primeru se stanje registra ohranja. 12.5.2 Programski ötevec Programski ötevec je v naöem primeru posebna oblika registra s slede ima vhodoma: • Reset: ob aktivnosti vhoda se programski ötevec postavi na 0. • Inc (Increment): e je vhod aktiven se vsebina programskega ötevca ob urini fronti pove a za 1 na na in 0,1,2,3,0,1... 12.5 Razlaga uporabljenih gradnikov 81 Vsebino registra lahko beremo preko izhoda Address, ki sluûi kot naslov za branje ukaza iz ukaznega pomnilnika. Realizacija programskega ötevca v Logisimu je prikazana na sliki 12.5. Slika 12.5 Realizacija 2-bitnega programskega ötevca v Logisimu. Del kombinatorne logike ( XOR vrata in negator) predstavlja realizacijo pove anja vsebine programskega ötevca za 1. e sta naslovna vhoda v multiplekserja ( inc) aktivna, se stanje ötevca v naslednji urini periodi pove a. e nista aktivna, se stanje ohranja. 12.5.3 Seötevalnik Seötevalnik omogo a seötevanje dveh ötevil in je del aritmeti no logi ne enote. V naöem primeru imamo seötevalnik, ki seöteje dve 2-bitni ötevili. 2-bitni seötevalnik realiziramo z vezavo dveh 1-bitnih polnih seötevalnikov. Realizacija 1-bitnega polnega seötevalnika v Logisimu je prikazana na sliki 12.6. Rezultat seötevanja dveh 1-bitnih ötevil a in b in prenosa carry_in gre na izhod sum. Izhod carry_out predstavlja prenos pri seötevanju. 2-bitni seötevalnik lahko realiziramo z vezavo dveh 1-bitnih polnih seötevalnikov kot prikazuje slika 12.7. Prenos pri seötevanju prvega seötevalnik ( carry_out) uporabimo kot carry_in vhod v drugi seötevalnik. 82 Poglavje 12 Dodatna vaja Slika 12.6 Realizacija 1-bitnega polnega seötevalnika v Logisimu. Slika 12.7 Realizacija 2-bitnega seötevalnika v Logisimu. Modula ADD 1 predstavljata 1-bitna polna seötevalnika. 12.5.4 Odötevalnik Ker velja, da je odötevanje enako priötevanju negativnega ötevila ( a ≠ b = a+(≠ b)), lahko pri realizaciji odötevalnika uporabimo seötevalnik, pri emer seötevamo ötevili a in ≠ b. V ta namen, moramo realizirati vezje, ki izra una negativno vrednost ötevila b. Negativno vrednost dobimo s t.i. dvojiökim komplementom, ki ga lahko izra unamo z uporabo slede e ena be ≠ b = b + 1 Vezje za izra un dvojiökega komplementa prikazuje slika 12.8. 12.5.5 Read Only Memory (ROM) ROM pomnilnik je pomnilnik iz katerega lahko programsko zgolj beremo. V naöem primeru vanj pred za etkom izvajanja ro no zapiöemo program. 12.6 Realizacija opisanega procesorja 83 Slika 12.8 Realizacija vezja za izra un dvojiökega komplementa v Logisimu. Modul ADD 2 predstavlja 2-bitni seötevalnik. Dvojiöki komplement izra unamo tako, da negirani vrednosti vhodnega signala b priötejemo 1. Vsebino ROM pomnilnika beremo tako, da na vhod A ( Address) pripeljemo naslovni signal. Na izhodu D ( Data) dobimo podatek, ki je zapisan na naslovu A. Z n-bitnim naslovom lahko naslavljamo 2 n lokacij. V Logisimu mora biti pomnilnik za uporabo omogo en. Omogo imo ga tako, da na sel ( Select) vhod pripeljemo konstanto 1. 12.5.6 Random Access Memory (RAM) RAM pomnilnik je pomnilnik v katerega lahko tako piöemo kot tudi beremo. Pri pisanju v pomnilnik podamo podatek, ki ga ûelimo zapisati in naslov, na katerega ûelimo pisati. Pri branju iz pomnilnika podamo naslov, iz katerega beremo. Pri uporabi RAM pomnilnika v Logisimu moramo upoötevati slede e vhode: • A ( Address): naslov iz katerega beremo oziroma na katerega piöemo. Z n-bitnim naslovom lahko naslavljamo 2 n lokacij. • D ( Data in): podatek, ki ga zapisujemo v pomnilnik. • str ( Store): podatek na vhodu D se shrani v pomnilnik ob fronti ure, e je aktiven vhod str. • sel ( Select): pomnilnik omogo imo tako, da na sel vhod pripeljemo konstanto 1. • ld ( Load): podatek na naslovu A gre na izhod pomnilnika D ( Data out) ob fronti ure samo, e je aktiven vhod ld. Iz pomnilnika beremo preko izhoda D ( Data out), tako da aktiviramo vhodni signal ld. Podatek se pojavi na izhodu ob fronti ure. 12.6 Realizacija opisanega procesorja Z ustrezno vezavo opisanih komponent lahko v Logisimu realiziramo preprost procesor. Realizacijo opisanega procesorja v Logisimu prikazuje slika 12.9. 84 Poglavje 12 Dodatna vaja Slika 12.9 Realizacija preprostega procesorja v Logisimu. 12.7 Zgled delovanja procesorja Zgled 35 V ukazni pomnilnik procesorja v Logisimu bomo zapisali program, ki se- öteje ötevili, ki sta zapisani na pomnilniökih naslovih 0 in 1 podatkovnega pomnilnika in rezultat zapiöe na pomnilniöki naslov 2. Najprej bomo program zapisali s t.i. mnemoniki: Load A 0 Load B 1 Add Store A 2 S pomo jo tabele 12.1 lahko ukaze zapiöemo v dvojiöki obliki: 0000 0101 1100 1010 Ukaze vnesemo v ukazni pomnilnik (ROM) v öestnajstiöki obliki: 12.7 Zgled delovanja procesorja 85 05CA A Slovensko-angleöki slovar osnovnih pojmov Osnove • preklopna funkcija: logic function • pravilnostna tabela: truth table • funkcijska vrednost: value of the function • vhodni vektor: input vector • logi na shema: logic scheme • logi na vrata: logic gates • spremenljivka: variable • vhod: input • izhod: output • in: and • ali: or • mnoûica: set • seötevanje: addition Standardne oblike zapisa • PDNO (popolna disjunktivna normalna oblika): full disjunctive normal form (FDNF) • DNO (disjunktivna normalna oblika): disjunctive normal form (DNF), also sum of products (SOP) • PKNO (popolna konjunktivna normalna oblika): full conjunctive normal form (FCNF) 87 88 Dodatek A Slovensko-angleöki slovar osnovnih pojmov • KNO (konjunktivna normalna oblika): conjunctive normal form (DNF), also product of sums (POS) • skrajöana oblika zapisa: compact notation • eksplicitna oblika zapisa: explicit notation • Veitchev diagram: Veitch diagram, its variation is known as Karnaugh map (K-map) Funkcijska polnost • funkcijsko poln sistem/nabor: functional complete set • funkcijska polnost: functional completeness • prevedba na znan funkcijsko poln sistem: proving the functional completeness of a set of functions by showing they can express all functions in already known functional complete set • osnovni zaprti razredi: important closed classes of functions (see also Post’s Functional Completeness Theorem) • ohranjanje ni le ( T 0): functions that preserve zero • ohranjanje enice ( T 1): functions that preserve one • linearna funkcija: linear function • monotona funkcija: monotone function • sebidualna funkcija: self-dual function • sosednja vektorja: adjacent vectors Minimizacija • MDNO (minimalna disjunktivna normalna oblika): minimal disjunctive normal form (MDNF), also minimum sum-of-products expression • MKNO (minimalna konjunktivna normalna oblika): minimal conjunctive normal form (MDNF), also minimum product-of-sums expression • MNO (minimalna normalna oblika): minimal normal form (MNF) • sosednja minterma: adjacent minterms Dodatek A Slovensko-angleöki slovar osnovnih pojmov 89 • sosednji polji: adjacent cells • vsebovalnik: implicant • glavni vsebovalnik: prime implicant • potrebni glavni vsebovalnik: essential prime implicant • pokritje: coverage, also loop on the diagram • nepopolna preklopna funkcija: incompletely specified function (includes don’t care values/symbols, i.e. ?) • Quineova metoda: Quine (also Quine-McCluskey) method Simteri ne funkcije • simetri na funkcija: symmetric function • popolnoma simetri na funkcija: totally symmetric function Multiplekserji • multiplekser: multiplexer • Shannonov teorem: Shannon expansion or Shannon decomposition (also Boole’s expansion theorem) • funkcijski ostanek: cofactor • funkcijski ostanek funkcije po x: cofactor of the function with respect to x • lo enje: decomposition • podatkovni vhodi: data inputs • naslovni vhodi: select inputs or address inputs Sekven na vezja • pomnilnik: memory • sinhrona sekven na logika: synchronous sequential logic • urin signal: clock signal 90 Dodatek A Slovensko-angleöki slovar osnovnih pojmov • pomnilna celica: flip-flop • stanje: state • karakteristi na tabela: characteristic table • vzbujevalna tabela: excitation table • trava: glitches • zdrs ure: clock skew Avtomati • (kon ni deterministi ni) avtomat: finite state machine (also finite state automaton) • stanje: state • rka: character • beseda: sequence of characters • vhodna abeceda: input alphabet (finite non-empty set of symbols) • notranja abeceda: internal alphabet (finite, non-empty set of states) • izhodna abeceda: output alphabet (finite, non-empty set of symbols) • funkcija prehajanja (notranjih) stanj: state-transition function • izhodna funkcija: output function • Moorov avtomat: Moore machine • Mealyjev avtomat: Mealy machine • diagram prehajanja stanj: state diagram • tabela prehajanja stanj: state transition table • kodirna tabela: coding table Literatura [1] Iztok Lebar Bajec. Preklopne strukture in sistemi: zbirka reöenih primerov in nalog z reöitvami. Zaloûba FE in FRI, Ljubljana, 2002. [2] Ronald J. Tocci, Neal Widmer, and Greg Moss. Digital Systems: Principles and Applications (11th Edition). Pearson, 2010. [3] Mira Trebar. Preklopna vezja in strukture: priro nik za vaje (2. izdaja). Zaloûba FE in FRI, Ljubljana, 1992. [4] Jernej Virant. Logi ne osnove odlo anja in pomnjenja v ra unalniökih sistemih. Zaloûba FE in FRI, Ljubljana, 1996. 91