Apunts d'Estructura de Computadors: Lògica Digital

I 0 flashcards i 9 preguntes més al document.

Text del document

APUNTS ESTRUCTURA DE COMPUTADORS I Grau en Enginyeria Informàtica Universitat de Lleida AprenAI 2026-2027 Guia completa d'Estructura de Computadors: sistemes de representació, àlgebra de Boole, mapes de Karnaugh, blocs MSI combinacionals i disseny seqüencial.

APREN.AI Índex 1 Representació numèrica — Sistemes de signe i complement a 2 Sistemes de representació amb signe Rangs de representació amb n bits Càlcul i comparació amb 4 bits Aritmètica bàsica i transport final 2 Àlgebra de Boole — Postulats, propietats i portes lògiques Àlgebra de commutació i postulats fonamentals Principi de dualitat i lleis de De Morgan Portes lògiques bàsiques i derivades Universalitat i propietat associativa de les portes lògiques 3 Funcions lògiques — Taules de veritat i formes canòniques Representació de funcions lògiques: taula de veritat i expressió algebraica Minterms i Forma Canònica Disjuntiva (SOP) Maxterms i Forma Canònica Conjuntiva (POS) Funcions incompletament especificades: termes no importa (don't care) 4 Simplificació de funcions — Mapes de Karnaugh Principis dels mapes de Karnaugh i adjacència lògica Mapes de 2, 3 i 4 variables Mapes de 5 i 6 variables: adjacència tridimensional Obtenció del producte de sumes i termes no importa 5 Circuits combinacionals — Estructures a dos nivells, anàlisi i síntesi Estructures de portes a dos nivells Anàlisi de circuits combinacionals Síntesi de circuits combinacionals Blocs MSI combinacionals 6 Descodificadors, codificadors i comparadors Descodificadors binaris Entrada d'habilitació (Enable) i expansió de descodificadors Codificadors bàsics i de prioritat Comparadors de magnitud i d'igualtat 7 Multiplexors i generació de funcions El multiplexor com a selector de dades Mòduls de multiplexors múltiples Implementació de funcions lògiques amb multiplexors Apunts d'Estructura de Computadors: Lògica Digital 1 El demultiplexor i la seva relació amb el descodificador Circuits seqüencials 8 Biestables i elements de memòria Fonaments dels circuits seqüencials i l'element bàsic de memòria Biestable elemental (latch) RS amb portes NOR i NAND Sincronisme: senyal de rellotge, nivell i flanc Biestables síncrons: RS, D, JK i T Entrades asíncrones o directes: Preset (Sd) i Clear (Rd) 9 Anàlisi i disseny d'autòmats d'estats finits Fonaments dels autòmats finits: models de Mealy i Moore Metodologia d'anàlisi de circuits seqüencials Metodologia de síntesi de circuits seqüencials Síntesi utilitzant biestables tipus D Síntesi utilitzant biestables tipus JK 10 Formulari Sistemes de representació numèrica Àlgebra de Boole i simplificació Blocs combinacionals MSI Biestables i circuits seqüencials Procediments de treball Taules d'excitació dels biestables Errors típics d'examen Solucions de les preguntes de repàs Aquests apunts poden contenir errors o omissions.

Són un material de suport i no substitueixen el temari oficial ni el professorat: contrasta la informació important. Apunts d'Estructura de Computadors: Lògica Digital 2 1 Representació numèrica — Sistemes de signe i complement a 2 EN ACABAR SABRÀS Determinar els rangs de representació per a S+M, Ca1 i Ca2 segons el nombre de bits. Convertir nombres enters positius i negatius entre els formats S+M, Ca1 i Ca2. Aplicar correctament el tractament del carry en operacions de suma segons el sistema de complement. PENSA-HI ABANS DE LLEGIR 1 Com pot un circuit digital diferenciar entre sumar i restar sense necessitar maquinari específic de resta?

La codificació de quantitats numèriques en sistemes digitals requereix mecanismes per distingir valors positius i negatius mitjançant cadenes binàries d'amplada fixa. ESQUEMA Estructura de la representació digital de la informació Sistemes de representació amb signe Quan es treballa amb una paraula de bits, existeixen tres esquemes fonamentals per codificar nombres enters amb signe: Signe-Magnitud (S+M), Complement a 1 (Ca1) i Complement a 2 (Ca2). En el format de Signe-Magnitud, el bit més significatiu (a l'esquerra) actua com a indicador de polaritat: un valor 0 indica signe positiu, mentre que un 1 senyala un valor negatiu.

Els bits restants codifiquen el mòdul o valor absolut del nombre en binari natural. Sistemes amb signe Codificació d'enters positius i negatius Signe-Magnitud Bit de signe separat de la magnitud Complement a 1 Inversió bit a bit dels positius Complement a 2 Sistema estàndard aritmètic sense duplicitat n n 1 Apunts d'Estructura de Computadors: Lògica Digital 3 Esquema del format Signe-Magnitud amb bit de signe i camp de magnitud. En els formats de complement, la representació d'un valor positiu o nul ( ) coincideix exactament amb el binari convencional començat per 0.

La diferència rau en el càlcul matemàtic dels valors negatius ( ): Complement a 1: la representació es defineix matemàticament com Pràcticament, equival a invertir bit a bit la paraula binària positiva. Complement a 2: la representació matemàtica respon a l'expressió Rangs de representació amb n bits Atesa l'amplada de paraula de dígits binaris, la quantitat de combinacions disponibles queda fitada entre dos extrems: En S+M i Ca1, el rang és simètric: [-(2^{n-1} - 1), +(2^{n-1} - 1)]. En ambdós formats existeixen dues representacions per al zero (+0 i -0).

En Ca2, s'elimina la duplicitat del zero, permetent una representació asimètrica que guanya un enter negatiu addicional: [-2^{n-1}, +(2^{n-1} - 1)]. COMPROVA-HO 2 Quin és el rang de valors representables en Complement a 2 si disposem de 4 bits? A 0 A 0 R (A) = Ca1 2 n 1 A R (A) = Ca2 2 n A n Apunts d'Estructura de Computadors: Lògica Digital 4 Càlcul i comparació amb 4 bits Per il·lustrar les diferències, prenem el valor codificat amb bits per representar tant +3 com -3: Format Valor +3 Valor -3 Procediment operatiu per a negatius Signe-Magnitud (S+M) 0011 1011 Bit de signe a 1 i mòdul invariable (011). Complement a 1 (Ca1) 0011 1100 Complementar tots els bits individualment.

Complement a 2 (Ca2) 0011 1101 Regla pràctica de rastreig des de la dreta o sumar 1 a Ca1. Per trobar la codificació en Complement a 2 d'un nombre negatiu, es pot emprar la regla directa d'inspecció: es recorren els bits d'ordre menor a major (de dreta a esquerra); es mantenen tots els zeros inalterats i també el primer 1 trobat; a partir d'aquest punt, s'inverteixen tots els bits restants cap a l'esquerra.

Aritmètica bàsica i transport final El comportament del transport generat per l'etapa més significativa (carry de sortida) difereix substancialment entre sistemes: Suma en Ca1: si la suma produeix carry final, és indispensable sumar 1 al resultat per obtenir el valor correcte (mecanisme de transport circular o end-around carry). Suma en Ca2: el transport de sortida que desborda l'amplada de bits es menysprea en condicions normals de no desbordament, sense requerir cap suma addicional.

ERROR FREQÜENT Confondre el tractament del carry de sortida entre Ca1 i Ca2: en Complement a 1, si apareix un carry final, aquest s'ha de sumar de nou a la posició de menys pes; en Complement a 2, el carry final simplement es descarta. COMPROVA-HO 3 Què cal fer si apareix un transport al final d'una operació de suma en Complement a 1? 3 = 10 11 2 n = 4 n Apunts d'Estructura de Computadors: Lògica Digital 5 IDEES CLAU Els sistemes S+M i Ca1 presenten rangs simètrics i doble representació del zero. El format Ca2 disposa d'un rang asimètric amb un únic zero, afegint un valor negatiu addicional.

El Ca2 d'un enter negatiu es pot calcular copiant els bits de dreta a esquerra fins al primer 1 inclòs, i invertint els restants. En sumar en Ca1, un carry de sortida obliga a sumar 1 al resultat final, operació innecessària en Ca2. COMPROVA EL QUE HAS APRÈS 4. Com s'obté la representació d'un nombre negatiu en Ca1 a partir del seu equivalent positiu? 5. Quina diferència operativa existeix quan es genera un carry de sortida en una suma en Ca1 en comparació amb Ca2? Test Encercla la resposta correcta. Les solucions són al final. 6. Quin és el rang de representació d'un sistema en Complement a 2 amb n bits? 7. Quina és la representació del nombre -3 amb 4 bits en format Signe-Magnitud? 8.

