Esercizi sui circuiti

(Nuovo Ordinamento)

Tra un esercizio ed un'altro, potrebbe essere interessante andare a leggersi questa breve biografia di Boole.
e Breve biografia di De Morgan.

Soluzione all'esercizio n.12 Cap.4 del Tanenbaum.

Esercizio 1(vecchio programma)

Fornire la forma canonica congiuntiva della funzione di 4 variabili (a,b,c,d) rappresentata dall'espressione ab^- + a^-cd + abcd^-

Soluzione. (By S. Fede)

Esercizio 2
Preso il circuito corrispondente ad ab^- + a^-cd + abcd^-, costruire un circuito equivalente, ma con almeno 10 porte logiche in piu'.

Soluzione. (By S. Fede and R.Ferraro)

Esercizio 3

Fornire due definizioni di circuito combinatorio. Una volta fatto, dimostrare che le due definizioni sono equivalenti.

Soluzione(?).

Soluzione(F. Caponnetto and C. Pata).

Esercizio 4

Cos'e' il principio di dualita' delle algebre booleane?

Soluzione (by Silvia Cariolo & Valentina Campisi)

Esercizio 5

Dimostrare che l'insieme { -->, ()^-} e' funzionalmente completo.
(Il connettivo --> e' l'implicazione: A-->B e' falso se e solo se A e' vero e B e' falso)

Soluzione (By S. Privitera).

Esercizio 6

Fare l'esercizio 19 del Capitolo 4 del Tanenbaum... e tutti gli altri.

Esercizio 7

(a) Fornire le definizioni di circuito combinatorio

Esercizio 8

Volete progettare un circuito sequenziale Accumula4 che restituisca 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:

istanti  1    2    3    4    5    6    7    8    9    10    11
Input    0    1    0    1    1    1    0    0    1    1     1  
Output  0000 0000 0000 0101 0000 0000 0000 1100 0000 0000  0000

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.

Soluzione.

Esercizio 9

Descrivere il circuito sequenziale dell'esercizio precedente suponendo di avere a disposizione anche dei registri a spostamento.

Esercizio 10

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.

Soluzione.

Esercizio 11
Dimostrare che per ogni espressione algebrica booleana ne esiste una equivalente (che rappresenta la stessa funzione) e che utilizza solo gli operatori NOR o NAND.

Risposta.

Semplici esercizi a quiz sulle Algebre booleane.
Nella pagina web http://homepages.wmich.edu/~johnson/ece250/Quiz1/quiz.html
Ci sono dei semplici quiz interattivi sull'algebra booleana. Buon divertimento.

Di seguito alcuni esercizi proposti ai vostri colleghi dell'Universita' di Milano.

NOTA:
per denotare il complemento di una espressione 'expr' viene usata la
notazione not{expr}. Espressioni consecutive come 'expr1 expr2' si
considerano in AND.

-  Usando le proprieta` dell'algebra di Boole dimostrare la
  seguente equazione:
   A + not{A} B = A + B.

-   Disegnare lo schema logico che realizza la funzione OR
  utilizzando solo porte logiche NAND. Mostrare i passi logici
  (utilizzando le proprieta` dell'algebra di Boole) che dimostrano la
  correttezza di tale schema.

-   Disegnare lo schema logico che realizza la funzione AND
  utilizzando solo porte logiche NAND.

- Sia M la funzione ``maggioranza'' di 3
  variabili, cioe`, M=1 se almeno 2 delle variabili sono a 1 e
  M=0 altrimenti. Mostrare come un MUX (multiplexer) 4-a-1 possa
  essere utilizzato per implementare M.

 Possibile soluzione (by Massimiliano Salfi).


- Si svolga l'esercizio precdente per la funzione M' che vale 1
  solo nel caso in cui esattamente 2 variabili siano a 1.

 Possibile soluzione (by Massimiliano Salfi).


- Implementare le due funzioni di 2 variabili XOR e AND
  utilizzando un singolo PLA 2x4x2.

- Implementare le due funzioni di 2 variabili XNOR e NAND
  utilizzando un singolo PLA 2x4x2.

- Implementare le due funzioni di 2 variabili XOR e AND
  utilizzando una singola ROM. Quale e` la dimensione minima
  necessaria per la ROM?



 Alcune soluzioni (by Massimiliano Salfi).  



 Altre soluzioni (by Massimiliano Salfi).

Esercizio 12
* Cos'e' un Multiplexer? Cos'e' un Demultiplexer?
* Dire brevemente perche' in un latch SR la configurazione S=1, R=1 non viene utilizzata.

Esercizio 13
Cos'e' un Multiplexer? Come si puo' usare un multiplexer per convertire dati da paralleli a seriali?

Esercizio 14
(a) Cos'e' una Macchina di Turing? Perche' il modello della Macchina di Turing e' alla base delle architetture di tipo Von Neumann?
(b) Il latch SR e' un circuito combinatorio? Giustificare brevemente.
Dire brevemente perche' in un latch SR la configurazione di input S=1, R=1 non viene utilizzata.

Esercizio 15
Abbiamo a disposizione uno spazio di indirizzamento di 2¹⁶ posizioni, in un sistema con memory mapped I/O.
Vogliamo che i 32 registri di un Chip di I/O vengano letti e scritti come se fossero le posizioni da 32 (2⁵) a 64-1 (2⁶-1) nel nostro spazio di indirizzamento. Disegnare il circuito combinatorio da collegare tra le linee di indirizzo del Bus e il segnale di Chip Select del Chip di I/O (supponendo che il CS sia asserito alto)

Soluzione.

Esercizio 16
Abbiamo a disposizione uno spazio di indirizzamento di 2⁸ posizioni. Una parte della memoria e' fisicamente realizzato da una ROM contenente 24 parole di memoria. Vogliamo che tali parole vengano lette dalla CPU come se fossero le posizioni da 8 (2³) a 15 (2⁴-1) e da 32 (2⁵) a 47 Disegnare il circuito combinatorio da collegare tra le linee di indirizzo del Bus e il segnale di Chip Select del Chip della ROM (supponendo che il CS sia asserito basso).

Soluzione.

Esercizio 17
Abbiamo un Chip di I/O che contiene due registri. Vogliamo che tali registri, utilizzando la tecnica di Memory Mapped I/O, vengano letti e scritti come se fossero, rispettivamente, la prima e l'ultima locazione di memoria dello spazio di indirizzamento disponibile, che si suppone essere di 2⁸ locazioni. Disegnare il circuito combinatorio che prende in Input le 8 linee di Address del bus e che restituisce in output il CS (Chip Select, che supponiamo asserito alto) del nostro Chip di I/O.

Soluzione.

Esercizio 18
Che cosa e' una switching algebra (algebra booleana minimale)?
Qual e' un possibile procedimento per passare dalla descrizione di una funzione booleana tramite tabella di verita' ad una descrizione della stessa funzione come espressione algebrica? Applicare tale procedimento a

Esercizio 19
Come puo' venire utilizzato il circuito di Figura 3-19 nell'implementazione della macchina Mic-1?
Da dove provengono, in tale implementazione, i vari segnali di input del circuito?

Esercizio 20
Descrivere il funzionamento del circuito di Fig. 3-24.

Esercizio 21
Abbiamo a disposizione uno spazio di indirizzamento di 2⁸ posizioni in un sistema con memory mapped I/O. Una parte della memoria e' fisicamente realizzato da una ROM contenente 56 parole di memoria. Vogliamo che tali parole vengano lette dalla CPU come se fossero le posizioni da 8 (2³) a 63 (2⁶-1) Disegnare il circuito combinatorio da collegare tra le linee di indirizzo del Bus e il segnale di Chip Select del Chip della ROM (supponendo che il CS sia asserito basso). Dare inoltre un'idea di come collegare le linee di indirizzo del Bus alle linee Indirizzo della ROM.

Soluzione.

Esercizio 22
Descrivere la funzionalita' ed il comportamento del circuito di Fig. 3-16 del testo.

Esercizio 23
Supponiate di avere un Bus con 4 linee per gli indirizzi e che tali linee siano collegate al segnale CS di una piccola ROM, come indicato nella figura.

                 __________ CS	
                 |
                AND	 
             _________
             |      |                                           
             OR     |          
           ______   |                       	   
            |  |    |                    
            |  |    |                       
A3	----x--|----|-------
A2      -------|----|-------
A1	-------x----|-------
A0	------------x-------

Ovviamente una CPU collegata a tale bus potra' leggere in uno spazio di indirizzamento di 2⁴ parole (con indirizzi da 0 a 2⁴-1). Di queste, quali sono quelle che fisicamente appartengono alla ROM sopra citata?
Giustificare la risposta.

Soluzione.

Esercizio 24
Fornire la definizione insieme di operatori booleani funzionalmente completo. Dimostrare che l'inseme {And, Or, Not} e' funzionalmente completo.

Soluzione.

Esercizio 25
Fornire le definizioni di: Circuito, Circuito Combinatorio, Circuito Sequenziale, Circuito Sequenziale Sincrono, Circuito Sequenziale Asincrono.

Esercizio 26
Disegnare il circuito di un Multiplexer (selettore di ingresso) a 4 vie.

Esercizio 27
I Chip di memoria non volatile (Nonvolatile Memory Chips). Discuterne.

Esercizio 28
Si consideri la realizzazione dell'ALU di Mic-1 tramite il collegamento di 32 alu da 1-bit come da Fig.3-19 del testo. Qual e' l'output della ALU se i sei bit di controllo
F₀, F₁, ENA, ENB, INVA, INC
sono settati con 010111? Giustificare la risposta.

Soluzione.

Esercizio 29
Descrivere la funzionalita' di un decodificatore (decoder). Fornire il circuito di un decodificatore a 4 uscite.

Esercizio 30
Cos'e' un insieme di operatori booleani funzionalmente completo? Dimostrare che {NAND, OR} e' funzionalmente completo.

Esercizio 31
E' possibile realizzare in Hw qualsiasi funzione f : {0,1}* --> {0,1}* ? Perche'?

Esercizio 32
Fornire la definizione di Insieme di operatori booleani funzionalmente completo.
Qual e' l'affermazione corretta tra le due seguenti? Dimostrarlo formalmente.

il numero di insiemi funzionalmente completi di operatori booleani e' finito.
il numero di insiemi funzionalmente completi di operatori booleani e' infinito.

Esercizio 33
Fornire le definizioni di circuito combinatorio, sequenziale, sequenziale sincrono e sequenziale asincrono.
Fornire il circuito di un Multiplexer a quattro vie.
Fornire la descrizione di un semplice circuito sequenziale asincrono.