Che materia stai cercando?

Appunti completi corso Reti Logiche

Appunti completi del corso Reti Logiche tenuto dal prof Fabio Salice al Politecnico di Milano. Argomenti trattati:
- Algebra di Boole
- Metodo di Karnaugh
- Metodo di Quine McCluskey
- Metodo di Quine McCluskey per più funzioni
- Metodi euristici
- Sintesi multilivello
- Aritmetica dei Calcolatori
- Registri e bistabili
- Sintesi sequenziale sincrona
-... Vedi di più

Esame di Reti Logiche docente Prof. F. Salice

Anteprima

ESTRATTO DOCUMENTO

In questa lezione vediamo un caso particolare dell'algoritmo di McCluskey, cioè nella

situazione di funzioni a più uscite, ovvero funzioni vettoriali. In realtà è come il metodo

normale, ma con alcuni accorgimenti. Prima di questo ricordo un paio di cose che

potrebbero essere utili per l'esame: l'onset comune di due funzioni si ottiene calcolando

l'AND tra esse, o facendo l'AND bit a bit sulle mappe di Karnaugh. Per trovare il dcset

algebricamente conoscendo onset e offset, bisogna fare l'AND degli implicanti negati dei

due insiemi. Infine, per verificare se due funzioni sono uguali bisogna porle in XOR ed

eguagliare l'equazione a zero, ricordandosi che per lo XOR valgono le seguenti proprietà

algebriche: A ^ B = B ^ A

(A ^ B) ^ C = A ^ (B ^ C)

A ^ B = C ↔ A ^ C = B

A ^ A = 0

A ^ !A = 1

A ^ 0 = A

A ^ 1 = !A

Tornando a McCluskey, la cosa più semplice che ci verrebbe in mente di fare è applicare

McCluskey sulle singole funzioni e poi riunire le soluzioni. Ma capiamo subito che è una

boiata perché sicuramente le diverse funzioni d'uscita avranno delle parti in comune che

posso essere processate sullo stesso pezzo del circuito finale. Quindi uno penserebbe di

fare l'AND di tutte le coppie di funzioni di uscita per trovare l'onset comune, ma questo

lavoro ha una complessità troppo elevata perché il numero di coppie possibili cresce

esponenzialmente col numero delle funzioni. L'idea è cercare un metodo per trovare la

parte comune direttamente in fase di sintesi, lavorando sull'intera funzione di uscita e non

sulle singole componenti. Il concetto di onset comune si vede facilmente se utilizziamo le

mappe di Karnaugh: per ottenerlo basta fare la mappa di ogni funzione di uscita e poi

applicare l'AND bit a bit tra loro per ottenere la mappa delle parti comuni. Tuttavia si vede

subito che lavorare graficamente con le mappe è scomodissimo, per cui non useremo

questo metodo.

In McCluskey si comincia come sempre con la fase di espansione, aggiungendo però il

concetto di APPARTENENZA A UNA FUNZIONE di un implicante: ovvero nella tabella

iniziale in cui raccogliamo le configurazioni di onset (e dcset) categorizzate in base al

numero di 1, aggiungiamo per ogni configurazione una stringa binaria che indica a quale

funzione di uscita appartiene quell'elemento dell'onset. Quando “fondiamo” le

configurazioni, l'etichetta risultante sarà l'AND binario delle due etichette, dicendoci con

quali funzioni è in comune l'implicante esteso ottenuto. Se si ottiene una stringa di soli

zeri, significa che quell'implicante non copre nessuna funzione e viene perciò scartato.

Invece viene marcata quella configurazione iniziale che ha come etichetta la stessa del

risultato dell'AND delle etichette. Le configurazioni non marcate sono quelle che non si

possono più espandere, per cui sono da considerarsi degli implicanti primi, che verranno

poi scelti o scartati nella fase di copertura.

Si procede alla seconda fase con la tabella di copertura: qui bisogna stare MOLTO attenti.

Naturalmente, se ci sono, le condizioni di indifferenza non vanno messe nella tabella

perché non sono vincoli, però bisogna dividere in più sezioni le colonne, dove ogni sezione

