Introducció als Computadors: teoria i disseny digital

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

Text del document

APUNTS INTRODUCCIÓ ALS COMPUTADORS Grau en Enginyeria Informàtica Universitat Politècnica de Catalunya AprenAI 2026-2027 Apunts complets d'Introducció als Computadors (FIB): representació binària i Ca2, circuits combinacionals i seqüencials, PPE i arquitectura UPG.

APREN.AI Índex 1 Aritmètica binària — Representació de naturals i enters en Ca2 Representació de nombres naturals i canvis de base Representació d'enters en complement a 2 (Ca2) Condicions de no representativitat (overflow) Circuits combinacionals 2 Fonaments, anàlisi i síntesi bàsica Definició i caracterització dels circuits combinacionals Portes lògiques elementals Regles d'interconnexió en circuits combinacionals Mètodes d'anàlisi de circuits combinacionals Síntesi clàssica mitjançant suma de minterms 3 Síntesi amb Decodificadors, ROM i retard Descodificador Dec-n-2^n i síntesi amb portes OR Memòria ROM com a matriu combinacional Temps de propagació, camí crític i glitches 4 Aritmètica combinacional — Sumadors, desplaçadors i comparadors Sumadors elementals: Half-Adder (HA) i Full-Adder (FA) El bloc sumador de n bits (ADD) i incrementador Detecció de desbordament: naturals ( ) vs enters ( ) Blocs de desplaçament (Shifters) Bloc restador SUB i síntesi de comparadors Circuits seqüencials 5 Biestables, registres i models de màquines Circuits combinacionals enfront de seqüencials El biestable D actiu per flanc ascendent Registres de dades i connexions seqüencials Models de màquines d'estats finits: Mealy i Moore Representació del comportament: grafs d'estats i taules 6 Síntesi i anàlisi temporal del cicle de rellotge Síntesi de circuits seqüencials de Moore Mètodes d'implementació: ROM i multiplexor Anàlisi temporal i camins de propagació Càlcul del camí crític i temps de cicle mínim c n v n Introducció als Computadors: teoria i disseny digital 1 7 Processadors específics — Arquitectura UC-UP, temps d'execució i disseny Arquitectura canònica: UP i UC Disseny de sistemes iteratius: Suma-4 i Suma-N Anàlisi temporal: camí crític i temps d'execució Estudi de cas: PPE pel Màxim Comú Divisor d'Euclides 8 Unitat de procés general — Arquitectura UPG, banc de registres i ALU Arquitectura global de la UPG Unitat Aritmètico-Lògica (ALU): estructura i operacions Banc de registres (REGFILE) Format de la paraula de control de 33 bits i aplicació 9 Formulari Aritmètica binària i formats numèrics Circuits combinacionals i blocs aritmètics Circuits seqüencials i anàlisi temporal Estructura de la Unitat de Procés General (UPG) 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. Introducció als Computadors: teoria i disseny digital 2 1 Aritmètica binària — Representació de naturals i enters en Ca2 EN ACABAR SABRÀS Calcular el rang de representació per a nombres naturals i enters en Ca2 amb n bits. Convertir nombres entre representació binària, decimal i hexadecimal. Aplicar l'extensió de signe i distingir-la de l'extensió amb zeros. Identificar les condicions d'overflow en operacions de naturals i enters. PENSA-HI ABANS DE LLEGIR 1 Per què un mateix patró binari com 1111 pot valer 15 o -1 segons com s'interpreti?

Els computadors processen dades mitjançant dígits binaris o bits. Per operar amb aquests valors numèrics, cal establir sistemes formals de codificació que permetin interpretar cadenes de bits com a magnituds naturals sense signe o com a valors enters amb signe. ESQUEMA Aritmètica binària en computadors Representació de nombres naturals i canvis de base Un nombre natural sense signe (unsigned, ) codificat amb bits utilitza la notació posicional clàssica en base 2. El valor es calcula sumant les potències corresponents a cada posició: El rang de valors representables per a una cadena de dígits en una base genèrica és . Per tant, en base binària el domini comprèn l'interval [0, 2^n - 1].

Per obtenir la representació d'un valor decimal a binari es divideix de forma successiva entre 2; el resultat es construeix recollint els residus des de l'últim quocient fins al primer residu. Nombres naturals Sense signe, rang [0, 2^n - 1] Extensió amb zeros Afegir 0s a l'esquerra Desbordament cn Detectat pel carry-out Nombres enters Complement a 2 (Ca2) Extensió de signe Replicar el bit més significatiu Desbordament vn Operands del mateix signe amb resultat oposat X u n X = u x i=0 n 1 i 2i n b [0, b n 1] Introducció als Computadors: teoria i disseny digital 3 Esquema de conversió decimal a binari mitjançant divisions successives per 2.

La conversió entre base 2 i base 16 (hexadecimal) és directa perquè : cada dígit hexadecimal equival exactament a un grup de 4 bits. Per a l'extensió de rang d'un nombre natural es manté el mateix valor simplement afegint zeros a l'esquerra. COMPROVA-HO 2 Quin és el rang de nombres naturals representables amb 5 bits? Representació d'enters en complement a 2 (Ca2) Per codificar nombres enters amb signe (signed, ), s'utilitza habitualment el sistema de complement a 2 (Ca2). En aquesta codificació, el bit de més pes ( ) actua com a bit de signe amb pes negatiu. Fórmula del valor decimal d'un enter en complement a 2.

L'expressió analítica per convertir una cadena binària en Ca2 a decimal és: 16 = 24 X s x n 1 X = s x n 1 2 + n 1 x i=0 n 2 i 2i Introducció als Computadors: teoria i disseny digital 4 Aquesta asimetria en el pes del bit més significatiu estableix el domini d'enters en Ca2 en l'interval [-2^{n-1}, 2^{n-1} - 1]. Per obtenir la representació d'un nombre negatiu a partir de la seva magnitud positiva es neguen tots els seus bits i s'hi suma 1. Per incrementar la mida de paraula d'un enter en Ca2, s'aplica l'extensió de signe: cal replicar el bit més significatiu a l'esquerra tantes posicions com calgui (0 si és positiu, 1 si és negatiu).

Bits ( ) Rang naturals ( ) Rang enters Ca2 ( ) 3 [0, 7] [-4, 3] 4 [0, 15] [-8, 7] 6 [0, 63] [-32, 31] 8 [0, 255] [-128, 127] ERROR FREQÜENT Confondre l'extensió de zeros amb l'extensió de signe. Si a un nombre negatiu en Ca2 (bit més significatiu 1) se li afegeixen zeros a l'esquerra, es converteix en un nombre positiu completament diferent. Per mantenir el valor de , cal replicar sempre el bit de signe. COMPROVA-HO 3 Quants bits com a mínim calen per representar el nombre -28 en Ca2?

Condicions de no representativitat (overflow) Quan se sumen dos nombres mitjançant un mòdul sumador (ADD), el resultat pot quedar fora de l'interval representable per a la mida de bits disponible: Desbordament en naturals: es produeix si i només si l'arrossegament de sortida del bit més significatiu ( ) és igual a 1. Desbordament en enters en Ca2 ( ): mai no hi ha desbordament si els dos sumands tenen signes diferents. En canvi, si els dos sumands tenen el mateix signe i el resultat presenta el signe oposat, es produeix overflow. Aquest indicador es calcula com: COMPROVA-HO 4 Pot haver-hi desbordament en sumar un enter positiu i un de negatiu en Ca2?

n X u X s X s c n v n v = n c n cn 1 Introducció als Computadors: teoria i disseny digital 5 IDEES CLAU El rang per a un nombre natural representable amb bits és . El rang per a un enter en complement a 2 amb bits és . El bit de més pes en Ca2 té assignat un pes negatiu: . L'extensió de rang d'un natural es fa afegint zeros a l'esquerra, mentre que en Ca2 cal replicar el bit de signe. En naturals l'overflow es detecta amb , mentre que en Ca2 s'indica per quan els dos operands tenen el mateix signe i el resultat té signe contrari. COMPROVA EL QUE HAS APRÈS 5. Com s'obté la representació binària en Ca2 d'un valor negatiu a partir de la seva representació positiva? 6.

