Exercicis: Simplificació amb mapes de Karnaugh

Explica com es construeix un mapa de Karnaugh de dues variables: quantes cel·les té, què representa cada cel·la i per què les columnes i files s'etiqueten seguint el codi Gray ($00$, $01$, $11$, $10$) en lloc de l'ordre binari habitual.

Enuncia les regles per formar grups en un mapa de Karnaugh: quines mides de grup són vàlides, què significa que les cel·les han de ser adjacents (inclosos els marges) i com s'obté el terme simplificat de cada grup.

El mapa de Karnaugh de la figura correspon a una funció de tres variables $f(a, b, c)$. Assenyala les agrupacions que faries (dibuixa-les o descriu-les per les seves cel·les) i obtén la funció mínima resultant.

Construeix el mapa de Karnaugh de dues variables $A$ i $B$ per a la funció $F = A \cdot B$ (funció AND) i respon:

1. a) Quantes cel·les té el mapa?

1. b) En quina cel·la va l'únic $1$? Indica els valors de $A$ i $B$ d'aquesta cel·la.

1. c) Intenta agrupar els uns del mapa en grups d'1, 2 o 4 cel·les adjacents: què comproves? Es pot simplificar l'expressió canònica de $F$?

En un mapa de dues variables hi ha uns a les cel·les $ab = 10$ i $ab = 11$. Descriu l'agrupació i raona quina variable s'elimina (la que canvia dins del grup) i quina queda fixa, escrivint el terme simplificat.

Explica per què un grup de dues cel·les elimina una variable, un de quatre cel·les n'elimina dues i un de vuit n'elimina tres. Quina mida de grup eliminaria totes les variables d'una funció de tres variables i quina funció en resulta llavors?

Un grup rectangular d'un mapa cobreix les cel·les on $a = 1$, amb $b$ i $c$ prenent tots els valors. Escriu el terme que representa aquest grup i justifica la regla: «el terme conté només les variables que no canvien dins del grup, negades si valen $0$ i sense negar si valen $1$».

Trasllada a un mapa de Karnaugh de tres variables (columnes $ab$: $00$, $01$, $11$, $10$; files $c$: $0$, $1$) els minterms $0$, $2$, $5$ i $7$ d'una funció. Dibuixa el mapa complet amb els seus uns i zeros a cada cel·la.

Pots fer-ho en paper i enviar una foto amb la teva resposta.

La funció $f(a,b,c)$ val $1$ per a les combinacions $1$, $3$, $5$ i $7$ (en decimal, amb $a$ com a bit més significatiu). Trasllada la taula de veritat a un mapa de Karnaugh de tres variables, forma l'agrupació més gran possible i obtén la funció mínima. Comprova el resultat substituint dues combinacions.

Simplifica amb un mapa de Karnaugh de tres variables la funció $f = \overline{a} \cdot \overline{b} \cdot c + \overline{a} \cdot b \cdot c + a \cdot \overline{b} \cdot c + a \cdot b \cdot c$, indicant quina variable s'elimina en el grup format. Comenta quina propietat de Boole confirma el resultat ($x \cdot c + \overline{x} \cdot c = c$).

En un mapa de quatre variables, explica per què la cel·la de la cantonada superior esquerra és adjacent a la de la cantonada superior dreta, i forma amb un exemple l'agrupació de quatre cantonades: quin terme simplificat produeix un grup amb les quatre cantonades d'un mapa de quatre variables?

Simplifica amb un mapa de tres variables la funció que val $1$ en els minterms $1$, $2$, $3$ i $6$ (amb $a$ com a bit més significatiu): dibuixa el mapa, marca les dues agrupacions necessàries i escriu la funció mínima com a suma de dos productes.

Pots fer-ho en paper i enviar una foto amb la teva resposta.

En un mapa de tres variables els uns ocupen les cel·les $0$, $1$, $4$ i $5$. Mostra que hi ha una única agrupació de quatre cel·les, explica per què és vàlida encara que les cel·les $0$ i $4$ no es toquin físicament en el mapa (adjacència pels marges) i obtén la funció mínima.

La figura mostra un mapa de Karnaugh de quatre variables $f(a,b,c,d)$ amb set uns. Assenyala l'agrupació més gran possible, escriu la funció mínima i comprova el resultat amb les combinacions $0000$ i $0101$.

La funció de tres variables $f$ val $1$ en els minterms $1$, $3$, $4$, $5$ i $7$. Dibuixa el mapa, busca les agrupacions (una de quatre i una altra de dues, amb encavalcament) i obtén la funció mínima. Explica per què un u pot pertànyer a dos grups alhora.

Pots fer-ho en paper i enviar una foto amb la teva resposta.

Dos companys obtenen per a la mateixa taula de veritat les funcions $f = \overline{a} \cdot c + a \cdot b$ i $f = \overline{a} \cdot c + a \cdot b + b \cdot c$. Comprova amb un mapa de Karnaugh si són equivalents i explica què és un terme redundant (o de consens) en aquest context.

