1 Element de bază circuite digitale

Circuitele digitale, două clase de variabile sunt utilizate în dispozitivele digitale de prelucrare a informațiilor de astăzi: numerele și variabile logice.

Numerele transporta informații despre caracteristicile cantitative ale sistemului, pe ele puteți face calcule aritmetice care aritmetică se bazează pe dispozitive digitale. O variabile logice definesc starea sistemului, sau că ea aparține unei clase de state care alcătuiesc cadrul logic al dispozitivelor digitale. Numerele și variabilele logice asociate între ele pentru rezolvarea sarcinilor de gestionare și de prelucrare a datelor.

1.1 algebra booleană

În proiectarea de circuite logice și dispozitive digitale ca instrumente matematice algebra logicii sau algebra booleană aplicată a fost dezvoltat la mijlocul secolului al XIX-lea, matematicianul irlandez George Boole, dezvoltarea în continuare și aplicarea primit în 1910 PS Ehrenfest în 1938 de către Shannon.

Baza matematică pentru dispozitive digitale este logica algebră care opereaza pe variabile care iau doar două valori, în mod arbitrar desemnate 0 și 1, adică variabile binare. Funcțiile variabile binare sunt numite logice. De asemenea, ei pot lua doar două valori.

Funcția logică este o funcție de forma F (x1. X2. Xn). care, la fel ca x1 sale argumente. x2. xn. poate lua doar două valori - 0 sau 1. Pentru orice funcție logică de n variabile există un număr N = 2 seturi n diferite, iar dacă aceste seturi de funcții este definită, o astfel de funcție se numește complet definită. Astfel, numărul de funcții logice de n variabile (x1. X2. Xn) = 2 N = 2 2 n.

Dacă funcția logică este definită nu pe toate seturile, nu este în totalitate sigur, sau underdetermined. On Funcția underdetermined setează valoarea variabilelor este notată cu O și poate fi arbitrar extinde definiția fie zero sau unu.

Deasupra variabilele din logica algebra pot efectua trei etape de bază: adăugarea logică (+, V) sau operație OR (disjuncție), multiplicarea logică (endo, ·.), Sau exploatarea și (împreună) și negație logică NU funcționare, sau (inversiune):

O funcție logică poate fi definită expresie verbală algebrice sau tabel numit un tabel de corespondență sau un tabel de adevăr. Acțiuni privind variabilele binare sunt fabricate în conformitate cu regulile de operații logice (legile din algebra logicii).

Legile de bază ale algebrei logicii:

Legile Boolean vă permit să convertiți funcțiile logice inițiale și să le aducă într-o formă adecvată pentru utilizare ulterioară.

1. legea comutativ (legea comutativitatea) pentru multiplicarea logică și adăugarea logică: a · b = b · a; a + b = b + a.

2. Dreptul asociativ (legea asociativă) pentru multiplicarea logică și adăugarea logică: (a · b) · c = a · (b · c); (A + b) + c = a + (b + c).

3. Legea de distribuție (legea distributiv): a + b · c = (a + b) (a + c);

4. legea de absorbție: a + b = a · (1 + b) = a; o · (a + b) = a · a + b = a.

6. Legea negație (legea dualității, legea de Morgan); ; - "Pierce Arrow" (funcția "Webb"),

7. Legea dublei negație :.

8. Legea de multiplicare de 1 și 0. · 1 = a; o · 0 = 0; o · a = a.

10. Excepțiile și contradicțiile de drept :; .

12. Operațiunea "XOR" (nonequivalence, valoarea

13. Operația comparație (echivalența, echivalența):

Legile 1 - 10 indică faptul că algebra logica are proprietatea dualitate (dualitate), în ceea ce privește operațiile de adunare și înmulțire logice. Dualitatea este definit ca o schimbare de semne cu privire la operațiuni și tranzacții semne sau semne sau toate operațiunile sau tranzacțiile Semne I.

Funcția Logic pentru comoditatea sintezei înregistrării și ulterior se exprimă ca suma produselor variabilelor, sau ca produse ale sumelor acestora. Prima intrare este numită o formă normală disjunctivă (DNF), al doilea - forma normala conjunctiva (CNF).

Pentru fiecare funcții logice pot exista mai multe forme disjuncte și conjunctive echivalente, dar există doar un singur tip de CNF sau DNF în care funcția poate fi scrisă în mod unic (forme normale perfecte și PDNF SKNF). In functie PDNF este scris ca o unitate logică sumă constituenților (mintermov), iar în SKNF - un produs logic constituenți zero (makstermov).

unu și zero, constituenți - o combinație de variabile pentru care funcția, respectiv, se referă la una sau la zero.

Mintermom (. Sau conjuncție elementară Qi sau o unitate constitutivă) este produsul logic al variabilelor directe sau invers, cu fiecare variabilă din produs are loc o singură dată.

Makstermom (. Sau disjuncție elementar Di sau constituent al zero) este o sumă logică a variabilelor directe și inverse, cu fiecare variabilă are loc în sumă doar o singură dată.

Numărul Mintermov makstermov și un număr predeterminat de argumente se potrivește cu numărul de seturi diferite de argumente N = 2 n.

Proprietăți mintermov și makstermov:

1. Între indicii i și makstermov mintermov omonimă n Boolean variabile au următoarele relații :. . unde subscriptului i - număr zecimal corespunde codului binar corespunzător unei combinații de valori ale argumentelor.

2. Suma logică a tuturor mintermov orice număr de variabile egal cu unitatea, adică, .

3. Produsul logic al tuturor makstermov orice număr de variabile egal cu zero, adică, .

4. mintermov produsului logic având diferiți indici este zero, adică, Qi · Qj = 0. atunci când i. j.

5. Suma logică a inegale makstermov egal cu unitatea, și anume, Di + Dj = 1. atunci când i. j.

Pentru a construi PDNF FCDHF funcție logică de n variabile definite de tabelul de adevăr, este necesar pentru fiecare set de variabile pe care funcția ia valoarea 1, înregistrarea conjuncția - tipul minterm și toate aceste conjuncții pentru a conecta semne de disjuncție. Variabilele care au o valoare de zero, inversat. . , Unde i - numerele zecimale corespunzătoare seturilor de argumente pe care F = Fi = 1.

Pentru a construi SKNF FCKHF funcție logică de n variabile definite de tabelul de adevăr, este necesar ca fiecare set de variabile pe care funcția este setată la 0, scrie disjuncției - tip maksterm și toate astfel de disjuncție conecta semne de colaborare. Variabilele care sunt importante unități inversat :. unde i - numerele zecimale corespunzătoare seturilor de argumente pe care F = Fi = 0.

Pentru a reduce numărul de elemente logice care realizează o funcție de diferite metode de minimizare. Prin minimizarea funcției de logica pentru a găsi cel mai simplu de a înțelege reprezentarea ei în formă de superpoziție, constituind orice sistem fix, complet funcțional.

O funcție logică poate fi simplificată prin transformarea algebric direct folosind legile Boolean (lipire și de absorbție). Dar, de regulă, astfel de conversii necesită calcule greoaie, precum și cunoștințe și abilități. Pentru funcțiile care au un număr mare de variabile (mai mult de trei), și un număr mare de termeni, există tehnici speciale. Cele mai frecvent utilizate metode folosind hărți Karnaugh și cartele Veitch reprezentând un tabel dreptunghiular, cu un număr de 2 n celule. Fiecare rând (coloana) din acest tabel corespunde unei anumite combinații de argumente (variabile), fiecare celulă corespunde unui anumit set de valori ale argumentelor, astfel încât la fiecare tranziție de la o celulă la un adiacent de-a lungul unui rând sau o coloană modifică valoarea doar un argument al funcției. hărți Karnaugh sunt diferite de ordinea argumentelor Veitch diagramele de locații, enumerate în codul ciclic (cod Gray) de numere binare.

Algoritmul pentru a minimiza funcția logică constă în următoarele etape:

1. Funcția logică ar trebui să conducă la PDNF (SKNF). Pentru a face acest lucru, trebuie să utilizați legile logicii algebră 2, 3, 7-10, și în fiecare dintre funcțiile membrilor, în care nu există argumente, introduceți expresia formei și de a folosi egalitatea pentru PDNF, unde i (pentru SKNF.) - este absent în argumentul pe termen lung.

2. Completați mintermami (makstermami) tabel dreptunghiular, numărul care este egal cu numărul de posibile mintermov celulei 2 n. Funcția logică Mintermy marcată 1 în celulele respective din tabel, și makstermy - 0. Două minterma situate în celulele vecine poate fi înlocuită cu un produs logic unic care conține una mai puțin variabile, pe baza legilor distributivă bonding și adăugare (multiplicare) și 1 0. în cazul general, prezența unităților (zerouri) 2 K celulele vecine elimină variabilele K.

3. În completarea tabelului încercuiască contururile rectangulare ale tuturor unităților (zero). Atunci când efectuează circuite adere la următoarele reguli: circuitul trebuie să fie dreptunghiular; în interiorul buclei trebuie să fie numai celulele umplute cu 1 (0); numărul de celule din interiorul buclei trebuie să fie o putere întreagă de 2, și anume 1, 2, 4, 8, 16; aceeași celulă umplută cu 1 (0), pot fi incluse în mai multe bucle; cea mai de jos și cea mai de sus rând al tabelului, precum și cea mai din stânga și din dreapta-cele mai multe coloane sunt considerate adiacente; circuite trebuie să fie cât mai mic posibil, iar contururile în sine - cât mai mare posibil.

minim DNP funcția 4. Exprimarea (MDNF) este scris după cum urmează. Fiecare circuit este reprezentat în membru MDNF, în care numărul de variabile în K mai mică decât totalul n - numărul de argumente ale funcției, adică, egală cu n - K. MDNF Fiecare membru este numai acelor argumente pentru circuitul respectiv sunt comune, adică sunt la fel de inversie sau fără inversare. În general, funcția poate avea mai multe forme minimale, care corespund diferite, dar egale în număr de membri MDNF.

De exemplu: Având în vedere o funcție de patru variabile (argumente)

hărți Karnaugh, vom face o acoperire

Scrieți rezultatul în formă de conjuncțiilor dezyunktsii acoperite (suma produselor):

Funcția de a reduce la minimum a avut 16 seturi de variabile, după patru.