Aritmètica binària

Les possibles combinacions de la suma binària són:

• 0 + 0 = 0
• 0 + 1 = 1
• 1 + 0 = 1
• 1 + 1 = 0, i en porto una

Les tres primeres combinacions són evidents. Però la suma d’1+1, que en decimal sabem que és 2, s’ha d’escriure en binari amb dos dígits (10). Per tant, la suma d’1+1 és 0 i s’arrossega una unitat que se suma a la següent posició a l’esquerra.

El complement a un i el complement a dos són dues eines matemàtiques que faciliten molt les tasques aritmètiques en el sistema binari, sobretot la realització de restes i el treball amb nombres negatius.

Per exemple, el complement a un del nombre 1101 és el nombre 0010.

Per exemple, per calcular el complement a dos del nombre binari 1001 primer calculem el seu complement a un invertint uns i zeros. Ens dóna el nombre 0110. A aquest complement a un li sumem una unitat i ja tenim el complement a dos: 0110 + 1 = 0111.

Generalment s’assumeix que el C2 és la manera de representar el negatiu d’un número binari.

Per exemple, fem la resta 1011011 - 0101110:

• Primer calculem el complement a un del subtrahend: 0101110 → 1010001.
• A continuació calculem el complement a dos d’aquest: 1010001 + 1 = 1010010.
• Finalment sumem el minuend amb el complement a dos del subtrahend.

En el resultat de la suma ens sobra un bit, ja que arrosseguem un 1 per l’esquerra. Però com que el nombre resultant de la resta no pot ser més gran que el minuend, el bit sobrant s’ignora. Per tant: 1011011 - 0101110 = 0101101.

Una altra manera de fer restes en sistema binari és plantejant-les com en el sistema decimal. Com que el sistema binari només té 2 estats, les quatre possibles restes que tenim són 0 - 0, 1 - 0, 1 - 1 i 0 - 1; tres són evidents:

• 0 - 0 = 0
• 1 - 0 = 1
• 1 - 1 = 0

Però, per la resta 0 – 1 obtindríem un resultat negatiu de - 1. Perquè això no passi, igual que en el sistema decimal, agafem una unitat prestada de la posició següent: 0 – 1 → 10 - 1. Aquesta unitat prestada s’ha de retornar, sumant-la, a la posició següent. Seguint l’exemple anterior, 1011011 - 0101110:

Començant per la dreta, les operacions que cal fer són:

1. 1 - 0 = 1
2. 1 - 1 = 0
3. 0 - 1 = 1 i agafem una unitat prestada al següent.
4. 1 - 1 = 0, però com que havíem agafat una unitat prestada, ara fem 0 - 1 = 1 i agafem una unitat prestada al següent.
5. 1 - 0 = 1, però com que havíem agafat una unitat prestada, ara fem 1 - 1 = 0.
6. 0 - 1 = 1 i agafem una unitat prestada al següent.
7. 1 - 0 = 1, però com que havíem agafat una unitat prestada, ara fem 1 - 1 = 0.

Veiem que el resultat de fer la resta és 0101101, igual que en l’exemple anterior.

Amb el sistema decimal, els nombres negatius es representen senzillament precedint-los amb el signe -. En canvi, en el sistema binari no s’utilitza el signe sinó que es fan servir altres mètodes. El mètode més utilitzat és el del complement a 2 (C2).

En la taula es mostra la representació binària des del -128 fins al +127. Si us hi fixeu, el bit de més pes sempre és zero per als nombres positius i sempre és u per als nombres negatius. Aquest bit de més pes s’anomena bit de signe, perquè ens indica si el nombre és positiu (bit de signe a zero) o negatiu (bit de signe a un). La resta de bits s’anomenen magnitud.

L’àlgebra de Boole es basa en el següent:

• Un conjunt d’elements que únicament poden tenir dos valors possibles i que anomenarem 0 i 1.
• Tres operacions que anomenarem suma lògica, producte lògic i negació.

Un element qualsevol de l’àlgebra de Boole es representa amb una lletra que s’anomena variable booleana o, alternativament, variable binària. Així, doncs, cada variable binària té associat un valor 1 o un valor 0.

Les tres operacions bàsiques de l’àlgebra de Boole són les següents:

• Suma lògica. És representada pel signe + i requereix dos operands com a mínim. Per exemple, en un circuit elèctric, si tenim dos interruptors en paral·lel per encendre una bombeta (a o b), polsant-ne qualsevol dels dos la bombeta s’encendria (a + b). Aquesta operació queda definida en la taula.

