Elaborazione dell’informazione

L’informazione, negli elaboratori elettronici, è ‘descritta’ ed elaborata sotto forma digitale, cioè, i segnali elettrici che la rappresentano assumono solo un numero discreto di valori nominali normalmente pari a due.
A seconda delle tecnologie e degli standard adottati tali valori possono essere per esempio 0 e 5 volt, +5 e –5 volt, +15 e –15 volt (volt  unità di misura della tensione elettrica).  
Possiamo codificare tali valori con due simboli o stati logici 0, I e dire quindi (secondo esempio) che una linea elettrica che si trovi a +5 volt è allo stato logico I e a –5 volt è allo stato logico 0. L’architettura e la circuiteria di un elaboratore elettronico sono tali da poter eseguire funzioni di trasferimento, memorizzazione e combinazione degli stati logici.

Abbiamo visto, in precedenza, che qualunque tipo d’informazione è rappresentabile in forma numerica (immagini, testi, suoni) e che esiste la codifica numerica binaria il cui alfabeto di cifre è costituito esattamente da due simboli. Risulta quindi chiaro come tale codifica sia in stretto legame con la rappresentazione dell’informazione su un elaboratore; molto semplicemente si associare alla cifra 0, per esempio, lo stato logico 0 e alla cifra 1 lo stato logico I.

Nei paragrafi che seguono punteremo l’attenzione sulle possibilità di combinazione degli stati logici.

Ipotesi di sommatore
Indubbiamente un’operazione aritmetica, come potrebbe essere la somma, combina le informazioni relative ai due operandi per ottenerne una nuova (il risultato).
Il metodo operativo per eseguirla è sommare cifre omologhe (dal punto di vista del peso nella rappresentazione posizionale) a partire dalle meno significative, tenendo conto degli eventuali riporti sulle cifre successive. Risulta chiaro allora, da un punto di vista puramente logico, che un circuito, il cui scopo sia quello di eseguire la somma tra due operandi ad n cifre, debba essere costituito da n blocchi interconnessi, ciascuno dei quali in grado di sommare due cifre e determinarne il relativo riporto (input per il blocco successivo). 

Rappresentati i numeri in binario e considerando l’equivalenza tra cifra binaria e stato logico (0  0  e  1  I), il comportamento di ciascun blocco può essere rappresentato dalla seguente tabella redatta seguendo le regole della somma in codifica binaria.
A	B	C	C’	R	
0	0	0	0	0	
0	0	I	0	I	
0	I	0	0	I	
0	I	I	I	0	
I	0	0	0	I	
I	0	I	I	0	
I	I	0	I	0	
I	I	I	I	I	

La tabella mette in relazione gli ingressi A,B,C con le uscite C’,R. Questa associazione univoca è espressione del concetto di funzione. In particolare abbiamo due funzioni; la R che rappresenta la somma tra due cifre binarie e la C’ che ne restituisce il resto. Queste funzioni sono dette binarie per via del fatto che i valori assumibili (codominio) sono solo due {0,I}.

DEFINIZIONE: Una funzione binaria di variabili binarie si dice funzione di commutazione. Un circuito o rete combinatoria è un sottosistema digitale che realizza una funzione di commutazione.

Il nostro obiettivo è sviluppare una metodologia per la progettazione di una rete combinatoria che realizzi una funzione di commutazione.

Funzione di commutazione ad una variabile:
Cerchiamo di identificare tutte le funzioni di commutazione che hanno in ingresso una sola variabile binaria x1.
Possiamo realizzare una tabella nella quale rappresentiamo a sinistra tutte le possibili configurazioni d’ingresso e a destra una serie di colonne, tante quante possono essere le funzioni distinte. Le configurazioni d’ingresso saranno ovviamente in numero di k = 2n dove ‘n’ rappresenta il numero delle variabili binarie in ingresso. Tutte le possibili funzioni di commutazione (colonne a destra) associabili agli ingressi saranno in numero di 2k.
Vediamo la tabella per le funzioni ad una variabile:

x1	f1	f2	f3	f4	
0	0	0	I	I	
I	0	I	0	I	

