Paniere Calcolatori e sistemi operativi - domande aperte

7. Lezione

Descrivere una rete logica a livello funzionale.

Una rete logica è caratterizzata da:

(2 )

- Un insieme di N variabili in ingresso, l’insieme dei valori assunti si chiama stato di ingresso. -

(2 )

Un insieme di M variabili in uscita, l’insieme dei valori assunti si chiama stato di uscita.

Inoltre, una rete logica è caratterizzata da una legge di evoluzione nel tempo che descrive come

le uscite evolvono in funzione degli ingressi.

Come si classificano le reti logiche?

Le reti logiche si classificano:

- In base alla presenza/assenza di memoria

o Reti combinatorie, lo stato di uscita dipende solo dallo stato di ingresso

o Reti sequenziali, lo stato di uscita dipende anche dalla storia degli stati di ingresso

precedenti

- In base alla temporizzazione della legge di evoluzione

o Reti asincrone, lo stato di uscita varia al variare dello stato di ingresso

o Reti sincrone, lo stato di uscita varia al variare dello stato di ingresso on momenti separati

nel tempo

Quale è la differenza fra reti sincrone e asincrone?

Le reti asincrone aggiornano continuamente lo stato di uscita ad ogni variazione dello stato di

ingresso, quelle sincronizzate aggiornano lo stato di uscita in momenti separati nel tempo.

Cosa è la fascia di indeterminazione del segnale?

La fascia di indeterminazione del segnale è quella fascia di tempo necessaria al modello fisico per

passare da una tensione alta ad una bassa o viceversa. Il modello astratto prevede che una variabile

cambi istantaneamente.

Cosa significa settare e resettare una variabile logica? 0

Settare una variabile logica significa effettuare la transizione a 1, viceversa si resetta quando transisce a

Descrivere il problema della contemporaneità.

Non si può garantire che due grandezze fisiche varino contemporaneamente. Se, quindi, si basa un

ragionamento sull’ipotesi che due variabili di ingresso varino contemporaneamente, poi non si potrà mai

costruire un sistema fisico che verifichi questa ipotesi. Pertanto, bisogna evitare di supporre che due variabili

di ingresso varino contemporaneamente. Non è possibile che in una realizzazione fisica di un sistema si

presentino in sequenza due stati di ingresso che differiscono tra loro per più di un bit. Se prima dell’istante t1

è presente lo stato di ingresso (10), e dopo è presente lo stato di ingresso (01), vuol dire necessariamente

che, per un certo intervallo di tempo, la rete ha visto in ingresso uno stato di ingresso intermedio (11 o 00).

Dovremo preoccuparci del fatto che gli stati di ingresso siano vincolati a cambiare un bit alla volta. In altre

parole si dovrà sempre supporre che stati di ingresso consecutivi siano adiacenti

8. Lezione

Cosa si intende per tempo di attraversamento?

Il tempo di attraversamento è il tempo che intercorre tra quando l’ingresso cambia stato e l’istante in

cui l’uscita cambia stato in accordo alla legge che regola la rete.

Quando una rete combinatoria si dice a regime?

La rete logica si dice a regime dopo il tempo di attraversamento, quando cioè l’uscita ha variato lo stato

in accordo all’ingresso

Cosa significa rete combinatoria pilotata in modo fondamentale?

La rete è pilotata in modo fondamentale quando ad ogni cambiamento in ingresso c’è il corrispettivo

cambiamento in uscita. La rete che riesce ad andare a regime per ogni cambiamento dello stato di

ingresso si dice pilotata in modo fondamentale.

9. Lezione

Dimostrare (tramite un opportuno esempio) che connettendo ad albero porte NAND

(oppure NOR) a due ingressi non si ottiene una generalizzazione della funzione logica

descritta per porte a due ingressi

Tramite la tabella della verità si può osservare che la connessione delle tabelle a due ingressi fornisce

un risultato diverso della funzione a 4 ingressi che sarebbe esattamente l’opposto.

z

0 0 1 0 0 1 1 1 0

0 1 0 0 1 0 0 0 1

1 0 0 1 0 0 0 0 1

1 1 0 1 1 0 0 0 1

Descrizione funzionale e tabella di verità di una porta logica elementare Or:

Si effettua su due o più variabili, l’uscita assume lo stato logico 1 se almeno una variabile di ingresso è allo stato logico 1. Nel

caso di due variabili di ingresso A e B, detta Y la variabile di uscita, si scrive: Y = A + B e si legge A or B.

Descrizione funzionale e tabella di verità di una porta logica elementare Nand:

