Appunti - appunti sulle reti logiche per il corso del Prof. Roffia - Calcolatori elettronici - a.a. 2015/2016 PDF

Preview

Summary

Download Appunti - appunti sulle reti logiche per il corso del Prof. Roffia - Calcolatori elettronici - a.a. 2015/2016 PDF

Description

Reti Logiche Il primo passo nell’elettronica digitale

Marco Alessandrini

Universit`a degli Studi di Bologna (Sede di Cesena)

*** dedica ***

Che cos’`e il genio? E` fantasia, intuizione, colpo d’occhio e rapidit`a di esecuzione. - Amici Miei (1975) -

Indice Premessa

7

1 Reti logiche 1.1 Prerequisiti . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Percorso di apprendimento . . . . . . . . . . . . . . . . . . . . 1.3 Informazione e segnali . . . . . . . . . . . . . . . . . . . . . . 1.3.1 Codifiche binarie . . . . . . . . . . . . . . . . . . . . . 1.4 Operazioni logiche. Algebra di Boole . . . . . . . . . . . . . . 1.4.1 Tabella di verit` a . . . . . . . . . . . . . . . . . . . . . 1.4.2 Propriet` a degli operatori e teoremi di equivalenza . . . Esercizio 1.a . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.3 Forme canoniche . . . . . . . . . . . . . . . . . . . . . 1.4.4 Notazioni simboliche . . . . . . . . . . . . . . . . . . . 1.4.5 Espressioni generali . . . . . . . . . . . . . . . . . . . 1.5 Modelli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.5.1 Tempo di propagazione . . . . . . . . . . . . . . . . . 1.5.2 Transitorio . . . . . . . . . . . . . . . . . . . . . . . . 1.5.3 Macchina combinatoria . . . . . . . . . . . . . . . . . 1.5.4 Macchine sequenziali . . . . . . . . . . . . . . . . . . . 1.6 Strumenti di analisi e sintesi . . . . . . . . . . . . . . . . . . . 1.6.1 La tabella di flusso . . . . . . . . . . . . . . . . . . . . 1.6.2 Il diagramma degli stati . . . . . . . . . . . . . . . . . Esercizio 1.b . . . . . . . . . . . . . . . . . . . . . . . . . . .

9 10 10 10 12 16 16 17 19 20 20 21 22 22 22 23 23 26 26 26 27

2 Reti combinatorie 2.1 Reti di costo minimo . . . . . . . . . . . . . . . . . . . . . . . 2.2 Definizioni di espressioni minime . . . . . . . . . . . . . . . . 2.3 Mappa di Karnaugh . . . . . . . . . . . . . . . . . . . . . . . 2.3.1 Raggruppamenti Rettangolari . . . . . . . . . . . . . . Esercizio 2.a . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 Eliminazione di alee statiche . . . . . . . . . . . . . . Esercizio 2.b . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.3 Analisi di espressioni con K-mappe . . . . . . . . . . . 2.4 Porte logiche . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 Analisi e sintesi con porte logiche . . . . . . . . . . . . 2.4.2 Fan-out e fan-in . . . . . . . . . . . . . . . . . . . . . 2.4.3 Sintesi con soli NAND o NOR . . . . . . . . . . . . . Esercizio 2.c . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.4 Decoder . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.5 MUX . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.6 Sommatore (Full adder) . . . . . . . . . . . . . . . . .

29 29 30 31 33 34 35 36 36 38 38 38 38 39 40 41 41

6

Indice 2.5

Circuiti programmabili . . . . . . . . . . . . . . . . . . . . . . 43 2.5.1 ROM . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.5.2 PLA e PAL . . . . . . . . . . . . . . . . . . . . . . . . 44 2.5.3 PLD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3 Reti asincrone 3.1 Memorie binarie . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Latch SR . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.2 Latch CD . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.3 Flip-flop edge-triggered . . . . . . . . . . . . . . . . . 3.2 Eliminazione delle corse critiche . . . . . . . . . . . . . . . . . 3.3 Procedimento di analisi . . . . . . . . . . . . . . . . . . . . . 3.4 Procedimento di sintesi . . . . . . . . . . . . . . . . . . . . . 3.5 Grafi primitivi, grafi non primitivi . . . . . . . . . . . . . . . Esercizio 3.a . . . . . . . . . . . . . . . . . . . . . . . . . . .