Le funzioni f1 ed f4 non sono di alcun interesse perché risultano indifferenti alle variazioni della variabile in ingresso (funzioni degeneri). La funzione f2 non ‘elabora’ in alcun modo l’informazione e si limita a replicare in uscita le segnalazioni presenti in ingresso. Nell’ ambito della realizzazione circuitale può tornare utile avere componentistica che realizzi tale funzione; il suo impiego può avere l’obiettivo di introdurre particolari ritardi o riamplificare le segnalazioni che hanno perso potenza.
La funzione f3 è invece particolarmente importante poiché esegue l’inversione dello stato logico presente in ingresso. E’ detta funzione complemento ed è indicata con il nome di NOT.

Funzione di commutazione a due variabili:
Cerchiamo di identificare tutte le funzioni di commutazione che hanno in ingresso due sole variabili binarie x1,x2. In modo analogo a quanto fatto per quelle ad una variabile rappresentiamo tutte le possibili funzioni attraverso una tabella.

x1	x2	f1	f2	f3	f4	f5	f6	f7	f8	f9	F10	f11	f12	f13	f14	f15	f16	
0	0	0	0	0	0	0	0	0	0	I	I	I	I	I	I	I	I	
0	I	0	0	0	0	I	I	I	I	0	0	0	0	I	I	I	I	
I	0	0	0	I	I	0	0	I	I	0	0	I	I	0	0	I	I	
I	I	0	I	0	I	0	I	0	I	0	I	0	I	0	I	0	I	

Fra le varie funzioni identificate, alcune risultano di particolare interesse. Le elenchiamo qui di seguito.
f2  AND	Risponde con I SE E SOLO SE gli ingressi sono tutti allo stato logico I
f7  XOR	Risponde con I SE E SOLO SE gli ingressi sono a stati logici differenti.
f8  OR	Risponde con I se almeno uno degli ingressi è allo stato logico I

Le funzioni NOT, AND, OR possono essere considerate come operatori sulle variabili binarie e, a livello circuitale, come porte logiche dotate di ingressi e relative uscite.
Vediamo la simbologia adottata:

FUNZIONE	SIMBOLO OPERATORE	SIMBOLO PORTA LOGICA	
NOT	“¯” o anche “” (ES. x1 op. x1)		
AND	“·” (ES.x1 · x2)		
OR	“+”(ES.x1 + x2)		

In una porta logica riconosciamo i terminali d’ingresso ai quali vengono applicati gli stati logici da combinare e un terminale d’uscita che rappresenta il valore logico assunto dalla funzione di commutazione ad essa associato.

Diamo allora una definizione costruttiva (operativo – induttiva) delle reti combinatorie:
DEF. Rete combinatoria:
1.	I terminali d’ingresso sono reti (reti elementari)
2.	Se N1 e N2 sono reti (scatole nere) lo sono anche le seguenti:

La combinazione di variabili binarie attraverso gli operatori appena visti dà origine alle espressioni (dette anche espressioni booleane).

Diamo allora una definizione di espressione:
DEF. Espressione booleana:
1.	Le variabili e le costanti (0,I) sono espressioni 
2.	Se E1 e E2 sono espressioni lo sono anche E1, E2, E1 + E2, E1 · E2

Nelle espressioni si fa uso delle parentesi per determinare la priorità dell’applicazione degli operatori. E’ comunque stabilita una priorità secondo la quale l’ordine di applicazione è dato dalla sequenza NOT AND OR.

Esempio: 
E= x1·x2 + x2 + x1·x4
Il senso di questo esempio è: “eseguire l’OR tra x1·x2, x2, x1·x4”. Quindi se volessimo mettere in evidenza la priorità degli operatori potremmo scrivere:
E= (x1·x2) + (x2) + (x1·x4)

Se avessimo voluto intendere l’applicazione dell’operatore NOT (complemento) non alla sola x2, ma a tutto ciò che lo segue avremmo dovuto scrivere:
E= (x1·x2) + (x2 + x1·x4)

Possiamo dire quindi che un’espressione descrive una rete combinatoria e che una rete combinatoria realizza un’espressione.

Regola d’induzione perfetta: Due espressioni E1 ed E2, definite sullo stesso insieme di variabili, sono equivalenti (E1=E2) se, per tutte le possibili assegnazioni alle variabili, i valori di E1 ed E2 coincidono.