Si effettua su due o più variabili, l’uscita assume lo stato logico 0 se tutte le variabili di ingresso sono allo stato logico 1. In tutti

gli altri casi Y=1. Corrisponde ad una AND con in cascata una NOT. La funzione logica si scrive: Y = A·B e si legge A nand B.

Descrizione funzionale e tabella di verità di una porta logica elementare XOR:

La funzione logica XOR fornisce un'uscita "vera" solo quando i due ingressi presentano le condizioni logiche opposte. Analogamente,

una porta logica XOR fornisce un livello logico "1" solo quando i due ingressi presentano livelli logici opposti.

PORTA OR: PORTA NAND: PORTA XOR:

A B Y A B Y A B Y

0 0 0 0 0 1 0 0 0

0 1 1 0 1 1 0 1 1

1 0 1 1 0 1 1 0 1

1 1 1 1 1 0 1 1 0

10. Lezione

Definizione e sintesi circuitale di un decoder 2 to 4 ingresso.

Ogni uscita riconosce uno ed un solo stato di

0 1 0 1 2 3 In particolare l’uscita J-esima riconosce lo stato di

0 0 1 0 0 0 ingresso i cui bit sono la codifica di j in base 2.

0 1 0 1 0 0

1 0 0 0 1 0

1 1 0 0 0 1

Che differenza c'è fra un decoder con enabler e un demultiplexer?

Nessuna differenza, si tratta di due modi diversi di chiamare la stessa rete.

Cosa significa che un multiplexer è una rete combinatoria universale?

Un multiplexer si realizza con porte AND,

2 1 0 OR e NOT ed è una rete a 2 livelli di logica,

0 0 0 0 0

1 0 0 1 1 può realizzare una qualunque rete combinatoria

2 0 1 0 0 ad una uscita e può essere messo in parallelo

3 0 1 1 0 per realizzare una rete combinatoria a più

4 1 0 0 1 motivi il multiplexer è una

uscite. Per questi

5 1 0 1 1 rete combinatoria universale.

6 1 1 0 1

7 1 1 1 0

11. Lezione

Cosa sono i sottocubi?

I sottocubi sono raggruppamenti di celle adiacenti all’interno di una mappa di Karnaugh. I

raggruppamenti devono essere considerati sempre per potenze del 2.

12. Lezione

Perché porte NAND e NOR sono dette universali?

Ogni funzione logica può essere rappresentata con sole porte NAND (oppure con sole porte NOR).

Esempio di sintesi a porte NAND (NOR) da sintesi SP (PS).

Per trasformare a porte NAND una rete logica SP (Somme di Prodotti) si eseguono i seguenti passaggi:

- Trasformazione delle AND in NAND (utilizziamo il teorema di idempotenza sulla complementazione)

- Applicazione di una delle leggi di De Morgan per trasformare gli OR in NAND

Per trasformare a porte NOR una rete logica PS (Prodotti di Somme) si eseguono i seguenti passaggi:

- Trasformazione delle OR in NOR (idempotenza sulla complementazione)

- Applicazione della seconda legge di De Morgan per trasformare le AND in NOR

Differenza fra sintesi SP e PS

Dal punto di vista algebrico una espressione a porte NAND si ottiene partendo da una SP (somma di

prodotti) complementandola 2 volte (idempotenza) ed applicando De Morgan una volta.

L’espressione a porte NOR si ottiene partendo da una PS (prodotto di somme) complementandola 2

volte (idempotenza) per sostituire le OR in NOR ed applicando la seconda legge di De Morgan per

trasformare le AND in NOR.

13. Lezione

Cosa si intende per stabilità di una rete sequenziale asincrona?

Si dice che una rete sequenziale asincrona è stabile quando non evolve, quando cioè non cambia stato

per un certo ingresso (arco ad orecchio nel grafo di flusso o cerchio intorno allo stato stabile nella tabella

di flusso).

Disegnare il diagramma di temporizzazione del flip-flop SR.

Si nota che la rete evolve in

uscita con un certo ritardo

rispetto al cambio dei valori in

ingresso. Questo dipende, oltre

che dai tempi di

attraversamento, dalla legge di

evoluzione che andrà

implementata e che introdurrà

comunque un ritardo.

Descrivere un riconoscitore di sequenza con il suo diagramma (oppure tabella) di flusso.

Un riconoscitore di sequenza è una rete che ha N ingressi (in questo caso N=2, sequenze di 2 bit), ed

una uscita, la legge di evoluzione è: L’uscita è ad 1 quando si presenta la sequenza di ingresso

desiderata (01, 11, 10), rimane a 0 altrimenti.

14. Lezione

Descrivere il modello strutturale con ritardo per la sintesi delle reti sequenziali asincrone