En un bus de comunicació de 4 bits ($A, B, C, D$, amb $A$ com a MSB), es necessita un circuit combinacional que discrimini certes paraules de dades.

1. a) Demostra formalment mitjançant el mapa de Karnaugh que la funció $f_1 = \sum m(0, 2, 4, 6, 8, 10, 12, 14)$ es redueix a un únic literal. Justifica el resultat a partir de la propietat d'adjacència de Karnaugh i del pes del bit menys significatiu en binari natural.
2. b) Un tècnic confon «nombre enter parell» amb «paritat parella» i proposa utilitzar aquesta mateixa funció $f_1$ per verificar si una paraula de 4 bits té paritat parella (nombre parell d'uns, considerant el zero com a parell: mintermes $0, 3, 5, 6, 9, 10, 12, 15$). Avalua críticament la seva proposta: dibuixa el mapa de Karnaugh de la paritat parella, explica per què el seu patró geomètric en escaquer impedeix qualsevol agrupació simplificadora i calcula el percentatge d'error que cometria el circuit del tècnic sobre el total de les 16 combinacions possibles.

Es vol dissenyar un circuit combinacional detector de nombres primers per a un bus de 4 bits ($A, B, C, D$, amb $A$ com a MSB). En el rang $[0, 15]$, es consideren primers els nombres $\{2, 3, 5, 7, 11, 13\}$ (el $0$ i l'$1$ no són primers).

1. a) Obtén la funció lògica simplificada mínima en forma de suma de productes (SOP) a partir del seu mapa de Karnaugh, justificant els llaços seleccionats.
2. b) Obtén l'expressió mínima en producte de sumes (POS) agrupant els zeros del mapa. Compara rigorosament ambdues implementacions (SOP i POS) en termes de nombre de portes lògiques i nombre total d'entrades (literals). Quina triaries per minimitzar l'àrea de silici?
3. c) Suposa que el circuit SOP dissenyat pateix una avaria física: la línia d'entrada $B$ queda permanentment curtcircuitada a nivell alt (stuck-at-1). Prediu quins nombres primers deixaran de ser detectats i quins nombres no primers activaran erròniament la sortida.

En el sistema de control d'una tremuja industrial es monitoritzen 3 sensors digitals de nivell ($A, B, C$, amb $A$ com a MSB). Per disseny mecànic de la instal·lació, hi ha estats prohibits o indiferències ($X$). La comporta de buidatge s'ha d'activar ($S = 1$) únicament en la combinació $m_5$ ($101_2$), i romandre tancada ($S = 0$) en les combinacions $\{0, 1, 2, 3\}$. Les combinacions $\{4, 6, 7\}$ corresponen als estats mecànicament impossibles.

1. a) Dedueix mitjançant el mapa de Karnaugh la funció mínima $S_{\text{amb } X}$ aprofitant les indiferències, i compara-la amb la funció $S_{\text{sense } X}$ que resultaria de fixar preventivament totes les indiferències a '0'. Quantifica l'estalvi de literals i portes lògiques.
2. b) Durant una operació de manteniment, un sensor falla i el sistema assoleix transitòriament la combinació imprevista $m_6$ ($110_2$). Prediu raonadament la resposta de la comporta en cadascun dels dos dissenys ($S_{\text{amb } X}$ i $S_{\text{sense } X}$). Justifica quina de les dues opcions ofereix més seguretat davant d'abocaments incontrolats de material perillós (criteri fail-safe).

Un mòdul descodificador converteix un codi BCD ($A, B, C, D$, amb $A$ com a MSB) per excitar el segment superior ($a$) d'un display de 7 segments. El segment s'ha d'encendre ($a = 1$) per als dígits $0, 2, 3, 5, 6, 7, 8$ i $9$. Les combinacions binàries del 10 al 15 no pertanyen a la codificació BCD i es consideren condicions indiferents ($X$).

1. a) Mitjançant el mapa de Karnaugh, obtén la funció mínima simplificada en suma de productes (SOP). Indica explícitament quin valor lògic ($0$ o $1$) ha adoptat en el teu disseny final cadascuna de les sis combinacions indiferents ($m_{10}$ a $m_{15}$).
2. b) Si per una fallada de sincronisme a la línia de dades entra al descodificador el codi binari no vàlid $1101_2$ ($13$ decimal), prediu si el segment $a$ s'il·luminarà o romandrà apagat segons la funció que has dissenyat.
3. c) En una aplicació crítica s'exigeix que, davant de qualsevol codi no vàlid ($10$ a $15$), tots els segments romanguin obligatòriament apagats per advertir l'usuari d'un error de lectura. Dissenya la nova funció del segment $a$ sota aquest requisit estricte i calcula el sobrecost en nombre de portes i literals respecte al disseny amb indiferències.