Quin valor decimal representa la cadena binària 1001 en format natural i en format Ca2 de 4 bits? Test Encercla la resposta correcta. Les solucions són al final. 7. Quin és el rang d'enters representable en Ca2 amb 4 bits? 8. Com s'estén la longitud de paraula d'un enter negatiu en Ca2? 9. Quan es pot produir overflow en la suma d'enters en Ca2? 10. Quin indicador determina el desbordament en una suma de naturals?

n [0, 2 n 1] n [ 2 , 2 n 1 n 1 1] 2n 1 c = n 1 v = n c n c n 1 De 0 a 15 a) De -7 a 7 b) De -8 a 7 c) De -16 a 15 d) Afegint zeros a l'esquerra a) Replicant el bit de signe b) Afegint uns a la dreta c) Invertint tots els bits d) Sumands amb el mateix signe a) Quan el resultat és zero b) Sempre que carry-out val 1 c) Sumands amb signes oposats d) El bit de signe a) La condició vn = 1 b) El canvi de paritat c) L'arrossegament de sortida cn d) Introducció als Computadors: teoria i disseny digital 6 2 Fonaments, anàlisi i síntesi bàsica EN ACABAR SABRÀS Distingir un circuit combinacional per la seva absència de memòria i aplicar les regles d'interconnexió.

Construir la taula de veritat associada a un circuit analitzant-lo per files o per columnes. Sintetitzar una funció lògica elemental mitjançant suma de minterms amb portes AND, NOT i OR. PENSA-HI ABANS DE LLEGIR 11 Per què no es poden connectar directament dues sortides lògiques a un mateix cable per combinar-les? Els sistemes digitals processen informació binària mitjançant xarxes de portes que transformen combinacions d'entrada en sortides definides. ESQUEMA Circuits combinacionals Circuits combinacionals 2 Fonaments, anàlisi i síntesi bàsica 3 Síntesi amb Decodificadors, ROM i retard Fonaments Sense memòria, regles d'interconnexió Portes bàsiques NOT, AND, OR, XOR, etc.

Mètodes d'anàlisi Extracció de la TV Per files Propagació entrada a sortida Per columnes Càlcul de nodes intermedis Síntesi clàssica De la TV a l'esquema lògic Suma de minterms Estructura de portes AND-OR Introducció als Computadors: teoria i disseny digital 7 Definició i caracterització dels circuits combinacionals Un circuit lògic combinacional (CLC) és un bloc lògic sense memòria. La resposta de les sortides depèn exclusivament dels valors binaris presents a les entrades en aquest mateix instant, a diferència d'un circuit seqüencial (vegeu «Circuits seqüencials — Biestables, registres i models de màquines»).

DEFINICIÓ La taula de veritat (TV) descriu de manera exhaustiva el comportament funcional d'un CLC. Per a un circuit amb línies d'entrada i senyals de sortida, la taula conté exactament files i columnes de sortida. Com a exemple d'especificació, un multiplexor de 2 entrades de dades ( ) i un selector ( ) tria quina línia es transfereix a la sortida : Esquema d'un multiplexor de dues entrades amb el seu senyal selector. 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 Amb entrades, la taula té files i una única sortida ( ). COMPROVA-HO 12 Quantes files tindrà la taula de veritat d'un bloc combinacional amb 5 entrades i 2 sortides?

n m 2n m x , x 0 1 s w s x 0 x 1 w n = 3 2 = 3 8 m = 1 Introducció als Computadors: teoria i disseny digital 8 Portes lògiques elementals Les portes lògiques són els blocs combinacionals elementals a partir dels quals es construeixen circuits més complexos: Porta Funció lògica Comportament característic NOT Inverteix el nivell lògic de l'entrada AND Sortida a 1 només si totes les entrades valen 1 OR Sortida a 1 si com a mínim una entrada val 1 XOR Sortida a 1 quan les entrades són diferents NAND Negació de la funció AND NOR Negació de la funció OR XNOR Sortida a 1 quan les entrades tenen el mateix valor BUFFER Manté el valor per retardar o regenerar senyals Regles d'interconnexió en circuits combinacionals El disseny de CLC exigeix complir tres restriccions estructurals i elèctriques fonamentals: ERROR FREQÜENT Connectar dues sortides a un mateix node per intentar fer una operació OR és un error greu d'examen: genera un conflicte de tensió (curtcircuit C).

Les combinacions lògiques s'han d'efectuar sempre intercalant la porta corresponent. COMPROVA-HO 13 Per què la presència d'un camí tancat (cicle) invalida que un circuit sigui combinacional pur? Mètodes d'anàlisi de circuits combinacionals L'anàlisi consisteix a trobar la taula de veritat a partir d'un esquema amb portes. Es pot realitzar seguint dues metodologies: w = x ˉ w = x × y w = x + y w = x y w = x × y ˉ w = x + y ˉ w = x y ˉ w = x Prohibició d'unir sortides: mai no s'han de connectar directament dues o més sortides entre si, ja que provocaria un curtcircuit (indicat amb el símbol C en simuladors). 1 Definició obligatòria de les entrades: cap entrada pot quedar desconnectada.

Un senyal sense nivell assignat queda en estat d'alta impedància (indicat com a Z). 2 Absència de cicles: no es permet cap camí de realimentació tancat. La presència d'un cicle podria generar oscil·lacions inestables o emmagatzematge d'estat, trencant la condició de circuit sense memòria. 3 Introducció als Computadors: teoria i disseny digital 9 Anàlisi per files: s'avalua una combinació concreta d'entrades i es propaga el valor lògic a través de les portes fins a la sortida final. El procés es repeteix per a cadascuna de les files.

Anàlisi per columnes: s'assignen etiquetes als nodes interns del circuit, s'obté la columna de valors per a cadascun i es dedueixen successivament fins a completar la sortida. Esquema d'anàlisi lògica amb propagació de senyals interns. 0 0 1 1 0 0 0 0 1 1 0 0 1 1 1 0 0 1 1 0 1 1 1 0 0 0 0 0 Síntesi clàssica mitjançant suma de minterms La síntesi és el procediment invers: obtenir un circuit a partir de la taula de veritat. Una funció es pot implementar mitjançant: Descomposició en suma de minterms (SOP). Descodificador i portes OR (vegeu «Circuits combinacionals — Síntesi amb Decodificadors, ROM i retard»).

Memòria ROM (vegeu «Circuits combinacionals — Síntesi amb Decodificadors, ROM i retard»). En la síntesi per suma de minterms es defineix una porta AND per a cada combinació d'entrada que produeix un '1' a la sortida, complementant amb NOT les entrades que valen '0'. Finalment, s'agrupen tots els minterms amb una porta OR. x y a = x ˉ b = y ˉ c = x × a d = b × y w = c + d Introducció als Computadors: teoria i disseny digital 10 Esquema d'implementació d'una funció XOR mitjançant suma de minterms. Per a la funció XOR, els uns apareixen a les files i .

L'expressió final implementada és: COMPROVA-HO 14 Quantes portes AND calen per sintetitzar per suma de minterms una funció amb 4 entrades que val 1 en 3 combinacions? IDEES CLAU Un circuit combinacional (CLC) no té memòria: les sortides depenen únicament de les entrades actuals. La taula de veritat d'un circuit amb entrades i sortides té sempre files i columnes. Està prohibit unir sortides directament (curtcircuit), deixar entrades flotants (alta impedància) o establir cicles. L'anàlisi d'un CLC es pot dur a terme avaluant fila a fila o desglossant les columnes dels nodes interns. La síntesi bàsica per suma de minterms empra portes AND per als termes actius i una porta OR per reunir-los.

