Calcolatori Elettronici N. Mazzocca

Sistemi di elaborazione

Un sistema di elaborazione può essere definito, da punto di vista fisico e funzionale, come un insieme di elementi (sottosistemi, apparati, organi) tra loro collegati e interagenti al fine di svolgere un’assegnata funzione d’elaborazione.

I sistemi di elaborazione, svolgendo la specifica funzione assegnata, hanno il compito di trasformare dati in ingresso in opportuni dati di uscita.

L’ambiente con cui i sistemi di elaborazione interagiscono richiede l’elaborazione di dati rappresentanti grandezze fisiche sia discrete che continue.

Sistemi di elaborazione digitali e analogici

In generale è possibile distinguere tra due classi di sistemi: analogici e digitali. I sistemi analogici operano su informazioni rappresentate da grandezze fisiche che assumono valori in modo continuo in un certo intervallo. I sistemi digitali operano su grandezze fisiche che sono rappresentate da insiemi discreti di valori.

Nel caso di grandezze continue, per poter adoperare un sistema digitale è necessario utilizzare dispositivi che provvedano alla conversione da grandezze continue a grandezze discrete (convertitore analogico/digitale) per le operazioni di input, e da grandezze discrete a grandezze continue (convertitore digitale/analogico) per le operazioni di output.

Per poter consentire l’impiego di un sistema di elaborazione digitale, in diversi contesti, è necessario, quindi, che le grandezze fisiche continue siano opportunamente discretizzate. Ciò, ovviamente, avviene con opportune approssimazioni che consentono di rappresentare una grandezza continua con un numero di valori finito e significativo per l’elaborazione da eseguire.

Rappresentazione dei dati di ingresso/uscita

Alcuni possibili insiemi di dati sono già per loro natura discreti, ad esempio l’insieme dei caratteri. Altri insiemi di dati sono invece continui ma, in relazione alla specifica applicazione, è possibile determinare un numero di elementi utili a rappresentare gli ingressi significativi.

Si pensi ad esempio alla temperatura del corpo umano comunemente misurata dai dispostivi medici, questa è sicuramente una grandezza continua, ma i valori d’interesse sono generalmente comprese tra 33 e 42 gradi centigradi. Ritenendo significative le variazioni di mezzo grado: i possibili valori d’interesse non sono quindi infiniti, ma sono in numero di 19. Ovviamente, nel caso di una diversa applicazione della misurazione della temperatura, potrebbe essere necessario apprezzare un numero maggiore di cifre decimali, che saranno sempre però in numero finito e quindi rappresentabili con numeri discreti.

Sistemi digitali di elaborazione

I sistemi digitali sono largamente impiegati in applicazioni di diversa tipologia: calcolo, gestione contabile, controllo di dispositivi industriali, automotive, telefonia, ecc.

I sistemi di elaborazione digitali sono realizzati mediante dispostivi elettronici, che consentono di memorizzare, elaborare e ricevere o inviare dati al mondo esterno utilizzando un insieme di valori discreti. I dati dal punto di vista logico sono rappresentati con un numero finito di bit (valori 0 e 1) e dal punto di vista fisico ad ogni bit è associato un valore di tensione in modo che l’informazione, così rappresentata, possa essere utilizzata dai dispositivi elettronici che compongono il sistema di elaborazione.

I sistemi di elaborazione posso essere dedicati o programmabili. Nei sistemi programmabili l’elaborazione può essere suddivisa in diverse istruzioni elementari, che sono eseguite nel tempo per ottenere un determinato risultato. Ogni istruzione utilizza parte o tutti gli elementi del sistema per eseguire la sua «attività».

Obiettivi del corso

Nel corso si considerano i sistemi digitali di elaborazione.

Saranno illustrati le principali metodologie e tecniche di sviluppo che consentono di realizzare sistemi digitali di elaborazione che implementano funzioni specifiche e sistemi programmabili, che operano sui dati di ingresso mediante un insieme di istruzioni per ottenere specifiche elaborazioni (tali sistemi prendono comunemente il nome di calcolatori elettronici).