Quin procediment ràpid permet passar un nombre a Complement a 2 des de la dreta? 9. Què s'ha de fer en generar-se carry en una suma en Complement a 1?

[ (2 n 1 1), 2 n 1 1] [ 2 , 2 n 1 n 1 1] [-( - 1), - 1] a) 2n 2n [- , - 1] b) 2n 1 2n 1 [-( - 1), - 1] c) 2n 1 2n 1 [- , - 1] d) 2n 2n 1011 a) 1100 b) 1101 c) 0011 d) Mantenir zeros i primer 1, invertir la resta a) Canviar només el bit de signe inicial b) Sumar 1 al bit de més pes c) Invertir tots els bits sense excepció d) Descartar-lo directament sense fer res més a) Invertir el bit de signe del total b) Restar 1 al bit de menor pes c) Sumar 1 al resultat final de l'operació d) Apunts d'Estructura de Computadors: Lògica Digital 6 2 Àlgebra de Boole — Postulats, propietats i portes lògiques EN ACABAR SABRÀS Aplicar els postulats, lleis d'absorció i teoremes de De Morgan per simplificar expressions booleanes.

Obtenir la funció dual d'una expressió lògica intercanviant operadors i constants. Identificar el comportament i les taules de veritat de les portes AND, OR, NOT, XOR, NAND, NOR i XNOR. Demostrar formalment la propietat associativa de la porta XOR i la no associativitat de NAND i NOR. PENSA-HI ABANS DE LLEGIR 10 Per què si neguem dues vegades el resultat d'una operació lògica podem transformar sumes en productes? L'àlgebra de commutació constitueix el fonament matemàtic del disseny lògic digital i dels sistemes de computació moderns. Proporciona el marc algebraic necessari per manipular variables binàries mitjançant operacions fonamentals.

ESQUEMA Estructura del Tema 2: Funcions lògiques Àlgebra de commutació i postulats fonamentals Aquesta estructura es defineix formalment a partir d'un conjunt de dos valors discrets B = {0, 1} sobre el qual operen dues lleis de composició interna: la suma lògica (representada per o pel símbol ) i el producte lògic (denotat com a o pel símbol ). Esquema dels components de l'àlgebra de commutació: conjunt binari i operadors.

Àlgebra de commutació Postulats, propietats i De Morgan Portes lògiques Bàsiques, compostes i universalitat Propietats associatives Associativitat XOR vs no- associativitat NAND/NOR + Apunts d'Estructura de Computadors: Lògica Digital 7 El funcionament d'aquest sistema es regeix per una sèrie de propietats i postulats fonamentals que mantenen una simetria exacta: Propietat Operador Suma ( ) Operador Producte ( ) Commutativa Associativa Element neutre Element complement Distributiva De manera addicional, s'estableix que l'element complement (o negació de ) és únic per a cada valor de la variable.

També es verifiquen els teoremes d'elements nuls ( i ), els elements neutres complementaris ( i ), així com la llei d'idempotència ( i ) i la llei d'involució ( ). Pel que fa a la simplificació d'expressions, s'apliquen dues lleis clau d'absorció: Primera llei d'absorció: i la seva versió dual . Segona llei d'absorció: i la dual . Diagrama de Venn representant la primera llei d'absorció booleana. COMPROVA-HO 11 Com es pot simplificar l'expressió aplicant directament les propietats establertes?

+ x + y = y + x x y = y x (x + y) + z = x + (y + z) (x y) z = x (y z) x + 0 = x x 1 = x x + = x 1 x = x 0 x + (y z) = (x + y) (x + z) x (y + z) = (x y) + (x z) x x x + 1 = 1 x 0 = 0 = 0 1 = 1 0 x + x = x x x = x = x x x + x y = x x (x + y) = x x + x y = x + y x ( + x y) = x y A ( + A B) Apunts d'Estructura de Computadors: Lògica Digital 8 Principi de dualitat i lleis de De Morgan DEFINICIÓ El principi de dualitat lògica estableix que qualsevol identitat algebraica vàlida es manté certa si s'intercanvien els operadors suma ( ) i producte ( ), i simultàniament se substitueixen els elements neutres 0 i 1 entre ells.

ERROR FREQÜENT En aplicar el principi de dualitat, no s'han de negar les variables. La transformació actua exclusivament sobre els operadors lògics i els elements d'identitat. Modificar els complements de les variables durant la dualització és un error que altera completament la funció resultant. Les lleis de De Morgan formalitzen la interacció entre la negació i les operacions binàries principals, permetent transformar sumes complementades en productes i a l'inrevés: Aquestes relacions resulten imprescindibles per canviar la representació de circuits lògics entre estructures basades en sumes i productes. COMPROVA-HO 12 Quina és l'expressió dual exacta de la igualtat ?

Portes lògiques bàsiques i derivades Els operadors de l'àlgebra s'implementen físicament mitjançant components electrònics anomenats portes lògiques. Cadascuna genera una sortida determinada en funció de les combinacions de les seves entrades. Porta lògica Operador / Funció Expressió Comportament característic NOT Complement Inverteix el nivell lògic de l'entrada. AND Producte lògic Sortida 1 només si totes les entrades valen 1. OR Suma lògica Sortida 1 si com a mínim una entrada val 1. NAND NOT AND Complement de la porta AND; val 0 només si totes les entrades són 1. NOR NOT OR Complement de la porta OR; val 1 únicament quan totes les entrades són 0.

+ = x + y x y = x y + x y x + = x 1 x x y x + y x y x + y Apunts d'Estructura de Computadors: Lògica Digital 9 Porta lògica Operador / Funció Expressió Comportament característic XOR OR exclusiu Sortida 1 quan les dues entrades presenten valors diferents. XNOR NOR exclusiu / Identitat Sortida 1 quan les entrades són idèntiques. Les taules de valors d'aquests operadors reflecteixen directament aquestes relacions (per aprofundir en la construcció sistemàtica de taules completes, vegeu «Funcions lògiques — Taules de veritat i formes canòniques»). COMPROVA-HO 13 Quina sortida produeix una porta XOR quan s'introdueixen els valors i ?

Universalitat i propietat associativa de les portes lògiques La porta OR satisfà la propietat associativa de forma immediata, de manera que avaluar és equivalent a connectar : Esquema de la propietat associativa aplicada a la porta lògica OR. No totes les funcions lògiques compostes mantenen aquest comportament associatiu. L'anàlisi de les portes NAND, NOR i XOR en cadenes de tres entrades demostra diferències fonamentals: No associativitat de la porta NAND: En canvi, associant primer les altres dues variables: Com que , la porta NAND no és associativa.

x y = x y + x y x y = = x y x + y x y x = 1 y = 1 (x + y) + z x + (y + z) = z x y + x y = z x y + z = x y z + x = y z + x y z x y + = z + x y z Apunts d'Estructura de Computadors: Lògica Digital 10 No associativitat de la porta NOR: Mentre que agrupant el segon bloc: Com que ambdues expressions són diferents, la porta NOR no és associativa. Associativitat de la porta XOR: Desenvolupant l'agrupació : Aplicant De Morgan sobre el terme negat, , de manera que l'expressió desplegada queda: Si es resol de manera anàloga l'expressió , s'obté exactament la mateixa suma de quatre productes. Per tant, l'operador XOR compleix la propietat associativa.

Malgrat no complir la propietat associativa, les portes NAND i NOR presenten la propietat de universalitat lògica: amb portes NAND o NOR és possible construir qualsevol circuit lògic sense necessitat d'emprar cap altre tipus de porta. COMPROVA-HO 14 Quina conseqüència té sobre el disseny pràctic que NAND i NOR no siguin associatives? IDEES CLAU L'àlgebra de commutació opera sobre el conjunt binari mitjançant els operadors suma ( ) i producte ( ). El principi de dualitat permet obtenir identitats vàlides intercanviant sumes amb productes i els valors 0 amb 1, sense alterar les variables.