• Producte lògic. És representat pel signe · i requereix dos operands com a mínim. Per exemple, en un circuit elèctric, si tenim dos interruptors en sèrie per encendre una bombeta (a i b), la bombeta només s’encendria quan polsem els dos (a · b). Aquesta operació queda definida en la taula.

• Negació. És una operació que només requereix un operand. Si l’operand és la variable a, una línia horitzontal sobre aquesta variable indica que està negada o complementada (). Aquesta operació queda definida en la taula.

Taula Negació lògica

a
0	1
1	0

L’àlgebra de Boole és el suport matemàtic per al disseny i l’anàlisi dels sistemes digitals i, com tota àlgebra, disposa d’una sèrie de propietats, postulats i teoremes (taula). Segurament les més importants són el teorema d’absorció, molt útil en simplificacions, i el teorema de DeMorgan, el qual ens indica com es converteix un producte lògic en una suma lògica i a l’inrevés.

Taula Propietats de l’àlgebra de Boole

Propietat	Descripció	Formulació
Idempotència	La repetitivitat d’una operació produeix un únic resultat
Involució	Dues negacions directes sobre el mateix element s’anul·len
Commutativitat	L’ordre de la suma o del producte és indiferent
Associativitat	Les sumes (o els productes) es poden resoldre en qualsevol ordre
Distributivitat	LA suma és distributiva envers el producte
Llei d’absorció	Eliminació de termes irrellevants
Teorema de DeMorgan	Descomposició de productes en sumes o de sumes en productes

En la primera expressió d’absorció veiem que el resultat només depèn de la variable A, que només té dos estats possibles: 0 i 1. En el cas que fos 0 tindríem 0 + 0 · b i qualsevol nombre per 0 és 0. Si fos 1, tindríem 1 + 1 · b; com que és una suma, el resultat sempre seria 1, per tant, a + a · b = a.

En la segona expressió, com que la variable a està multiplicant tot el parèntesi, el valor de sortida sempre serà a. Si a fos 0, tindríem un valor multiplicat per 0, que és igual a 0, i si a fos 1, tindríem 1 multiplicat per (1 + b) que és igual a 1. Per tant, a · (a + b) = a.

Anomenem funció lògica una variable binària que pren el valor d’una expressió algebraica formada per altres variables binàries relacionades de la manera que sigui mitjançant les operacions suma lògica, producte lògic i negació.

Per exemple, les següents expressions són funcions lògiques definides per una expressió algebraica:

Per exemple, la funció següent és una suma de productes:

Per exemple, la funció següent és un producte de sumes:

Una taula de veritat és una manera de representar una funció lògica, en la qual es mostra el valor que pren la funció per a cadascuna de les combinacions de les variables d’entrada de la funció.

Per construir la taula de veritat d’una funció lògica s’han de seguir els següents passos:

1. Dibuixar una taula amb:
   • tantes columnes com variables tingui la funció, més una columna addicional
   • tantes files com el nombre de possibles combinacions de les variables d’entrada, més una fila addicional
2. En la fila superior es posen els noms de les variables (en les columnes de l’esquerra) i de la funció (en la columna de la dreta).
3. S’omple la resta de files amb les diferents combinacions de valors de les variables d’entrada, en ordre creixent, com si comptéssim en binari natural.
4. S’omple la columna de la dreta amb el valor que pren la funció per a cada combinació de valors d’entrada.

Taula Taula de veritat de la funció

a	b	c
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

Una funció booleana es pot definir indistintament amb una expressió algebraica o amb una taula de veritat. Coneixem el mètode per trobar la taula de veritat d’una funció expressada algebraicament.

El que encara no hem vist és com es fa el pas invers: partir de la taula de veritat d’una funció i trobar una expressió algebraica que descrigui la mateixa funció. Això és el que estudiarem en l’apartat “Formes canòniques d’una funció”.

Abans, però, ens podríem plantejar si hi ha més d’una expressió algebraica que verifiqui una taula de veritat donada. I, efectivament, és això.

La manera més fàcil de descobrir si dues funcions són equivalents és trobar la taula de veritat a partir de cadascuna de les expressions algebraiques i comprovar si donen el mateix resultat.

Com a exemple, veurem si són equivalents les funcions següents:

Primer omplim la taula de veritat de : el resultat el podeu veure a la taula.

Taula Taula de veritat de

a	b
0	0	0
0	1	0
1	0	1
1	1	1

A continuació omplim la taula de veritat de : el resultat el podeu veure a la taula.

Taula Taula de veritat de

