Macchine combinatorie

1. Generalità

La macchina può essere rappresentata dal banale modello di figura

Modello di macchina combinatoria

Il modello presentato è del tutto generale e nessuna ipotesi viene fatta a priori sulla natura delle variabili di ingresso e di uscita: poiché trattasi di un sistema finito, l'applicazione ω può in particolare essere espressa mediante una tabella di corrispondenza fra gli elementi di I e quelli di U.

Se in particolare I e U sono insiemi di informazioni codificate in binario, allora l'applicazione ω si trasforma in una funzione booleana generalizzata.

Spesso molte proprietà del sistema si ricavano indipendentemente dal codice adoperato. Per tale motivo spesso le macchine combinatorie possono essere studiate indipendentemente dal fatto che esse siano binarie e le reti combinatorie sono un particolare modo di costruire le macchine combinatorie.

Reti combinatorie

In generale si ha che

Lo schema di principio di una macchina combinatoria è dunque realizzabile con lo schema di una macchina binaria.

Schema di rete combinatoria

Avendo comunque fissato una codifica degli stati, l'applicazione diventa

Y = F(X)

che esprime sinteticamente le funzioni booleane:

La corrispondenza biunivoca esistente fra forma algebrica di una funzione booleana e rete di commutazione fa sì che qualsiasi eguaglianza fra espressioni booleane si traduca in equivalenza logica fra reti differenti atte e realizzare la medesima funzione.

In fase di analisi, l'intervento dell'algebra di Boole si estrinseca con l'associare ad una rete le corrispondenti espressioni booleane

In fase di sintesi, si può impiegare tutto quanto esposto per trarre, dalla definizione del problema combinatorio, una forma algebrica della funzione che lo implementi.

Reti unilaterali. Porte elementari

Sono, ad esempio, in logica positiva i circuiti operanti con le seguenti convenzioni:

e sono viceversa in logica negativa i circuiti operanti con le seguenti assegnazioni:

Sotto il profilo logico si preferisce lasciare indeterminati i livelli di tensione alto e basso ed indicarli rispettivamente con E_H (High = alto) e E_L (Low = basso). In logica positiva si ha:

E_H = E₁        E_L = E₀

mentre in logica negativa è

E_H = E₀        E_L = E₁

I circuiti che realizzano le funzioni fondamentali dell'algebra si dicono anche porte. Ad esempio, se il circuito opera secondo la prima colonna di figura 3.1, esso realizza in logica positiva la funzione AND, y = x₁x₂ ed in logica negativa la OR, y = x₁+x₂.

Relazioni fra circuiti in logica positiva ed in logica negativa.

Si ha infatti in generale, per la legge di dualità:

Schemi delle porte elementari: a) AND; b) OR; c) NOT; d) elemento neutro (f= x); e) NAND; f) NOR; g) XOR; h) EQ (detto anche XNOR)

Porte con ingressi negati

A titolo di esempio, si riportano gli schemi di alcuni semplici circuiti con l'impiego di porte di vario tipo.

Esempi di reti combinatorie: a) ; b) ; c) come a. in logica NAND; d) come b. in logica NOR

Struttura delle reti unilaterali

a) Reti AND-OR a due livelli,

b) Reti OR-AND a due livelli,

c) Reti NAND

d) Reti NOR,

Complementazione con porte NAND e NOR.

f) Reti XOR

XOR realizzata con porte NAND

g) Reti miste,

h) Reti con AND e/o OR di connessione

OR e AND di connessione: a,c) ; b,d)

Struttura delle reti bilaterali

     

Reti bilaterali: a) contatto; b) variabile di posizionamento del contatto; c) rete con circuiti di eccitazione; d) rete con ingressi su 'punti'

f_AB = f(x₁, x₂, ,x_n)

a)         Struttura serie-parallelo:

         

Connessioni serie-parallelo: a) a 3 livelli; b) a 2 livelli.

b)     Struttura a ponte:

a) rete serie-parallelo; b) rete modificata; c)rete a ponte.