(Schema grafico e discussione di ciascun componente)

La legge B può essere impostata con una rete

combinatoria con W ingressi ed M uscite, la legge

A con una rete combinatoria di N+W ingressi e W

uscite. Nel mezzo un meccanismo di marcatura

che per il momento consideriamo come un

le variabili

ritardo. Codifichiamo differentemente

che codificano:

, … ,

Lo stato interno presente

- 0 −1

, … ,

- Lo stato interno da marcare (che diventa stato presente dopo un ritardo pari a delta).

0 −1

Sintesi completa di un riconoscitore di sequenza 01, 11, 10

Per sintetizzare un riconoscitore di

sequenza è necessario un percorso

di ordine 4, vanno codificati 4 stati

interni in modo adiacente. Si

supponga di utilizzare S0=00, S1=01,

S2=11, S3=10 che ci permette di

rispettare la regola che vuole stati

adiacenti che differiscono di un solo bit. È ben visibile il salto necessario per il passaggio dallo stato S3

allo stato S0.

15. Lezione

Sintetizzare un FF-SR considerando il modello strutturale ad elementi di ritardo (considerare la presenza

dell'uscita affermata e negata).

Le versioni commerciali del FF-SR offrono in uscita anche la variabile negata. È realizzato con

elementi neutri di ritardo come meccanismo di marcatura nel modo seguente:

- La rete CN2 è un corto circuito

- Si codificano gli stati interni a 2 bit con valore alle uscite: S0=01,

S1=10

la codifica a 2 bit è ridondate e crea problemi di corse tra le variabili di stato ma la sua sintesi

risulta semplice e produce una rete molto veloce e robusta. Per gli stati non adiacenti è necessario

guidare le corse con uno stato ponte, le transizioni S0-S1 e S1-S0 passeranno per lo stato ponte.

Disegnare la sintesi a porte NAND del FF-SR. Si possono eliminare i ritardi di marcatura? Perché’?

stato non rientrano in

Si possono eliminare i ritardi di marcatura perché le variabili di

zone interessate a transizioni di ingresso. Infatti se cambia s, q rientra sull’altra NAND,

che è a regime. Dato che non servono i ritatrdi, la rete è più veloce.

Temporizzazione del FF D-latch. l'ultimo valore di d prima che

Per memorizzare correttamente

passi da 1 a 0, occorre che il valore di d rimanga costante per

qualche tempo prima (T ) e per qualche tempo dopo (T ) il

setup hold

verificarsi dell'evento.

16. Lezione

Sintesi del riconoscitore di sequenza 01 11 10 usando il modello strutturale con FF-SR.

Utilizziamo la tabella degli stati

interni accanto, la tabella delle

transizioni non descrive più le uscite

di CN1 ma specifica se il nuovo

valore delle variabili di stato 1 0

(quello che si legge dentro la cella) è

o meno al vecchio (che si

uguale

legge sulla riga corrispondente).

Sintesi del FF D-latch usando il modello strutturale con FF-SR.

Il FF D-latch memorizza l’ingresso d quando p=1.

Quando p=0 conserva l’informazione

memorizzata. A fianco la tabella di flusso. Le

di p

regole ilotaggio stabiliscono che si debba

tenere costante d a cavallo della transizione di p

da 1 a 0. I tempi in cui deve essere costante sono

servono a garantire che la rete

e

ℎ

non veda transizioni multiple di ingresso e che si

stabilizzi in modo prevedibile.

Sintesi del Flip Flop D-positive-edge-triggered (FF-DET) usando il modello strutturale con FF-SR

Si realizza con due sottoreti: la prima è il campionatore sul fronte di salita di p, la seconda è un FF-SR

> .

che seve ad inserire il ritardo e garantire che l’uscita sia aggiornata solo dopo ℎ

- La rete campionatore dovrà conservare il valore campionato sul fronte di salita. Sarà essa a pilotare

il FF-SR con comandi di conservazione, set e reset. Si sintetizza come una rete

sequenziale asincrona a tre stati interni. - S0: per p=0 la rete è in conservazione,

l’uscita del campionatore vale 00, non è

sensibile a d; quando p va ad 1 può

succedere di resettare il ritardatore (se

d=0) o settarlo (se d=1). Visto che le

uscite del campionatore sono diverse si

devono prevedere 2 stati interni distinti,

S1 ed S2

per settare o resettare il ritardatore.

- S1: si arriva se d=0 quando p transita a 1. Si ordina al ritardatore di resettare e si rimane in S1. In

S1 la rete deve essere stabile, non ascolta d. Unica transizione di stato se p transita a 0 si torna a S0 in

attesa di un nuovo fronte di salita di p.

- S2: come S1 con l’unica differenza nel comando al ritardatore che viene settato con 10 in

ingresso.

17. Lezione

Disegnare lo schema realizzativo di una RAM con D latch.

Una RAM statica è una matrice di D-Latch. Una riga è una locazione con bit 0 a destra e bit 3 a sinistra.

Per la lettura, le uscite dei D-Latch devono essere selezionate da un multiplexer in cui gli ingressi sono le

uscite del D-Latch e le variabili di comando sono i fili di indirizzo. Le uscite sono bloccate da porte tri-state

che saranno abilitate quando si sta leggendo dalla memoria (per la gestione si utilizza la rete combinatoria

“C” come funzione di /s, /mr, /mw).

Per la scrittura, ciascuna riga, avrà l’ingresso p prodotto da un demultiplexer comandato dai fili di

indirizzo, in questo modo commuterà la scrittura sulla riga giusta ed anche se i fili dati sono in ingresso a

tutti i D-Latch soltanto una riga li sentirà. Il comando di scrittura è prodotto dalla rete combinatoria “C”

come funzione di /s, /mr, /mw).

