| << |  <  |  >  | >> |

Indice

Prefazione                                           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 XI

L'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 1

L'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.

| << |  <  |