Corso di Progettazione di Sistemi Digitali (I canale, A.A. 2019-20)

Prof. Daniele Gorla

Il corso di Progettazione di Sistemi Digitali (Ex Architettura degli Elaboratori I, fino all'aa 2007-2008) tratta argomenti preliminari alla descrizione dell'organizzazione di un calcolatore: rappresentazione dell'informazione, progettazione di reti combinatorie e sequenziali, registri e loro interconnessione. Tale corso fornisce quindi gli strumenti necessari alla comprensione del funzionamento e delle problematiche di progetto di un calcolatore, argomenti che verranno trattati nel corso di Architettura degli Elaboratori.

Orario delle lezioni

Le lezioni si svolgeranno secondo il seguente orario:

Testi consigliati

• [1] F. Preparata Introduzione alla organizzazione e alla progettazione di un elaboratore elettronico Franco Angeli editore
• [2] Appunti della prof.ssa Velardi reperibili all'indirizzo: http://twiki.di.uniroma1.it/twiki/view/Architetture1/PZ/

Chi non trovasse il testo precedente puo' fare riferimento a:

• F. Fummi, M. Sami, C. Silvano PROGETTAZIONE DIGITALE McGraw Hill
• M. Morris Mano, C. R. Kime Reti logiche Pearson
• D. P. Bovet Introduzione all'architettura dei calcolatori Zanichelli.

N.B.: i lucidi NON sono da considerarsi come una sostituzione del libro di testo! Sono, semmai, un ausilio per avere una immagine fedele di come sono stati spiegati gli argomenti in classe e per seguire meglio le lezioni in aula (per questo vengono pubblicati PRIMA delle lezioni).

Programma del Corso

Il programma di massima del corso è:

• Introduzione alla organizzazione di un elaboratore elettronico: componenti principali di un elaboratore.

• Rappresentazione dell'informazione. Codici e di codifica. Sistemi di numerazione, sistema binario. Rappresentazione in complemento a due. Rappresentazione ottale ed esadecimale. Rappresentazione in virgola fissa e in virgola mobile. Alcuni codici: ASCII, Unicode, codici per il controllo dell'errore.

• Definizione di algebra di commutazione o booleana. Assiomi e proprietà. Variabili espressioni booleane. Espressioni equivalenti. Principio di dualità. Funzioni di commutazione di una e due variabili. Dispositivi per la realizzazione di funzioni: porte NOT, AND e OR. Tabella di verità. Definizione di rete combinatoria. Relazione tra reti combinatorie ed espressioni booleane. Forma normale e forma canonica SOP e POS. Operatori NAND e NOR. Universalità di NAND e NOR. L'operatore XOR e sue proprietà.

• Analisi e sintesi di una rete combinatoria: procedimento ed esempi. Introduzione alla minimizzazione. Definizione di espressioni SOP e POS minimali. Definizione di mappa di Karnaugh. Funzioni di commutazione con condizioni indifferenti (don't care) e loro minimizzazione..

• Moduli combinatori MSI: codificatore, decodificatore, ROM, PLA, transcodificatore, multiplexer, demultiplexer. Progetto di un comparatore di numeri binari. Semiaddizionatore (o Half-Adder); addizionatore a propagazione di riporto e progetto della cella addizionatrice (Full-Adder).

• Introduzione alle reti sequenziali: memorizzazione e feedback. Latch SR. Flip-Flop SR, Flip-Flop D (delay), Flip-Flop JK, Flip-Flop T. Tabella di verità per ricavare le funzioni di eccitazione di tutti i tipi di Flip-Flop.

• Analisi di reti sequenziali sincrone. Criteri per il riconoscimento di automi contatori e automi riconoscitori di sequenze. Rappresentazione di automi tramite diagramma di stato e tramite tabella. Diagramma temporale di un automa. Automi a stati finiti. Automi a stati finiti con output: modello di Mealy e modello di Moore. Equivalenza tra automi. Trasformazione da automa di Mealy ad automa di Moore e viceversa. Minimizzazione di automi.

• Sintesi di reti sequenziali. Contatori modulo 2**n. Contatore alla rovescia. Contatori bidirezionali (up-down counter). Contatori modulo k con k diverso da 2**n. Contatori preselezionabili (o prefissabili). Contatore di impulsi su una linea x. Contatori asincroni.

• Registro universale: tutte le combinazioni di caricamento e scaricamento seriale e parallelo, scorrimento a sinistra, rotazione a destra e a sinistra.

• Interconnessione tra registri: 4 modalità (tutte le possibili combinazioni tra sorgente fissa o variabile, destinazione fissa o variabile).

  ---

Argomento delle Lezioni

In questa sezione vengono riportati gli argomenti svolti ad ogni lezione, con i relativi riferimenti ai testi.

Lezione 24 Settembre 2019 Presentazione del corso (per una visione d'insieme delle tematiche che si studieranno nei corsi di PSD e Architetture, raccomando di leggere il capitolo 2 di [1]). Sistemi digitali ed evoluzione storica degli elaboratori ([2], sezione 1.1 e 1.2). Rappresentazione dell'informazione, definizione di codice e di codifica, requisiti di una codifica; Definizione e proprietà dei sistemi di numerazione posizionali, sistema binario ([1] sez. 1.1 e 1.2; [2] sez. 1.3, 1.3.1 e 1.3.2). Conversioni di base per i numeri naturali: conversioni da decimale a base b, conversioni da base b a decimale; Intervallo di rappresentazione in base b con un numero assegnato di cifre; sistemi ottale ed esadecimale ([1] sez. 1.3, 1.3.1 e 1.5; [2] sez. 1.3.2, 1.3.3.A1).

lucidi 1 - lucidi 2

Esercitazione 27 settembre 2019 Conversione di numeri naturali da decimale a binario, ottale, esadecimale e viceversa.

Esercitazione sulla conversione dei naturali

Lezione 27 settembre 2019 Operazioni sui naturali ([1] sez. 1.4; [2] sez. 1.3.3.A2).

lucidi 3

Esercitazione 1 ottobre 2019 Operazioni tra numeri naturali in base diversa da 10.

Esercizi su operazioni tra naturali

Lezione 1 ottobre 2019 Rappresentazione degli interi in complemento a due: intervallo di rappresentazione, procedura per trovare l'opposto di un numero. Addizione e sottrazione nella rappresentazione in complemento a due ([2] sez. 1.3.3.B e B1; per una trattazione più completa, ma anche matematicamente più complessa, suggerisco di leggere [1] sez. 6.1, 6.2 e 6.3).

lucidi 4

Lezione 1 ottobre 2019 Conversioni di numeri razionali (numeri con la virgola): procedura di conversione da decimale a binario e da binario a decimale. Rappresentazione in virgola fissa ([2] sez. 1.3.3.C, C.1). Rappresentazione in virgola mobile; intervalli di rappresentazione. Standard IEEE. ([2] sez. C.2, C.2.1).

lucidi 5

Esercitazione 4 ottobre 2019 Addizione, sottrazione e opposto di un numero in complemento a due.

Esercizi su complemento a due

Lezione 4 ottobre 2019 Operazioni nella rappresentazione in virgola mobile ([2] sez. C.2.2).

lucidi 6

Esercitazione 8 ottobre 2019 Esercitazione sulla rappresentazione dei razionali in virgola fissa e virgola mobile e conversione in diverse basi. Somma, sottrazione e moltiplicazione nella rappresentazione in virgola mobile.

Esercizi sui razionali - Esercizi su operazioni in virgola mobile

Lezione 8 ottobre 2019 Codice ASCII ([1] sez. 1.6.3) e UNICODE ( pagina wikipedia). Nozioni basilari sui codici per il controllo e la correzione dell'errore: bit di parità; parità longitudinale e trasversale ([1] sez. 1.7 e 1.7.1); codice di Haming 4+3 ( note; N.B.: la teoria dei codici è un'area molto vasta ed interessante, che esula dalle finalità di questo corso; gli studenti interessati possono avere più dettagli, per esempio da questi lucidi).

lucidi 7

Esercitazione 11 ottobre 2019 Esercizi sui codici correttori. Bit di parità singolo. Codice prodotto (bit di parità longitudinali e trasversali) per la correzione di un singolo bit di errore. Calcolo dei bit di controllo per il codice di Hamming 4a3 e relative operazioni di codifica e decodifica di un messaggio.

Esercizi su codici correttori

Lezione 11 ottobre 2019 Definizione di algebra di commutazione o booleana. Assiomi: associatività, commutatività, distributività, elemento neutro, complemento. Proprietà derivate: la legge di involuzione, idempotenza, elemento nullo, assorbimento, leggi di De Morgan ([1] sez.3.4; [2] sez. 1.4). Variabili booleane e espressioni booleane. Espressione duale. Espressione complementare. Espressioni equivalenti e verifica di equivalenze. Funzioni di commutazione a 1, 2 o più variabili; tavole di verità ([1] sez. 3.1, 3.2; [2] sez. 2.1). Definizione di porte logiche ([1] sez. 3.3; [2] sez. 2.1, 2.2 e 2.3.4). Operatori NAND e NOR e loro universalità; porte XOR ([1] sez. 3.6.1, 3.6.2 e 4.7).

lucidi 8 - lucidi 9 (fino al lucido 9)

Esercitazione 15 ottobre 2019 Dimostrazioni di identità e semplificazioni di espressioni booleane utilizzando le regole dell'algebra booleana.

Esercizi su algebre di Boole - Esercizi su operatori booleani (solo es. svolto n.2 ed es. da svolgere n.1)

Lezione 15 ottobre 2019 Definizione di porte logiche ([1] sez. 3.3; [2] sez. 2.1, 2.2 e 2.3.4). Operatori NAND e NOR e loro universalità; porte XOR ([1] sez. 3.6.1, 3.6.2 e 4.7).

lucidi 9 (dal lucido 10)

Lezione 15 ottobre 2019 Espressioni booleane in forma canonica SOP (somma di prodotti); mintermini; forma normale disgiuntiva o SOP. Relazione tra la tavola di verità di una funzione e la sua espressione in forma canonica SOP. Trasformazione di espressioni in forma normale SOP e in forma canonica SOP. ([1] sez. 3.5; [2] sez. 2.3.1 e 2.3.2). Forma normale POS (prodotto di somme); maxtermini; trasformazione di espressioni in forma normale POS e in forma canonica POS. Relazione tra la tavola di verità di una funzione e la sua espressione in forma canonica POS ([1] sez. 3.5 e 3.7; [2] sez. 2.3.1 e 2.3.2).

lucidi 10

Esercitazione 18 ottobre 2019 Convertire un'espressione booleana usando solo porte NAND/NOR. Esercizi su come ricavare POS e SOP canonica a partire da una funzione booleana.

Esercizi su operatori booleani (es. svolti nn.1 e 3; es. da svolgere n.2) - Esercizi su forme SOP e POS

Lezione 18 ottobre 2019 Introduzione alla minimizzazione di espressioni booleane. Definizione di mappa di Karnaugh. Rappresentazione di funzioni tramite mappe di Karnaugh. Procedura per ottenere un'espressione minimale SOP ([1] sez. 4.3, 4.4.1, 4.4.2 e 4.4.3; [2] sez. 2.5.1) Maxtermini e termini somma su mappe di Karnaugh ([1] sez. 4.4.3). Procedura per ottenere un'espressione minimale POS. Funzioni non completamente definite, uso dei simboli don't care. ([1] sez. 4.5)

lucidi 11

Esercitazione 22 ottobre 2019 Esercizi sulla minimizzazione di espressioni booleane.

Esercizi su SOP/POS minime

Lezione 22 ottobre 2019 Definizione di rete combinatoria; relazione tra reti combinatorie ed espressioni booleane. Analisi di una rete combinatoria: procedimento ed esempi ([1] sez. 4.1 e 4.2.1; [2] sez. 2.4). Sintesi di una rete combinatoria: procedimento ed esempi ([1] sez. 4.2.2; [2] sez. 2.5). Sintesi circuiti notevoli: l'addizionatore di naturali e di interi, con condizioni di trabocco ([2] sez. 2.6.2); complementatore e sottrattore. Comparatore di numeri naturali.

lucidi 12 - lucidi 13

Esercitazione 25 ottobre 2019 Esercizi sull’analisi e sintesi di reti combinatorie.

Esercizi di analisi combinatoria - Esercizi di sintesi combinatoria

Lezione 25 ottobre 2019 Codificatore e schema con matrice di OR; decodificatore e schema con matrice di AND. ROM: definizione e uso per la realizzazione di funzioni di commutazione. PLA: definizione e uso per la realizzazione di funzioni di commutazione. Multiplexer e demultiplexer; uso del multiplexer per la generazione di funzioni booleane. ([1] sez. 4.8.1, 4.8.2, 4.8.3, 4.8.4, 4.8.5; [2] sez. 2.5.2)

lucidi 14

Esercitazione 29 ottobre 2019

Esercizi su Multiplexer, PLA e ROM. Ricapitolazione sulla sintesi combinatoria.

Esercizi su ROM/PLA/MUX - lucidi 15

Lezione 12 novembre 2019 Introduzione alle reti sequenziali: memorizzazione e feedback. Diagrammi temporali per variabili ed elementi circuitali. Elementi di memoria elementari: latch SR (comportamento in funzione dei valori degli ingressi s e r, tabella e funzione d'eccitazione). Flip-Flop D: definizione, tabella di verità e funzione d'eccitazione. Flip-Flop JK: definizione, tabella di verità e funzione d'eccitazione. Flip-Flop T (toggle): definizione, tabella di verità e funzione d'eccitazione. Realizzazione di latch D, JK e T tramite latch SR. Segnale orologio (clock). Latch sincrono (gated latch): definizione e schema circuitale; flip-flop master-slave sensibile al fronte di discesa del clock ([1] sez. 5.1, 5.2, 5.3, 5.5 e 5.6; [2] sez. 3.5).

Automi a stati finiti con output: modello di Mealy e modello di Moore. Rappresentazione di automi tramite tabella e tramite grafi etichettati ([2] sez. 3.1, 3.2, 3.3. N.B.: questa parte del programma non è trattata in maniera esauriente su [1]!!).

lucidi 16 - lucidi 17

Esercitazione 12 novembre 2019
Correzione del primo esonero.

Esercitazione 15 novembre 2019 Passaggio dal linguaggio verbale alla costruzione di un automa che lo rappresenti. Descrizione temporale di un automa che riceve un determinato input.

Esercizi su automi

Lezione 15 novembre 2019 Equivalenza tra automi. Trasformazione da automa di Mealy ad automa di Moore e viceversa; Dimostrazione dell'equivalenza dei due modelli ([2] sez. 3.3. N.B.: questa parte del programma non è trattata in maniera esauriente su [1]!!)

lucidi 18

Esercitazione 19 novembre 2019 Esercizi sul passaggio Mealy/Moore e Moore/Mealy.

Esercizi sul passaggio tra automi

Lezione 19 novembre 2019
Equivalenza tra stati di un automa. Procedura di minimizzazione di automi mediante tabella triangolare ([2] sez. 3.4. N.B.: questa parte del programma non è trattata in maniera esauriente su [1]!!)

lucidi 19

Esercitazione 22 novembre 2019 Esercizi sulla minimizzazione di un automa.

Esercizi di minimizzazione di automi

Lezione 22 novembre 2019
Analisi di reti sequenziali: costruzione della tabella degli stati futuri; diagramma di stato della rete sequenziale e del corrispondente automa; descrizione verbale ([1] sez. 5.9; [2] sez. 3.6).

lucidi 20

Lezione 26 novembre 2019
Descrizione della procedura per la sintesi di reti sequenziali: descrizione verbale, diagramma dell'automa, minimizzazione dell'automa, tabella degli stati futuri, calcolo delle funzioni di eccitazione dei FF, schema circuitale della rete sequenziale ([1] sez. 5.10; [2] sez. 3.7).

lucidi 21

Esercitazione 26 novembre 2019 Esercizi sull'analisi di reti sequenziali sincrone.

Esercizi di analisi sequenziale

Lezione 29 novembre 2019
Registri di memorizzazione: tutte le combinazioni di caricamento e scaricamento parallelo e sequenziale ([1] sez. 5.7) Registri a scorrimento: shifter a destra, sinistra, bidirezionale; con mantenimento del bit; registri circolari ([1] sez. 5.12.1).

lucidi 23

Esercitazione 29 novembre 2019 Esercizi sulla sintesi di reti sequenziali.

lucidi 22

Esercitazione 3 dicembre 2019 Esercizi sulla sintesi di reti sequenziali (N.B.: per l'esercizio 2 da svolgere servono le nozioni di contatori introdotte nella prossima lezione).

Esercizi di sintesi sequenziale

Lezione 3 dicembre 2019
Sintesi del contatore modulo 8 e suo diagramma temporale. Contatori modulo 2^n. Contatore alla rovescia modulo 2^n. Up-and-down counter (http://www.allaboutcircuits.com/vol_4/chpt_11/3.html). Contatore modulo k, con k diverso da 2^n. Contatore di 1 provenienti da una linea di input ([1] sez.5.12.2). Contatori asincroni (http://www.allaboutcircuits.com/vol_4/chpt_11/2.html). FF con ingressi asincroni (PRE)SET e CLEAR (http://www.allaboutcircuits.com/vol_4/chpt_10/7.html). Contatori modulo k con k diverso da 2**n usando gli ingressi asincroni CLEAR dei Flip-Flop (http://highered.mcgraw-hill.com/sites/dl/free/0072823151/56549/vra23151_ch07.pdf, sez. 7.10). Contatori preselezionabili (http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/cwl3/report.html#load).

lucidi 24

Lezione 6 dicembre 2019
Interconnessione tra registri: le quattro modalità di connessione. Descrizione della modalità di interconnessione sorgente prefissata - destinazione prefissata (point-to-point e con buffer tristate), sorgente variabile - destinazione prefissata (Multiplexer), sorgente prefissata - destinazione variabile (decodificatore); sorgente variabile - destinazione variabile (mesh, con registri sorgente e destinazione distinti e coincidenti; bus). Esempi di progettazione, tra cui uno schema semplificato di una ALU (per questa lezione, si segue il materiale in queste dispense). Alcuni esempi di esercizi di interconnessione.

lucidi 25 - lucidi 26

Esercitazione 6 dicembre 2019
Ancora esercizi di sintesi sequenziale.

Esercitazione 10 dicembre 2019 Esercizi di interconnessione tra registri ed Esercitazione riepilogativa, su esercizi proposti dagli studenti.

Esercizi di interconnessione

Esercitazione 13 dicembre 2019
Esercitazione riepilogativa, su esercizi proposti dagli studenti.

Esercitazione 17 dicembre 2019
Orale aperto.

Esercitazione 20 dicembre 2019
Prova simulata di esame.

Modalità di esame

Per superare l'esame bisogna:

• superare lo scritto o gli esoneri
• sostenere un esame orale (su tutti gli argomenti svolti a lezione), da sostenere solo dopo aver superato scritto o esoneri. IMPORTANTE: l'orale non necessariamente porta a migliorare il voto; un orale non soddisfacente può anche abbassare il voto dello scritto, o addirittura portare a dover rifare lo scritto. N.B.: all'orale non verrà chiesto di svolgere esercizi, ma saranno fatte domande di teoria (definizioni formali, piccole dimostrazioni, circuiti notevoli, ...)

• NON si possono consultare libri, appunti, esercizi svolti, etc.
• ognuno deve venire con un documento di identità con foto
• ognuno deve portarsi dei fogli bianchi per la brutta copia (i fogli di bella verranno distribuiti in sede d'esame) e la cancelleria occorrente (matite, penne, gomme, temperini, etc.); per nessun motivo questo materiale potrà venir scambiato tra gli studenti nel corso dell'esame
• NON si può portare la calcolatrice
• i cellulari e i tablet devono essere spenti e tenuti fuori mano per tutta la durata dell'esame
• non si potrà uscire dall'aula d'esame nel corso della prova per andare in bagno
• è OBBLIGATORIO prenotarsi, sempre su Infostud. Chi non si è prenotato non verrà ammesso in aula. N.B.: bisogna prenotarsi ogni volta che ci si presenta ad un esonero/esame!

Date e orari degli appelli di tutte le sessioni sono pubblicate nel sito del corso di laurea, alla voce "Appelli d'esame".

L'orale va effettuato nello stesso appello dello scritto, pena la decadenza del voto di quest'ultimo. Le date dell'orale verranno comunicate dal docente contestualmente con la pubblicazione dei risultati degli elaborati; sarà data la possibilità agli studenti di fissare una tra le varie opzioni date dal docente. Gli orali si terranno ragionevolmente la settimana successiva allo scritto. N.B.: Un orale gravemente insufficiente può portare a dover rifare anche lo scritto.

Testi e (alcune) soluzioni delle prove scritte passate

• Scritti a.a. 19/20:
  • Primo esonero (8-11-19): Testo;
  • Secondo esonero (14-1-20): Testo;
  • Appello di Gennaio (14-1-20): Testo;
  • Secondo esonero (4-2-20): Testo;
  • Appello di Febbraio (4-2-20): Testo;
• Scritti a.a. 18/19:
  • Primo esonero (9-11-18): Testo;
  • Secondo esonero (18-1-19): Testo;
  • Appello di Gennaio (18-1-19): Testo;
  • Appello di Febbraio (5-2-19): Testo;
  • Appello di Giugno (12-6-19): Testo;
  • Appello di Luglio (3-7-19): Testo;
  • Appello di Settembre (13-9-19): Testo;
• Scritti a.a. 17/18:
  • Primo esonero (9-11-17): Testo;
  • Appello di Gennaio (11-1-18): Testo;
  • Appello di Febbraio (1-2-18): Testo;
  • Appello di inizio Giugno (8-6-18): Testo;
  • Appello di fine Giugno (27-6-18): Testo.
  • Appello di Settembre (5-9-18): Testo.
• Scritti a.a. 16/17:
  • Primo esonero (10-11-16): Testo.
  • Appello di Gennaio (17-1-17): Testo.
  • Appello di Febbraio (7-2-17): Testo.
  • Appello di Giugno (13-6-17): Testo.
  • Appello di Luglio (4-7-17): Testo.
  • Appello di Settembre (12-9-17): Testo.
• Scritti a.a. 15/16:
  • Primo esonero (5-11-15): Testo.
  • Primo appello e secondo esonero (21-1-16): Testo.
  • Secondo appello e secondo esonero (11-2-16): Testo.
  • Appello di Giugno (13-6-16): Testo.
  • Appello di Luglio (4-7-16): Testo.
  • Appello di Settembre (14-9-16): Testo.
• Scritti a.a. 14/15:
  • Primo esonero (13-11-14): Testo.
  • Secondo esonero (18-12-14): Testo.
  • Primo appello (13-1-15): Testo.
  • Secondo appello (3-2-15): Testo.
  • Appello di Giugno (15-6-15): Testo.
  • Appello di Luglio (9-7-15): Testo.
  • Appello di Settembre (8-9-15): Testo.
• Scritti a.a. 13/14:
  • Primo esonero (11-11-13): Soluzioni.
  • Secondo esonero (14-1-14): Testo.
  • Primo appello (28-1-14): Testo.
  • Secondo appello (18-2-14): Testo.
  • Appello di Giugno (24-6-14): Testo.
  • Appello di Luglio (15-7-14): Testo.
  • Appello di Settembre (15-9-14): Testo.
• Scritti a.a. 12/13:
  • Primo esonero (12-11-12): testi e soluzioni della Fila A, Fila B, Fila C e Fila D.
  • Secondo Esonero (10-1-13): testo e soluzioni
  • Esame del 22-1-13: testo e soluzioni
  • Esame del 12-2-13: testo e soluzioni
  • Esame del 10-6-13: testo (le soluzioni sono un semplice adattamento delle soluzioni del compito di Febbraio)
  • Esame del 2-7-13: testo e soluzioni
  • Esame del 16-9-13: testo e soluzioni
• Scritti a.a. 11/12
• Scritti a.a. 09/10
• Scritti a.a. 08/09
• Scritti a.a. 07/08
• Scritti a.a. 06/07
• Scritti a.a. 05/06
• Scritti a.a. 04/05
• Scritti a.a. 02/03
• Scritti a.a. 01/02

  ---

  ---