Esercizi sull'algebra Booleana, le mappe di Karnaugh ed i
Circuiti Combinatori e Sequenziali
PARTE 2
Esercizio 41
Supponimo di avere una classe C di automi a stati finiti.
Per tutti gli automi di C, quando costruiamo la tabella a scala
nel processo di minimizzazione, il numero di croci iniziali e' w.
Qual'e' il valore di w affinche' la complessita' del processo
di minimizzazione per gli automi appartenenti a C sia O(k2p) ?
(w puo' anche essere una funzione di k e p)
Esercizio 42
Descrivere un automa a stati finito non minimo con 8 stati
tali che partizionandoli rispetto la relazione di equivalenza tra
stati, ci siano tre classi di equivalenza, due con tre elementi ed
una con due.
Soluzione.
(By R.Ferraro and S. Fede)
Esercizio 43
Dimostrare che la rete sintetizzata a partire da
un automa a stati finiti (completamente specificato),
tale che la tabella a scala prodotta all'inizio del
procedimento di minimizzazione non contenga alcuna croce,
calcola una(un insieme di) funzione(i) booleana(e).
Soluzione.
(By R.Ferraro and S. Fede)
Esercizio 44
(a) Dare la definizione di insieme irridondante di implicanti
di una funzione.
(b)
In casa avete un sistema di cellule fotoelettriche che invia un segnale che
indica se siete in casa o no; inoltre indica anche se siete in bagno o no.
Progettare un circuito che invii un segnale di accensione o
spegnimento alla segreteria telefonica. La segreteria va accesa se siete
fuori casa e spenta se siete dentro. Inoltre quando siete in casa deve
accendersi quando siete in bagno.
Descrivere tutti i passi utilizzati nella sintesi della rete per quanto possano essere semplici.
(a) Fornire la definizione di Implicante.
(b)
Avete organizzato una mostra su "I transistor". Il materiale e' esposto in tre sezioni:
Sezione 1: i transistor medioevali -- Sezione 2: i transistor nel rinascimento --
Sezione 3: i transistor nella Germania dell'800.
Per far seguire un ordine nella visita del materiale della mostra, all'ingresso
mettete un cartello che spiega che la Sezione 2 si puo' visitare solo se si e' appena
visitata la Sezione 1 o la Sezione 3
e che la Sezione 3 si puo' visitare solo se si e' appena visitata la Sezione 2.
Si puo' uscire dalla mostra quando si vuole.
Per dare a tutti la tranquillita' necessaria per meditare sulle meraviglie della mostra,
supponiamo che questa sia visitata da un unico
visitatore alla volta (sara' il portiere a preoccuparsi che questo vincolo sia soddisfatto).
Per esser sicuri che i visitatori seguano strettamente quel che avete scritto nel cartello,
mettete
un sistema di cellule fotoelettriche che invia le seguenti informazioni:
- Il visitatore e' nella Sezione1
- Il visitatore e' in Sezione2
- Il visitatore e' in Sezione3
- Non c'e' alcun visitatore
Utilizzando le informazioni che arrivano dal sistema di fotocellule volete costruire
una rete sequenziale sincrona che con il suo output controlli l'accensione di un altoparlante che
diffonde la seguente registrazione: "Ignorantone! non hai letto il cartello all'ingresso?!?".
La registrazione andra' diffusa non appena il visitarore non rispetta le indicazioni del cartello.
Verra' interrotta non appena il visitatore ricomincia corretamente il giro oppure esce.
Sintetizzare la rete sequenziale, utilizzando un circuito SP minimale per la sua parte combinatoria,
mostrando tutti i passaggi del processo di sintesi.
L'automa a stati finiti utilizzato nella sintesi deve essere minimo.
Nel caso si riesca a descrivere direttamente un automa minimo, applicare su di esso comunque
il procedimento di minimizzazione per dimostrare la sua minimalita'.
Si suppone che il passaggio da una sezione all'altra della mostra avvenga istantaneamente
(senza passaggi intermedi, per intenderci) e che non esistano vincoli fisici che impediscano
agli ignorantoni di spostarsi tra tutte le varie sezioni contravvenendo alle disposizioni del cartello.
Una funzione booleana si puo' vedere come una proposizione logica?
questo vale anche per un implicante p di f?
Come interpretare dunque in quest'ottica la notazione p -> f ?
Sintetizzare un circuito combinatorio che prenda in input un numero
naturale tra 0 e 15 codificato in binario con 4 bit e restituisca
la sua codifica utilizzando come codice il codice di Hamming a correzione
di 1 errore descritto nella figura 2-14 del Tanenbaum.
Sintetizzare un circuito combinatorio che fornisca la decodifica
(correggendo l'eventuale errore) di un numero tra 0 e 15 codificato
con il codice di Hamming di cui al primo punto.
Controllare che la soluzione dell'esercizio 47 sia giusta e provare
a minimizzare l'auoma fornito (poiche' siamo capaci di minimizzare
solo automi completamente specificati, rendere completamente specificato
l'automa fornito, prima di minimizzarlo).
Esercizio 50
Vogliamo realizzare un circuito che riceva una sequenza di bit in cui i bit sono
da considerarsi logicamente raggruppati in sottosequenze consecutive di 2 e 1 bit.
La sottosequenza di due bit rappresenta un numero in binario, a cui viene
sommato il valore del bit successivo ed il risultato fornito in output.
E' ininfluente l'output fornito negli istanti intermedi.
Esempio:
(a) Fornire le definizioni di circuito combinatorio, di circuito sequenziale,
e di automa a stati finiti
(b)
Si consideri una funzione boolena con quattro argomenti, che valga 1 solo quando almeno una
delle due condizioni sia soddisfatta:
- Il primo ed il terzo argomento sono uguali
- Il primo ed il quarto argomento valgono 1 ed il terzo vale 0.
Si richiede che lo studente:
descriva la funzione formalmente
fornisca la sua forma canonica disgiuntiva
dica se esistono implicanti primi essenziali della funzione e quali sono
Esercizio 52
Sintetizzare, mostrando tutti i passaggi del processo di sintesi, un circuito sequenziale con un bit in ingresso ed uno in uscita. L'uscita varra' sempre 0
fino al momento, se mai accadra', in cui appariranno in ingresso due 1 seguiti da due 0.
Da questo punto in poi l'uscita varra' sempre 1.
Utilizzare un circuito SP minimale per la parte combinatoria del circuito.
L'automa a stati finiti utilizzato nella sintesi deve essere, possibilmente, minimo.
Soluzione. Esercizio 53
(a)
Dire cosa fa il seguente automa a stati finiti con stati interni S={1,2,3,4}
(lo stato 1 e' quello iniziale), ingressi X={A,B,C}
ed uscite Z={0,1}.
E' un automa minimo? Dimostrare che lo e' o costruire l'automa
minimo equivalente mostrando tutti i passi.
Soluzione.
(b)
Descrivere il compostamento del flip-flop RS (Set-Reset).
Perche' gli ingressi S=R=1 non sono permessi?
(a)
Quando si applica una nuova configurazione di ingresso
ad una rete combinatoria, e' possibile che insorgano dei fenomeni
transitori. Dire quali possono essere le cause di tali
fenomeni ed eventualmente descrivere delle possibili soluzioni per
evitarli.
(b)
Vogliamo costruire un giochino elettronico che ci permetta di giocare
alla morra cinese (quella del "sasso", "forbice" e "foglio", per intenderci)
premendo dei pulsanti anziche' fare sconvenienti gesti con le mani e che possa
permettere ai giocatori di fare la loro mossa senza che questa sia necessariamente
simultanea a quella dell'avversario.
Ogni giocatore ha tre pulsanti ("sasso", "forbice" e "foglio"). Quando
uno di questi viene premuto, premerne un'altro non ha alcun effetto
finche' l'altro giocatore
(che ovviamente non puo' vedere i pulsanti dell'altro) non fa la sua scelta.
A questo punto il sistema indica
con un breve segnale luminoso il risultato (vittoria giocatore 1,
vittoria giocatore 2 o parita') e il gioco puo' continuare.
La meccanica dei tasti e' tale che non si riescano a premere due o tre tasti insieme.
Fornire l'automa a stati finiti che descrive il comportamento del nostro giochino.
Nel caso la stesura di tutti i possibili ingressi ed uscite sugli archi risultasse
eccessivamente pesante, scriverne alcuni significativi e spiegare brevemente
cosa manca.
Descrivere l'automa a stati finiti Accumula4. Tale automa riceve in sequenza
singoli segnali binari restituendo sempre 4 bit 0 agli
istanti 4k-3, 4k-2, 4k-1 (per ogni k>1). Agli istanti 4k restituira' invece
una stringa di bit formata dai bit ricevuti negli istanti
4k-3, 4k-2, 4k-1, 4k.
Esempio di comportamento di Accumula4:
Supponete di non aver la possibilita' di costruire nuovi circuiti
e di avere a disposizione i seguenti moduli:
Addizionatori, Registri, Multiplexer (selettori in ingresso),
Demultiplexer (selettori in uscita), Comparatori.
Tali moduli li potete avere di qualsiasi dimensione.
Costruire, componendo tali moduli,
la rete sequenziale sincrona che realizza Accumula4.
Tenete presente che avete la possibilita' di fornire
agli ingressi dei moduli anche dei valori costanti.
Descrivere il circuito sequenziale dell'esercizio precedente
suponendo di avere a disposizione anche dei registri a spostamento.
Esercizio 57
Supponete di dover dimostrare una proprieta' dell'algebra booleana
minimale (switching algebra) della forma exp1 = exp2.
Quali metodi potete utilizzare?
(a)
Discutere brevemente dei vantaggi e degli svantaggi delle reti sequenziali
sincrone e asincrone e dei contesti nei quali risultano utilizzabili.
(b)
Fornire l'automa a stati finiti che descriva il seguente comportamento:
supponendo di avere {0,1} come possibili ingressi e uscite,
si manda in output 1 quando esattamente due degli
ultimi 3 input sono a 0, in tutti gli altri casi l'output sara' 0.
(Si supponga che solo per il secondo input della sequenza la condizione
sia "quando gli ultimi 2 bit siano a 0").
Minimizzare l'automa o dimostrare che e' minimo.
Fornire la definizione di insieme di operatori booleani funzionalmente
completo. Dimostrare che l'insieme { piripi' } e' funzionalmente completo,
dove piripi' e' l'operatore booleano ternario definito dalla seguente
tavola di verita'
(a)
Si consideri la funzione booleana f= a'b + cd'b + d'b + ab'c' (l'apice " ' " corrisponde alla funzione not)
Quale degli implicanti dell'insieme I = { ab'c'd, c', bc, a'bd }
e' un implicante di f ?
Qualche elemento di I e' un implicante primo di f?
I e' un insieme irridondante di implicanti?
Eliminando c' da I si ha un insieme irridondante?
Giustificare formalmente tutte le risposte.
(b)
Fornire l'automa a stati finiti che descriva il comportamento di
un distributore automatico che accetta tre tipi di monete di
valore 5, 10 e 25. La merce viene erogata al raggiungimento del valore 20.
Il distributore prevede un resto massimo di una moneta da 5 e di una da 10.
Fornire solo l'automa a stati finiti, non la sua realizzazione.
Dimostrare che l'insieme di operatori booleani {not, and} e' funzionalmente completo.
Dire perche' non puo' esistere un insieme di operatori funzionalmente completo
e contenente un solo operatore booleano.