47 48 48 49 49 49 50 51 52 52

4 Reti sincrone 55 4.1 Flip-flop . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 4.1.1 Flip-flop D . . . . . . . . . . . . . . . . . . . . . . . . 56 4.1.2 Flip-flop JK . . . . . . . . . . . . . . . . . . . . . . . . 56 4.1.3 Flip-flop T . . . . . . . . . . . . . . . . . . . . . . . . 56 4.2 Procedimento di analisi . . . . . . . . . . . . . . . . . . . . . 56 4.3 Procedimento di sintesi . . . . . . . . . . . . . . . . . . . . . 57 4.4 Registri e contatori . . . . . . . . . . . . . . . . . . . . . . . . 58 4.4.1 Registro accumulatore . . . . . . . . . . . . . . . . . . 58 4.4.2 Contatore binario . . . . . . . . . . . . . . . . . . . . . 58 Esercizio 4.a . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 Esercizio 4.b . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4.4.3 Registro a scorrimento . . . . . . . . . . . . . . . . . . 60 Elenco delle figure

64

Elenco delle tabelle

65

Bibliografia

67

Indice analitico

68

Premessa Se non sai risolvere un problema, allora ce n’`e uno pi` u semplice che puoi risolvere: trovalo. - George P´olya1 -

Lo studio delle Reti Logiche e`, generalmente, il primo affrontato dai giovani ingegneri dell’informazione. Esso `e propedeutico, per gli argomenti trattati, ad una lunga serie di altri insegnamenti successivi: Calcolatori Elettronici, Controlli Automatici, Elettronica dei Sistemi Digitali, oltre che i vari altri livelli di Elettronica. Mancare la comprensione delle linee principali circa le Reti Logiche (uno studio approfondito necessiterebbe di molti mesi) significa precludersi la via principale al successo in questo stesso esame e nei successivi, prima indicati. Per questo, mancando del materiale soddisfacente reperibile, vorrei tentare di fornire il mio approccio alla materia, che si e` rivelato tutto sommato soddisfacente. Il materiale `e tratto s`ı da appunti universitari, ma `e ove possibile integrato con riferimenti di livello tecnico inferiore per facilitare la comprensione. In molti casi, argomenti sviluppati con difficolt` a in sede universitaria vengono spiegati dai docenti di scuola superiore omettendo s`ı alcuni dettagli, ma permettendo agli studenti di capire di cosa si stia parlando. Nonostante il parere contrario di alcuni docenti, non `e detto che la semplificazione sia un male assoluto: pagando il prezzo di sopprimere alcuni dettagli, si ottiene in cambio la padronanza degli argomenti. Che `e, di base, l’obiettivo posto con questo manualetto.

1 George P´ olya (Budapest (Ungheria), 13/12/1887 - Palo Alto (USA), 7/9/1985), matematico ungherese.

Capitolo 1

Reti logiche Propongo di considerare questa domanda: “Le macchine sono in grado di pensare?”. - Alan Turing1 -

La logica `e l’ultimo rifugio della gente priva di immaginazione. - Oscar Wilde Sommario In questo capitolo introduttivo saranno esposte tutte le basi per iniziare, da zero o quasi, lo studio dei circuiti logici. In particolare ci si soffermer`a su alcune propriet`a dell’algebra binaria, anche proponendo degli esempi rilevanti. Saranno poi accennate alcune particolarit` a delle reti logiche, ognuna delle quali avr`a il proprio spazio di approfondimento nei capitoli successivi. ` E per` o bene cominciare da subito a familiarizzare con alcuni concetti, che ritorneranno utili a breve, eventualmente in maniera pi` u estesa.

Teorema 1. Una rete logica e` una macchina a stati finiti, nella quale i simboli di ingresso, uscita e stato sono espressi in notazione binaria. Sar` a utile, nel proseguio del capitolo, riprendere questo teorema per esplicare i concetti in esso insiti e richiamare alcuni requisiti necessari al corso. Nel frattempo, si pu` o individuare una serie di contenuti che, al termine, dovranno esser noti. Un minimo sindacale (soprattutto per rendere non troppo dettagliato l’elenco) comprende: • classificazione di segnali; • codice binario e codifiche binarie; • macchine a stati finiti; • metodi di studio e rappresentazione delle macchine; • reti combinatorie; • reti sequenziali asincrone; • reti sequenziali sincrone. 1 Alan Turing (Londra (GB), 23/6/1912 - Wilmslow (GB), 7/6/1954), matematico, logico e crittografo inglese.

10

Reti logiche

Si cercher` a di seguire l’ordine con rigorosit`a, evitando i salti e le lacune che caratterizzano troppi manuali di Reti Logiche (come, ad esempio, quello di Laschi [8]).

1.1

Prerequisiti

A titolo di prerequisiti `e richiesto di saper manipolare espressioni binarie ed operare con l’algebra binaria. Se ci` o non fosse possibile occorre attrezzarsi, aiutandosi con i paragrafi successivi. ` richiesta, inoltre, la conoscenza e la padronanza degli elementari struE menti matematici, in particolare per quanto riguarda la trattazione di espressioni polinomiali e la conservazione dell’equivalenza. Tutte le altre nozioni basilari sono fornite all’inizio del corso, dunque nel seguito di questo capitolo.

1.2

Percorso di apprendimento

La difficolt` a delle reti logiche sta nella loro espandibilit` a: aggiungendo elementi se ne complica la difficolt` a, arrivando anche a cambiarne la fisionomia e trasformarle in reti completamente differenti. Il punto di partenza, dopo aver introdotto alcuni concetti sull’informazione e alcuni criteri di analisi (che saranno sviluppati in seguito, caso per caso), `e lo studio delle porte logiche. Esse realizzano le pi` u comuni operazioni algebriche binarie. Combinando porte logiche in maniera opportuna si pu` o risolvere un’espressione pi` u complessa, in maniera analoga agli strumenti matematici comuni. Aggregando molte porte logiche, secondo particolari conformazioni standard, si ottengono delle reti combinatorie. Queste hanno la propriet` a di saper elaborare i dati, ma solo quelli istantaneamente presenti all’ingresso. Non sono, quindi, dotate di memoria. Inoltre soffrono di alcuni mali, ereditati dalle porte logiche, come i ritardi di propagazione e le alee. Per introdurre un concetto di memoria, aggiungendo alcune porte logiche in retroazione alla rete combinatoria si ottiene una rete sequenziale. La rete sequenziale pu` o essere asincrona, se i segnali in ingresso agiscono non appena inviati, oppure sincrona, se l’accesso dei segnali `e scandito e regolato da un controllore esterno (clock ). Per i vari tipi di rete sono previsti strumenti di analisi (per studiare le reti) e sintesi (per crearle, a partire da caratteristiche tecniche predeterminate). Ogni rete presenter` a dei vantaggi rispetto a quella precedente, di cui costituisce uno sviluppo, ma pure degli svantaggi che andranno risolti, volta per volta, con le tecniche conosciute o sfruttando le caratteristiche di altre reti o degli stessi componenti. L’idea principale `e che, partendo dal piccolo mondo dei gate, si possa ampliare man mano il loro utilizzo grazie agli strumenti (anche matematici o simili) e realizzare grandi macchine in grado di risolvere problemi complessi.

1.3

Informazione e segnali

L’elettronica si occupa della manipolazione dei segnali. Un segnale `e la variazione di una grandezza fisica. In particolare, i segnali dell’elettronica

1.3 Informazione e segnali

11

sono elettrici, sotto forma di tensione e/o corrente. Se siamo interessati a tutti i valori (infiniti) assunti dal segnale nel tempo, allora esso `e analogico; se, invece, ci interessano solo alcuni livelli (fasce) discreti del segnale, allora esso `e digitale o logico. Bisogna notare che un segnale non `e, a prescindere, analogico o digitale: `e l’utente che sceglie, a seconda delle esigenze, di considerarne tutti i valori o solo alcuni. Un segnale digitale, generalmente, ammette due soli livelli di valori: uno alto (valore logico 1) e uno basso (0). Questo segnale `e detto binario e i suoi valori sono detti bit. Il bit `e la quantit` a minima di informazione, perch´ e pu`o valere solo 0 oppure 1. L’informazione `e trasportata dal segnale, che `e dunque un vettore fisico. Definizione 1.3.1 (Informazione). L’informazione `e una diminuzione dell’incertezza. Come detto, l’informazione pi` u piccola e` la scelta tra due alternative che  1 si ha nel bit: il grado di incertezza `e del 50% , che `e pari all’informazione 2   1 1 . Ad esempio, su un dado a 6 facce: ricevuta 1 − = 2 2 1 − |{z} 100%