Saranno analizzate le tecniche che consentono la progettazione fisica dei sistemi (hardware) e poi per i sistemi programmabili, sarà illustrata l’architettura in termini di sottocomponenti e le modalità di utilizzo mediante dei programmi, ovvero insieme di istruzioni che operano sui dati (software).

Unit 2

Progettazione di macchine

La progettazione di un sistema di elaborazione digitale si basa su delle metodologie che consentono di determinare, in relazione alle funzionalità previste e ai tempi di risposta attesi, i componenti hardware e software costituenti il sistema.

I sistemi sono progettati per eseguire:

• una specifica attività elaborativa (ad esempio, un distributore di bibite)
• diverse attività elaborative cambiando opportunamente il programma in esecuzione (ad esempio, un computer).

Le tecnologie disponibili incidono in modo significativo sulle tecniche di progettazione dei sistemi digitali di elaborazione.

Programmi e istruzioni

La possibilità di utilizzare lo stesso sistema fisico (hardware) per ottenere elaborazioni differenti, cambiando la sequenza delle istruzioni (cambiando i programmi), rende i sistemi digitali utilizzabili in diverse applicazioni contenendo i costi di realizzazione. In modo semplificativo, un qualunque miglioramento dell’hardware potrà essere utilizzato da diverse applicazioni che utilizzano lo stesso sistema fisico.

I programmi si compongono di istruzioni che operano su dati di ingresso opportunamente codificati. Ciascuna istruzione esegue una particolare operazione elementare (che dipende dalle capacità elaborativa del sistema che la eseguirà). L’insieme ordinato di istruzioni costituisce un programma che opererà sui dati di ingresso per poter ottenere i dati di uscita.

Macchine elettroniche

Per fornire gli elementi necessari alla realizzazione di un sistema di elaborazione è opportuno procedere quindi ad un’analisi delle modalità di rappresentazione delle informazioni in ingresso e in uscita dal sistema di elaborazione, nonché di riferimenti algebrici per poter procedere poi alla descrizione del comportamento dei componenti di un sistema.

Nel caso di macchine elettroniche per l’elaborazione dell’informazione sia ha che