a	b
0	0	0
0	1	0
1	0	1
1	1	1

Observant les dues taules, veiem que els resultats de les dues funcions són idèntics. Per tant, i són equivalents.

A continuació veurem com podem trobar una expressió algebraica d’una funció a partir de la seva taula de veritat. Hi ha dues maneres de fer-ho i es coneixen com a formes canòniques.

La primera forma canònica es basa a expressar la funció com una suma de productes que deduirem de la taula de veritat mitjançant el procediment que utilitzem en l’exemple següent:

1. A la taula de veritat, ens fixarem en les combinacions de valors de les variables d’entrada que fan que la funció valgui 1.
2. Per cadascuna d’aquestes combinacions hem de trobar un terme producte, anomenat minterm, amb les següents característiques:
   • Està format per totes les variables de la funció, negades o no.
   • Aquestes variables estan multiplicades.
3. Per saber si la variable ha d’estar negada o no a cada minterm, us heu de fixar en la combinació de valors:
   • Si el valor d’aquesta variable és 0, aquesta variable haurà d’anar negada en el terme producte.
   • Si el valor d’aquesta variable és 1, aquesta variable haurà d’anar directa (no negada) en el terme producte.
4. Finalment, la primera forma canònica s’obté sumant tots els minterms.

La segona forma canònica es basa a expressar la funció com un producte de sumes que deduirem de la taula de veritat mitjançant el següent procediment:

1. A la taula de veritat, ens fixarem en les combinacions de valors de les variables d’entrada que fan que la funció valgui 0.
2. Per cadascuna d’aquestes combinacions hem de trobar un terme producte, anomenat maxterm, amb les següents característiques:
   • Està format per totes les variables de la funció, negades o no.
   • Aquestes variables estan sumades.
3. Per saber si la variable ha d’estar negada o no a cada maxterm, us heu de fixar en la combinació de valors:
   • Si el valor d’aquesta variable és 0, aquesta variable haurà d’anar directa (no negada) en el terme suma.
   • Si el valor d’aquesta variable és 1, aquesta variable haurà d’anar negada en el terme suma.
4. Finalment, la segona forma canònica s’obté multiplicant tots els maxterms.

Fins i tot els sistemes digitals més complexos estan formats per blocs més petits encarregats de fer operacions senzilles amb senyals binaris. Aquests blocs fonamentals són el que coneixem com a portes lògiques.

Cada porta lògica fa una funció determinada; de totes les possibles funcions existents, les portes lògiques bàsiques són aquelles que es constitueixen com a bons elements de disseny de propòsit general. Les portes lògiques bàsiques són la porta AND, la porta OR , la porta NOT, la porta NAND i la porta NOR.

La porta AND fa la funció de producte lògic i rep el nom de la paraula anglesa and, que significa i en català.

La figura mostra el símbols d’una porta AND de dues entrades, però els mateixos símbols serveixen per a un nombre d’entrades més gran, només cal afegir les connexions d’entrada necessàries al símbol.

Com podeu veure en la figura, la làmpada X1 tan sols s’encén (és a dir, la sortida es posa a estat 1 lògic) quan els interruptors A i B estan tancats (és a dir, quan les dues entrades estan a 1 lògic).

La porta OR realitza la funció suma lògica i rep el nom de la paraula anglesa or, que significa o en català.

La figura mostra el símbols d’una porta OR de dues entrades, la seva expressió algebraica i la seva taula de veritat.

Com podeu veure en la figura, la làmpada X2 s’encén (és a dir, la sortida es posa a estat 1 lògic) quan, com a mínim, un dels dos interruptors A i B està tancat.

Aquesta porta, també coneguda com a inversor, només té una entrada i realitza la funció de negació, de manera que la sortida és 1 si l’entrada és 0 i la sortida és 0 si l’entrada és 1.

La figura mostra els símbols d’una porta NOT, la seva expressió algebraica i la seva taula de veritat.

El nom d’aquesta porta prové de la unió de les paraules angleses notiand i, com el seu nom indica, és una porta AND amb la sortida invertida.

La figura mostra els símbols d’una porta NAND, la seva expressió algebraica i la seva taula de veritat.

La sortida d’una porta NOR és la invertida d’una porta OR. El seu nom prové de la unió de les paraules angleses noti or.

La figura mostra els símbols d’una porta NOR, la seva expressió algebraica i la seva taula de veritat.

També anomenada porta OR-exclusiva. La seva sortida és 1 només quan les dues variables d’entrada tenen valors diferents.

