CN Wiki

= Laboratorul 0 - Introducere în logica digitală. Falstad = == 1. Sisteme de numerație == Un număr **N** de forma **c_nc_n-1...c₂c₁c₀** reprezentat în baza 10 are valoarea: **N = c_n*10ⁿ + c_n-1*10^n-1 +...+ c₂*10² + c₁*10¹ + c₀*10⁰** * 12345₍₁₀₎ = **1***10⁴ + **2***10³ + **3***10² + **4***10¹ + **5***10⁰ Baza unui sistem de numerație poate fi însă orice întreg b > 1, ponderea cifrei din poziția i fiind în acest caz **bⁱ**. Atunci, valoarea în baza b a unui număr **N** reprezentat ca mai sus este: **N = c_n*bⁿ + c_n-1*b^n-1 +...+ c₂*b² + c₁*b¹ + c₀*b⁰** **(1)** În circuitele digitale, semnalele pot avea, în mod normal, una din cele doua stări posibile. Aceste stări sunt asociate cifrelor binare 0 și 1, ceea ce face ca baza 2 să fie o alegere naturală pentru reprezentarea numerelor în sistemele digitale. * 100101₍₂₎ = 1*2⁵ + 0*2⁴ + 0*2³ + 1*2² + 0*2¹ + 1*2⁰ O altă bază folosită în sistemele digitale este baza 16, deoarece permite o reprezentare mai facilă a numerelor decât baza 2, dealtfel și conversia între baza 2 și baza 16 fiind foarte rapidă. Cifrele folosite în baza 16 sunt, în ordinea crescătoare a valorii, 0..9 plus literele A, B, C, D, E și F. * 1EE7₍₁₆₎ = 1*16³ + 14*16² + 14*16¹ + 7*16⁰ = 7911₍₁₀₎ Pentru a găsi reprezentarea unui număr într-o bază b este necesar să determinăm cifrele c_nc_n-1...c₂c₁c₀ care satisfac ecuația **(1)**, ținând cont de faptul că c_i < b. Rearanjând ecuația **(1)** obținem: **N = (c_n*b^n-1 + c_n-1*b^n-2 +...+ c₂*b¹ + c₁*b⁰)*b + c₀** Se observă că tot ce trebuie să facem pentru a îl afla pe c₀ este să împărțim numărul de convertit la b, c₀ fiind chiar restul împărțirii. Câtul rezultat va fi apoi împarțit din nou la b pentru a afla pe c₁ ș.a.m.d. pentru celelate cifre c₂, ..., c_n. * 37₍₁₀₎ = 100101₍₂₎ ^ ^ Cât ^ Rest ^ Cifra ^ | 37/2 | 18 | 1 | c₀ | | 18/2 | 9 | 0 | c₁ | | 9/2 | 4 | 1 | c₂ | | 4/2 | 2 | 0 | c₃ | | 2/2 | 1 | 0 | c₄ | | 1/2 | 0 | 1 | c₅ | * 7911₍₁₀₎ = 1EE7₍₁₆₎ ^ ^ Cât ^ Rest ^ Cifra ^ | 7911/16 | 494 | 7 | c₀ | | 494/16 | 30 | 14 (E) | c₁ | | 30/16 | 1 | 14 (E) | c₂ | | 1/16 | 0 | 1 | c₃ | În cazul în care între baza sursă b_s și baza destinație b_d există o relație de forma: **b_s = b_d^r** sau **b_d = b_s^r**, conversia între cele doua baze se poate face mult mai ușor având în vedere că fiecare cifră a bazei mai mari poate fi scrisă ca un grup de r cifre ale bazei mai mici. * 16 = 2⁴ * 1EE7₍₁₆₎ = 0001 1110 1110 0111₍₂₎ * 100101₍₂₎ = 0010 0101₍₂₎ = 25₍₁₆₎ == 2. Algebra booleană == Algebra booleană este o algebră formată din: * elementele **0** și **1** * 3 operații: **ȘI** (and), **SAU** (or) și **NEGAȚIE** (not). ^ Operator ^ Notatie in logica propozitionala ^ Notatie in C ^ Denumiri uzuale ^ | Negatie | ¬ sau ~ | ! | not | | Conjunctie | ∧ sau ∙ | & | and | | Disjunctie | ∨ sau + | <nowiki>|</nowiki> | or | | Disjunctie exclusiva | ⊕ | <nowiki>^</nowiki> | xor | | Implicatie | → | n/a | n/a | | Echivalenta | ↔ | n/a | n/a | Dintre cele mai uzuale axiome ale algebrei boolene amintim: * **Principiul dublei negații** * ¬(¬x) = x * **Legile lui De Morgan** * ¬(x ∧ y) = ¬x ∨ ¬y * ¬(x ∨ y) = ¬x ∧ ¬y <hidden Mai multe informații despre algebra booleană> Axiomele algebrei boolene se pot rezuma in felul următor: * Operații cu elementul neutru * x ∨ 0 = x * x ∧ 1 = x * x ∧ 0 = 0 * x ∨ 1 = 1 * Operații cu complementul * x ∨ ¬x = 1 * x ∧ ¬x = 0 * Principiul idempotenței * x ∨ x = x * x ∧ x = x * Principiul dublei negații * ¬(¬x) = x * Comutativitate * x ∨ y = y ∨ x * x ∧ y = y ∧ x * Asociativitate * x ∨ (y ∨ z) = (x ∨ y) ∨ z = x ∨ y ∨ z * x ∧ (y ∧ z) = (x ∧ y) ∧ z = x ∧ y ∧ z * Distributivitate * x ∧ (y ∨ z) = x ∧ y ∨ x ∧ z * (x ∨ y) ∧ (x ∨ z) = x ∨ y ∧ z * Legile lui De Morgan * ¬(x ∧ y) = ¬x ∨ ¬y * ¬(x ∨ y) = ¬x ∧ ¬y * Implicație * x => y := ¬x ∨ y * Echivalenta * x <=> y := x => y ∧ y => x Orice predicat logic poate fi rescris dintr-o **formă normal conjunctivă** (conjuncție de disjuncții) într-o **formă normal disjunctivă** (disjuncție de conjuncții) pe baza precedentului set de teoreme. De notat că operația ∧ are prioritate în faăa operației ∨ (lucru mai vizibil dacă se foloseste notația cu ∙ și +). </hidden> == 3. Porți logice == Porțile logice se folosesc în circuitele digitale pentru a implementa operațiile din algebra booleană. Fiindcă sunt foarte multe moduri în care o anumită funcție logică poate fi realizată (nu numai ca design de circuit, ci și ca mod de fabricație al circuitelor integrate), porțile sunt grupate în **familii logice**. * **Wired logic** (logică cablată cu diode): circuite extrem de ușor de realizat, folosind numai diode și rezistențe de pull-up/pull-down. Sunt circuite pur pasive (nu au etaj final de amplificare), așa că nivelele logice de la ieșire sunt degradate (spre exemplu 0.6V în loc de 0V, 4.4V în loc de 5V). * **RTL** (resistor-transistor logic): prima formă de logică digitală ce foloseste elemente active, și anume tranzistori bipolari. Logica este efectuată în etajul de intrare, utilizând rezistențe. Dezavantajul acestei familii de porți logice este consumul foarte mare, din cauza tranzistorilor folosiți și a rezistențelor. * **DTL** (diode-tranzistor logic): această familie combină logica cablata cu un etaj final cu tranzistori bipolari. * **TTL** (transistor-transistor logic): reprezintă un avans față de DTL, folosind tranzistori bipolari, în general multiemitor, inclusiv în etajul de intrare. Etajul de ieșire este realizat folosind 2 tranzistori, unul **NPN** și unul **PNP**, într-o conexiune ce poartă denumirea de **stâlp totemic** sau push-pull. * **ECL** (emitter-coupled logic): o familie de mare viteză, ce folosește tot tranzistori bipolari, însă care nu intră niciodată în saturație. Din acest motiv, marginea de zgomot((diferența dintre tensiunea în starea LOW și tensiunea în starea HIGH)) este foarte mica, deci aceste circuite sunt susceptibile la zgomot. * **NMOS** (N-type metal-oxide-semiconductor logic): spre deosebire de familiile anterioare, NMOS se folosește de tranzistori cu efect de camp (**FET**) și de rezistențe de pull-up. * **CMOS** (complementary metal-oxide-semiconductor logic): nu folosește deloc rezistenșe, ci tranzistori de tip nMOS și pMOS. Este tehnologia folosita În prezent la fabricarea majorității dispozitivelor electronice. După cum se poate vedea, aproape toate formele de logică digitală contin, într-un mod sau altul, tranzistori. Din motive tehnice, este mai ușor să realizăm porți logice pentru funcțiile **NAND** și **NOR** decât pentru echivalentele lor în logica pozitivă, **AND** și **OR**. Din această cauză, ne vom rescrie funcțiile logice, folosind teoremele algebrei boolene prezentate mai sus, astfel încat să folosim numai aceste operații. Nu este ieșit din comun ca procesoare întregi să fie implementate utilizând numai porți **NAND** sau numai porți **NOR**. === 3.1. Inversorul NMOS === Să vedem cum poate fi realizată o poartă **NOT** în logică **NMOS**. {{:lab:cn1:NMOSNOT_zps77b925f9.png?200}} Funcționarea sa este următoarea: * În starea HIGH pe intrare, (A), tranzistorul se deschide și trage V_out (tensiunea la terminalul F) la masă. * În starea LOW pe intrare, tranzistorul se blocheaz și drena intră în impedanță marită. V_out este tras la V_DD de către rezistența R (numită rezistență de pull-up). === 3.2. Inversorul CMOS === Să vedem cum poate fi realizată o poartă **NOT** în logică **CMOS**. {{:lab:cn1:CMOSNOT_zpsb2753d9b.png?250}} Această poartă funcționează astfel: * Întâi trebuie să observam că cei doi tranzistori sunt legați în **stâlp totemic**: pMOS-ul legat la V_DD și nMOS-ul legat la masă. * Având intrările conectate în paralel, niciodată cei doi tranzistori nu vor fi deschiși în același timp. * În starea LOW pe intrare tranzistorul pMOS este deschis iar cel nMOS este blocat. Ieșirea se duce, asadar, la V_DD. * În starea HIGH pe intrare tranzistorul pMOS este blocat iar cel nMOS este deschis. Ieșirea este legată la masă. === 3.3. Porți NAND și NOR cu CMOS === ^ NAND ^ NOR ^ | {{:lab:cn1:CMOSNAND_zpsf39dacb2.png?300}} | {{:lab:cn1:CMOSNOR_zps4571909a.png?350|NOR}} | === 3.4. Reprezentarea porților logice === Pentru că tendința în electronică este, în general, "set and forget"((construim niște dispozitive din siliciu, le numim tranzistori și uităm de siliciu, apoi construim niște porți logice din tranzistori și uităm de tranzistori, apoi construim niște circuite integrate și uităm de porți logice, apoi construim niște procesoare și uităm de circuite integrate, apoi uităm de electronica și programăm procesoarele în assembly, apoi uităm de assembly și programăm in C, apoi uităm de C și programăm în Java, apoi uităm tot și ne angajăm la McDonalds)), asta vom face și noi. În loc de scheme bloc cu tranzistori, vom lucra cu imagini "de ansamblu" care să reprezinte porțile logice la nivel conceptual. De asemenea, vom inlocui valorile de tensiuni cu nivele logice (LOW și HIGH). Atunci, putem sa rezumăm întreaga poveste în felul următor: ^ Denumire ^ Simbol ^ Operator ^ Tabel de adevăr ^ | Inversor (**NOT**) | {{:lab:cn1:not_zps6bd04c6f.png?100}} | F = ¬A | {{:lab:cn1:nu_zps8fa808f3.png?100}} | | Poartă ŞI (**AND**) | {{:lab:cn1:and_zpsf44122a4.png?100}} | F = A ∧ B | {{:lab:cn1:SI_zpse0db1273.png?100}} | | Poartă SAU (**OR**) | {{:lab:cn1:or_zps68e6b0cc.png?100}} | F = A ∨ B | {{:lab:cn1:sau_zps8bc1e31e.png?100}} | | Poarta ŞI-NU (**NAND**) | {{:lab:cn1:nand_zpse6d994ea.png?100}} | F = ¬(A ∧ B) | {{:lab:cn1:sinu_zpsd8592dac.png?100}} | | Poartă SAU-NU (**NOR**) | {{:lab:cn1:nor_zps9107befe.png?100 }} | F = ¬(A ∨ B) | {{:lab:cn1:saunu_zps35965747.png?100}} | | Poartă SAU EXCLUSIV (**XOR**) | {{:lab:cn1:xor_zpsf73e24a0.png?100}} | F = A ⊕ B | {{:lab:cn1:sauexclu_zpsf33338d2.png?100}} | == 4. Circuite logice combinaționale == Circuitele logice combinaționale sunt circuitele reprezentate prin porți logice ce aplică o funcție pe intrări. Valorile de ieșire depind doar de valorile de intrare, nu și de stări de reactie (feedback), iar când starea unei intrări se schimbă, se reflectă imediat la ieșiri. {{ https://www.electronicshub.org/wp-content/uploads/2015/06/Combinational-Block-diagram-.jpg?411x300 | Circuit combinațional cu n intrări și m ieșiri}} Un circuit combinațional poate fi descris printr-o schema de interconectarea a unor porți logice, prin funcția (expresia) în logica booleană ce este aplicată pe intrări și prin tabele de adevăr (dacă nu au un număr prea mare de intrări). Circuitele combinaționale sunt folosite în procesoare în cadrul componentelor de calcul, iar cele mai des întalnite sunt: * Multiplexoare și demultiplexoare * Sumatoare * Codificatoare și decodificatoare * Comparatoare * Memorii ROM (read-only, nu păstrează starea) === 4.1. Multiplexoare === Un multiplexor digital este un circuit combinațional care implementează o funcție de selecție a uneia dintre intrările sale. Alegerea semnalului de ieșire se face pe baza unor intrări suplimentare care reprezintă în baza 2 numărul intrării ce trebuie selectate, astfel un multiplexor cu 2ⁿ intrări va avea nevoie de n semnale de selecție. În exemplul din figura de mai jos avem schema bloc a unui multiplexor cu 4 intrări, iar acesta are nevoie de doar 2 intrări de selecție. {{ http://elf.cs.pub.ro/ac/wiki/_media/lab/lab00/mux4.png?170x190 | Reprezentarea unui multiplexor 4:1}} Funcția logică corespunzătoare unui multiplexorului 4:1 din exemplul de mai sus este următoarea: **out = ¬S₁∧¬S₂∧I₁ ∨ S₁∧¬S₂∧I₂ ∨ ¬S₁∧S₂∧I₃ ∨ S₁∧S₂∧I₄**. Folosind această expresie putem descrie circuitul combinațional pentru multiplexor, având nevoie conform formulei de 4 porți logice AND cu trei intrări, o poartă OR cu 4 intrări și porți NOT pentru negarea semnalelor de selecție. {{ http://elf.cs.pub.ro/ac/wiki/_media/lab/lab00/mux4-gates.png?w=300&tok=211f1b | Schema block a unui multiplexor 4:1}} === 4.2. Sumatoare === Sumatoarele (adders), folosite cel mai mult în unitățile aritmetice logice ale procesoarelor, realizează adunări pe un număr dat de biți, furnizând la ieșirea circuitului suma și transportul (carry) rezultat în urma operației. Există mai multe tipuri de sumatoare pentru adunarea numerelor pe n biți, iar acestea se bazează pe sumatoare simple de 1 bit ce pot fi de două tipuri: * Half-adder: însumează doi operanzi pe 1 bit și oferă la ieșire suma acestora și un transport. * Full-adder: însumează doi operanzi pe 1 bit și un transport și oferă la ieșire suma acestora trei și un transport. ^ Half Adder ^ Full Adder ^ | S = A xor B \\ C_out = A and B | S = (A ⊕ B) ⊕ C_in \\ C_out = A ∧ B ∨ (C_in ∧ (A ⊕ B)) | | {{ https://upload.wikimedia.org/wikipedia/commons/thumb/1/14/Half-adder.svg/325px-Half-adder.svg.png?250x250 |Half Adder }} | {{http://i.stack.imgur.com/0rqZz.png?300x200|Full Adder}} | == 5. Circuite logice secvențiale == Spre deosebire de circuitele logice combinaționale, cele secvențiale nu mai depind exclusiv de starea curentă a intrărilor, ci și de stările anterioare ale circuitului. După cum este arătat și în figura de mai jos, circuitului combinațional format din porți logice i se adaugă un element de memorare a stărilor. {{ http://www.c-jump.com/CIS77/images/figure_3_23_sequential_logic.png?350x200 | Circuit logic secvențial}} Circuitele secvențiale sunt de două tipuri: * **asincrone** (se mai numesc și **latch**): sunt rar folosite și țin cont de ordinea în care se schimbă intrările, elementul de memorare fiind de fapt căi de feedback. * **sincrone**: se folosesc pentru memorarea stării (acel “black box” din figura de mai sus). * Exemplu: **bistabili** (sau **Flip-Flop**), ce își schimbă valoarea stocată doar la schimbarea semnalului de ceas primit la intrare. <note Important> Pe scurt, latch-urile sunt **transparente**: ieșirea se actualizează "în timp real", odată cu modificarea vreuneia dintre intrări. În contrast, bistabilele sunt sincrone, deci își schimbă starea numai pe frontul crescător (sau descrescător) al semnalului de ceas. </note> === 5.1. Latch-ul SR === {{ https://cdn.sparkfun.com/assets/learn_tutorials/2/1/6/30-SR-flipflop-circuit.PNG?250x200 | SR Latch}} Latch-ul SR are două intrări: * S (**Set**): pune Q pe HIGH, deci stochează valoarea HIGH. * R (**Reset**): pune Q pe LOW, deci stochează valoarea LOW. Funcționarea sa este următoarea: * S = R = LOW => Q nu se schimbă * S = HIGH, R = LOW => Q = HIGH * R = HIGH, S = LOW => Q = LOW * S = R = HIGH => stare nedeterminată === 5.2. Bistabilul JK === {{ http://upload.wikimedia.org/wikipedia/commons/f/ff/JK-FlipFlop_%284-NAND%29.PNG?240x100 | Bistabil JK}} Acest bistabil este similar celui SR, având două intrări J și K, însă elimină starea ambiguă (ambele intrări HIGH) * J = K = LOW => Q nu se schimbă * J ≠ K => Q = J * J = K = HIGH => Q basculeaza === 5.3. Bistabilul D === {{ http://upload.wikimedia.org/wikipedia/commons/6/69/D-FlipFlop_%284-NAND,_1-NOT%29.PNG?240x100 | Bistabil D}} Ideea acestui bistabil pornește tot de la eliminarea stării ambigue de la bistabilul SR, și reușește acest lucru prin a nu mai permite ca S și R să fie egale. Bistabilul D are o singură intrare, (D), conectând cele două intrări SR printr-un invertor. * D = 0 => Q_t+1 = 0 * D = 1 => Q_t+1 = 1 [[http://tinyurl.com/y9bt4qgx|Edge-Triggered D Flip-FLop circuit]] <note Info> Acest tip de bistabil este cel mai des utilizat, datorită proprității sale de a se comporta ca o celula de memorare. Este folosit pentru realizarea registrelor procesoarelor. </note> == 6. TL;DR == * Sisteme de numerație: * transformari între baze * conversia între baze cu proprietatea b_s = b_d^r sau b_d = b_s^r * Algebra booleană: * elementele **0** și **1** * 3 operații: **ȘI** (and), **SAU** (or) și **NEGAȚIE** (not) * Porți logice: * familii logice: wired, RLT, DTL, TTL, ECL, NMOS, CMOS * set and forget: reprezentarea porților logice, nivele logice(LOW, HIGH) * Circuite logice combinaționale: * valorile de ieșire dependente exclusiv de valorile de intrare, nu și de feedback * în cadrul componentelor de calcul: multiplexoare, sumatoare, codificatoare, comparatoare * Circuite logice secvențiale: * dependente atat de starea curentă a intrarilor, cât și de stările anterioare ale circuitului * două tipuri: sincrone și asincrone == 7. Exerciții == Vom folosi pentru exemplificarea noțiunilor prezentate mai sus, un simulator de circuite, [[http://www.falstad.com/circuit/|Falstad]]. Implementați și observați comportamentul următoarelor circuite: - Porți logice - NOT folosind logică CMOS - NOT folosind logică RTL - NAND folosind logică CMOS - NOR folosind logică CMOS - XOR folosind logică CMOS - Circuite combinaționale - Multiplexoare - Multiplexor 2:1 folosind porți logice - Multiplexor 4:1 folosind porți logice - Sumatoare - Half-adder folosind porți logice - Full-adder folosind porți logice - Circuite secvențiale - Latch SR folosind porți logice - Bistabil JK folosind porți logice - Bistabil D folosind porți logice