Les lleis de De Morgan estableixen que la negació d'una suma és el producte de complements ( ) i la negació d'un producte és la suma de complements ( ). Les portes NAND i NOR tenen caràcter universal perquè permeten sintetitzar qualsevol funció booleana. Mentre que AND, OR i XOR són associatives, les operacions NAND i NOR no verifiquen la propietat associativa. COMPROVA EL QUE HAS APRÈS 15. Per què no es neguen les variables en obtenir l'expressió dual d'una funció booleana? 16. Com demostra l'àlgebra que la porta NAND no compleix la propietat associativa?

= + z x + y x + y = z (x + y) z = x + y + z x = y + z x (y + z) (x y) z ( y + x x ) y z = ( y + x ) x y z + ( y + x x ) y z = ( y + x ) x y (x + )( + y x y) = xy + x y xyz + z + x y y + x z x y z x (y z) B = 0, 1 + = x + y x y = x y + x y Apunts d'Estructura de Computadors: Lògica Digital 11 Test Encercla la resposta correcta. Les solucions són al final. 17. Quina expressió és el resultat d'aplicar la segona llei d'absorció a x + x'·y? 18. Quina porta lògica produeix un 1 quan les seves dues entrades són iguals? 19. Quina de les operacions següents NO compleix la propietat associativa? 20. Quina afirmació descriu la universalitat de les portes NAND i NOR?

3 Funcions lògiques — Taules de veritat i formes canòniques EN ACABAR SABRÀS Diferenciar la unicitat de la taula de veritat enfront de la multiplicitat d'expressions algebraiques. Construir minterms i expressar funcions en forma canònica disjuntiva (suma de productes). Construir maxterms i expressar funcions en forma canònica conjuntiva (producte de sumes). Identificar i aplicar termes no importa en funcions lògiques incompletament especificades. PENSA-HI ABANS DE LLEGIR 21 Si dues persones dissenyen una expressió algebraica diferent per al mateix circuit, com podem comprovar amb certesa absoluta si fan exactament el mateix?

x a) x' + y b) x · y c) x + y d) Porta XNOR a) Porta NOR b) Porta NAND c) Porta XOR d) XOR a) AND b) NAND c) OR d) Poden implementar qualsevol circuit lògic a) Són equivalents a una porta NOT b) Compleixen totes les propietats associatives c) Tenen taules de veritat idèntiques d) Apunts d'Estructura de Computadors: Lògica Digital 12 Representació de funcions lògiques: taula de veritat i expressió algebraica Una funció lògica descriu el comportament d'una sortida binària a partir d'un conjunt de variables d'entrada booleanes. Aquest comportament es pot formalitzar mitjançant dos mecanismes fonamentals: la taula de veritat i l'expressió algebraica.

La taula de veritat és una representació exhaustiva i única per a cada funció lògica. En ella s'enumeren totes les possibles combinacions d'entrada (exactament files per a variables) acompanyades del valor de sortida corresponent. Per exemple, per a tres variables d'entrada , la taula presenta les 8 combinacions binàries possibles ordenades del 0 al 7: x y z f 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 1 1 1 1 0 En canvi, l'expressió algebraica està constituïda per variables connectades mitjançant operadors binaris (suma lògica, producte lògic i complement).

A diferència de la taula de veritat, l'expressió algebraica no és única, ja que diferents fórmules algebraiques poden descriure exactament la mateixa funció mitjançant les propietats de l'àlgebra booleana (vegeu «Àlgebra de Boole — Postulats, propietats i portes lògiques»). EXEMPLE Considerem les dues expressions següents sobre les variables : Manipulant algebraicament : Aplicant la identitat distributiva (on i ): Comprovant les operacions, veiem que ambdues expressions són equivalents sota manipulació algebraica ( ) tot i tenir aspectes inicials completament diferents.

2n n x, y, z x, y, z f = 1 x + y ˉ z ˉ f = 2 + x ˉz ˉ x + z ˉ xyz f 2 f = 2 ( + z ˉ x ˉ x) + xyz = z ˉ 1 + xyz = + z ˉ xyz A + B = A ˉ A + B A = z ˉ = A ˉ z + z ˉ z(xy) = + z ˉ xy f = 1 f 2 Apunts d'Estructura de Computadors: Lògica Digital 13 COMPROVA-HO 22 Per què una taula de veritat és única per a una funció però l'expressió algebraica no ho és? Minterms i Forma Canònica Disjuntiva (SOP) Per sistematitzar la relació entre la taula de veritat i una expressió algebraica s'empren les formes canòniques. La primera forma d'expressió normalitzada es basa en els minterms.

DEFINICIÓ Un minterm és un producte lògic de totes les variables (directes o complementades) que pren valor 1 per a una única combinació binària de les entrades. Per generar el minterm associat a una fila concreta de la taula: Si la variable val 1 en aquesta fila, s'escriu sense complementar. Si la variable val 0 en aquesta fila, s'escriu complementada. Els minterms s'identifiquen convencionalment amb la lletra minúscula , on el subíndex representa el valor decimal equivalent de la combinació binària.

La forma canònica disjuntiva (o suma de productes, SOP) s'obté sumant lògicament tots els minterms per als quals la funció té com a sortida el valor 1 lògic: Aquesta mateixa suma es pot expressar de manera compacta amb el sumatori de minterms: On la notació estàndard empra el símbol de sumatori: Fila x y z Minterm Maxterm 0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0 5 1 0 1 6 1 1 0 7 1 1 1 m i i f(x, y, z) = + x ˉy ˉz ˉ yz + x ˉ x + y ˉz ˉ x z y ˉ f(x, y, z) = m + 0 m + 3 m + 4 m = 5 m(0, 3, 4, 5) = m(0, 3, 4, 5) f(x, y, z) = m(0, 3, 4, 5) s a dir, m(0, 3, 4, 5) = e ˊ m + 0 m + 3 m + 4 m 5 = x ˉy ˉz ˉ m 0 x + y + z = M 0 z = x ˉy ˉ m 1 x + y + = z ˉ M 1 y = x ˉ z ˉ m 2 x + + y ˉ z = M 2 yz = x ˉ m 3 x + + y ˉ = z ˉ M 3 x = y ˉz ˉ m 4 + x ˉ y + z = M 4 x z = y ˉ m 5 + x ˉ y + = z ˉ M 5 xy = z ˉ m 6 + x ˉ + y ˉ z = M 6 xyz = m 7 + x ˉ + y ˉ = z ˉ M 7 Apunts d'Estructura de Computadors: Lògica Digital 14 ERROR FREQÜENT Un error habitual en els exàmens és intercanviar la regla de complementació: en un minterm el 0 es complementa i l'1 va directe ( ), mentre que en un maxterm el 0 va directe i l'1 es complementa ( ).

Invertir aquesta convenció invalida completament l'expressió canònica. COMPROVA-HO 23 Quin és el minterm corresponent a la combinació x=1, y=0, z=0 en un sistema de 3 variables? Maxterms i Forma Canònica Conjuntiva (POS) La formulació dual de la forma disjuntiva és la canònica conjuntiva, que analitza les files on la sortida és 0 lògic. DEFINICIÓ Un maxterm és una suma lògica de totes les variables (directes o complementades) que pren valor 0 per a una única combinació binària de les entrades. La regla de construcció del maxterm associat a una fila concreta és la inversa de la dels minterms: Si la variable val 0 en aquesta fila, s'escriu sense complementar.

Si la variable val 1 en aquesta fila, s'escriu complementada. Els maxterms s'indiquen amb la lletra majúscula , utilitzant el mateix índex numèric decimal . La forma canònica conjuntiva (o producte de sumes, POS) s'obté multiplicant lògicament tots els maxterms en què la funció val 0 lògic. Per a la mateixa taula anterior, on els zeros es localitzen a les files 1, 2, 6 i 7: Aquesta funció s'expressa de manera abreujada amb el símbol de producte canònic : PER RECORDAR-HO Els minterms i els maxterms d'una mateixa fila són complementaris per les lleis de De Morgan (vegeu «Àlgebra de Boole — Postulats, propietats i portes lògiques»): .

Així mateix, els índexs que no apareixen a la suma de minterms són exactament els que formen el producte de maxterms: . x = 0 x ˉ x = 1 x ˉ M i i f(x, y, z) = (x + y + ) (x + z ˉ + y ˉ z) ( + x ˉ + y ˉ z) ( + x ˉ + y ˉ ) z ˉ M f(x, y, z) = M(1, 2, 6, 7) = M M M M 1 2 6 7 = m ˉ i M i m(0, 3, 4, 5) = M(1, 2, 6, 7) Apunts d'Estructura de Computadors: Lògica Digital 15 ESQUEMA Formes de representació de funcions lògiques COMPROVA-HO 24 Si una funció de 3 variables s'expressa com a sumatori de minterms f = m(0, 2, 5), quina és la seva expressió en producte de maxterms?

