![]() |
|
|
| << | < | > | >> |IndicePrefazione XI Capitolo 1 Introduzione 1 Capitolo 2 Algebra di Boole e di commutazione 7 2.1 Algebra di Boole 7 2.1.1 Proprietà dell'algebra 9 2.2 Algebra di commutazione 11 2.3 Funzioni ed espressioni 13 2.3.1 Espressioni booleane 14 2.3.2 Funzioni booleane 15 2.3.3 Tabella della verità 16 2.3.4 Funzioni non completamente specificate 17 2.4 Forme canoniche 18 2.4.1 Teorema di espansione 19 2.4.2 Prima forma canonica 20 2.4.3 Seconda forma canonica 22 2.5 Espressioni e proprietà dell'algebra 23 2.6 Porte logiche 24 2.6.1 Operatori funzionai mente completi: NAND e NOR 27 2.6.2 Altre porte logiche 28 2.7 Circuiti logici 29 Esercizi 33 Capitolo 3 La codifica dell'informazione 39 3.1 Codici e codifiche 39 3.2 Codici numerici 42 3.3 Rappresentazione dei numeri naturali 44 3.3.1 Codifica naturale 44 3.4 Rappresentazione dei numeri relativi 49 3.4.1 Codifica in modulo e segno 49 3.4.2 Codifica in complemento alla base 50 3.4.3 Codifica in complemento alla base diminuita 52 3.5 Rappresentazione dei numeri razionali 54 3.5.1 Codifica in virgola fissa 54 3.5.2 Codifica in virgola mobile 58 3.5.3 Standard IEEE 754 59 3.6 Altri codici 61 3.6.1 Binary-coded decimal (BCD) 61 3.6.2 Gray 62 3.6.3 One-hot 63 3.7 Aritmetica binaria 63 3.7.1 Somma e sottrazione in codifica binaria naturale 64 3.7.2 Somma algebrica in codifica modulo e segno 66 3.7.3 Somma algebrica in complemento a 1 67 3.7.4 Somma algebrica in complemento a 2 70 3.7.5 Moltiplicazione in codifica binaria naturale 71 3.7.6 Moltiplicazione in codifica modulo e segno 73 3.7.7 Moltiplicazione in complemento a 2 73 Esercizi 78 Capitolo 4 Reti combinatorie 83 4.1 Introduzione. 83 4.2 Formalizzazione della specifica 85 4.3 Sintesi 86 4.3.1 Prima forma canonica 87 4.3.2 Seconda forma canonica 88 4.3.3 Funzioni non completamente specificate 89 4.4 Minimizzazione esatta 91 4.4.1 Metodo delle mappe di Karnaugh 92 4.4.2 Metodo di Quine-McCluskey 104 4.4.3 Metodi di supporto alla copertura 124 4.5 Minimizzazione euristica di reti a due livelli 130 4.5.1 Approccio iterativo 130 4.5.2 Descrizione del problema e soluzione iniziale 132 4.5.3 Trasformazioni 133 4.6 Minimizzazione euristica di reti su più livelli 138 4.6.1 Modello di riferimento 138 4.6.2 Trasformazioni 140 4.6.3 Applicazione delle trasformazioni 145 Esercizi 148 Capitolo 5 Circuiti combinatori speciali 167 5.1 Reti combinatorie di base 167 5.1.1 Multiplexer 167 5.1.2 Demultip1exer 169 5.1.3 Decoder 170 5.1.4 Priority encoder 172 5.2 Sommatori e sottrattori 173 5.2.1 Sommatori ripple-carry 173 5.2.2 Sommatori carry look-ahead 174 5.2.3 Sommatori carry-save 176 5.2.4 Sommatori misti 179 5.2.5 Sommatori / sottrattori 180 5.3 Complementatori 182 5.3.1 Complemento a uno 182 5.3.2 Complemento a due 183 5.4 Comparatori 185 5.4.1 Comparatori di uguaglianza 185 5.4.2 Comparatori generici 185 5.5 Moltiplicatori 187 5.6 Unità aritmetico logiche 191 5.6.1 Multiplexed ALU 191 5.6.2 Bit-sliced ALU 193 Capitolo 6 Macchine a stati finiti 195 6.1 Introduzione 195 6.2 Macchina di Moore e macchina di Mealy 198 6.3 Modelli per le macchine a stati finiti 201 6.3.1 Grafo di transizione dello stato 202 6.3.2 Tabella di transizione dello stato o tabella degli stati 203 6.3.3 Modello di Huffman 204 6.3.4 Rete logica sincrona 205 6.3.5 Differenze tra modelli comportamentali e modelli comportamentali/strutturali 206 6.4 Procedura di trasformazione dei modelli 207 6.4.1 Procedura per il passaggio da una macchina di Moore a una di Mealy 207 6.4.2 Procedura per il passaggio da una macchina di Mealy a una di Moore 207 Esercizi 211 Capitolo 7 Bistabili 217 7.1 Introduzione 217 7.2 Classificazione basata sulla modalità di sincronizzazione 218 7.2.1 Latch SR asincrono 218 7.2.2 Latch SR sincrono 222 7.2.3 Flip-flop master-slave 224 7.2.4 Flip-flop data lock-out 226 7.2.5 Flip-flop edge-triggered 227 7.3 Classificazione basata sul tipo 230 7.3.1 Tipo SR 230 7.3.2 Tipo D 231 7.3.3 Tipo JK 231 7.3.4 Tipo T 232 7.4 Temporizzazione e metastabilità 233 7.5 Ingressi asincroni di preset e clear 234 7.6 Analisi di funzionamento temporale 234 Esercizi 235 Capitolo 8 Sintesi delle macchine a stati finiti 243 8.1 I passi della fase di progetto 243 8.2 Dalla specifica al diagramma dello stato 245 8.2.1 Stato di partenza 245 8.3 Modelli di Mea1y e di Moore 247 8.4 Sequenza di interesse e completamento delle transizioni 248 8.5 Dal diagramma di stato alla tabella degli stati 255 8.6 Codifica dello stato 255 8.6.1 Codifica a distanza minima 258 8.6.2 Codifica a priorità 260 8.6.3 Codifica basata sull'uscita 264 8.7 Dalla tabella delle transizioni di stato codificato alla tabella delle eccitazioni 265 8.8 Riepilogo 267 Esercizi 268 Capitolo 9 Ottimizzazione delle macchine a stati finiti 281 9.1 Introduzione 281 9.2 Macchine completamente specificate 283 9.3 Macchine non completamente specificate 292 Esercizi 308 Capitolo 10 Ottimizzazione strutturale 319 10.1 Introduzione 320 10.2 Retiming 322 10.2.1 Modello per il retiming 323 10.2.2 Aspetti generali 324 10.2.3 Minimizzazione del periodo di clock 326 10.2.4 Minimizzazione dell'area 333 10.2.5 Pipelining ottimo 335 10.3 Peripheral retiming 338 Esercizi 340 Capitolo 11 Circuiti sequenziali speciali 349 11.1 Registri 349 11.1.1 Registro parallelo/parallelo 350 11.1.2 Registro serie/parallelo 351 11.1.3 Registro serie/serie 352 11.1.4 Registro serie/serie circolare 352 11.1.5 Registro parallelo/serie 353 11.2 Contatori 354 11.2.1 Progettazione comportamentale dei contatori 356 11.2.2 Progettazione strutturale dei contatori 359 11.2.3 Contatori veloci 361 Bibliografia 365 |
| << | < | > | >> |Pagina XIPrefazioneL'evoluzione delle tecnologie elettroniche ha portato a una sempre più ampia diffusione dei sistemi digitali in ogni ambito della vita quotidiana, dai telefoni cellulari alle macchine fotografiche digitali a molti componenti delle automobili. Nonostante la loro applicazione specifica, questi sistemi mantengono un'architettura di tipo generale, analoga dunque a quella dei personal computer, con una o più CPU che eseguono le applicazioni software e uno o più componenti hardware dedicati. La progettazione di sistemi con queste caratteristiche richiede quindi competenze miste, relative ai sottosistemi sia software sia hardware, e in ultima analisi implica la disponibilità di componenti hardware qualificati in termini di prestazioni, dimensioni e costi, che il progettista deve sapere appropriatamente scegliere e introdurre nel sistema. Questo libro ha lo scopo di fornire le competenze di base necessarie per progettare i componenti hardware di un sistema digitale. L'ampiezza e la complessità del tema avrebbero comunque impedito una presentazione completa; ci siamo perciò orientati a offrire una trattazione approfondita dei principi e dei metodi di base per la progettazione delle reti logiche sincrone, tralasciando dunque in particolare l'analisi delle reti asincrone oltre che lo studio di tutte le problematiche relative alla gestione del flusso di progetto. | << | < | > | >> |Pagina 1IntroduzioneL'evoluzione dei sistemi hardware digitali negli ultimi cinquant'anni è stata caratterizzata da miglioramenti in termini di funzionalità, costi e prestazioni mai visti in altri settori tecnologici. Oggi i sistemi hardware digitali pervadono le nostre vite, inseriti all'interno di oggetti di uso quotidiano. Questi sistemi, chiamati sistemi dedicati, sono tipologie di sistemi di elaborazione che svolgono compiti specifici all'interno di sistemi di tipo diverso. Tra gli esempi più comuni si possono ricordare i dispositivi mobili (palmari, cellulari), le macchine fotografiche o telecamere digitali, l'elettronica per applicazioni automobilistiche, i sistemi antifurto, elettrodomestici, apparecchiature per le telecomunicazioni, così come moltissime apparecchiature biomedicali. La crescente diffusione dei sistemi dedicati all'interno di molti oggetti di uso quotidiano e la continua evoluzione delle tecnologie di miniaturizzazione rendono sempre più reale il concetto di pervasive computing, che richiede l'integrazione su singolo chip di sistemi complessi. Questi dispositivi includono componenti hardware digitali dedicati, processori (spesso più di uno) tra loro interconnessi, componenti software interagenti, sensori, attuatori per l'interazione con il mondo fisico circostante, componenti a radiofrequenza per la comunicazione, componenti meccaniche ecc. Progettare questi sistemi è un compito difficile che richiede, oltre a delle solide competenze miste hardware e software, intuito ed esperienza. Tra le competenze di base richieste è quindi anche necessario essere in grado di realizzare componenti hardware dedicati, a partire dalla descrizione delle funzionalità richieste. Obiettivo di questo testo è quello di insegnare le tecniche fondamentali per progettare e implementare sistemi hardware digitali sincroni complessi. Un sistema hardware è un sistema realizzato mediante interconnessione di componenti elettronici che possono essere analogici o digitali: gli ingressi e le uscite di un sistema digitale possono assumere solo valori finiti e discreti. Un sistema digitale sincrono è un sistema in cui le uscite degli elementi cambiano valore solo in istanti ben precisi di tempo. In un sistema asincrono invece, le uscite possono variare in modo arbitrario nel tempo, rendendone più complessa la gestione. Oggi, la stragrande maggioranza dei sistemi hardware digitali è sincrona. È più semplice comprendere i sistemi hardware digitali considerando le modalità con cui vengono descritti, che possono essere distinte in base al livello di dettaglio della descrizione. In questo ambito consideriamo tre livelli: il livello comportamentale, il livello logico e il livello circuitale. Il livello comportamentale descrive in modo astratto gli ingressi, le uscite e la relazione tra di essi (il comportamento), ossia le funzionalità del sistema. Il livello logico considera la struttura del sistema definendo l'interconnessione (la rete) degli elementi logici di base, chiamati porte logiche, che rappresentano i componenti elementari utilizzati nella progettazione. A livello circuitale, i componenti di base sono rappresentati da dispositivi elettronici che implementano i componenti logici. Questo libro è dedicato alla progettazione logica, ossia alla trasformazione di una descrizione comportamentale in una descrizione in termini di reti di porte logiche, senza occuparsi dell'implementazione delle porte logiche a livello circuitale. L'obiettivo è quello di insegnare le diverse modalità di rappresentazione a livello comportamentale di un sistema digitale e le tecniche che consentono di trasformare questi modelli in una descrizione a livello strutturale (la cosiddetta sintesi logica), ossia nella rete di porte logiche. In realtà, la relazione tra descrizione comportamentale e descrizione strutturale non è univoca, ma esistono più reti che realizzano lo stesso comportamento. Quindi, in genere, si vuole realizzare una rete logica che soddisfi anche dei vincoli non funzionali, quali prestazioni, dimensioni, costi, consumo di potenza, in base alle caratteristiche e all'applicazione finale del sistema. In particolare, questo libro considera come criteri per l'identificazione della soluzione migliore la dimensione della rete finale, ossia il numero di porte logiche, o le prestazioni, ossia il tempo massimo di attraversamento della rete dall'ingresso all'uscita. Progettare un sistema significa quindi passare da una rappresentazione a un'altra, sempre più dettagliata, fino a ottenere il circuito fisico da realizzare. La rappresentazione iniziale consiste in genere in una descrizione in italiano, piuttosto imprecisa, dei requisiti funzionali e non del sistema da realizzare. Il primo passo consiste quindi nel tradurre questa descrizione in una rappresentazione più precisa e formale, iniziando dall'identificazione degli ingressi e delle uscite del sistema e della relazione che tra essi intercorre. La modalità di rappresentazione dipende dal tipo di funzionalità che si vuole descrivere: i sistemi più semplici sono caratterizzati dal fatto che le uscite dipendono dagli ingressi che si presentano nello stesso istante, mentre in quelli più complessi (la maggior parte dei sistemi) i valori delle uscite dipendono dalla sequenza temporale degli ingressi, ossia devono mantenere memoria del comportamento passato del sistema. Le reti logiche che implementano una funzione in cui il valore delle uscite dipende dal valore corrente degli ingressi vengono chiamate reti combinatorie. Un esempio è un addizionatore che realizza la somma tra due numeri presenti sugli ingressi. Le reti logiche che realizzano una funzione che dipende non solo dai valori correnti degli ingressi, ma anche dalla storia dei precedenti valori di ingresso, sono chiamate reti sequenziali. Tale dipendenza sarebbe molto difficile da soddisfare se il sistema dovesse effettivamente ricordare tutta la storia degli ingressi: in pratica i valori di ingresso corrente portano il sistema in un insieme finito di configurazioni, chiamate stati. Un sistema sequenziale prende quindi in ingresso la configurazione attuale dello stato e i valori di ingresso correnti e genera i nuovi valori di uscita e il nuovo stato. Dopo un certo intervallo di tempo il nuovo stato diventa lo stato corrente e il processo di calcolo del nuovo stato e dei nuovi ingressi si ripete. Nel nostro caso la configurazione del sistema cambia in risposta a un segnale di ingresso speciale, il clock, rendendo il sistema sincrono. Un esempio di semplice sistema sequenziale è quello di un semaforo, in cui il numero degli stati rappresenta la sequenza di cambiamento del colore del semaforo: rosso, giallo, verde, rosso. Le modalità di rappresentazione delle funzionalità di un sistema combinatorio e di un sistema sequenziale sono diverse. Nel caso dei sistemi combinatori è possibile rappresentare la funzionalità mediante una tabella che elenca, per ogni possibile configurazione degli ingressi, il valore delle uscite. Queste tabelle sono chiamate tabelle della verità e sono una buona rappresentazione di funzioni con pochi ingressi. Per sistemi con un numero di ingressi più elevato, la tabella della verità cresce di dimensioni in modo esponenziale: una rappresentazione alternativa è la descrizione della funzione mediante una espressione composta da operazioni sugli ingressi. Nel caso dei sistemi sequenziali è necessario specificare, per ogni configurazione di ingresso e di stato corrente, il valore delle uscite e dello stato prossimo: si chiama in questo caso tabella di transizione dello stato. In un sistema digitale, gli ingressi e le uscite sono segnali elettrici, che vengono rappresentati da valori discreti di tensione. In particolare, i sistemi digitali più semplici considerano solo due valori di tensione, rappresentati convenzionalmente da 0 e 1, ottenendo quindi un sistema binario: ogni ingresso o uscita può assumere solo due valori. I sistemi digitali binari rappresentano la base di quasi tutti i sistemi hardware digitali. Il principale vantaggio dei sistemi digitali è la rigorosa base matematica su cui si fondano, che deriva dalla logica matematica e dall'algebra di Boole. Questo è il motivo per cui il libro si apre con le basi dell'algebra di Boole, introducendo le operazioni logiche fondamentali che consentono di manipolare i valori logici. Il Capitolo 2 mostra che esiste una equivalenza tra tabelle della verità ed espressioni booleane, per cui è possibile derivare una espressione booleana da una tabella della verità e viceversa. Come già accennato, gli elementi logici di base nella rete logica sono le porte logiche: il capitolo mostra anche che esiste una equivalenza tra espressioni logiche e descrizione in termini di rete di porte logiche, grazie al fatto che per ogni operatore logico esiste una corrispondente porta logica. Il Capitolo 3 approfondisce le basi dei sistemi di codifica, in particolare i codici numerici, introducendo poi le operazioni aritmetiche, focalizzate sulla codifica binaria. Dopo aver fornito le basi matematiche per la rappresentazione sia del comportamento sia della struttura dei sistemi digitali, il libro prosegue nella presentazione dei metodi di trasformazione di una rappresentazione comportamentale nella rete logica ottimizzata secondo i criteri di prestazioni e area. Il Capitolo 4 inizia considerando le tecniche per trasformare la rappresentazione comportamentale di un sistema combinatorio nella corrispondente rete logica minima, considerando come criterio la minimizzazione del numero di porte logiche. Le prime reti logiche considerate sono le reti a due livelli, ossia costruite a partire dalla rappresentazione canonica derivata della funzione booleana, che esprime la funzione come la somma logica di termini di prodotti logici delle variabili di ingresso (o a partire dalla forma canonica duale, chiamata prodotto di somme). Il processo di riduzione di una funzione booleana nella sua forma minima è chiamato minimizzazione booleana. Il libro presenta sia dei metodi semplici, applicabili a funzioni con un numero di ingressi molto piccolo, sia un algoritmo dettagliato che consente di ottenere in modo esatto l'implementazione minima, con il minor numero di porte logiche. Questo metodo, chiamato metodo di Quine McCluskey, al crescere del numero degli ingressi può rapidamente non portare a una soluzione. Il capitolo presenta quindi i metodi euristici utilizzati negli strumenti software di sintesi logica combinatoria, il cui obiettivo è quello di trovare una buona soluzione velocemente senza garantire la soluzione minima. Infine il capitolo presenta le principali strategie per progettare reti logiche a più di due livelli, che consentono di minimizzare ulteriormente il numero di porte logiche rispetto alle reti a due livelli. Si tratta di strategie sofisticate, implementate in strumenti software di supporto alla progettazione, sia commerciali sia accademici, come SIS (sviluppato dalla University of California, Berkeley). Il Capitolo 5 conclude la parte relativa alle reti combinatorie, presentando come realizzare componenti combinatori più complessi a partire dalle porte logiche. Il Capitolo 6 è il primo dei capitoli dedicati ai sistemi sequenziali, il cui comportamento dipende non solo dai valori di ingresso correnti ma anche dalle sequenze passate e che devono quindi memorizzare tale informazione, rappresentata dallo stato. Il capitolo introduce i modelli di rappresentazione a livello comportamentale, basati sulle macchine a stati finiti, e a livello strutturale. Per mantenere le informazioni di stato è necessario disporre di elementi di memoria, realizzati a partire da un piccolo numero di porte logiche connesse in modo opportuno. Il Capitolo 7 presenta e classifica in base alle loro caratteristiche le diverse strutture degli elementi di memoria, che possono essere distinte principalmente in latch e flip-flop. Le porte logiche e gli elementi di memoria rappresentano quindi i componenti base per realizzare le reti logiche sequenziali. Obiettivo del Capitolo 8 è quello di presentare i metodi per derivare la macchina a stati finiti a partire da una descrizione a parole e quindi trasformare tale descrizione in una rete logica sequenziale, introducendo i passi necessari alla sintesi sequenziale.
La fase di ottimizzazione della macchina a stati finiti è
oggetto dei due capitoli seguenti. Il Capitolo 9 dedicato all'ottimizzazione
della rappresentazione comportamentale mentre il Capitolo 10 affronta l'analisi
delle possibili ottimizzazioni della rete logica derivata dalla sintesi. Infine,
il Capitolo 11 presenta i principali componenti sequenziali, utilizzati nella
realizzazione di sistemi più complessi. Al termine di ciascun capitolo (a
eccezione dei Capitoli 5 e 11, che come si è detto sono di natura più
descrittiva) sono riportati numerosi esercizi risolti e un certo numero di
esercizi proposti. Le soluzioni di questi ultimi sono disponibili nel booksite
abbinato al libro, all'indirizzo:
| << | < | > | >> |Pagina 195
Questo capitolo illustra il formalismo con il quale si descrivono sistemi la
cui risposta, ad una medesima sollecitazione, dipende anche dal tempo. Il
formalismo è quello relativo alle macchine a stati. Tra tutti i possibili
sistemi a cui è possibile riferirsi, l'ambito in cui ci si colloca restringe il
campo alle macchine fisicamente realizzabili che evolvono sulla base di un
evento esterno (segnale di sincronismo). Oltre ad illustrare le caratteristiche
formali della macchina utilizzata, questo capitolo descrive le procedure di
passaggio tra i due tipi macchine possibili (Mealy/Moore e viceversa) e presenta
alcune indicazioni sulle relazioni tra i modelli e gli ambiti applicativi.
6.1 Introduzione Una macchina a stati (detta anche automa a stati) è un modello matematico utilizzato come approssimazione di fenomeni fisici o astratti. Sebbene non sia parte degli obiettivi di questo testo mostrare la generalità e la potenza del modello, è rilevante sottolineare che la sua significatività non è confinata in una specifica area scientifica ma trova applicazione diretta in ambiti che spaziano dalla psicologia alla gestione finanziaria, dalla comunicazione alla linguistica, dall'attività neuronale al funzionamento di un sistema digitale e in molti altri ancora. Come è noto, un generico sistema è caratterizzato da un insieme di variabili che può essere suddiviso in variabili di ingresso, variabili di uscita e variabili di stato. Mentre quelle di ingresso e di uscita sono entità che possono essere osservate e misurate, quelle di stato rappresentano una condizione del sistema che permette di conoscere l'evoluzione dell'uscita a partire da una sequenza di ingresso nota: lo stato rappresenta, cioè, la memoria storica del sistema. Si osservi che, contrariamente a quanto avviene per le reti combinatorie (in cui l'uscita dipende solo dall'ingresso), l'uscita di una macchina a stati dipende sia dall'ingresso che dallo stato; ne consegue che è possibile osservare valori d'uscita differenti applicando lo stesso ingresso in istanti di tempo diversi. Sebbene sia possibile, da un punto di vista teorico, considerare un modello nel quale gli insiemi delle configurazioni di ingresso e di uscita e l'insieme degli stati possono avere cardinalità infinita, il contesto in cui ci si pone presuppone di considerare la realizzabilità come caratteristica essenziale; per questa ragione, le macchine a stati che vengono prese in esame sono caratterizzate da un insieme finito di simboli di ingresso X, da un insieme finito di simboli di uscita Z e da un insieme finito di stati S. Quest'ultimo aspetto riduce il campo di studio alle macchine a stati finiti o FSM (Finite State Machine).
Un'ulteriore restrizione al modello generale è dettata da
un'ipotesi relativa al "modello del tempo" che verrà adottato. In una generica
macchina a stati finiti, l'evoluzione dello stato è dettata da un evento; se
quest'ultimo è prodotto da una sorgente indipendente di sincronizzazione la
macchina è denominata
sincrona
mentre, nel caso in cui non lo sia, la macchina è definita
asincrona.
Nel contesto in cui ci si pone, gli automi considerati sono di tipo sincrono.
|