Domande con risposte Progettazione sistemi digitali, prof. Gorla

Il caso migliore si ottiene quando è un quadrato perfetto, in quanto avrò una matrice quadrata e

= = √. 2√

quindi avrò che Aggiungo quindi bit.



Il caso peggiore si ottiene quando è un numero primo, in quanto avrò una matrice con una sola

+ 1

colonna o una sola riga. Aggiungo quindi bit di ridondanza.

2√ + 1.

A seconda del caso quindi, i bit di ridondanza da aggiungere variano da a

Codice di Hamming prestazioni e quanti bit servono

Il codice di Hamming, come il metodo dei bit di parità longitudinali e trasversali, riesce a rilevare al massimo

log + 1.

2 errori ed a correggerne al massimo 1, ma utilizzando meno bit di ridondanza, ovvero sempre 2

I bit di controllo vengono inseriti nelle posizioni che sono potenze di 2, mischiati coi bit di messaggio che

vengono inseriti nelle restanti posizioni.

Algebra di Boole e dimostrazioni correlate alle proprietà

Un’algebra in matematica è un insieme dotato di operazioni che godono di determinate proprietà.

L’algebra di Boole è quindi un insieme costituito da solo due elementi {0,1}, dotato di tre operazioni {+, *, ¯}

rispettivamente AND, OR e COMPLEMENTO, che gode delle proprietà commutativa, associativa,

distributiva, elemento neutro e complemento.

Tramite queste proprietà è possibile derivare ulteriori leggi:

Legge di involuzione: il doppio complemento si annulla;

Legge di idempotenza: se moltiplico o sommo un fattore per sé stesso, ottengo lo stesso fattore;

Somma:

Prodotto:

Legge dell’elemento annullatore: se moltiplico un fattore booleano per 0, il risultato sarà 0;

;

Legge di assorbimento: se sommo a sé stesso moltiplicato per qualcosa il risultato è sempre

Legge di De Morgan: se faccio la negazione di una somma ottengo il prodotto dei negati; se faccio la

negazione di un prodotto ottengo la somma dei negati.

Cosa dice il principio di dualità e perché vale

Il principio di dualità afferma che se ho una legge valida, questa legge rimarrò valida anche se scambio gli 0

con gli 1 e gli AND con gli OR (o viceversa).

Vale perché gli assiomi dell’algebra di Boole godono del principio di dualità ed essendo ogni legge

dimostrata tramite gli assiomi, ogni legge goderà del principio di dualità.

Perché la NAND è universale e passaggio a all-NAND

Le porte NAND e NOR vengono dette porte universali, ovvero avendo un circuito è possibile scriverne uno

equivalente utilizzando esclusivamente porte NAND o porte NOR.

Il COMPLEMENTO vale per idempotenza del prodotto:

L’AND vale per involuzione:

L’OR vale per involuzione e per De Morgan:

Le dimostrazioni per le porte NOR sono le duali di quelle per le porte NAND

Dimostrare che la XOR è associativa ( ⊕ ) ⊕ = ⊕ ( ⊕ ),

Per dimostrare l’associatività dello XOR, ovvero che basta sviluppare

⊕ = ⋅ ¯ + ⋅ ¯

enntrambi i membri ricordando la definizione di XOR e vedere che sono

equivalenti.

Quando due espressioni booleani sono equivalenti?

Quando a stessi assegnamenti delle variabili corrispondono stessi risultati. Questo è dimostrabile o tramite

gli assiomi dell’algebra di Boole, o tramite induzione perfetta (tramite le tavole di verità provo tutti i

possibili assegnamenti di variabili e vedo se gli output sono uguali).

Cos’è una forma canonica ed una forma normale

Esistono due tipi di forma canonica:

 Disgiuntiva: la somma di mintermini (prodotto di letterali il cui valore vale 1 solo per una

determinata sequenza di assegnazione) che sono implicanti della funzione, ovvero mintermine = 1

implica funzione = 1.

 Congiuntiva: il prodotto di maxtermini (somma di letterali il cui valore vale 0 solo per una

determinata sequenza di assegnazione) che sono implicanti della funzione, ovvero maxtermine = 0

implica funzione = 0.

Una forma normale è invece una funzione espressa tramite somma di prodotti di letterali (in caso di FND) o

prodotto di somma di letterali (in caso di FNC) che però non sono mintermini o maxtermini, ovvero più

sequenze di input tornano un 1. Sono comunque implicanti della funzione.

Comparatore aritmetico

Il circuito è formato da celle elementari, le quali prendono in input due bit e tornano in output un segnale

se i due bit sono uguali; se il bit della prima stringa è maggiore del bit della seconda. Questi bit

= >

andranno in input alla seconda cella elementare che prenderò in input i secondi bit meno significativi delle

stringhe. Il procedimento viene iterato fino al bit più significativo.

Il segnale è uguale al NOR tra e .

< = > La cella elementare ha la seguente tavola di verità.

 >′

=′

= :

In caso e rimangono uguali a e .

= >

 >′

=′

< :

In caso vale 1 e vale 0

 >′

=′

> :

In caso vale 0 e vale 1



In caso e valgono entrambi 1, i risultati sono dei don’t

= >

care

Sommatore, opposto e sottrazione