COMPROVA EL QUE HAS APRÈS 15. Quin efecte elèctric s'origina en unir dues sortides lògiques directament? 16. En què es diferencia l'anàlisi per files de l'anàlisi per columnes? m ( y) 1 x ˉ m (x ) 2 y ˉ w(x, y) = m (x, y) + 1 m (x, y) = 2 y + x ˉ x y ˉ n m 2n m Introducció als Computadors: teoria i disseny digital 11 CIRCUITS COMBINACIONALS 3 Síntesi amb Decodificadors, ROM i retard EN ACABAR SABRÀS Sintetitzar funcions lògiques combinacionals mitjançant descodificadors i portes OR. Calcular les dimensions i contingut binari d'una memòria ROM per a una taula de veritat. Identificar el camí crític d'un CLC i justificar l'aparició d'un glitch.

PENSA-HI ABANS DE LLEGIR 17 Per què un circuit combinacional pot donar un resultat erroni durant uns nanosegons abans d'estabilitzar-se? Descodificador Dec-n-2^n i síntesi amb portes OR La síntesi clàssica d'un circuit combinacional (CLC; vegeu «Circuits combinacionals — Fonaments, anàlisi i síntesi bàsica») a partir de la seva taula de veritat es pot realitzar mitjançant la descomposició en suma de minterms. No obstant això, aquest procediment requereix sintetitzar individualment cada terme producte amb inversors i portes AND. Un descodificador (Dec-n- ) simplifica aquest procés en generar directament tots els minterms possibles de les entrades.

Aquest bloc combinacional rep una adreça de bits i disposa de línies de sortida . El seu funcionament matemàtic estableix que . Per tant, una única sortida s'activa a nivell alt mentre totes les altres romanen a 0. L'estructura interna d'un descodificador està formada per portes NOT i portes AND de entrades cadascuna. 2n n A = a ...a a n 1 1 0 2n D = d ...d d 2 1 n 1 0 d = j 1 si i nom s si A = e ˊ u j n 2n n Introducció als Computadors: teoria i disseny digital 12 Esquema de l'estructura interna i símbol del descodificador Dec-3-8.

Per sintetitzar qualsevol funció lògica amb un descodificador, n'hi ha prou d'associar les variables d'entrada respectant estrictament els seus pesos binaris i connectar a una porta OR aquelles sortides que corresponen als minterms actius de la sortida desitjada. Si una funció només conté un únic minterm actiu, no cal cap porta OR addicional. COMPROVA-HO 18 Quantes portes i de quin tipus conté internament un descodificador Dec-3-8? Memòria ROM com a matriu combinacional La memòria ROM (Read Only Memory) porta la integració un pas més enllà encapsulant en un sol component el descodificador, una xarxa de connexions programable i les portes OR de sortida.

Emmagatzema informació no volàtil que equival directament al contingut de la taula de veritat del circuit. Una memòria ROM amb entrades d'adreça ( ) i sortides organitza les dades en paraules de bits. La seva capacitat total és de 2^n m bits, estructurada internament mitjançant: Un descodificador Dec-n- encarregat de seleccionar la fila o paraula sol·licitada. Una matriu de connexió interconnectada de mida punts. Un conjunt de portes OR, cadascuna amb entrades potencials, que recullen els bits de sortida. d j n 0 a 2 n 1 m m × 2n 2 × n m m 2n Introducció als Computadors: teoria i disseny digital 13 Esquema lògic i representació compacta d'una memòria ROM.

ESQUEMA Mètodes de síntesi de circuits combinacionals ERROR FREQÜENT Invertir l'ordre dels pesos de les entrades d'adreça ( com a bit més significatiu en lloc de ) desordena completament les files seleccionades de la ROM o les sortides del descodificador, fent que el circuit retorni valors erronis.

En comparar els tres mètodes de síntesi per a una taula de veritat de entrades i sortides, s'observen compromisos clars entre reutilització i cost d'àrea: Mètode de síntesi Components necessaris Grau d'integració Suma de minterms bàsica Portes NOT, AND específiques i OR Discret / baix Descodificador + portes OR Dec-n- extern i portes OR Modular / mitjà Memòria ROM Xip únic integrat ( bits) Complet / màxim COMPROVA-HO 19 Quants bits totals emmagatzema una memòria ROM de 3 línies d'adreça i 6 línies de dades?

Suma de minterms Implementació directa amb NOT, AND i OR Descodificador + OR Descodificador Dec-n-2^n compartit i portes OR Memòria ROM Descodificador, matriu i OR integrats a 0 a n 1 n m 2n m 2 × n m Introducció als Computadors: teoria i disseny digital 14 Temps de propagació, camí crític i glitches Els senyals binaris no es transmeten de manera instantània a través de les portes lògiques. El temps de propagació ( ) representa el retard temporal necessari perquè una transició a l'entrada es reflecteixi a la sortida d'un dispositiu. En portes individuals com NOT, AND o OR, aquest retard s'assumeix habitualment idèntic per a totes les entrades ( ).

Si una transició a l'entrada no altera l'estat de la sortida, es considera . Cronograma del temps de propagació en una porta AND-2. En circuits formats per múltiples portes interconnectades, existeixen diversos recorreguts entre les entrades i les sortides: Temps de propagació del circuit ( ): És el valor màxim de temps de propagació considerant totes les parelles entrada-sortida possibles. Camí crític: És el camí físic des d'una entrada fins a una sortida que presenta el més elevat. Poden existir múltiples camins crítics simultanis si comparteixen el mateix retard màxim.

Com a conseqüència dels retards asimètrics dels diferents camins interns, apareix el fenomen de glitch: un valor transitori incorrecte a la sortida del circuit mentre els senyals s'estan propagant. Un cop superat el retard del camí crític, la sortida s'estabilitza definitivament en el seu valor lògic correcte. PROCÉS Gènesi i resolució d'un glitch 1 Canvi a l'entrada Transició lògica en els senyals d'adreça 2 Propagació asimètrica Diferents camins presenten retards desiguals 3 Aparició del glitch Valor erroni transitori a la sortida 4 Estat estable Sortida correcta després del retard crític COMPROVA-HO 20 Per quina raó física apareix un glitch a la sortida d'un circuit combinacional?

T p T = px-w T py-w T = p 0 T p T p Introducció als Computadors: teoria i disseny digital 15 IDEES CLAU Un descodificador Dec-n- activa exclusivament la sortida quan el valor d'adreça val . La síntesi amb descodificador estalvia la implementació individual dels minterms canalitzant les sortides actives cap a portes OR. Una memòria ROM encapsula un descodificador, una matriu de connexions de punts i les portes OR de sortida. El camí crític d'un CLC és aquell que presenta el màxim temps de propagació entre entrades i sortides. Un glitch és un estat transitori incorrecte generat per diferències de retard en els camins interns d'un circuit. COMPROVA EL QUE HAS APRÈS 21.

Quina mida té la matriu de connexió d'una ROM amb 4 entrades d'adreça i 8 sortides? 22. Com es defineix formalment el temps de propagació total d'un circuit combinacional? Test Encercla la resposta correcta. Les solucions són al final. 23. Quantes files té la taula de veritat d'un circuit amb 4 entrades i 3 sortides? 24. Quina condició sobre un circuit trenca la condició de combinacional pur? 25. En una síntesi clàssica per suma de minterms, quina porta recull el resultat final? 26. Com s'anomena l'estat d'un senyal d'entrada que no té cap valor connectat? 27. Quina sortida s'activa en un Dec-3-8 si l'adreça d'entrada és 110 en binari?

2n d = j 1 A u j 2 × n m 16 files a) 64 files b) 12 files c) 8 files d) Utilitzar portes NOT a) Emprar més de dues entrades b) Presentar camins tancats (cicles) c) Tenir més d'una sortida d) Una porta OR a) Una porta XOR b) Una porta AND c) Una porta NOT d) Curtcircuit a) Alta impedància b) Minterm nul c) Glitch lògic d) Sortida d5 a) Sortida d3 b) Sortida d6 c) Sortida d7 d) Introducció als Computadors: teoria i disseny digital 16 28. Quants bits totals emmagatzema una memòria ROM de 8 paraules de 6 bits cadascuna? 29. Quina funció realitza el camí crític en un circuit combinacional? 30. Què produeix l'aparició d'un glitch a la sortida d'un CLC?

