Algebre booleane e progetto logico dei calcolatori digitali: differenze tra le versioni

Wikibooks, manuali e libri di testo liberi.
Contenuto cancellato Contenuto aggiunto
m fix
ortografia
Riga 2 332: Riga 2 332:


# Circuiti di memorizzazione: cioè capaci di ricevere, conservare, restituire i segnali delle informazioni.
# Circuiti di memorizzazione: cioè capaci di ricevere, conservare, restituire i segnali delle informazioni.
# Circuiti operatori: cioè capaci di realizzare le funzioni booleane a partire dai segnali delle [[w:iInformazione|nformazioni]].
# Circuiti operatori: cioè capaci di realizzare le funzioni booleane a partire dai segnali delle [[w:Informazione|informazioni]].
# Circuiti di connessione: cioè capaci di trasferire i segnali.
# Circuiti di connessione: cioè capaci di trasferire i segnali.
[[File:Rappresentazione di una informazione digitale.png|right]]
[[File:Rappresentazione di una informazione digitale.png|right]]

Versione delle 21:36, 20 nov 2016

Copertina

Parte I

Algebre Booleane

Introduzione

1.1. I sistemi aritmetici
I calcolatori aritmetici moderni, le reti di comunicazione (come le centrali telefoniche), gli insiemi dei comandi automatici dei processi industriali (come quelli delle pile atomiche per esempio) sono, in totalità o in parte, dei sistemi aritmetici: essi hanno la caratteristica essenziale di manipolare delle informazioni discrete; cioè i segnali che sono applicati al sistema (le entrate), o quelli che sono prodotti (uscite), prendono soltanto un numero finito di valori distinti (gli stati), che non variano con continuità.
Che i valori dei segnali siano discreti può essere un risultato della costruzione del sistema: i sassolini o le dita con cui si conta possono essere un esempio.
Ma il più delle volte è in seguito ad una convenzione speciale che si quantificano delle grandezze fisiche che, macroscopicamente, ci appaiono invece come continue.
I calcolatori forniscono un esempio di questo processo di quantificazione.
I calcolatori in effetti si dividono in due categorie:

Calcolatori analogici
Macchine calcolatrici in cui ogni grandezza matematica o fisica, su cui swi vuole operare, viene rappresentata da una grandezza fisica variabile con continuità e nelle quali il calcolo viene eseguito costruendo un modello del sistema in esame.
Risolvono particolari tipi di problemi, simulandoli su modelli adeguati.
La principale applicazione dei calcolatori analogici si ha nello studio di sistemi descrivibili per mezzo di equazioni differenziali ordinarie ed equazioni differenziali alle derivate parziali.
Vengono altresì usati per la risoluzione di sistemi di equazioni algebriche lineari (simultanee) e per il calcolo delle radici di polinomi.
Il regolo calcolatore, inventato nel secolo XVII, è il primo esempio di calcolatore analogico sul quale, ad es., i logaritmi sono rappresentati da lunghezze ad essi proporzionali (da cui il nome analogia).<be/> Questo procedimento presenta però notevoli difficoltà se si lavora su dei fenomeni discontinui, ed altresì presenta l 'inconveniente che la precisione dei calcoli è limitata da quella degli organi utilizzati nel calcolatore.
I vantaggi più interessanti dei modelli analogici sono il tempo relativamente breve necessario per giungere alla soluzione del problema, ed inoltre la possibilità, una volta introdotto il problema nell'elaboratore, di esaminare in pochissimo tempo, le soluzioni corrispondenti ad un vasto campo di valori dei parametri.

Calcolatori aritmetici(numerici o digitali)-
All'analogia diretta utilizzata dal calcolatore analogico si sostituisce , nei calcolatori aritmetici, un'analogia indiretta.
Usufruendo della rappresentazione numerica delle grandezze, si applica l'operazione di codifica (analogia evocata prima) sulle cifre che compongono i numeri, in luogo di applicarla alle grandezze rappresentate da quest'ultimi.
Un calcolatore digitale rappresenta quindi numeri in forma codificata e questi assumono valori finiti o discreti.
Da un punto di vista strettamente concettuale, i calcolatori digitali traggono la loro origine dalla macchina descritta dal logico matematico A.M.Touring nel 1936.

1.2. Storia del calcolatore
Il primo mezzo che si possa qualificare come un calcolatore digitale è l'abaco(il pallottoliere) ideato verso il 600 a.c.
l'abaco permette di rappresentare i numeri con la posizione delle palline o dischetti su una rastrelliera.
Le somme e le sottrazioni vengono effettuate rapidamente e con efficienza spostasndo in modo appropriato i dischetti (abaculi).
I problemi di navigazione, bellici, commerciali, con conseguente necessità di risolvere calcoli di notevole mole, suscitarono, a partire dal XVII, e nel XVIII secolo, un violento impulso per lo sviluppo delle "macchine" da calcolo.
Nel 1620l'inglese E.Gunter ideava il regolo calcolatore; e dello stesso periodo erano le invenzioni di B.Pascasl (1642) e di W.Leibniz (1651): il primo ideava unamacchina addizionatrice , il secondo una moltiplicatrice; macchine funzionanti per mezzo di ruote azionate manualmente ma con riporto automatico.
Altro tentativo degno di essere menzionatoè quello di G.Poleni (1709) veneziano, che ideo una "macchina per calcolare", di cui realizzo un prototipo funzionante.<be/> A Charles- Xavier Thomas de Colmar va il merito di aver costruito (1820) la prima calcolatrice venduta su scala commerciale.
Mentre un altro francese, Falcon, un secolo prima, aveva ideato il sistema delle schede perforate
L'inglese C.Babbage, che a diritto può essere considerato il padre del moderno calcolatore digitale, combinando le due idee su menzionate, inventava nel 1833 un dispositivo analitico e stabiliva un certo numero di principi fondamentali per la teoria dei calcolatori aritmetici.
Ma il moderno "computer" (calcolatore) è nato con lo sviluppo dei relais, dei tubi a vuoto e dei transistori: l'insieme dei dispositivi meccanici, magnetici ed elettrici di cui è costituito un calcolatore è chiamato correntemente "hardware".
Nel 1944 entra in funzione nell'università di Harward il Mark I° a relais:


nel 1946 l'Eniac (Pensilvania Univ.): a valvole.
nel 1951 Univac e IBM, primi calcolatori a valvole in commercio:


nel 1959 calcolatori a transistor
nel 1960 calcolatori a circuiti integrati
nel 1960 calcolatori a a dispositivi superintegrati.
Oggi esistono calcolatori che compiono 20 milioni di operazioni al secondo, cioè una operazione ogni 50 10-9 sec.
E' continuata negli anni e continua con ritmo sempre più crescente la diffusione dei calcolatori sia nelle applicazioni di tipo organizzativo sia in quelle tecnico-scientifiche.

Sistemi di numerazione, aritmetica binaria

2.1. struttura della memoria dal punto di vista operativo
In un calcolatore digitale la memoria è l'organo capace di conservare dei dati e delle istruzioni codificati in un certo modo. Si pone così il problema di cercare qual è il supporto migliore per memorizzare un'informazione. Dato un dispositivo che può assumere b stati diversi, è possibile codificare un numero in una certa base associando ad ogni stato una cifra del numero in questione.
Per esempio, si pensi di avere un dispositivo capace di assumere 10 stati diversi (S0,S1,S2...S9) e di associare ad ognuno di essi una delle dieci cifre base del sistema decimale nel seguente modo;

Ora se si vuole codificare il numero 3541 abbiamo bisogno di quattro dispositivi (perché quattro sono le cifre del numero da codificare) che chiameremo D1,D2, D3 e D4, dove
D4 assumerà lo stato corrispondente al numero delle unità
D3 a quello delle decine
D2 a quello delle centinaia
D1 a quello delle migliaia.

stato S0 S1 S2 S3 S4 S5 S6 S7 S8 S9
D1 3
b D2 5
D3 4
D4 1

In definitiva per codificare un numero di n cifre in base b occorrono n dispositivi capaci di assumere b stati diversi, ed una volta costruito un tale sistema vi si possono codificare (beninteso non contemporaneamente) bn numeri.
Vediamo ora come si può arrivare a dire che la base 2 è la più conveniente nel senso che a parità di numero di informazioni da memorizzare è necessario il minor numero di stati.
Si è visto che per memorizzare un numero di n cifre in base b occorre un dispositivo che contiene bxn stati diversi e capace di memorizzare N=bn informazioni diverse; il problema si pone quindi:

Immaginando ora di far variare b ed n con continuità si hanno le condizioni estremali:

dalle quali segue che lg b=1 cioè b=e che si può verificare è effettivamente un punto di minimo per la funzione b×n con la condizione di bn=cost.
Poiché 2<e<3 si potrebbe scegliere tanto il 2 quanto il 3 come base ma per motivi tecnici 8ad esempio quelli riguardanti il vantaggio dei dispositivi bistabili) si è scelta la base 2.
Vediamo ciò con un esempio pratico: il numer0 99910=1111011112 (il numero in basso sta ad indicare la base, il passaggio dalla base 10 alla base 2 verrà trattato in seguito). Allora volendo costruire i dispositivi atti a rappresentarli avremo:

Disp. S0 S1 S2 S3 S4 S5 S6 S7 S8 S9
D1 9
D2 9
D3 9
..... D1 D2 D3 D4 D5 D6 D7 D8 D9 D10
S0 0
S1 1 1 1 1 1 1 1 1 1

è facile vedere che nel primo caso occorrono 30 stati diversi, mentre nel secondo solo 20, ed inoltre nel primo si possono memorizzare 103=1000 informazioni menttre nel secondo 210=1024 informazioni.
Visto che la base 2 è migliore, vediamo come sono organizzati i dispositivi atti a memorizzare un numero in tale base.
Logicamente essi saranno in gradodi assumere due stati diversia cui diamo i valori:1 o 0; + o -; vero o falso.
I dispositivi vengono raggruppati (fisicamente) in insiemi, l'insieme delle informazioni binarie in essi contenute viene chiamato voce.
Ad ogni insieme viene associato un numero (indirizzo) che ci permette di accedere alla voce. Per esempio se si ha bisogno di conservare da qualche parte una informazione si da al computer l'istruzione di memorizzarla nella voce per es. 001.

2.2. Sistemi di numerazione
La nozione di numero è una delle nozioni fondamentali dell'aritmetica e della matematica. Non tracceremo qui ne la storia di questa nozione ne descriveremo l'evoluzione che ha portato alle definizioni assiomatiche dei numeri. Constateremo solamente che in praticai numeri ci risultano accessibili grazie ad una rappresentazione che è in generale decimale, ma può anche essere di tipo differente (sessagesimale, romana...). Un metodo di rappresentazione costituisce quello che si chiama un sistema di nemerazione. Il sistema piùusato nella vita corrente è quello decimale.
Consideriamo il numero:

Questa notazione significa in pratica che N può considerarsi risultante dalla somma:

In altri termini, la scrittura ordinaria dei numeri è un modo di esprimerli in funzione delle cifre da 0 a 9 e delle potenze di 10.
Questa notazione ha le seguenti proprietà:
-la posizione di una cifra indica la potenza di cui essa è coefficiente nel calcolo della somma
-in assenza di una potenza nella somma si mette uno0 nella posizione corrispondente
non è necessario scrivere gli eventuali zeri a sinistra dell'ultima cifra non nulla.
A causa di queste proprietà si ha l'abitudine di dire che la numerazione decimale è una numerazione di posizione.
Il numero 10, in funzione delle cui potenze si esprime il numero N, viene detto la base del sistema e sono necessari 10 simboli distinti 0, 1, 2, 3....9 per scrivere un numero.
L'utilizzazione della base 10 non è legata ad alcuna necessità logica o matematica ma probabilmente a considerazioni di tipo pratico; comunque si è fatto uso anche di altri sistemi di numerazione (base 12, 20, 60 in particolare). Si può allora generalizzare questa nozione di numerazione di posizione al modo seguente: dato un numero intero b>1, detto base del sistema del sistema di numerazione considerato, è b simboli distinti x0, x1.....x{b-1}, si fa la convenzione di scrivere un numero intero sotto la forma:

e questo per convenzione significa che il numero X può essere calcolato mediante la formula

Ogni simbolo xn...xk....x0 è uno fra i b simboli utilizzati per rappresentare i numeri da 0 a b-1.br/> Data la rappresentazione xnx{n-1}.....x0 la sommatoria fornisce X univocamente, e inversamente si può dimostrare che la rappresentazione xnx{n-1}....x0 di un intero è unica.

Nota 1:

  • Per b=2 si ha un sistema di numerazione binario
  • " b=8 ottale
  • " b=10 decimale
  • " b=12 dodecasimale
  • " b=16 esadedcimale
  • " b=60 sessagesimale

Nota 2
Se si effettua la somma in un altro sistema di numerazione , il risultato sarà un numero X. Ad esempiosi può utilizzare un sisterma di posizione ma con una base b' diversa.
Sarà allora

Esempio:
Consideriamo il numero rappresentato in ottale da: X8= 3017.
Questo numero può essere rappresentato in decimale al modo seguente:

e quindi il numero che si scrive X8=3017 in ottale diventa X10=1551 in decimale.

Nota 3
L'indice k ha nome peso o rango: il peso più debole è 0, quello più forte è n.

Nota 4:
E' da notare la distinzione tra un numero e la sua rappresentazione; tale distinzione è importante ed interviene nei problemi di conversione di un numero da un sistema di numerazione ad un altro.
Le definizioni precedenti si riferiscono a numeri interi. In generale si avranno espressioni comprendenti una parte intera ed una frazionaria che scriveremo:

espressione del numero

Come nel sistema decimale la virgola separa la parte intera da quella frazionaria.

2.3. Sistema di numerazione binario
2.3.1.Numerazione binaria.
In questo sistema un numero è rappresentato , conformemente alla definizione generale da una successione di 1 e di 0:


cioè

in cui i simboli xi assumono i valori o 0 o 1 per ogni valore di i sono detti cifre binarie o digits.

Esempio:


Nota:
Con n cifre decimali è possibile rappresentare 10n numeri. Per rappresentare questi numeri nel sistema binario è necessario un numero di cifre binarie m tali che


cioè

.

2.3.2. Addizione e sottrazione in binario. Complementazione
Addizione: consideriamo due numeri



Si cerca S=X+Y. A tale scopo si procede come nel sistema decimale, partendo dal rango 0 e determinando rango per rango la somma S. Ad ogni rango i si determina:
-la somma modulo 2 di xi, yi e del riporto ri ottenuto dal rango precedente, ottenendo il digit si della somma S.
-il riporto r{i+1} da riportare sul rango i+1.

queste due operazioni sono riassunte nella tabella 2.3.

Xi Yi ri Xi+Yi+ri Si ri
0 0 0 0 0 0
0 0 1 1 1 0
0 1 0 1 1 0
0 1 1 10 0 1
1 0 0 1 1 0
1 0 1 10 0 1
1 1 0 10 0 1
1 1 1 11 1 1

Esempio:




Sottrazione:
In modo analogo si ha la tabella 2.4, che fornisce per ogni rango, la sottrazione Si ed il riporto r{i+1} per la sottrazione S=X-Y.

Xi Yi ri Xi-(Yi+ri) Si ri
0 0 0 0 0 0
0 0 1 -1=-2+1 1 1
0 1 0 -1=-2+1 1 1
0 1 1 -2 0 1
1 0 0 1 1 0
1 0 1 0 0 0
1 1 0 0 0 0
1 1 1 -1=-2+1 1 1

Esempio:





In pratica però si utilizza il metodo dei complementi che riconduce il calcolo della sottrazione a quello di addizione.


Complementazione:
Si definisce complemento vero di un numero intero binario 0<x<2n la quantità:


Esempio:
Sia il numero X=11001 di cinque cifre. Il suo complemento vero (detto anche complemento a due) sarà:


Si definisce invece complemento ad 1di un numero intero binario 0<X<2'n la quantità:


Esempio:

sia X=11001: Il suo complemento ad 1 sarà:


Nel sistema binario il complemento ad 1 di un numero può essere ottenuto direttamente scambiando nella rappresentazione del numero stesso gli 1 con gli 0. Conoscendo il complemento ad 1 di un numero binario si può ottenere il complemento vero sommando un 1:


Si può ora utilizzare la definizione di complemento e quella di classi residuo modulo m per costruire un algoritmo in grado di calcolare una sottrazione mediante una operazione di somma.
Siano A e B due numeri tali che:


allora:


Si possono presentare due casi:
a) per A-B≥0 si ha:


b) per A-B ≤0 si ha:

Per distinguere tra i due casi è sufficiente esaminare la posizione n nella operazione A+C2n(B): infatti se A+C2n(B)≥2n nella n-esima posizione del risultato comparirà un 1 (caso a) e quindi il residuo modulo 2n fornisce la differenza stessa; se invece compare lo 0 l'operazione fornisce il valore complementato del valore assoluto del risultato (caso b).
Esempio:





2.3.3. Moltiplicazione e divisione in binario

  • Moltiplicazione- Il metodo di base è quello che si usa anche in decimale: a seconda che la cifra del moltiplicatore valga 1 o 0si aggiunge o no il moltiplicando alla somma parziale, scalando ad ogni passo quest'ultima di un rango verso sinistra:





  • Divisione- Il metodo di base consiste nel sottrarre , come nel sistema decimale, il divisore moltiplicato per il solo fattore possibile e cioè 1.

Esempio



I metodi esposti per le quattro operazioni costituiscono solo dei procedimenti a partire dai quali sono stati trovati molti accorgimenti per accrescerne la velocità di esecuzione da parte del calcolatore.

2.3.4 Sistemi con base 2p (p≥1)
Per p=1 si ha il binario puro. Per p>1 si hanno dei sistemi (p=3 ottale, p=4 esadecimale) che vengono spesso utilizzati come notazioni abbreviate per il binario puro, sia per facilitare la lettura agli operatori, sia per certi calcoli. Le conversioni dalla base2 alla base 2p e viceversa si riconducono a dei semplici raggruppamenti di termini. Consideriamo dei numeri interri: pur di aggiungere il necessario numero di zeri a sinistra di un numero binario, si può sempre scrivere:


con



cioè raggruppando le cifre binarie a gruppi di p a partire da destra.br/> Segue che:


I gruppi Xi sono quindi in binario puro le rappresentazioni delle cifre di N nel sistema a base 2p.
Inversamente , dato un numero N in un sistema di base 2p, sarà sufficiente rappresentare ogni cifra in binario per avere il numero N in binario puro.
Esempio: codice ottale



Il codice ottale è quindi spesso utilizzato come notazione compatta del binario puro. Esso infatti, a causa della semplicità della procedura di conversione, permette di economizzare allora del tempo-macchina o di semplificare i dispositivi di conversione (caso di visualizzazione numerica a cifre luminose).


3.4 Conversioni da un sistema di numerazione ad un altro.
2.4.1 Primo metodo.

  • Numeri interi: Consideriamo un numero N; lo si può scrivere mediante due basi b1 e b2 ottenendo per N due espressioni che chiameremo Nb1 e Nb2. Si avrà allora:


con le relazioni:


Il problema della conversione è il seguente: data l'espressione Nb1 nel sistema di base b1 trovare l'espressione Nb2 dello stesso numero N nel sistema di base b2, o viceversa. A tale fine osserviamo che y0 è il resto della divisione di N per la base b2.
Infatti:


quindi:


cioè


Possiamo fare le stesse considerazioni nel numero N1 e quindi y1 sarà il resto della divisione di N1 per b2 e così via.
Si vede quindi che si ottengono le cifre successive di N2 considerando i resti successivi così ottenuti:

in cui y0, y1....ym rappresentano i resti delle divisioni successive.
Esempio: convertire N10=3412 in base 8.
Si cercano allora i resti successivi delle divisioni per 8. Si ottiene:





e quindi


Notiamo che il metodo di conversione tra due basi b1 e b2 sopra esposto è in teoria applicabile nei due sensi (b1→b2 e b2→b1). In pratica volendo passare dalla base b1 alla base b2, è necessario eseguire le operazioni di divisione nella base b1. Quindi quando i calcoli sono fatti a mano non si ricorrerà a questo metodo che per convertire un numero decimale in un'altra base, come nell'esempio visto. Lo stesso discorso non vale nel caso in cui l'operazione di conversione sia meccanizzata mediante un sistema automatico.

  • Numeri frazionari inferiori all'unità.

Consideriamo, analogamente al caso precedente, in numero N in una rappresentazione Nb1 in un sistema di base b1; e cerchiamo la rappresentazione Nb2 in un sistema di base b2. Notiamo che l'espressione:


significa:

.

Moltiplicando N per b2 si ha:


Cioè la cifra che in (N×b2) appare a sinistra della virgola è la prima cifra cercata: y-1. Possiamo ora considerare il numero ottenuto conservando solo le cifre a destra della virgola ed applicare lo stesso procedimento: cioè lo si moltiplica per b2 e la cifra che risulta a sinistra della virgola sarà y-2, ecc,
Il procedimento considerato può anche non avere termine, e quindi la rappresentazione di un numero frazionario può avere termine in un sistema di numerazione e non averlo in un altro.
Come per la conversione di numeri interi, si può notare che il metodo qui visto per i numeri frazionari comporta delle moltiplicazioni nel sistyemsa di partenza a base b1. Quindi , per i calcoli a mano, questo metodo si utilizza solamente per le conversioni a partire dal sistema decimale verso una generica base b.
Esempio: Convertire N10=0,71875 in base 2.








e quindi N2=0,101110 ha termine dopo la 5a cifra.

  • Numeri con parte intera e parte frazionaria.

Si procede in due tempi: si applica il metodo (a) alla parte intera ed il metodo (b) alla parte frazionaria. Il numero cercato si ottiene mediante unione dei due risultati.


2.4.2.Secondo metodo
Dato un numero avente la rappresentazione:


si esprimono le cifre xn, x{n-1},....,x0, x{-1} nel sistemadi numerazione b2 e così anche per le potenze di b1: b1n b1(n-1).... b1,b1(-1) e si effettua la somma seguente nel sistema di base b2:

.

In questo caso notiamo che il passaggio dalla base b1 alla base b2 implica che la somma (c) sia effettuata nel sistema di base b2, e quindi questo metodo è quello usato quando è necessario convertire un numero da una base generica a quella decimale nei calcoli fatti a mano.

  • Esempio: convertire N2=11011,101 in base 10.



I metodi di conversione esposti si prestano a numerose varianti: i parametri da prendere in considerazione dal punto di vista tecnico consistono essenzialmente nella rapidità di conversione e nella complessità dei dispositivi, in contrasto fra loro.

Codici

3.1 Generalità
I calcolatori elettronici, per motivi di realizzazione, utilizzano una rappresentazione interna sia delle grandezze che dei simboli di tipo binario. Ad ogni numero o simbolo viene fatta corrispondere una parola binaria, cioè una successione di 0 ed 1 definendo quindi un codice binario.
In generale, stabilire una corrispondenza biunivoca tra i simboli di un insieme E1 (insieme dei messaggi da codificare) e quelli di un insieme E2 (insieme delle parole-codice) è per definizione codificare gli elementi di E1mediante gli elementi di E2.
In pratica si dice codice la corrispondenza 8cioè l'insieme delle regole di traduzione) tra gli insiemi E1 e E2. Il seguito del capitolo tratta i codici (essenzialmente binari) utilizzati per la rappresentazione delle informazioni. Seguirà una descrizione dei metodi per l'addizione , la sottrazione, la moltiplicazione e la divisione decimale.
Verrà inoltre trattata l'aritmetica floating-point, i cheks di parità e i codici autocorrettori.

3.1.1. Codice binario puro Il sistema di numerazione binario, descritto nei paragrafi precedenti, costituisce uno dei procedimenti mediante i quali si può rappresentare un numero sotto forma binaria.
Si è visto però che le conversioni binario-decimali richiedono un procedimento relativamente complesse e quindi, per evitare o semplificare il più possibile questa operazione di conversione tra dati esterni e rappresentazioni interne, si ricorre in certi casi ad un altro tipo di codifica binaria fornita dai codici di tipo B.C.D.(binary-coded-decimal).

3.1.2. Codici di tipo B.C.D.
Il principio consiste nel codificare il numero rappresentato in base decimale, cifra decimale per cifra decimale ottenendo la rappresentazione binaria cercata accostando la codifica binaria delle varie cifre. La tabella 3.1 fornisce un esempio di codifica delle cifre decimali: si utilizza semplicemente la loro rappresentazione in binario puro prendendo il numero minimo di simboli binari, e cioè 4.

Mediante questo codice il numero decimale 1358 sarà rappresentato da:

Per codificare in binario le 10 cifre da 0 a 9 sono necessarie almeno quattro posizioni binarie, che permettono di fornire 24=16 combinazioni. Se si considera quindi un codice a quattro posizioni , si può definire un codice particolare scegliendo 10 combinazioni tra le sedici permesse per attribuirle alle cifre 0.1.2..9, in un certo ordine. Si ha che il numero dei codici di 10 cifre decimali mediante 4 posizioni binarie è dato dal numero di disposizioni di classe 10 di 16 oggetti, cioè:


In pratica però non tutti i codici così formati sono effettivamente distinti, nel senso che non consideriamo distinti due codici i quali differiscano solamente per la permutazione delle variabili, e nel circuito ad uno scambio di fili.
Inoltre , nel caso che tutte le variabili siano disponibili sotto le due forme complementata e non complementata (uscita dei flip-flop, per esempio) possono ancora essere considerati equivalenti due codici che differiscono solo per la complementazione di una o più delle quattro posizioni.
Comunque, malgrado ciò, il numero dei codici distinti resta dell'ordine dei milioni.


3.1.3. Codici B.C.D pesati a 4 posizioni.
Il codice utilizzato in precedenza (tabella 3.1.) e cioèp quello binario puro, è di tipo pesato. Se si pone:


per la cifra decimale, x0 x1 x2 x3 simboli binari della corrispondente parola-codice, si ha:


.

Le cifre 8, 4, 2, 1 costituiscono i pesi (cioè i coefficienti da attribuire a x3, x2, x1, x0 quando si ricostruisce X mediante la (1)). Il codice della tabella 3.1 , detto codice (8,4,2,1) non è che un esempio fra i tanti, di codice pesato a 4 posizioni. In un tale codice , ogni cifra decimale da 0 a 9 è rappresentata da una espressione del tipo


I coefficienti Pi costituiscono i pesi caratteristici del codice considerato e si usa indicare il codice mediante la successione ordinata dei Pi: si avrà quindi il codice 8421, il codice 2421, ecc. Si hanno nella tabella 3.2 cinque esempi di codici a pesi positivi.

Notiamo che nel codice pesato(a quattro o più posizioni) ogni gruppo decimale codificato in binario può essere facilmente convertito in un segnale analogico a dieci livelli: sommando correnti proporzionali ai pesi si ottiene una corrente proporzionale alla cifra decimale considerata.


3.1.4 Codici B.C.D. non pesati a quattro posizioni.
Non tutti i codici sono pesati. Tra i codici non pesati a quattro posizioni, quello che viene più usato è il codice a accesso di 3.
In questa rappresentazione, alla cifra decimale X (0≤x≤9) si fa corrispondere la rappresentazione binaria pura di X+3 (tabella 3.3)

Questo tipo di codice è di lettura meno immediata rispetto al codice 8421 per un operatore umano e si presta meno bene alla conversione numerica analogica delle cifre decimali: ma dal punto di vista della realizzazione dei circuiti aritmetici esso possiede notevoli proprietà di simmetria: in particolare il fatto di essere autocomplementare. Infatti per ogni X=(x3x2x1x0) si ha


ove C9(x) è il complemento a 9 di x: per ottenere il complemento a 9 di una cifra è sufficiente complementare in binario, cifra dopo cifra, la rappresentazione x3x2x1x0 di X. Nel caso del codice 8421 ad es., le cifre binarie di 9-x non dipendono in maniera così diretta da quelle di X.


3.1.5 Codici B.C.D. a più di quattro posizioni.
Codice 2 su 5
Per questi tipi di codici B.C.D., si utilizzano 5 posizioni binarie per rappresentare le 10 cifre da 0 a 9.
A tale scopo si scelgono le 10 combinazioni binarie che hanno 2 cifre su cinque uguali ad 1.
La tabella 3.4 da un esempio di codice di questo tipo, corrispondente ad una permutazione delle dieci parole binarie in oggetto.

Questo non è un codice pesato. La nozione di codice pesato si generalizza facilmente al caso di qualunque numero di cifre binarie. Inoltre, affinché un codice sia autocomplementare, è necessario (ma non sufficiente) che la somma dei pesi sia uguale a 9. Anche la nozione di codice ad eccesso di 3 può essere esteso a codici di eccesso di E.