contiene gli elementi dell'onset di una funzione. Quando si riempie la tabella, bisogna

stare attenti su quali elementi vengono effettivamente coperti da quell'implicante: può darsi

che le due funzioni abbiano un elemento in comune nell'onset, ma l'implicante considerato

in realtà ne copre uno solo. È a questo scopo che bisogna consultare le stringhe binarie di

ogni implicante. Per quanto riguarda i famosi criteri, ci sono degli accorgimenti

fondamentali. In quanto all'essenzialità, si può eliminare un implicante con tutte le sue

colonne solamente se esso è essenziale per TUTTE le funzioni, se invece è essenziale

solo per alcune funzioni, l'implicante rimane nella tabella e si tolgono le colonne solo della

funzione per cui l'implicante è essenziale. Il criterio di riga rimane invariato rispetto al

caso di una funzione singola, mentre il criterio di colonna è valido all'interno di una

singola funzione. In quanto al costo, ad ogni mintermine si assegna il costo iniziale 1, che

viene portato a 0 nel caso in cui un mintermine venga scelto per una o più funzioni ma

rimane nella tabella. In questo modo esso diventa un buon candidato nella scelta tra più

implicanti equivalenti. Un altro metodo è assegnare il numero di letterali, da porre poi a 1

nel caso in cui l'implicante venga scelto senza essere tolto dalla tabella.

Facendo un riassunto che a Salice piace sempre fare, finora abbiamo parlato della sintesi,

partendo dalle forme canoniche implementate dalle ROM e passando poi ad una sintesi

esatta con l'aiuto degli amici Karnaugh e McCluskey con l'obiettivo di minimizzare il costo

in termini di letterali e mintermini. Abbiamo capito che minimizzare i costi migliora anche le

prestazioni perché nella pratica si cerca di usare porte logiche con meno ingressi. Ci

siamo accorti che le semplificazioni tramite regole algebriche non portano a nulla mentre

gli amici citati ci aiutano su vari fronti, come la gestione di condizioni di indifferenza. Con

Karnaugh ci siamo resi conto che ci scontriamo con dei limiti, mentre McCluskey ci ha

permesso di spingerci più in là con il numero di variabili, permettendoci pure la sintesi di

funzioni vettoriali. Ma abbiamo ancora un problema: il problema della sintesi è NP-

completo con complessità esponenziale. Con i metodi esatti ci sarà sempre un limite

superiore al numero di variabili processabili. Come facciamo allora quando ci sono tante

variabili in gioco? Bisogna abbandonare i metodi esatti per utilizzare i metodi EURISTICI,

che sono gli unici che possono fornirci una soluzione adeguata, anche se approssimata.

In sta lezione non c'è nulla da studiare, consiste nel prof che parla di cose interessanti per

mezz'ora per darci un'idea di come funzionano i metodi euristici. Quello di cui ha parlato si

chiama ESPRESSO e in sostanza ripete iterativamente tre fasi: riduzione, espansione,

irridondanza. Quando la soluzione non migliora ulteriormente l'algoritmo termina.

L'espansione è quella che conosciamo noi e che facciamo sempre, ovvero consiste nel

“cancellare” letterali per espandere al massimo i mintermini e trovare quelli primi. Alla fine

togliamo i mintermini ridondanti, cioè che sono inglobati già in altri. La fase di riduzione è

quella che si fa per prima ma la vediamo per ultima perché è controintuitiva, ovvero

AGGIUNGE letterali. In pratica torna indietro per provare altre espansioni possibili non

provate. La riduzione avviene in sostanza prendendo dei mintermini parzialmente già

coperti da altri e togliergli gli 1 coperti (equivale questo ad aggiungere letterali). È questa

la parte euristica del processo! Una volta ridotto, il mintermine viene espanso in un'altra

direzione. La scelta di quale implicante ridurre è una cosa molto complicata... Nell'esempio

sulle slide sembra banale perché quello è un caso semplice e lo vedi subito a occhio, ma

nell'algoritmo c'è tutta una logica per assegnare un peso ad ogni implicante per decidere

chi ridurre e chi no. Nel resto delle slide è spiegato in dettaglio come funziona il lato