4 Aritmètica combinacional — Sumadors, desplaçadors i comparadors EN ACABAR SABRÀS Diferenciar l'estructura i taula de veritat d'un Half-Adder i un Full-Adder. Calcular i distingir el desbordament en naturals (carry-out) i en enters en Ca2 (flag de desbordament). Triar el tipus de bloc de desplaçament adequat (SL, SRL o SRA) per multiplicar o dividir naturals i enters. Sintetitzar comparadors de magnitud per a naturals i enters a partir d'un bloc SUB. PENSA-HI ABANS DE LLEGIR 31 Per què un sumador binari convencional no pot saber per si sol si el resultat d'una suma s'ha desbordat sense conèixer abans si els bits representen naturals o enters?

L'aritmètica combinacional construeix operadors digitals mitjançant circuits combinacionals (vegeu «Circuits combinacionals — Fonaments, anàlisi i síntesi bàsica»). Aquests mòduls permeten sumar, restar, desplaçar i comparar nombres naturals i enters en complement a 2 (vegeu «Aritmètica binària — Representació de naturals i enters en Ca2»).

64 bits a) 14 bits b) 24 bits c) 48 bits d) Optimitza el nombre de portes a) Inverteix la sortida lògica b) Elimina els estats transitoris c) Determina el retard màxim d) Canvis simultanis d'alimentació a) Saturació de portes AND b) Manca de línies de memòria c) Retards asimètrics entre camins d) Introducció als Computadors: teoria i disseny digital 17 ESQUEMA Blocs aritmètics combinacionals Sumadors elementals: Half-Adder (HA) i Full-Adder (FA) El bloc més bàsic és el Half-Adder (HA) o mig sumador. Aquest circuit rep dos bits d'entrada ( i ) i calcula la seva suma aritmètica produint dos bits de sortida: la suma i l'arrossegament de sortida (carry).

(carry) (suma) 0 0 0 0 0 1 0 1 1 0 0 1 1 1 1 0 Les expressions lògiques del Half-Adder són: Per encadenar múltiples etapes cal un Full-Adder (FA) o sumador complet, capaç de processar tres entrades: dos bits d'operand ( , ) i l'arrossegament previ .

0 0 0 0 0 Circuits sumadors HA, FA i sumador ADD de n bits Half-Adder i Full-Adder Síntesi cel·lular bàsica Sumador ripple-carry Cadena de n blocs FA Circuits restadors Bloc SUB basat en complement a 2 Blocs de desplaçament Shifters lògics i aritmètics Desplaçament esquerra (SL) Multiplica per potències de 2 Desplaçament dreta (SRL/SRA) Divisió de naturals i enters Comparadors de magnitud EQ, LTU, LEU, LT i LE x y s c x y c s s = x y, c = x y x k y k c k x k y k c k c k+1 w k Introducció als Computadors: teoria i disseny digital 18 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 1 0 0 0 1 1 0 1 1 0 1 1 0 1 0 1 1 1 1 1 Un Full-Adder es pot sintetitzar mitjançant dos Half-Adders i una porta OR per combinar els arrossegaments parcials: Esquema de síntesi d'un Full-Adder a partir de dos Half-Adders.

COMPROVA-HO 32 Quina és la diferència funcional bàsica entre un circuit HA i un circuit FA? x k y k c k c k+1 w k Introducció als Computadors: teoria i disseny digital 19 El bloc sumador de n bits (ADD) i incrementador Connectant blocs FA en cascada (propagate o ripple-carry) s'obté el bloc ADD de bits. Cada FA calcula el bit i passa el carry a l'etapa següent. La propagació de l'arrossegament des del bit 0 fins a fixa el camí crític del circuit (vegeu «Circuits combinacionals — Síntesi amb Decodificadors, ROM i retard»). Esquema del bloc sumador ADD de n bits amb carry. Un cas particular és l'incrementador (+1), que calcula .

Es construeix amb FA sumant el vector d'entrada amb el valor constant , o bé introduint directament un carry inicial . Detecció de desbordament: naturals ( ) vs enters ( ) El sumador ADD genera un resultat de mida fixa bits, calculant . La suma convencional compleix sempre la relació aritmètica següent: La interpretació del resultat depèn del format numèric: Nombres naturals: hi ha desbordament si el resultat necessita bits. Això s'indica directament amb el carry de sortida . Nombres enters en Ca2: hi ha desbordament ( ) si sumem dos nombres del mateix signe i obtenim un signe diferent. Això equival a comparar els dos últims arrossegaments: . n n w k c k+1 n 1 W = u (X + u 1) mod 2n n X 000 …

001 2 c = 0 1 c n v n n W = u (X + u Y ) mod u 2n X + u Y = u c n 2 + n W u n + 1 c = n 1 v = 1 v = n c n c n 1 Introducció als Computadors: teoria i disseny digital 20 Esquema del bloc ADD indicant els flags de carry i desbordament. ERROR FREQÜENT L'arrossegament final NO indica desbordament en enters en complement a 2. Per a nombres enters cal utilitzar exclusivament el flag de desbordament . Per exemple, en 4 bits, la suma de -7 ( ) i -1 ( ) dona -8 ( ) amb i : el resultat és correcte en enters ( ), però val 1.

0011 3 3 0110 6 6 1001 9 -7 0 1 1001 9 -7 1111 15 -1 1000 8 -8 1 0 1011 11 -5 1100 12 -4 0111 7 7 1 1 1000 8 -8 0010 2 2 1010 10 -6 0 0 COMPROVA-HO 33 Si sumem dos enters en 4 bits amb Ca2 i obtenim i , hi ha hagut desbordament d'enters? Blocs de desplaçament (Shifters) Els desplaçaments permeten implementar multiplicacions i divisions per potències de 2 sense emprar multiplicadors genèrics: SL-k (Shift Left lògic): desplaça posicions a l'esquerra i insereix zeros per la dreta. Multiplica per mòdul . És vàlid tant per a naturals com per a enters. En naturals es perd informació si algun dels bits més alts descartats val '1'.

En enters, no és representable si els bits més significatius d'entrada no tenen el mateix valor. SRL-k (Shift Right lògic): desplaça posicions a la dreta i insereix zeros per l'esquerra. Realitza la divisió entera exclusiva per a naturals; no és vàlid per a enters negatius perquè altera el bit de signe. c n v n 1001 2 1111 2 1000 2 c = 4 1 c = 3 1 v = 4 1 1 = 0 c 4 X X u X s Y Y u Y s W W u W s c n v n c = 4 1 c = 3 0 k 2k 2n k k + 1 k X /2 u k Introducció als Computadors: teoria i disseny digital 21 SRA-k (Shift Right aritmètic): desplaça posicions a la dreta i replica el bit de signe (extensió de signe) per l'esquerra. Divideix enters en Ca2 per preservant el signe.

El resultat és sempre representable. Bloc Operació aritmètica Inserció de bits Camp d'aplicació SL-k Multiplicació per Zeros a la dreta Naturals i enters en Ca2 SRL-k Divisió entera entre Zeros a l'esquerra Només naturals SRA-k Divisió entera entre Replica bit de signe Enters en Ca2 Bloc restador SUB i síntesi de comparadors El bloc SUB calcula la resta sumant amb el complement a 2 de . Genera el resultat , el carry de préstec (borrow) i el flag de desbordament .

Combinant SUB amb un detector de zeros z (una porta NOR de tots els bits de la resta), es construeixen els diferents comparadors de magnitud: Comparador Condició Senyal resultant EQ (Igualtat) LTU (Menor, naturals) (borrow de la resta) LEU (Menor o igual, naturals) LT (Menor, enters) LE (Menor o igual, enters) Per a enters en Ca2, si la resta no és representable ( ), el signe obtingut en el bit més significatiu queda invertit. Per tant, la condició de menor es corregeix efectuant l'operació XOR: . COMPROVA-HO 34 Per què la comparació en enters necessita l'expressió en lloc d'examinar només el bit de signe ?