Esistono alcuni metodi per trattare sistematicamente le reti a ponte, che in questa sede si omettono per brevità.

c Struttura in cascata

                   

Reti bilaterali in cascata: a) schema di principio; b) esempio

d) Schema unilaterale,

Schema unilaterale di reti bilaterali:

a,c) b,d)

Reti con strutture speciali

Reti con elementi a soglia

Detto k il primo numero intero maggiore o uguale a P, la funzione di cui sopra risulta uguale ad 1 se e solo se k o più variabili delle n sono uguali ad 1. Ad esempio, la funzione:

f = x₁x₂ + x₁x₃ + x₂x₃

è una funzione a soglia del tipo '2 su 3' per la quale P = 2, n = 3 (si adopera talora il simbolo Σ_2,3): essa è infatti alta se due o più variabili fra le tre sono alte e può essere indicata con il simbolo di figura

Elemento a soglia

Reti universali

Si dicono universali le reti atte a realizzare una qualsiasi funzione di n variabili con una medesima struttura fisica.

Da un punto di vista concettuale, una rete universale deriva della considerazione che una qualsiasi funzione è esprimibile nella forma normale:

ed è dunque sufficiente realizzare una rete che la implementi

Rete universale

Le α_i vengono dette 'bit di specificazione'; infatti, una volta fissata la configurazione delle α_i, assegnando singolarmente i valori 0 e 1, la rete implementa la corrispondente funzione delle n variabili x_i.

Progetto logico di reti combinatorie

Definizione della macchina

Codifica degli ingressi e delle uscite

Costruzione delle funzioni booleane

Esempio 1

Una rete combinatoria debba elaborare i bit x₁, x₂, x₃ fornendo un segnale alto y₁ se è alto x₁ oppure, simultaneamente, x₂ e x₃ e un segnale y₂ alto quando, essendo basso x₁, siano alti x₂ oppure x₃. Trasformando direttamente in termini di logica l'enunciato del problema, si ha:

y₁ = x₁ + x₂ · x₃;      y₂ = (x₂ + x₃)

Esempio 2

Una rete combinatoria abbia in ingresso due segnali, x e y, rappresentanti ciascuno una cifra binaria e debba eseguire l'addizione delle due cifre, nel senso di fornire in uscita la cifra s somma di x e y e la cifra di riporto per la coppia di cifre di peso superiore. Le tabelle di verità derivano direttamente dalle tabelle di addizione in aritmetica binaria

Tabella di verità per semiaddizionatore binario

Da queste si ottiene

s = y + x = x y

r = xy

Scelta della forma algebrica e minimizzazione

Trasformazione della forma algebrica in rete

Problemi di carico

A causa dei problemi di carico, per cui una porta può pilotare un numero massimo di porte del livello successivo (fan-out) è talora necessario inserire nella rete elementi elettronicamente attivi in funzione di amplificatori di potenza; tali elementi possono essere anche logicamente attivi (e in tal caso si tratta di invertitori o di porte NAND con funzioni di invertitori), oppure possono essere logicamente 'neutri' ed hanno allora puramente funzione elettronica.

Se, ad esempio, la funzione f = abc deve pilotare un numero eccessivo di porte, si possono inserire altrettanti elementi neutri, come in fig. 7 .4a), oppure altrettanti invertitori (fig. 7.4b), alterando ovviamente la funzione nella sua negata, f=a|b|c.

Fig.7.4 - Aggiunta di amplificatori (a) o di invertitori (b)

per risolvere problemi di carico

Riduzione ed estensione degli ingressi di una porta

Fig.7.5 - Riduzione del numero degli ingressi in una porta

Logica ROM

Una macchina combinatoria binaria

U = f(I)                                

si può semplicemente realizzare con l'impiego di una memoria binaria a sola lettura il cui memory-address contenga i valori di ingresso I ed il memory-buffer quelli di uscita U.

La memoria realizza infatti la funzione

: U = M(I)