euristico ed è un po' complicato, ma si capiscono quali sono i principi ragionevoli per

assegnare le priorità ai mintermini. È simile agli algoritmi di A* o delle liste autorganizzanti.

Una cosa data per scontato nei problemi di sintesi affrontati finora, è che avevamo il

vincolo dei due livelli: un piano di AND uniti da un piano di OR. Ma se tralasciamo questo

vincolo, ci tuffiamo nel problema della SINTESI MULTILIVELLO e qui andiamo a sbattere

la testa. L'insieme delle soluzioni, che era già grande col vincolo dei due livelli, qui

esplode: è come confrontare la Terra con una supernova in termini di dimensioni, per

capirci. Per questo motivo in tale tipo di sintesi esistono SOLO algoritmi euristici: quelli

esatti ce li scordiamo! Inoltre si nota qualcosa di insolito: nella sintesi a due livelli c'era una

proporzionalità tra area e ritardo del circuito (ovvero tra costo e prestazione). Nella sintesi

multilivello invece aumentare l'area riduce il ritardo e viceversa, quindi di fatto non esiste

una soluzione ottima, perché si ragiona in termini di trade-off. Si fanno minimalizzazioni

dell'area con vincolo sul ritardo oppure minimizzazioni del ritardo con vincolo sull'area.

Proprio a causa di questo trade-off non esiste una soluzione ottima o univoca, le soluzioni

possibili sono numerosissime e NON ESISTONO algoritmi esatti per trovarle.

Le reti combinatorie a più livelli possono essere rappresentate tramite un grafo orientato

aciclico, noto anche come DAG, in cui si ha un nodo di partenza per ogni input, un nodo

d'arrivo per ogni output, e nel mezzo ci sono nodi che prevedono due ingressi e una

uscita. Ogni nodo interno contiene un'operazione logica a due livelli con gli ingressi. Da

questo grafo si ottengono delle trasformazioni, che possono essere LOCALI (modificano il

contenuto di un singolo nodo) oppure GLOBALI (si elimina un nodo sostituendo la sua

funzione logica nei nodi che la utilizzano).

Segue una lista di sostituzioni di cui sinceramente non ho capito un cazzo, ma ho capito il

metodo usato per compiere la FATTORIZZAZIONE, cioè cercare letterali in comune tra gli

implicanti partendo dalla forma canonica. Si fa una tabella che in ogni riga contiene un

implicante e in ogni colonna mette un possibile letterale. Se un letterale compare in un

certo implicante mettiamo 1 nella cella, altrimenti mettiamo 0. Aggiungiamo un'ultima riga

che conterrà la somma di ogni colonna: la prima colonna con la somma più grande

rappresenta il letterale che compare in più implicanti e viene fattorizzato. Si ripete

ricorsivamente l'algoritmo sulla tabella contenente gli implicanti a cui è stato tolto il

letterale finché si arriva a forme minime.

Ah la roba che non ho capito è che l'euristica consiste in una serie di trasformazioni sul

grafo. La fattorizzazione è solo una delle trasformazioni possibili. Un algoritmo chiamato

MIS (o nella sua versione più recente SIS) descrive l'ordine con cui eseguire queste

trasformazioni per ottenere una soluzione soddisfacente. La stesura di questo algoritmo e

la sua utilità sono date dall'esperienza d'uso e non da dimostrazioni formali, per questo si

tratta di procedimenti euristici, cioè dati dall'esperienza e dalla ragionevolezza delle scelte.

Questa parte è bella e anche semplice perché contiene alcuni argomenti già visti a

Fondamenti di Informatica e ad ACSO. Infatti si inizia parlando della codifica dei numeri

interi, che può essere in MODULO E SEGNO, dove il bit più significativo rappresenta solo

il segno (con 0 per numeri positivi e 1 per numeri negativi), mentre tutti i bit rimanenti

rappresentano il modulo. Ma nei calcolatori si usa il COMPLEMENTO A DUE, dove i

numeri negativi si rappresentano facendo il negato del numero positivo a cui si aggiunge

1. In questa codifica il bit più significativo non è il segno, ma è portatore dell'informazione