Funcions incompletament especificades: termes no importa (don't care) En determinats circuits combinacionals hi ha configuracions d'entrada que mai es produiran en el funcionament real, o bé condicions on el valor de la sortida resulta del tot indiferent per al sistema. Aquestes situacions defineixen les funcions incompletament especificades. El valor que pren la sortida per a aquestes combinacions s'anomena terme no importa (o don't care) i es representa a la taula de veritat mitjançant el símbol X (o la lletra d). Aquests valors podran ser aprofitats posteriorment durant el disseny per simplificar el circuit (vegeu «Simplificació de funcions — Mapes de Karnaugh»).

Taula de veritat Descripció exhaustiva i única Expressió algebraica Formulació no única Forma disjuntiva Suma de minterms per a sortides 1 Forma conjuntiva Producte de maxterms per a sortides 0 Apunts d'Estructura de Computadors: Lògica Digital 16 Taula de veritat per a mesos de 31 dies amb termes no especificats. Un exemple clau d'aquest tipus de funció és el circuit que detecta si un determinat mes de l'any té 31 dies: Com que l'any conté 12 mesos, es requereixen 4 variables d'entrada ( ), les quals proporcionen combinacions totals. La combinació 0000 (fila 0) no correspon a cap mes i s'assigna com a terme no especificat (X).

Els mesos de gener a desembre es codifiquen de l'1 al 12: els mesos amb 31 dies (gener, març, maig, juliol, agost, octubre i desembre) tenen valor de sortida 1; la resta de mesos vàlids prenen valor 0. Les configuracions 13, 14 i 15 no representen cap mes de l'any, per la qual cosa la seva sortida s'assigna també a X perquè mai es donaran com a entrades vàlides.

Mes Índex Sortida (31 dies) - 0 0 0 0 0 X Gener 1 0 0 0 1 1 Febrer 2 0 0 1 0 0 Març 3 0 0 1 1 1 Abril 4 0 1 0 0 0 Maig 5 0 1 0 1 1 a , a , a , a 3 2 1 0 2 = 4 16 a 3 a 2 a 1 a 0 Apunts d'Estructura de Computadors: Lògica Digital 17 Mes Índex Sortida (31 dies) Juny 6 0 1 1 0 0 Juliol 7 0 1 1 1 1 Agost 8 1 0 0 0 1 Setembre 9 1 0 0 1 0 Octubre 10 1 0 1 0 1 Novembre 11 1 0 1 1 0 Desembre 12 1 1 0 0 1 - 13 1 1 0 1 X - 14 1 1 1 0 X - 15 1 1 1 1 X COMPROVA-HO 25 Per què les combinacions 0, 13, 14 i 15 es marquen amb una X en l'exemple dels mesos de l'any? IDEES CLAU La taula de veritat d'una funció lògica és única, mentre que existeixen múltiples expressions algebraiques equivalents.

Un minterm és un producte lògic de totes les variables que val 1 per a una sola fila (les variables a 0 es complementen). Un maxterm és una suma lògica de totes les variables que val 0 per a una sola fila (les variables a 1 es complementen). La forma canònica disjuntiva suma els minterms dels 1 lògics, i la conjuntiva multiplica els maxterms dels 0 lògics. Els termes no importa (X) representen combinacions que no intervenen o no es produeixen mai en el funcionament del circuit. COMPROVA EL QUE HAS APRÈS 26. Com es construeix el maxterm M associat a la combinació binària 101? 27.

Quina relació tenen els conjunts d'índexs de la forma canònica disjuntiva i de la forma canònica conjuntiva d'una funció completament especificada? a 3 a 2 a 1 a 0 Apunts d'Estructura de Computadors: Lògica Digital 18 Test Encercla la resposta correcta. Les solucions són al final. 28. Quina de les següents afirmacions sobre la representació de funcions lògiques és correcta? 29. Com es representa el minterm m per a les variables d'entrada x, y, z? 30. En la construcció d'un maxterm, com s'escriu una variable que pren valor 1 en la taula? 31. Per què s'utilitzen termes 'no importa' (X) en funcions de 4 variables que codifiquen els mesos?

4 Simplificació de funcions — Mapes de Karnaugh EN ACABAR SABRÀS Identificar i aplicar l'adjacència lògica basada en el codi Gray en mapes de Karnaugh. Formar agrupacions rectangulars òptimes de potències de 2 en mapes de 2 a 6 variables. Obtenir expressions mínimes en forma de suma de productes o producte de sumes. Optimitzar funcions incompletament especificades mitjançant l'ús correcte de les condicions no importa. PENSA-HI ABANS DE LLEGIR 32 Per què ajuntar cel·les que només difereixen en una variable permet esborrar aquesta variable d'una funció booleana?

L'expressió algebraica sempre és única a) La taula de veritat és única b) Els minterms sumen les sortides a 0 c) Cada funció té una única expressió d) x̄ + y + z̄ a) x + ȳ + z b) x̄ · y · z̄ c) x̄ · ȳ · z d) Igual que en un minterm a) Sense complementar b) Multiplicada per zero c) Complementada d) Perquè representen un error de circuit a) Perquè 4 variables generen 16 combinacions b) Perquè les taules sempre tenen 12 files c) Perquè el mes de febrer varia d) Apunts d'Estructura de Computadors: Lògica Digital 19 Principis dels mapes de Karnaugh i adjacència lògica La simplificació de funcions lògiques pretén minimitzar el nombre de termes i de literals d'una expressió booleana.

El mapa de Karnaugh és un mètode gràfic que reorganitza la taula de veritat (vegeu «Funcions lògiques — Taules de veritat i formes canòniques») en una graella bidimensional. La clau d'aquest mètode rau en la disposició de les cel·les: dues posicions contigües presenten sempre adjacència lògica. Als mapes de Karnaugh, les cel·les adjacents només difereixen en el valor d'una variable gràcies a l'ordenació per codi Gray. Aquesta seqüència (00, 01, 11, 10) garanteix que, en passar d'una casella a una altra veïna, només commuti un bit. Així s'aplica directament la propietat d'absorció de l'àlgebra booleana (vegeu «Àlgebra de Boole — Postulats, propietats i portes lògiques»): .

DEFINICIÓ Un implicant primer és el producte lògic que resulta d'agrupar el nombre màxim possible de cel·les adjacents amb valor 1 en potències de dues unitats ( ). Si no està contingut completament en cap altre grup més gran, constitueix un candidat indispensable per a l'expressió simplificada mínima. En cobrir els termes 1 per obtenir la suma de productes, les variables que mantenen el valor 1 s'escriuen directes, les que conserven el valor 0 es representen complementades, i les que canvien d'estat dins l'agrupació queden eliminades. COMPROVA-HO 33 Per quina raó les columnes d'un mapa de Karnaugh es numeren 00, 01, 11, 10 i no pas en ordre binari natural?

Mapes de 2, 3 i 4 variables En un mapa de 2 variables ( ), disposem de 4 cel·les. Per a una funció amb minterms com , la unió de cel·les adjacents permet extreure termes simplificats com unint grups de dues caselles. Per a 3 variables ( ), la taula compta amb 8 cel·les distribuïdes en dues files ( ) i quatre columnes ( ). Cal tenir en compte que els extrems dret i esquerre també són adjacents entre si, atès que 00 i 10 només difereixen en un bit. Per exemple, si tenim uns als minterms 4 ( ) i 5 ( ), formen un grup de dues cel·les que simplifica a , mentre que les cantonades de les columnes 00 i 10 poden unir-se per formar termes com .

En funcions de 4 variables ( ), la matriu consta de 16 cel·les ( ). Les regles d'agrupació exigeixen formar rectangles o quadrats de grandària 2^k cel·les (1, 2, 4, 8 o 16): Les vores oposades (superior amb inferior, i esquerra amb dreta) són contigües. Les quatre cantonades del mapa (cel·les 0, 2, 8 i 10) formen un bloc vàlid de 4 cel·les, el qual elimina dues variables i resulta en . x y + x = y ˉ x (y + ) = y ˉ x 2k a, b f(a, b) = b + a ˉ ab + ab ˉ a + b x, y, z x yz 100 2 101 2 x y ˉ z ˉ a, b, c, d 4 × 4 b ˉd ˉ Apunts d'Estructura de Computadors: Lògica Digital 20 Diagrama d'agrupacions en mapa de Karnaugh de 4 variables.