3.2 Codici a distanza unitaria
3.2.1 Generalità (caso binario)
Si dice codice a distanza unitaria un codice binario che possiede la seguente proprietà: le rappresentazioni in questo codice di due numeri consecutivi differiscono per una sola posizione. Se si definisce distanza di Hammimg D(X,Y) fra le due parole-codice X e Y il numero di posizioni differenti, si ha che dati due numeri x{i+1} e xi aventi per parole codice X{i+1}, Xi e tali che x{i+1}-xi=1, questa proprietà è espressa dalla relazione


x X
7 0111
8 1000


Si ha:


3.2.2. Codice riflesso (Codice Gray).
costruzione di un codice riflesso ad n ranghi binari.
Questo codice è rappresentato (per 4 posizioni) nella tabella 3.5. e può essere costruito come segue:

  • Considerate il blocco verticale (b1) ad una colonna e due righe. Scrivete al di sotto un blocco (b'1) simmetrico rispetto all'asse b1/b'1. Per il rango binario a sinistra (rango 1) porre degli zeri di fronte al blocco (b1) e degli 1 di fronte al blocco (b'1). In tal modo si ottiene un blocco (b2) a 2 colonne e 22 righe.

Scrivete al di sotto di (b2) un blocco (b'2)simmetrico e completate il rango a sinistra (rango 2) con degli 0 di fronte a (b2) e degli 1 di fronte a (b'2). Si ottiene così un blocco (b3) a 3 colonne e 23 righe.
Ripetere l'operazione di volta in volta, ecc.
Questo codice è un codice a distanza unitaria. infatti , se un blocco (bn) è ottenuto in tale modo e possiede tale proprietà, il blocco (b(n+1)) la possiede anch'esso, perché:

  • la cifra di sinistra cambia solo attorno all'asse di simmetria n mentre il resto della parola (parte destra) non cambia.

Là ove non cambia la cifra di sinistra si hanno solo i cambiamenti propri del blocco (bn) che è per ipotesi un codice a distanza unitaria.
Quindi (bn) possiede la proprietà di distanza unitaria essendo costruitoa partire da (b1) per cui tale proprietà è verificata.
Figura 3.5.

  • Formule di conversione Binartio puro-Binario riflesso

Si verifica facilmente che le cifre Bk in binario puro sono ottenute dalle cifre Rk in binario riflesso mediante la relazione:


mentre inversamente si ha:


  • Esempio: Conversione del Binario puro 10110.

Con invarianza del valore scriviamo 010110, e operiamo come segue:
R4 = B5 XOR B4 = 0 XOR 1 = 1
R3 = B4 XOR B3 = 1 XOR 0 = 1
R2 = B3 XOR B2 = 0 XOR 1 = 1
R1 = B2 XOR B1 = 1 XOR 1 = 0
R0 = B1 XOR B0 = 1 XOR 0 = 1
ottenendo 11101 come conversione di 10110.
Queste formule di conversione mostrano che il calcolo dei simboli di rango k fa intervenire le quantità di rango superiore, ciò implica che la conversione ha inizio dai pesi maggiori. Questo costituisce un inconveniente in pratica in quanto negli organi di calcolo in binario puro, a causa della struttura del codice binario, le operazioni il più delle volte vengono fatte a partire dai pesi più piccoli.
La formula (1) si può perfò mettere sotto una forma che si presta ad un trattamento per ranghi crescenti:




................................................


Nel caso che l'operazione di conversione sia eseguita con un procedimento in serie, questa formula da luogo ad una semplice realizzazione : è sufficiente infatti far circolare due volte la parola in codice riflesso in un flip-flop di tipo T al cui ingresso arrivano successivamente le cifre: in uscita del flip-flop di tipo T (inizialmente a zero) si avrà la somma modulo 2 dei valori d'ingresso. La prima circolazione permette la determinazione del valore B0, mentre durante la seconda circolazione il flip-flop darà come uscite successive i simboli Bk.


3.2.3. Utilità dei codici a distanza unitaria.
I codici a distanza unitaria sono molto utili ogni qualvolta si vogliono evitare transizioni contemporaneamente su più posizioni. Consideriamo, ad es., il passaggio da 0111 a 1000 e cioè fra cifre che pur differendo di una sola unità, comportano la variazione di tutte e quattro le posizioni della rappresentazione binaria. Il passaggio, percome sono costruiti i codificatori, non avviene simultaneamente, ma attraverso gli stati scaglionati:


Quindi gli errori, riferiti al valore finale 1\000 sono rispettivamente per ogni stadio pari a 1,5,7,8,0. I codici a distanza unitaria non sono quindi soggetti a questo tipo di inconveniente.


3.3. Controllo degli errori.
3.3.1. I circuiti di commutazione elettronici ed in particolare quelli dei calcolatori digitali non sono dotati di perfetto grado di affidabilità: si possono generare errori dovuti a cause diverse quali elementi parassiti, perdite di alimentazione, errori casuali dati da componenti oscillanti al di fuori della tolleranza, errori sistematici dovuti al cattivo funzionamento di un componente, per usura o per guasto.


Teoria della commutazione

4.1. Relais elettromagnetici con interruttori.
Numerosi sistemi elettrici hanno nei loro circuiti di comando e di controllo dei relais elettromagnetici. Un tale relais è composto essenzialmente da un elettromagnete e da una armatura mobile , portante delle lamine metalliche.
Ogni lamina è fissata all'armatura da una estremità mentre l'altra estremità è lbera e può , a seconda della posizione dell'armatura, chiudere o no un contatto. L'insieme della lamina e del punto di contatto associato, costituisce ciò che si chiama interruttore: esso può essere aperto o chiuso. A seconda che la bobina di eccitazione della elettrocalamita sia eccitata o no da una corrente, l'armatura portante si trova in una o nell'altra di due posizioni: quando non passa corrente d'eccitazione, essa si trova nella posizione detta di riposo mentre de la bobina è eccitata , l'armatura si trova in una seconda posizione.

Si può allora distinguere nella maggior parte dei relè due tipi principali di interruttori: interruttori normalmente aperti e interruttori normalmente chiusi. Gli interruttori normalmente aperti sono aperti quando l'armatura è nella posizione di riposo e chiusi quando questa è attirata dalla elettrocalamita. Gli interruttori normalmente chiusi sono chiusi quando l'armatura è nella posizione di riposo e aperti quando essa è attirata dalla elettrocalamita.
Riassumendo quindi, il relè descritto possiede le caratteristiche seguenti:

  • 1) c'è un valore di ingresso costituito dallo stato della bobina di eccitazione: essa può essere eccitata o no.>br/>
  • 2) vi è un certo numero di uscite, ciascuna delle quali è costituita dallo stato di chiusura o di apertura degli interruttori.

Il rapporto ingresso-uscita (cioè la relazione tramite la quale il relè apre o chiude un contatto in funzione del valore in ingresso) dipende dalla natura degli interruttori: essa può essere riassunta nella tabella seguente:


4.2. Variazioni binarie associate ad un relè. Complemento di una variabile.
L'esame della tabella rivela che il comportamento di un relè può essere descritto mediante delle variabili che possono assumere 2 valori, cioè delle variabili binarie.

E' comodo fare astrazione dal nome delle variabili e utilizzare al posto delle coppie di simboli A0, A1, ecc., 2 simboli solamente (gli stessi per tutte le variabili). Si possono prendere per questo le cifre 0 e 1 e attribuirle in maniera arbitraria ai due stati di ogni variabile:

Si può osservare che quando la variabile X ha un dato valore, la variabile Y ha l'altro. Si può allora porre:


dove la variabile Y è definita in funzione di X: essa si chiama il complemento di X:

complemento di X
X
0 1
1 0


Si hanno allora le relazioni:


Si vede quindi che con questa convenzione, la variabile X associata ad un interruttore normalmente aperto è uguale ad E, mentre quella associata ad un interruttore normalmente chiuso è , per cui è sufficiente una sola variabile E a definire il relè.
Nasce quindi la convenzione di associare ad ogni relè una lettera X. Il valore della variabile rappresenta lo stato di eccitazione del relè e si indicano con X gli interruttori normalmente aperti e con gli interruttori normalmente chiusi.
Esempio: tre rappresentazioni di un circuito con interruttori:


Le differenti lettereche compaiono in uno schema corrispondono ai diversi relè, i differenti simboli X e corrispondono agli interruttori di un relè e la presenza o l'assenza della sbarra sulla lettera informa della natura dell'interruttore (normalmente aperto o normalmente chiuso).





4.3. Funzione di trasmissione di un circuito.
In generale, dato un circuito a 2 terminali A e B, si definisce una variabile binaria TAB chiamata funzione di trasmissione tramite la seguente convenzione:

(a)Trasmissione di un interruttore
Dato un circuito costituito da un unico interruttore, si hanno le seguenti relazioni


  • Interruttore normalmente aperto:

che permette di scrivere algebricamente:


  • interruttore normalmente chiuso:

che permette di scrivere algebricamente:



(b) trasmissione in un circuito

Si consideri il circuito costituito da 2' interruttori X e Y in serie (e la cui natura è generica):


Se gli interruttori X e Y sono entrambi chiusi, il circuito è chiuso. Viceversa, se l'uno dei due interruttori è aperto, o se lo sono entrambi, il cammino tra A e B è aperto.

Si può rappresentare tutto ciò tramite una tabella (tavola della verità) che ha per ingresso le differenti combinazioni possibili di X e Y e, come uscite , il valore della trasmissione TAB del circuito tra A e B. Così la risposta binaria del circuito appare come una funzione T=T(X,Y) delle due variabili binarie X e Yo, ancora, come una operazione sulle variabili X ed Y.
Si porrà allora:


Così all'operazione di messa in serie dei 2 interruttori x ed Y è associata l'operazione (*) sui valori algebrici delle variabili X ed Y. Tale operazione si chiama prodotto.

(c) Trasmissione di un circuito con 2 interruttori in parallelo

Si consideri il circuito costituito da 2 interruttori X e Y (di natura qualsiasi) posti in parallelo. Se uno dei due interruttori X o Y è chiuso, o se sono entrambi chiusi, il cammino tra A e B è chiuso. Viceversa se i due interruttori sono aperti contemporaneamente, il cammino AB' è aperto.
Il funzionamento del circuito AB potrà essere riassunto:

La risposta TBA del circuito appare come una funzione delle due variabili X e Y oppure come una operazione su X e Y che si scriverà:


Così all'operazione di messa in parallelo di 2 interruttori è associata l'operazione (+) sulle risposte di X e Y, ed è chiamata somma.

Sono così definite tre operazioni sugli interruttori.
1) La complementazione: essa consiste nel sostituire ad un interruttore in paralleloX' un interrurrore dell'altro tipo: la nuova trasmissione è .
2) La messa in serie: la trasmissione risultante è T=X*Y
3) La messa in parallelo: la trasmissione risultante è x*y.
Finora si sono considerati dei circuiti costituiti da interruttori elementari, e mediante le tre suddette operazioni si sono costruiti altri circuiti, ma si possono naturalmente definire le operazioni -, +, * anche per dei generici circuiti.

Complementazione: si dice circuito complementare di un circuito di trasmissione T', un circuito che da la risposta

Messa in serie: T1*T2
dove T1 e T2 sono le risposte dei due circuiti

Messa in parallelo: Tp=T1+T2

Quindi con le operazioni di complementazione, messa in serie e messa in parallelo si può definire un procedimento di costruzione di circuiti sempre più complessi partendo da un circuito elementare. Ad ogni passo costituito da una operazione sui circuiti, si può associare una operazione algebrica sulla risposta dei circuiti. Al circuito finale si potrà quindi associare una risposta algebrica ed esprimerla in funzione di quella degli interruttori dei differenti relè.
Prima di dare qualche esempio di questo metodo, si esporranno alcune proprietà delle operazioni di -, *, +.
Per dimostrare queste proprietà si può procedere in due maniere:
1) Ragionando direttamente sui circuiti
2) Utilizzando le tavole di definizione delle operazioni.


4.4. Proprietà delle operazioni (-), (*), (+).
Prima di passare alla trattazione delle operazioni (-), (*), (+), diamo qui di seguito la definizione di circuiti equivalenti.
Due circuiti si dicono equivalenti, se le variabili associate ai circuiti assumono gli stessi valori, ogni qualvolta gli interruttori, comuni ai due circuiti, si trovano nello stesso stato.
Due circuiti possono essere equivalenti anche se non tutti gli interruttori, di cui sono formati, sono in comune.
In questo caso però le variabili associate ai circuiti non devono dipendere da questi interruttori.
Si indicano le proprietà delle operazioni (-), (*), (+) con i simboli da R1 a R20.
Si lascia al lettore, per esercizio, la dimostrazione di tali relazioni.

R1)


R2)


R3)


R4)


R5)


R6)


R7)


R8)


R9)


R13)

A titolo di esempio diamo qui di seguito la dimostrazione della relazione


  • Primo metodo: ragionamdo sui circuiti si vede che se A è aperto, i due circuiti sono chiusi solamente se B e C sono chiusi, e aperti negli altri casi.

Se A è chiuso, i due circuiti sono chiusi qualunque sia lo stato di B e C. I due circuiti hanno quindi lo stesso funzionamento per le diverse combinazioni di A, B, C.

  • Secondo metodo:uso delle tavole.

Essendo tre gli interruttori, abbiamo 23=8 combinazioni di valori per A, B, C. I termini componenti la relazione sono 6 e cioè:

Calcoliamo pertanto tutte le combinazioni possibili di A, B, C e degli altri 6 termini utilizzando le regole di definizione delle operazioni (+) e (*).
Le colonne corrispondenti ad A*B*C e (A+B)*(A+C) sono identiche e quindi le due espressioni in questione hanno gli stessi valori per tutte le combinazioni delle variabili A, B e C.
Da ciò discende l'equivalenza.

4.5.Esempi di applicazione

Esempio 1: Si consideri l'esempio in figura: esso è costituito dai tre relais A, B, C e 6 interruttori. E' possibile trovare un circuito R' equivalente nel senso che esso sarà chiuso quando R è chiuso , aperto quando R è aperto e che comporta un numero minimo di interruttori.
Il circuito R possiede tre rami in parallelo ognuno dei quali è composto di due interruttori in serie.
I rami hanno per funzioni di trasmissione:


per cui la trasmissione T del circuito R sarà:


Sostituendo ad i loro valori numerici, per ognuna delle 23=8 combinazioni di A, B e C, si ottiene il valore della trasmissione in ogni caso.
Si possono eseguire le seguenti operazioni:


=
=
=
=
=
=
=
=

Si ottiene quindi un nuovo circuito, equivalente al primo, ma costituito solo da 4 interruttori:

Volendo conoscere i valori della funzione T abbinata al circuito in questione, è sufficiente considerarla con l'ausilio di una tabella della verità:




Esempio 2: Si consideri il circuito in figura. Quando esso sarà aperto?







Il circuito è dunque sempre chiuso ed è equivalente ad una semplice connessione. Con questi esempi si è messo in evidenza come si possano sostituire i ragionamentoi diretti sui circuiti con delle operazioni algebriche.
Negli esempi precedenti si è visto come , dato un circuito, mediante il disegno delle disposizioni dei suoi interruttori, se ne possa trovare l'espressione logica che lo rappresenta.
Su questa espressione logica si può operare utilizzando le proprietà R1....R20 ottenendo così dei circuiti equivalenti: operando opportunamente si può pensare di ottenere circuiti con minimo numero di interruttori.
Si è visto inoltre come, volendo conoscere i valori assunti dalla funzione di trasmissione di un circuito, questi si possono dedurre utilizzando una tabella della verità.
Esiste ora il problema inverso: progettare un circuito che si comporti secondo una tabella della verità fissata a priori.


Sia allora noto il numero di interruttori necessari: tale informazione , e la tabella della verità, spiegano completamente il comportamento del circuito. Si consideri il circuito dato nell'esempio 1: di esso , in questo caso, si sa che èp fornito di tre interruttori A,B e C ed è data la sua tabella della verità.
Se si considera la funzione T, come somma delle funzioni T1,T2,T3 e T4, essa assumerà il valore 1 se, e soltanto se una delle funzioni T1,T2,T3 e T4, ha il valore 1. Così la funzione T varrà 1 sempre e soltanto in corrispondenza alle combinazioni prefissate. Se si considera ora una qualsiasi delle funzioni Ti (i=1...4) si nota che essa assumerà il valore 1 se la si rappresenta come prodotto degli interruttori: questi ultimi ovviamente saranno rappresentati nella forma non complementata se valgono 1, nella forma complementata se valgono 0. Nell'esempio precedente si ottiene:


Trovata l'espressione logica, si può cercare di semplificarla con i metodi studiati e, successivamente , disegnare il diagramma del circuiuto trovato.

<br/



Esempio 3: Con il seguente esempio si vuole illustrare il processo completo costituito dal prendere in considerazione un problema e trovarne le soluzioni in termini di dispositivi fisici. Un fattore ha un granaio la cui porta rimane facilmente aperta: la capra della fattoria ha la tendenza di avvicinarsi a questo deposito. Terzo elemento del problema è un lupo che circola nei pressi della fattoria. Il fattore decide allora di costruire un circuito con tre interruttori: uno che segnali se la porta del granaio è aperta o chiusa, uno per la capra in vista, uno per il lupo in vista.
Un garzone viene poi messo a controllare la situazione; se una o più delle circostanze predette si manifesta, egli deve premere il pulsante corrispondente. Se la situazione diventa pericolosa , il sistema darà l'allarme e il fattore si comporterà di conseguenza. E' ovviamente il fattore, ideatore del circuito , che deve definire quando una situazione è pericolosa: egli potrà per esempio assumere che:
1) la situazione tranquilla se il lupo e la capra non sono contemporaneamente visibili.
2) il lupo non costituisce un pericolo per il grano.
Riassumendo queste considerazioni in una tabella della verità, si ottiene:


dove L=lupo, C=capra, P=porta.
Funzione di trasmissione:


1)Disposizione 011- il lupo può mangiare la capra se non sono separati.
2)Disposizione 110- la porta è aperta e la capra è nelle vicinanze
3)Disposizione 111- entrambe le situazioni pericolose sono presenti.
Riducendo l'espressione della funzione di trasmissione si ottiene:


Il circuito cercato sarà quindi:


4.6.funzioni di due variabili.<brf/> Si sono definite in precedenza le due funzioni di due variabili, chiamate X*Y e X+Y, mediante l'uso di una tavola nella quale viene rappresentato il valore della funzione pe rogni combinazione dei valori delle due variabili X e Y. Si può usare questo procedimento per definire altre funzioni di 2 variabili. per fare questo si consideri ancora la lista delle combinazioni di ingresso e si consideri il fatto che, per ognuna di esse , si può scegliere di attribuire come valore di uscita il valore 1 o il valore 0. Poiche esistono 4 combiunazioni di ingresso, a ciascuna delle quali si può fare corrispondere 2 valori, in conseguenza esistono 24=16 funzioni possibili di 2 variabili.


Queste diverse funzioni possono ora essere espresse mediante le operazioni * e + e l'operaziione di complementazione.
1) Si consideri per esempio la funzione T1:
T1 vale 1 quando X e Y valgono zero tutti e due, cioè quando e valgono 1 e zero in tutti gli altri casi per cui:


Considerando la tavolka della verità si può verificare che effettivamente la colonna corrispondente e T1 e hanno lo stesso valore per ogni combinazione dei valori di X e Y.


In generale si otterrà:









Si è così definita nell'insieme dei circuiti con interruttori un'algebra che viene chiamata algebra dei contatti o algebra di commutazione.
In segutito si introdurranno altri elementi di commutazione ; principalmente elementi elettronici e magnetici8 che si possono organizzare in reti complesse e che potranno essere4 studiati grazie ad un'algebra che si rivelerà avere la stessa struttura dell'algebra dei contatti.


Algebra delle classi-Algebra della logica

5.1.Insiemi
Introduciamo il concetto di insieme mediante esempi.
L'insieme degli italiani, l'insieme dei numeri interi, ecc. Gli enti che fanno parte di un insieme vengono chiamati elementi.
Per scrivere che un elemento X appartiene ad un insieme A, si usa la notazione:


Inversamente , se X non appartiene ad A si scriverà:


Inoltre, per rappresentare un insieme , si utilizzeranno delle parentesi, all'interno delle quali si troveranno gli elementi stessi, oppure il simbolo dell'elemento generale con l'enuncuato della proprietà comune a tutti gli elementi dell'insieme.
Così se R è l'insieme delle radici della equazione.


si avrà:

R={1,2,3}

oppure:

R={x|x3-6x2+11x-6=0}

e questa seconda notazione si leggerà: R è l'insieme degli elementi x tali che si abbia:


Si dice che due insiemi , A e B, sono uguali (0 identici)se essi sono formati dagli stessi elementi: e si scrive A=B.
In altri termini, ogni elemento x appartenente ad A appartiene a B e viceversa.

1) Esempio: gli insiemi:


dove {x} è l'insieme costituito dal solo elemento 2', sono uguali.
Si dice che un insieme A è un sottoinsieme di un insieme Bse ogni elemento di A appartiene a B (si dice anche che A è incluso in B o che A è una parte di B, o infine, che B contiene A) e si utilizzano le notazioni:



Nella definizione data, come nelle notazioni 1) e 2), non si esclude il caso in Dato un insieme A come sottoinsieme di un insieme U, si chiama complemento di A rispetto ad U l'insieme dei punti di U che non appartengono ad A.
Si scrive:


Si può scrivere, utilizzando le notazioni di cui sopra:

Esempio: se U è l'insieme dei numeri reali ed A quello dei numeri razionali, U-A è l'insieme dei numeri irrazionali.

L'insieme U-A è un complemento relativo. Quando non vi è ambiguità sull'insieme U da considerare, si può definire un complemento assoluto come l'insieme dei punti che non appartengono ad A e lo si denota con la espressione:


Si noti che l'operazione con la quale si ottiene da A, cioè la complementazione, è una operazione ad un solo termine.

Definiamo ora operazioni a 2 termini (binarie).
a)L'unione di due termini A e B è l'insieme dei punti che appartengono ad A o a B oppure ad entrambi contemporaneamente.
L'unione di A e B è rappresentata:

.

Così l'unione dell'insieme dei punti del segmento 0≤x≤1 e del segmento 0,5≤x≤1,5 è l'insieme dei punti del segmento 0≤x≤1,5.
b)L'intersezione di due insiemi A e B è l'insieme dei punti che appartengono contemporaneamente ad A ed a B e si rappresenta:

.

Per esempio l'intersezione dei numeri primi e dell'insieme dei numeri pari è l'insieme {2}.
E' comodo introdurre un insieme il quale non possiede alcun elemento: esso si chiama elemento vuoto e lo si rappresenta con il simbolo Φ.
Segue che l'uguaglianza:


significa che gli insiemi A' e B non hanno alcun punto in comune. Si dice anche che essi sono disgiunti. Analogamente è conveniente introdurre un insieme contenente tutti gli elementi possibili: insieme universale o universo (e lo si noterà con il simbolo U.I, ecc.).
Dato un insieme E, i suoi sottoinsiemi possono essere considerati come gli elementi dell'insieme potenza P(E) o 2E (insieme delle parti di E costituito dai sottoinsiemi di E, inclusi l'insieme vuoto e quello improprio).
Esempio:


P(E) è dunque un insieme di insiemi dei suoi sottoinsiemi: sono particolarmente interessanti quelli chiamati ricoprenti di E o parti di E.
Dato un insieme E (appartenente all'insieme universale U), si chiama ricoprimento di E un insieme delle parti di E un insieme delle parti di Etale che E sia uguale alla loro unione.
Esempi: l'insieme dei numeri interi, dei numeri razionali, dei numeri irrazionali e dei numeri trascendenti, costituisce un ricoprimento dell'insieme dei numeri reali.
Un ricoprimento di E sia tale che due insiemi qualunque di esso siano disgiunti. Ogni punto di E si trova allora in un insieme della partizione, ed uno solo.
Così l'insieme dei numeri razionali e dei numeri irrazionali , costituiscono una partizione dell'insieme dei reali.


Quesste differenti definizioni possono ricevere una interpretazione grafica chiamata Diagrammi di Venn
L'insieme universale è rappresentato con un rettangolo e gli insiemi A e B ecc. sono rappresentati come cerchi.
Nelle figure seguenti si dà l'interpretazione delle diverse operazioni definite precedentemente:


5.2.Algebra delle classi.
Si consideri un insiemeI che starà a rappresentare , nel seguito, l'insieme universale. I differenti sottoinsiemi di I formano essi stessi un insieme, sul quale si possono definire le tre operazioni di: unione, intersezione e complementazione. L'insieme dei sottoinsiemi di I costituisce così un'algebra denominata algebra delle classi.
A partire dalle definizioni di insieme, sottoinsieme, e delle 3 operazioni di cui sopra, si possono dimostrare diverse proprietà di questa algebra. Esse si possono giustificare con l'aiuto dei diagrammi di Venn, oppure con rigorose dimostrazioni , partendo dalle definizioni.


E' la proprietà detta dell'associatività dell'unione .



E' la legge d'associatività dell'0perazione di intersezione.



essa è la legge di commutatività dell'0perazione di unione ; risulta dalla definizione di A∪B: il risultato non dipende evidentemente dall'ordine dei due operandi A e B.



legge di commutatività dell'operazione d'intersezione.



Φ non contiene nessun elemento quindi la sua unione con l'insieme A non è altro che A stesso.



Essendo A' contenuto in I (per definizione), i punti comuni ad A ed I sono tutti quelli di A.






Legge di distributività dell'unione rispetto all'intersezione.



Un insieme A ed il suo complementare non hanno alcun punto in comune : essa è una conseguenza della definizione di



L'unione di un insieme A e del suo complementare è sempre l'insieme universale. Esso è una conseguenza della definizione di . quindi il complementare di A soddisfa alle due relazioni : E9 e E10.
Inversamente, se un insieme B soddisfa alle relazioni:


Esso è il complemento di A; ossia:


Infatti, sia un elemento x∈B, la E'9 afferma che x∉A e la E'10 che x∈I.
Dunque x appartiene ad , . Dunque . Ma ogni elemento di A, d'altra parte, verifica E9 ed E10; dunque se , ; per cui .
Da cui . In altri termini, le due relazioni E'9 e E'10 hanno per soluzioni e le si utilizzeranno, in pratica, per definire direttamente .



Legge di idempotenza per la unione U.


Legge di idempotenza per la intersezione .




Prima legge d'assorbimento.
L'intersezione E=A∩B è un sottoinsieme di A; l'ulteriore unione di E con A non può che dare A.



seconda legge di assorbimennto.
A è contenuto in E=A∪B, da cui A∩E=A.




Primo teorema di Morgan per gli insiemi:
Esso si enuncia dicendo che il complementare della unione è uguale all'intersezione dei complementari.

Secondo teorema di De Morgan:


Il complemento delle intersezioni è uguale all'unione dei complementari.


5.3.
- Valore logico delle proposizioni.
Se si esamina il linguaggio di cui si fa uso ogni giorno, e più particolarmente quello che serve come mezzo per esprimere un ragionamento scientifico, se ne possono discernere degli elementi detti : legandole tra di loro , si può costruire l'enunciato di un teorema, la dimostrazione di un teorema, una definizione, ecc..
Questa articolazione del linguaggio in è, del resto, una delle caratteristiche fondamentali del linguaggio umano.
Così le espressioni:

1) "11 è un numero primo"
2) "il triangolo 'ABC è rattangolo"

costituiscono delle proposizioni.
Ciascuna di queste proposizioni, può essere esaminata sotto l'aspetto della sua verità o della sua falsità.
Per esempio: la proposizione 1) è vera mentre la 2) può essere esaminata con il criterio su accennato e deve essere possibile se essa è vera o falsa.
Nel seguito si studieranno le proposizioni e si supporrà che le proposizioni esaminate non possano essere che vere o false.



Continuando l'esame del linguaggio ordinsrio, si puòl mettere in evidenza tutta una classe di parole, o anche di espressioni più complesse, che però non sono proposizioni ma elementi di legame tra proposizioni: e, o, ma, oppure, "implica che", "equivale a dire che", ecc.. Nel linguaggio corrente, queste operazioni di legame delle proposizioni elementari, formando proposizioni più complesse, non sono prive di ambiguità.
Nondimeno, le nozioni di proposizione e di legami, forniscono lo spunto per un insieme di concetti matematici che, in questo caso, saranno dotati di una definizione rigorosa.



Consideriamo per esempio le due proposizioni:

"x è un numero primo"
"Il triangolo ABC è rettangolo"

Con l'aiuto della congiunzione "e" (AND) si può formare una nuova proposizione che si enuncerà: " x è un numero primo E il triangolo ABC è rettangolo".
Quando essa sarà vera?
Questa nuova proposizione sarà considerata come vera, quando le due proposizioni componenti sono vere tutte e due, e falsa in tutti gli altri casi. Ovviamente si sarebbe potuto considerare altre due proposizioni, ad esempio:

"Roma è la capitale d'Italia"
"Il clima italiano è mite"