Algebra di commutazione
La progettazione delle reti si basa su un formalismo chiamato algebra delle commutazioni. La definizione del comportamento degli operatori e le loro proprietà sono definiti in modo assiomatico.

Assioma principale: Ciascuna espressione assume il valore 0 o I per ogni assegnazione di valori (0,I) alle sue variabili.

COMPLEMENTO:		0 = I			I = 0
Proprietà di Involuzione  (0) = I		(I) = 0	 cioè	(x) = x  (x variabile)

AND (o prodotto logico)	OR (o somma logica)	Proprietà
x1 · x2 = x2 · x1	x1 + x2 = x2 + x1	Commutatività
x · x = x	x + x = x	Idempotenza
x · I = x	x + 0 = x	Elementi neutri
x · 0 = 0	x + I = I	
x · x = 0	x + x = 1	Complementarietà
x · (y + z) = x · y + x · z	x + (y · z) = (x + y) · (x + z)	Distributività
x · (x + y) = x	x + (x · y) = x	Assorbimento
(x · y) · z = x · (y · z)	(x + y) + z = x + (y + z)	Associatività
(x · y) = x + y	(x + y) = x · y	De Morgan

x + x · z = x + z		Identità di consenso
x · y + y · z + z · x = x · y + z · x

Come si può notare, nella tabella di equazioni comprese tra le due righe orizzontali, le due colonne hanno in comune il fatto che un’equazione a destra si ottiene da quella sulla stessa riga a sinistra cambiando l’operatore “·” con “+” e lo stato logico 0 con I e viceversa.
Tale osservazione si esprime per mezzo del seguente principio.

Principio di dualità : Da un’espressione valida se ne ottiene un’altra valida scambiando gli operatori e le costanti dualmente.

Espressioni booleane
Vediamo ora alcune forme nelle quali si scrivono le espressioni per ottenere, di solito, una maggior chiarezza espressiva.

Forma NORMALE 	SOP (Sum Of Product)
	POS (Product Of Sum)

Forma CANONICA	SOP o Disgiuntiva 
	POS o Congiuntiva

Normale SOP
Data un’espressione booleana in forma generica, descriviamo i passi algoritmici per esprimerla in forma normale SOP, cioè nella somma di prodotti tra letterali. Definiamo letterale una variabile complementata oppure no (es. di letterali x1, x1, x5).

1.	Portare la complementazione direttamente sulle variabili (uso delle leggi di De Morgan)
2.	Applicare la proprietà distributiva  (AND rispetto all’OR)
3.	Eliminare i termini ridondanti (idempotenza)

ES. E=[ x1 + x2 · ( x3 + x4 · x1)] · x3 + (x2 · x4)

Passo 1
E=[ x1 + x2 · (x3 · (x4 + x1))] · x3 + x2 + x4

Passo 2
E=[ x1 + x2 · x3 · x4 + x2 · x3 · x1 ] · x3 + x2 + x4
E=  x1 · x3 + x2 · x3 · x4 · x3 + x2 · x3 · x1 · x3 + x2 + x4

Passo 3
E=  x1 · x3 + x2 · x3 · x4 · x3 + x2 · x3 · x1 · x3 + x2 + x4
questi due termini sono identicamente nulli per la regola di complementarietà dell’operatore AND riferito al prodotto x3 · x3.
Quindi E= x1 · x3 + x2 + x4
Normale POS
Data un’espressione booleana in forma generica descriviamo i passi algoritmici per esprimerla in forma normale POS.

1.	Portare la complementazione direttamente sulle variabili (uso delle leggi di De Morgan)
2.	Applicare la proprietà distributiva  (OR rispetto all’AND)
3.	Eliminare i termini ridondanti (idempotenza)

L’applicazione è analoga a quanto fatto per la forma SOP. Attenzione al fatto che questa volta occorre applicare, al passo 2, la distributività della somma logica rispetto al prodotto logico.
L’espressione dell’esempio precedente diviene in forma POS:
E= (x1 + x2 + x4) · (x2 + x3 + x4)