A la figura anterior s'observa com la funció definida per es redueix mitjançant diferents associacions: un bloc de 4 central-superior ( ), les quatre cantonades ( ), un grup de 4 a les vores laterals ( ) i un grup de dues cel·les ( ), generant l'expressió . De la mateixa manera, a partir de termes com , es traslladen els uns a la graella per cobrir-los amb blocs optimitzats que donen lloc a . COMPROVA-HO 34 Quantes variables s'eliminen en un mapa de 4 variables en realitzar una agrupació rectangular de 8 cel·les?

Mapes de 5 i 6 variables: adjacència tridimensional Quan el nombre de variables supera les 4, el pla bidimensional esdevé insuficient i cal recórrer a la superposició de submapes de 16 cel·les per avaluar l'adjacència en un espai tridimensional. En el cas de 5 variables ( ), s'utilitzen dos submapes de 4 variables: un per a i l'altre per a . Dues cel·les són adjacents si ocupen la mateixa fila i columna en ambdós submapes superposats, variant exclusivament el valor de la variable .

m(0, 1, 2, 4, 5, 6, 8, 10, 13, 15) a ˉc ˉ b ˉd ˉ a ˉd ˉ abd f = + a ˉc ˉ + b ˉd ˉ abd + a ˉd ˉ + a ˉb ˉc ˉ bd + a ˉ abc + a d + b ˉc ˉ ab + a ˉb ˉc ˉ d + c ˉ bd + ab a, b, c, d, e a = 0 a = 1 a Apunts d'Estructura de Computadors: Lògica Digital 21 Esquema d'adjacència tridimensional en un mapa de 5 variables. A la il·lustració es mostra l'anàlisi de la cel·la 5 ( ): a més de tenir adjacències al seu propi submapa amb les cel·les 1, 4, 7 i 13, és adjacent directament a la casella 21 ( ) del submapa veí. Així, per a la funció , s'obtenen agrupacions com: El grup de 4 cel·les format per {0, 1, 16, 17}, que elimina i dues variables més, resultant en .

El grup de 4 cel·les format per les cantonades {8, 10, 24, 26}, donant . El grup pla de 4 en format per {0, 1, 4, 5}, que genera . El minterm aïllat 31, que es manté com abcde. L'expressió simplificada final és . En funcions de 6 variables ( ), s'empren 4 submapes de 16 cel·les cadascun, indexats segons el codi Gray per a les variables : 00, 01, 11, 10. L'adjacència es manté tant en el pla de cada graella com entre submapes contigus horitzontalment o verticalment (i entre els blocs extrems oposats 00 i 10).

00101 2 10101 2 m(0, 1, 4, 5, 8, 10, 16, 17, 24, 26, 31) a b ˉc ˉd ˉ bc ˉe ˉ a = 0 a ˉb ˉd ˉ f = abcde + b + c ˉe ˉ + b ˉc ˉd ˉ a ˉb ˉd ˉ a, b, c, d, e, f ab Apunts d'Estructura de Computadors: Lògica Digital 22 Esquema de simplificació amb 4 submapes per a 6 variables. Per exemple, a la funció , la superposició permet trobar implicants com: Unió de files completes entre submapes: {0, 1, 2, 3, 32, 33, 34, 35} resulta en . Parella superposada entre i en les cel·les {10, 14, 26, 30}, donant . Grups que combinen cel·les entre i , com {29, 61} per a o {26, 30, 58, 62} per a . Termes puntuals o de parelles planes com , i .

COMPROVA-HO 35 En un mapa de 6 variables, amb quins submapes és adjacent el bloc assignat a ab = 00? Obtenció del producte de sumes i termes no importa A més d'agrupar uns per obtenir sumes de productes, el mapa de Karnaugh permet deduir el producte de sumes mínim agrupant els zeros de la funció. Un maxterm és una suma lògica de totes les variables (directes o complementades) que pren valor 0 per a una única combinació. Per extreure els factors de suma simplificats a partir de grups de zeros veïns, s'aplica el criteri dual (vegeu «Àlgebra de Boole — Postulats, propietats i portes lògiques»): La variable que roman constant amb valor 0 s'escriu sense complementar.

La variable que roman constant amb valor 1 s'escriu complementada. m(0, 1, 2, 3, 10, 14, 15, 26, 29, 30, 32, 33, 34, 35, 45, 48, 49, 58, 61, 62) b ˉc ˉd ˉ ab = 00 ab = 10 ce a ˉ f ˉ ab = 01 ab = 11 bcd f e ˉ bce f ˉ cde a ˉb ˉ acd ˉe ˉ acd e ˉf ˉ Apunts d'Estructura de Computadors: Lògica Digital 23 Les variables que commuten s'eliminen del factor de suma. Per a la funció expressada com a producte canònic , s'ubiquen els zeros al mapa i s'agrupen de dos en dos o individualment: Grup de cel·les (zeros) Valors constants Factor suma resultant {1, 5} {6, 14} {12, 14} {11} (aïllat) El producte final és: .

D'altra banda, en dissenys pràctics sorgeixen funcions incompletament especificades que inclouen termes no importa (denotats com o ). Aquestes combinacions mai no es produeixen a l'entrada o la seva sortida no té rellevància funcional. ERROR FREQÜENT Els termes 'don't care' ( ) no s'han d'agrupar mai de manera obligatòria. Tractar-los com a uns o zeros necessaris crea termes redundants que compliquen el circuit. Una només s'inclou si augmenta la grandària d'un grup existent d'uns (o de zeros), aconseguint així simplificar-lo. Si una queda lliure, simplement s'ignora. Considerem l'exemple d'una funció incompleta expressada en minterms i termes no importa: .

Aquesta mateixa funció es pot descriure en maxterms amb les cel·les buides com a zeros: . g(a, b, c, d) = M(1, 5, 6, 12, 14, 11) a = 0, c = 0, d = 1 (a + c + ) d ˉ b = 1, c = 1, d = 0 ( + b ˉ + c ˉ d) a = 1, b = 1, d = 0 ( + a ˉ + b ˉ d) a = 1, b = 0, c = 1, d = 1 ( + a ˉ b + + c ˉ ) d ˉ g(a, b, c, d) = ( + a ˉ + b ˉ d)( + a ˉ b + + c ˉ )( + d ˉ b ˉ + c ˉ d)(a + c + ) d ˉ d X X X X f(a, b, c, d) = m(1, 5, 6, 9) + d(2, 10, 12, 13, 15) f(a, b, c, d) = M(0, 3, 4, 7, 8, 11, 14) + d(2, 10, 12, 13, 15) Simplificació agrupant uns i aprofitant 'X': Els minterms 1, 5, 9 s'uneixen amb la de la cel·la 13 formant una columna de 4 ( ). El minterm 6 s'uneix amb la del 2 per formar un grup de 2 ( ).

S'assigna així valor 1 a les cel·les {2, 13} i valor 0 a {10, 12, 15}. El resultat és . 1 X d c ˉ X c a ˉ d ˉ f = d + c ˉ c a ˉ d ˉ Simplificació agrupant zeros i aprofitant 'X': S'agrupen els zeros {0, 4, 8} amb la de la cel·la 12 ( ), els zeros {3, 7, 11} amb la de la cel·la 15 ( ), i el zero 14 s'uneix amb les de les cel·les 10, 12 i 15 per consolidar . El resultat és . 2 X c + d X + c ˉ d ˉ X + a ˉ c ˉ f = (c + d)( + c ˉ d)( + a ˉ ) c ˉ Apunts d'Estructura de Computadors: Lògica Digital 24 PROCÉS Procediment de simplificació amb mapa de Karnaugh 1 Graella i codi Gray Distribuir les cel·les ordenant files i columnes segons codi Gray.

2 Transferència de valors Col·locar els 1, 0 i termes don't care provinents de la funció. 3 Formació de grups Cobrir els valors objectiu fent blocs rectangulars màxims de mida 2^k. 4 Lectura d'implicants Eliminar variables canviants i conservar literals fixos de cada bloc. IDEES CLAU Els mapes de Karnaugh empren l'ordenació per codi Gray per garantir que les cel·les veïnes presentin adjacència lògica i difereixin en una única variable. Les agrupacions han de ser rectangulars i de grandària cel·les, cobrint vores oposades i cantonades. En mapes de 5 i 6 variables, l'adjacència s'estén tridimensionalment comparant les mateixes posicions entre submapes adjacents de 16 cel·les.

