Esercizi sull'algebra Booleana, le mappe di Karnaugh ed i
Circuiti Combinatori e Sequenziali
PARTE 1
Tra un esercizio ed un'altro, potrebbe essere interessante andare a
leggersi questa
breve biografia di Boole.
e
Breve biografia di De Morgan. Esercizio 1
Descrivere il circuito minimo a due livelli (AND-OR) che calcoli
la seguente funzione booleana in 4 variabili (x' indica (NOT x)):
Dopo aver dato la definizione di implicante primo e di implicante
ridondante in un insieme,
prendere la mappa qui a lato e
dimostrare che l'implicante
primo C e' ridondante nell'insieme {A, B, C}
(utilizzare il teorema del
consenso: xy + x'z + yz = xy + x'z).
Esercizio 6
Presa la funzione f(a,b,c,d) il cui valore e' 1
quando il numero rappresentato in binario da abcd e' primo o divisibile per 3:
determinare la tavola di verita' di f
determinare una espressione minimale per f come somma di prodotti
modificare due (e solo due) valori di f in modo che la nuova
funzione sia esprimibile come somma di sue soli prodotti
(e' possibile fornire due differenti coppie di modifiche)
(ricordare che 1 non e' primo e 0 non e' divisibile per 3)
Esercizio 7
Dimostrare che per ogni espressione algebrica booleana ne esiste una equivalente
(che rappresenta la stessa funzione) e che utilizza solo gli operatori NOR o NAN
D.
Sintetizzare un circuito sequenziale sincrono che realizzi la funzionalita'
di blocco tastiera in un telefonino, supponendo che la tastiera
si blocchi premendo il tasto "#" e si sblocchi premendo contemporaneamente i tasti "*" e "#".
Sintetizzare (descrivendo tutti i passi di sintesi, per quanto
possano essere semplici)
un circuito sequenziale che prenda in ingresso una sequenza
di caratteri "a" e "b" ed invii un segnale 1 ogni volta che nella sequenza
compare un carattere "b" che si trova in posizione pari dentro una
sottosequenza formata da soli "b".
Esempio:
-Input: aabbaaabbbbbaba....
Output: 000100001010000.....
N.B.: i circuiti combinatori della rete devono essere sintetizzati
utilizzando il procedimento per ottenere forme SP minimali.
Esercizio 10
In casa avete lo
scaldabagno e la lavatrice, ma a causa di un impianto difettoso, non potete
utilizzarli contemporaneamente. Sintetizzare
(descrivendo tutti i passi di sintesi, per quanto possano essere semplici) un circuito sequenziale che,
opportunamente collegato agli interruttori di tali elettrodomestici, impedisca
di utilizzarli entrambi nello stesso momento (se la lavatrice e' accesa allora
accendere lo scaldabagno non ha alcun effetto e viceversa; non ha alcun effetto
anche accendere contemporaneamente tutti e due).
N.B.: i circuiti combinatori della rete devono essere sintetizzati utilizzando il procedimento per ottenere forme SP
minimali.
Fornire almeno sei rappresentazioni (esplicite o implicite: che rappresentino
solo il comportamento oppure come la funzione viane calcolata) per la
funzione booleana di tre argomenti (a, b, c) che restituisca 0
se e solo se (b=c=0 oppure a=b=1).
Perche' per sintetizzare una rete combinatoria a 5 variabili non
e' possibile utilizzare una mappa di carnaugh bidimensionale con
4 colonne ed 8 righe ?
Prendete una mappa di carnaugh a 4 variabili che contenga due implicanti
contigui, il primo rappresentato da un rettangolo con 4 "uni" ed uno
rappresentato da un rettangolo con 2 "uni". Perche' nel processo di sintesi
delle espressioni SP minimali questi due rettangoli non vengono "fusi" insieme?
Disegnare un circuito minimale con 4 morsetti in ingresso
ed uno in uscita che calcoli la funzione booleana di quattro variabili
rappresentata da una mappa di Carnaugh formata da soli "0". Fare lo stesso
nel caso la mappa sia formata da soli "1".
Supponete che, per motivazioni a noi oscure, si possano scegliere
due configurazioni di ingresso a piacere che non si potranno mai presentare.
Scegliere tali configurazioni in modo che il circuito SP sintetizzato
dalla mappa risulti il piu' semplice possibile.
Soluzione. (By L. Di Odoardo, M.Firrincieli, E. Rizzo)
Esercizio 26bis
Non scordatevi di fare anche gli esercizi (quelli per cui abbiamo gli
strumenti per farli) proposti dal Luccio-Pagli. In particolare,
fate gli esercizi proposti in sezione 2.11 e 3.11.
Tenete presente che in questi quiz al posto di "X" per indicare
il valore non specifucato su una mappa, si utilizza "d". Inoltre anziche'
utilizzare "PS"("SP") si utilizza "POS"("SOP")
Ideare un circuito a cinque ingressi che restituisca in output la codifica binaria della radice quadrata arrotondata per difetto del
numero binario inserito come input.
Costruire un "sottrattore parallelo" per numeri naturali rappresentati
in binario (esercizio 3.7 del Luccio-Pagli).
Il sottrattore deve ralizzare il classico algoritmo della sottrazione
cifra per cifra con eventuali "prestiti".
Tra i problemi per la progettazione delle reti sequenziali asincrone c'e'
anche quello che le alee potrebbero provocare la transizione su stati
interni non desiderati. Fare un semplice esempio di circuito asincrono
in cui un'alea statica puo' provocare danni.
Esercizio 31
Un comparatore e' un circuito combinatorio che prende in input due
stringhe binarie e ritorna 1 se e solo se le due stringhe sono uguali.
Sintetizzare un comparatore per stringhe lunghe due con il metodo delle
mappe di Karnaugh. Sintetizzarlo a mano e con meno blocchi supponendo di
avere a disposizione il blocco logico XOR ( aXORb=1 <=> (aORb)AND(a=b-) ).
Senza utilizzare il processo di sintesi per reti sequenziali sincrone,
descriverne una che conta il numero di cicli di clock trascorsi modulo
32. Per noi il clock e' un segnale implusivo per la rete.
Dare una risposta formale del perche' non e' possibile avere
una rete asincrona che fa la stessa cosa.
Ho una rete sequenziale sincrona in cui la parte combinatoria
e' realizzata a due livelli. Un segnale per attraversare una
porta logica impiega 2 nanosecondi.
La sincronizzazione della rete avviene con un clock
inviato ad un latch Fc. La durata dell'impulso e' di 6 nanosecondi.
Puo' funzionare questa rete? In quale caso?
Sintetizzare una rete sequenziale sincrona che controlli
un parcheggio con due posti macchina dotato di una sbarra al suo
ingresso ed un'uscita (sempre aperta) diversa dall'ingresso.
Ci sono anche delle cellule fotoelettriche all'ingresso ed all'uscita del
parcheggio che permettono di sapere se una
macchina ha attraversato un passaggio.
Per far si che si invii un segnale corretto al circuito dell'esercizio 36
che indichi quando una macchina e' entrata e per evitare
che il passaggio di un pedone o un cane venga interpretato come il
passaggio di una macchina, sintetizzare un circuito sequenziale
che riceva in input dei segnali provenienti da due fotocellule
appaiate. Tali fotocellule sono ad una distanza tale che possono
venire interrotte entrambe solo da una macchina, mentre una persona o un cane
non son potranno mai farlo. Il circuito sequenziale inviera' il segnale
di "macchina entrata" solo quando una macchina avra' passato le due fotocellule.
Altra soluzione(piu' corretta
della precedente?) (by Luigi Santangelo)
Esercizio 38
Sintetizzare una rete sequenziale con un bit in ingresso ed uno in uscita.
Negli istanti 4k, 4k+1, 4k+2 e 4k+3 (k=0,1,2,...) il segnale di uscita
e' uguale al segnale di ingresso della reta all'istante 4k.
Ovviamente la sistesi va eseguita seguendo i passi del procedimento
descritto nel testo.
Prendete l'esercizio 5.2 del Luccio-Pagli. Sintetizzare il circuito in
modo che la risposta nei primi tre istanti delle sequenze di quattro
sia non specificata nella descrizione dell'automa.
Aggiungere poi all'uscita della rete la
rete sintetizzata nell'esercizio 38, per far si che
l'output al termine di una sequenza di quattro rimanga sicuramente stabile
per i 3 istanti successivi.
Le due reti vanno sincronizzate con lo stesso clock?
Se colleghiamo l'output della prima direttamente con l'input della
seconda, a che tipo di problemi andiamo incontro?
Se tra l'output della prima e l'input della seconda inseriamo
un latch (sincronizzato con quale clock?), a che problema andiamo incontro? Come lo risolviamo?
Esercizio 40
Utilizzando la metodologia descritta nel Luccio-Pagli,
minimizzare l'automa descritto nella Figura 5.6 del testo.