k 2k 2k 2k 2k X Y X Y W b v X = Y X Y = 0 z X < u Y u b = 1 X u Y u b z X < s Y s w n 1 v X s Y s (w n 1 v) z X s Y s v = 1 w n 1 w n 1 v LT w n 1 v w n 1 Introducció als Computadors: teoria i disseny digital 22 IDEES CLAU Un Half-Adder suma 2 bits produint suma i arrossegament; un Full-Adder incorpora un arrossegament d'entrada permetent l'encadenament en cascada. En la suma de naturals, el desbordament s'identifica directament amb el carry de sortida . En la suma d'enters en Ca2, el desbordament es calcula amb i mai mirant només el carry final.

El desplaçament SL-k multiplica per afegint zeros a la dreta; SRL-k divideix naturals afegint zeros a l'esquerra i SRA-k divideix enters replicant el bit de signe. Els comparadors es construeixen a partir del bloc SUB: EQ empra el flag zero, LTU empra el borrow , i LT empra . COMPROVA EL QUE HAS APRÈS 35. Quina funció lògica s'utilitza per calcular el flag de desbordament d'enters a partir dels arrossegaments del sumador? 36. Per quina raó el bloc SRL-k no es pot emprar per dividir nombres enters negatius en complement a 2? Test Encercla la resposta correcta. Les solucions són al final. 37. Quin senyal indica que la suma de dos naturals no és representable amb n bits? 38.

Com gestiona el bloc SRA-k els bits buits que s'introdueixen per l'esquerra? 39. Com es detecta que X < Y (LT) en enters utilitzant el bloc SUB? 40. Quin d'aquests circuits no necessita un carry d'entrada en la seva estructura?

c = n 1 v = n c n c n 1 2k b w n 1 v v n El bit de més pes del resultat a) El flag de desbordament v b) El carry intermedi c c) El carry de sortida c d) Introdueix sempre zeros a) Inverteix els bits d'arrossegament b) Replica el bit de signe c) Introdueix sempre uns d) Fent una operació NOR a) Comprovant si b = 1 b) Calculant w XOR v c) Comprovant si w = 0 d) Half-Adder (HA) a) Sumador ripple-carry b) Full-Adder (FA) c) Bloc restador SUB d) Introducció als Computadors: teoria i disseny digital 23 5 Biestables, registres i models de màquines EN ACABAR SABRÀS Distingir el funcionament d'un circuit lògic combinacional d'un circuit lògic seqüencial.

Analitzar la resposta temporal del biestable D i l'operació de registres amb càrrega (Load). Diferenciar les arquitectures de Mealy i Moore en màquines d'estats finits. Interpretar i construir grafs d'estats amb les seves taules de transició i sortida. PENSA-HI ABANS DE LLEGIR 41 Com pot un circuit electrònic recordar si un botó ha estat premut anteriorment si el polsador ja s'ha deixat anar? Els circuits lògics seqüencials incorporen memòria interna per recordar la història prèvia del sistema.

ESQUEMA Circuits lògics seqüencials Circuits combinacionals enfront de seqüencials A diferència d'un circuit lògic combinacional (vegeu «Circuits combinacionals — Fonaments, anàlisi i síntesi bàsica»), on les sortides depenen únicament de les entrades actuals, en un circuit lògic seqüencial (CLS) el resultat depèn tant dels senyals d'entrada com de la informació emmagatzemada prèviament.

Circuits seqüencials 5 Biestables, registres i models de màquines 6 Síntesi i anàlisi temporal del cicle de rellotge Circuits seqüencials (CLS) Sistemes amb memòria i estat Biestables i registres Biestable D, REG-n, Load i desplaçament Models de màquines Arquitectures de Mealy i Moore Representació funcional Grafs d'estats i taules de transició Introducció als Computadors: teoria i disseny digital 24 Aquesta informació guardada rep el nom d'estat del sistema. Per allotjar-la s'utilitzen elements de memòria bàsics denominats biestables. Cada biestable guarda exactament 1 bit de dada. Si un CLS disposa de biestables, el seu vector d'estat conté bits, permetent diferenciar un màxim de estats.

En funció de com s'actualitza l'estat, els circuits seqüencials es classifiquen en: Asíncrons (event driven): l'estat pot variar en qualsevol instant temporal a partir d'un canvi en les entrades. S'apliquen principalment a circuits d'entrada/sortida. Síncrons (clock driven): les transicions estan governades per un senyal periòdic de rellotge (Clk) de període i freqüència . L'actualització de l'estat té lloc de manera coordinada cada unitats de temps. Per garantir l'estabilitat dels valors als sistemes síncrons, el període ha de ser prou gran per cobrir el temps de propagació del bloc combinacional encarregat de calcular el nou estat.

COMPROVA-HO 42 Quants estats diferents pot emmagatzemar un circuit seqüencial que disposa de 3 biestables interns? El biestable D actiu per flanc ascendent El component fonamental dels circuits seqüencials síncrons és el biestable D (també anomenat delay flip-flop). Disposa d'una entrada de dades , una entrada de rellotge Clk i una sortida . Símbol lògic del biestable D actiu per flanc ascendent El funcionament s'ajusta a una regla temporal estricta: el valor de l'entrada D es transfereix a la sortida Q exclusivament en l'instant del flanc ascendent de rellotge (transició de nivell lògic 0 a 1).

La sortida roman completament inalterada i estable durant la resta del període fins a l'arribada del següent flanc actiu. Aquesta dinàmica aporta propietats clau al disseny digital: Eliminació de glitches: neteja el senyal filtrant les oscil·lacions transitòries espúries procedents del circuit combinacional precedent. Estabilització del senyal: manté la sortida fixa durant tot el cicle un cop superat el temps de propagació intern del biestable ( ). k k 2k T c f = 1/T c T c T c D Q Q T p Introducció als Computadors: teoria i disseny digital 25 Retard d'un cicle: una mostra situada a l'entrada durant el cicle només apareix disponible a la sortida al cicle següent .

Registres de dades i connexions seqüencials Quan s'agrupen biestables que comparteixen la mateixa línia de rellotge, es forma un registre de n bits (REG-n). Tots els seus bits s'actualitzen simultàniament amb el flanc del rellotge comú. En el disseny de circuits seqüencials síncrons s'admeten bucles de realimentació cíclics sempre que qualsevol camí tancat travessi, com a mínim, un registre o biestable. D'aquesta manera s'eviten oscil·lacions combinacionals no controlades. Per evitar sobreescriure les dades a cada cicle, s'utilitza el registre amb càrrega (Load).

Mitjançant un senyal de control extern Ld i un multiplexor associat a l'entrada de cada bit, es decideix l'operació al flanc ascendent: Estructura interna d'un registre amb senyal de càrrega Load Si : es carrega el nou valor extern a l'interior del registre. Si : el registre realimenta la seva pròpia sortida , mantenint invariable el valor emmagatzemat. D'altra banda, en un registre de desplaçament (shift register), els biestables es connecten en cascada de manera que la sortida de cadascun és l'entrada del següent. Emmagatzema els darrers valors rebuts de l'entrada sèrie, oferint a les sortides les dades retardades seqüencialment: , , i .

D k Q k + 1 n Ld = 1 X Ld = 0 W n w = 0 x(t 1) w = 1 x(t 2) w = 2 x(t 3) w = 3 x(t 4) Introducció als Computadors: teoria i disseny digital 26 ERROR FREQÜENT Creure que un registre amb càrrega manté les dades desconnectant el rellotge. El rellotge sempre arriba als biestables de manera contínua; quan el registre manté el valor perquè el multiplexor torna a injectar la seva sortida actual cap a la seva pròpia entrada. COMPROVA-HO 43 Què passa a la sortida d'un registre amb senyal Load si durant el flanc ascendent tenim Ld = 0?