e costruire in maniera analoga una proposizione nuova con la congiunzione "e"(AND).
Si vede dunque che l'operazione AND da una proposizione nuova , a partire da due proposizioni componenti, in una maniera caratterizzata essenzialmente dal modo in cui si determina se essa è falsa o vera , conoscendo la falsità o la verità delle componenti, ma, in fondo, indipendentemente dal senso e dalla natura delle proposizioni. Si può aòòora rappresentare ogni proposizione, con una variabile capace di prendere soltanto i due valori logici rappresentati von V (vero) e F (falso).

L'0perazione di AND allora, tra due proposizioni generiche P e Q verrà definita dalla tavola AND.
Si definisce così una delle operazioni della logica matematica: essa viene indicata con il simbolo e si chiama operazione di AND o prodotto logico. Una tavola come quella a fianco prende il nome di tavola della Verità: essa descrive , per tutte le combinazioni possibili, il valore (vero o falso) della proposizione composta , in funzone dei valori delle proposizioni componenti.


(somma logica)


Si consideri la frase (nell'algebra ordinaria)

"il prodotto X Y è nullo se x=0, y≠0; oppure se x≠0, y=0; oppure x=0, y=0."

La proposizione (x=0) oppure (y=0) fornisce un esempio di una nuova operazione che si può definire rigorosamente mediante una tavola
Date due proposizioni P e Q si chiamerà "proposizione P OR Q" e si scriverà "P V Q", la proposizione composta definita dalla tavola affiancata.
L'operazione V, così definita, prende il nome di somma logica.



A partire da una proposizione come "oggi piove", possiamo formulare una seconda proposizione "oggi non piove". E' chiaro che se la prima è vera, la seconda è falsa e viceversa. Si può quindi definire l'operazione di negazione: la negazione di una proposizione P viene rappresentata con il simbolo ()P; ed è data dalla tavola affiancata. Conformemente all'uso generale , si preferisce rappresentare i due valori logici di una variabile, non con i simboli V ed F ma con i simboli 0 ed 1; si noti però che si tratta di una convenzione pratica alla quale l'aritmetica è completamente estranea. Tra le due convenzioni possibili si è scelta la seguente:


E' facile riscrivere la tavole precedenti con il nuovo simbolismo.

Oltre alle tre operazioni logiche fin qui studiate, possiamo, con lo stesso metodo di definizione, costruire 24=16 tavole della verità di due variabili che definiscono altrettante operazioni o funzioni logiche:



E' il nome dato alla funzione F6: si confrontino le due tavole della verità di P⊕Q e P v Q>br/> Si noti che P ⊕ Q ha il valore 1 quando P e Q hanno valori logici differenti e 0 altrimenti.<be/> Al contrario la proposizione P v Q assume il valore 1 anche per P=1 e Q=1

math>\underline {Esempio}</math>

Il prodotto delle variabili algebriche non nulle A e B è negativose A oppure B sono negative.



: P ↔ Q (F9).

Con l'operazione si otterrà una nuova proposizione e si scriverà P ↔ Q; vera quando P e Q hanno lo stesso valore logico e falsa nel caso contrario: essa si chiama equivalenza di P e Q; oppure implicazione reciproca di P e Q.
Si noti come le due proposizioni P ↔ Q e P ⊕ Q sono l'una la negazione dell'altra. Il nome di implicazione di P ↔ Q trova giustificazione nella operazione seguente.


E' la funzione P → Q. Essa traduce il senso, talvolta vago, della nozione di implicazione nel linguaggio ordinario: quando P è vero, anche Q è vero (se piove allora ci sono le nubi): quindi P → Q è vero se P=1 e Q=1.
Inoltre, quando P è falso, niente impedisce che Q assuma un valore arbitrario 1 o 0 e quindi P → Q è considerata vera nei due casi in cui P=0. In breve: Q non può essere falsa quando P è vera.
Il simbolo P → Q si legge: P implica Q oppure P è una condizione sufficiente per avere Q.


La funzione F13 rappresenta in maniera analoga la funzione Q → P. Si consideri la proposizione (P → Q)∧(Q → P): si può costruire la tabella della verità affiancata.
La colonna di destra è la stessa di quella della operzaione P ↔ Q ciò che giustifica il simbolo e il nome di implicazione reciproca della operazione .




E' la funzione F7.
La proposizione P/Q è falsa quando P e Q sono entrambi veri , e vera in tutti gli altri casi. Questo giustifica il nome di Incompatibilità di P e Q.
Essa è anche uguale alla negazione della funzione F8.



E' la funzione F1.
La proposizione è vera quando ne P ne Q sono vere.
Essa è anche uguale a:

.


Una proposizione composta, che è falsa per tutti i valori logici possibili delle n proposizioni componenti, è una contraddizione.
Una proposizione composta che è vera per tutti i valori logici delle n proposizioni componenti, è una tautologia.

. Principio della doppia negazione (tautologia).


ogni proposizione equivale alla negazione della sua negazione.


Principio d'identità:
Ogni proposizione implica se stessa.


Principio del terzo escluso:

ogni proposizione è vera o falsa.



: contraddizione.
  • Ogni proposizione non può essere contemporaneamente vera o falsa.
  • Qualche proprietà delle funzioni AND, OR e negazione.
  • Nel seduito compaiono un certo numero di identità algebriche che legano le tre operazioni AND, OR e negazione (, , -).

Esse si presentano sotto forma di tautologie e di contraddizioni che figurano in certe identià.



















Esempi d'applicazione

Nell'algebra ordinaria perché un prodotto m = a x b x c sia ≠ 0 è necessario e suffciente che sia a ≠ 0, b ≠ 0, c ≠ 0.
Si ha dunque:


Inversamente perchèp sia m = 0:



Si consideri il prodotto M = a x b


la regola dei segni si scrivera:


inversamente:

Algebre Booleane


Si chiamera algebra di Boole o algebra Booleana il sistema:

dove:

  • 1) E è un insieme non vuoto che contiene almeno due elementi, e cioè 1 e 0,
  • 2) (+) e () sono due operazioni binarie definite su E e tali che E sia chiuso rispetto ad esse.
  • 3) su E è definita una relazione di equivalenza, rappresentata dalla notazione = (e si legge uguale), e come tale soddisfacente, alle seguenti relazioni.

e tale che, , risultano soddisfatti i seguenti assiomi:

Nei precedenti due capitoli, abbiamo studiato l'algebra dei circuiti, l'algebra delle classi e l'algebra della logica; tutte e tre queste algebre rappresentano esempi di strutture algebriche Booleane. La definizione assiomatica dell'algebra di Boole riassume infatti le regole di calcolo incontrate nello studio delle algebre su menzionate. Per quanto riguarda l'applicazione dell'algebra astratta di Boole, vogliamo fare un breve cenno ad alcuni risultati dell'algebra dei circuiti (più avanti considereremo esempi di applicazione). Partendo dalla constatazione che operazioni quali connettere in serie, connettere in parallelo due o più interruttori elettrici e invertire un interruttore (chiuderlo se esso è aperto, aprirlo se esso è chiuso), soddisfano a tutti gli assiomi Ai,j(i=1,..,5); J=1, 2) si giunge alla conclusione che ogni risultato , ottenuto in sede astratta pe le algebre di Boole, può essere tradotto in termini di interrruttori, o più in generale, di circuiti.


Gli assiomi precedenti ci permettono di dimostrare diversi teoremi. Per semplificare le dimostrazioni si scriverà a destra di ogni identità o equazione, gli assiomi o i teroremi utilizzati.
Si hanno i seguenti teoremi:


In maniera più generale si può dimostrare (per ricorrenza per esempio) che:



In maniera analoga si potrà generalizzare il risultato nella maniera seguente:

(T1) e (T2) costituiscono le proprietà di idempotenza; ossia che in un'algebra di Boole non vi sono ne multipli ne potenze.












Ragionando per assurdo, si supponga che l'elemento A possieda due componenti e . In virtù dell'assioma (A5)si avranno le relazioni:


Si ha allora:


Quindi A_1 e A_2 non possono che essere uguali.
Si chiama complementazione l'operazione che consiste nel far corrispondere l'elemento .



Si consideri l'elemento e si cerchi il suo complemento che verrà scritto .
Si avrà:


d'altra parte:


Si ha allora che soddisfano alle stesse equazioni e poiché per il teorema T9, il complemento è unico, segue che



Si cercherà il complemento di e si dimostrerà che esso è A+B.
Si consideri la quantità :


Analogamente si ha:



Dunque verificano le due equazioni:


per cui è il complemento (unico) di : dunque



Si consideri il secondo membro e se ne prenda il complemento:


Si consideri ancora il complemento dei due membri:



Si considerino le coppie degli assiomi Ai.j. Due assiomi di una qualunque di queste coppie si corrispondono nella maniera indicata nella tabella seguente (dove x rappresenta la variabile generica che figura negli assiomi).

Con questo procedimento , da un assioma di una coppia, si deduce l'altro.
Per esempio, a partire da A1.1:

si può scrivere immediatamente A1.2


Si dice che i due assiomi di una tale coppia sono duali: oppure che le identità che li esprimono sono duali. In generale, si chiameranno espressioni duali due espressioni algebriche che si deducono l'una dall'altra meddiante le regole della tabella precedente.


Il fatto che gli assiomi di un'algebra di Boole si raggruppino in coppie duali costituisce già una particolarità interessante. Ma più interessante è la considerazione che se ne trae sotto la forma detta del Principio di dualità. Si consideeri un terorema valido su un'algebra di Boole; per dimostrarlo si deve applicare una successione di operazioni che, in ultima analisi, è una applicazione , in tappe successive, degli assiomi. Se ora si sostituisce ad ognuna di queste operazioni intermedie l'0perazione duale, si otterrà, ovviamente, il risultato duale; si potrà quindi fare a meno di dimostrare il duale di un teorema.<bar/> Il principio di dualità si può cosi enunciare:
'Ad ogni teorema , vero in un'algebra di Boole, corrisponde un teorema duale che è altrettanto vero'.
Data una espressione E si indicherà con E l'espressione duale.



Si consideri un insieme I a due elementi: siano 0 ed 1; definiamo su questo insieme {0,1} 3 operazioni, date dalla tavola 6.1.


L'insieme {0,1} fornito delle operazioni +,*,neg ha una struttura algebrica Booleana:


Per giustificare tale asserzione, è sufficiente dimostrare che gli assiomi Ai.j sono soddisfatti.
Cominciamo col verificare gli assiomi A4.1 e A4.2.
In sede di definizione dell'algebra di Boole, si era detto che l'insieme E doveva essere composto da almeno due elementi, e che tali elementi devevano essere 0 e 1; per cui il nostro insieme I soddisfa a questa prima proprietà.
Passiamo a verificare ora la A4.1:


cioè, quale che sia l'elemento , associato con l'elemento mediante l'operatore (+), il risultato di tale applicazione deve essere ancora A. E questo si verifica puntualmente nel nostro insieme I; verifichiamo l'assioma A4.1 prima con l'elemento e quindi con l'elemento :


abbiamo cioè riottenuto gli elementi 1 e 0 sfruttando la definizione dell'0perazione (+) (vedi tabella 6.1a).
Analogo discorso si farà per l'assioma A4.2:


usufruendo della tabella 6.1b, che riguarda l'operatore () verifichiamo tale assioma per l'insieme I.


Per quanto riguarda l'assioma A5:


usufruendo della tabella 6.1, possiamo facilmente verificarlo ponendo A=1, A=0 e viceversa:


Lasciamo come esercizioal lettore la verifica dei restanti assiomi.



Un secondo esempio di algebra di Boole è quello costituito dall'insieme di tutti i sottoinsiemi di un dato insieme M quando per ∪, ∩ e −, si prendano rispettivasmente le ordinarie operazioni di riunione, intersezione e complementazione tra insiemi, e perle costanti 0 e 1 ris\ ettivamente l'insieme vuoto Φ e l'insieme delle parti IM:

Per vedere che gli assiomi Ai.j sono verificati è sufficiente considerare le relazioni incontrate nel capitolo.
Giova rilevare che M non è necessariamente finito; se lo è, se contiene cioè n (>2) elementi, l'algebra di Boole BM ne contiene 2n.



Consideriamo un insieme L di proposizioni, fornito delle operazioni tale che se , si abbia . In queste condizioni gli assiomi Ai,j prenderanno la forma delle relazioni (L1...L10): l'insieme L delle proposizioni, con le operazioni è un'algebra di Boole:


L'algebra delle proposizioni ha l'implicazione reciproca (↔) come relazione di equivalenza.



Si consideri l'insieme dei vettori binari ad n dimensioni. Un vettore binario (matrice riga) X è un insieme ordinato di variabili (componenti) capaci di assumere uno dei valori:0 e 1:


Questo insieme comprende:


Si possono introdurre le operazioni seguenti:
1) Prodotto
Dati due vettori X e Y

1) Prodotto
Dati due vettori X e Y



si chiama prodotto booleano di X e Y, denotato con , il vettore


2) Somma.
Dati due vettori X e Y definiti come sopra, si chiama somma booleana di X e Y il vettore:


3) Complemento:
Dato un vettore il complemento di X è il vettore:


Le operazioni +, ., -, sulle variabili x,y sono quelle definite nell'algebra a due elementi.
4) Vettore nullo Per definizione esso è un vettore formato unicamente da zeri:


5) Vettore unità
E' il vettore formato unicamente da 1:


In queste condizioni l'insieme dei vettori binari ad n dimensioni, fornito di queste tre operazioni, è un'algebra di Boole a 2n elementi, con 0 e 1 per elementi costanti:


Si può dimostrare l'asserto facendo vedere che gli assiomiA1.1 sono verificati per i vettori si troverà ogni volta che la dimostrazione si riporta alle componenti. Ora, per quest' ultime, gli assiomi sono verificati in quanto si tratta di un'algebra di Boole a due elementi.
Si verifichi per esempio l'assioma A1.1. Si ha:

(X+Y)+Z=X+(Y+Z)

ma ciò equivale a scrivere:


Per ogni i quest'ultima relazione è vera in quanto abbiamo visto che per le componenti gli assiomi sono verificati (algebra a due elementi).
Per l'equivalenza, discende che anche la proposizione vettoriale è vera.
L'assioma (A1.1) è dunque verificato.
In maniera analoga si dimostrano gli alti assiomi.


Variabile booleana: è una variabile i cui valori appartengono ad una algebra di boole. Le lettere che abbiamo usato nelle definizioni degli assiomi e dei teoremi fino ad ora, rappresentano tali variabili. Si dirà anche che l'algebra considerata costituisce il dominio della variabile.

Espressione booleana: si chiamerà espressione booleana, o forma booleana, ogni espressione algebrica formata, a partire dalle variabili e dalle costanti appartenenti ad un'algebra booleana, mediante un numero finito di applicazioni delle operazioni ( .
Più precisamente si può dire:

  • 1) 0 e 1 sono espressioni
  • 2) ogni variabile x è una espressione
  • 3) se A è una espresssione, anche lo è
  • 4) se A e B sono espressioni, anche A+B e A*B lo sono
  • 5) un'espressione può essere ottenuta applicando le regole1,2,3 e 4 un numero finito di volte.

Funzioni generate da una espressione.
Data una espressione booleana ad n variabili, e sia

,

se si sostituiscono le variabili con degli elementi particolari di E, che è l'insieme sostegno, si ottiene come risultato dell'espressione un elemento di E.
Si chiama assegnazione (dei valori alle variabili) ogni combinazione di valori particolari attribuiti alle variabili . L'elemento ottenuto, calcolando la G in corrispondenza dell'assegnazione , è il valore dell'espressione a tale assegnazione.
Sia data ad esempio l'espressione:


il suo valore per la combinazione ( 1,0,1 ) (cioè A=1, B=0, C=1) sarà:


Se si calcolano i valori dell'espressione in corrispondenza a tutte le possibili combinazioni dei valori delle variabili, si definisce una funzione di En in E. Si dirà allora che l'espressione G genera la funzione in questione e, inversamente, che G è un'espressione o una rappresentanza di fG.
Consideriamo ad esempio la funzione Somma di due variabili che, ad ogni coppia di valori, associa la loro somma; l'espressione sarà:


avremo:


in tal modo abbiamo definito la funzione somma; cioè la corrispondenza che, mediante S(A,B), viene generata tra E2 ed E.
Vi è inoltre da notare che un'espressione definisce un'unica funzione mentre, per una funzione data di En in E, esistono infinite (a causa, ad esempio, della legge di idempotenza) espressioni che la generano. Così nell'algebra


le espressioni


rappresentano la stessa funzione definita dalla tabella:

A B f(A,B)
0 0 0
0 1 1
1 0 1
1 1 0

Si dice che 2 espressioni sono uguali (o equivalenti) se esse assumono gli stessi valori per ogni assegnazione di valori delle vasrabili, cioè se esse generano la stessa funzione.
L'uguaglianza di due espressioni G e G' sarà rappresentata dal segno =. Si può verificare che essa è una relazione di equivalenza nel senso usuale.


Come si è detto precedentemente, una funzione booleana può essere rappresentata da infinite espressioni algebriche; tra tutte queste però, ve ne sono due particolari che prendono il nome di forme canoniche: Per giungere alla definizione di tali forme, occorre enunciare il seguente teorema:


Ogni espressione booleana di una variabile si può sempre esprimere medfiante una espressione del tipo:


dove con F(1) e F(0) s'intende la funzione calcolata per i valori 1 e 0 della variabile.
Verifichiamo la validità di tale teorema perle funzioni base:

a)Funzioni costanti: F(x)=A, in tal caso l'espressione è indipendente dal valore della variabile; si ha cioè:

per cui applicando gli assiomi visti nel paragrafo 6.1 si può scrivere:

.

b)La funzione assume il valore della variabile x: P(x)=x; avremo:

per cui:

c)La funzione assume il valore della variabile complimentata: avremo:

per cui:

Tenendo presente che ogni espressione booleana non sarà altro che una combinazione delle tre espressioni a), b), c), si può dimostrare la validità del teorema di Shannon per ogni espressione di una funzione ad una variabile. Per ottenere ciò è sufficiente far vedere che: date due funzioni F(x) e G(x) verificanti la (), allora anche il loro prodotto, la loro somma, ed il complemento di una di esse la verificano.

d) Sia H(x)=F(x)*G(x) e quindi H(1)=F(1)G(1) e H(0)=F(0)G(0) applicando la su F(x) e G(x) otterremo:

e) Sia K(x)=F(x)+G(x) quindi

applicando la () su F(x) e G(x) otterremo:


f) Sia e quindi

applicando la () su F(x) e per il primo e secondo teorema di Morgan avremo:








Abbiamo così dimostrato che le operazioni , in una espressione di una funzione booleana, conservano la proprietà di Shannon e ciò ci permette sempre di ridurre l'espressione ad una forma lineare ed omogenea nelle variabili e :

nella quale compaiono solo due costanti F(1), F(0) facilmente determinabili data l'espressione della funzione.


E' possibile enunciare il teorema di Shannon anche per espressioni ad n variabili: ma prima di fornire tale enunciato, esponiamo il procedimento con cui si giunge a tale generalizzazione del teorema.
si consideri una espressione ad n variabili:

e si supponga di fissare (cioè considerare costanti) n-1 variabili: l'espressione F è allora una espressione ad una variabile, che gode quindi della proprietà di Shannon e può, di conseguenza, essere espressa nella forma:

I termini sono, non considerando più costanti, delle espressioni ad n-1 variabili, nelle quuali noi possiamo di nuovo fissare momentaneamenten n-2 variabili, per esempio le ultime n-2, ed applicare ancora alla variabile x_2 il teorema di Shannon. Da cui:





Si può continuare ad applicare il teorema di Shannon fino all'esaurimento delle variabili; infine si otterrà la seguente espressione:

con la convenzione:

ed vettore binarioad n dimensioni.
Per scrivere in maniera più compatta, si può pensare di considerare "e" come la rappresentazione binaria di un numero.
Da ciò la notazione abbreviata:

ed ora possiamo enunciare il teorema di Shannon per espressioni ad n variabili:

ogni funzione booleana di n variabili, si può sempre
esprimere mediante una espressione del tipo .

La forma algebrica del secondo menbro di porta il nome di forma canonica disgiunta, volendo indicare con questa terminologia, cher essa è una somma di prodotti.
In essa compaiono i possibili coefficienti F(e) ed altrettanti monomi della forma:

Una espressione booleana ad n variabili è quindi conosciuta quando si hanno i coefficienti di F(e).
Un prodotto della forma si chiama prodotto fondamentale.

Espressioni duali

Applicando il principio di dualità si deducono le formule seguenti:

(teorema di Shannon duale) da cui:

che prende il nome di forma congiuntiva.
Essa è un prodotto di somme. Le somme della forma:

sono chiamate somme somme fondamentali.
In maniera più compatta si scriverà:

dove = complemento ad 1 di e.



Consideriamo l'espressione . Per calcolare il complemento non è necessario applicare passo passo i teoremi di De Morgan: è sufficiente sostituire l'espressione con l'espressione , ottenuta con le regole seguenti:

Si noterà che questa tabella è differente, nelle ultime righe, da quella che definisce la regola di dualizzazione:


Per definizione si ha:

Per semplificare tale espressione si può applicare il teorema di De Morgan oppure la regola sopra enunciata; applichiamo entrambe, e confrontiamo l'uguaglianza dei risultati.







come si vede questo secondo metodo è molto più rapido.


<br/

Data una espressione che comporta più livelli di complementazione sovrapposti, come ad esempio:

è sempre possibile ricondurre una tale espressione ad una forma dove le complementazioni appaiono, al massimo, ad un livello.
Che ciò sia sempre possibile è una conseguenza dell'esistenza delle forme canoniche.
Comunque, applicando ripetutamente i teoremi di De Morgan, si può verificare tale affermazione senza dover ricorrere4 alle forme canoniche.
Per l'espressione precedente si avrà:

}

cioè si è ottenuta una espressione dove gli elementi sono complimentati al massimo una volta.
Tale espressione si potrà sviluppare in somma di prodotti:



Data una espressione di una funzione le tavole delle regole di dualizzazione e di complementazione permettono di dedurre due espressioni associate alla funzione data:



La relazio0ne che lega queste due funzioni è

i procedimenti per costruire le espressioni F,sim F,\bar F possono essere riassunte nella tabella a fianco.
F è costituita da un numero finito di operazioni +, *, -, a partire dalle variabili e dalle costanti 0 ed 1; e si vede che applicando passo passo la corrispondenza della tabella, la relazione è verificata.

Funzioni Booleane


Si definisce variabile binaria, quella variabile che ha per dominio l'insiema {0,1} composto di 2 elementi. Il prodotto cartesiano di tale insieme per se stesso, cioè l' insieme delle coppie ordinate (a1,a2)di elementi in {0,1}, verrà indicato con {0,1}2 = {0,1}x{0,1}.
Iterando ilragionamento, l'insieme {0,1}n={0,1}x{0,1}x...{0,1} sarà composto dalle n-ple ordinate a1, a2...an), di elementi in {0,1}. A questo punto è possibile definire la funzione booleana di n variabili(od anche funzione binaria, o funzione di commutazione) come una applicazione di {0,1}n in {0,1}.
Abbiamo già detto che una funzione booleana piò essere espressa o mediante una classe di espressioni booleane equivalenti, oppure mediante una tabella della verità nella quale in corrispondenza di ogni combinazione delle n variabili deve scrivere il valore associato della funzione. Se si assume come convenzione di scrivere le combinazioni delle n variabili in ordine crescente, cioè in modo tale che leggendole come numeri binari, esse rappresentino la sequenza di numeri da 0 a 2n-1, allora non sarà necessario scrivere tutta la tabella, ma risulterà sufficiente scrivere solo i valori della funzione.


Le tabelle della verità possono essere anche ‎di tipo rettangolare, e cioè le n variabili sono ripartite in due insiemi disgiunti (x1,...,xs) e (x{s+1},...,x{n})
A ciascuno dei due insiemi si assegna una delle due dimensioni del rettangolo e su di essa l'insieme di variabili assume tutte le possibili combinazioni: ad ogni combinazione corrisponde una colonna (o una riga).
Spieghiamo con un esempio il funzionamento del nuovo tipo di tabella, paragonandolo alla tabella usata fino ad ora nella quale però, per brevità, non prenderemo in esame le combinazioni che corrispondono ad un valore nullo della funzione.
Sia f(x1, x2, x4, x5) definita dalla tabella (a) a fianco:



Volendo riscrivere la tabella , questa volta in forma rettangolare procediamo prima nel seguente modo:
Consideriamo , ad esempio, la 5a colonna. Ad essa corrisponde l'assegnazione (x1, x2, x3)=(100) ed alla 2a riga corrisponde l'assegnazione (x4 x59=(01). Se ora consideriamo contemporaneamente le due assegnazioni, esse corrispondono all'unica (x1, x2, x3, x4, x5)=(10001). A tale combinazione , nella tabella (a), corrisponde il valore 1 (della funzione); Nella tabella b (a fianco), allora, scriveremo all'intersezione della 5a colonna con la 2<sbr/> up>a riga il valore 1.


La tabella completa avrà la forma della tabella b2 accanto:
E' sotto questa forma che utilizzeremo soprattutto le tabelle della verità: messa infatti sotto questa forma conveniente (diagramma di Karnaugh), una simile tabella è un mezzo per la semplificazione delle espressioni algebriche.
Inoltre questa forma serve ogni qualvolta si vuole mettere in rilievo il ruolo di una certa variabile; in tal caso le si attribuirà un lato della tabella.



La colonna di desrta della tavola della verità, del 1° tipo , è un vettore binario.


Se si conservano le convenzioni fatte sulle combinazioni delle variabili, la conoscenza di questo vettore è sufficiente a definire la funzione. Chiameremo tale vettore vettore caratteristico della funzione f e lo denoteremo con:


dove Vk è il valore della funzione associata a quella combinazione binaria delle variabili, che rappresenta il numero k. (Esempio figura accanto)




Il Vettore Vf costituisce la rappresentazione binaria di un numero intero compreso tra 0 e 2n-1.
Si può allora definire la funzione mediante l'equivalenza decimale di questo numero:






Forniamo una 2a rappresentazione del vettore caratterisistico: rappresentazione molto usata anche se meno compatta della prima
Se si esamina l'esempio 1°, si vede che il vattore caratteristico assume il valore 1 in corrispondenza a quelle combinazioni che rappresentano i numeri decimali 0,2,5,6. Allora si può rappresentare il vettore caratteristico, fornendo quest'insieme di valori decimali.





Usando le tavole della verità, che ci permettono di definire le funzioni booleane, possiamo ora definire le operazioni di somma, prodotto e complementazione delle funzioni.


Date le due funzioni f e g, ad n variabili, con i vettori caratteristici Vf e Vg, la funzione somma di f è g è quella il cui vettore caratteristico è Vf+Vg (vedi 6.4.4).
Si ha dunque per definizione:



In maniera analoga , il prodotto di f e g è la funzione di vettore caratteristico Vf*Vg:





E' la funzione notata e definita mediante
Per definizione si ha quindi:



E' la funzione il cui vettore caratteristico è il vettore nullo.


E' la funzione il cui vettore caratteristico è il vettore (1).


L'insieme delle funzioni booleane ad n variabili possiede 2n elementi distinti.Infatti ogni vettore caratteristico è formato da una sequenza di 2n elementi: l'insieme delle funzioni sarà dato da tutte le possibili combinazioni (disposizioni con ripetizione) di questi 2n elementi; per cui avremo 22n vettori distinti.
E' mediante l'aiuto dei vettori caratteristici che noi abbiamo definito sull'insieme delle funzioni booleane le operazioni +, *, -.
Questi ultimi formano un'algebra di Boole a 2N = 22n elementi e quindi segue che l'insieme delle funzioni di n variabili, munite di queste operazioni, formano ugualmente un'algebra di Boole a 2N elementi.


Esaminiamo ora il seguente problema: data una funzione booleana di n variabili x1...xn conosciuta mediante la sua tavola della verità, trovarne una rappresentazione algebrica.
Per fare ciò definiamo alcune funzioni di n variabili che ci saranno utili in seguito.


: Si chiama prodotto fondamentale o minterm ad n variabili un prodotto della forma:

con
con

In altri termini un prodotto fondamentale è un prodotto di n variabili (dirette o complamentate) in cui ogni variabile compare una sola volta.



Affinché il prodotto


sia uguale ad 1, è necessario e sufficiente che tutti i suoi fattori siano uguali ad 1.
Cioè che si abbia:


Ora con riguardo a quanto detto nel par.6.6 si ha:


Quindi perché =1, è necessario e suffciente che xi=ei.

Per cui affinché P=1 è necessario e sufficiente che si abbia:


Il prodotto fondamentale P è dunque uguale ad 1 quando le variabili assumono le cmbinazioni (e1, e2,...en); cioè quando si ha che:


Per esempio, il prodotto fondamentale assumerà il valore 1 solo per la combinazione (1 0 1); cioè, se esprimiamo tale prodotto sotto forma di tabella, avremo (tabella affiancata):
Diremo che una funzione è generata da un prodotto fondamentale, quando la sua tabella (o il vettore caratteristico è del tipo di cui alla tabella mostrata, e rappresentiamo la funzione con l'espressione:


dove e1....en è la combinazione di valori per cui il prodotto fondamentale risulta uguale ad 1.


Consideriamo ora la funzione a tre variabili definita dalla tabella A e prendiamo in esame le tre funzioni f1,f2, f3 definite dalla tabella B: ora, confrontando i vettori Vf, V{f1}, V{f2}, V{f3}, è facile verificare che le quattro funzioni soddisfano la seguente reelazione:


dove le f1, f2, f3, sono generate, ciascuna, da un prodotto fondamentale. Indichiamo quest'ultimo prodotto con mabc, dove abc è la combinazione binaria che rende uguale ad 1 tale prodotto; cioè avremo:


Se ora consideriamo i tre prodotti fondamentali che generano le funzioni f1,f2,f3, e trasformiamo il numero binario abc in decimale, avremo le seguenti notazioni:




ed inoltre , essendo le tre funzioni generate da tali prodotti, si può scrivere:


da cui


E' chiaro che il ragionamento effettuato nel caso di tre variabili e su di una funzione particolare , vale anche in generale; e che ogni funzione booleana si può esprimere come somma booleana dei prodotti fondamentali.
Per fare ciò si seguiranno le seguenti regole:

  1. - si scrivono tutti i prodotti fondamentali corrispondenti alle combinazioni delle variabili per le quali la funzione f(x1...xn) vale 1.
  2. - si forma la somma booleana di tutti questi prodotti.

L'espressione così ottenuta, costituisce una rappresentazione algebrica della funzione, chiamata prima forma canonica o forma canonica disgiuntiva.>br/> Si ha:


La prima forma canonica è unica: il carattere di unicità risulta direttamente dalla corrispondenza biunivoca che esiste tra i prodotti fondamentali componenti la forma canonica e le combinazioni binarie della tabella della verità per le quali la funzione vale 1.


Si voglia determinare la forma canonica disgiuntiva della funzione f definita dalla tabella relativa.
Per fare ciò, determiniamo prima i tre prodotti fondamentali:


<bar/>

da ciò ne discende che la forma canonica disgiuntiva della funzione sarà:


Si chiama somma findamentale, o maxterm una espressione della forma:

dove, per le xiei, valgono le convenzioni fatte precedentemente.
In altri termini, una somma fondamentale ad n variabili è una somma delle n variabili (dirette o complementate) dove ciascuna dellexi compare una sola volta.


Affinché la somma:

sia nulla, è necessario e sufficiente che tutti i suoi termini siano nulli: cioè che si abbia:

unque, perché S sia nulla, è necessario e sufficienteche la combinazione delle variabili sia identica a quella dellle ei complementate.
Riassumendo: la somma S ha una tavola della verità che è nulla in corrispondenzaad una sola combinazione delle variabili:

e vale 1 per tutte le altre.
Inversamente , ogni funzione avente una tavola della verità di questo tipo, cioè nulla per una sola combinazione (a1,a2,...,an) delle variabili, potrà essere rappresentata con una somma fondamentale:

cioè se (a1 a2...an) è l'unica combinazione che annulla la f potremo scrivere tale funzione come somma delle xi aventi, per indice superiore, i valori complementari della n-pla.

.

à1- La somma fondamentale

è nulla per la combinazione 0110 e per questa soltanto.
2- Si consideri la funzione definita dalla tabella affiancata: essendo 011 l'unica combinazione che annulla la f si può scrivere:




3-Si considerino le funzioni f,f1,f2,f3 definite dalla tabella sulla destra:
esaminando 9 vettori caratteristici delle funzioni si vede che si può scrivere f=f1 f2 f3, dove f1, f2, f3, sono funzioni generate da somme fondamentali associate agli zeri della colonna f
Si ha inoltre che:

da cui

.


Ragionando come nel caso della forma disgiuntiva, si vede che ogni funzione potrà essere espressa come un prodotto di somme fondamentali, utilizzando le regole seguenti:

  1. scrivere tutte le somme fondamentali corrispondenti alle combinazioni per le quali la funzione f=(x1...xn) vale zero.
  2. scrivere il prodotto di queste somme.


L'espressione così ottenuta, costituisce una rappresentazione algebrica della funzione, chiamata: seconda forma canonica o forma canonica congiuntiva.
Si scriverà in generale:



Si voglia determinare la forma canonica congiuntiva della funzione tabellata a fianco:
Le somme fondamentali sono:

e la funzione f avrà la seguente forma canonica congiuntiva:

La seconda forma canonica, come la prima, è unica. Ciò discende dall'identico processo logico seguito.
Un'altra considerazione è che nella forma canonica disgiuntiva i termini il cui coefficiente risulta essere scompaiono se f è nulla. Nella forma canonica congiuntiva, i fattori scompaiono dal prodotto quando vale1, cioè quando il fattore è della forma

.



Prodotti fondamentali:

dove è un indice espresso nella base decimale e tale che , mentre è la sua rappresentazione binaria.

in quantoi e j sono i numeri che corrispondono all'unica combinazione binaria che rende uguale ad 1 il prodotto fondamentale.
Somme fondamentali:

dove per vale quanto sopra.

Forma canonica disgiuntiva

Forma canonica congiuntiva



Data una funzione , si chiama funzione duale la funzione che soddisfa alla relazione

Proprietà

1- duale di una funzione duale

infatti

2- duale di una somma
3- duale di un prodotto
4- duale di un complemento
5- duale di una funzione costante

Poiché stiamo considerendo un'algebra a due elementi 0 e 1, le funzioni costanti possono assumere solo l'uno o l'altro di questi due valori, per cui se:

allora si ha che

in quanto il valore di una funzione costante non dipende dall'assegnazione delle variabili. Risulta allora:

Nella stessa maniera si ha che se

allora

Riassumendo possiamo dire che, data una espressione rappresentante una funzione, si ottiene l'espressione della funzione duale sostituendo a + con , con + e lasciando le variabili (complementate o no) tali e quali e sostituendo 0 con 1, e 1 con 0; regole che sono le stesse viste nel capitolo 6 in generale.



Nel capitolo 5 sono state definite le funzioni di AND, OR, PEIRCE, SHEFFER, di due argomenti; vogliamo ora dedfinire di nuovo tali funzioni attribuendo loro n argomenti. <con ciò non intendiamo dire che la singola funzione opera ripetutamente fino all'esaurimento delle variabili, bensì che essa viene considerata una operazione n-aria che opera contemporaneamente sulla n-pla di argomenti.
Questa osservazione rivela la sua importanza in considerazione del fatto che non tutte le funzioni sopranominate godono della proprietà associativa e quindi, se la funzione non opera contemporaneamente su tutti gli argomenti, otterremmo risultati diversi a seconda delle associazioni fatte, e di conseguenza arbitrari.


E' la funzione che vale

si scrive


E' la funzione che vale

si scrive


E' la funzione che vale

e si scrive

questa funzione è definita anche per n=1 cioè:

Per la funzione PEIRCE non vale la legge associativa.


E' la funzione che vale

si scrive

anche la funzione di SHEFFER è definita se n=1 cioè , e non gode della proprietà associativa.




Tenendo presente le definizioni ora date, vediamo che la funzione PERIRCE vale 1 per una sola combinazione di valori delle variabili, ma allora possiamo facilmente scrivere tale funzione, mediante la 1a forma canonica, come il prodotto fondamentale m0 cioè:

o ancora ,tenendo presente le regole della complementazione

Viceversa, la funzione di SHEFFER, si annulla in un solo caso; quindi possiamo esprimerla facilmente, mediante la 2a forma canonica, come la somma fondamentale M0 cioè:

o ancora, tenendo presente le regole della complementazione




Consideriamo la funzione di PEIRCE ad n variabili.
Si può scrivere:

Dunque la funzione duale della funzione di Peirce () è la funzione di Sceffer (/).
Viceversa: considerando la funzione di Sheffer x1/x2/.../xn ad n variabili, si può scrivere:

Quindi la funzione duale di Sheffer (/) è la funzione di Peirce .
Consideriamo la finzione di Peirce espressa mediante l'operazione (*), si ha: complementando ambo i membri si ottiene:

ma la funzione di Sheffer era stata espressa mediante una somma cioè:

da cui confrontando la (a) con la (b) risulta:

Ripetendo il ragionamento sulla funzione di Sheffer, espresso mediante la somma si ottiene:

Le ultime due relazioni generalizzano in un certo senso la formula di De Morgan:


Pseudo associatività

Come abbiamo già detto, gli operatori di Sheffer e di Peirce non sono associativi. Consideriamo le espressioni:


si ha che , infatti:


Dunque, per un insieme di dati valori ABC, F e F' non sono necessariamente uguali. In altri termini l'operazione non è associativa. Si vedrà in maniera analoga che l'operazione / non è associativa.
Tuttavia tali operatori godono di una notevole proprietà detta pseudo associatività:


dimostrazione

Queste proprietà si generalizzano, nel caso di n variabili, come segue:



Dalla definizione dell'operatore si deducono le seguenti relazioni:







Operazione

ponendo <

Operazione (+)

In maniera analoga si ha :


ponendo

Complemento (-)

E' facile verificare dalle definizioni che

Analogamente:

Inoltre grazie a delle proprietà già viste è possibile esprimere il complemento anche nel modo seguente:


}

Da ciò è facile vedere che:



A partire dalle due forme canoniche è facile ottenere delle espressioni utilizzanti e /, che si possono chiamare forme canoniche di Sheffer.
Consideriamo la funzione F a tre variabili, A,B,C, definita dalla tabella collaterale.
Per la prima forma canonica abbiamo che:

a) possiamo allora scrivere:

(teorema di De Morgan e doppia negazione)
Per la definizione di / si ha:

Quindi: conoscendo la prima forma canonica, si ottiene una espressione della funzione mediante l'operatore di /, sostituendo semplicemente tutti i segni operativi (+), (*) con / e racchiudendo tra parentesi i gruppi di lettere corrispondenti ai prodotti fondamentali.

b) Consideriamo ora la seconda forma canonica:

possiamo scrfivere:


Donde la regola:

a partire dalla seconda forma canonica, si ottiene una espressione della funzione
medianter l'operatore sostituendo (+), con ( e racchiudendo in parentesi i gruppi corrispondenti alle somme fondamentali della seconda forma canonica.



Anche questa funzione l'abbiamo incontrata già, e sommariamente trattataal capitolo 5.3.
Oltre che con il nome di OR esclusivo, questa funzione la si può incontrare anche sotto il nome di inequivalenza, dilemma e addizione modulo 2.Mentre i primi tre nomi traggono origine dall'algebra delle proposizioni, addizione modulo 2 trova la sua giustificazione nel fatto che: se si considera come risultato di una somma la classe resto mod.2 a cui appartiene il risultato vero, allora si ottengono gli stessi valori della funzione XOR, cioè:

Rappresentazione geometrica delle funzioni booleane e loro minimizzazxioine

8.1

I diagrammi di Venn sono una rappresentazione grafica delle relazioni tra insiemi, ed in particolare , delle operazioni di unione, intersezione e complementazione. Si è visto inoltre che ogni algebra di insiemi con le operazioni sopra citate è un'algebra du Boole. Ne segue che questi diagrammi di Venn possono essere utilizzati per rappresentare le operazioni sulle funzioni di commutazione che formano esse stesse un'algebra di Boole. Per fare ciò è sufficiente utilizzare la seguente corrispondenza tra gli insiemi e le funzioni booleane: ad ogni insieme Ei si associa la funzione cararreistica Xi.
Questo comporta la corrispondenza tra operazioni su insiemi e funzioni caratteristiche:




Dati n insiemi E1...En rappresentati su un diagramma di Venn, essi definiscono 2n sottoinsiemi caratterizzati dalla loro inclusione o non inclusione in ciascuno degli insiemi E1...En.


Ogni insieme esistente nel diagramma di Venn può essere definito mediante una selezione degli insiemi E1...En:br/>



La funzione caratteristica E definita nella tavola (8.1) è quindi rappresentata dall'insieme E dal diagramma di Wenn (8.2).
E è dato dagli insiemi colorati.
L'insieme E può essere anche definito mediante una espressione:



se ne deduce per X l'espressione:



Ci proponiamo di semplificare le espressioni di E e di X





=
=
=

Ma la semplificazione si può ottenere anche osservando che l'insieme E può essere ottenuto come:

1)riunione di 4 insiemi disgiunti (8.2a)
2)riunione di 3 insiemi disgiunti (8.2b)

Considerando quindi semplicemente il diagramma di Wenn si ottiene:


espressioni ottenute in precedenza in via algebrica.
Riassumendo, il digramma di Wenn permette di sostituire le operazioni algebriche con l'esame delle configurazioni geometriche, e questo metodo può essere utilizzato soprattutto per la semplificazione delle espressioni.


8.2

Esporremo ora il metodo per la semplificazione delle funzioni dovuto a Karnaugh. Tale metodo ci permetterà di eseguire le minimizzazioni con una certa speditezza , ed è conveniente applicarlo a funzioni con al massimo 6 variabili.
per poter applicare questo procedimento, è necessario conoscere le rappresentazioni delle funzioni col metodo di Karnaugh. Rappresentazioni che permettono di visualizzare una funzione sotto forma di superficie e sono una applicazione della teoria degli insiemi-Nelle tavole della verità abbiamo visto che, nelle colonne delle variabili, ad ogni riga corrisponde un valore possibile della variabile presa in considerazione.
Nei diagrammi di Karnaugh, anziché far corrispondere una riga, per ogni valore della variabile, si fa corrispondere una superficie delimitata da un quadretto. Costruiamo per esempio il diagramma di Karnaugh per una funzione X dipendente da due variabili:




La tavola (8.2) della verità di questa funzione ha quattro righe, corrispondenti alle 4 possibili combinazioni dei valori assunti dalle variabili.



Il diagramma di Karnaugh corrispondente avra due righe e 4 caselle, essendo i valori di A (prima variabile) posti sopra le caselle orizzontalmente ed i valori della seconda variabile posti a fianco in verticale.
Nei quadretti interni distribuiremo i valori assunti dalla funzione. La tavola della verità (8.2) avrà il diagramma affiancato.






La tavola della verità della funzione a tre variabili ha 8 righe.






Il corrispondente diagramma di Karnaugh avrà 8 caselle, ognuna associata ad una delle 8 combinazioni possibili, poste su due colonne e 4 righe. Ad una variabile si assegnano le due colonne, una per il valore 0 l'altra per il valore 1; alle altre variabili si fanno corrispondere le 4 righe, ognuna relativa alle combinazioni:

0 0, 0 1, 1 1, 1 0

Notiamo che nella tavola della verità le combinazioni sono:

0 0, 0 1, 1 0, 1 1

mentre nei diagrammi di Karnaugh avremo le ultime due cifre invertite (vedere tabella 8.4).
Poiché ad ogni casella corrisponde il valore che la funzione assume per i particolari valori delle variabili, è stato scelto opportunamente l'ordine delle righe, per fare in modo che, passando da un quadratino al successivo, si abbia il cambiamento di una sola variabile.



Una tabella della verità a quattro variabili ha 16 righe corrispondenti a tutte le possibili combinazioni. Il Diagramma di Karnaugh avrà 16 caselle, disposte su quattro righe e quattro colonne. Si assegneranno le quattro colonne alle possibili combinazioni delle prime due variabili e le quattro righe alle combinazioni 00,01, 11, 10 delle altre due.
Se le variabili fossero 5 o 6 si userebbero dei Diagrammi multipli: la forma cui proposta non è l'unica ma quella di uso più corrente.





Parte II

Circuiti logici e calcolatori digitali

circuiti logici e di memoria

1.1 Rappresentazione di una informazione digitale.

1.1.1 Struttura fondamentale dei circuiti digitali.

Si distinguono nei circuiti digitali, tre tipi fondamentali:

  1. Circuiti di memorizzazione: cioè capaci di ricevere, conservare, restituire i segnali delle informazioni.
  2. Circuiti operatori: cioè capaci di realizzare le funzioni booleane a partire dai segnali delle informazioni.
  3. Circuiti di connessione: cioè capaci di trasferire i segnali.

Nella forma più semplice la struttura unitaria è composta di:

-due circuiti di memorizzazione (A,B) in cui sono conservate delle informazioni (I1,I2) e capaci di emettere i corrispondenti segnali (i1,i2).
-un operatore capace di realizzare la funzione dei segnali tali che:

-un circuito di memorizzazione (C) che riceve il segnale (i3) emesso dall'operatore e capace di conservare l'informazione corrispondente I3.<br/
-connessioni tra questi circuiti.



Un segnale i, rappresentativo di una informazione I, sarà una grandezza fisica suscettibile di assumere nel tempo due diversi valori determinati dai circuiti emettitori e operatori.
Si cercano in genere quei dispositivi , legati a grandezze fisiche, capaci di assumere due distinti sati di eqwuilibrio stabile.
Una generica informazione sarà rappresentata da un insieme di segnali elementari. Nei calcolatori elettronici moderni i segnali rappresentativi delle informazioni, sono generalmente costituiti da tensioni o correnti elettriche.

-Segnali elettrici rappresentativi delle informazioni.

Precisiamo il senso booleano che si può attribuire ad un segnale trasmesso nell'insieme dei componenti di un calcolatore digitale. Consideriamo un segnale elettrico variabile nel tempo (ad esempio, una tensione): A=V(t).
Consideriamo due livelli di riferimento m0 e m1 con la seguente convenzione sulla informazione binaria contenuta in V(t):

Naturalmente le cifre binarie 0 ed 1 non implicano che l'informazione sia espressa nella base 2, ma solo che l'informazione è espressa in un linguaggio a due distinti valori che potrebbero essere rappresentati dagli elementi di una generica coppia (+,-), (0,-).
La differenza fra i due livelli è determinata dal potere risolutivo degli strumenti e determina a sua volta la differenza fra massima e minima ampiezza dei possibili segnali.

Considerando la figura 1.2 notiamo che, nel tempo, il segnale è:

perfettamente definito in uno dei due possibili valori negli intervalli
(t2,t3),(t6,t7),(t4,t5,t8),(t7),...
indeterminato negli intervaali
(t1,t2),(t3,t4),(t5,t6),(t7,t8),...

e di conseguenza il segnale deve essere utilizzato solo in istanti ben determinati dagli intervalli di ambiguità.


1.1.2 Strutture sequenziali

L'analisi tecnica dell'andamento temporale del segnale, in funzione dei componenti del circuito e nelle condizioni più sfavorevoli, corrispondenti a zone di ambiguità di maggiore larghezza, permette di stabilire gli intervalli temporali entro i quali ha senso esaminare il valore dell'informazione.
Il succedersi, nel tempo, di questi intervalli, può essere regolare o irregolare. Nel secondo caso, si parla di circuiti asincroni ed è il funzionamento interno di ogni circuito che determina gli intervalli opportuni.
Più frequentemente siha una ripetizione regolare nel tempo di tali intervalli (circuiti sincroni) con periodo Θ. Si può dire che , durante l'intervallo di tempo di un periodo binario, il segnale è atto a rappresentare una informazione binaria elementare. Oggi si superano valori di periodo corrispondenti ai 10 nano-secondi (=!0-9 sec).

Consideriamo adesso una informazione rappresentata da impulsi secondo la convenzione:

cioè avendo sostituito alla nozione di livello rappresentativo quella di presenza o assenza di impulso.
Nella figura si è riportato un segnale ideale di impulso, cioè privo di zone di ambiguità, per mettere in evidenza che esistono altre cause per le quali il segnale è significativo solo in brevi intervalli di tempo, e cioè si deve escludere anche il tempo che il segnale impiega per ripristinare la condizione iniziale (eventuale ritorno a zero).
Gli intervalli di tempo significativi sono scanditi con un segnale di riferimento H, detto segnale di orologio. Si può aggiungere che il segnale di orologio è rappresentativo della tautologia.


1.1.3 Convenzioni della logica

La scelta che, nel caso appena visto, ha associato il valore 1 alla presenza di impulso, è arbitraria. Distinguiamo una logica (intesa qui in pratica come metodo di

realizzazione elettronica di operatori logici) positiva, relativa alla convenzione di associare il valore 1 al livello più alto (+) ed una logica negativa alla convenzione il valore 0al livello inferiore (-).
In generale , se con una convenzione si ha funzione booleana, con la convenzione opposta si ha la funzione duale, infatti:



1.1.4 Porte e livelli

Ai circuiti che realizzano i vari operatori logici si da il nome di porte. Nella figura si anno il simbolo in standard DIN (acronimo di Deutsches Institut fuer Normun) di complementazione e quelli, pure in standard DIN, di AND, OR, XOR, NOR, NAND a tre ingressi.
Si da nome di livelli ai successivi stadi determinati dagli operatori elementari, attraverso i quali passa il segnale prima di giungere alla realizzazione del segnale risultante.
Considerando le funzioni booleane si vede che ad ogni livello si ha un cambiamento di forma (disgiuntiva o congiuntiva).


Esempio: consideriamo la funzione

Si hanno 4 livelli e 7 porte:

La nozione di livello è molto importante dal punto di vista tecnico, essendo il numero dei livelli pari al numeto massimo di porte attraversate successivamente da un segnale fornisce una stima del tempo di propagazione del segnale.
Notiamo infine che non tutti i segnali devono necessariamente percorrere lo stesso numero di livelli. In una tecnica sincrona è necessario per tenerne conto compensare le differenze con opportuni ritardi.
Ogni forma booleana elementare richiede, per essere realizzata, almeno due livelli di operatori elementari.


1.1.5 Circuiti combinatori e circuiti sequenziali


Un circuito di commutazione è un circuito i cui segnali seguono una logica a due valori, come nel caso booleano. Distinguiamo due tipi di circuiti: combinatori e sequenziali.
Un circuito combinatorio è un circuito tale che ad ogni insieme di stati d'ingresso completamente specificato fa corrispondere un ben determinato insieme di stati d'uscita. Ad uno stesso insieme di stati in uscita possono corrispondere più insiemi di stati in ingresso.
Ad esempio, i circuiti in figura (1), (2), (3) e (4):

Un circuito sequenziale è un circuito per il quale delle variabili interne, associate ad elementi di memoria, intervengono nella funzione di uscita. L'insieme degli stati di uscita è quindi una funzione non solo delle variabilidi ingresso, ma anche degli stati precedenti.


1,2 Circuiti di memoria
1.2.1 Introduzione del tempo nelle funzioni booleane

La nozione del tempo è indissociabile dalla formulazione delle funzioni in dipendenza dalla evoluzione temporale delle operazioni.
Notiamo che l'algebra di Boole non permette di introdurre il tempo come variabile indipendente nella formulazione delle funzioni.
Ciò costituisce un inconveniente soprattutto nello studio dei circuiti sequenziali; per lo più si cerca di ricondurre lo schema di un circuito sequenziale a quello di un circuito combinatorio in cui gli insiemi di stato delle variabili sono legati da un ordine logico dipendente dal tempo.
Per lo studio dei circuiti digitali si opera una discretizzazione del tempo in intervalli (regolari o non). L'insieme di questi intervalli costituisce la sequenza temporale fondamentale:




1.2.2
  • Ritardo

Come prima conseguenza dell'introduzione del tempo, bisogna determinare dei circuiti atti a restituire una informazione in un intervallo di tempo diverso da quello della sua formazione.
Un primo procedimento di spostamento nel tempo di una informazione consiste nel fare percorrere al segnale rappresentativo, un elemento di ritardo tale che il segnale risultante sia sempre rappresentativo della stessa informazione:


Esprimiamo la funzione di ritardo tramite un operatore Δ che agisce sulla sequenza temporale:

(essendo X il ritardo scritto in numero di periodi Θ della sequenza temporale) si ha:

L'operatore Δ è commutativo e associativo.

  • Funzioni sequenziali elementari.

Combinando l'operatore Δ con una generica operazione booleana si realizza una funzione sequenziale elementare, cioè una funzione booleana in cui il tempo interviene come variabile indipendente.

Ad esempio:


1.2.3
  • Circuiti chiusi (o ad anello)

La combinazione dell'operatore Δ e di operatori booleani conducono alla realizzazione di particolari funzioni sequenziali, in cui una delle variabili di ingresso è la funzione di uscita. La realizzazione pratica consiste in un circuito comprendente un percorso chiuso o anello, in cui una connessione riporta fra gli ingressi un valore di uscita (feed-back).

Esempio 1:


Questo circuito funziona da memoria.


Esmpio 2:



Questo circuiti fornisce risposta affermativa in funzione della diparitàdella sequenza binaria A.


1.2.4
  • Memorie elementari

Un secondo procedimento (cfr. il ritardo) di spostamento nel tempo di una informazione booleana consiste nel registrarne opportunamente il valore conservandolo in memoria.
Nel caso delle informazioni binarie elementari, questa funzione è svolta da un operatore logico detto memoria elementare.


I due segnali esterni , S ed R, impongono all'uscita Z i valori:


Questo elemento di memoria registra il valore di un segnale S e conserva un segnale rappresentativo di tale valore finché un segnale R non lo riporta a zero.
L'operatore quindi è suscettibile di:

  1. ricevere un segnale
  2. conservare il segnale ricevuto
  3. essere azzerato

Si suddividono i circuiti di memoria in due categorie in funzione delle strutture tecniche richieste:

a) memorie elementari statiche: la cui realizzazione tecnica più usuale è il Flip-Flop (ved,§ 1.3.3).
b) memorie dinamiche elementari: sono basate sulla presenza o assenza di circolazione di un impulso in un circuito di ritardo. Quindi, al contrario per esempio della linea di ritardo costituita da elementi bipolari, una memoria dinamica necessita di un circuito chiuso o ad anello.
Flip-Flop S-R

Dal punto di vista funzionale il F/F S-R presenta due ingressi detti S (Set) ed R (Reset), e due uscite complementari Z e . Il funzionamento è il seguente:

  • un segnale su S mette o lascia il F/F nello stato 1 (iscrizione dell'1)
  • un segnale su R mette o lascia il F/F nello stato 0 (iscrizione dell'0)
  • un segnale nullo lascia invariato il F/F
  • la combinazione 11 in ingresso è proibita

Lo stato interno della memoria è accessibile mediante l'esame della combinazione di uscita fra le due possibili (01 e 10). Si può introdurre anche una variabile di stato interno Q e si hanno le due possibili scelte:

Assumendo Q=Z il funzionamento di un F/F S-R è rappresentato nella tabella seguente:


Risulta:


Se inoltre la combinazione logica S_nR_n=1 (corrispondente alla combinazione 3 e 7 della tabella) è resa materialmente impossibile si può fare uso dei termini eliminati per minimizzare ulteriormente l'espressione, ottenedo:

Flip-Flop J-K

File:Excerpt from functional table for FLIP-FLOP JK..png|right]] Si comporta come un F/F S-R con J ingresso di set. E' però ammessa la combinazione 11 in ingresso e l'effetto è quello di far cambiare lo stato interno cioè:

immagine

Risulta quindi:


Flip-Flop T


E' un Flip-Flop ad un solo ingresso T e tale da cambiare stato ad ogni segnale in ingresso.

Zn+1=Tn⊕Zn



1.2.5
Memorie elementari dinamiche'
  • Flip-Flop dinamico di tipo S-R.

Consideriamo il circuito in figura . I segnali d'ingresso arrivano in S e in R, l'ingresso H è quello dell'orologio: il segnale applicate consiste in una successione regolare di impulsi. In uscita della porta OR si trova un ritardo δ pari al periodo dell'orologio.


