4 Дигитална логика
У поглављу о исказном рачуну видели смо да бинарних операција, тј. Булових функција две променљиве, има 16 (табела 3.2). Од њих смо за везнике изабрали конјункцију, дисјункцију, импликацију и еквиваленцију, и то из једног разлога: оне одговарају речима „и“, „или“, „ако … онда“ и „ако и само ако“, којима закључујемо у свакодневном говору. Тај избор условљен је језиком, а не математиком.
У дигиталном свету не мора да буде тако. Рачунар не говори, већ рачуна помоћу кола направљених од прекидача, па је за њега „најприроднија“ она операција коју је најлакше и најјефтиније физички направити. Видећемо да то нису ни конјункција ни дисјункција, већ њихове негације — NAND (Шеферова функција \(\uparrow\)) и NOR (Пирсова стрелица \(\downarrow\)). Свака од њих је сама довољна да се изрази било која Булова функција, па се од једне врсте кола може изградити цео процесор.
У овом поглављу пратимо тај пут: од потпуних скупова везника, преко прекидача и универзалних логичких кола, до сабирача и меморије.
Потпуни скупови везника
Колико нам од 16 бинарних операција заиста треба? Видели смо да свака Булова функција има СДНФ, у којој се појављују само \(\neg\), \(\land\) и \(\lor\), па нам остале операције, строго говорећи, нису ни потребне. Можемо ли са још мање?
Дефиниција 4.1 (Потпун скуп везника) Скуп логичких операција је потпун ако се свака Булова функција може изразити формулом у којој се појављују само операције из тог скупа.
Теорема 4.1 Скупови \(\{\neg, \land, \lor\}\), \(\{\neg, \land\}\), \(\{\neg, \lor\}\), \(\{\uparrow\}\) и \(\{\downarrow\}\) су потпуни.
Доказ. Скуп \(\{\neg, \land, \lor\}\) је потпун по теореми 3.2, јер СДНФ користи само ове три операције (нула-функција се може записати као \(p \land \neg p\)). Дисјункцију можемо изразити помоћу \(\neg\) и \(\land\), а конјункцију помоћу \(\neg\) и \(\lor\) (Де Морганови закони): \[ p \lor q \equiv \neg(\neg p \land \neg q), \qquad p \land q \equiv \neg(\neg p \lor \neg q), \] па су потпуни и скупови \(\{\neg, \land\}\) и \(\{\neg, \lor\}\). Коначно, помоћу Шеферове функције изражавамо негацију и конјункцију, а помоћу Пирсове стрелице негацију и дисјункцију: \[ \neg p \equiv p \uparrow p, \quad p \land q \equiv (p \uparrow q) \uparrow (p \uparrow q), \qquad \neg p \equiv p \downarrow p, \quad p \lor q \equiv (p \downarrow q) \downarrow (p \downarrow q). \]
Скуп \(\{\neg, \land, \lor\}\) је, дакле, само један од могућих избора — онај на који нас је навикао језик. Математички је довољна и једна једина операција, \(\uparrow\) или \(\downarrow\). Видећемо да је управо то кључно за технику.
Логичка кола
Дигитална логика бави се пројектовањем кола која рачунају. Док у исказном рачуну радимо са апстрактним вредностима 0 и 1, у дигиталним системима оне добијају физички облик — најчешће висок напон представља логичку јединицу (1), а низак напон логичку нулу (0). Свака Булова функција тако може бити остварена физичким склопом — логичким колом. Ова кола су основни градивни блокови свих дигиталних уређаја, од калкулатора до најмоћнијих процесора.
Клод Шенон (Claude Shannon) је 1937. године у свом мастер раду показао да се прекидачка и релејна кола могу описати и пројектовати помоћу Булове алгебре. Тај рад се сматра почетком пројектовања дигиталних кола.
Прекидач као градивни елемент
Основни градивни елемент сваког дигиталног рачунара је прекидач: елемент који пропушта или прекида ток нечега (струје, воде, …). Прекидач на зиду којим палимо светло то ради, али њиме управља прст. За рачунар нам је потребан прекидач са једном кључном особином:
прекидачем се управља истом физичком величином коју он пропушта.
Код електричних кола то је напон: прекидач се затвара када на његов управљачки улаз доведемо висок напон (1), а отвара када доведемо низак напон (0). Захваљујући томе, излаз једног прекидача може да управља следећим прекидачем, па се прекидачи могу надовезивати у произвољно велика кола, без човека који их помера.
Напон није једина могућност. Замислимо цеви са водом и вентил који се отвара када се повећа притисак воде у управљачкој цеви: вода која излази из једног вентила може да отвара или затвара следећи вентил. Од таквих вентила могла би се, у принципу, направити читава рачунска машина — и заиста, шездесетих година прошлог века прављени су логички склопови засновани на протоку течности и гаса (тзв. флуидна логика). За логику није важно шта тече, већ само да се прекидачем управља оним што он пропушта.
NOT, NAND и NOR од прекидача
У савременим чиповима прекидачи су транзистори, и то две врсте које се понашају супротно:
- n-прекидач проводи (затворен је) када је на његовом улазу 1, а не проводи када је 0;
- p-прекидач (на цртежу има кружић на улазу) проводи када је на улазу 0, а не проводи када је 1.
Излаз \(Y\) кола повезује се са високим напоном \(+V\) (вредност 1) преко групе p-прекидача, а са масом (вредност 0) преко групе n-прекидача. Групе су направљене тако да је увек затворен пут тачно до једног од та два краја, па излаз увек има одређену вредност. Овакав начин слагања назива се CMOS (енгл. complementary MOS).
На сликама 4.1, 4.2 и 4.3 свака шема је уцртана у симбол кола који се користи у дигиталној логици. Симбол је „кутија“ која говори само шта коло ради, а транзистори у њој показују како то ради. Када једном знамо да коло ради исправно, унутрашњост више не морамо да цртамо — даље користимо само симбол.
Мењајте улазе и посматрајте који транзистори проводе (p-прекидачи магентом, n-прекидачи тиркизно) и са којим крајем је излаз спојен.
- NOT (Слика 4.1): за \(A = 1\) проводи доњи n-прекидач и излаз је спојен са масом, \(Y = 0\); за \(A = 0\) проводи горњи p-прекидач и \(Y = 1\). Дакле, \(Y = \neg A\).
- NAND (Слика 4.2): n-прекидачи су везани редно, па је излаз спојен са масом само када проводе оба, тј. када је \(A = 1\) и \(B = 1\). p-прекидачи су везани паралелно, па је у свим осталим случајевима излаз спојен са \(+V\). То је функција \(Y = \neg(A \land B)\).
- NOR (Слика 4.3): распоред је обрнут — n-прекидачи су везани паралелно, па је \(Y = 0\) чим је \(A = 1\) или \(B = 1\), а p-прекидачи редно, па је \(Y = 1\) само када је \(A = B = 0\). То је функција \(Y = \neg(A \lor B)\).
Приметимо да свако од ових кола природно даје негацију: n-прекидач спаја излаз са масом баш када је улаз 1. Зато су NOT, NAND и NOR најједноставнија кола која се могу направити — NAND и NOR са по четири транзистора — док је за AND потребан NAND и још један инвертор, дакле шест транзистора. Ова кола можете испробати и у датотеци основна кола у програму Logisim.
Основни симболи дигиталне логике
Основне логичке операције реализују се помоћу логичких кола чији су стандардни симболи приказани у табели 4.1.
| Операција | Симбол | Булов израз | Опис |
|---|---|---|---|
| NOT |  |
\(Y = \neg A\) | Инверзија улаза (негација) |
| AND |  |
\(Y = A \land B\) | Излаз је 1 само ако су сви улази 1 |
| OR |  |
\(Y = A \lor B\) | Излаз је 1 ако је бар један улаз 1 |
| XOR |  |
\(Y = A \oplus B\) | Излаз је 1 ако су улази различити |
| XNOR |  |
\(Y = \neg (A \oplus B)\) | Излаз је 1 ако су улази исти |
| NAND |  |
\(Y = \neg (A \land B)\) | Негација AND функције |
| NOR |  |
\(Y = \neg (A \lor B)\) | Негација OR функције |
Ради једноставнијег приказа сложенијих функција користе се и проширени симболи, за кола са више улаза или са инвертованим улазима (табела 4.2).
| Опис | Симбол |
|---|---|
| NAND коло са три улаза |  |
| NAND са три улаза, први улаз инвертован |  |
| NOR коло са четири улаза |  |
Универзална логичка кола
NAND коло остварује Шеферову функцију, а NOR коло Пирсову стрелицу. По теореми 4.1, скупови \(\{\uparrow\}\) и \(\{\downarrow\}\) су потпуни, па се свака Булова функција може остварити искључиво помоћу NAND кола, или искључиво помоћу NOR кола. Зато их зовемо универзална логичка кола.
Ова два резултата — математички (NAND и NOR су потпуни) и технички (NAND и NOR се најлакше праве од прекидача) — заједно објашњавају зашто су NAND и NOR толико важни: целокупна логика једног чипа може се изградити умножавањем само једне врсте једноставног градивног блока. То знатно поједностављује пројектовање и производњу; по NAND колима је, на пример, добила име и NAND флеш меморија у USB меморијама и SSD дисковима.
Исти принцип, нове технологије
Прекидач са описаном особином остварен је кроз историју на више начина. Свака нова генерација била је мања, бржа и трошила је мање енергије од претходне:
| Генерација | Прекидач | Пример |
|---|---|---|
| 1930-е и 1940-е | електромеханички релеј — струја кроз калем покреће метални контакт | рачунар Z3 Конрада Цузеа (1941), око 2 600 релеја |
| 1940-е и 1950-е | електронска (вакуумска) цев | ENIAC (1945), око 17 500 цеви |
| од 1950-их | транзистор (изумљен 1947. године) | рачунари са појединачним транзисторима |
| од 1960-их | интегрисано коло — много транзистора на једној плочици силицијума | процесор Intel 4004 (1971), око 2 300 транзистора |
| данас | транзистори величине неколико нанометара | процесори са десетинама милијарди транзистора |
Промене су огромне: релеј се пребацује за неколико милисекунди, а савремени транзистор за делић наносекунде. Ипак, начин на који се прекидачи слажу у NAND, NOR и остала кола, и начин на који се од њих састављају Булове функције, остао је у својој сржи исти.
Ту је јасна подела посла. Усавршавање самог прекидача ствар је технологије — физике, хемије и електротехнике. Дигитална логика се бави оним што остаје исто кроз све генерације: како се прекидачи и логичка кола слажу да би остварили задату Булову функцију. Зато знање које стичемо у овом поглављу не застарева са сваком новом генерацијом рачунара.
Кола која рачунају: сабирачи
Полусабирач
Пример 4.1 Полусабирач је коло које сабира два бита \(A\) и \(B\) и даје збир \(S\) и пренос \(C\) (бит који се „преноси“ у следећи разред, као при сабирању бројева на папиру):
| \(A\) | \(B\) | \(S\) | \(C\) |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
Из таблице читамо да је \(S = A \oplus B\) и \(C = A \land B\), па се полусабирач састоји од једног XOR и једног AND кола (слика 4.4):
Кликом на улазе \(A\) и \(B\) проверите све четири врсте таблице.
Повезивањем оваквих кола добијају се сабирачи вишецифрених бинарних бројева, а они су део аритметичко-логичке јединице сваког процесора.
Потпуни сабирач
Полусабирач сабира само два бита. Када сабирамо вишецифрене бинарне бројеве, у сваком разреду осим најнижег сабирамо три бита: по један бит оба сабирка и пренос из претходног разреда — исто као при сабирању бројева на папиру. Коло које то ради назива се потпуни сабирач. Његови улази су битови \(A\) и \(B\) и улазни пренос \(C_{ул}\), а излази збир \(S\) и излазни пренос \(C_{из}\): \[ S = A \oplus B \oplus C_{ул}, \qquad C_{из} = (A \land B) \lor \big(C_{ул} \land (A \oplus B)\big). \]
| \(A\) | \(B\) | \(C_{ул}\) | \(S\) | \(C_{из}\) |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Потпуни сабирач се саставља од два полусабирача и једног OR кола (слика 4.5): први полусабирач сабира \(A\) и \(B\), други додаје улазни пренос, а излазни пренос је 1 ако је пренос настао у било ком од њих. Полусабирач више не цртамо преко појединачних кола, већ као блок са два улаза и излазима \(S\) и \(C\) — као што смо CMOS кола сакрили иза њихових симбола, сада полусабирач сакривамо иза његовог блока.
Кликом на улазе проверите свих осам врста таблице.
Сабирач од 8 бита
Повезивањем осам потпуних сабирача у низ добијамо сабирач два 8-битна броја (слика 4.6). Бит \(i\) оба сабирка улази у \(i\)-ти потпуни сабирач (ПС), а излазни пренос сваког сабирача постаје улазни пренос следећег, вишег разреда. У најнижем разреду улазни пренос је 0. Пренос се тако простире с десна налево, па се овакав сабирач назива сабирач са прослеђивањем преноса (енгл. ripple-carry adder).
Збир два 8-битна броја може бити и 9-цифрен: највећи збир је \(255 + 255 = 510\). Пренос из највишег разреда тада показује да резултат не стаје у 8 бита — то је прекорачење (енгл. overflow).
Кликните на битове сабирака или унесите бројеве од 0 до 255 и пратите како се пренос простире.
Од 8 до 64 бита: удвостручавање
Сабирач од 16 бита не морамо да пројектујемо изнова: довољно је два 8-битна сабирача повезати тако да излазни пренос нижег бајта постане улазни пренос вишег (слика 4.7).
На исти начин два 16-битна сабирача дају 32-битни, а два 32-битна 64-битни сабирач. Ширина са којом процесор ради — дужина речи — кроз историју се управо тако удвостручавала:
| Дужина речи | Пример процесора | Година |
|---|---|---|
| 4 бита | Intel 4004 | 1971. |
| 8 бита | Intel 8080 | 1974. |
| 16 бита | Intel 8086 | 1978. |
| 32 бита | Intel 80386 | 1985. |
| 64 бита | AMD64 (Opteron, Athlon 64) | 2003. |
Ширине су степени двојке зато што се сви подаци у рачунару мере бајтовима (8 бита), а удвостручавање значи да се исти блок само понови још једном — као код сабирача. На 64 бита се за сада стало (табела 4.3): са 64 бита може се записати \(2^{64} \approx 1{,}8 \cdot 10^{19}\) различитих вредности, што је довољно и за адресирање меморије и за готово све целе бројеве који се у пракси јављају. За рад са већом количином података процесори имају посебне векторске јединице које у једном кораку обрађују 128, 256 или 512 бита, али то је више 64-битних (или мањих) операција истовремено, а не шира реч.
Треба још рећи да прави процесори не користе сабирач са прослеђивањем преноса, јер пренос кроз 64 разреда путује споро. Уместо тога користе сложеније сабираче са предвиђањем преноса (енгл. carry-lookahead), који преносе израчунавају унапред, али су изграђени од истих логичких кола.
Језгра процесора
Сличан принцип — више копија истог блока — примењује се и на процесор у целини: један чип данас садржи више језгара, од којих је свако потпун процесор који може да извршава свој програм. Често их има 2, 4, 8 или 16.
Ако се и језгра удвостручавају, како онда постоје процесори са 3 или 5 језгара? Разлика је у томе што ширина речи мора да се уклопи у бинарни запис (бајтове, адресе, регистре), а језгра су независни блокови који се не „сабирају“ бит по бит. Њих може бити колико год се произвођачу исплати — одлучују површина чипа, потрошња енергије и цена. Произвођачи често направе чип са више језгара, па она неисправна искључе и продају га као јефтинији модел: процесор AMD Phenom X3 са 3 језгра настао је од четворојезгарног чипа са једним искљученим језгром. Данас су уобичајени и процесори са 6, 10, 12 или 14 језгара, а процесори у мобилним телефонима често комбинују „јака“ и „штедљива“ језгра у различитом броју.
Кола која памте
Флип-флоп: коло које памти
Сва досадашња кола била су комбинациона: излаз зависи само од тренутних вредности улаза. Рачунар мора и да памти, а за то је потребна повратна веза — излаз кола враћа се на његов улаз.
Најједноставније коло које памти један бит је SR флип-флоп (SR реза) од два NOR кола чији је излаз сваког повезан на улаз другог (слика 4.8). Улаз \(S\) (енгл. set) поставља излаз \(Q\) на 1, а улаз \(R\) (енгл. reset) га брише на 0:
| \(S\) | \(R\) | \(Q\) |
|---|---|---|
| 0 | 0 | не мења се (коло памти) |
| 1 | 0 | 1 (постављање) |
| 0 | 1 | 0 (брисање) |
| 1 | 1 | забрањена комбинација |
Кључна је прва врста. Ако је \(S = R = 0\) и \(Q = 1\), доње коло даје \(\overline{Q} = \neg(0 \lor 1) = 0\), а горње \(Q = \neg(0 \lor 0) = 1\) — излази се међусобно одржавају и вредност 1 остаје запамћена. Исто важи и за \(Q = 0\). Комбинација \(S = R = 1\) се не користи, јер оба излаза постају 0, а по њеном престанку стање зависи од тога који се улаз први врати на 0. Исто коло може се направити и од два NAND кола, уз улазе који су активни на 0.
Поставите \(S = 1\), па га вратите на 0: вредност \(Q = 1\) остаје запамћена. Затим исто урадите са \(R\).
Од флип-флопа до меморије
Флип-флоп памти један бит, а од оваквих кола граде се све врсте меморије:
- Додавањем улаза за такт (енгл. clock) добија се D флип-флоп, који вредност са улаза \(D\) упише само у тренутку откуцаја такта. Низ таквих флип-флопова чини регистар: 8 флип-флопова памти један бајт, а 64 флип-флопа једну 64-битну реч.
- Статичка меморија (SRAM), од које је, на пример, направљена брза кеш меморија процесора, чува сваки бит у пару унакрсно повезаних инвертора — по истом принципу повратне везе као на слици 4.8 — уз два транзистора за приступ, што је укупно шест транзистора по биту.
- Главна меморија (DRAM) је гушћа и јефтинија: бит се чува као наелектрисање малог кондензатора уз само један транзистор, али се наелектрисање губи, па се меморија мора периодично освежавати.
- Меморијске ћелије су распоређене у велику табелу, а адреса записана у бинарном систему бира ћелију. Са \(k\) адресних битова може се адресирати \(2^k\) ћелија — и ту се поново сусрећемо са ширином од 64 бита.
Логичка кола можете и сами да састављате и испробавате у бесплатном програму Logisim Evolution. Кола из овог поглавља доступна су у датотекама основна кола и полусабирач и сабирач.
Резиме
- Бинарних операција на \(\{0, 1\}\) има 16. Језик фаворизује конјункцију, дисјункцију, импликацију и еквиваленцију, али у дигиталној логици најважније су NAND (\(\uparrow\)) и NOR (\(\downarrow\)).
- Скупови \(\{\neg, \land, \lor\}\), \(\{\neg, \land\}\), \(\{\neg, \lor\}\), \(\{\uparrow\}\) и \(\{\downarrow\}\) су потпуни.
- Логичка кола физички остварују Булове функције. NOT, NAND и NOR су најједноставнија кола од прекидача, а NAND и NOR су универзална: свако коло може се саставити само од њих.
- Од логичких кола граде се сабирачи (полусабирач, потпуни сабирач, сабирач од \(n\) бита), а помоћу повратне везе и кола која памте (флип-флоп, регистри, меморија).
Темељи математичке логике постављени су много пре настанка рачунара, а данас се налазе у основи сваког процесора и дигиталног уређаја.
Задаци
Задаци за ово поглавље, са решењима, налазе се у збирци задатака: Дигитална логика.