1 6 |{z}

incertezza

=

5 6 |{z}

informazione

1 5 a maggiori informazioni rispetto a Siccome > , il lancio di un dado mi d` 6 2 quelle fornite da un bit. Teorema 2. Maggiore e` la quantit` a di possibilit` a, minore `e l’incertezza, maggiore `e l’informazione. Sulla base di questo `e possibile classificare i segnali digitali e analogici: il segnale analogico pu` o trasportare grandi quantit` a di informazioni, le quali per` o sono disturbate dal rumore; il segnale digitale pu` o trasportare solo poche (di solito 2) alternative di informazione, che per` o sono sicure e protette dal rumore. Il progettista, quindi, deve valutare l’opportunit` a di trasportare molti dati in contrapposizione all’utilizzo di un vettore di informazioni robusto contro il rumore2 . Il corso di Reti Logiche si occupa esclusivamente di segnali digitali e delle tecniche per aumentare la quantit` a di dati trasportabili, analizzabili, processabili dalle macchine. 2 Il rumore e` un fenomeno elettromagnetico, dovuto alle caratteristiche fisiche dei mezzi (cavi, macchine, strumenti, eccetera) utilizzati. Poich´ e il rumore si somma al segnale, se si considera il segnale come analogico invece di leggere il valore vero leggeremo il valore con sommato il rumore (che e` aleatorio e dunque sconosciuto, come valore). Al contrario, sommando rumore al segnale digitale e` ben pi` u difficile che cambi il livello, perch´ e esso e` appartenente a una fascia ampia di possibili valori e il rumore non `e mai cos`ı grande da permettere il passaggio di stato.

12

1.3.1

Reti logiche

Codifiche binarie

Per trasmettere un segnale digitale si adotta un codice, affich´e il destinatario del messaggio possa comprendere quel che sta comunicando il mittente. Questo codice non `e unico: ne esistono molti tipi diversi a seconda degli impieghi e, soprattutto, delle problematiche (fisiche, strutturali, informative, . . . ) di cui tener conto. Di seguito sono illustrati brevemente alcuni codici di uso comune in Elettronica, a titolo di conoscenza o per essere utilizzati in seguito, per esercizi o altro. Ridondanza Un codice `e ridondante se il numero di bit trasmessi `e superiore al numero di bit strettamente necessari alla comunicazione del messaggio. Per contro, un codice non ridondante (o irridondante) trasmette un numero di bit pari a quello minimo necessario alla comprensione. Si pu` o stabilire di utilizzare un codice ridondante per utilizzare i bit in eccesso come controllo d’errore: esistono varie tecniche3 per rilevare e correggere gli errori in trasmissione, qualora il canale di trasmissione sia disturbato, sottoposto a perdite, o a rischio d’errore. Si paga, cos`ı, sulla quantit` a di dati da trasmettere (dunque sull’economicit` a) per rendere pi` u affidabile la comunicazione. Notazioni esadecimale e ottale Esprimere un numero secondo le potenze di 8 o 16 (operazione spesso compiuta in ambito informatico) sembrerebbe una cosa molto lontana dai dati binari. In realt`a, a ben pensarci, 8 e 16 sono potenze di 2. Lavorando di matematica si scopre che e` possibile agilmente convertire un numero binario in esadecimale o in ottale, semplicemente raccogliendono le cifre in gruppi e convertendole. In tabella 1.1 `e riportata la corrispondenza tra le quattro notazioni nelle basi 2, 8, 10 e 16. Se voglio convertire in esadecimale, raccolgo le cifre a 4 per 4 (partendo dalle meno significative) e converto ogni gruppo nel corrispondente esadecimale. Ad esempio: (10|1101|0011|1010|1011)bin = (2|D|3|A|B )hex (110|1100|0111|0101)bin = (6|D|C |7|5)hex Si nota facilmente che e` agevole convertire pure numeri spropositatamente lunghi, e in generale qualunque numero decimale anche molto elevato, senza nessun ausilio elettronico (` e sufficiente convertire in binario e poi raggruppare in esadecimale). Per convertire in ottale `e lo stesso identico discorso, salvo che i raggruppamenti sono da fare 3 per 3. Ad esempio, riproponendo i casi precedenti: (101|101|001|110|101|011)bin = (5|5|1|6|5|3)oct (110|110|001|110|101)bin = (6|6|1|6|5)oct 3 Queste tecniche, tra le quali si possono ricordare il controllo di parit` a , il FEC, l’ARQ, . . . sono studiate nei corsi di Telecomunicazioni.

1.3.1 Codifiche binarie Dec 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

13 Hex 0 1 2 3 4 5 6 7 8 9 A B C D E F

Oct 0 1 2 3 4 5 6 7 10 11 12 13 14 15 16 17

B3 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

B2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1

B1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1

B0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1

Tabella 1.1: Corrispondenza tra notazioni decimale, esadecimale, ottale e binaria Codice BCD Il codice BCD `e un metodo di espressione dei numeri decimali in formato binario. Al contrario del codice binario puro, col quale il numero decimale viene semplicemente convertito (per cui ad esempio 13dec = 1101bin ), il BCD suddivide il numero da convertire nelle singole cifre, convertendo queste ultime col corrispondente binario a 4 bit. Questo significa che, ad esempio, se devo convertire un numero decimale a 5 cifre in BCD, il risultato `e a 5 · 4 = 20 bit. A fronte dello spreco di circa 1/6 dei bit, c’` e il guadagno di una facile conversione a mano anche di numeri decimali imponenti. In tabella 1.2 `e illustrata la corrispondenza tra codice BCD e numeri decimali. Se, ad esempio, volessi convertire il numero 478302 in BCD: 4|7|8|3|0|2 = |0100 | {z } | {z } | 0010 | {z } | 0000 | {z } | 0011 | {z } | 1000 {z } | 0111 4

7

8

3

0

2

Codice per display a 7 segmenti Per visualizzare cifre esadecimali si utilizzano, solitamente, display a sette segmenti. Sono gli stessi che si trovano in alcuni vecchi registratori, televisori, calcolatrici, e in tutti i dispositivi pi` u moderni che usano cifre a cristalli liquidi. La struttura dei segmenti e` in figura 1.1.

Figura 1.1: Display a 7 segmenti

14

Reti logiche Dec 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

B3 0 0 0 0 0 0 0 0 1 1 X X X X X X

B2 0 0 0 0 1 1 1 1 0 0 X X X X X X

B1 0 0 1 1 0 0 1 1 0 0 X X X X X X

B0 0 1 0 1 0 1 0 1 0 1 X X X X X X

Tabella 1.2: Codice BCD Per ottenere le cifre si devono accendere i segmenti secondo le modalit` a in tabella 1.3. Hex 0 1 2 3 4 5 6 7 8 9 A B C D E F

a b c d e f g 1 1 1 1 1 1 0 0 1 1 0 0 0 0 1 1 0 1 1 0 1 1 1 1 1 0 0 1 0 1 1 0 0 1 1 1 0 1 1 0 1 1 1 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 1 1 1 1 1 1 0 0 1 1 1 0 0 1 1 1 1 0 1 1 0 0 1 1 1 1 1 0 0 0 1 1 1

Tabella 1.3: Codice 7 segmenti

Codice Gray Il codice Gray4 `e un codice esistente in tutte le lunghezze (in tabella 1.4 ne sono riportate le versioni a 2, 3 e 4 bit), la cui caratteristica fondamentale e apprezzatissima `e che, tra una configurazione e la successiva, si modifica un solo bit. Questo `e molto importante per evitare errori, specie in casi (meccanici) in cui il cambiamento contemporaneo di oltre un bit sarebbe 4

Frank Gray, ricercatore dei laboratori Bell.

1.3.1 Codifiche binarie

15

difficile o impossibile, e mal interpretato dalla macchina; col codice Gray se cambia un bit e` tutto a posto, se ne cambia pi` u d’uno per volta c’`e stato un errore. Si noti che il codice e` circolare, cio` e la propriet`a (che cambi un solo bit) esiste anche tra l’ultima configurazione in tabella e la prima. (a) Gray a 2 bit

Dec 0 1 2 3

B1 0 0 1 1

B0 0 1 1 0

(b) Gray a 3 bit

Dec 0 1 2 3 4 5 6 7

B2 0 0 0 0 1 1 1 1

B1 0 0 1 1 1 1 0 0

B0 0 1...