• i possibili ingressi e le possibili uscite sono finite e, pertanto, sia i valori rappresentanti gli ingressi che quelli rappresentanti le uscite (in logica binaria 0 e 1) possono essere codificati con un numero finito di bit (si ricordi la relazione num bit=ceiling[log_2⁡(n)], dove n è pari alla cardinalità dell’insieme da rappresentare e ceiling è la funzione che restituisce il primo intero maggiore o uguale dell'argomento);
• gli ingressi e le uscite della macchina sono rappresentati associando specifici valori di tensione ai valori 0 e 1, per ciascun bit di codifica. La variazione di un ingresso dal valore 0 al valore 1 (e viceversa) corrisponde, quindi, ad una variazione di tensione;
• ogni macchina reale risponde ad una variazione dell’ingresso in un tempo (tempo di risposta) che è funzione delle modalità costruttive e che, ovviamente, non può essere nullo.

Unit 3

Classificazione

I sistemi di elaborazione sono classificabili secondo differenti approcci. Ad esempio: in base al comportamento delle uscite rispetto agli ingressi, alle capacità elaborative, alla programmabilità, all’implementazione, ai modelli realizzativi, ai campi di impiego, etc.

Una possibile schematizzazione funzionale prevede una modellazione generale di un sistema in termini di unità operativa ed unità di controllo.

L’unità operativa si occupa della elaborazione dei dati. Essa contiene, ad esempio, i componenti per l’esecuzione delle istruzioni logiche e aritmetiche.

L'unità di controllo ha il compito di eseguire il flusso di controllo, ovvero di coordinare tutte le azioni dell’unità operativa in un certo ordine, consentendo così di eseguire una specifica elaborazione. Nel caso dei sistemi programmabili l’unità di controllo consente di eseguire una specifica istruzione avvalendosi dell’unità operativa.

Realizzazione delle unità operativa e di controllo

Le modalità di realizzazione dell’unità di controllo e dell’unità operativa sono oggetto di specifiche tecniche di progettazione. Per entrambe si possono distinguere due differenti casistiche per la loro realizzazione in termini di:

• Macchine combinatorie in cui l’uscita in un determinato istante dipende solo dall’ingresso nel medesimo istante. Ad esempio, un componente che effettua una somma di due numeri interi (compresi tra 0 a 9) può essere realizzato come una macchina combinatoria, poiché la somma dipende solo dagli specifici addendi che si intende sommare e non dagli interi precedentemente sommati;
• Macchine sequenziali in cui l’uscita in un determinato istante dipende non solo dall’ingresso nel medesimo istante ma anche da quelli precedentemente forniti alla macchina. Ad esempio, un sistema per l’erogazione di bevande è una macchina sequenziale, dato che l’uscita è funzione della moneta inserita e di quelle inserite in precedenza.

Nel caso di un’unità operativa in grado di svolgere più operazioni, l’unità di controllo dovrà essere in grado di selezionare quelle parti dell’unità operativa necessarie per svolgere la specifica elaborazione d’interesse. Nel caso di operazioni complesse che richiedono una sequenza di elaborazioni elementari, l’unità di controllo dovrà nel tempo selezionare in modo opportuno le operazioni che eseguire l’unità operativa eseguendo così l’eleborazione in più fasi.

Unit 4

Il concetto di informazione

L’analisi delle modalità di rappresentazione delle informazioni è di fondamentale importanza per poter comprendere come sia possibile rappresentare un dato all’interno di un sistema digitale di elaborazione.

E’ possibile definire qualunque informazione tramite tre caratteristiche fondamentali:

• Valore: indica il particolare elemento assunto dall’informazione
• Tipo: indica l’insieme degli elementi entro cui è stato scelto il valore attribuito all’informazione
• Attributo: indica il significato associato all’informazione nel contesto in cui questa viene utilizzata

Si ottiene un’informazione completa quando un attributo assume un valore di un determinato tipo.

Esempio

• Attributo: Soluzione dell’equazione di primo grado
• Valore: 3,45
• Tipo: Numeri reali

Il tipo di un’informazione

Ogni tipo ha una propria cardinalità N che è pari al numero di elementi che appartengono al tipo, ciò è fondamentale per pervenire ad una rappresentazione del dato con un insieme finito di simboli.

Si noti che il valore dell’informazione (elemento di un insieme) non va confuso con la sua rappresentazione, come mostrato in figura.

L’informazione più elementare è quella il cui tipo ha cardinalità 2 ed è detta bit (binary digit).

Codifica delle informazioni

Data una informazione di tipo D=(x₁,…..,x_N) rappresentata secondo un alfabeto origine, la sua codifica consiste nel rappresentarla mediante stringhe di simboli di un altro tipo R=(a₁,…..,a_k), detto alfabeto codice.

La funzione di codifica c è una funzione iniettiva dall’insieme D all’insieme R^m

D → R^m = R x R x … x R, |R^m| ≥ |D|

• In generale, a ciascun elemento x_i ∈ D corrisponde una stringa di lunghezza l_i di elementi a_i ∈ R, detta parola codice
• Dati k simboli nell’alfabeto codice, per poter rappresentare gli N valori diversi dell’informazione di tipo D con parole codice diverse, è necessario che l_i ≥ ceiling[log_kN]

Codifica a lunghezza fissa e variabile

Se l_i = l (con l ≥ ceiling[log_kN]) è costante per tutti gli elementi di D, allora si parla di codifica a lunghezza fissa.

Se l= ceiling[log_kN] si parla di codice a lunghezza minima

Se l= ceiling[log_kN] con N potenza di k, il codice viene detto completo; se N non è potenza di k, il codice è incompleto e ci saranno parole codice non utilizzate.

Se l> ceiling[log_kN], il codice viene detto ridondante.

Se la lunghezza l_i della parola codice dipende da x_i, si parla di codifica a lunghezza variabile

Usata quando gli elementi del tipo D non hanno tutti la stessa probabilità di occorrenza: parole codice più corte sono associate a elementi dell’alfabeto origine con maggiore probabilità di occorrenza.

Rappresentazione dei numeri e notazione posizionale

Dato un tipo qualsiasi di cardinalità N, i suoi valori possono essere rappresentati, secondo la codifica binaria, come un insieme ordinato di (almeno) l bit, con l ≥ cieling[log₂N] e 2l ≥ N

Esempio: per rappresentare il tipo ColoreSem{verde,rosso,giallo} di cardinalità 3, sono necessari almeno l= cieling[log₂3]= bit (3<2²)

I calcolatori utilizzano la codifica binaria per rappresentare le informazioni, che sono memorizzate in registri.

Una particolare rappresentazione binaria è quella decodificata, che prevede l’utilizzo di un codice ridondante in cui le parole codice hanno lunghezza e contengono un solo bit di valore 1 ed N-1 bit di valore 0.

Esempio: gli semi delle carte francesi possono essere rappresentati come:

• Cuori → 1000
• Quadri → 0100
• Fiori → 0010
• Picche → 0001

Esempi di codifica in diverse basi

I calcolatori adottano strategie di codifica binaria (b=2), e quindi un numero n è sempre rappresentato internamente come una stringa di bit: a_i ={0,1}.

Codifica binaria (b=2) cifre={0,1}

(1100110)₂ = 1*2⁶ + 1*2⁴ + 1*2²+1*2¹ = 64 + 32 + 4+2 = (102)₁₀

E’ frequente però l’utilizzo di basi diverse per la rappresentazione dei numeri, specie per favorirne la manipolazione da parte dell’operatore umano.

Codifica ottale (b=8) cifre={0,1,2,3,4,5,6,7}

(146)₈ = 1*8² + 4*8¹ + 6*8⁰ = 64 + 32 + 6 = (102)₁₀

Codifica esadecimale (b=16) cifre={0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}

(66)₁₆ = 6*16¹ + 6*16⁰= 96 + 6 = (102)₁₀

Rappresentazione dei numeri: i numeri naturali

L’associazione di un numero alla parola codice viene realizzata differentemente a seconda della tipologia di numeri che si desidera rappresentare (naturali, relativi, razionali, ecc.) ed è influenzata da aspetti che mirano a preservare la facile manipolazione delle rappresentazioni da parte del calcolatore (operazioni aritmetiche, confronti logici, ecc.).

Mentre la cardinalità degli insiemi numerici che occorre rappresentare è infinita, sia la dimensione che il numero dei registri in un calcolatore sono finiti, dunque è inevitabile che solo un sotto-insieme finito di elementi possa essere rappresentato.

Un sottoinsieme dei numeri naturali può essere rappresentato attraverso stringhe di bit di lunghezza costante n

• Il numero degli elementi rappresentabili è pari a 2ⁿ; tipicamente, volendo rappresentare sempre anche lo zero, si rappresentano i numeri compresi tra 0 e 2ⁿ – 1
• Ad ogni numero si associa la stringa di bit che lo rappresenta nel sistema di numerazione binario posizionale.Quando si tenta di rappresentare un numero esterno all’intervallo [0, 2ⁿ –1] si ha overflow

Esempio:

Con n=5 bit è possibile rappresentare i numeri naturali fra 0 e 31, con la codifica 00000 (=0), 00001 (=1),…, 11110 (=30), 11111 (=31).

Rappresentazione dei numeri: i numeri relativi

Esistono diverse tecniche per la rappresentazione di un numero relativo x su n bit.

Segno e modulo

• Il bit più significativo codifica il segno (0 se positivo, 1 se negativo)
• I restanti n-1 bit di X rappresentano il modulo (numero naturale)
• Intervallo di rappresentazione: [–(2^n-1 – 1), 2^n-1 – 1]
• Lo zero ha 2 rappresentazioni: 0 positivo e 0 negativo

Complementi alla base

• Il bit più significativo codifica il segno (0 se positivo, 1 se negativo)
• Intervallo di rappresentazione: [–2^n-1 , 2^n-1 – 1]

Rappresentazione dei numeri: i numeri relativi/2

Complementi diminuiti

Il bit più significativo codifica il segno (0 se positivo, 1 se negativo)

Intervallo di rappresentazione: [–(2^n-1 – 1), 2^n-1 – 1]

Lo zero ha 2 rappresentazioni: 0 positivo e 0 negativo

Eccesso -k

k viene scelto maggiore o uguale al più piccolo numero da rappresentare

Tutti i numeri sono traslati verso l’alto di k

Se k=2^n-1, i numeri compresi in [-2^n-1, 2^n-1-1] sono mappati tra [0, 2^{n -1}]: i numeri positivi hanno 1 come primo bit, quelli negativi hanno 0

Rappresentazione dei numeri: i numeri relativi

Le rappresentazioni in segno e modulo e in complementi diminuiti sono semplici ma non sono molto usate nella pratica a causa della doppia rappresentazione dello zero e della complessità dei calcoli aritmetici che comportano.

La rappresentazione in complementi alla base ha il fondamentale vantaggio di permettere, nell’ambito di operazioni aritmetiche, di lavorare direttamente sulle rappresentazioni ed è quindi la più usata.

La rappresentazione in eccessi mantiene la proprietà di disuguaglianza sulle rappresentazioni ed è usata principalmente nella codifica di numeri reali.

Codifica binaria: i caratteri

Codici standard sono stati proposti allo scopo di facilitare lo scambio di testi codificati tra diversi sistemi di calcolo, ad esempio: ASCII, UNICODE, etc…

Lo standard ASCII (American Standard Code for Information Interchange) nella sua versione originale prevede di rappresentare 128 caratteri con stringhe di 7 bit:

• i caratteri sono elencati seguendo un particolare ordine e associati a stringhe di bit corrispondenti a numeri naturali crescenti da 0 a 127 (se interpretate come numeri binari);
• un’estensione del codice ASCII prevede l’uso dell’ottavo bit: i caratteri da 128 a 255 rappresentano vari caratteri speciali, simboli matematici e lettere non appartenenti all’alfabeto inglese. Questi codici non sono altrettanto universali, e dunque non sempre sono correttamente interpretati.

Lo standard UNICODE è uno standard recente che usa 16 o più bit, e risolve in maniera completa il problema della specificità delle lingue e dei simboli matematici. E’ compatibile con ASCII (lo contiene)

L’algebra di Boole

L’algebra di Boole è uno strumento matematico di fondamentale importanza per la progettazione dei circuiti digitali.

Nel seguito saranno riassunti alcuni argomenti propedeutici utili per il prosieguo del corso, già affrontati nei corsi di fondamenti di informatica.

L’algebra di Boole fu introdotta nel 1854 come strumento per la soluzione matematica di problemi di logica.

L’impiego dell’algebra di Boole per descrivere reti binarie di commutazione si deve a Claude Shannon (A symbolic analysis of relay and switching circuits - 1938).

L’Algebra di Boole è un’algebra definita su un supporto K = {0,1} dotata di tre operazioni (AND, OR, NOT).

AND (·) K ×K → K

OR (+) K ×K → K

NOT (¬) K → K

In figura la definizione del operazioni e delle 14 proprietà.

Le proprietà dell’algebra di Boole

Le proprietà dell’algebra di Boole

In generale, un'algebra è una tripla , dove K è un generico insieme su cui sono definite due leggi binarie di composizione interna, indicate come + (OR) e ∙ (AND) rispettivamente.

Un’algebra si dice reticolo se, per ogni elemento di K, valgono le seguenti proprietà:

• commutativa:P1 : a+b = b+aP’1 : a ·b = b ·a
  • (La proprietà associativa ci dice che le due operazioni binarie possono essere genralizzate a funzioni di più di due ingressi)
• associativa:P2 : (a+b)+c = a+(b+c) = a+b+cP’2 : (a∙b)∙c = a∙(b∙c) = a ·b · c
• idempotenza o potenza identica:P3 : a+a = aP’3 : a∙a = a
• assorbimento:P4 : a+(a∙b) = aP’4 : a∙(a+b) = a

I reticoli sono insiemi parzialmente ordinati, che possiedono cioè una relazione d’ordine.

Una relazione d’ordine x≤y deve godere delle seguenti proprietà:

• riflessiva: x ≤ x
• antisimmetrica: x ≤ y e y ≤ x => x = y
• transitiva: x ≤ y e y ≤ z => x ≤ z

Dato il nostro reticolo , la relazione d’ordine è espressa dalla relazione binaria x+y=y o, equivalentemente, da x∙y=x.

Le proprietà dell’algebra di Boole

Un reticolo si dice distributivo se per ogni elemento di K vale la proprietà distributiva:

P5 : a·(b+c)=a·b+a·c

P’5 : a+(b·c)=(a+b)·(a+c)

Si noti che la proprietà è assegnata sia per la somma rispetto al prodotto che per il prodotto rispetto alla somma.

Un reticolo distributivo si dice dotato di minimo e massimo assoluti se in K sono presenti due elementi - che diremo 0 e 1 rispettivamente - i quali verificano la proprietà del minimo e massimo:

P6 : a ∙ 0 = 0

P’6 : a + 1 = 1

Gli elementi 0 e 1 si dicono minimo e massimo in quanto si ha:

a≤1 e 0≤a per ogni elemento di K

Un reticolo distributivo si dice complementato se, per ogni elemento a di K, esiste ed è unico un elemento (che diremo complemento di a ed indicheremo con ¬a, !a o ā) per il quale è valida la proprietà del complemento:

P7 : a ∙ ¬a = 0

P’7 : a + ¬a = 1

Un reticolo distributivo, dotato di minimo e massimo assoluti e complementato, si dice un'algebra di Boole <K, +, •, ¬, 0, 1>

La legge di dualità e il Teorema di De Morgan

Da qualsiasi identità booleana se ne può trarre un'altra per dualità, sostituendo cioè ad ogni operatore e agli elementi 0 ed 1 il rispettivo duale.

Si può dimostrare che da qualsiasi identità booleana se ne può trarre un'altra equivalente per dualità:

• il duale di + è *,
• il duale di 0 è 1,
• il duale di a è in generale !a (a negato, NOT a).

Per la (2) vuol dire che (!a*!b) è il negato di (a+b): applico la proprietà del complemento ad (a+b) e ottengo la 1.2 e la 1.1 rispettivamente, che devono essere verificate:

Le porte logiche e l’algebra di Boole

I circuiti logici che compongono un sistema di elaborazione digitale sono realizzabili mediante componenti elementari (porte logiche) in grado di eseguire le operazioni di AND, OR e NOT definite nell’algebra di Boole. I valori 0 e 1 sono rappresentati con opportuni valori di tensione.

Nel seguito delle lezioni sarà illustrata la metodologia che consente di pervenire da una funzione definita mediante l’algebra di Boole alla sua rappresentazione circuitale in termini di porte AND, OR e NOT .

In altri termini sarà possibile specificare in modo univoco una funzione e pervenire successivamente ad una rappresentazione realizzabile interamente con componenti elettronici.

Operatori e porte logiche

Consideriamo un esempio per illustrare la corrispondenza tra gli operatori AND, OR e NOT e le porte logiche. Assumendo che il valore 0 del bit sia rappresentato con 0 Volt e il valore 1 del bit con 5V, si avrà che:

• avendo un valore del bit 0 in ingresso ad una porta logica in grado di eseguire una operazione di AND il risultato in uscita dalla porta sarà un bit di valore 0 rappresentato con 0 Volt.
• avendo un valore del bit 1 in ingresso ad una porta logica in grado di eseguire una operazione di OR il risultato in uscita dalla porta sarà un bit di valore 1 rappresentato con 5 Volt.

In figura la rappresentazione grafica delle porte logiche

Riferimenti

http://architettura-calcolatori.dieti.unina.it/index.php/calcolatori-elettronici/argomenti-ce/1-introduzione-al-corso

Testi:

G. Conte, A. Mazzeo, N. Mazzocca, P. Prinetto, Architettura dei calcolatori, Città Studi Edizioni (2015). Cap. 1

B. Fadini, A. Esposito, Teoria e progetto delle reti logiche, Liguori (1994)

B. Fadini, N. Mazzocca, Reti logiche - complementi ed esercizi, Liguori (1995)

F. Fummi, M. Sami, C. Silvano, Progettazione digitale, (seconda edizione), McGraw-Hill (2007). Cap. 1, 2

M. Morris Mano, C. R. Kime, Reti logiche (quarta edizione), Pearson (2008). Cap. 1