Models de màquines d'estats finits: Mealy i Moore Un sistema seqüencial general s'estructura mitjançant un registre d'estat de biestables que guarda l'estat actual i blocs combinacionals per calcular l'estat futur i les sortides a partir de les entrades . Model Funció d'estat futur ( ) Funció de sortida ( ) Dependència de la sortida Mealy Estat actual i entrades actuals Moore Únicament de l'estat actual En el model de Moore, les sortides depenen únicament de l'estat emmagatzemat, fet que evita que les variacions sobtades o glitches de les entrades externes passin directament a les sortides durant el cicle de rellotge.

Esquema estructural del model de màquina d'estats de Moore L'especificació d'un autòmat de Moore requereix determinar: 1. Bloc combinacional (transicions): té bits d'entrada ( d'entrades externes i d'estat actual) i bits de sortida d'estat futur. La seva taula té files. 2. Bloc combinacional (sortides): té només bits d'entrada (estat actual) i bits de sortida de dades. La seva taula té files.

Representació del comportament: grafs d'estats i taules El comportament d'un autòmat es descriu mitjançant taules de transició i sortida o bé de forma equivalent amb un graf d'estats: Ld = 0 k Q Q+ W X CLC r CLC s Q = + r(X, Q) W = s(X, Q) Q = + r(X, Q) W = s(Q) r n + k n k k 2n+k s k m 2k Introducció als Computadors: teoria i disseny digital 27 Nodes: representen cadascun dels estats del sistema. En el model de Moore, s'hi inscriu tant el codi d'estat com el valor de sortida associat ( ). Cal marcar clarament l'estat inicial (habitualment amb una doble circumferència). Arcs dirigits: expressen les transicions entre estats.

De cada node han de sortir exactament transicions, una per a cada possible combinació de les entrades. Llegenda: identifica la disposició de les variables als nodes i arcs ( als arcs, sortides al node) per fer el graf intel·ligible. A partir del graf es construeixen cronogrames de seguiment pas a pas, registrant la seqüència d'estats i sortides davant d'una determinada cadena d'entrades. COMPROVA-HO 44 D'un node d'un graf d'estats que té 2 variables d'entrada externes, quants arcs han de sortir obligatòriament? IDEES CLAU Un circuit seqüencial (CLS) basa les seves sortides en les entrades actuals i en la memòria prèvia del sistema (l'estat).

El biestable D s'actualitza només al flanc ascendent de rellotge, filtrant glitches i retardant la dada exactament un cicle. Un registre amb càrrega (Load) manté el contingut gràcies a un multiplexor que recarrega la sortida quan . Al model de Moore les sortides depenen exclusivament de l'estat actual, mentre que al de Mealy depenen de l'estat i de les entrades externes. El graf d'estats té arcs sortints per node per cobrir totes les possibles combinacions d'entrades. COMPROVA EL QUE HAS APRÈS 45. En què es diferencia la dependència de les sortides en els models de Mealy i Moore? 46. Quina funció compleix el senyal Load (Ld) en un registre?

q q /w w 1 0 1 0 2n n x x 1 0 Ld = 0 2n Introducció als Computadors: teoria i disseny digital 28 CIRCUITS SEQÜENCIALS 6 Síntesi i anàlisi temporal del cicle de rellotge EN ACABAR SABRÀS Calcular el nombre mínim de biestables i dimensionar les taules de transició i sortida per a un CLS de Moore Sintetitzar les funcions d'un CLS mitjançant l'estructura de ROM i multiplexor de busos Classificar els camins de propagació d'un CLS de Moore i calcular el temps de cicle mínim a partir del camí crític PENSA-HI ABANS DE LLEGIR 47 Per què un circuit seqüencial no pot funcionar a una freqüència de rellotge infinitament ràpida?

Síntesi de circuits seqüencials de Moore La síntesi d'un circuit seqüencial (vegeu «Circuits seqüencials — Biestables, registres i models de màquines») comença habitualment amb la representació del comportament desitjat en un graf d'estats. Per passar del graf a una descripció estructural cal codificar cadascun dels estats mitjançant variables binàries emmagatzemades en biestables. DEFINICIÓ Per codificar un total de estats diferents es requereix un nombre mínim de biestables donat per .

Quan certes combinacions d'entrada no poden ocórrer mai des d'un estat determinat, o bé quan certs patrons binaris dels biestables no s'assignen a cap estat real, aquestes transicions i sortides es tracten com a condicions indiferents (Don't Care). En el graf d'estats, una combinació d'entrades impossible es representa mitjançant un arc que no va a parar a cap node de destinació. Aquestes condicions permeten simplificar les funcions lògiques resultants. En el model de Moore, el sistema es descompon en dos blocs combinacionals: Bloc de transició d'estat ( ): rep entrades primàries i línies d'estat actual, i genera els bits d'estat següent ( ).

La seva taula de veritat té files i columnes de sortida. Bloc de sortides ( ): rep exclusivament els bits d'estat actual i produeix les sortides del circuit. La seva taula té files i columnes.

N k = log N 2 G n k k Q+ 2n+k k H k m 2k m Introducció als Computadors: teoria i disseny digital 29 PROCÉS Flux de síntesi d'un CLS de Moore 1 Graf d'estats Descripció funcional del sistema seqüencial 2 Codificació d'estats Assignació binària amb k = ceil(log2 N) 3 Taules de veritat Construcció de les taules G i H 4 Implementació estructural Síntesi amb portes, descodificadors o ROM COMPROVA-HO 48 Quantes files tenen respectivament les taules de transició i de sortida d'un CLS de Moore amb 3 entrades, 4 sortides i 5 estats?

Mètodes d'implementació: ROM i multiplexor Les taules de veritat obtingudes es poden implementar mitjançant portes lògiques discretes, descodificadors amb portes (vegeu «Circuits combinacionals — Síntesi amb Decodificadors, ROM i retard») o estructures de memòria ROM. Una alternativa eficient consisteix a unificar les funcions en una ROM amb multiplexor de busos. Esquema d'assignació de taules de transició i sortides a ROM amb multiplexor. En lloc d'adreçar la ROM amb totes les entrades i tots els estats alhora, s'adreça la memòria únicament amb els bits d'estat actual procedents del registre.

La paraula emmagatzemada conté l'estat següent per a cadascuna de les combinacions possibles d'entrada, a més dels bits de sortida corresponents a aquell estat. k 2n m Introducció als Computadors: teoria i disseny digital 30 Esquema estructural genèric d'un CLS sintetitzat amb ROM i multiplexor. A continuació, un multiplexor controlat per les entrades del circuit selecciona la combinació adequada de bits per alimentar l'estat següent ( ) del registre. La capacitat de memòria necessària es manté idèntica a la d'utilitzar dues memòries independents: Aquesta arquitectura unificada evita duplicar blocs d'adreçament extern i regularitza el disseny del mòdul de control.

Anàlisi temporal i camins de propagació Per garantir el funcionament lliure d'errors, cal assegurar que les entrades de tots els biestables romanguin estables abans que arribi el flanc actiu de rellotge. Els senyals no poden travessar un biestable sense sincronització, per la qual cosa els camins temporals es defineixen sempre entre punts d'origen i punts de destí ben delimitats. DEFINICIÓ En un CLS de tipus Moore es distingeixen exactament tres tipus de camins de propagació: Biestable a biestable (b-b): s'inicia a la sortida Q d'un biestable i finalitza a l'entrada D d'un altre biestable (o del mateix). Travessa exclusivament circuits combinacionals.

Entrada a biestable (e-b): comença en una entrada primària del CLS i arriba a l'entrada D d'un biestable. Depèn del temps que triga l'entrada externa a estabilitzar-se des del flanc anterior. Biestable a sortida (b-s): neix a la sortida Q d'un biestable i acaba en una sortida del CLS. Requereix mantenir la sortida estable abans del següent esdeveniment de rellotge. n k Q+ 2 k (2 n k + m) = 2 k+n k + 2 k m bits Introducció als Computadors: teoria i disseny digital 31 A diferència de les màquines de Mealy, en una màquina de Moore no existeixen camins combinacionals purs entrada-sortida (e-s), ja que les sortides depenen directament i exclusiva de l'estat intern emmagatzemat.