In tal modo il circuito funzione come un Flip-Flop a due stati caratterizzati dalla presenza o dall'assenza di una ricircolazione di un impulso nel percorso chiuso abcda.
Consideriamo per esempio uno stato iniziale caratterizzato dall'assenza di impulso in abcda.
Un impulso su S in sincronismo con H ricircola con periodo δ finchè non arriva un impulso in R(con cui si blocca il rientro dell'impulso) e questo sia che si applichi o no degli impulsi in S. Viceversa, se si applica un impulso su R in sincronismo con H, l'impulso circolante che si trova in a non può rientrare nell'anello e la ricircolazione è interrotta. Si è così ritornati allo stato iniziale. Questo è il funzionamento del F/F di tipo S-R descritto prima, a parte il fatto che è permessa la combinazione di ingresso S=1, R=1 per Zn=0, 1 con Zn+1=1. Ciò permette di urilizzare la seconda espressione minimizzata trovata per il F/F S-R e, aggiungendo la variabile Hn rappresentativa dell'orologio si verifica che il circuito formisce la:

  • Flip-Flop dinamico tipo T


Con la medesima convenzione fatta per il Flip-Flop SR si ha, per il circuito a lato,


che realizza un Flip-Flop di tipo T. L'uscita Z, quando si applica un impulso in T, vale 1 ogni due impulsi, realizza quindi un divisore per due:

sequenza d'ingresso e di uscita per un Flip-Flop di tipo T con stato interno inizialmente nullo.


  • Circuito dinamico di ritardo



Il circuito in figura fornisce in uscita una sequenza uguale a quella in ingresso , ma ritardata di un periodo di orologio.

Un impulso 1 in ingresso pone in 1 il Flip-Flop: l'impulso in uscita viene ritardato di un periodo e passa, in sincronia con l'impulso di orologio, per la porta di AND. L'uscita è l'impulso ritardato. Questo impulso di uscita viene rinviato tramite una porta di AND all'ingresso R solo se il nuovo impulso è zero. Se invece il nuovo impulso fosse stati 1 l'iumpulso si reset sarebbe stato inibito dalla relativa porta di AND. Si può verificare che il circuito, con , fornisce la:

1.3 Aspetti tecnologici

  • 1.3.1 Tecniche a semiconduttori

La comparsa sul mercato di singoli componenti semi-conduttori ha rivoluzionato la tencia dei circuiti elettronici.<zbr/> I semi conduttori sono conosciuti da tempo (primi rivelatori radio), ma solo dopo il 1950 la loro realizzazione industriale ha ottenuto i requisiti necessari per poter sostituire i tubi a vuoto.
Un semiconduttore intrinseco cioè allo stato puro è un conduttore cattivo in una vasta zona di temperatura. L'introduzione di impurità modifica profondamente le proprietà di conducibilità elettrica: sin hanno allora i semi-conduttori estrinseci. A seconda della natura della impurità il materiale semi-conduttore si comporta come donatore o come accettore di elettroni. Nel primo caso si dice di tipo N (negativo) e la conducibilità avviene per trasporto di elettroni, nel secondo caso si dice di tipo P (positivo) e la conducibilità viene descritta in termini di buche o lacune positive
Uno dei semi-conduttori più usati è il cristallo di germanio (Ge). I cristalli semi conduttori sono ottenuti, a partire dal cristallo puro, per introduzione di impurità: antimonio (Sb), bismuto (Bi) o arsenico (As) per il tipo N; alluminio (Al), boro (B), rame (Cu) per il tipo P. Oltre il germanio sono in uso anche il selenio ed il silicio.


Sono realizzati dal contatto di cristalli di tipo P e N: si forma una barriera di potenziale che contrasta il passaggio della corrente elettrica in una delle due direzioni.

La curva caratteristica i in funzione della tensione V' ai capi è riportata nel grafico a latere.
Da quanto accennato sui diodi a proposito dei tubi a vuoto e dei semi-conduttori si può astrarre il comportamento del diodo ideale: elemento unidirezionale capace di far scorrere in un solo senso una corrente comunque elevata con resistenza interna Ri e differenza di tensione ai capi nulla; mentre presenta infinita resistenza interna al passaggio di corrente nel senso opposto. Il comportamento dipende dal segno della differenza di potenziale applicata (polarizzazione diretta ed inversa rispettivamente).


Sulla destra grafico del compotamento di un diodo ideale


  • Porte a diodi


La figura di fianco rappresenta una porta a diodi e resistori. Schematizzando i diodi come ideali si vede che se una o entrambe le tensioni di ingresso sono negative (-), inferiori alla tensione +, l'uscita avrà tensione -, viceversa se entrambi gli ingressi hanno tensione + l'uscita avrà tensione +. Nel primo caso si ha passaggio di corrente e nel secondo no. Con i diodi reali si avrà valore non nullo della resistenza nel primo caso e valore finito nel secondo.
Analogamente dalla figura qui affiancata segue la costruzione della funzione F2.


In logica positiva (conf.par,1.1.3)il circuito attinente la funzione F1 realizza una porta AND, mentre quello attinente la funzione F2realizza una porta OR
Con la convenzione logica negativa i due circuiti realizzano le funzioni duali e cioè OR e AND' rispettivamente.
L'inconveniente maggiore nell'uso del semi-conduttori risiede nelle condizioni di funzionamento. Nonostante i continui miglioramenti è sempre necessario, con precauzioni di condizionamento di aria, di refrigerazione ... mantenere il funzionamento in un ristretto intervallo di temperatura


  • 1.3.2 Transistori


Notiamo che le porte AND e OR non sono sufficienti poe la realizzazione di una funzione booleana; da un punto di vista logico è necessario aggiungere un circuito atto a realizzare la complementazione.
Questo tipo di circuito non si può ottenere con i componenti visti sinora, che erano tutti di tipo passivo. Infatti la complementazione di un segnale può richiedere che il segnale passi da un livello basso ad uno alto, cioè debba essere amplificato, e questo può essere ottenuto solo con componenti attivi. I componenti attivi sono necessari anche per la rigenerazione di un segnale che, a causa dell'attenuazione, rischi di essere inferiore del suo livello rappresentativo.


Fra gli elementi attivi facciamo cenno ai transistori. Il transistor a giunzione comprende due giunzioni che separano tre regioni semi-.conduttrici di cui le estreme dello stesso tipo e quella intermedia di tipo opposto. Si hanno quindi le due forme possibili PNP e NPN.
Una delle due estremità , l'emettitore, molto ricco di impurità, può emettere un gran numero di cariche che sono più o meno raccolte dall'altra estremità, il collettore, formato di cristalli meno ricchi di impurità.

<br/<>

Il flusso di cariche è regolato dallo stato della regione intermedia, la base. Poiché devono rappresentare gli stati 0 e 1 in modo che risultino distinguibili senza ambiguità, i transistori vengono fatti lavorare esclusivamente nelle due opposte condizioni di interidzione e saturazione
Schematizziamo il comportamento ideale di un transistor: mandando alla base una corrente nulla, è nulla la corrente di collettore; il transistor si comporta come un contatto aperto (interdizione) e la tensione di collettore è uguale a quella di alimentazione, non essendo il resistore R percorso da corrente. Inversamente mandando alla basse una debole corrente il transistor si comporta come un corto circuito (saturazione), la tensione di collettore va a zero e quindi ai capi del resistore R si ha una differenza di potenziale pari alla tensione di alimentazione.
Il comportamento reale di un transistore è rappresentato dalle seguenti caratteristiche:

Quindi con una debole corrente di base (dell'ordine delle decine di μA) si regola una corrente di collettore da valori molto bassi a valori dell'ordine di grandezza dei mA; e quindi, essendo la corrente di collettore maggiore di quella necessaria per controllarla, si parla di guadagno di corrente.
Corrispondentemente si ha, in interdizione, una differenza di tensione (ΔV)int non nulla ai capi del transistor e la tensione del collettore non è quella di alimentazione bensì quella di alimentazione diminuita di (ΔV)int: (VCE)int=VA-(ΔV)int essendo VA la tensione di alimentazione.
Nel caso di saturazione si ha ai capi del transistor una differenza di tensione non più pari alla tensione di alimentazione, ma leggermente inferiore, per cui la tensione di collettore assume un valore non nullo (VCE)=VA-(ΔV)sat.
I valori (VCE)sat e (VCE)int sono tali da essere considerati rappresentativi dei valori logici 0 e 1 in logica positiva.


  • Invertitore a transistor.

Per quanto detto il transistor tipo PNC' nel circuito aggregato realizza una funzione NOT: infatti lavorando nelle opposte zone di saturazione ed interdizione è tale da fornire per un imput in B come nel circuito l'outpt riportato in C, al limite per un transistor ideale con la tabella della verità in cui x è il valore di imput ed F(x) quello di output.


  • Circuiti NAND e NOR a transistor.



L'interesse dei circuiti che realizzano gli operatori NAND e NOR consiste nel fatto che detti operatori costituiscono , singolarmente, degli insiemi funzionalmente completi (cfr. Parte 1a, Cap.VII°).
In linea di principio gli elementi visti fin qui sono sufficienti per formare un circuito NAND o NOR. Infatti è sufficiente un circuito formato da una porta a diodi (paragrafo 1.3.2), e da un invertitore a transistor. Il circuito così formato appartiene alla famiglia dei D-T-L (Diodo-Transistor-Logic).
I circuiti affiancati fanno parte della famiglia D-C-T-L (Direct-Coupled-Transistor-Logic) e realizzano le funzioni NAND e NORtramite l'uso dei transistor in luogo dei diodi.
Consideriamo il circuito NAND: solo se entrambi i transistor conducono ci sarà una caduta di tensione ai capi del resistore ed il potenziale in G1 sarà basso. Invece considerando il circuito NOR risulta che è sufficiente che uno solo dei due transistor conduca perchè il potenziale di G2 sia basso. Ne segue la tabella della verità mostrata.
Analogamente a quanto detto a proposito delle porte a diodi la funzione G1 e G2 in logica positiva realizzano le funzioni NAND e NOR rispettivamente, mentre in logica negativa realizzano le funzioni duali NOR e NAND rispettivamente.
In simboli i circuiti NAND e NOR oltre che come indicato al paragrafo 1.1.4 possono anche essere indicati con i simboli del codice DIN qui raffigurati.

  • Flip-Flop

Quanto visto finora è sufficiente per comprendere la struttura di un Flip-Flop, il cui funzionamento logico si é visto al paragrafo 1.2.4.
Limitiamoci a considerare il caso in cui la combinazione Sn=Rn=1 è proibita , riscriviamo la funzione di uscita Zn+1 ed il suo complemento in funzione degli ingressi Sn e Rn tramite l'operatore NOR:



ed inoltre, considerando che in questo caso si ha si ha anche:



Queste due funzioni sono realizzate col circuito logico evidenziato a lato.
E' ora sufficiente considerare due circuiti NOR, e connettere simmetricamente l'uscita di uno dei due circuiti ad uno dei due ingressi dell'altro per ottenere uno schema semplificato di Flip-Flop.(vedasi figura)
Pertanto, quando la coppia di transistor di ingresso S e Z conduce (caso di saturazione) il potenziale del comune collettore (segnale ) mantiene a livello basso quello di una delle basi dell'altra coppia di transistor che, per quanto detto, si trova in condizione di interdizione.
Vi sono pertanto due stati di equilibrio stabile, caratterizzati dal fatto che una delle due coppie di transistor è in saturazione e l'altra in interdizione.
Quando il circuito si trova in uno dei due stati, identificabili tramite le funzioni di uscita e , vi rimane indefinitamente, realizzando cioè la funzione di memoria. Tramite segnali di comando esternisi ottiene che il circuito commuti all'altro dei due possibili stati; questi segnali (S e R) vengono mandatia una delle basidi una coppia di transistor. Il passaggiodi un Flip-Flop dallo stato 0 allo stat 1 si dice setting, quello dallo stato 1 allo stato 0 di resettig. Il comando che provoca la commutazione può essere o un livello di tensione (comando in continua) o impulso di tensione (comando in alternata).

Circuiti di un calcolatore digitale (a)

2.1 Addizionatore e sottrattre binario

Siano le variabili xi, yi, ri, si e r{i+1} definite nel cap.2 Parte Ia, a proposito della somma e della sottrazione di due numeri binari.
Facendo la convenzione di rappresentate l'i aritmetico mediante l'! della logica booleana, lo 0 aritmetico mediante lo 0 booleano, ed utilizzando gli stessi simboli di variabile per i due tipi di grandezza , si possono estrarre dalle tavole del Cap.2 Parte I le tavole della verità che definiscono , per un singolo rango la somma e la sottrazione.

File:Truth Table of Half Adder.png


2.1.1 Semiaddizionatore (half-adder)

Questo circuito è un blocco fondamentale costituito da 3 porte di AND ed una porta di OR. Il suo funzionamento viene stasabilito mediante la adiacente tavola della verità

E' da notare che questo circuito presenta due output separati: uno per la somma e l'altro per il riporto.
Le due funzioni booleane descritte dalla tavola sono:


Il diagramma logico di un semi addizionatore sarà quindi quello evidenziato a lato
Il circuito che genera la funzione Si viene anche impigato come porta di (or esclusivo)

File:Full Adder Truth Table (2).png


2.1.2 Addizionatore elementare (Full Adder)

Il processo della somma binaria consiste in questo caso nella addizione contemporanea delle due variabili Xi e Yi edel riporto ri ottenuto durante la somma parziale precedente . La tabella della verità relativa Si e ri+1 sarà quindi quella qui adiacente:

  • Equazione booleana di un addizionatore
Forma canonica:
Altre espressioni:

Per Si, si può scrivere:





La funzione ri+1 essere semplificata:



=
<brt/>

Per comodità , possiamo scrivere ulteriormente:



Quindi Si e ri+1 possono essere ottenuti mediante due reti: la prima sarà e , la seconda e .


Ciascuna di queste reti è un semiaddizionatore.
Connettendole come da figura ed utilizzando una porta supplementare OR per formare , si ottiene un addizionatore elementare a tre ingressi .

Mediante altre trasformazioni algebriche, si possono ovviamente ottenere altri schemi.
Per esmpio, considerando le espressioni:



si avrà il seguente schema:

L'addizionatore elementare che realizza le funzioni Si e ri+1, può essere utilizzato sia in un addizionatore in serie che in un addizionatore in parallelo.


2.1.3 Addizionatore in serie-Addizionatore in parallelo

Nell'addizionatore in serie le cifre degli operandi X e Y (Xi,Yi) si presentano negli istanti successivi i.
Una memoria M (per esempio una linea di ritardo con ritardo di un bit) conserva il riporto ri+1, elaborato all'istante i, fino all'istante i+1 (vedi figura)

Nell'addizionatore in parallelo, le cifre Xi e Yi (i=0,...,n) degli operandi X e Y si presentano in entrata in parallelo (simultaneamente
Con n+1 cifre, il circuito possiede 2(n+1) ingressi (Xi,Yi) e n+1 uscite.
Nella versione più classica (forma iterativa) esso possiede n+1 blocchi o stadi: uno stadio di rango 0 che è un semiaddizionatore ed n stadi costituiti da addizionatori elementari del tipo descritto in (2.1.2) (rango i>0).
Il riporto elaborato al rango i (ri+1) costituisce uno degli ingressi dello stadio i+1.
Nella figura posta accanto n=3.
Si noterà che la lunghezza massima che i segnali devono attraversare è di n+1 stadi , ossia di 2(n+1) livelli se i blocchi sono appunto a 2 livelli.
Per certe condizioni (X=2n+1-1, Y=1 per es.) la lunghezza di propagazione del riporto è effettivamente uguale a questo valore..
Un addizionatore in parallelo completa l'addizione in un tempo che è determinato dal tempo di arrivo di un digit più il tempo di propagazione dell'eventuale riporto, mentre un addizionatore seriale richiede n intervalli di tempo (digit times). Quindi l'addizionatore parallelo ha il vantaggio di essere veloce, mentre quello seriale ha il vantaggio di avere meno circuiti.

File:Tabella della verità per la sottrazione binaria.png
2.1.4 Sottrazione binaria

Mediante la tabella della verità affiancata si può definire il funzionamento di un blocco chiamato semi-sottrattore (half-subtractor) binario.Si fa l'ipotesi che il minuend0 Xe il sottraendo Ysiano positivi e tali che X≥Y.
Le equazioni booleane che definiscono la differenza e la ritenuta in una sottrazione binaria sono dunque:


File:TrueTable for Full Subtractor.png

Solo la seconda equazione differisce da quella ottenuta per l'addizione: essa si può dedurre da quella del par.2.1.1 sostituendo con .
Un semisottrattore genera la differenza d e la ritenuta ri+1 mediante il minuendo Xi e il sottraendo Yi.


Volendo invece ottenere la differenza die la ritenuta ri+1 considerando il sottraendo Xi, il minuendo Yi e la ritenuta ri del passo precedente, si ottiene la tabella della verità annessa al fianco.

Le equazioni booleane corrispondenti sono:




Uno dei possibili modi di realizzare un sottrattore elementare completo consiste nel considerare due semisottrattori.

Il semi-sottrattore ed il sottrattore completo possono essere utilizzati per costruire sottrattori in serie e in parallelo, sempre con l'ipotesi xhe X e Y siano senza segno e con X≥Y.
In seguito vedremo la realizzazione della sottrazione mediante l'uso dei complementi ad 1 e a 2. Infatti un circuito costruito per sommare numeri rappresentati con segno e modulo è molto più completodi quello che utilizza una rappresentazione complementata di numeri negativi.


2.2 Circuito di comlementazione (ad 1)

Sia il numero X=Xn-1 Xn-2...X0, il suo complemento ad 1 è il numero che ha per rappresentazione :

Si suppone X intero:

Infatti, se si costruisce la somma , cifra dopo cifra, si ha:

da cui, essendo r0=0,

Un cirfcuito complementatore (ad 1) converte un numero binario avuto in input in un output che ne è il complemento ad 1.
Un complementatore può essere costruito in modo da ricevere un input seriale oppure uno in parallelo.

In figura sono mostrati due complementatori che forniscono in output il valore , essendo P il valore di un opportuno segnale di controllo: si ottiene il complemento ad 1 quando P=1, infatti:

se la variabile di controllo è P=0 in output si ha la stessa variabile di ingresso X.
La figura a sinistra delle due mostra un complementatore seriale nel cui input X compare una sequenza binaria rappresentante un numero binario.
Questo circuito può essere usato come complementatore parallelo: è necessario allora avere un numero di circuiti pari al numero di bit del numero binario.
L'altra figura rappresenta un complementatore in parallelo: i due output del Flip-Flop X costituiscono i due inputs. Ovviamente ci devono essere tanti di questi circuiti quanti sono i bits del numero binario.
Questo circuito a sua volta può essere utilizzato come complementatore seriale: sarà allora richiesto un solo circuito e lo stato del Flip-Flop cambierà ad ogni digit time generando così una sequenza binaria rappresentante il nujmero binario.

2.3-circuito di complentazione a 2

Sia il numero binario X si chiama complemento vero o complemento a 2, la quantità .
Si ha dunque:




Aggiungendo 1 a C1(X) si ottiene:

>br/>

Ricordando come si esprimono in algebra booleana le somme e i riporti di una addizione della aritmetica booleana, si ha:




.
.


Ponendo:


si ottengono le seguenti equazioni di un circuito complementare a 2 seriale:


Tenendo presente l'equazione booleana di un Fip-Flop SR, si può pensare di realizzare l'equazione mediante un SR con l'ingresso R sempre mantenuto a 0 e con lo stato interno iniziale Z0=0.
Nella figura è descritto un complementatore a 2 di tipo seriale per numeri binari senza segno.

Nella seguente figura è descritto invece un complementatore seriale a 2 per numeri binari con segno: la sua caratteristica è determinata dal fatto che se il numero è negativo (bit del segno uguale ad 1), esso esce in output complementato a 2, se l'input invece è positivo , il numero uscirà nella forma vera.
Si fa l'assunzione che il bit del segno arrivi come primo bit nella sequenza di input: gli seguiranno i bits delle cifre significative in ordine di peso crescente.
Quando il bit del segno, arriva in input , esso passa attraverso la via a e compare invariato in output.
Nel frattempo un segnale di controllo del segno selezione la via c.
Se il bit del segno è 0 (numero positivo), il Flip-Flop S rimane nello stato 0 e i bit successivi del numero passano attraverso la via a ed appaiono in output.
Se il bit del segno è 1 (numero negativo), il Flipo-Flop S viene messo nello stato 1. La via a viene interdetta e la via b viene permessa.
I bits successivi del numero passeranno allora per la via b e verranno complementati nella maniera descritta per numeri senza segno.
Osservando la figura del diagramma logico del complementate a 2 di tipo seriale si verifica la regola pratica per ottenere il complemento a 2 (detto anche complemento vero) di un numero binario. Essa consiste nel lasciare inalterati tutti gli zeri prima del primo 1 incontrato nel risalire la parola X partendo dai pesi più deboli e procedendo verso quelli più forti, nel lasciare inalterato questo 1, e nel complementare tutte le cifre a sinistra di questo 1.



Se consideriamo il circuito dell'accennata figura notiamo che il Flip-Flop interviene in due porte di AND: in una i bits di X entrano in forma negata e nell'altra no.
Ora, consideriamo un input seriale a partire dai pesi più deboli, i bit 0 non cambiano lo stato iniziale del Flip-Flop la cui uscita Z=0 interdcde la pota AND relativa negata dei bits di X, e questo fino all'arrivo del primo bit 1, dopo il quale lo stato del Flip-Flop cambia; si ha la situazione inversa della precedente , in cui l'uscita interdisce la porta AND relativa ai bits di X.
Si ha inoltre:


Si vede quindi che, facendo le operazioni modulo 2n, si ottengono gli stessi risultati sia operando con X-Y che con X+C2(Y).
Quanto affermato sopra, è già stato dimostrato con l'ausilio del calcolo dei residui nel Cap.2 parte I.
Dimostriamo ora la veridicità mediante l'algebra di Boole. Poniamo:


Le operazioni X-Y e X+C2(Y)=X+Y' sono definite in forma ricorrente dalle equazioni:


Supponiamo che al rango k si abbia S'k=Sk:
Si ha allora:


cioè


Si deduce immediatamente:



da cui




Consideriamo l'ultimo termine: si ha:



e quindi iterando il procedimento, si ha:


Da cui:


di conseguenza


E quindi se S'k= Sk si ha S'k+1=Sk+1
Poiché S'0=S0=(X0⊕Y0), la relazione di uguaglianza sussiste per ogni rango K: S'k=Sk.

Per quanto riguarda un complementatore a 2 parallelo, esso consiste in n complementatori ad 1, in un addizionatore parallelo ad n bit e in un Flip-Flop C. Con n si è indicato il numero dei bit che compongono il numero binario. Il bit del segno passa inalterato nel circuito. Per ottenere il complemento a 2 del numero, se ne trova prima il complemento ad 1 e quindi si somma 1 al bit meno significativo [C2(X)=C1(X)+1]
L'addizioned di 1 al bit meno significativo la si ottiene ponendo inizialmente il Flip-Flop C ello stato 11; in tal modo questa operazione consiste nell'addizionare due addendi di cui uno nullo, ma con un riporto iniziale di 1, e quindi sostanzialmente ogni adder dell'addizionatore parallelo lavora com un half-adder.

2.4-Controlli di parità

Si chiama Bit di Parità, una cifra binaria che si aggiunge talvolta ad una parola binaria in modo da scoprire eventuali errori di trasmissione.
Data una parola X ad n posizioni:


Si usa trasmettere la parola ad n+1 posizioni :


dove P è tale che il numero totale degli 1 della parola X' sia pari.
Esempio:



Si piò fare un'altra convenzione e definire un bit di disparità, tale che il numero totale degli 1 sia dispari.
Con questa nuova convenzione , non vi può essere un numero X' formato da zeri.
Questa combinazione risulta essere proibita, e la sua presenza può servire a mettere in evidenza certi difetti di funzionamento (come per esempio un difetto di alimentazione).
Si ha la corrispondenza:


e quindi:


dove P e Xi sono variabili aritmetiche. Con la convenzione già usata, considerando P e Xi variabili booleane, si ha:


Il bit di parità indica gli errori di trasmissione su di un numero dispari di posizioni.
Come circuito di controllo, si può pensare un Flip-Flop di tipo T dove lo stato interno Q0 iniziale è posto a zero.


-Addizione di 2 numeri con bit di parità

Consideriamo 2 numeri binari X e Y ad n cifre:


alle n cifre siano stati aggiunti i bit di parità Px e Py:


chiamiamo Ps la cifra di parità x+y.
Calcoliamo l'espressione di Ps mediante le equazioni che danno la somma sk e il riporto rk+1 di rango K in funzione di xk, yk, rk.
Poniamo:


(Supponiamo quindi che S sia anch'essa di n cifre).
Si ha allora:





La cifra di parità Ps di S=X+Y è quindi la somma modulo 2 delle cifre dparità Px e Pydi X e Y e dei riporti rk (k=0, ..., n-1).

Nota-Quando la cifra Ps calcolatamediane la somma effettivamente ottenuta e la cifra Ps' calcolata mediante la (1.7.1) sono differenti, vi è errore. Poiché tutte le operazioni aritmetiche in un calcolatore sono effettuate, in ultima analisi, mediante addizioni , il procedimento sopra esposto può essere, in teoria, esteso come verifica di una qualunque operazione aritmetica.
2.5-Circuito per il confronto di 2 numeri binari.

Il problema che ci si propone di risolvere è quello di effettuare una operazione di confronto tra due numeri binari ad n bit in modo da determinare quale dei due ha valore maggiore in modulo.
In un primo tempo costruiremo un comparatore seriale nel cui input arrivano i bits da confrontare secondo la sequenza determinata dal crescere del rango. Sia dunque la parola binaria:


chiameremo con X(k) la parola tronca formata dalle k+1 cifre di peso più debole (ranghi da 0 a k).

File:Variabile binaria.png


File:Tabella riassuntiva delle diffrenze.png

Consideramo quindi due numeri X e Y e la variabile binaria definita dalla corrispondenza

Da queste condizioni segue che:


d'altra parte, se xk≠yk, la diseguaglianza tra xk e yk da una parte, x(k) y(k) sono definite nello stesso verso.

quanto detto può, può essere riassunto dalla tabella seguente.
Si ha dunque:



Si riconosce per Sk l'espressione della ritenuta ottenuta durante l'operazione Y-X.


Si vede quindi che Sn-1=1 quando l'operazione Y-X produce una ritenuta al rango n-1, situazione che si deve verificare quando x>y. Per confrontare i due numeri però non è necessaqrio determinare la differenza : infatti è sufficiente il valore Sn-1 della ultima ritenuta di questa differenza. Per costruire il circuito, conviene però mettere la equazione.


sotto la forma seguente:







Per realizzare questo circuito, è sufficiente considerare un Flip-Flop di tipo T in cui Sk-1 rappresenta lo stato interno ed il resto dell'espressione costituisce l'ingresso del Flip-Flop mentre l'uscita determina la funzione di confronto tra i due numeri X e Y.
L'operazione realizzata da l circuito ha termine ovviamente quando in input si sono presentati tutti gli n' bits di X e Y.

File:Tabella di un comparatore seriale.png

Supponiamo invece che i bits di X e Y si presentino nell'ordine determinato dai pesi decrescenti: il circuito in questo caso sarà molto più semplice in quanto non ci sarà bisogno di utilizzare un circuito sequenziale.
La tabella di un comparatore seriale in cui l'input sia costituito da bits di peso decrescente sarà come quella affiancata.


Da tale tabella si deduce il circuito a latere

Appena x_k≠y_k si arrestano i confronti.


Comparatore parallelo

Un comparatore parallelo sarà costituito da n circuiti comparatori in cui gli n bitsdi X e Y verranno confrontati separatamente e contemporaneamente.
La prima coppia di bits xi e yi (i=n-1,n-2,...,0) che differisce , determina l'uscita finale del comparatore, a prescindere dal valore di xi-1, yi-1,...ecc.
Nel seguito viene costruito un circuito comparatore in parallelo di 2 numeri di 2 bit: un circuito relativo a parole a n bits, avrà l'uscita uguale a quello di figura 2.5.2 e 2 circuiti NAND in più per ogni coppia di bit addizionale.
Siano quindi da confrontare i due numeri; X=x1 x0 e Y=y1 y0.
La tabella della verità relativa al problema del confronto in parallelo sarà:


Semplificando la funzione mediante un diagramma di Karnaugh si ha:





Semplificando la funzioine mediante un diagramma di Karnaugh si ha:




Dalla tabella della verità si deduce che:

Utilizzando alloa delle porte di NAND (/) si costruirà il circuito a latere


.

Sia il numero binario X e siano le sue due rappresentazioni binarie:


Le formule di conversione (Cap.3 parte I) sono:


Le conversioni si fanno più facilmente dalle cifre di peso più forte.
In queste condizioni, poniamo, per la conversione binario riflesso-binario puro:


Si ha:

Mediante le equazioni trovate possiamo dedure lo schema del circuito che realizza la conversione da un codice riflesso ad uno binario puro: per avere la uscita Zp è sufficiente una porta di XOR mentre per l'uscita Qp+1 è necessario utilizzare un Flip-Flop T

Per la conversione binario puro-binario riflesso, si pone:



si ha quindi

Da cui il circuito nella figura accanto:



2.7.1 Si chiama contatore un circuito capace di prendere nota del numero di impulsi che arrivano in input e conservare il risultato dell'operazione di conteggio.
Se un contatore somma ogni qual volta arriva un impulso in input, esso pende il nome di forward counter o up counter. Se un contatore assume inizialmente una certa configurazione rappresentante un numero ed ad ogni impulso in input sottrae da questo numero, esso viene chiamato reverse counter o down counter.
Se un contatore è provvisto di due terminali di input in modo da addizionare se gli impulsi arrivano ad uno dei terminali di input e da sottrarre per gli impulsi che arivano all'altro input , esso viene chiamato reversible counter o up-down counter.
I contatori vengono classificati anche in base alla maniera di memorizzare il numero del conteggio.
Se il numero memorizzato è un numero binario, in codice binario puro il contatore è un contatore binario.
Se il numero memorizzato è un numero decimale è un contatore decimale.>br/> Se il digit decimale viene rappresentato mediante un codice binario il contatore è un binay-codet decimal digit counter.
Vi sono inoltre contatori capaci di esprimere il conteggio in altri codici binari (p.es.codice Gray). Pe ottenere le equazioni booleane di un contatore binario puro si può pocedee in due modi.


2.7.2 Primo modo per la determinazione booleana di un contatore binario.


Il passaggio da un numero X al numero X+1 può essere rappresentato mediante certe relazioni booleane che legano la rappresentazione dei numeri X e X+1. Consideriamo infatti l'addizione:
Si ha:







Le relazioni che rappresentano il numero x+1 in funzione di x sono:




Si ha:

Le relazioni che danno la rappresentazione del numero X-1 in funzione di quella di X possono essere ottenute con il seguente procedimento:








Le rrelazioni (2.7.2) rappresentano il meccanismo di un u-counter e le (2.7.3) quelle di un down-counter), entrambi un codice binario puro. Si noterà che si passa dall'incremento al decremento complementando le variabili che compaiono nella ritenuta.
Complementando ambo i membri della relazione (2.7.3) si ottiene:


che insieme alla:

dà la relazione di incremento per i numeri corrispondenti alle parole binarie complementate. Infatti chiamiamo |A| il valore rappresentato dal nome A, si ha:





Se si chiama con E la variabile d'entrata del circuito, con l'indice n si indica il tempo dell'orologio (n≥0), si ottengono le seguenti equazioni:




Le figure A e B rappresentano degli up-conter a 16 stadi interni quattro stadi binari). L'orologio non viene indicato).
La generalizzazione al caso di m stadi (2m stadi interni) è immediata.
Si noterà che per m elevato non è possibile connettere i Flip-Flop mediante una logica ad 1 livello come in figura A in quanto per il rango k è necessari una porta a k entrate.<br7> Si possono allora realizzare i prodotti π xi mediante funzioni di funzioni come in figura B.
Nella configurazione data, sono sufficienti delle porte AND a due entrate: risulta essere più lungo però il tempo di propagazione del riporto.
Per il rango k ci vuole un tempo k volte maggiore di quello necessario per il contatore A.

Le cifre xk di rango k ad un certo istante n sono ovviamente rappresentate dagli stati interni dei Flip.Flop T di rango corrispondente mentre le uscite complimentate rappresentano le .
Le xk fanno parte della rappresentazione di x+1 mentre le sono la rappresentazione binaria di .
La costruzione di un down-counter risulta ovvia e la si può vedere facilmente nel grafico sovrastante dove e rappresentato un up-down counter
Nello schema sono state aggiunte delle linee di ritardo: esse stanno ad indicare che l'input delle porte di AND che proviene dai Flip-Flop è lo stato dei Flip-Flop prima che essi vengano commutati.
Se i Flip-Flop posseggono un loro ritardo sufficiente, questi ritardi aggiuntivi non sono necessari.
Comde si è appunto supposto nelle figure A e B).
Il disegno logico di un contatore binario può essere ricavato utilizzando una tavola della verità. La tavola mostra non solo le relazioni tra i successivi stati dei Flip-Flop ma anche gli stati di imput dei Flip-Flop che causano una commutazione di questi Flp-Flop. Consideriamo un up-counter binario a tre stadi e proponiamoci di costruirlo con Flip-Flop di tipo T.