Canonica disgiuntiva
La particolarità della forma canonica, disgiuntiva rispetto a quella normale SOP, consiste nel fatto che i termini prodotto, per un’espressione ad n variabili, sono costituiti ciascuno esattamente dalle n variabili, ognuna presa complementata o meno.
Consideriamo un esempio:

Espressione booleana di tre variabili in forma normale SOP.
E= x1 · x3 + x2 + x3

Espressione equivalente alla precedente ma espressa in forma canonica disgiuntiva
E= x1 · x2 · x3 + x1 · x2 · x3 + x1 · x2 · x3 + x1 · x2 · x3 + x1 · x2 · x3 + x1 · x2 · x3 + + x1 · x2 · x3

Regola : Normale SOP  Canonica disgiuntiva
Considerate ogni termine prodotto nella forma normale SOP e per ogni variabile xi non presente in quel termine, moltiplicatelo per ( xi + xi ). Applicate quindi la regola di distributività del prodotto rispetto alla somma logica.

ES. E= x1 + x2 · x3   E= x1 · ( x2 + x2 ) · ( x3 + x3 ) + x2 · x3 · ( x1 + x1 )
E= x1 · x2 · x3 + x1 · x2 · x3 + x1 · x2 · x3 + x1 · x2 · x3 + x1 · x2 · x3 + x1 · x2 · x3
Canonica congiuntiva
Considerando una funzione di commutazione ad n variabili, l’espressione in forma canonica congiuntiva che la rappresenta, è costituita dal prodotto di termini ognuno dei quali è la somma logica di tutte le n variabili, ciascuna presa complementata o meno.
Prendiamo come esempio l’espressione vista in precedenza:
E= x1 · x3 + x2 + x3
E’ in forma normale SOP. La sua forma normale POS si ottiene facilmente applicando passi algoritmici 1. 3.  per la trasformazione di un’espressione in forma generica a forma POS. In particolare il passo 1. non necessita di essere applicato perché la complementazione è già presente sulle singole variabili. Il passo 2. (distributività dell’OR rispetto all’AND) si applica in relazione al primo OR da sinistra sull’AND tra x1 e x3.

E= (x1 · x3) + (x2 + x3) = (x2 + x3 +x1) · (x2 + x3 + x3) = x2 + x3 +x1
							 I
L’espressione ora si trova in forma normale POS ma, per sola coincidenza, anche in forma canonica poiché il termine (x2 + x3 +x1) è OR logico tra tutte le variabili dell’espressione!.

Regola : Normale POS  Canonica congiuntiva
Per ottenere la forma canonica congiuntiva di un’espressione generica, se ne determina prima la forma normale POS. Successivamente per ogni termine della produttoria (POS  prodotto di somme) al quale, nella somma, manchi la variabile xi, si somma il termine 
(xi · xi) (che risulta essere identicamente nullo e quindi non modifica l’espressione). Si applica poi la distributività della somma rispetto al prodotto logico tra questi due termini.

ES. Data l’espressione a tre variabili (x1,x2,x3) E= x2 + x3 determinarne la forma canonica congiuntiva.
Si nota subito che E è già in forma normale POS nella quale l’unico termine della produttoria logica è (x2 + x3). Per ottenerla in forma canonica congiuntiva dobbiamo sommargli il termine (x1 · x1) in quanto x1 è mancante.
E= (x2 + x3) + (x1 · x1)
Applichiamo poi la distributività dell’OR rispetto all’AND tra x1 e x1.
E= (x2 + x3 + x1) · (x2 + x3 + x1)
che è la forma canonica congiuntiva cercata.
Le forme canoniche sono uniche, cioè data una funzione di commutazione esistono una sola espressione canonica congiuntiva ed una sola canonica disgiuntiva ad essa associate.

Ora che abbiamo visto le forme canoniche delle espressioni definiamo due ‘oggetti’ algebrici d’interesse per quanto riguarda la sintesi di una funzione di commutazione.

DEF. mintermine  Data una funzione di commutazione ad n variabili, un mintermine ad essa associato è il prodotto logico di tutte le n variabili prendendo ciascuna in complemento o meno.

I mintermini associati ad una funzione di n variabili sono esattamente 2n. Infatti si possono mettere in coincidenza i concetti di complementazione o meno di una variabile corrispondentemente con i valori 0,1 di una parola binaria di n bit.