del segno, oltre ad avere valore numerico. Esiste anche una terza codifica, il

COMPLEMENTO A UNO, che funziona come il complemento a due senza sommare 1 nei

numeri negativi. In sostanza questa codifica non serve a nulla perché rimane il problema

che ci sono due modi per rappresentare lo zero e l'addizione e sottrazione restano

operazioni distinte.

Più interessante è la codifica dei numeri decimali, di cui abbiamo parlato al primo anno ma

li abbiamo poi lasciati un po' da parte. Sai che si possono rappresentare in VIRGOLA

FISSA e in VIRGOLA MOBILE. E sai già che la virgola fissa è semplicemente composta

da due interi: uno per la parte intera e uno per la parte decimale. La virgola mobile invece

è rappresentata in modo ben diverso, perché segue la notazione scientifica. Per esempio il

3

numero 3756,98 verrebbe espresso come 3,75698 x 10 . In questo esempio 10 è la

BASE, 3,75698 è la MANTISSA e 3 è l'ESPONENTE. Nei numeri in virgola mobile

abbiamo infatti dei bit dedicati alla mantissa, dei bit dedicati all'esponente e un bit per il

segno (si preferisce usare la codifica in modulo e segno). Inoltre la mantissa deve essere

NORMALIZZATA, cioè in decimale è un valore nell'intervallo [1, 10), in binario è un valore

nell'intervallo [1, 2). Quindi la prima cifra binaria della mantissa è sempre 1: per questo

motivo non si esprime e viene sottintesa, risparmiando un bit. L'esponente inoltre, siccome

deve rappresentare valori sia positivi che negativi, è shiftato di un valore detto di BIAS tale

che il valore 1, in precisione semplice, sia espresso da 1000000, mentre lo 0 sia espresso

da 01111111. In questo modo abbiamo che gli esponenti negativi iniziano con 0 mentre

quelli positivi (o nulli) iniziano con 1. Da questa regola possiamo capire come mai i floating

point possono rappresentare anche i valori di Infinito e NaN.

Precisione semplice Precisione doppia Precisione quadrupla

32 bit 64 bit 128 bit

Segno 1 1 1

Esponente 8 11 15

Mantissa 23 52 112

Bias 127 1023 16383

Mantissa Esponente

0 (pos/neg) 0 0

Numeri denormalizzati Non zero 0

Numeri normalizzati Qualunque Da 00000001 a 11111110

Infinito (pos/neg) 0 11111111

NaN Non zero 11111111

Un esponente esattamente pari a zero provoca l'UNDERFLOW, cioè la rappresentazione

di un numero troppo piccolo per cui viene approssimato a zero. Un esponente pari a 255

provoca l'OVERFLOW, ovvero un numero più grande del massimo rappresentabile.

Esempio di conversione da decimale a floating point:

4,25

Conversione base 4,25 → 100,01

10 2 2

Normalizzazione 100,01 → 1,0001 x 2

Traslazione esponente esponente + bias = 2 + 127 = 129 → 10000001

10 2

Segno Positivo

Risultato 0 10000001 00010000000000000000000

Esempio di conversione da floating point a decimale:

1 10000000 10010010000000000000000

Segno Negativo

Esponente esponente - bias = 128 - 127 = 1

Mantissa 1 + 1/2 + 1/16 + 1/128 = 1,5703125

Calcolo -1,5703125 x 2

Risultato -3,140625

A questo punto si parla dei circuiti logici che implementano l'addizione: i più semplici sono i

famosi HALF ADDER e FULL ADDER che fanno la somma e sottrazione di numeri binari

in complemento a due. Sai già come funzionano (calcolano la somma con uno XOR e il

riporto con un AND), ma sai anche che sono poco efficienti perché vi è il percorso critico

dato dal riporto che deve viaggiare attraverso tutti gli stadi del sommatore (appartengono

alla categoria dei circuiti RIPPLE CARRY). C'è un modo per velocizzare i conti? Beh se

scriviamo in forma algebrica l'espressione logica della somma e del riporto, scopriamo che

possiamo calcolare tutti i riporti in parallelo conoscendo solo il primo (cioè quello usato per

complementare). È ciò che fanno i CLA ADDERS (CARRY LOCK AHEAD ADDERS).