Esquema de traçat del camí temporal biestable-biestable amb retard acumulat. COMPROVA-HO 49 Per què en un circuit seqüencial de Moore no existeix cap camí temporal directe d'entrada a sortida (e-s)? Càlcul del camí crític i temps de cicle mínim El temps de propagació global d'un camí es calcula sumant els retards de tots els seus components: Camí b-b: . El retard del biestable de destí no s'hi afegeix perquè correspon al cicle següent. 1 T = p T (biestable origen) + p T (l gica combinacional) p o ˋ Camí e-b: . 2 T = p T + estabilitzaci d'entrada o ˊ T (l gica combinacional) p o ˋ Camí b-s: .

3 T = p T (biestable origen) + p T (l gica combinacional) + p o ˋ T estabilitat sortida requerida Introducció als Computadors: teoria i disseny digital 32 ERROR FREQÜENT Un error molt habitual és sumar el temps de propagació del biestable de destí al camí b-b, o cercar camins continus que creuin de llarg a través dels biestables. Els biestables tallen la propagació combinacional en sec: el camí acaba a la patilla D i no continua fins que arriba el flanc de rellotge. Un cop avaluats tots els camins de cadascun dels tres tipus, s'identifica el camí crític, definit com el camí amb el temps de propagació més alt de tot el circuit.

Per garantir la correcta captura dels valors a les entrades de registre, el temps de cicle mínim ( ) ha de complir: Tipus de camí Punt d'origen Punt de destí Elements inclosos en el càlcul de b-b Sortida Q del biestable Entrada D del biestable e-b Entrada primària del CLS Entrada D del biestable b-s Sortida Q del biestable Sortida primària del CLS COMPROVA-HO 50 Si en un CLS el camí b-b més lent triga 230 u.t., el camí e-b triga 180 u.t. i el camí b-s requereix 240 u.t., quin és el temps de cicle mínim Tc? IDEES CLAU Per codificar estats calen com a mínim biestables. En la síntesi amb ROM i multiplexor, la ROM s'adreça amb els bits d'estat i el MUX selecciona l'estat següent amb les entrades.

En un CLS de Moore només existeixen tres tipus de camins: biestable a biestable (b-b), entrada a biestable (e-b) i biestable a sortida (b-s). No hi ha camins combinacionals purs entrada-sortida (e-s) en un model de Moore perquè les sortides depenen únicament de l'estat. El temps de cicle mínim ha de ser igual o superior al retard del camí crític del circuit. T c T c T (cam cr tic) p ı ˊ ı ˊ T p T (biestable origen) + p T (portes intermediate) p T + estabilitat entrada T (portes intermediate) p T (biestable origen) + p T (portes) + p T marge sortida N k = log N 2 k n T c Introducció als Computadors: teoria i disseny digital 33 COMPROVA EL QUE HAS APRÈS 51.

Com s'expressa la capacitat total en bits d'una ROM utilitzada amb multiplexor de busos per sintetitzar un CLS amb k biestables, n entrades i m sortides? 52. Quins elements determinen el temps de propagació d'un camí de tipus entrada-biestable (e- b)? Test Encercla la resposta correcta. Les solucions són al final. 53. Quants arcs surten de cada node en un graf d'estats amb 3 entrades? 54. Quan s'actualitza la informació d'un biestable D actiu per flanc ascendent? 55. En el model de Moore, de què depenen les sortides del sistema? 56. Com reté les dades un registre amb càrrega quan Ld = 0? 57. Quants biestables es necessiten com a mínim per codificar un circuit seqüencial amb 11 estats? 58.

Quin tipus de camí temporal NO existeix mai en una màquina seqüencial de Moore?

16 arcs a) 6 arcs b) 8 arcs c) 3 arcs d) En qualsevol canvi de la dada d'entrada a) Durant el nivell alt de rellotge b) En la transició de 1 a 0 del rellotge c) En la transició de 0 a 1 del rellotge d) Només de les entrades actuals a) De l'estat actual i de les entrades b) Exclusivament de l'estat futur c) Únicament de l'estat actual d) Recarregant el valor de la sortida a l'entrada a) Posant la sortida en alta impedància b) Aturant el senyal de rellotge c) Resetejant els biestables a zero d) 11 biestables a) 3 biestables b) 4 biestables c) 5 biestables d) Biestable a biestable (b-b) a) Biestable a sortida (b-s) b) Entrada a biestable (e-b) c) Entrada a sortida (e-s) d) Introducció als Computadors: teoria i disseny digital 34 59.

Què s'inclou en el càlcul del temps de propagació d'un camí biestable-biestable (b-b)? 60. Com es defineix el temps de cicle mínim Tc d'un circuit seqüencial? 7 Processadors específics — Arquitectura UC-UP, temps d'execució i disseny EN ACABAR SABRÀS Descompondre un sistema digital complex en Unitat de Control (UC) i Unitat de Procés (UP). Definir i identificar els senyals de la paraula de control i de la paraula de condició. Calcular el temps de cicle crític (Tc) considerant els camins creuats entre UC i UP. Calcular el temps d'execució total (Te) a partir del nombre de cicles (Nc).

PENSA-HI ABANS DE LLEGIR 61 Per què no es dissenya un circuit de 16 bits amb un únic graf d'estats convencional? Quan un sistema digital ha de manipular dades amples (com ara paraules de 8 o 16 bits), dissenyar un únic circuit seqüencial mitjançant un graf d'estats global resulta inviable per l'explosió del nombre d'estats possibles. Per gestionar aquesta complexitat, s'aplica una estratègia modular que separa el maquinari en dos blocs coordinats.

Només la lògica combinacional intermèdia a) El biestable de destí i les entrades b) Ambdós biestables i la lògica intermèdia c) El biestable d'origen i la lògica intermèdia d) El retard exclusiu del camí biestable-sortida a) La suma dels tres camins principals b) Igual o superior al camí crític c) La mitjana de retards dels camins b-b d) Introducció als Computadors: teoria i disseny digital 35 ESQUEMA Estructura d'un Processador de Propòsit Específic Un Processador de Propòsit Específic (PPE) és un circuit digital dissenyat per executar un algorisme concret, estructurat internament en una Unitat de Procés i una Unitat de Control. Esquema de la interfície de comunicació entre la UC i la UP.

Arquitectura canònica: UP i UC La cooperació entre la gestió de dades i la presa de decisions es divideix clarament: Unitat de Procés (UP) o data path: conté els elements d'emmagatzematge de dades (registres i biestables) interconnectats amb operadors combinacionals (sumadors, restadors, comparadors, multiplexors i portes). S'encarrega de manipular i transformar el flux de dades de l'algorisme seguint una arquitectura feta a mida (ad-hoc). Unitat de Control (UC): màquina d'estats finits (típicament model de Moore) que governa l'operació de la UP mitjançant la generació seqüencial dels senyals adequats en cada cicle de rellotge.

Compta amb pocs estats interns en comparació amb el sistema global. La interfície de comunicació interna entre tots dos blocs es basa en dues línies d'informació clau: Processador Específic Arquitectura modular global Unitat de Control (UC) FSM que genera la paraula de control Paraula de control Senyals de selecció i càrrega Unitat de Procés (UP) Data path amb registres i aritmètica Paraula de condició Flags i esdeveniments (z, CMP) Introducció als Computadors: teoria i disseny digital 36 Paraula de control: conjunt de senyals binaris enviats de la UC cap a la UP. Inclou línies de selecció per a multiplexors i senyals de càrrega o habilitació per a registres.