L’idea per il sommatore è quella di operare come una normale somma, ovvero sommare i bit meno

significativi generando un bit meno significativo ed un eventuale riporto.

La prima cella è un half-adder, il quale prende in input due bit e torna come risultato la somma dei due bit

ed un eventuale riporto.

− 1

Le altre celle sono dei full-adder, i quali prendono in input l’eventuale riporto e i due bit, tornando la

loro somma ed un ulteriore riporto.

In caso si verifica un riporto sull’ultima cella si ha un overflow.

Si può realizzare anche un progetto più uniforme utilizzando tutti full-adder ed impostando il riporto della

cella meno significativa a 0.

Per fare l’opposto basta sommare il NOT bit a bit del numero da negare con la stringa 0…01 (un 1 come bit

meno significativo). − = + (−)

Per fare la sottrazione basta sommare il primo numero con l’opposto del secondo

Composizione interna di Mux e Demux (in senso stretto e generalizzato)

Un MUX in senso stretto è un circuito formato da n linee dati ed n linee di

controllo in ingresso di cui al più una vale 1. L’output è una linea che prende il

valore della linea dati i-esima se l’i-esima linea dati di controllo vale 1.

log

Un MUX generalizzato è una rete combinatoria con ingressi, un’uscita e 2

-esima

segnali di controllo. Sulla linea di uscita viene riportata la linea di entrata

.

se la composizione dei bit di controllo vista come numero naturale vale

La composizione interna è formata da un decodificatore che prende in input le linee di controllo e le cui

uscite sono in AND con gli input del MUX.

Un DEMUX in senso stretto è l’opposto del MUX, ovvero un circuito che prende in

input una linea dati ed n linee di controllo di cui al massimo una vale 1. In uscita ha

linee di cui la i-esima prende il valore della linea dati se l’-esima linea di controllo

vale 1.

Un DEMUX generalizzato è formato da un decodificatore che prende in input i

log segnali di controllo i cui output vanno in ingresso ad un DEMUX in senso

2

stretto, ovvero in AND con la linea di ingresso.

Il circuito riporta l’ingresso sull’-esima linea d’uscita dove è la composizione dei bit di controllo vista

come numero naturale.

Disegnare ROM e spiegarla a parole

Una ROM (read only memory) è un circuito ad ingressi (linee di

indirizzamento) ed uscite (linee dati). È la composizione di un

decodificatore e un codificatore generalizzato, ovvero una matrice

di AND le cui entrate sono linee di indirizzamento e le cui uscite

sono le entrate di una matrice di OR le cui uscite sono le linee dati.

Una ROM può essere utilizzata per rappresentare un insieme di

funzioni booleane dove la matrice di AND (ovvero il decodificatore)

rappresenta la parte destra della tavola di verità, ogni riga della

matrice di OR rappresenta una funzione. La matrice di OR è

programmabile inserendo un “diodo” in corrispondenza di ogni 1

presente sulla riga i-esima della TV

Essendo la matrice di AND sempre uguale, si disegna lasciando implicito il modulo del decodificatore.

Com'è realizzato un Decodificatore

Un decodificatore è un dispositivo dotato di linee di

2 -esima

ingresso e linee di uscita. La linea di uscita vale

.

1 quando la codifica binaria della linea di ingresso vale

Il circuito può essere espresso tramite uno schema

denominato matrice di AND.

Com’è realizzato un Codificatore

Un codificatore è un dispositivo dotato di linee di ingresso (di cui

log

solo una alla volta vale 1) e linee di uscita. Le linee di uscita

2

prendono il valore della codifica binaria della linea di ingresso che

vale 1.

Il circuito può essere espresso tramite uno schema denominato

matrice di OR.

Cos’è un PLA

Un PLA è simile ad una ROM ed è formata da ingressi, m uscite e tre stadi interni: uno stadio di inversione

dei segnali di ingresso, una matrice di AND ed una matrice di OR.

Un PLA viene venduto con tutti gli ingressi n affermati e negati e con gli ingressi alle porte AND e OR non

cablati, in quanto è programmabile.

I collegamenti sono formulati in termini di funzioni in Forma Normale Disgiuntiva. Il processo è quindi più

laborioso rispetto a quello di una ROM in quanto vanno manualmente calcolate le FND per ognuna delle m

FB.

Differenza tra ROM e PLA (che espressioni booleane calcolano)

La differenza principale tra la ROM e il PLA è il fatto che il PLA ha sia la matrice di AND sia la matrice di OR

entrambe programmabili, ovvero viene venduto con gli ingressi alle porte AND e alle porte OR non cablati.

Il PLA anche rappresenta funzioni booleane, solo che i collegamenti sono formulati in termini di funzioni

in Forma Normale Disgiuntiva, e non in forma Canonica come avviene per la ROM.

Questo riduce il numero di collegamenti da effettuare ma rende il lavoro più laborioso in quanto c’è il

bisogno di calcolare a mano le forme normali minime di ogni funzione.

I vari tipi di latch

Latch SR: è in grado di memorizzare un 1 (set), di memorizzare uno 0 (reset) e di mantenere il bit

memorizzato (hold).

Latch D: risolve il problema della configurazione non determinata SR=11 facendo in modo che S ed R siano

semp