L'agrupació de zeros genera un producte de sumes mínim assignant la variable complementada si val 1 i sense complementar si val 0. Els termes 'don't care' ( ) només s'utilitzen si permeten expandir un grup existent, sense cap obligació d'agrupar-los si resten aïllats. COMPROVA EL QUE HAS APRÈS 36. Com s'escriu una variable que pren valor 0 de manera constant en una agrupació de zeros en el mapa de Karnaugh? 37. Quina condició és necessària per poder aprofitar un terme no importa (don't care) en una simplificació? Test Encercla la resposta correcta. Les solucions són al final. 38. Per què les cel·les adjacents d'un mapa de Karnaugh només canvien en una variable? 39.

Quina mida ha de tenir obligatòriament qualsevol agrupació vàlida al mapa de Karnaugh? 2k X Perquè apliquen el complement a dos a) Perquè s'ordenen en binari pur b) Perquè són funcions incompletes c) Per l'ordenació en codi Gray d) Potència de dos ( ) a) 2k Nombre senar de cel·les b) Qualsevol nombre parell c) Múltiple de tres cel·les d) Apunts d'Estructura de Computadors: Lògica Digital 25 40. Quina forma pren una variable que val 1 en agrupar zeros per obtenir maxterms? 41. Com s'han de tractar els termes 'don't care' (X) aïllats que no amplien cap grup?

5 Circuits combinacionals — Estructures a dos nivells, anàlisi i síntesi EN ACABAR SABRÀS Transformar estructures a dos nivells AND-OR a NAND-NAND i OR-AND a NOR-NOR. Analitzar un esquema combinacional obtenint les funcions lògiques i la taula de veritat. Sintetitzar un circuit combinacional a partir d'una descripció funcional complint restriccions de disseny. PENSA-HI ABANS DE LLEGIR 42 Per què en la fabricació real de circuits integrats es prefereix utilitzar exclusivament portes NAND o NOR en lloc de combinar AND i OR? Els circuits combinacionals es caracteritzen perquè les seves sortides depenen exclusivament de la combinació actual dels valors d'entrada.

En aquest tema s'estudien tant les topologies clàssiques de realització amb portes a dos nivells com les metodologies sistemàtiques d'anàlisi i disseny.

ESQUEMA Circuits combinacionals Apareix sense complementar a la suma a) Apareix complementada a la suma b) Apareix directa al producte c) S'elimina automàticament del terme d) S'agrupen sols com a minterms a) Es converteixen obligatòriament en 1 b) S'ignoren completament c) Invaliden el mapa de Karnaugh d) Estructures a 2 nivells Formes canòniques i universals AND-OR a NAND-NAND Equivalència per sumes de productes OR-AND a NOR-NOR Equivalència per productes de sumes Metodologies Tractament del circuit lògic Anàlisi Del circuit a la funció lògica Síntesi De l'especificació al circuit físic Apunts d'Estructura de Computadors: Lògica Digital 26 Estructures de portes a dos nivells Quan s'expressa una funció lògica com a suma de productes o com a producte de sumes, el circuit resultant s'organitza en dues etapes consecutives de portes lògiques.

Els inversors connectats directament a les entrades no es consideren un nivell addicional de retard en aquesta classificació bàsica. Esquema que mostra la porta NOT d'entrada sense comptar com a nivell. Suma de productes: AND-OR i NAND-NAND Una expressió com a suma de productes requereix un primer nivell de portes AND que generen els termes producte i un segon nivell format per una única porta OR que suma aquests termes.

Per exemple, per a la funció lògica: Aplicant la doble negació i les lleis de De Morgan (vegeu «Àlgebra de Boole — Postulats, propietats i portes lògiques»), aquesta estructura es transforma de manera directa en una xarxa equivalent de portes NAND: Una estructura de dos nivells AND-OR és lògicament equivalent a una estructura NAND-NAND. Aquesta propietat és essencial en tecnologia electrònica gràcies a la propietat de conjunt universal que tenen les portes NAND, amb les quals es pot implementar qualsevol circuit lògic (per exemple, unint les entrades d'una porta NAND s'obté un inversor ).

f(x, y, z) = x y ˉ + z ˉ x ˉ z + x ˉ y f(x, y, z) = = x + z + y y ˉ z ˉ x ˉ x ˉ ( ) ( ) ( ) x y ˉ z ˉ z x ˉ y x ˉ = a a a ˉ Apunts d'Estructura de Computadors: Lògica Digital 27 Producte de sumes: OR-AND i NOR-NOR D'altra banda, una forma com a producte de sumes utilitza portes OR en el primer nivell i una porta AND en el segon nivell: Esquema d'estructura clàssica a dos nivells de tipus OR-AND. Considerem la funció en forma conjuntiva: Negant dues vegades l'expressió i aplicant la llei de De Morgan sobre el producte exterior ( ): Una estructura de dos nivells OR-AND és lògicament equivalent a una estructura NOR-NOR. Això permet fabricar el sistema emprant exclusivament portes d'aquest tipus.

COMPROVA-HO 43 Per què una estructura AND-OR es pot substituir directament per portes NAND sense canviar les entrades? Anàlisi de circuits combinacionals L'anàlisi combinacional consisteix a deduir el comportament funcional o equacions de sortida a partir de l'esquema d'un circuit existent.

El procediment s'inicia etiquetant els punts o nodes interns intermedis i expressant la seva funció booleana d'esquerra a dreta: f(x, y, z) = (x + y + z) ( + x ˉ y) (x + ) z ˉ = a b + a ˉ b ˉ f(x, y, z) = = (x + y + z) ( + y) (x + ) x ˉ z ˉ ( ) + ( ) + ( ) x + y + z + y x ˉ x + z ˉ Apunts d'Estructura de Computadors: Lògica Digital 28 Esquema d'anàlisi d'un circuit combinacional amb nodes intermedis etiquetats. En el circuit representat, disposem de 3 entrades ( ) i 2 sortides ( ).

Establim primer les equacions de les sortides intermèdies de les portes AND: A continuació, deduïm les expressions algebraiques de les sortides finals combinant els termes: Un cop obtingudes les equacions simplificades, es pot avaluar cada combinació d'entrada per construir la taula de veritat completa (vegeu «Funcions lògiques — Taules de veritat i formes canòniques»). ERROR FREQÜENT En analitzar circuits amb portes NOR, un error típic és oblidar negar la suma global o calcular com a . Recordeu aplicar correctament De Morgan: la negació d'una suma lògica és sempre el producte de les variables negades, és a dir, .

Síntesi de circuits combinacionals La síntesi de circuits combinacionals és el procés invers a l'anàlisi: a partir de les especificacions verbals o funcionals d'un sistema, es dissenya l'esquema de portes òptim. {x, y, z} {A, B} P = 1 x ˉ y P = 2 y z ˉ A = = x + P 1 = x + y x ˉ x ˉ ( ) = y x ˉ x ˉ (x + ) = y ˉ x ˉ y ˉ B = P + 1 P = 2 x ˉ y + y z ˉ x + P 1 + x ˉ P 1 = a + b a ˉ b ˉ Definició d'entrades i sortides: Identificar les variables binàries d'entrada i les funcions que cal generar a la sortida. 1 Elaboració de la taula de veritat: Llistar totes les combinacions possibles i assignar el valor requerit de la sortida per a cadascuna.

2 Simplificació lògica: Obtenir l'expressió algebraica mínima mitjançant procediments com els mapes de Karnaugh (vegeu «Simplificació de funcions — Mapes de Karnaugh»). 3 Apunts d'Estructura de Computadors: Lògica Digital 29 EXEMPLE: CIRCUIT DE VOTACIÓ PER MAJORIA DE 4 VARIABLES Es vol dissenyar un sistema amb 4 entrades ( ) que activi la sortida únicament quan la majoria estricta d'entrades es trobi a nivell 1 lògic (és a dir, 3 o 4 entrades a 1).