Questi circuiti implementano delle funzioni logiche (dette di GENERAZIONE e

PROPAGAZIONE) che sono di supporto per il calcolo in parallelo dei riporti. Le uscite poi

finiscono in un array di sommatori che devono semplicemente fare lo XOR dei bit di

ingresso col riporto. L'unica pecca di questo sistema è che diventa ancora più inefficiente

in presenza di tanti bit in ingresso, ma funziona bene fino a 4 bit. Per questo motivo in

realtà non si usa un unico CLA con tutti i 32 o 64 bit da sommare, ma ci sono più “strati”.

Ora è il momento cruciale: la MOLTIPLICAZIONE. Fare la moltiplicazione in codifica

naturale è molto semplice e non cambia assolutamente nulla da quello che si fa in

decimale. In realtà in binario è ancora più facile, perché siccome i valori ammessi sono

solo 0 e 1, se abbiamo un prodotto A * B allora nei prodotti parziali gli unici termini che

possono comparire sono A*0 cioè 0 e A*1 cioè A. Per la moltiplicazione in complemento a

due basta fare due accorgimenti essenziali: mentre nella codifica naturale i bit mancanti

sono sempre 0, nella moltiplicazione in complemento a due i bit mancanti sono una

ESTENSIONE DEL SEGNO. Questo vuol dire che se il moltiplicando è negativo, e quindi

ha come bit più significativo 1, allora anche nei prodotti parziali i bit aggiunti sulla sinistra

devono sempre essere 1. Questa è una cosa su cui porre molta attenzione perché è facile

sbagliare. Altra regola fondamentale è che il moltiplicatore DEVE ESSERE POSITIVO. Se

si ha un numero positivo per uno negativo, si invertono i due operandi. Se entrambi gli

operandi sono negativi, allora si fa il prodotto dei corrispondenti valori positivi, dato che il

risultato sarà lo stesso. Tuttavia per velocizzare il calcolo delle moltiplicazioni esiste un

metodo chiamato ALGORITMO DI BOOTH. Vediamo ora la sua versione più semplice,

RADIX-2, che non dà particolari vantaggi computazionali, e poi la versione RADIX-4 che

velocizza di molto i calcoli.

Nella versione radix-2 dell'algoritmo di Booth, il moltiplicatore viene espresso con una

codifica tale per cui si aggiunge uno 0 in fondo e si prendono, scorrendo da destra verso

sinistra, gruppi di 2 bit sovrapposti (eventualmente estendendo il segno). Ad ogni coppia di

bit assegniamo il valore -a+b, come in questo esempio:

0110010 → 01100100 → 01 11 10 00 01 10 00

01 → 1

11 → 0

10 → -1

00 → 0

01 → 1

10 → -1

00 → 0

A questo punto non facciamo più la moltiplicazione con il moltiplicatore originale, ma con

una sequenza che vale 1 0 -1 0 1 -1 0. In questo modo abbiamo che in una moltiplicazione

A * B, il prodotto parziale vale:

0 se B = 0

– A se B = 1

– -A se B = -1

Il tutto con l'estensione del segno (da non dimenticare). Questo metodo non velocizza il

calcolo dei prodotti perché il numero di prodotti parziali rimane uguale rispetto al caso

della moltiplicazione normale. Tuttavia radix-2 è didatticamente utile per introdurre il radix-

4, che invece migliora di molto i tempi di calcolo.

Radix-4 si differenzia dal radix-2 per il fatto che il moltiplicatore viene diviso in gruppi di 3

bit anziché 2. In questo caso la codifica diventa -2a+b+c, ovvero:

000 0

001 1

010 1

011 2

100 -2

101 -1

110 -1

111 0

Utilizzando questa codifica il numero di prodotti parziali si dimezza e si calcolano con

queste semplici regole:

0 se B = 0

– A se B = 1

– A*2 (ovvero A.0) se B = 2

– -A se B = -1

– -A*2 (ovvero -A.0) se B = -2

A sto punto uno si chiede: ma perché non fare un radix-8 dove prendi gruppi di 4 bit e