L’operador XOR en les expressions algebraiques és el símbol , un signe de suma encerclat.

En el cas de tenir més de dues entrades, podeu recordar com funciona una porta XOR si recordeu el següent:

La figura 14 mostra els símbols d’una porta XOR, la seva expressió algebraica i la seva taula de veritat.

Per a qualsevol aplicació que ens plantegem, és evident que l’obtenció de la funció més curta possible té grans avantatges:

• Circuits més petits i ràpids
• Preu més reduït

Una de les eines més senzilles per obtenir una funció simplificada a partir d’una taula de veritat és l’anomenada mapa de Karnaugh, que consisteix en un mètode gràfic.

Partint de la taula de veritat d’una funció digital d’entre dues i quatre variables, el mètode consisteix en reescriure aquella taula de veritat seguint unes indicacions concretes. Això ens donarà el punt de partida per realitzar la simplificació.

De la mateixa manera que una taula de veritat té un nombre 2ⁿ de resultats possibles per a n variables, el mapa de Karnaugh resultant tindrá el mateix nombre de caselles.

A l’interior de les caselles haurem de posar el valor de la sortida corresponent a cadascuna de les combinacions dels valors de les entrades. Aquests valors poden ser:

• 0: zero lògic.
• 1: u lògic.
• X: indiferent, podrem prendre’l com a 0 o com a 1 segons ens interessi.

Aquesta manera de representar la taula de veritat ens servirà per detectar aquells termes de la funció canònica que estan generats per combinacions de les entrades entre les quals només canvia un dígit. Dit així, sembla complicat, però com és un mètode gràfic, no ho és pas.

Construcció d'un mapa de Karnaugh per a una funció de 2 variables

Imaginem una taula de veritat d’una funció de 2 variables a, b, i una sortida x:

Taula Taula de veritat de 2 variables

a	b	x
0	0	0
0	1	1
1	0	1
1	1	X

En aquest cas, el mapa serà una taula amb els valors possibles d’a i de b a cadascun dels eixos:

Noteu que hi hem copiat els valors corresponents de la sortida (només els 1) per a cadascuna de les combinacions.

Construcció d'un mapa de Karnaugh per a una funció de 3 variables

Imaginem una taula de veritat d’una funció de 3 variables a, b, c, i una sortida x:

Taula Taula de veritat de 3 variables

a	b	c	x
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	X
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	1

En aquest cas, el mapa serà una taula amb els valors possibles d’a, de b i de c a cadascun dels eixos. En un dels eixos hi hauran d’aparèixer dues d’elles, i el més important és que passarem d’una casella a l’adjacent’ només canviant el valor d’una sola variable.

Vegeu com, en la figura següent, hem posat a l’eix horitzontal la combinació ab, amb els valors possibles exactament en el següent ordre:

1. 00
2. 01
3. 11
4. 10

No segueixen l’ordre natural que seria 0, 1, 2, 3 (00-01-10-11), sinó que estan ordenats de forma que d’un terme al següent només canvia un dígit, i a més, també canvia un sol dígit entre el darrer i el primer.

Noteu que hi hem copiat els valors corresponents de la sortida (només els 1) per a cadascuna de les combinacions.

Construcció d'un mapa de Karnaugh per a una funció de 4 variables

Imaginem una taula de veritat d’una funció de 4 variables a, b, c, d, i una sortida x:

Taula Taula de veritat de 4 variables

a	b	c	d	x
0	0	0	0	0
0	0	0	1	1
0	0	1	0	1
0	0	1	1	X
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	1
1	0	0	0	1
1	0	0	1	X
1	0	1	0	1
1	0	1	1	0
1	1	0	0	1
1	1	0	1	0
1	1	1	0	1
1	1	1	1	0

En aquest cas, el mapa serà una taula amb els valors possibles d’a, de b, de c i de d a cadascun dels eixos. Als dos eixos hi hauran d’aparèixer dues d’elles, i el més important és que passarem d’una casella a l’adjacent’ només canviant el valor d’una sola variable.

Vegeu com, en la figura següent, hem posat a l’eix horitzontal la combinació ab i a l’eix vertical cd, igualment amb els valors possibles exactament en el següent ordre:

1. 00
2. 01
3. 11
4. 10

No segueixen l’ordre natural que seria 0, 1, 2, 3 (00-01-10-11), sinó que estan ordenats de forma que d’un terme al següent només canvia un dígit, i a més, també canvia un sol dígit entre el darrer i el primer.

Noteu que hi hem posat els valors corresponents de la sortida (només els 1) per a cadascuna de les combinacions.