a b c d f 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 1 1 1 0 0 0 0 1 0 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 0 0 0 1 1 0 1 1 1 1 1 0 1 1 1 1 1 1 Traslladant aquests valors a un mapa de Karnaugh de 4 variables, s'agrupen els uns en quatre conjunts adjacents de 2 cel·les (que comparteixen el minterm 15, ), resultant la funció simplificada: Aquesta expressió requereix 4 portes AND de 3 entrades en el primer nivell i una porta OR de 4 entrades en el segon nivell, directament convertible a 5 portes NAND si el disseny ho requereix. Dibuix de l'esquema: Traçar la interconnexió de portes atenent a les restriccions del ventall d'entrades (fan-in) o la tecnologia disponible.

4 a, b, c, d f = 1 a b c d f = a b d + a c d + b c d + a b c Apunts d'Estructura de Computadors: Lògica Digital 30 COMPROVA-HO 44 Quants termes producte mínims té la funció de votació per majoria de 4 entrades i quin tamany té cadascun? IDEES CLAU Les estructures a dos nivells AND-OR equivalen directament a xarxes formades íntegrament per portes NAND-NAND. Les estructures OR-AND es transformen de manera directa en xarxes NOR-NOR aplicant les lleis de De Morgan. L'anàlisi combinacional obté les funcions i la taula de veritat deduint les equacions intermèdies des de les entrades cap a les sortides.

La síntesi combinacional segueix el procés invers: d'una especificació funcional es genera la taula de veritat, se simplifica i s'implementa l'esquema de portes. Els inversors connectats directament a les línies d'entrada no comptabilitzen com un nivell de retard addicional en les estructures a dos nivells. COMPROVA EL QUE HAS APRÈS 45. Com s'expressa el terme producte a la sortida d'una porta NAND amb entrades i ? 46. Quin paper juguen les restriccions tecnològiques (com el nombre màxim d'entrades d'una porta) en l'etapa final de síntesi? Test Encercla la resposta correcta. Les solucions són al final. 47. Quina transformació lògica directa és equivalent a una xarxa AND-OR a dos nivells? 48.

Com es comporta una porta NAND de dues entrades si unim totes dues entrades? 49. En el mètode d'anàlisi de circuits, quin és el primer pas un cop identificat l'esquema? x ˉ y x ˉ y Xarxa XOR-NAND a) Xarxa NOR-NOR b) Xarxa OR-AND c) Xarxa NAND-NAND d) Com una sortida a 1 constant a) Com una porta OR b) Com una porta AND c) Com un inversor NOT d) Dibuixar el mapa de Karnaugh a) Obtenir la taula de veritat b) Canviar totes les portes per NOR c) Etiquetar i formular els nodes intermedis d) Apunts d'Estructura de Computadors: Lògica Digital 31 50. En el circuit de decisió per majoria de 4 variables, per a quantes combinacions la sortida val 1?

5 combinacions a) 4 combinacions b) 3 combinacions c) 8 combinacions d) Apunts d'Estructura de Computadors: Lògica Digital 32 6 Descodificadors, codificadors i comparadors EN ACABAR SABRÀS Descriure el principi de funcionament i les equacions d'un descodificador binari. Dissenyar l'expansió d'un descodificador de major capacitat emprant mòduls menors i línies d'habilitació. Construir la taula d'operació d'un codificador de prioritat integrant la sortida Input Active. Formular el circuit d'un comparador d'igualtat mitjançant portes XNOR i analitzar comparadors de magnitud.

PENSA-HI ABANS DE LLEGIR 51 Com pot un circuit determinar quina de dues línies s'ha d'atendre si totes dues s'activen exactament al mateix instant? Descodificadors binaris Un descodificador és un mòdul combinacional d'escala mitjana d'integració (MSI) que disposa de entrades i exactament sortides. La seva funció consisteix a activar una única línia de sortida per a cadascuna de les possibles combinacions binàries presents a les entrades. DEFINICIÓ Un descodificador de a és un circuit combinacional que activa la sortida que correspon al valor numèric binari fixat pel conjunt de les seves entrades.

Cada sortida materialitza de forma directa un minterm diferent (vegeu «Funcions lògiques — Taules de veritat i formes canòniques»). Considerem un descodificador de 2 entrades ( ) i 4 sortides ( ), conegut habitualment com a DEC (2 a 4). Quan la paraula d'entrada és , s'activa la línia ; amb , s'activa ; amb , s'activa ; i amb , s'activa .

E1 E0 S3 S2 S1 S0 Sortida activa 0 0 0 0 0 1 Blocs MSI combinacionals 6 Descodificadors, codificadors i comparadors 7 Multiplexors i generació de funcions n 2n n 2n E , E 1 0 S , S , S , S 3 2 1 0 E E = 1 0 00 2 S 0 E E = 1 0 012 S 1 E E = 1 0 10 2 S 2 E E = 1 0 11 2 S 3 S 0 Apunts d'Estructura de Computadors: Lògica Digital 33 E1 E0 S3 S2 S1 S0 Sortida activa 0 1 0 0 1 0 1 0 0 1 0 0 1 1 1 0 0 0 Les equacions lògiques associades a cadascuna d'aquestes sortides coincideixen amb cadascun dels productes canònics fonamentals: Esquema lògic de les portes AND que formen un descodificador 2:4.

Cadascuna de les sortides es sintetitza directament mitjançant una porta AND amb les entrades directes o invertides segons pertoqui. COMPROVA-HO 52 Quina sortida s'activa en un descodificador 2:4 si l'entrada és E1=1 i E0=0? Entrada d'habilitació (Enable) i expansió de descodificadors Per ampliar la funcionalitat dels mòduls descodificadors s'incorpora una entrada de control denominada enable ( ).

Quan el senyal d'habilitació es troba actiu ( ), el circuit opera amb normalitat; si es troba desconnectat o desactivat ( ), totes les línies de sortida forcen el seu estat a S 1 S 2 S 3 S = 0 , S = E ˉ1E ˉ0 1 E , S = E ˉ1 0 2 E , S = 1E ˉ0 3 E E 1 0 e e = 1 e = 0 Apunts d'Estructura de Computadors: Lògica Digital 34 0 amb independència de les dades d'entrada. Mitjançant l'ús de l'entrada enable i d'inversors, és possible construir estructures de major capacitat interconnectant blocs idèntics de menor ordre. Aquest procediment es coneix com a expansió modular. Símbol lògic d'un mòdul descodificador de 3 a 8 línies.

Per construir un descodificador de 3 a 8 a partir de dos blocs de 2 a 4: A2 A1 A0 B7 B6 B5 B4 B3 B2 B1 B0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 S'assignen els bits de menor pes ( ) en paral·lel a les entrades de dades ( ) de tots dos descodificadors 2:4. 1 A , A 1 0 x , x 1 0 S'empra el bit de major pes ( ) com a senyal de selecció de bloc. 2 A 2 Es connecta directament a l'entrada enable ( ) del mòdul inferior i mitjançant un inversor ( ) a l'entrada enable ( ) del superior.

3 A 2 e A ˉ2 e Apunts d'Estructura de Computadors: Lògica Digital 35 A2 A1 A0 B7 B6 B5 B4 B3 B2 B1 B0 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 Quan , el mòdul inferior resta inhabilitat i el mòdul superior genera les sortides a . Quan , el bloc superior queda desactivat i l'inferior activa les sortides a segons el valor dels bits inferiors. ERROR FREQÜENT Connectar un bit de menor pes (com ara ) a l'habilitació en lloc del bit més significatiu ( ). Si es connecta a l'enable, els mòduls s'alternaran amb nombres parells i senars, de manera que les sortides quedaran desordenades i no seguiran la seqüència numèrica contínua de a .

COMPROVA-HO 53 Quants descodificadors de 2:4 calen per construir un descodificador de 3:8? Codificadors bàsics i de prioritat La funció d'un codificador és exactament la inversa a la d'un descodificador: rep línies d'entrada i genera a la sortida el codi binari de bits corresponent a la línia que s'ha activat.

En un codificador elemental de 4 entrades ( ) i 2 sortides ( ), se suposa la hipòtesi que només una entrada pot romandre activa alhora: E3 E2 E1 E0 S1 S0 Línia codificada 0 0 0 1 0 0 0 0 0 1 0 0 1 1 0 1 0 0 1 0 2 1 0 0 0 1 1 3 D'aquesta taula es dedueixen les funcions lògiques immediates: Aquest esquema presenta dues mancances crítiques en circuits reals: no pot tractar la presència de múltiples entrades actives simultànies ni distingeix la situació on l'entrada activa és d'aquella en què totes les entrades valen zero (ja que ambdues generen la sortida ).

A = 2 0 B 0 B 3 A = 2 1 B 4 B 7 A 0 A 2 A 0 B 0 B 7 2n n E , E , E , E 3 2 1 0 S , S 1 0 S = 1 E + 2 E , S = 3 0 E + 1 E 3 E 0 S S = 1 0 00 Apunts d'Estructura de Computadors: Lògica Digital 36 Diagrama de blocs funcional d'un codificador de 4 a 2 línies. Per resoldre aquesta situació s'utilitza el codificador de prioritat. En cas d'activació concurrent, l'índex superior té preferència absoluta sobre els inferiors ( ). Quan un bit de rang alt val 1, la resta de bits inferiors esdevenen condicions que no importen o don't care ( ).

Addicionalment s'incorpora la sortida Input Active (IA), la qual pren el valor 1 si almenys una de les entrades està activa i 0 si cap ho està: E3 E2 E1 E0 S1 S0 IA 0 0 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 x 0 1 1 0 1 x x 1 0 1 1 x x x 1 1 1 Així es distingeix de manera unívoca l'absència d'entrades actives ( ) del cas d'activació de la línia ( amb sortida 00). E > 3 E > 2 E > 1 E 0 x IA = 0 E 0 IA = 1 Apunts d'Estructura de Computadors: Lògica Digital 37 COMPROVA-HO 54 En un codificador de prioritat de 4 entrades on E3 té màxima prioritat, quina sortida S1S0 i IA s'obté per a E=0110?

Comparadors de magnitud i d'igualtat Un comparador és un bloc MSI que rep dues paraules binàries de bits i determina quina relació d'ordre o igualtat tenen entre si. El comparador d'igualtat disposa de entrades (dividides en dues paraules i de bits) i d'una única sortida. La sortida s'activa si i només si tots els bits homòlegs d'ambdues paraules són idèntics. Per a un únic bit, la comparació es duu a terme mitjançant la funció d'equivalència lògica: Per comparar paraules de 4 bits ( i ), cada parell de bits s'avalua amb una porta XNOR (o una porta XOR seguida d'un inversor).

Les 4 comparacions parcials es combinen finalment amb una porta AND: D'altra banda, el comparador de magnitud proporciona 3 línies de sortida exclusives: , i . Opcionalment també pot generar sortides compostes com ara . Només una de les condicions bàsiques pot romandre activa simultàniament.

A (a1 a0) B (b1 b0) S1 (B > A) S2 (A = B) S3 (A > B) S4 (A B) 00 00 0 1 0 1 00 01 1 0 0 0 00 10 1 0 0 0 00 11 1 0 0 0 01 00 0 0 1 1 01 01 0 1 0 1 01 10 1 0 0 0 01 11 1 0 0 0 10 00 0 0 1 1 10 01 0 0 1 1 10 10 0 1 0 1 10 11 1 0 0 0 11 00 0 0 1 1 n 2n A B n a = b = a XOR b a XNOR b = ab + a ˉb ˉ A = a a a a 4 3 2 1 B = b b b b 4 3 2 1 (A = B) = (a XNOR b ) AND (a XNOR b ) AND (a XNOR b ) AND (a XNOR b ) 1 1 2 2 3 3 4 4 S (B > 1 A o A < B) S (A = 2 B) S (A > 3 B) S (A 4 B) Apunts d'Estructura de Computadors: Lògica Digital 38 A (a1 a0) B (b1 b0) S1 (B > A) S2 (A = B) S3 (A > B) S4 (A B) 11 01 0 0 1 1 11 10 0 0 1 1 11 11 0 1 0 1 ESQUEMA Mòduls combinacionals MSI COMPROVA-HO 55 Quina porta lògica fonamental determina la coincidència bit a bit en un comparador d'igualtat?

Descodificador n entrades a 2^n sortides Bàsic amb Enable Control d'activació global Expansió modular Mòduls petits per fer-ne de grans Codificador 2^n entrades a n sortides Codificador de prioritat Resolució de concurrències Línia Input Active Indica presència d'entrades Comparador Compara dues paraules binàries Comparador d'igualtat Basat en portes XNOR Comparador de magnitud Detecta menor, igual o major Apunts d'Estructura de Computadors: Lògica Digital 39 IDEES CLAU Un descodificador converteix una combinació binària de entrades en l'activació d'una única de les sortides disponibles.

L'entrada Enable permet desactivar totes les sortides del descodificador i resulta clau per connectar mòduls en cascada i ampliar la paraula d'entrada. Els codificadors bàsics requereixen exclusivitat estricta a l'entrada i no distingeixen el valor zero de la inactivitat. El codificador de prioritat assigna la sortida al bit actiu amb més pes i fa servir el senyal Input Active (IA) per indicar si hi ha algun valor entrant. Els comparadors d'igualtat empren portes XNOR connectades a una porta AND final per detectar coincidència bit a bit, mentre que els de magnitud discriminen menor, igual o major. COMPROVA EL QUE HAS APRÈS 56.

Com s'utilitza l'entrada Enable per expandir dos descodificadors de 2:4 cap a un de 3:8? 57. Quina funció compleix el senyal Input Active (IA) en un codificador de prioritat? BLOCS MSI COMBINACIONALS 7 Multiplexors i generació de funcions EN ACABAR SABRÀS Deduir l'equació lògica i el funcionament intern d'un multiplexor i demultiplexor. Configurar mòduls de multiplexors múltiples amb línies de control compartides. Implementar funcions lògiques generals de n+1 variables utilitzant un multiplexor de n línies de selecció. Relacionar la correspondència funcional i estructural entre descodificadors i demultiplexors.

PENSA-HI ABANS DE LLEGIR 58 Com és possible sintetitzar qualsevol funció lògica de 4 variables utilitzant només un multiplexor de 8 entrades sense necessitar portes addicionals a la sortida? El multiplexor com a selector de dades Un multiplexor (habitualment abreujat com MUX) és un circuit combinacional MSI dissenyat per actuar com a selector de vies de dades. La seva funció consisteix a dirigir una d'entre múltiples línies d'entrada cap a una única línia de sortida compartida, depenent exclusivament del valor present a les seves entrades de control.

n 2n Apunts d'Estructura de Computadors: Lògica Digital 40 De manera formal, un multiplexor disposa de línies d'entrada de dades, exactament línies de selecció i una única sortida . La combinació binària aplicada a les entrades de control determina de forma unívoca quina entrada es transfereix directament cap a la sortida. Esquema lògic intern d'un multiplexor de 4 entrades i 2 selectors. Considerem l'estructura clàssica d'un multiplexor de 4 entrades ( ) i dues línies de control ( ).

La taula de funcionament descriu la transferència de senyal segons el codi de selecció: Línia Línia Sortida 0 0 0 1 1 0 1 1 Internament, el circuit s'implementa mitjançant portes AND associades a una porta OR final (vegeu «Circuits combinacionals — Estructures a dos nivells, anàlisi i síntesi»). Cada porta AND avalua el minterm de selecció corresponent juntament amb l'entrada de dades assignada. L'equació lògica característica resultant s'expressa com a suma de productes: COMPROVA-HO 59 Quantes línies de selecció necessita un multiplexor que ha de triar entre 16 canals d'entrada?

Mòduls de multiplexors múltiples En moltes arquitectures de computadors és necessari commutar paraules o vectors de bits complets en paral·lel. Un multiplexor múltiple integra diversos multiplexors individuals dins d'un mateix encapsulat físic.

2n n S E , E , E , E 0 1 2 3 C , C 1 0 C 1 C 0 S E 0 E 1 E 2 E 3 S = E + 0C 1 ˉ C 0 ˉ E C + 1C 1 ˉ 0 E C + 2 1C 0 ˉ E C C 3 1 0 Apunts d'Estructura de Computadors: Lògica Digital 41 La característica fonamental d'aquests blocs és que cada submòdul té les seves pròpies entrades i la seva pròpia sortida independent, però comparteixen les línies de selecció i la línia d'habilitació (enable, vegeu «Blocs MSI combinacionals — Descodificadors, codificadors i comparadors»). Diagrama de blocs d'un múltiplex quàdruple amb línia de selecció compartida. Un cas típic és el quàdruple multiplexor de dues entrades per canal.

Aquest bloc conté quatre selectors 2:1 que comparteixen la mateixa línia de control : Si : s'encaminen simultàniament les entrades del canal 0 ( , , , ). Si : es transfereixen les entrades del canal 1 ( , , , ). Aquesta agrupació permet commutar entre dos busos de 4 bits mitjançant un únic senyal de control.…