E’ chiaro quindi che la forma canonica disgiuntiva è esprimibile anche come somma logica tra mintermini!

DEF. Maxtermine  Data una funzione di commutazione ad n variabili, un maxtermine ad essa associato è la somma logica di tutte le n variabili prendendo ciascuna in complemento o meno.

Analogamente a quanto visto per i mintermini, anche i maxtermini sono 2n per una funzione di commutazione a n variabili.

E’ chiaro quindi che la forma canonica congiuntiva è esprimibile anche come prodotto logico tra Maxtermini!

Introduciamo ora una notazione convenzionale per i mintermini.
Consideriamo per esempio il mintermine x1 · x2 · x3 · x4; associamo a questo mintermine una quadrupla binaria ordinata (b1b2b3b4), dove bi corrisponde ad xi o a xi e bi=1 se xi non è complementata ed è 0 altrimenti. Nel nostro esempio a x1 · x2 · x3 · x4 associamo 0110; questa stringa è l’equivalente binario di 6, cosicché denoteremo x1 · x2 · x3 · x4 con m6.
ES.
E= x1 · x2 · x3 + x1 · x2 · x3 + x1 · x2 · x3 + x1 · x2 · x3 + x1 · x2 · x3
si può scrivere anche come:
E= m7 + m5 + m1 + m3 + m2
Introduciamo ora una notazione convenzionale per i Maxtermini.
Consideriamo per esempio il mintermine x1 + x2 + x3 + x4; associamo a questo Maxtermine una quadrupla binaria ordinata (b1b2b3b4), dove bi corrisponde ad xi o a xi e bi=1 se xi è complementata ed è 0 altrimenti. Nel nostro esempio a x1 + x2 + x3 + x4 associamo 1001; questa stringa è l’equivalente binario di 7, cosicché denoteremo x1 + x2 + x3 + x4 con M7.

Facciamo alcune considerazioni sui mintermini e i Maxtermini.
Se analizziamo il comportamento di un fissato mintermine per ogni assegnazione delle sue variabili, si nota che, trattandosi di un prodotto logico, assumerà il valor logico I solo quando i suoi letterali sono allo stato logico I; cioè solo quando alle variabili complementate è assegnato lo stato 0 e a quelle non complementate lo stato I. Quindi la funzione di commutazione associata ad un mintermine risponde sempre con il valore 0 tranne che per un’unica configurazione degli ingressi.
ES. Consideriamo il mintermine x1 · x2 · x3 · x4. La funzione F che esso esprime, è tabulabile associando ad ogni quadrupla di valori logici da assegnare alle variabili, il valore dell’espressione (tabella della verità).
	x1	x2	x3	x4	F	
m0	0	0	0	0	0	
m1	0	0	0	I	0	
m2	0	0	I	0	0	
m3	0	0	I	I	0	
m4	0	I	0	0	0	
m5	0	I	0	I	0	
m6	0	I	I	0	I	
m7	0	I	I	I	0	
m8	I	0	0	0	0	
m9	I	0	0	I	0	
m10	I	0	I	0	0	
m11	I	0	I	I	0	
m12	I	I	0	0	0	
m13	I	I	0	I	0	
m14	I	I	I	0	0	
m15	I	I	I	I	0	

Se ragioniamo ora sulla tabella di verità di una funzione f generica, possiamo pensare che f sia la somma logica (OR) di tante funzioni fi quanti sono gli stati I nella risposta di f; ciascuna fi è la funzione espressa dal mintermine in corrispondenza dell’i-esimo I.

ES. 
f = x1 · x2 · x3 + x1 · x2 · x3 + x1 · x2 · x3 + x1 · x2 · x3 + x1 · x2 · x3
o equivalentemente
f = m7 + m5 + m1 + m3 + m2 = f1 + f2 + f3 + f4 + f5

	x1	x2	x3	f1	f2	f3	f4	f5	f	
m0	0	0	0	0	0	0	0	0	0	
m1	0	0	0	I	0	0	0	0	I	
m2	0	0	I	0	I	0	0	0	I	
m3	0	0	I	0	0	I	0	0	I	
m4	0	I	0	0	0	0	0	0	0	
m5	0	I	0	0	0	0	I	0	I	
m6	0	I	I	0	0	0	0	0	0	
m7	0	I	I	0	0	0	0	I	I	