Per fer la simplificació de la funció digital, el primer que hem de fer és triar amb quin resultat (0 o 1) treballarem. en el nostre cas, per fer-ho més fàcil, sempre treballarem amb els uns (1) de la funció.

Prenent com a punt de partida el mapa emplenat amb els uns (1) i els indiferents (X), la simplificació consisteix en fer agrupacions tot seguint les set regles que descrivim tot seguit.

Regla 1

Un element es pot agrupar amb d’altres elements amb els quals estigui en contacte directe als costats, a dalt o a sota, en horitzontal o en vertical. Mai en diagonal.

Així, vegeu a la figura possibles agrupacions correctes i incorrectes.

Regla 2

Al mapa de Karnaugh els extrems es toquen, tant per les bandes laterals com per dalt i per baix.

Així, les agrupacions mostrades en la figura seran totes correctes.

Regla 3

Els grups poden tenir un nombre d’elements que sigui potència de 2. Així, els grups podran tenir 1, 2, 4 o 8 elements (mai 3 o 6, que són els errors típics).

D’aquesta manera, vegeu a la figura possibles agrupacions correctes i incorrectes.

Regla 4

Els grups han de tenir una forma compacta: poden ser quadrats o rectangulars. Mai podran tenir forma de L o similar.

D’aquesta manera, vegeu a la figura possibles agrupacions correctes i incorrectes.

Regla 5

Els grups es poden superposar entre ells. Això vol dir que un 1 pot pertànyer perfectament a més d’un grup.

Les agrupacions de la figura són completament correctes.

Regla 6

Els grups han de ser tan extensos com sigui possible. No importa si per a això s’han de superposar. Millor dos grups de 4 que se superposin que no pas un de 4 amb un de 2 al costat.

Així, davant de les dues propostes de solució mostrades en la figura, hi ha una que és òptima i l’altra, essent correcta (el circuit funcionaria), no és la millor solució possible.

Regla 7

Tots els uns del mapa han de pertànyer a algun grup. No pot quedar cap 1 sense agrupar. Les X sí que poden intervenir en la formació dels grups o no, segons les nostres necessitats.

Si es miren les files i columnes a què afecta un grup del mapa es pot veure si les variables (a, b, c, d en el nostre cas) tenen un valor fix o si canvien de valor.

La forma de construir un terme a partir d’un grup és la següent:

1. Mireu en tota l’extensió del grup, variable per variable, quines variables tenen valor fix i quines canvien de valor.
2. El contingut del terme es farà en funció de:
   • Variables que canvien de valor: no apareixen al terme
   • Variables que valen 0 fix: apareixen negades (ex: ) al terme
   • Variables que valen 1 fix: apareixen directes (ex: ) al terme

Exemple de generació de termes de grups d'un element

• Grup de l’esquerra (totes fixes): a = 0, b = 0, c = 1, d = 1
• Grup de la dreta (totes fixes): a = 1, b = 0, c = 0, d = 1

Exemple de generació de termes de grups de dos elements

• Grup horitzontal (b canvia de valor): a = 0, b = 0/1, c = 1, d = 1
• Grup vertical (c canvia de valor): a = 0, b = 1, c = 0/1, d = 1

Exemple de generació de termes de grups de quatre elements

• Grup de l’esquerra (a i d canvien de valor): a = 0/1, b = 1, c = 0/1, d = 1
• Grup de la dreta (b i c canvien de valor): a = 1, b = 1/0, c = 0/1, d = 1

Exemple de generació de termes de grups de vuit elements

• Grup (b, c i d canvien de valor): a = 1, b = 1/0, c = 0/0/1/1 , d = 0/1/1/0

Sigui la taula de veritat (quatre variables a, b, c, d; una sortida f) mostrada a la taula.

Construïm primer el mapa de Karnaugh resultant de la taula de veritat, que serà el mostrat a la figura.

A continuació fem les agrupacions tot seguint les set regles anteriors. El resultat serà el que es mostra a la figura.

Noteu que per tal de crear grups més grans hem aprofitat una de les X i l’altra no ha calgut.

Els termes seran:

• Grup de 2 vertical: a = 0, b = 0, c = 1, d = 1/0
• Grup de 4: a = 0/1, b = 1, c = 0/1, d = 1
• Grup de 2 horitzontal dalt: a = 1, b = 1/0, c = 0, d = 1
• Grup de 2 horitzontal baix: a = 1, b = 1/0, c = 1, d = 0

La funció òptima de sortida serà: