Introducció als Computadors FIB: apunts del 1r parcial

Representació de nombres naturals

Sistemes de numeració posicional i rang de representació

En els computadors digitals, la informació numèrica es representa mitjançant sistemes de numeració direccionals o posicionals. En un sistema de base $b$, el valor quantitatiu d'un nombre natural ve determinat pel valor propi de cada dígit i pel pes associat a la seva posició. Si es disposa d'un nombre fix de $n$ dígits, el conjunt de valors que es poden codificar és finit i estricte.

En el cas concret del sistema binari ($b = 2$), una paraula de $n$ bits permet representar exactament $2^n$ combinacions diferents, que van des de 0 fins a $2^n - 1$. Si un resultat supera aquest sostre màxim, es produeix un desbordament de capacitat (situació que s'estudia en el càlcul de l'arrossegament a «Blocs aritmètics combinacionals per a naturals»).

Extensió de rang en naturals

Quan cal transferir un valor numèric natural des d'un format de $n$ bits a un format més ampli de $m$ bits (on $m > n$), el valor numèric ha de romandre inalterat. En nombres sense signe, aquesta operació s'anomena extensió de rang per zeros (o zero extension).

Avaluació polinòmica: conversió a base decimal

Per obtenir el valor decimal d'un nombre expressat en una base qualsevol $b$, s'aplica el teorema fonamental de la numeració, que consisteix a sumar cadascun dels dígits multiplicat per la base elevada a la potència de la seva posició (començant per la posició 0 a l'extrem dret):

Vegem dos casos concrets d'aplicació:

• De binari a decimal ($b = 2$): Per a $X = 1001001_2$:
  $$X_u = 1 \cdot 2^6 + 0 \cdot 2^5 + 0 \cdot 2^4 + 1 \cdot 2^3 + 0 \cdot 2^2 + 0 \cdot 2^1 + 1 \cdot 2^0 = 64 + 8 + 1 = 73$$
• De base 5 a decimal ($b = 5$): Per a $X = 134_5$:
  $$X_u = 1 \cdot 5^2 + 3 \cdot 5^1 + 4 \cdot 5^0 = 25 + 15 + 4 = 44$$

Conversió de decimal a binari i hexadecimal (divisions successives)

Per convertir un nombre natural en base decimal cap a una altra base d'arribada $b$, s'utilitza l'algorisme de divisions successives per la base objectiu:

1. Es divideix el nombre decimal entre la base $b$ mitjançant divisió entera, obtenint un quocient i un residu.
2. El residu obtingut constitueix el dígit de la posició actual, començant pel dígit de menys pes o dret ($b^0$).
3. Es pren el quocient i es torna a dividir entre la base $b$, generant el residu de la posició següent ($b^1$, $b^2$, etc.).
4. El procés es repeteix successivament fins que el quocient esdevé 0. Els dígits del resultat es llegeixen en ordre invers al que s'han obtingut: el primer residu és el dígit de menys pes (LSD), i l'últim quocient/residu és el de més pes (MSD).

En la figura anterior s'observa la conversió del nombre decimal 426 a binari: dividint successivament per 2 s'obtenen els residus ordenats de dreta a esquerra, resultant en $426_{10} = 110101010_2$.

De la mateixa manera, per passar de decimal a hexadecimal ($b = 16$), es divideix successivament per 16. En l'exemple de la imatge superior amb el nombre $637_{10}$:

• $637 / 16 = 39$ amb residu 13 (que correspon a la lletra D en hexadecimal, pes $16^0$).
• $39 / 16 = 2$ amb residu 7 (pes $16^1$).
• $2 / 16 = 0$ amb residu 2 (pes $16^2$).

Recollint els dígits de l'últim al primer, s'obté $637_{10} = 27\text{D}_{16}$.

Correspondència directa binari-hexadecimal

Atès que $16 = 2^4$, cada dígit hexadecimal equival exactament a un grup de 4 bits binaris (anomenat nibble). Aquesta propietat permet fer conversions instantànies sense haver de passar per la base decimal:

Idees clau

• El rang de representació d'un natural amb n dígits en base b és estrictament de 0 a $b^n$ - 1.
• L'extensió de rang en naturals es realitza sempre inserint zeros a les posicions superiors de l'esquerra.
• La conversió de decimal a qualsevol base s'obté mitjançant divisions enteres successives, llegint els residus de baix a dalt.
• Com que 16 és igual a $2^4$, cada dígit hexadecimal es tradueix directament en un quartet de 4 bits començant per la dreta.

Posa a prova el que has après

1. Quin és el valor màxim representable amb 8 bits per a un nombre natural? — 255
2. En convertir un decimal a binari per divisions successives, quin bit representa el primer residu obtingut? — El bit de menys pes
3. A quin valor hexadecimal correspon el nombre binari 10111100_2? — BC
4. Com s'estén la longitud de bits d'un nombre natural per evitar canviar el seu valor? — Afegint zeros a l'esquerra

Circuits lògics combinacionals — Fonaments i anàlisi

Fonaments dels circuits lògics combinacionals

Un circuit lògic combinacional (CLC) és un sistema digital en què el valor de les sortides depèn exclusivament de la combinació de valors presents a les entrades en aquell mateix instant. A diferència dels circuits lògics seqüencials (que s'estudien a «Circuits lògics seqüencials — Biestables, registres i funcionament síncron»), un CLC no disposa d'elements de memòria ni d'estat intern: davant d'un mateix vector d'entrada, la resposta del circuit és sempre idèntica i immediata, llevat del retard físic de commutació dels seus components.

La dimensió d'una taula de veritat ve determinada pel nombre de variables d'entrada i de sortida. Si un circuit disposa de $n$ senyals d'entrada binaris i de $m$ senyals de sortida, la taula conté exactament $2^n \text{ files} \times m \text{ columnes de sortida}$. Cada fila es correspon amb una combinació binària única del vector d'entrada.

Exemple: Multiplexor de dues entrades de dades (MX 2:1)

Un multiplexor de 2 a 1 selecciona una de les dues entrades de dades ($x_0$ o $x_1$) i la transfereix a la sortida $w$ en funció d'un senyal de control o selector $s$. La seva descripció algorísmica és:

$$\text{si } (s = 0) \rightarrow w = x_0; \text{ altrament } (s = 1) \rightarrow w = x_1$$

Atès que té 3 entrades ($s, x_0, x_1$) i 1 sortida ($w$), la seva taula de veritat té $2^3 = 8$ files:

s	x₀	x₁	w
0	0	0	0
0	0	1	0
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	1

Portes lògiques elementals

Les portes lògiques constitueixen les unitats estructurals bàsiques amb què es construeix qualsevol circuit combinacional. Cadascuna implementa una funció booleana elemental:

La porta NOT (inversor) produeix el complement lògic de la seva única entrada ($w = \bar{x}$). Quan l'entrada és 0, la sortida és 1, i viceversa.

El BUFFER manté inalterat el valor lògic de l'entrada ($w = x$). No modifica la funció lògica, però s'utilitza a la pràctica per restaurar o amplificar nivells elèctrics o introduir retards de propagació controlats.

La porta AND efectua el producte lògic ($w = x \wedge y$ o $w = x \thinspace y$). La sortida pren el valor 1 si i només si totes dues entrades valen 1; si qualsevol entrada és 0, la sortida queda anul·lada a 0.

La porta OR calcula la suma lògica ($w = x + y$). La sortida s'activa a 1 sempre que almenys una de les entrades sigui 1, sent 0 únicament quan totes les entrades són 0.

La porta NAND correspon a una porta AND seguida d'una inversió ($w = \bar{xy}$). Produeix un 0 exclusivament quan totes les entrades són 1.

La porta NOR inverteix la funció OR ($w = \bar{x + y}$). La seva sortida és 1 únicament quan totes les entrades es troben a nivell baix (0).

La porta XOR (disjunció exclusiva) actua segons l'operació $w = x \text{ \textasciicircum } y = x \bar{y} + \bar{x}y$. La sortida val 1 si les dues entrades tenen valors diferents, i val 0 si coincideixen.

La porta XNOR és la negació de la XOR ($w = \bar{x \text{ \textasciicircum } y} = xy + \bar{x}\bar{y}$). Actua com a comparador d'equivalència: genera un 1 si les entrades tenen el mateix estat lògic.

Regles fonamentals d'interconnexió

Perquè una estructura de portes lògiques constitueixi un circuit combinacional vàlid i operatiu, s'han de complir estrictament tres restriccions:

1. Prohibició d'unió de sortides: Mai s'han de connectar entre si dues o més sortides de portes o blocs. Si una porta intenta imposar un 1 (tensió d'alimentació) i una altra un 0 (massa), es produeix un curtcircuit elèctric i un estat de conflicte (indicat amb el símbol 'C' en entorns de simulació).
2. Definició completa de les entrades: Totes les entrades de totes les portes han d'estar connectades de forma unívoca a un senyal d'entrada o a una sortida anterior. Una línia sense connectar queda en estat d'alta impedància (indicat habitualment amb 'Z'), donant lloc a tensions flotants i comportaments impredictibles.
3. Absència de cicles o camins tancats: No hi pot haver camins de realimentació des d'una sortida cap a una entrada prèvia sense elements de memòria intermedis. La presència d'un cicle podria provocar oscil·lacions inestables o bé generar retenció d'estat, de manera que el sistema deixaria de ser un CLC per convertir-se en un circuit seqüencial asíncron.

Mètodes d'anàlisi de circuits combinacionals

L'anàlisi consisteix a deduir el comportament funcional d'un circuit —resumit en la seva taula de veritat o funció booleana— a partir del seu esquema lògic. Existeixen dues metodologies sistemàtiques: per propagació de files i per càlcul d'expressions per columnes.

Anàlisi per propagació de files

Aquest mètode avalua el circuit combinació a combinació, seguint els passos següents:

1. S'estableix una de les $2^n$ combinacions als senyals d'entrada (començant per la primera fila, normalment tots zeros).
2. Es propaguen aquests valors lògics a través de cada porta cap a les etapes posteriors aplicant les respectives taules de veritat individuals.
3. Quan s'arriba a la sortida final, s'anota el valor obtingut a la fila corresponent de la taula de veritat.
4. Es repeteix el procediment de forma seqüencial per a cadascuna de les files restants.

En l'esquema anterior es pot observar com es propaguen els quatre vectors d'entrada ($xy \rightarrow 00, 01, 10, 11$). A les sortides dels inversors es generen $a = \bar{y}$ i $b = \bar{x}$, a les portes AND es generen $c = x\bar{y}$ i $d = \bar{x}y$, i finalment a la porta OR la sortida és $w = c + d$, donant el vector 0, 1, 1, 0, que correspon precisament a una porta XOR.

Anàlisi per càlcul de columnes (nodes interns)

Quan el circuit conté més de tres variables o un nombre elevat de nivells lògics, l'anàlisi per files resulta lenta i propensa a errors. El procediment recomanat és l'anàlisi per columnes:

1. S'identifiquen i s'etiqueten tots els nusos o senyals interns del circuit (per exemple, $a, b, c, d, e$).
2. S'escriu l'expressió lògica associada a cadascun dels nusos en funció de les seves entrades immediates.
3. S'amplia la taula de veritat creant una columna per a cada node intern intermedi.
4. S'omplen les columnes de forma progressiva d'esquerra a dreta fins a obtenir la sortida definitiva.

Idees clau

• Un circuit lògic combinacional (CLC) es caracteritza pel fet que les seves sortides depenen únicament de les entrades actuals, sense memòria ni dependència temporal.
• La taula de veritat d'un CLC amb n entrades i m sortides conté exactament $2^n$ files i m columnes.
• Les portes lògiques bàsiques inclouen NOT, BUFFER, AND, OR, NAND, NOR, XOR i XNOR.
• En un CLC està terminantment prohibit interconnectar dues sortides, deixar entrades a l'aire o crear cicles de realimentació.
• L'anàlisi d'un circuit es pot dur a terme de forma puntual per files o bé de manera modular i desacoblada mitjançant columnes de nodes interns.

Posa a prova el que has après

1. Quina condició defineix estrictament un circuit lògic combinacional? — Les sortides depenen de les entrades actuals
2. Quina porta lògica produeix un 0 exclusivament quan les dues entrades són iguals? — XOR
3. Què representa l'estat Z en una simulació lògica d'un CLC? — Una entrada en alta impedància no connectada
4. Quin és el principal avantatge de l'anàlisi per columnes respecte a la propagació per files? — Descompon l'avaluació en nodes interns fàcils

Circuits lògics combinacionals — Mètodes de síntesi

Introducció a la síntesi de circuits lògics combinacionals

La síntesi d'un circuit lògic combinacional (CLC, concepte introduït a «Circuits lògics combinacionals — Fonaments i anàlisi») és el procediment sistemàtic pel qual s'obté un esquema lògic funcional a partir d'una especificació formal, normalment expressada mitjançant una taula de veritat. Mentre que en l'anàlisi es parteix de les portes lògiques per deduir la funció, en la síntesi es recorre el camí invers.

Secció completa amb Premium

Idees clau

• na aliqua ut enim ad minim veniam quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat lorem ipsu
• s nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat lorem ipsum dolor sit amet consectetur adi
• s nisi ut aliquip ex ea commodo consequat lorem ipsum dolor sit amet consectetur adipiscing elit sed do eiusmod tempor incid
• quat lorem ipsum dolor sit amet consectetur adipiscing elit sed do eiusmod tempor incididunt ut labore et dolore magna aliqua ut enim ad
• ctetur adipiscing elit sed do eiusmod tempor incididunt ut labore et dolore magna aliqua ut enim ad mini