File:Tvola della verita di un up-counter.png

La tavola della verità di questo contatore è mostrata nella figura D.
In questa tavola i tre flip-flop e le loro uscite sono rappresentati con le variabili A3,A2,A1 rappresentano i loro rispettivi input; p rappresenta gli impulsi in input da conteggiare; t0, t1..ecc. rappresentano la sequenza temporale degli impulsi.
Le tre colonne relative agli A mostrano la sequenza desiderata degli stati dei tre flip-flop. Le ultime tre colonne mostrano i valori veri richiesti per gli input a3t, a2t, a1t, capaci di cambiare lo stato del contatore.
In queste tte colonne , lo 0 significa che non è richiesto alcun impulso nell'input del flipo-flop , mentreun 1 significa che è necessario un impulso nell'imput del flip-flop.
Questi 0 e questi 1 sono ottenuti dalla commutazione dello stato dei Flip-Flop indicata nelle tre colonne relative agli A.
Per esempio, quando lo stato del contatore viene cambiato da 000 a 001, gli stati di A3 e A2 non cambiano, quindi i valori di a3t e a2tsono entrambi 0 nella prima riga delle colonne relative a a3t e a2t.
Però lo stato di A1 cambia da 0 a 1; quindi il valore di a1t è 1 nella prima riga dell'ultima colonna. Gli altri valori delle ultime tre colonne vengono ottenuti nella stessa maniera.
Da notare che all'istante t8lo stato del contatore è 000 lo stesso che all'istante t0
Il contatore quindi ha un compotamednto ciclico. Le equazioni di input per i tre Flip-Flop dedotte dalla tabella della verità D sono:



che possono essere anche scritte come:



Quando le equazioni di input vengono sostituite nell'equazione di stato di un Flip-Flop T (Qn+1=Qn ⊕ En) si ottiene:



Queste sono le equazioni di stato di un contatore e descrivono lo stato dei tre Flip-Flop.
Applicando queste equazioni a quelle precedenti di input si ottengono i circuiti di fig.A e B.

File:Tavola della verità per flip-flop SR.png


Al posto di un Flip-Flop T, si può pensare di utilizzare un SR per costruire un contatore binario. Nella tavola E compaiono le condizioni necessarie per costruire un up-counter binario mediante Flip-Flop SR.
In questa tabella a3r, a2r, a1r, rappresentano gli input di riset (R) nei tre Flip-Flop ed a3s, a2s, a1s, i tre set inputs, p rappresenta gli impulsi di input da conteggiare; t0, t1, ecc. rappresentano la sequenza temporale degli impulsi di input.
Gli 0 e gli 1 delle ultime sei colonne sono anche qui ottenuti mediante i cambiamenti di stato dei Flip-Flop indicati nelle tre prime colonne. Essi però differiscono da quelli della tabella D. Nella tabella E l' 1 nella colonna dell' input reset (colonne sei, otto, dieci) indica il cambiamento di stato del Flip-Flop da 1 a 0, mentre lo 0 indica tutti gli altri casi (da 0 a0, da 1 a 1, da 0 a 1).
L'1 nella colonna dell' input reset (colonne sette, nove, undici) indica il cambiamento dello stato del Flip-Flop da 0 a 1 mentre lo 0 indica tutti gli altri casi (da 0 a 0, da 1 a 1, da 1 a 0). Per esempio, quando lo stato del contatore cambia da 000 a 001, gli stati di A3 e A2 rimangono immutati, per cui i valori di a3r, a3s, a2r, a2s sono 0 nella prima riga delle colonne sei, sette, otto e nove.
Lo stato A1 però deve cambiare da 0 a 1, quindi il valore di a1r è 0 mentre il valore di a1s è 1 nella prima riga delle due ultime colonne rispettivamente. I valori degli altri input set e reset sono ottenuti nella stessa maniera.
Dalla tabella E possiamo ottenere le equazioni di input dei tre Flip-Flop:







se si sostituiscono le equazioni di input nella equazione di stato di un Flip-Flop SR (), si ottengono le equazioni 2.7.8, cioè le equazioni di stato di un up-counter binario.

Le equazioni 2.7.10 si possono scrivere in un altro modo.
Alle prime tre equazioni di 2.7.10 si aggiungono rispettivamente i termini ; queste somme logiche non cambiano il valore delle espressioni di partenza.
Le sei equazioni diventano allora:




Si noti che queste sono le equazioni delle somme e del riporto in output di un half-adder.
Quindi a1s e a1r sono rispettivamente la somma e il riporto di un half-adder i cui input sono A_1 e p.
In modo equivalente , si ha che a2s e a2r come a3s e a3r sono le uscite di half-addeers.
Il contatore binario utlizzante degli half-adder e dei flip-flop SR, viene mostrat in figura F.



I contatori decimali sono circuiti che accettano degli impulsi in input, li contano e ogni volta che la somma totale risulti essere 10, ritornano allo stato iniziale emettendo sulla linea di uscita un impulso di riporto (dettom carry o overflow).
Tali contatori di capacità 10 vengono chiamati decadi.br/> Interconnettendo m elementi decimali di conteggio di questo tipo, in modo che l'uscita di un elemento J-1 serva come ingresso all'elemnto J, si può realizzare un contatore di capacità 10m.
Per codificare i 10 stati interni si usano generalmente codifiche di tipo binario con almeno 4 digit binari.

File:Codice 8421.png


Si è visto (cap.III°, parte Ia) che quando la cifra decimale corrispondente deve essere convertita in analogico, può essere utile considerare un codice ponderato. Infatti nel caso di una conversione in tensione sarà sufficiente fare la somma ponderata delle correnti corrispondenti ai 4 digit binari.
Nella tabella posta accanto compaiono il codice 8421 (I) e quello ad eccesso di 3 (II)
Ci proponiamo nel seguito di costruire un contatore relativo al codice 8421 e quello relativo al codice ad eccesso di tre.


La configurazione generale di un contatore decimale relativo al codice 8421 sarà:
Il numero rappresentato dallo stato interno dei Flip-Flop A4, A3, A2 A1, raggiungeà al massimo 1001, equivalente al digit decimale 9.
Appena arriva un nuovo impulso, il contatore assume lo stato 0000 (equivalente al digit decimale 0), e produce un riporto che servirà come input per incrementare la seconda decade.

File:Tabella 2.8.2.png

Queste considerazioni e la conoscenza delle proprietà dei Flip-Flop T che vogliamo utilizzare per realizzare il circuito , ci permettono di scrivere ls seguente tabella (2.8.2):


Possiamo scrivere le equazioni di input a4t, a3t, a2t, a1t direttamente dalla tabella 2.8.2.



Possiamo semplificare le espressioni boolea ne mediante diagrammi di Karnaugh; in questa semplificazione si può far uso anche degli stati non esistenti 1010, 1011, 1100, 1101, 1110, 1111 (segnati con crocetta).
La variabile p è una variabile d'ingresso ma poiché vale sempre 1, è inutile prenderla in considerazione durante la semplificazione.
Dai digrammi si esplicano:





Sostituendo questi valori di input nella equazione di stato di un Flip-Flop si ottengono le equazioni di stato di una decade relativa al codice 8421:



Nella figura viene dato il diagramma logico di una realizzazione di questo circuito.

File:Tabella relativa a contatore codice accesso tre.png




Supponiamo ora di voler costruire un contatore per un codice a accesso di tre.
La tabella della verità relativa viene data in figura 2.8.4
Semplificando con Karnaugh si ottengono le equazioni di input seguenti:





Per le semplificazioni si sono considerate anche le combinazioni che non compaiono nel codice ad eccesso di tre.
Dalle equazioni di input si deduce una possibile realizzazione del circuito (2.8.5): decadi per codici ad eccesso di tre.



Determiniamo per prima cosa le relazioni che legano due parole codice e rappresentanti in codice rilflesso due numeri e consecutivi, cioè tali che .
Si è visto (cap.3 parte I) che e devono essere adiacenti.
Si possono avere due e si può scrivere cosìcasi.

- primo caso:

Si ha allora:


a questi due numeri corrispondono le seguenti rappresentazioni in codice Gray:



Si ha quindi:


Quindi se rappresenta in codice Gray un intero pari, si ottiene , complemetando il digit più a destra.

-Secondo caso: dispari:

comincia a destra con un 1 e si può scrvere così:



Da cui:



e:


Quindi, quando rappresenta in codice Gray un numero dispari, si ottiene la rappresentazione del numero successivo complementando la prima cifra a sinistra del primo 1 incontrato partendo da destra.
Consideriamo ora un contatore R=(Rm...Rk...R0) binario riflesso in cui Rk sono gli stati interni di Flip-Flop T ed indicano il valore delle cifre di rango K in codice Gray.

Chiamiamo con l'ingesso del Flip-Flop T di rango k all'istante n; si avrà:

da cui:

Conoscendo lo stato di parità del numero , si possono dedurre dalla (2.9.1) e (2.9.2), le , cioè i valori di ingresso da dare ai singoli Flip-Flop in modo da ottenere il numero .
Ora, la parità del numero consideerato è dato dal digit della rappresentazione in binario puro.




Si deducono le seguenti relazioni:


dove E rappresenta la variabile d'ingresso del contatore.


Ponendo:


Si ha allora per


Nelle figure (2.9.4 e 2.9.4bis)sono rappresentati 2 contatori in codice binario riflesso ottenuti applicando le formule (2.9.3) o considerando una decomposizione analoga a quella fatta nel caso dei contatori in binario puro. E' da notare inoltre il segno - su tutte le salvo quella di rango k-1 e la presenza della variabile rappresentata da un Flip-Flop supplementare di parità.
Questo Flip-Flop di rango -1, commuterà ogni volta che si applicherà un 1 al suo ingresso.


2.10 - Diagrammi di stato

Consideriamo a titolo di esempio, un addizionatore binario seriale (fig.2.1.3) ed assumiamo che la configurazione della memoria M, che conserva fino all'istante i+1 il valore del riporto ottenuto all'istante i, sia rappresentativa dello stato interno del circuito.

A partire da uno stato iniziale risulta che le tre combinazioni di ingresso di (cfr.§2.1.2) 00,01,10 il valore di , e cioè lo stato interno del circuito non cambia; mentre per la combinazione lo stato interno passa dal valore 0 al valore 1. Analogamente si può considerare per quali combinazioni delle variabili d'ingresso lo stato interno rimane uguale ad 1 e per quale valore cambia invece nuovamente da 1 a 0. Si può quindi riscrivere la tavola della verità di § 2.1.2 sotto la forma di diagramma di stato, in cui rappresenta la combinazione dei valori d'ingresso, lo stato interno; ed in funzione dei valori di e di sono riportati in ogni casella, separati da una /, il nuovo stato interno ed il valore di uscita .


Si può equivalentemente rappresentare il comportamento del circuito per mezzo di un grafo composto da vertici rappresentativi dello stato interno e da archi orientati tra le coppie di vertici.
Gli archi orientati sono rappresentativi dei valori di ingresso che determinano il passaggio dello stato interno dasl vertice di partenza a quello di arrivo, e recano, separati da una barra, oltre a questi valori , anche i corrispondenti valori di uscita.
Nell'esempio in esame si ha quindi il grafo posto di fianco:

Il grafo di una rete sequenziale contiene dunque le stesse informazioni della tabella della verità; con esso però si mette in particolare evidenza la connessione logica degli stati che il sistema può assumere. Una altra rappresentazione molto usata ha nome di diagramma di stato ed indica gli stati successivamente assunti dal sistema.
Un semplice esempio riguarda il diagramma di stato di un contatore binario modulo 23 in (2.10.1 a). Il nujmero binario racchiuso nel circolo indica lo stato dei tre Flip-Flop , e le frecce indicano la sequenza dei cambiamenti di stato (cnf:§2.7)

Un contatore decimale ,o decade, richieder invece 10 stati distinti. Il diagramma di stato. Il diagramma di stato di un tale contatore con codice 8.4.2.1 è riportato in (2.10.1 b). br/>

Se come visto nel § 2.7.3 con (i=1,2,3,4) si rappresentano i valori di input capaci di cambiare lo stato dei quattro rispettivi Flip-Flop , dal diagramma di statosi possono ottenere, senza costruire la tabella della verità, le equazioni di input ricavate nel §2.8. Ad esempio , infatti, considerando che i numeri racchiusinel circoletto rappresentano i valori assunti di volta in volta dall'insieme ordinato e se consideriamo in particolare lo stato , inizialmente posty a 0, notiamo che detto stato commuta sempre e solo a partire da una configurazione del tipo 0\ -\ - 1 e quindi l'equazione di input relativa al Flip-Flop di stato tenuto conto della variabile d'ingesso p, deve essere:

.

Circuiti di un calcolatore digitale (b)

3.1
-registri di scorrimento

Un registro in un calcolatore digitale è un circuito di memorizzazione di ampiezza, in generale, pari a una parola (o voce) di macchina.
Poiché una parola di macchina consiste di un numero determinato di bit, e poichèp un Flipo-Flop è un elemento di memorizzazione binario, un registro è costituito da un insieme di Flip-Flop.

In figura 3.1.1 viene data la rappresentazione simbolica di un registro: ogni quadrato rappresenta un Flip-Flop.

La lettera A indica il registro A e la lettera Ai il Flip-Flop i-esimo.
Un registro a scorrimento (o shift rergister) permette di fare scorrere il proprio contenuto sulla destra , o sulla sinistra o in entrasmbe le direzioni; in fig.3.1.2a compare la rappresentazione simbolica di un registro di shift. Un registro di shift a n bits fa scorrere un bit alla volta richiedendo quindi n operazioni di shift per inserire o edstrarre una parola seriale di n bits.


Circuiti addizionali sono richiestinel registro di shift se una parola deve essere inserita o prelevata in parallelo: infatti un registro può convertire una parola seriale in una parallelo (3.1.2b)o una parallela in una seriale (3.1.2c).

Connettendo l'output all'input di un egistro di shift , quest'ultimo un circulating regster (3.1.2d)


-Equazioi logiche di un registro di shift

Un regisro di shift richiede una memorizzazione temporanea tra due Flip-Flop adiacenti in modo che venga conservata l'informazione di un Flip-Flop che sta per cambiare e utilizzare tale memorizzazione come input per il Flip-Flop successivo. In fig.3.1.3 compare un registro di shift in cui l'elemento base è costituito da Flip-Flop SR.
L'output di questo Flip-Flop SR viene indicato con lettera maiuscola An o il complemento ; gli inputs sono indicati con lettere minuscole, anr e ans, e rappresentano gli input reset e set dell'n-simo Flip-Flop.
La lettera p rappresenta il segnale di clock che determina l'operazione di shift. Come si è già visto a proposito dei contatori, anche per i registri di shift vi sono due tipi di equazioni logiche.


Il primo tipo descrive lo stato del registro : gli stati dei singoli Flip-Flop di un registro a scorrimento sono rappresentati nella tabella affinacata, da cui si deduce l'equazione di stato


Questa equazione indica che lo stato dello n-esimo Flip-Flop dopo l'intervallo temporale τ è lo stato del Flip-Flop (n-1)-esimo.


Il secondo tipo di equazioni logiche descrive l'input del Flip-Flop. I valori che devono essere assuntidagli impulsi Set e Rersetdel Flip-Flop n-desimo sono rappresentati nella figura adiacente.

Da cui si deducono le equazioni di input dei Flip-Flop di un registro di shift:


Da queste considrazioni è stato dedotto il circuito di fig.3.1.3


3.2
-Trasferimento dell'informazione

L'informazione conservata in un registro costituisce una parola: mediante un trasferimento di informazione, cerchiamo di realizzare il trasferimento della una parola da un registro ad un altro o un trasferimento multiplo da uno o più registri ad altri registri.
L'importanza di una operazione di trasferimento consiste non solo nel trasferimento stesso, ma nella possibilità di compiere operazioni logiche sulla parola durante il trasferimento. Il trasferimento dell'informazione traa vari regfistri è l'operazione base mediante la quale possono essere realizzati la elaborazione dei dati, le decisioni logiche, ecc., in un calcolatore: inizialmente le informazioni sono conservate in una unità di memoria da cui vengono trasferite nei vari registri secondo una certa sequenza.
Sono stati sviluppati dei metodi simbolici per poter rappresentare questo processo di trasferimento delle informazioni: in primo luogo un trasferimento viene espresso mediante una istruzione simbolica
Le equazioni logiche ed i diagrammi logici possono essere quindi ottenuti dalle istruzioni simboliche.
Per poter descrivere un tale procedimento simbolico si sono mostrati nel seguente elenco i simboli utilizzati.

Simboli Descrizione dei simboli
Lettere maiuscole indicano i registri
Indice i Denota lo iesimo bit di un registro
Parentesi () Indicano il contenuto di un registro
Doppia freccia Indica il trasferimento di una parola da un registro all'altro
Parentesi [] Porzione di registro il cui contenuto ha una dipendenza funzionale del registro stesso
Due punti : Due punti (preceduti da una variabile booleana) indicano il verificarsi dell'istruzione segujente quando la variabile ha il valore 1
Freccia semplice Indica una sequenza di stati
Segno + Questo simbolo ha due significati: 1) una operazione logica OR quando esso è usato tra variabili booleane; 2) un'addizione aritmetica quando è usato tra numeri
Segno - Questo simbolo indica una operazione aritmetica

Per esempio (A) indica il contenuto del registro (A) e (Ai) indica il contenuto dell'isimo bit del registro A; (A,B) indica il contenuto dei registri A e B che vengono usati insieme come un unico registro.
Con (A) B si indica che il contenuto del registro A viene trasferito in B e A significa che degli zeri vengono inseriti in A. L'operazione di shift a sinistra viene indicata con , supponendo che l'indice i incrementato indichi un bit significativo di rango superiore.
L'operazione di shift a destra sarà alloa:


Le espressioni simboliche e , indicano la parte segno e la parte numerica del registro A. L'espressione indica che, quando pi ha il valore 1, viene eseguita l'istruzione che azzera il registro A.
Mediante questo simbolismo, si può descrivere una operazione di trasferimento: supponiamo di avere una parole di 3 bit nel registro A e di trasgerirla in B al momento in cui viene dato il via da un segnale P1 proveniente dall'unità di controllo del calcolatore.
Tale operazione si esprimerà nella forma



Supponendo che i registri siano costituiti da Flip-Flop T, dalla (3.2.2)si deduce ta tavola della verità (3.2.3).
In questa tabella, il trasferimento inizia quando l'impulso p dell'orologio è uguale ad 1: indica il valore d'ingresso del Flipo-Flop rappresentativo dell' bit nel registro B.

Queste equazioni indicano che l'0perazione di trasferimento in un registro B costituito da Flip-Flop T viene realizzato mediante un XOR. Nella figura collocata di fianco compare il diagramma logico (trasferimento in parallelo di una parola dal registro A al registro B) che descrive la connessione dei due registri.
L'esempio presente si riferisce ad un trasferimento in parallelo di una parola: una informazione può essere però trasferita in forma sequenziale.
Come esempio, consideriamo la somma aritmetica tra due numeri binari entrambi di cinque bit: siano essi conservatinei registri di shift A e B (fig.3.2.5). L'addizione avviene quando P1, proveniente dalla unità di controllo, assume il valore 1.


Nella addizione seriale , coppie di bits corrispondenti dei due numeri vengono sommati allo stesso istante, quindi i due numeri vengono fatti scorrere del registro a trasferimento dagli impulsi di orologio P1, P2, P3, P4 e P5.br/> Il trasferimento può essere espresso dalla seguente formula simbolica:


C_{i+1} =

dove Si e Ci sono le funzioni descritte nel cap.II parte II.
Le prime tre istruzioni simboliche indicano lo shift a destra dei registri A e B.
Le ultime due istruzioni descrivono la connessione del bit di riporto e la memorizzazione del bit somma nel Flip-Flop A5.
Il diagramma logico di questo addizionatore binario seriale è mostrato in (3.2.5)
Il metodo simbolico visto ora può essere utilizzato sia per costruire i diagrammi logici di un circuito , sia le equazioni logiche di quest'ultimo. Nella figura compare il diagramma logico di un accumulatore binario seriale. Esso consiste in un addizionatore seriale per eseguire la somma e in un registro a scorrimento per conservare uno degli addendi prima della addizione o la somma dopo l'addizione.


3.3
-Accumulatori binari

Per accumulatore binario, si intende un circuito in cui un registro memorizza un numero binario e appena ne riceve un'altr4o , quest'ultimo viene sommato (o sottratto) dal primo numero ee quindi viene memorizzata la somma (o la differenza). Un accumulatore può essere costruito per operazioni in parallelo o in serie.
Nella figura compare il diagramma logico di un accumulatore binario seriale. Esso consiste in un addizionatore seriale per eseguire la somma e in un registro a scorrimento per conservare uno degli addendi prima della della addizione o la somma dopo l'addizione.
La sottrazione può essere ottenuta mediante la somma del complemento a 2 del numero.



Se l'addizionatore seriale di fig.3.3.1 viene sostituito con un sottrattore seriale o con un addizionatore-sotttattore seriale, l'accumulatore può eseguire la sottrazione o entrambe le operazioni di somma e sottrazione.
In figura 3.3.2 viene mostrato un accumulatore binario parallelo.
Ogni Flip-flop dell'accumulatore funziona come un contatore modulo 2.
Il primo addendo è inizialmente conservato in questi contatori
Durante l'addizione ogni contatorer contegga gli impulsi rappresentativi del bit di addendo o di riprto, e genera un segnale di riporto quando il suo stato cambia da 1 a 0.
Il diagramma logico di un accumulatore binario parallelo relativo all'addizione viene ora descritto mediante il metodo simbolico.


In fig.3.3.3 consideriamo l'i-esimo stadio: l'addizione può essere decomposta in due pass; durante il primo vrengono sommati i bits Ai e Bi, durante il secondo vengono addizionate la somma risultante dal primo passo e il bit di riporto dovuto all'operazione di somma compiuta sui bit di rango inferiore.
Le istruzioni simboliche di questi due passi sono:

In queste istruzioni la somma di Ai e Bi avviene al clock pulse p1; la somma del risultante bit Aie del riporto Ci-1 avviene all'impulso seguente p2. Entrambe le addizioni hanno luogo dutasnte lo stato P1 che da l'ordine di addizionare da pate dell'unità di controllo.
Il bit di riporto può essere formato in più modi.>br/> Per esempio:

dove e math>\bar S_i</math> sono le uscite del Flip-Flop Ai dopo il clock pulse P1
La linea di ritardo assicura che il cambio di stato dello Flip-flop Aiavvenga dopo che si sia formato il nuovo riporto.
Un accumulatore può essere anche predisposto ad eseguire una sottrazione . In questo caso le istruzioni simboliche relative alla differenza sono le stesse di quelle relative alla somma mentre cambia l'espressione booleana che dà il riporto.
Chiameremo inoltre P2 lo stato del calcolatore che indica l'operazione di sottrazione.

dove Ri è la ritenuta:

essendo Di la differenza allo isimo stadio.
Nella figura 3.3.4 compare il diagramma logico di un accumulatore-sottrattore.

Nella figura 3.3.4 compare il diagramma logico di un accumulatore-sottrattore.


Si può ora formare un accumulatore relativo sia all'addizione che alla sottrazione.

Esaminando infatti i diagrammi 3.3.3 e 3.3.4 si vede che l'unica differenza tra i due consiste nella connessione della uscita del Flipo-Flop Ai.
Un accumulatore per addizione e sottrazione può allora essere costruito usando quattro addizionali porte di AND e due addizionali circuiti OR. (fig-3.3.5)
Quando lo stato è P1, l'accumulatore somma, quando lostato è P2, avviene la sottrazione.


3.4-Matrici di commutazione

Un importante circuito di un elaboratore digitale è costituito dalle matrici di commutazione, descrittenelseguito del paragrafo mediante l'ausilio delle matrici booleane.

3.4.1 Circuiti di commutazione con uscita multipla

Un circuito di commutazione con output multiplo può essere descritto mediante un certo numero di funzioni booleane.
Prendiamo come esempio il full-adder relativo ad un singolo bit.
Le tavole della verità sono date nel capitolo II° parte IIda e da queste si ottengono le formule per la somma S e il riporto C0:

dove X, Y e Cisono rispettivamente gli addendi, e il bit di riporto.
Queste funzioni possono essere scritte mediante i prodotti fondamentali:

Le due funzioni S e C_0 possono però essere espresse anche come:


Queste due ultime equazioni possono essere rappresentate mediante matrici booleane , come segue:

o con notazione matriciale:

dove [0], [B] e [m] sono rispettivamente la matrice di uscita , la matrice booleana B e la matrice dei prodotti fondamentali.
La moltiplicazione della matrice B per la matrice m segue le regole ordinarie della moltiplicazione dell'algebra matriciale.
In altre parole, gli elementi della matrice 0 sono la somma dei prodotti dei termini di m per i corrispondenti bit della matrice B, come mostrato nella 3.4.1 e 3.4.2.

La matrice B è costituita da due righe e otto colonne: ogni riga rappresenta una uscita mentre ogni colonna rappresenta un minterm.
Gli 1 dela riga 01101001 rappresentano i termini m1, m2, m4 m7 mentre quelli della riga 00010111 rappresentano i termini m3, m5, m6, m7: cioè la matrice booleana B rappresenta un insieme dei vettori caratteristici delle finzioni booleane S e C0.
Le espressioni booleane per S e C0 possono essere scritte mediante i maxterm (somme fondamentali).

espressioni equivalenti a :

Rappresentando le formule (3.4.3) e (3.4.4) mediante matrici booleane, si ha:


o con la notazione matriciale:


dove [M] è la matrice M dei maxterm.
In questo caso la moltiplicazione della matrice B per la matrice M non segue le regole ordinarie della moltiplicazione dell'algebra matriciale.
Infatti, come si vede dalle (3.4.4) e (3.4.5) il generico elemento della matrice prodotto è definito come il prodotto delle somme dei singoli termini di M con il corrispondente bit della matrice B.
Le funzioni (3.4.3) e (3.4.6) ottenute mediante notazioni matriciali, risultano espresse nelle due forme canoniche e le matrici booleane B delle due forme risultano identiche.
Quindi, quando di un circuito a più uscite, si conosce la matrice B della notazione matriciale booleana e quest'ultima è data in forma canonica, sono conosciute immediatamente anche le equazioni booleane di tutti gli output, sia nella forma canonica disgiuntiva che in quella congiuntiva.
Ovviamente si possono trovare immediatamente le espressioni e . Infatti:

oppure>br/>

Da cui le espressioni matriciali booleane:


oppure


dove [] è la matrice di uscita complementare e [] è la matrice B complementata.
E' da notare che ogni bit di è il complemento a 1 del corrispondente bit della matrice B
La moltiplicazione della matrice <magth>\bar B</math> per la matrice m segue le regole dellamoltiplicazione dell'algebra matriciale.:
Usando i maxterms, si ha invece:

da cui, le forme matriciali sono:


oppure:


La moltiplicazione della matrice B con la matrice M non segue le reggole ordinarie dell'algebra matriciale ma è definita da (3.4.4) e (3.4.5).


4.4.2-Matrici di commutazione rettangolari


La matrice di commutazione è un circuito con output multiplo: essa realizza una matrice booleana.
Le matrici più comuni sono quelle rettangolari, ad albero e a doppio albero.
Esistono però anche altri tipi di matrici.
Una matrice rettangolare che utilizza solo porte di AND è rappresentata in fig.3.4.1.
Tale matrice è relativa a tre variabili booleane e coinvolge nella sua realizzazione tre coppie di input e otto output.<br7> Per ogni prodotto delle tre variabili di input esiste uno ed uno solo output.
Le funzioni booleane dei 8 output sono:


Il circuito può anche essere espresso mediante una forma matriciale:
In questa matrice booleana compare un solo 1 in ogni riga e tutti gli 1 si vengono a trovare sulla diagonale principale.
Per la realizzazione del circuito non sono necessarie porte di OR.
Questa è la forma più semplice che può assumere una matrice B relativa ad una matrice di commutazione avente tre coppie di input ed otto output.
Si vede da fig.3.4.1, che per tre variabili sono necessarie otto porte di AND a tre ingressi. All'input di ogni AND led tre variabili di input possono comparire sia in forma diretta che in forma complimentata.
Per n coppie di variabili di input, il numero di input relativi alla porta di AND diventa di n 2n; cioè un numero molto elevato per un valore grande di n.
Matrici più economiche si ottengono mediante strutture ad albero 0 a doppio albero (vedi fig.3.4.3).
Una matrice retangolare con tre variabili di input e utilizzante porte di OR risulta essere uguale a quella di fig.3.4.1, dfove le porte di AND sono sostituite con porte di OR.
Le funzioni booleane delle otto uscite sono:





La matrice di commutazione si può allora rappresentare nella forma logica:
Il numero di input per le porte OR risulta essere anche esso 2n


3.4.3 - Matrici di commutazione ad albero

In figura 3.4.2 è rappresentata una matrice di commutazione adalbero costruita da circuiti AND e con quattro variabili booleane per input.
Vi sono quindi quattro coppie di input e 16 output.
Le equazioni booleane dei 16 output sono:






Le precedenti equazioni booleane possono essere scritte in forma matriciale. In questo caso, la matrice booleana è a livello multiplo ed i diversi livelli vengono indicati dalle precedenti parentesi tonde e quadre.
Vedremo in seguito tali rappresentazioni matriciali.
La seguente (3.4.2) è la rappresentazione di una matrice di commutazione ad albero con circuiti AND.


Nelle equazioni (3.4.9), le parentes onde e quadre indicano anche la maniera di connettere i blocchi di AND di fig.3.4.2.br/> Per n=2, sono necessari 23'input per gli AND-br/> Per n=3, sono richiesti per gli AND 23 + 24 inputs.
Per n coppie di variabili, è richiesto un numero N di inputs per ogni AND, dove N è dato da:


Rispetto alla matrice rettangolare , la matrice ad albero richiede un minor numero di inputs di AND.
Funzioni booleane di matrici di matrici ad albero aventi blocchi di OR hanno espressioni simili a quelli di (3.4.9), in termini però di somme fondamentali e la loro realizzazione circuitale si ottiene da quella di fig.3.4.2 sostituendo alle porte di AND quelle di OR.
In fig.3.4.3 viene mostrata una matrice a doppio albero con porte di AND, quattro coppie di variabili di input e 24 outputs.
Questa configurazione richiede un numero di inpus di AND'inferiore a quello delle configurazioni ad albero o rettangolari.
Le equazioni booleane dei 16 outputs del circuito sono:











Le funzioni pfrercedenti possono essere scritte mediante una formulazione matriciale: la matrice booleana è anche in questo caso a livelli multipli.
Le parentesi delle equazioni (3.4.10) indicano il modo di connettere i blocchi di AND di fig.3.4.3.





In figura 3.4.4 viene mostrato come si può realizzare una matrice con otto coppie di inputs e 256 outputs.
Gli otto inputs vengono divisi in due gruppi di quattro variabili ciascuno.
Se n non è multiplo di quattro, si può seguire lo stesso procedimento, solo che la configurazione risultante non sarà simmetrica.


3.4.4-Confronto tra i vari tipi di matrici


I tre tipi di matrici di commutazione (rettangolare, ad albero, a doppio albero)realizzano le stesse operazioni logiche ma richiedono un numero differente di inputs per le porte di AND (o di OR).
In tavola 3.4.5 vengono rappresentati i valori assunti dal numero di inputs per un n compreso tra 2 e 12.
Si noterà il rapido crescere degli inputs delle porte di AND in una matrice rettamgolare , all'aumento di n.
In una matrice ad albero, ogni volta che l'input aumenta di una coppia, il numero richiesto di input diventa più del doppio mentre in una matrice a doppio albero il numero risulta minore del doppio.
Queste differenze diventano molto sensibili quando n è, per es., dell'ordine di 12.
Ma lo studio degli input delle porte di AND non è sufficiente per la scelta della particolare matrice di commutazione.
Un'altra considerazione da fare è quella relativa al numero di livelli che un segnale deve attraversare dall'input all'output.
In una matrice rettangolare, il segnale passa attraverso un solo livello; per una matrice ad albero, esso deve passare attraverso n-1 livelli.
In una matrice a doppio albero il segnale passa attraverso un livello per n=2, due livelli per n=3 e 4, tre livelli per n=5 fino a 8, e quattro livelli per n che va da 9 a 16.


-3.4.5 Applicazioni delle matrici di Commutazione


In figura 3.4.6 (Matrici di commutazione usate come decodificatori e codificat0ri) e 3.4.7 (Matrici di commutazione usate come selettori e distributori) sono illustrate alcune applicazioni delle matrici di commutazione.
In fig.3.4.6 (a) appare un decodificatore.
Vi sono n coppie di inputs e 2n uscite. Come si vedrà nei capitoli seguenti, una porzione di una parola di istruzione di un calcolatore digitale costituisce un codice operativo ed il decodificatore utilizza tale codice per identificare l'istruzione da seguire e dare inizio alla sua esecuzione.
L'uscita di un decodifcatre può essere inferiore a 2n terminali, se lo si desidera.
Una variante di un decodificatore può essere un traduttore che traduca, per esempio, un numero in codice binario decimale nella corrispondente cifra decimale.
In questo caso vi sono quattro coppie di input (nel caso di un codice a quattro bit) e 10 uscite che rappresentano le 10 cifre decimali.
In fig.3.4.6(b) viene mostrato un codificatore: in esso vi sono 2n input e n coppie di outputs.
Per esempio, le ventisei lettere dell'alfabeto possono essere codificate mediante ventisei combinazioni di cinque variabili booleane.
In fig.3.4.7.(a) viene mostrata una matrice di selezione . In questa matrice vi sono due gruppi di inputs e una uscita.
Un gruppo, costituito da 2n terminali di inputs, è connesso alla sorgente dei segnali, e l'altro grippo , costituito ds da n coppie di inputs, viene attivato da un codice selezionato.
In uscita , ad ogni istante, compare un solo segnale. Per esempio, una parola seriale può essere letta dal dispositivo di un canale selezionato su tamburo magnetico.
In questo caso le n coppie di input di fig.3.4.7(a) rappresentano l'indirizzo del canale, i 2n input provengono dal dispositivo di lettura e l'output dà la parola letta.
Viceversa, un distributore, come da fig.3.4.7(b), ha 2n uscite, un segnale sorgente ed n coppie di input.
Il segnale viene distribuito nelle varie uscite mediante una data combinazione delle n coppie di entrata.


Per esempio, una parola seriale che arriva da una sorgente di segnali viene distribuita al canale selezionato su tamburo magnetico.
Se le n coppie di fig.3.4.6(a) provengono da un contatore binario che conteggia una sequenza di impulsi di orologio, il circuito risultante si dice commutatore (fig.3.4.8):
In un commutatore , le uscite sono selezionate una dopo l'altra, secondo la sequenza degli stati del contatore.
Per esempio, un commutatore può essere usato per inviare segnali ai vari canali secondo una particolare sequenza temporale.
Le matrici possono essere anche usate come generatori di sequenza o come filtri di sequenze.


3.4.6 - Esempi di matrici di commutazione






(.a)- Un Full-adder può essere considerato una matrice di commutazione: le equazioni 3.4.2 e 3.4.2, ne danno la rappresentazione booleane.

In fig.3.4.9 compare il diagramma logico: la porzione di sinistra del circuito è costituito da una matrice rettangolare di porte di AND.

vi sono solo sette porte di AND in quanto nelle equazioni 3.4.1, 3.4.2, compaiono solo sette prodotti fondamnetali (sugli otto possibili determinati dalle tre variabili booleane).

Le linee orizzontali aggiuntive costituiscono gli input dei due circuiti OR i cui output sono S e C0: la disposizione delle connessioni degli input per le porte OR corrisponde alla disposizione dei bit 1 e 0 delle righe nella matrice booleana B che compare in 3.4.3 per la rappresentazione matriciale del Full-adder.

La matrice rappresentativa di un Full-adder viene chiamata una AND-OR matrix.

Se la sintesi del circuito viene fatta partendo dalle operazioni 3.4.4, la matrice risultante viene chiamata OR-AND matrix (fig.4.4.10)


(.b)- La matrice rettangolare di fig.3.4.11 è la sintesi della tabella della verità posta qui sul lato destro.

La matrice rappresenta un traduttore che converte un digit codificato nel codice binario 8.4.2.1, nel corrispondente digit decimale.

Poiché delle sedici combinazioni possibili dovute alle quattro variabili booleane solo le prime 10 vengono prese in considerazione, la matrice di fig.3.4.11, è il diagramma logico delle matrici booleane seguenti

Analogamentesi possono costruire matrici di conversione relative ai codici tipo ad eccesso ditre. etc..




(.c)- Le matrici a) e b) sono rappresentate in forma booleana da matrici booleane di tipo elementare.
Volendo usare matrici a più livelli, si possono usare matrici booleane di forma non elementare.
Un circuito di confronto tra due numeri binari è anch'esso un circuito a più uscite: siano A e B le due parole binarie da confrontare. Il modo di operare del comparatore è descritto dalle seguenti equazioni booleane (supponendo che A e B siano costituite da tre bit ciascuna):






Le funzioni f1, f2, f3 diventano rispettivamente uguali ad 1 quando la prima, la secondas e la terza coppia di bit corrispondenti sono uguali e la funzione f diventa 1 quando le f1, f2, f3 sono tutte uguali ad 1.

Le quattro funzioni possono essere scritte mediante la forma matriciale non elementare rappresentata a destra::

Questa funzione viene realizzata dalla matrice di fig.3.4.12. Questa è una matrice AND-OR-AND con 21 input. Se la funzione ì viene scritta mediante prodotti fondamentali la corrispondente matrice rettangolare richiede 56 inputs.


3.5- Generatori di sequenze binarie

Per sequenza binaria si intende una sequenza temporale di bit 1 e 0., L'intervallo di tempo che intercorre tra due bit adiascenti viene chiamato bit time o digit time.
Un numero decimale codificato in BCD può essere rappresentato con diverse sequenze binarie. Per esempio, consideriamo il numero decimale 159. Nel codice 8.4.2.1 esso diventa 001,0101,10001.
In fig.3.5.1 vengono fatti vedere quattro possibili modi di rappresentare questo numero.


In fig.3.5.1(a), tutti i digits e i bits appaiono in una sequenza binaria. essa è una rappresentazione del tipo serial digit-serial bit.
Se i digit arrivano sequenzialmente mentre i bit sono in parallelo (fig.3.5.1(b)), si ha una rappresentazione serial digit-parallel bits
In fig.3.5.1(c) i digits sono in parallelo e i bits in serie: si ha quindi una rappresentazione parallel digit-serizal bits
In fig.3.5.1(d) sia i bits che i digits sono in parallelo. avremo così una rappresentazione parallel digit.parallel bits

In un calcolatore digitale lascelta della rappresentazione dipende da diverse considerazioni quali la velocità di calcolo, il numero dei componenti ect.
Una matrice di commutazione può essere considerata come un filtro di sequernza o un generatore di sequenza.
Se la matrice filtra secondo un certo criterio una sequenza di input, viene detta binary sequence filter: tali sono ad esempio il full adder ed il traduttore. Per ogni insieme di input viene prodotto come output un altro insieme di sequenze binarie.

Se viene considerato come input di una matrice solo una certa scelta di sequenze binarie e l'uscita è uconosciuta sequenza , si dice che la matrice è un binary sequence generator.





In fig.3.5.2 viene mostrato un generatore di sequenze binarie: un contatore binario conteggia gli impulsi di un orologio: per ogni stato del contatore, la matrice produce un output costituito da un digit BCD
Quindi mentre un contatore binario conteggia, viene generato un numero decimale del tipo serial-digit parallel bit.
La matrice descritta in tav.3.5.3 permette di generare la costante π: l'output del contatore binario è rappresentato mediante le lettere A,B,C,D e l'output della matrice dalle lettere W,X,Y,Z.
Entrambi gli output sono espressi in numeri binari. il contenuto delle colonne W,X,Y,Z rappresenta il numero decimale 3141592653589793 , dove si assume che la virgola sia posta tra i primi due bit più significativi.
Le quattro funzioni di output possono essere scritte partendo dalla tavola 3.5.3. Se queste funzioni vengono minimizzate, si ottiene la matrice booleana di tav.3.5.4.
La matrice booleana è in forma elementare: in fig.3.5.5 compare un generatore della costante π sotto forma di AND-OR MATRIX.


3.6-Semplificazione delle matrici booleane<br/

Nei paragrafi precedenti è stato mostrato come un circuito di commutazione con output multiplo può essere rappresentato mediante una matrice booleana d forma canonica, di forma elementare o non.
Nel seguito verranno riassunte le caratteristiche di una matrice booleana:

1) Ogni riga della matrice rappresenta una funzione booleana ovvero un output della matrice di commutazione.

Il numero delle righe nella matrice non può essere ridotto a meno che una riga non sia composta da soli zeri oppure due o più righe siano identiche.

2) Ogni colonna della matrice rappresenta un prodotto (od una somma).

Il numero delle colonne è riducibile e si deve cercare di renderlo minimo.

3) Se una riga della matrice consiste di tutti 0, la riga ed il suo output possono essere tolti dalla matrice.
4) Se una colonna nella matrice consiste di tutti 0, il termine corrispondente nella matrice [n] o [M] può essere eleminato.
5) Se vi è un solo 1 in ogni riga, la matrice di commutazione consiste di sole porte di AND (oppure di OR).
6) Se vi è più di un 1 in almeno una riga, la matrice di commutazione è una matrice AND-OR quando la matrice della funzione è della forma [m] oppure una matrice OR-AND se la matrice della funzione è della forma [M].
7) Quando un output di una matrice booleana, risulta essere una variabile di un prodotto (o di una somma) di un'altra rappresentazione matriciale, la risultante matrice di commutazione ha due o più livelli.

Con la semplificazione di una matrice booleana, si ottiene di conseguenza quella della matrice di commutazione risultante.
Il procedimento che si segue è quello di minimizzare le singole funzioni booleane con i soliti metodi.
Se la matrice data è in forma canonica e non può essere minimizzata e il numero di bit 1 è superiore a quelli 0, la matrice B booleana complementare risulta più semplice.
La semplificazione può essere ottenuta talvolta esprimendo la matrice in forma non elementare.


3.7-generazione di segnali di controllo.

Un calcolatore digitale opera per passi successivi e durante ogni passo viene eseguita una micro-istruzione. Esempi di micro-istruzioni sono gli schift, il conteggio, il trasferimento, la somma, l azzeramento, la complementazione. Una sequenza di micro-istruzioni costruita per raggiungere un determinato scopo costituisce una operazione.
Un calcolatore digitale è progettato per eseguire un certo insieme di operazioni. Queste operazioni son codificate mediante un certo numero di bits: specificando il codice operativo tramite i bits che fanno parte di una voce si puo informare il calcolatore di eseguire la corrispondente operazione.Per le istruzioni semplici , ogni istruzione consiste in un codice operativo e in un indirizzo (vedere cap.IV parte II).
Il programmatore scrive una sequenza di istruzioni e questa costituisce un programma capace di risolvere un certo problema. Quando un calcolatore riceve un'istruzione, il codice operativo contenuto in quest'ultima viene trasferito e memorizzato in un registro di operazioni. Sono necessari allora dei circuiti logici capaci di generare in corrispondenza al codice operativo dei segnali di controllo appropriati che comandano una sequenza di micro-operazioni.


La fig.3.7.1 mostra una semplice configurazione per la generazione di segnali di controllo.
Essa è costituita da un registro, un decodificatore, un orologio, un distributore di livelli temporali, una matrice di controllo.
Supponiamo che in un calcolatore siano previste 16 operazioni e che queste siano codificate con un codice operativo a 4 bit: siano fi con i da 0...a 15.
Assumiamo che vi siano 10 micro-operazioni (con cui vengono formate 16 sequenze di micro operazioni rappresentative delle sedici operazioni) e che i segnali di controllo per queste micro-operazioni siano designate con mj, j=0,...,9.
Il fine perseguito dal circuito di fig.3.7.1 è quello di generare, per ogni codice operativo contenuto nel registro delle operazioni, una corrispondente sequenza di segnali di controllo di micro-operazioni.
Quando la parte del codice operativo di una istruzione viene memorizzata nell'Operation register, il decodificatore a 16 linee di uscita (ognuna per uno dei 16 codici operativi) attiva una e una sola linea.


Nello stesso istante, dei livelli temporali vengono generati mediante un orologio da un timing level generator.
Supponiamo che vi siano 5 linee di uscita del generatore di livelli ed indichiamole con tk k=1,...,5: i livelli generati da tali linee vengono mostrati in fig.3.7.2.
Questi livelli costituiscono una sequenza temporale chiamata ciclo temporale di base
Il numero di livelli in un ciclo base è scelto generalmente in modo da poter eseguire una istruzione (quindi controllare una sequenza di micro-operazioni).
Per certe istruzioni quali la moltiplicazione e la divisione spesso vengono usati più di un ciclo base e quindi viene aggiunto un contatore (che non figura in fig.3.7.1) in modo da conteggiare il richiesto numero di cicli base. L'nput della matrice di controllo è costituito dalle 16 linee fi, output del codificatore e dalle 5 linee tk, outputs del generatore di livelli temporali.
La matrice ha 10 linee di uscita e il segnale di ciascuna di queste linee controlla una specifica micro-operazione.
Questi segnali sono rappresentati dalla lettera mj Ogni mirco-operazione è realizzata DALLA COMBINAZIONE DEL SEGNALE DI CONGTROLLO E DA UN SEGNALE DI OROLOGIO.
Le funzioni relative alla matrice di controllo sono, per esempio, quelle del seguente sistema di equazioni logiche:



---------------

dove p rappresenta il segnale dell'orologio. La prtima equazione dice che la micro-operazione m0 è controllata dal codice operativo al livello temporale t1, o dal codice operativo f7 al livello t3, o dal codice operativo f9 al livello t4: la micro-operazione viene eseguita quando compare il segnale p dell' orologio. La matrice di controllo del sistema di equazioni logicheè essenzialmente una matrice di commutazione AND-OR.

Progetto logico di un calcolatore digitale

Nei capitoli precedenti sono stati descritti i circuiti logici capaci di manipolare le informazioni e di memorizzarle ed è stato presentato un metodo algebrico utile alla rappresentazione di questi circuiti.
Nel presente capitolo si cercherà di presentare il progetto logico di un semplice calcolatore digitale.

4.1-Progetto del calcolatore

Un calcolatore digitale opera mediante delle informazioni , numeriche o di altro tipo, rappresentate in forma digitale.
Dal punto di vista del progetto logico, un calcolatore digitale può essere idealmente descritto come l'insieme de dispositivi di memoria bistabili (per es. Flip-Flop) connessi da reti logiche.
Lo stato di queste memorie di tipo discreto cambia in certi istanti; lo stato iniziale viene fissato dal programma.
La programmazione di un problema per un calcolatore digitale consiste nella preparazione di una sequenza di istruzioni mediante la quale il problema dato viene risolto dal calcolatore.
Per questo fine, la programmazione comprende l'analisi del problema, la preparazione di un diagramma a blocchi, e la codifica delle istruzioni. Il progetto di un calcolatore digitale può essere diviso in tre fasi: progetto del sistema, progetto logico, progetto dei circuiti.
Nella prima fase vengono prese in considerazione le richieste del problema e le specifiche del calcolatore tenendo conto del costo, delle dimensioni, della manutenzione, ecc. Questa fase richiede siano precisate le operazioni richieste (aritmetiche, logiche , e altre), la velocità delle operazioni , i metodi per il controllo degli errori ed altri dispositivi quali:registri indice, interruttori, ecc., capaci di fornire un uso più efficiente della macchina.
Si può includere in questa fase la selezione del tipo di circuiti logici, il tipo di memoria e le sue capacità, la qualità e la quantità dei dispositivi di input-output.
La seconda fase stabilisce il formato della parola, la configurazione della macchina e l istruzioni di macchina; questa fase termina una volta stabilito un insieme di equazioni logiche o un insieme di diagrammi logici dettagliati.
La terza fase comporta il progetto dei circuiti logici, della memoria e dei dispositivi di ingresso-uscita.<bra sua volta, /> Il progetto logico di un calcolatore può essere, a sua volta, diviso in tre fasi: progetto funzionale, progetto simbolico, progetto dettagliato. Nella prima fase viene stabilito, innanzi tutto, il formato della parola. Vengono scelti i registri, i contatori, le matrici, gli addizionatori e gli altri elementi; questi vengono completati con la memoria scelta ed i dispositivi di input-output in modo da stabilire un particolare insieme di istruzioni di macchina:
Nella seconda fase viene stabilita la sequenza di controllo del programma e le istruzioni di macchina vengono espresse in istruzioni simboliche. Durante questa fase è utile uno studio dettagliato della sequenza di operazioni relative alle istruzioni di macchina
Nella terza fase viene elaborato un insieme di equazioni logiche od un insieme di diagrammi logici che descrivono le singole le singole operazioni del calcolatore.>br/> Nell'attuale progetto logico di un semplice calcolatore digitale , vengono costruite in modo completo le equazioni logiche ; i diagrammi logici verranno mostrati abbastanza dettagliatamente in modo che il diagramma copleto possa essere ricavato dal lettore.

4.2-Progetto del sistema

Il calcolatore che verrà illustrato nel seguito fornisce un esempio di progetto logico di un calcolatore digitale capace di memorizzare un programma (stored-program computer) e capace di eseguire un certo numero di operazioni elementari quali la somma, la sottrazione, lo shift a destra e a sinistra di un bit, il trasferimento condizionato e incondizionato. Per semplicità il funzionamento del calcolatore si considera sincrono, binario e parallelo.

4.3-Progertto funzionale

La prima fase del progetto del progetto logico è il progetto funzionale: innanzi tutto viene stabilito il formato della parola.
La configurazione del calcolatore viene formulata scegliendo i registri, le matrici, la memoria ed i dispositivi di input-output. Vengono stabilite le istruzioni di macchina e si dà una breve descrizione della sequenza operativa.

Formatto della parola

Una parola (o voce) in un calcolatore è un insieme ordinato di digits che viene trattato dal calcolatre come una unità unitaria.
Si dice che il calcolatore ha una struttura a parole (a voci) se un da e che questa sia piccola.to numero o una istruzione viene rappresentata mediante una parola.
Per facilitare lo studio del nostro ipotetico calcolatore, supponiamo di fissare la lunghezza della parola e che questa sia piccola. Come vedremo una parola corta consente un numero piccolo di istruzioni di macchina e di indirizzi di memoria.
La lunghezza di parla scelta per questo esempio è di 9 bits:


Una parola viene trattata dalla unità aritmetica come un numero: in questo caso il formato della parola viene chiamato formato del numero .
Sempre in questo esempio, il numero viene dato in una rappresentazione binaria frazionaria con i numeri negativi dati dal complemento a 2 del corrispondente numero positivo.
Il punt0 binario viene rappresentato idealmente tra i bits x_0 e x_1, mentre x_0 rappresenta il segno.
Poichè il valore di un numero binario con segno è compreso nell'intervallo -1≤x<1 il nostro calcolatore viene chiamato binary fractional computer.
Quanto detto non costituisce una vera restrizione per i calcoli, poiché un numero furi dell'intervallo sopra indicato può essere rappresentato nel calcolatore moltiplicandolo per 2n, con un appropriato valore di n.
La moltiplicazione per 2n non è altro che una operazione di shift.
Poiché il punto binario è fisso, il calcolatore è un fixed-point computer.
Esso differisce da un floating-point computer, capace di lavorare con una aritmetica in virgola mobile.


La parola considerata come istruzione è suddivisa in due parti (campi): il codice operativo e l'indirizzo. Il formato istruzione del nostro calcolatore sarà quindi:
Con un solo indirizzo, questo formato viene chiamato simple -address format
La porzione di tre bit chiamata codice operativo costituisce un codice binario di una operazione di macchina: perr es. esso indica un trasferimento, una operazione aritmetica o logica.
I sei bits della parte indirizzo costituiscono il numero dell'indirizzo di memoria di una voce; questa parola di memoria viene chiamata operando. Un tale formato di istruzione indica che una operazione (specificata dalla porzione di codice operativo) viene eseguita sull'operando conservato nella posizione di memoria specificata dalla porzione di indirizzo.
Certe istruzioni non necessitano di operandi:in questo caso la parte relativa all'indirizzo può essere usata per altri scopi.


configurazione del calcolatore


La configurazione del nostro calcolatore ipotetico è mostrata in fig.4.3.1.
Per essere uno stored-programm computer il calcolatore deve memorizzare sia i numeri che le istruzioni.
Questa considerazione fa introdurre l'unità di memoria (indicata cin i registri M): la sua capacità è di 64 parole di 9 bits ciascuna.
Come mostrato in figura 4.3.2, questi flip-flop sono denotati con M(ji), dove j indica la J(sima) parola ed i il bit(simo).
ene messo tra il registr
C Ad ogni locazione di memoria viene attribuito un indirizzo : la selezione degli indirizzi viene fatta mediante il memory register C.
Il registro C consiste di 6 Flipo-Flop (fig.4.3.2).
Un duplicatore di indirizzi viene messo tra il registro C e la memoria.
Perché il calcolatore possa eseguire operazioni aritmetiche, occorre introdurre una unità aritmetica, capace in questo caso semplice di sole somme e sottrazioni.
Un accumulatore (registro A) è sufficiente come unità aritmetica: esso consiste in 9 bits, in modo da memorizzare una intera parola (fig.4.3.2)