riduci a un quarto il numero di prodotti parziali? Teoricamente si può fare, ma in questo

modo ti ritrovi dei prodotti con numeri poco carini come 3, 5, 6, 7 che non si calcolano

facilmente. Così facendo il vantaggio di avere meno prodotti parziali viene distrutto dal

fatto che questi prodotti diventano complicati e quindi non ha senso. Con il radix-4 invece

riduciamo i prodotti parziali e sono facili da calcolare perché facciamo moltiplicazioni per 1

e per 2.

Anche questa lezione è piuttosto semplice perché affronta argomenti già visti in ACSO e in

Elettronica, ma sono argomenti molto importanti e facciamo bene a ripassarli. Da qui in poi

studieremo i circuiti sequenziali, ovvero quelli in cui l'uscita non dipende solo dagli

ingressi, ma anche dallo stato del circuito. Questo significa che le uscite sono dipendenti

dalla storia passata e dalle condizioni iniziali considerate.

Il circuito base delle reti sequenziali è il BISTABILE, che ha lo scopo di memorizzare un

bit. Sai bene che è composto da due NOR retroazionate, dove le uscite sono Q e Q' e gli

ingressi sono S (detto SET) e R (detto RESET). Il segnale di set imposta l'uscita Q a 1, il

segnale di reset imposta l'uscita Q a 0. Quando entrambi i segnali non sono attivi l'uscita

Q rimane costante, mentre se set e reset sono attivi contemporaneamente si ha uno stato

instabile, per cui l'uscita si porta in modo imprevedibile a 1 oppure a 0. Per questo la

configurazione (S, R) = (1, 1) è vietata. Questo circuito si chiama BISTABILE SR

ASINCRONO.

Il comportamento dei circuiti sequenziali si può esprimere attraverso la TABELLA DELLE

TRANSIZIONI, che indica qual è lo stato prossimo a partire dagli ingressi e dallo stato

attuale, o la TABELLA DELLE ECCITAZIONI, che indica quali devono essere le

configurazioni in ingresso per cambiare stato. Vediamo un esempio sul bistabile SR:

TRANSIZIONI ECCITAZIONI

S R Q* Q Q* S R

0 0 Q 0 0 0 -

1 0 1 0 1 1 0

0 1 0 1 0 0 1

1 1 - 1 1 - 0

Dalla tabella delle transizioni si ricava l'ESPRESSIONE LOGICA, che nell'esempio in

esame è Q* = S + R'Q

Il problema del circuito appena visto è che è appunto asincrono. Il suo comportamento non

è controllato e dipende dagli eventi agli ingressi. Ma sai bene che ingressi e uscite non si

aggiornano istantaneamente: ci sono dei ritardi di propagazione che non fanno comportare

il circuito come desiderato. Per questo si aggiunge un segnale di controllo C a monte del

bistabile tale per cui se C = 0 gli ingressi non sono visibili (modalità OPACA), mentre se C

= 1 gli ingressi possono agire (modalità TRASPARENTE). Il bistabile con il segnale di

controllo si chiama LATCH SR ed è composto in ingresso da due AND: il primo con

ingressi S e C, il secondo con ingressi C e R. Da questo circuito si può realizzare un

LATCH D composto da un ingresso D che impone la relazione S = R'. In questo caso,

quando il latch è in modalità trasparente, lo stato insegue l'ingresso D. A questo punto il

prof ci fa vedere un esempio che fa capire il problema di fondo dell'asincrono: prova a

costruire uno shift register con latch D. Beh, la sorpresa è che le nostre intenzioni sono di

shiftare un solo bit, invece tutti i bit vengono shiftati continuamente fintantoché il segnale di

controllo è alto. Per shiftare un solo bit dovremmo sapere per quanto tempo tenere alto il

segnale di controllo, ma questo tempo dipende da circostanze non misurabili e contingenti:

la tecnologia usata, i ritardi di propagazione, la temperatura ecc... Non è così che si fanno

gli shift register!

Prima di andare oltre è bene sapere che esiste il bistabile JK che dà un senso alla

configurazione (S, R) = (1, 1) ovvero inverte lo stato. È realizzato con una AND a tre

ingressi dove il terzo ingresso è la retroazione dell'uscita stessa. Tuttavia il latch JK è

instabile, perché quando i segnali S ed R sono entrambi alti e il latch è in modalità

trasparente, l'uscita continua a commutare finché il segnale di controllo rimane alto. Perciò

non è possibile prevedere quale sarà l'uscita quando si abbasserà il segnale di controllo.

Per risolvere i problemi visti dobbiamo introdurre un ulteriore elemento di sincronismo, e a

questo scopo esistono i FLIP FLOP, in versione MASTER SLAVE oppure EDGE

TRIGGERED. In particolare il master slave è composto da due latch SR in cascata dove il

segnale di controllo è inviato dritto nel primo (il master) e negato nel secondo (lo slave), in

modo che non capita mai che i due latch siano trasparenti nello stesso momento. Così

facendo, quando il segnale di controllo è alto, il master vede l'ingresso e aggiorna lo stato

interno del circuito, e quando il segnale di controllo è basso lo slave vede il nuovo stato e

aggiorna l'uscita. L'edge-triggered è una versione più sofisticata che effettivamente

campiona gli ingressi sui fronti di salita o discesa del segnale di controllo e perciò non

possono più essere modificati durante il duty cicle. Per fare ciò contengono una logica che

permette di calcolare la derivata del segnale di controllo, che viene usata come impulso

per la lettura e il campionamento degli ingressi.

Con i flip flop risolviamo tutti i problemi visti in precedenza. Anche il flip flop JK funziona in

modo stabile (l'unica differenza è che la retroazione delle uscite sulla AND viene

scambiata) e si possono realizzare in modo analogo anche i flip flop di tipo D e T.

Quello che finora abbiamo chiamato in modo generico segnale di controllo, è chiamato

ENABLE quando è aperiodico e CLOCK quando è periodico. Nella pratica il segnale di

controllo è quasi sempre il clock, ma non deve esserlo necessariamente.

Come ultimo argomento, prima di passare ai registri, è bene sapere che nelle board ci

sono alcuni segnali che vanno ovunque, come l'alimentazione e la massa. Uno di questi è

il segnale di RESET, utilizzato all'accensione di un dispositivo per inizializzare tutti i

segnali ad un certo valore (solitamente 0). I flip flop vengono così forniti con due ulteriori

segnali, il PRESET e il CLEAR, che forzano l'uscita del circuito scavalcando gli ingressi.

Questi comandi sono attivi bassi e soprattutto sono asincroni, collegati con il segnale di

reset che pervade tutto il chip.

Nella lezione precedente abbiamo parlato a lungo dei bistabili, che sono i blocchi costitutivi

dei circuiti sequenziali. Abbiamo visto che sono alla base dei flip flop che possono essere

di tipo SR, D, JK e T. Adesso è il momento di utilizzarli per sintetizzare e costruire delle reti

sequenziali.

Nei circuiti sequenziali abbiamo la nozione di stato, ed è proprio questo che ci fa intuire

che la sintesi inizia dalla costruzione di, indovina cosa, una macchina a stati finiti! Il

primo passo quindi è creare un automa a stati finiti in cui possiamo facilmente correlare

nodi e archi con stati e segnali di ingresso e uscita. È importante sottolineare che non

potremo MAI costruire una macchina a stati infiniti, perché dovremmo codificare infiniti bit

e ciò non è possibile. Questo ragionamento fa tornare alla mente ciò che disse

Martinenghi per cui anche i computer sono in realtà delle macchine a stati finiti, ma

essendo i bit a disposizione un numero gigantesco gli automi non sono il modello migliore

per rappresentarli.

Le macchine a stati finiti possono dividersi in due categorie: le MACCHINE DI MEALY, in

cui l'uscita dipende dallo stato e dall'ingresso, e le MACCHINE DI MOORE, dove l'uscita

dipende solo dallo stato corrente. Nel caso di Mealy quindi l'uscita si legge durante le

transizioni, cioè quando cambiamo stato. In Moore al contrario leggiamo l'uscita mentre ci

troviamo all'interno di uno stato definito. Questi modelli sono intercambiabili tra loro

semplicemente modificando la topologia del grafo. Tuttavia nella pratica si utilizza un

modello piuttosto che un altro in base a ciò che ci conviene di più per il circuito in

costruzione.

Dopo aver realizzato la macchina a stati finiti, dobbiamo convertirla nella TABELLA

DEGLI STATI, che associa ad ogni coppia stato-ingresso un nuovo stato d'arrivo. Ogni

riga della tabella è associata ad uno stato e ogni colonna ad un ingresso. Le celle

contengono lo stato d'arrivo. L'uscita invece va inserita in posti diversi in base al tipo di

macchina che abbiamo costruito. Nel caso delle macchine di Mealy, l'uscita dipende sia

dallo stato che dall'ingresso, per cui va inserita nella cella insieme allo stato d'arrivo. Per le

macchine di Moore invece, dato che l'uscita dipende solo dallo stato corrente, va inserita

in una colonna apposita. Ah dimenticavo una cosa importante: come in ogni macchina a

stati fatta bene, deve esserci uno stato iniziale da cui partire (anche dal punto di vista

pratico il circuito deve partire da qualche parte). Questo stato iniziale sarà poi associato al

comando di reset nell'implementazione finale.

Dalla tabella degli stati passiamo alla TABELLA DELLE COMMUTAZIONI. Molto

semplicemente dobbiamo trovare una codifica binaria per ogni stato e andarla a sostituire

nella tabella degli stati. Possiamo scegliere la codifica che preferiamo: le più usate sono

quella binaria naturale e la one hot. Attenzione che la scelta della codifica andrà a

influenzare sulla realizzazione fisica del circuito. Una codifica binaria naturale fa crescere il

numero di flip flop da usare con complessità logaritmica rispetto al numero degli stati,

mentre la one hot la fa crescere linearmente!

Ora arriva la parte tosta: la creazione della TABELLA DELLE ECCITAZIONI. Per

realizzarla dobbiamo scegliere il bistabile da usare, in quanto gli strumenti che ci servono

sono la tabella delle commutazioni creata in precedenza e la tabella delle eccitazioni del

bistabile scelto. Lo scopo di questo passaggio è identificare quali devono essere i segnali

in ingresso ai bistabili affinché si realizzi la transizione di stato desiderata. Farlo è un

lavoro noiosissimo: dobbiamo prendere tutte le coppie ordinate bit di stato iniziale / bit di

stato finale e osservare nella tabella delle eccitazioni del bistabile a quale configurazione

di ingresso corrisponde. Quello che troviamo dovremo metterlo nelle celle della tabella


ACQUISTATO

1 volte

PAGINE

26

PESO

614.12 KB

AUTORE

fiorixf2

PUBBLICATO

+1 anno fa


DESCRIZIONE APPUNTO

Appunti completi del corso Reti Logiche tenuto dal prof Fabio Salice al Politecnico di Milano. Argomenti trattati:
- Algebra di Boole
- Metodo di Karnaugh
- Metodo di Quine McCluskey
- Metodo di Quine McCluskey per più funzioni
- Metodi euristici
- Sintesi multilivello
- Aritmetica dei Calcolatori
- Registri e bistabili
- Sintesi sequenziale sincrona
- Ottimizzazione di reti sequenziali sincrone completamente specificate
- Ottimizzazione di reti sequenziali sincrone non completamente specificate
- Assegnamento degli stati a reti sequenziali sincrone
- Contatori
- Dispositivi programmabili


DETTAGLI
Esame: Reti Logiche
Corso di laurea: Corso di laurea in ingegneria informatica (COMO - CREMONA - MILANO)
SSD:
A.A.: 2017-2018

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher fiorixf2 di informazioni apprese con la frequenza delle lezioni di Reti Logiche e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Politecnico di Milano - Polimi o del prof Salice Fabio.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea in ingegneria informatica (como - cremona - milano)

Guida per la programmazione in C
Dispensa
Esercizi sulla programmazione in C
Esercitazione
Architettura dei calcolatori e sistemi operativi - Appunti
Appunto
Livello di linea
Appunto