Paraula de condició: senyals d'estatus enviats des de la UP cap a la UC que informen d'esdeveniments rellevants en les dades (per exemple, un flag de zero o el resultat d'una comparació), necessaris perquè la UC prengui decisions en branques o bucles condicionals.

Característica Unitat de Control (UC) Unitat de Procés (UP) Funció primària Orquestrar passos temporals i decisions Emmagatzemar i operar dades Entrades Entrades de control externes i paraula de condició Entrades de dades externes i paraula de control Sortides Sortides de control externes i paraula de control Sortides de dades externes i paraula de condició Components típics Biestables d'estat, ROM, multiplexors de control Registres, sumadors, restadors, comparadors, MUX de dades COMPROVA-HO 62 Quina informació viatja exactament en la paraula de condició i quin bloc la rep?

Disseny de sistemes iteratius: Suma-4 i Suma-N Per entendre el patró de disseny, s'analitza l'acumulació de dades en operacions iteratives modulars sobre . Cas Suma-4 L'objectiu és sumar seqüencialment 4 nombres de 8 bits que arriben cicle a cicle per l'entrada DATO a partir de l'activació del senyal Ini = 1 . El resultat es mostra a la sortida RESULT durant el cicle en què s'activa el senyal de finalització Fin = 1 . La UP requereix un registre acumulador de 8 bits ( REG ), un sumador de 8 bits ( ADD ) i un multiplexor de selecció. La paraula de control només necessita un bit Mx per triar si s'introdueix el primer operand directament o la suma acumulada.

28 Introducció als Computadors: teoria i disseny digital 37 Esquema lògic complet del circuit PPE Suma-4 amb ROM i UP. La UC disposa de 5 estats (codificats amb bits) sintetitzats típicament amb una memòria ROM i multiplexors: E0: estat d'espera i captura del primer operand si Ini = 1 ( , ). E1 a E3: estats d'acumulació successiva del 2n, 3r i 4t operand ( , ). E4: validació del resultat final ( , ), tornant a E0 o E1 segons el valor d' Ini .

Cas generalitzat Suma-N En el PPE Suma-N, el nombre d'elements és variable i s'introdueix pel bus X en el cicle inicial: Unitat de Procés: compta amb dos registres (un per a la suma acumulada i un altre per al comptador iterador), dos blocs aritmètics (un sumador ADD i un decrementador SUB de pas 1), multiplexors de configuració inicial ( Mx0 , Mx1 ) i una porta o bloc detector de zero ( z ). Paraula de condició: el senyal de sortida ( quan l'entrada del comptador arriba a 0). Paraula de control: formada pels senyals de selecció Mx0 i Mx1 .

Unitat de Control: consta d'un estat d'espera (E0), un d'inicialització de registres (E1), un bucle de càlcul (E2) que s'executa mentre , i un estat final de presentació del resultat (E3). COMPROVA-HO 63 Per què a Suma-4 no fa falta paraula de condició mentre que a Suma-N és imprescindible? k = log 5 = 2 3 Mx = 0 F in = 0 Mx = 1 F in = 0 Mx = 0 F in = 1 N z z = 1 z = 0 Introducció als Computadors: teoria i disseny digital 38 Anàlisi temporal: camí crític i temps d'execució Per garantir el funcionament rítmic s'ha de calcular el temps de cicle mínim ( ), el qual ve determinat pel retard de propagació del camí crític del sistema global.

En un PPE cal analitzar tant els camins interns com els camins creuats entre la UC i la UP: Camins entrada-biestable (e-b): des de les entrades de dades o control fins als registres interns (ex. ). Camins biestable-biestable (b-b): camins interns a la UP, interns a la UC o creuats entre ambdues unitats (ex. ). Camins biestable-sortida (b-s): des dels registres fins a les sortides externes (ex. ).

EXEMPLE DE CÀLCUL DE CAMÍ CRÍTIC A SUMA-4 Suposant retards de: , , , estabilitat d'entrades de , estabilitat abans del flanc de sortides de , : Camí e-b per dades: Camí b-b intern a la UP: Camí b-b creuat UC-UP: El camí crític és el camí e-b d'entrada de dades, imposant El temps d'execució ( ) total que triga el processador a completar una tasca es defineix pel producte del nombre total de cicles de rellotge emprats ( ) pel període de cicle: Mentre que a Suma-4 és constant, en general depèn del valor concret de les dades processades i s'obté resseguint el graf d'estats de la UC. ERROR FREQÜENT Analitzar únicament els retards interns de la UP o de la UC de manera aïllada.

En un PPE, sovint el camí crític s'origina a la UC (biestables d'estat i ROM de sortides de control) i finalitza a la UP travessant multiplexors i operadors aritmètics abans d'arribar al registre de destí, o a l'inrevés mitjançant la paraula de condició. Estudi de cas: PPE pel Màxim Comú Divisor d'Euclides L'algorisme d'Euclides calcula el MCD de dos naturals i de 16 bits restant repetidament el menor del major fins que tots dos són iguals ( ). T c DATO ADD MUX UP REG UP REG UC ROM MUX UP REG UP REG UP RESULT T (ADD) = p 500 u.t. T (MUX) = p 100 u.t. T (REG) = p 50 u.t. 120 u.t. 40 u.t. T (ROM) = p 80 u.t. 120 + 500(ADD) + 100(MUX) = 720 u.t. 50(REG) + 500(ADD) + 100(MUX) = 650 u.t.

50(REG ) + UC 80(ROM) + 100(MUX ) = UP 230 u.t. T c 720 u.t. T e N c T = e N c T c N = c 4 N c X Y A = B Introducció als Computadors: teoria i disseny digital 39 Diagrama de la UP per a l'algorisme del MCD d'Euclides. Unitat de Procés Per dur a terme l'algorisme amb maquinari compartit, la UP es dissenya amb els següents elements: Dos registres amb senyals de càrrega independents: REGA (amb senyal LdA ) i REGB (amb senyal LdB ). Un únic restador combinacional de 16 bits compartit per calcular tant com , precedit pels multiplexors Mx3 i Mx4 que commuten els operands. Dos multiplexors d'entrada ( Mx1 , Mx2 ) per escollir entre les dades externes noves ( , ) o la sortida del restador.

Un comparador de magnituds ( CMP ) que avalua els continguts d' i . Interfície i Unitat de Control La comunicació entre ambdues unitats s'organitza de la manera següent: Paraula de condició (UP cap a UC): dos senyals del comparador: diferència ( , expressat com ) i majoria ( ). Paraula de control (UC cap a UP): senyals de selecció de multiplexors ( Mx1 , Mx2 , Mx3 , Mx4 ) i senyals de càrrega ( LdA , LdB ). El graf d'estats de la UC arrenca en repòs a l'estat d'espera (S1).

Quan s'activa el senyal d'inici ( Ini = 1 ), es carreguen i als registres i es passa a comprovar la condició de sortida a S2: A B B A X Y A B A = B A B A > B X Y Si , s'avança directament cap a S3 (estat de finalització amb Fin = 1 ). 1 A = B Introducció als Computadors: teoria i disseny digital 40 COMPROVA-HO 64 Quants cicles trigarà l'algorisme d'Euclides a completar-se si les entrades inicials són X = 12 i Y = 12? IDEES CLAU Un PPE divideix el sistema en Unitat de Procés (camí de dades ad-hoc) i Unitat de Control (màquina d'estats finits). La UC dirigeix la UP mitjançant la paraula de control (senyals de selecció i càrrega de registres).

La UP envia a la UC la paraula de condició (flags i comparacions) per decidir salts i bucles. El temps de cicle mínim ( ) depèn del camí crític global, incloent camins creuats entre la UC i la UP. El temps d'execució total es calcula com , on depèn del nombre de cicles determinat per les dades. COMPROVA EL QUE HAS APRÈS 65. Quina funció té la paraula de control i en quin sentit viatja? 66. Com influeixen els camins creuats entre UC i UP en el càlcul del temps de cicle crític? 67. De què depèn el nombre de cicles en algorismes amb bucles com el MCD d'Euclides? Test Encercla la resposta correcta. Les solucions són al final. 68.

Quin bloc s'encarrega d'executar operacions com sumes o restes en un PPE? 69. Quina informació conté la paraula de condició enviada de la UP a la UC? Si , s'avalua la relació de magnitud: si es realitza la resta carregant només REGA (S5); si es computa carregant només REGB (S6). Ambdós retornen a avaluar la condició. 2 A = B A > B A B A < B B A T c T = e N c T c N c N c La Unitat de…