Un mòdul receptor de telemetria processa trames de 4 bits ($A, B, C, D$, amb $A$ com a MSB). La sortida de validació $f$ s'ha d'activar ($1$) per als minitermes canònics $\{1, 3, 7, 11, 15\}$. Les combinacions $\{5, 9, 13\}$ s'han catalogat al protocol com a «indiferències teòriques» ($X$), ja que corresponen a ordres de manteniment que no s'haurien de presentar en mode d'operació ordinari.

1. a) Obtén mitjançant Karnaugh la funció mínima $f_1$ aprofitant les indiferències i la funció mínima $f_0$ forçant $X = 0$. Compara totes dues en cost d'implementació (nombre de portes i literals).
2. b) L'equip de ciberseguretat adverteix que un atacant podria injectar paquets utilitzant deliberadament les trames de manteniment $\{5, 9, 13\}$ per activar el sistema sense autorització. Analitza què passarà amb cadascuna d'aquestes tres trames sota la implementació $f_1$ i sota $f_0$.
3. c) Proposa una modificació en la síntesi de la funció que permeti mantenir un cost de portes reduït però garanteixi que cap de les trames reservades $\{5, 9, 13\}$ activi la sortida $f$, deduint algebraicament la funció resultant.

En tecnologia de fabricació CMOS integrada, la síntesi en Producte de Sumes (POS) mitjançant portes NOR pot requerir menys transistors o menor temps de propagació que la Suma de Productes (SOP) tradicional.

Considera una funció combinacional de 3 variables $f(A, B, C)$ definida pels seus maxitermes nuls $M(0, 1, 4, 5)$ (és a dir, la sortida val $0$ únicament en aquestes combinacions).

1. a) Demostra formalment l'obtenció analítica de la forma POS simplificada agrupant zeros al mapa de Karnaugh i aplicant l'àlgebra de Boole / lleis de De Morgan.
2. b) Obtén la forma mínima SOP agrupant els uns. Compara ambdues arquitectures (POS vs. SOP) calculant el nombre exacte de transistors CMOS requerits per a cadascuna, sabent que un inversor NOT requereix 2 transistors i una porta bàsica (NAND o NOR) de $n$ entrades necessita $2n$ transistors.
3. c) Aplica la mateixa anàlisi comparativa (POS enfront de SOP) a una funció de 4 variables $g(A, B, C, D)$ els zeros de la qual se situen exclusivament a les quatre cantonades del mapa de Karnaugh: $M(0, 2, 8, 10)$. Determina si en aquest cas alguna de les dues formes presenta avantatge en nombre de portes o transistors i justifica el resultat per simetria.

A la unitat de control d'un autòmat industrial s'han de generar dues sortides lògiques a partir de 3 variables d'entrada ($A, B, C$, amb $A$ com a MSB).

La sortida principal respon a la funció canònica $F_1(A, B, C) = \sum m(0, 1, 2, 5, 6, 7)$.

1. a) Mitjançant el mapa de Karnaugh, demostra que no existeix cap implicant primer essencial i obtén les dues cobertures mínimes alternatives possibles per a $F_1$, comprovant que ambdues posseeixen un cost idèntic en termes i literals.
2. b) El segon senyal requerit és $F_2(A, B, C) = \sum m(6, 7)$. Si ambdues funcions s'han d'implementar conjuntament en el mateix circuit compartint portes lògiques intermèdies per minimitzar l'àrea total, justifica rigorosament quina de les dues cobertures de $F_1$ obtingudes a l'apartat (a) s'ha de seleccionar.
3. c) Dibuixa l'esquema del circuit combinacional òptim resultant que genera ambdues sortides ($F_1$ i $F_2$) compartint portes, i indica quantes portes i entrades totals s'estalvien respecte a implementar ambdues funcions de manera desacoblada.

Un equip de desenvolupament dissenya un verificador d'integritat per a un bus de 4 bits ($A, B, C, D$, amb $A$ com a MSB) que transporta codis BCD natural. La sortida $V$ ha de valer $1$ si la combinació d'entrada representa un dígit BCD vàlid ($0$ a $9$) i $0$ si representa un codi fora de rang ($10$ a $15$).

1. a) Un projectista novell sosté: «Com que en un sistema BCD els valors del 10 al 15 mai no es produiran, podem marcar-los com a indiferències ($X$) al mapa de Karnaugh perquè el circuit sigui al màxim de simple possible». Rebat tècnicament aquesta afirmació: obtén quina funció resultaria d'aplicar la seva idea i explica la paradoxa que invalidaria completament el propòsit del circuit.
2. b) Dissenya el circuit simplificat òptim sense indiferències mitjançant el mapa de Karnaugh, tant en Suma de Productes (SOP) com en Producte de Sumes (POS). Justifica quina de les dues formes canòniques mínimes és preferible pel que fa a cost de portes.
3. c) Implementa la funció triada utilitzant exclusivament portes universals NAND de no més de 2 entrades. Descriu les connexions del circuit i determina el nombre total de portes NAND requerides.