Montaggio di una RAM in serie. Spiegare anche a cosa serve?

Il montaggio in serie serve per raddoppiare il numero di locazioni mantenendo fissa la loro dimensione.

Per poter indirizzare banchi da 256Kx8 usando banchi da 128Kx8, è necessario avere un filo di indirizzi in

più che, attraverso il valore trasportato, indirizza alla “parte alta” o alla “parte bassa”, generando un

).

segnale di select per i due blocchi (si combinano /s e Tutto il resto dei fili è portato in parallelo sui

17

due blocchi.

Montaggio di una RAM in parallelo. Spiegare anche a cosa serve?

Montare le RAM in parallelo, significa raddoppiare la dimensione della memoria. Per ottenere un il

montaggio basta collegare i fili in parallelo, soltanto i bus dati sono affiancati per costituire

l’informazione completa; i dati utilizzeranno lo stesso indirizzo.

18. Lezione

Differenze fra le reti sequenziali asincrone e quelle sincronizzate

Le reti sequenziali asincrone campionano continuamente gli ingressi e forniscono gli stati in uscita con il

solo ritardo di attraversamento. Le reti sequenziali sincronizzate campionano lo stato di ingresso all’arrivo

del clock e non ha alcuna importanza di cosa succeda tra due clock. Le RSS evolvono sul fronte di risalita

del clock e non quando cambiano gli ingressi.

Definizione di rete sequenziale sincronizzata e principali regole di progetto (cosa si può fare e

cosa non si può fare nella realizzazione di tali reti).

Si definisce rete sequenziale sincronizzata, una collezione di registri e reti combinatorie montati in

qualsiasi modo. È fondamentale che non ci siano anelli di reti combinatorie (formerebbero una RSA) e che

i registri abbiano tutti lo stesso clock.

Disegnare lo schema generale di una rete sequenziale sincronizzata e discutere le regole di

pilotaggio Il clock deve permettere di produrre un nuovo stato di ingresso

attraverso le reti combinatorie e di farlo arrivare, attraverso le

reti combinatorie, in ingresso ai registri.

Temporizzazione di una generica rete sequenziale sincronizzata (con spiegazione dei tempi

considerati).

Si definiscono i seguenti ritardi:

 : il tempo di attraversamento della più lunga catena fatta di sole reti combinatorie

−−−

che si trovi tra una variabile di ingresso della rete fino all’ingresso di un registro

 : il tempo di attraversamento della più lunga catena fatta di sole reti combinatorie

−−−

che si trovi tra l’uscita di un registro e l’ingresso di un registro

 : il tempo di attraversamento della più lunga catena fatta di sole reti combinatorie

−−−

che si trovi tra una variabile di ingresso della rete ed una variabile di uscita della rete

 : il tempo di attraversamento della più lunga catena fatta di sole reti combinatorie

−−−

che si trovi tra l’uscita di un registro ed una variabile di uscita della rete

19. Lezione

Disegnare un registro contatore Si può realizzare un contatore up con un

modulo sommatore ed un registro. Il

sommatore sarà una rete combinatoria in

base β capace di sommare due numeri a N

cifre. Visto che si incrementa sempre di

uno, è possibile mantenere uno degli

ingressi a 0 ed il riporto entrante uguale ad

1. Il numero W degli elementi del registro è

uguale a N*NumeroBitCodificaDiUnaCifra

Sintesi del full adder in base 2

Il full adder in base 2 è un c