Consideriamo ora un generico Maxtermine. Osservandone il valore assunto per ogni combinazione degli stati logici assegnati alle sue variabili si nota che lo stato logico 0 si ottiene solo nel caso in cui, alle variabili complementate, si assegni lo stato I e a quelle non complementate lo stato 0. In tutte le altre combinazioni, la funzione rappresentata dal maxtermine, risponde con lo stato logico I.

ES.
F = x1 + x2 = M2
	x1	x2	F	
M0	0	0	I	
M1	I	0	I	
M2	0	I	0	
M3	I	I	I	
Intanto notiamo che Mj = mj e ciò è facilmente dimostrabile attraverso l’impiego delle leggi di De Morgan e della proprietà d’involuzione del complemento.

Se ragioniamo ora sulla tabella di verità di una funzione f generica, possiamo pensare che f sia il prodotto logico (AND) di tante funzioni fi quanti sono gli stati 0 nella risposta di f; ciascuna fi è la funzione espressa dal Maxtermine in corrispondenza dell’i-esimo 0.

	x1	x2	x3	x4	f1	f2	f3	f4	f5	f	
M0	0	0	0	0	I	I	I	I	I	I	
M1	0	0	0	I	I	I	I	I	I	I	
M2	0	0	I	0	I	I	I	I	I	I	
M3	0	0	I	I	I	I	I	I	I	I	
M4	0	I	0	0	0	I	I	I	I	0	
M5	0	I	0	I	I	I	I	I	I	I	
M6	0	I	I	0	I	0	I	I	I	0	
M7	0	I	I	I	I	I	I	I	I	I	
M8	I	0	0	0	I	I	0	I	I	0	
M9	I	0	0	I	I	I	I	0	I	0	
M10	I	0	I	0	I	I	I	I	I	I	
M11	I	0	I	I	I	I	I	I	I	I	
M12	I	I	0	0	I	I	I	I	I	I	
M13	I	I	0	I	I	I	I	I	I	I	
M14	I	I	I	0	I	I	I	I	I	I	
M15	I	I	I	I	I	I	I	I	0	0	

f = f1 · f2 · f3 · f4 · f5 = M4 · M6 · M8 · M9 · M15   forma canonica congiuntiva

Normalmente, a meno che non sia richiesta una forma specifica, si può ottenere più vantaggiosamente l’espressione della funzione in forma Maxterminale o minterminale secondo che, rispettivamente, nella risposta della funzione vi siano più I o più 0.

Inoltre, poichè Mj = mj, si può facilmente ottenere la forma Maxterminale da quella minterminale. Infatti si può pensare di estrarre dalla tabella di verità della funzione f la forma minterminale di f e complementando quest’ultima si ottiene la forma Maxterminale della f. Questo perchè una forma minterminale di f complementata dà origine ad una forma Maxterminale (legge di De Morgan) che esprime ovviamente la f. Quindi per l’assioma di involuzione, se parto con la forma minterminale di f e la complemento, ottengo la forma Maxterminale di f.

Per chiarire meglio il concetto facciamo un esempio.
Supponiamo di avere la funzione:
f = x1 + x2 · x3
Tabella di verità
	x1	x2	x3	f	f	
0	0	0	0	0	i	
1	0	0	I	0	i	
2	0	I	0	I	0	
3	0	I	I	0	i	
4	I	0	0	I	0	
5	I	0	I	I	0	
6	I	I	0	I	0	
7	I	I	I	I	0	

Forma canonica disgiuntiva :
 f = m2 + m4 + m5 + m6 + m7 = ( x1 · x2 · x3) + ( x1 · x2 · x3) + ( x1 · x2 · x3) + ( x1 · x2 · x3) + ( x1 · x2 · x3)
Considero ora l’espressione canonica disgiuntiva della f:
f = m0 + m1 + m3 
 Se ora complementiamo entrambi i membri dell’equazione:
( f ) = ( m0 + m1 + m3 ) = M0 · M1 · M3 = (x1 + x2 + x3) · (x1 + x2 + x3) · (x1 + x2 + x3)
otteniamo la forma canonica congiuntiva della f.