Quando una istruzione viene presa dalla memoria, essa viene conservata temporaneamente in un registro per essere successivamente eseguita. L'apposito registro viene chiamato intruction register (R) ed è ovviamente di 9 bits
I bit R0 R1 R2 memorizzano il codice operativo, mentre i 6 bits da R3 a R9 conservano la parte indirizzo della parola istruzione.
La necessità di eseguire un controllo di sequenze introduce la program control unit.
Il nostro calcolatore ha un operation counter (F), di 4 bits (fig.4.3.2), I tre bits F2 F3 F4, danno il codice operativo.
L'operation counter conteggia gli impulsi di un orologio e genera i segnali di controllo mediante un decodificatore di operazioni.
Un generatore di impulsi d'orologio da una sequenza di impilsi temporsali con periodo τ.
L'impulso di orologio serve a sincronizzare le operazioni del calcolatore.
Un altro clock-pulse generator ( non indicato in fig.4.3.1) genera un singolo impulso: esso è sotto il controllo dell'operatore che in questa maniera, può osservare il procedere del calcolatore passo per passo.
Altro dispositivo di controllo è il Fliop-Flop G, capace di avviare od arrestare le operazioni del calcolatore.
Il controllo del Flipo-Flop G è accessibile all'esterno mediante lo switch (interruttore) S.
Come dispositivi di input capaci di inserire in memoria dati e istruzioni, vi sono gli switchs Q mentre per fornire i risultati ci possono essere dei dispositivi luminosi ( non indicati in fig.4.3.1). Sia gli switchs Q che i dispositivi luminosi sono connessi ai singoli bit di memoria.
I dispositivi luminosi sono anche connessi ai singoli bit dei registri in modo da osservare le operazioni del calcolatore durante eventuali test.


Istruzioni di macchina

Formuliamo ora l'insieme di istruzioni che la macchina è capace di eseguire.
La lista di istruzioni capace di risolvere un certo problema deve essere ovviamente codificata prima di essere caricata nel calcolatore in modo che le istruzioni stesse siano comprensibili alla macchina:
Le istruzioni eseguibili da questo calcolatore ipoteticosno raggruppate in tabella 4.3.3 seguente

Codice........... Istruzione Desceizione dell'istruzione
000 uvwxyz Addizione Prende il numero dalla memoria all'indirizzo uvwxyz, lo mette nel regisro R; somma il conternuto di R al contenuto del registro A e conserva il risultato nel registro A.
001 uvwxyz Sottrazione Prende il numero dalla memoria all'indirizzo uvwxyz, lo mette nel regisro R; sottrae il conternuto di R al contenuto del registro A e conserva il risultato nel registro A.
010 uvwxyz trasferimento condizionato Se A0=1 (segno di A negativo) si prende come nuova istruzione quells contenuta nella memoria all'indirizzo uvwxyz; se A0=0 (segno di A positivo), si prende la nuova istruzione in sequenza.
100 uvwxyz trasferimento incondizionato Prende la nuova istruzione dalla memoria di indirizzo uvwxyz.
011 uvwxyz Memorizzazione Memorizza il contenuto del registro A nell'indirizzo uvwxyz di memoria
1011000 yz Shift a destra -
1010100 yz Shift a sinistra Ilo contenuto del registro A viene shiftato a sinistra di 1 bit.
1010010 yz Azzera l'accumulatore Si azzera l'accumulatore A
1010001 yz Stop Stop della macchina e nel registro C compare l'indirizzo 000000.

Poiché la macchina non o0mpie alcuna operazione in relazione agli organi di input-output, non sono previste istruzioni relative ad operazioni di ingresso-uscita.
La quantità uvwxyz indica uno dei 64 possibili indirizzi di memoria.
E' da osservare che le ultime quattro istruzioni di tabella 4.3.3 non fanno riferimento a posizioni di memoria (cioè non è necessario un operando e quindi la parte indirizzo può essere utilizzata nella codificazione del codice operativo).
Quindi, pur avendo solo 3-bit a disposizione del codice, si hanno in effett nove operazioni.

sequenza operativa del calcolatore

Facendo riferimento alla configurazione di fig-4.3.1, le istruzioni codificate che formano un programma vengono inserite per prima cosa in memoria tramite l'interruttore Q attraverso la porta A7.
L'operatore pone l'interruttore S in posizione ON e la macchina incomincia a funzionare.
Lo stato di tutti i registri viene cambiato tramite i segnali di controllo provenienti dallo operation counter.
Questi cambiamenti possono solo aver luogo in concomitanza degli impulsi di orologio.
Quando la macchina opera per la prima volta, il contenuto del registro C è 000000; per cui la prima parola di memoria è la prima istruzione.
Il segnale di controllo h trasferisce questa istruzione dall'unità di memoria al registro R tramite le porte A3 e A4.
La parte codice operativo della istruzione che si trova ora nel registro R viene trasferita al registro F tramite la porta A8 sotto il controllo del segnale i, mentre il segnale di controllo c trasferisce la parte indirizzo tramite la porta A1 al registro C.
Il codice operativo nel registro F è ora decodificato e vengono generati i comandi necessari all'esecuzione dell'istruzione,
Per le operazioni aritmetiche, il segnale di controllo d trasferisce, attraverso le porte A3 e A4, un numero dalla memoria al registro R, ed il segnale di controllo g determina, mediante la porta A9, la realizzazione di una specifica operazione aritmetica sul numero contenuto in R e su quello inizialmente in A.
Per le operazioni di shift e di azzeramento dell'accumulatore si ha il segnale di controllo f.
L'operazione di trasferimento relativa alla sequenza di controllo avviene sotto i segnali b o H, mentre il segnale e, selezionando la porta A6, conserva mediante la porta A5, il controllo dellaccumulatore nella memoria all'indirizzo che si trova nel registro C.
L'ultima istruzione del programma in memoria è in genere una istruzione di stop: l'operation counter invia il segnale di controllo a al Flip-Flop G e la macchina si ferma.


4.4-Fase di progettazione simbolica

In questa fase viene stabilita la sequenza di controllo del programma e le operazioni di macchina vengono rappresentate mediante espressioni simboliche.
Tra i simboli già introdotti nel Cap.3 Parte IIa, dobbiamo introdurre il seguente: < >, con cui indichiamo l'indirizzo di una parola di memoria e precisamente M<C> indica la locazione di memoria il cui indirizzo è nel registro C.
Le istruzioni indicate in tabella 4.3.3 vengono ora espresse in termini di espressioni simboliche elencate nella seguente tabella 4.4.1

Istruzioni.....................................................br/> ! Operazioni richieste............... Operazioni ausiliarie
Addizione (000uvwxyz) (M<C>=>R ; (R)+(A)=>A (Ad[R])=>C ; (C)+10=>C
Sottrazione (001uvwxyz) (M<C>R=>R ; (A)-(R)=>A come sopra
Trasferimento condizionato (010uvwxyz) nessuno come sopra se A0=0 nessuno se A0=1
Memorizzazione (011uvwxyz) (A)=>M<C> (Ad[R])=>C ; (C)+1=>C
Trasferimento incondizionato (100uvwxyz) nessuno nessuno
Shift right (1011000) (A{i-1}=>Ai ; (A)0=>A0 (Ad[R])?>C ; (C)+1=>C
Test Shift left (1010100yz (Ai+1)=>Ai ; (A0)=>A8 come sopra
Azzeramento accumulatore (1010010yz 0=>A come sopra
Stop (10010001yz) 0=>G ;0=>C ; 1=>F nessuna
Comando d'avvio (manuale) 1=>G nessuna
Comando inserimento dati (manuale) (Qij)=>Mij nessuna


L'addizione mostrata in tabella 4.3.3 è costituita da due operazioni La prima operazione consiste nel prendere un numero dalla memoria di indirizzo uvwxyz e metterlo nel registro R, simbolicamente.


dove C contiene l'indirizzo di memoria uvwxyz.
La seconda operzione è: addizionare il contenuto del registro R al contenuto del registro A, e conserva il risultato nel registro A. Simbolicamente si ha:


Nella tabella 4.4.1 compaiono le due espressioni simboliche per la istruzione di addizione. Si hanno inoltre due espressioni simboliche simili alle precedenti , per la sottrazione.
L'istruzione di memorizzazione del contenuto del registro (A) nella memoria di indirizzo uvwxyz, si esprime come:


dove C contiene il riferimento all'indirizzo di memoria uvwxyz.
L'istruzione di shift' a destra consiste nello spostare il contenuto del registro A di un bit a destra e simbolicamente:



La seconda espressione dice che lo shift a destra richiede che il bit più a sinistra del registro A conservi il valore originale durante l'operazione di scorrimento.
L'operazione di shift a sinistra richiede che il contenuto del registro A sia spostato di 1 bit a sinistra:



Questa operazione di shift a sinistra muove il bit più a sinistra del registro A in maniera circolare.
L'azzeramento dell'accumulatore diventa:


L'istruzione di stop consiste nell'arrestare la macchina e porre nel registro C il primo indirizzo 000000; simbolicamente:


L'operazione di avvio del calcolo e di inserimento delle istruzioni dei dati in memoria non vengono indicate in tabella 4.4.1 in quanto operazioni manuali.
Simbolicamente, esse sono:


La prima espressione indica il set del Flip-Flop G mentre la seconda indica l'inserimento del contrnuto dell'interruttore Qji nel bit di memoria Mji


4.4.1-Ciclo d'istruzione e ciclo di esecuzione

Sia le istruzioni che i dati di un programma capace di risolvere un certo problema vengono inizialmente conservati in memoria.
Il programmatore scrive queste istruzioni in una sequenza in accordo con l'ordine degli indirizzi di memoria in cui queste istruzioni verranno memorizzate.
Nel nostro calcolatore ipotetico la prima istruzione del programma viene messa nella posizione 000000.
Il calcolatore esegue la sequenza di istruzioni conservata in memoria: esso opera secondo una sequenza interna eseguendo ogni istruzione come vengono chiamate , una dopo l'altra, dal programma.
La sequenza interna passa da un ciclo d'istruzione ad un ciclo di esecuzione. Durante il ciclo istruzione viene presa una istruzione dalla memoria e il calcolatore viene posto nelle condizioni di poter compiere la esecuzione di una sola istruzione.
Durante il ciclo esecuzione viene eseguita l'istruzione ed il calcolatore viene posto nelle condizioni di poter tornare al ciclo istruzione.
In fig-4.4.2 sono raffigurati entrambi i cicli.


Durante la fase del ciclo di istruzione vi sono quattro operazioni (fig-4.4.3a); la prima permette di prendere una istruzione: una parola viene presa dalla memoria il cui indirizzo è nel registro C (000000 per la prima istruzione ) e trasferita nel registro R; simbolicamente:


Il contenuto di C (memory-address) durante questa operazione è un instruction address. La seconda e terza operazione (che avvengono contemporaneamente) sono operazioni di trasferimento mediante le quali vengono trasferite la porzione del codice operativo dal registro R, Op[R], nella porzione istruzione del registro F, e la parte indirizzo di R, Ad[R] nel registro C:



A questo istante la la parte indirizzo di R, è un operand address e quindi non è più l'indirizzo di istruzione menzionato nella fase precedente.
Dopo il trasferimento la parte di codice operativo fa generare dal decodificatore di operazioni, dei segnali di comando, dando cosi inizio all'esecuzione della istruzione mentre l'indirizzo dell'operando si trova ora nel registro R:
Normalmente questo ciclo istruzione è completo: nel nostro calcolatore ipotetico, data la sua semplicità, è necessaria una quarta operazione che trasferisca l'indirizzo della istruzione contenuta in C nella parte indirizzo di R:


Il motivo di questa ulteriore operazione è dovuto al fatto che la parte indirizzo del registro R (operand address) viene trasferita nel registro C e quindi l'indirizzo della istruzione contenuta in C (000000 per la prima istruzione) viene perduto.>br/>


Questo indirizzo della istruzione che è stato preso in considerazione deve essere conservato in qualche maniera in quanto l'indirizzo della nuova istruzione è ottnuto da quello della presente, sommando 1.
Poiché la parte indirizzo del registro R è stata trasferita nel registro C e non è usata per il momento. l'indirizzo della presente istruzione può essere trasferito per una memorizzazione temporanea nella parte indirizzo del registro R.
In altre parole, l'indirizzo della presente istruzione contenuto in C viene trasferito in R e nello stesso istante l'indirizzo dell'operando contenuto i R viene trasferito in C.
Questi due trasferimenti simultanei sono possibili se si fa l'ipotesi che i Flip-Flop dei registri R e C abbiano un delay sufficiente.
In un calcolatore digitale ordinario con capacità di memorizzazione di programmi c'è generalmente un ulteriore contatore di istruzioni atto a memorizzare l'indirizzo della attuale istruzione e, tramite incremento di 1 unità dopo l'esecuzione di una istruzione si determina l'indirizzo della nuova istruzione da eseguire.
In tal caso non è necessaria l'operazione di trasferimento da C ad Rprecedentemente descritta.
Le operazioni che avvengono durante il ciclo istruzioni sono sempre le stesse , mentre quelle che compaioni durante il ciclo esecuzione dipendono dal codice operativo dell'istruzione.
In fig-4.4.3b si è preso in considerazione il ciclo esecutivo di una istruzione d'addizione: esoo incomincia prendendo la parola operando dalla memoria localizzata dall'operand address contenuto in C. La parola operando è trasferita nel registro R che viene utilizzato attualmente come memoria temporanea:


Durante l'operazione di caricamento dell'operando , il contenuto della parte indirizzo di R che alro non è se non l'indirizzo della attuale istruzione, viene trasferito in C:


L'operando ora contenuto in R viene addizionato al contenuto del registro <a' (che è un accumulatore):


Infine, il contenuto del registro C (contenente l'indirizzo della attuale istruzione) viene incrementato di 1 diventando cosi l'indirizzo della nuova istruzione:


Cosi il ciclo esecutivo risulta completo.
La nuova istruzione è pronta per essere presa dalla memoria mediante la prima operazione del ciclo istruzione dell'indirizzo di memoria indicato dal contenuto di C.
Nel caso di una istruzione di trasferimento incondizionato, l'indirizzo della nuova istruzione è dato dall'indirizzo dell'operando.
Nel caso di una istruzione di trasferimento condizionato, la sequenza proce de come nel caso del trasferimento incondizionato , se la condizione è verificata (A0=1); se la condizione non è verificata (A0=0), la nuova istruzione da eseguire viene determinata mediante l'operatore (C)+1=>C.
L'operazione ausiliaria (1=>F) viene spiegata nel seguito.


-4.4.2 Diagramma di stato

L'unità di controllo del programma (registro F) del nostro calcolatore ipotetico consiste in un contatore e in un decodificatore associato (fig-4.3.2).
Gli stati del contatore rappresentano gli stati del calcolatore; quindi la sequenza degli stati del contatore controlla la sequenza operativa del calcolatore.>br/> Poiché sono contemplate nove operazioni, sono richiesti all'operation counter nove stati, e ciò implica un minimo di 4 Flip-Flop, F1,F2,F3,F4.
I Flip-Flop f2 e f4 costituiscono la parte istruzione del registro F(o I[F]); in essi vengono memorizzati i 3 bit della porzione codice operativa del registro istruzioni R.
Per un contatore cob quattro flip-flop, si possono presentare 16 stati; essi vengono indicati con la notazione fi in tabella 4.4.4 (l'indice i rappresenta il numero binario corrispondente di 4 bit).
ogni atato rappresenta 1 segnale di comando. come si vede da tavola 4.4.4.>br/>


operation counter F1 F2 F3 F4.......... stato................. segnali di comando
0 0 0 0 f0 comando di addizione
0 0 0 1 f1 comando di sottrazione
0 0 1 0 f2 comando di trasferimento condizionale
0 0 1 1 f3 comando di imaggazinaggio
0 1 0 0 f4 comando ciclo istruzioni
0 1 0 1 f5 comando per f12, f13, f14, f15
0 1 1 0 f6 non usato
0 1 1 1 f7 non usato
1 0 0 0 f8 comando operazione di addizione
1 0 0 1 f9 comando operazione di sottrazione
1 0 1 0 f10 comando ciclo istruzioni
1 0 1 1 f11 comando operazione aggiunta di 1
1 1 0 0 f12 comando di scorrimento a destra
1 1 0 1 f13 comando di scorrimento a sinistra
1 1 1 0 f14 comando di svuotamento dell'accumulatore
1 1 1 1 f15 comando di arresto

Poiché sono sufficienti 14 stati, i comandi f6 e f7 non vengono usati. Gli stati f4 e f10sono quelli corrispondenti al ciclo istruzione ; gli stati rimanenti corrispondono al ciclo esecutivo.
Poiché vi sono 9 istruzioni , vi sono nove possibili percorsi da f10 a f4; durante il ciclo esecutivo, la sequenza operativa segue una di queste nove vie.
Quando il calcolatore esegue un programma, non fa altro che percorrere ciclicamente queste vie del diagramma di stato (fig-4.4.5) in accordo con le istruzioni programmate.
La scelta dei 14 segnali di comando tra i 16 possibili stati del contatore non è del tutto arbitraria ma è stata fatta cercando di semplificare la logica del circuito.
Infatti gli stati f0, f1, f2, f3, f4, f5 sono relativi a comandi di istruzioni e questa scelta fa si che il Flip-Flop F1 sia uguale a 0 per tutti i comandi di istruzione , semplificando cosi la logica del circuito.
Mediante la tabella 4.4.4 e conoscendo la sequenza di controllo relativa ai cicli-istruzione e cicli.esecuzione si può costrure la figura 4.4.5 detta anche diagramma di stato in cui compaiono gli stati del calcolatoredopo le singole operazioni e le operazioni conseguenti ad ogni singolo stato.
In figura 4.4.5 l'operazione di prendere una istruzione in memoria durante il ciclo-istruzione avviene allo stato f4, mentre le altre tre operzioni relative al ciclo-istruzione avvengono allo stato f10.
La sequenza interna dedl ciclo esecutivodipende dal contenuto dei Flip-Flop R0, R1, R2.
Vi sono sei strade: per l'addizione, la sottrazione, il trasferimento condizionato, il trasferimento incondizionato, il comando di memorizzazione, inoltre vi sono le strade che compaiono quandoR0R1R2 è 101 e indicano le operazioni di left-shift, right-shift, clear accumulator e stop.
L'operazione che costruisce l'indirizzo relativo all'istruzione successiva (detto anche indirizzo di ritorno) avviene negli stati f0, f1, f2, f3 e f5 mentre non è necessaria se l'istruzione appena eseguita è un trasferimento incondizionato.
Uno zero viene inserito nel Flip-Flop G allo stato f5 se C3 è 1.
L'oprazione di incremento di 1 avviene durante lo stato f11.
L'operazione di prendere dalla memoria l'operando avviene durante gli stati f0 e f1 mentre le operazioni di addizione e di sottrazione vengono eseguite agli stati f8 e f9 rispettivamente.
Allo stato f15, il comando di stop inserisce tutti 0 nel registro C e tutti 1 nel registro F.
L'operation counter continua a conteggiare i segnali dell'orologio ma il suo stato rimane f15 a causa dell'operazione 1=>F:
Perciò, sotto il comando di stop il calcolatore non si arresta ma viene sospesa solo la sequenza operativa.<br/ Quando lo switch S' viene messo nello stato off , il Flip-Flop G assume lo stato 0: il calcolatore continua ad eseguire l'istruzione in corsofino a quando l'operation counter, raggiunge lo stato f4.
A questo punto, l'operation counter assume lo stato f15 e rimane in tale stato.
Quando la sequenza è stata sospesa, può essere ripristinata ponendo lo switch S nella posizione ON
Quando questo accade, il Flip-Flop G assume lo stato 1 e l'operation counter assume lo statof4
Poiché il contenuto del registro C era stato cambiato in 000000, il calcolatore comincia dall'istruzione contenuta nella prima posizione di memoria.


4.5-Equazioni logiche.

Durante questa fase vengono derivate le equazioni logiche dei circuiti, partendo dalle espressioni simboliche di figura 4.4.5.
Queste equazioni rappresentano le equazioni di input dei Flip-flop dei registri F,A,C,R,M e del Flip-Flop G.

4.5.1-Operation counter.
Nell'operation counter vi sono quattro Flip-Flop F1,F2,F3,F4: esso deve realizzare la sequenza di figura 4.4.5 ed assumere lo stato 1111 quando G è 0.
Da figura 4.4.5 si ha allora che lo stato del Flip-Flop F1 cambia quando dallo stato f4 (0100) si passa allo stato f10 (1010).
Cambia inoltre quando f10 (1010) diventa f0 (0000), con R0,R1,R2 (000).
In breve lo stato del Flip-Flop F1 cambia quando si presenta una delle sei seguenti condizioni.


Le altre condzioni che detertminano il cambiamento dello stato di F1 possono essere dedotte con considerazioni simili, tenendo sempre presente il diagramma di stato di figura 4.4.5.
Chiamando quindi p l'impulso d'orologio che commuta i Flip-Flop , si hanno le seguenti equazioni di input per F1, F2, F3, F4.






Quando il contatore si trova nello stato f15 ed il Flip-Flop G ha valore 0, viene richiesta l'operazione 1=>F: in tavola 4.5.2 vengono mostrati i valori assunti dai Flip-Flop Fi durante tale operazione.

Le equazioni di input dei Flip-Flop F in tale caso saranno:


Poiché f15 è F1F2F3F4=1111, negFi f15 nella equazione 4.5.3 è sempre 0, e quindi l'equazione (4.5.3) non è necessaria.
Le equazioni 4.5.1 sono le equazioni di input del registro F-
In fig-4.5.4 compare il diagramma logico relativo alle (4.5.1).



4.5.2 Accumulatore
Come mostrato nel diagramma 4.4.5, l'accumulatore interviene durante l'esecuzione delle operazioni relative agli stati:






Durante l'operazione di addizione relativa allo stato f8,Ai e Ri sono gli isimi bits degli addendi.
Ki è il riporto dovuto alla somma fatta sugli (i+1)simi bits.
L'operazione di somma viene mostrata in tabella 4.5.5.

Ai Ri Ki Ki-1 Ai t Qit
0 0 0 0 0 0
0 0 1 0 1 1
0 1 0 0 1 1
0 1 1 1 0 0
1 0 0 0 1 0
1 0 1 1 0 1
1 1 0 1 0 1
1 1 1 1 1 0

Da tale tabella, si ricavano le seguenti equazioni di input:


mentre per il riporto si ha:br/>



Per l'operazione di sottrazione relativa allo stato f9, Ai e Ri sono rispettvamente l'isimo bit del minuendo e dell'isimo bit del sottraendo.
Le ewquazioni di inpute del riportto sono le stesse di (4.5.6) ad eccezione di Ri che viene sostituito da e K8 viene sostituito da 1in modo da sostituire il c ontenuto di Rcon il suo complemento a 2.
Le equazioni di input e del riporto sono quindi:





L'operazione di scorrimento a destra avviene allo stato f12.
Esso fa scorrere il contenuto dell'accumulatore di un bit a destra mentre lo stato di A0 rimane inalterato.
La tabella (4.5.8) rappresenta l'operazione di scorrimento a destra.
Le equazioni di input sono:


Non vi è alcuna equazione per a0t in quanto lo stato del Flip-Flop A0 non deve cambiare.
L'operazione di scorrimento a sinistra avvierne allo stato f13.
Essa fa scorrere il contenuto dell'accumulatore di un bit verso sinistra mentre lo stao di A8viene sostituito da quello di A0.

Le equazioni di input saranno:



L'operazione di azzeramento dell'accumulatore avviene allo stato f14 (tabella 4.5.9):
Le equazioni di input sono:


quindi le equazioni di input dei Flip-Flop che costituiscono l'accumulatore A saranno:


math>a_{0t}=(A_0\oplus K_0)f_8p+(\bar R_0\oplus K_0)f_9p+(A_0\oplus A_1)f_{13}p+a_0f_{14}p</math>
math>a_{8t}=(A_8\oplus K_8)f_8p+(\bar R_8\oplus K_8)f_9p+(A_7\oplus A_8)f_{12}p+(A_0\oplus A_8)f_{13}p+a_8f_{14}p</math>

i=1,...,8


Il diagramma logico dell'isimo stadio dell'accumulatore viene presentato in fig.4.5.10



4.5.3 - Memory address register.


Nel diagramma di stato di fig-4.4.5, il registro C deve permettere le seguenti operazioni:


La tabella della verità relativa alla operazione (Ad[R]=>C è quella posta a fianco.
Le equazioni di input da tale tavola sono:



L'operazione (C)+1=>C avviene allo stato f11: durante questa operazione , il registro C funziona come un contatore binario.
Le equazioni di input saranno quindi:







La terza operazione, quella inerente all'azzeramento del registro C, viene eseguita allo stato
La tavola della Verità corrispondente è uguale a quella di Fig-4.5.9.
Le equazioni di input sono:


In definitiva, le equazioni di input dei Flip-Flop relativi al memory-address register sono:







dove :::
In fig-4.5.11 compare un diagramma logico relativo al memory-address register.<br/ In questa figura è indicat anche l'address decoder , che non è altro che una matrice con 6 coppie di input e 64 output.
Gli output Dj (jsima parola) del decodificatore sono rappresentati come:







4.5.4-Instruction register.<br/ L'instruction register permette la memorizzazione temporanea di una parola presa dall'unità di memoria:
Come è mostrato in fig-4.4.5, sono richieste le esecuzioni delle seguenti operazioni:




La prima operazione, relativa al trasferimento del contenuto del registro C nella parte indirizzo del registro R ha la tabella della verità affiancata.
Le equazioni di input saranno quindi:


La seconda operazione prende una parola dalla memoria il cui indirizzo è dato dal contenuto del registro Ce la conserva nel registro R.
Lindirizzo contenuto viene indicato con la notazione Dj, dove J specifica la jsima parola.
Nella memoria del nostro ipotetico calcolatore vi sono 576 bits conservati in 64 parole; essi vengono espressi con il simbolo Mjiil quale indica il contenuto del isimo bit relativo allajsima parola.
L'operazione di trasferimento del bit Mji dalla memoria all'isimo bit del registro Rè la stesssa di quella di tabella 4.5.13, dove Ci-3 viene sostituito da Mji
Le equazioni di input sono:


Le equazioni precedenti non sono complete in quanto contemplano solo il trasferimento del contenuto del bit Mji e non considerano la selezione della voce di indirizzo DjSe il bit isimo della jsima parola in m3emoria viene selezionato mediante il comando Dj (il quale può esseree uno qualsiasi dei 64 comandi di indirizzo) Mji e vengono sostituiti dalle equazioni seguenti:



Per cui, le equazioni di input diventano:


In definitiva, le equazioni di input del registro R saranno:



dove Dj è dato dall'equazione (4.5.12).
In fig-4.5.14, cvompare il diagramma logico dello isimo stadio del registro R.



4.5.5-Unità di memoria.
La memoria nel nostro ipotetico calcolatore è costituita da un insieme di 576 Flip-Flop: essa deve poter eseguire le due operazioni seguenti:


La prima operazione memorizza il contenuto dell'accumulatore nella memoria con l'indirizzo selezionato da Dj allo stato f3:


Le equazioni di input saranno allora:


La seconda operazione consiste nell'inserire delle parole in memoria mediante gli interruttori Q
Se Qji indica l'interruttore connesso al bit di memoria Mji, l'operazione ha la tabella di verità affiancata.
La forma finale delle equazioni di input della unità di memoria è:


In fig-4.5.15 compare un diagramma logico abbreviato del registro di memoria.



4.5.6-Start-stop Flip-Flop.
La partenza e l'arresto del calcolatore vengono controllati mediante il Flip-Flop G, il quale viene a sua volta attivato dall'interruttore S mediante operazione manuale.
Le due operazioni richieste sono:



La prima operazione cambia il Flip-Flop G nello stato 0 quando compare lo stato f_5 e C_3 è 1; le equazioni di input sono quindi:


La seconda operazione mette in ON od in OFF l'interruttore S per permettere l'avvio o l'arresto della macchina.
L'equazione di input è:




4.6-Un calcolatore completo

Nei paragrafi precedenti abbiamo stabilito le equazioni di input di tutti i registri del nostro ipotetico calcolatore.
la configurazione del calcolatore dato in fig-4.3.1 può essere ora completata dando le equazioni simboliche relative ai singoli registri.(fig-4.6.1)<br&> Questo diagramma può essere reso più dettagliato usando i diagrammi logici stabiliti nei precedenti paragrafi.
La procedura operativa del nostro calcolatore sarà la seguente:
-1 Accensione del calcolatore. Se il Flip-Flop di avvio-arresto si trova nello stato 1 durante questo periodo, il calcolatore funzioneera in maniera irregolare.
-2 Si mette lo switch S nella posizione off.
Questo implica che lo start-stop Flip-Flop sia nello stato 0, lo operation counter in 1111 e l'indirizzo contenuto nel memory address register uguale a 000000.
Si inserisce il programma in memoria mediante gli interruttori Q.
-3 Si mette lo switch S nella posizione ON.
Il Flip-Flop Gassume lo stati 1 e la macchina comincia ad esguire il programma.
La prima istruzione si trova nella memoria di indirizzo 000000.
-4 Il programma deve terminare con una istruzione di stop: questa ultima inserisce 0 in G, 1111 in F e 000000 in C.
Un nuovo programma può essere inserito nella memoria ed il calcolatore può iniziare il calcolo rimettendo lo switch nella posizione ON.
-5 Si leggono i risultati ottenuti mediante dispositivi luminosi connessi ai Flip-Flop di memoria (non mostrati nei diagrammi precedenti).