Appunti Calcolatori elettronici I

Calcolatori elettronici

Algebra di Boole

Introduzione

L’algebra di Boole è uno strumento matematico necessario per la progettazione e l’ottimizzazione dei circuiti (analisi e sintesi di reti di commutazione). Essa consente di descrivere algebricamente un circuito e stabilisce con esso una relazione biunivoca (funzione booleana <-> circuito).

Algebra astratta

Un’algebra astratta è un’entità costituita da:

• Un insieme K (sostegno);
• Due leggi binarie di composizione interna “+” e “*” (operazioni generiche);

In altre parole, un’algebra astratta è definita da una terna <K, +, *>.

L’algebra di Boole è un’algebra astratta che gode di ulteriori proprietà.

Definizione rigorosa di algebra di Boole

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

1. a + b = b + a; a*b = b*a; proprietà commutativa.
2. (a + b) + c = a + (b + c); (a*b)*c = a*(b*c); proprietà associativa.
3. a + a = a; a*a = a; idempotenza o potenza identica.
4. a + (a*b) = a; a*(a + b) = a; assorbimento.

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

5. a*(b + c) = a*b + a*c; a+(b*c) = (a + b)*(a + c); proprietà distributiva.

Un reticolo distributivo si dice dotato di minimo e massimo assoluti se in K sono presenti due elementi, 0 e 1, che verificano la seguente proprietà:

6. a*0 = 0; a + 1 = 1; proprietà del minimo e massimo.

Un reticolo distributivo si dice complementato se per ogni elemento di K esiste ed è unico un elemento chiamato complemento di a per il quale vale la seguente proprietà:

7. a*ā = 0; a + ā = 1; proprietà del complemento.

Un’algebra di Boole è un reticolo distributivo, dotato di minimo e massimo assoluti e complementato. Può essere identificata dalla sestupla <K, +, *, -, 0, 1>.

Da qualsiasi identità booleana se ne può trarre un’altra servendosi della legge di dualità, ovvero sostituendo ad ogni operatore e agli elementi 0 e 1 il rispettivo duale. Quindi le 14 relazioni che sono state precedentemente elencate in realtà sono 7 più altre 7 ricavate per dualità.

Variabili e funzioni booleane

• I valori booleani sono elementi del sostegno K dell’algebra.
• Le variabili che possono assumere valori booleani sono dette variabili booleane.
• Le funzioni definite in K sono chiamate funzioni booleane.
• Un insieme F di funzioni si dice funzionalmente completo se qualsiasi funzione dell’algebra può essere ottenuta come composizione di funzioni appartenenti ad F (vedi <AND, OR, NOT>).
• Una funzione δ si dice duale rispetto ad una funzione f quando è possibile ricavare δ da f servendosi della legge di dualità, sostituendo la somma col prodotto e il minimo con il massimo (o viceversa).

Più operazioni sono coinvolte in una funzione booleana, più alto sarà il numero di livelli da superare per poter ottenere l’espressione desiderata dell’uscita. L’obiettivo, perciò, è quello di minimizzare il numero di livelli per ridurre la complessità della funzione e i tempi necessari per ottenere l’uscita.

Altri teoremi e teoremi di De Morgan

• 0 e 1 sono uno il complemento dell’altro.
• Negando due volte un elemento si ottiene l’elemento stesso.
• 0 è l’elemento neutro della somma.
• 1 è l’elemento neutro del prodotto.
• āa + b = ā + b; assorbimento del complemento.
• Il complemento della somma è pari al prodotto dei complementi; De Morgan.
• Il complemento di un prodotto è pari alla somma dei complementi; De Morgan.

I due teoremi di De Morgan evidenziano la convenienza di utilizzo delle porte NAND e NOR.

Principio di eliminazione

Nell’algebra di Boole non vale il principio di eliminazione: x + y = x + z non implica necessariamente che y = z, per poterlo dimostrare è necessario anche che xy = xz.

Algebre notevoli

I teoremi precedentemente enunciati possono essere applicati anche ad altre algebre:

1. Algebra degli insiemi;
2. Algebra della logica delle proposizioni;
3. Algebra dei circuiti.

Algebra degli insiemi

Il teorema di Stone afferma che ogni algebra di Boole è rappresentabile su un’algebra di insiemi.

Algebra della logica delle proposizioni

L’insieme K = {0, 1} su cui siano definite le operazioni di:

• Disgiunzione (v);
• Congiunzione (^);
• Negazione (¬),

è una sestupla ‹K, v, ^, ¬, F, V› definibile come algebra di Boole.

Due funzioni notevoli dell’algebra della logica delle proposizioni sono:

• La funzione equivalenza: a <=> b se e solo se f(a, b) = ab + (-a -b).
• La funzione implicazione: a => b se e solo se f(a, b) = -a +b.

In generale, quindi:

Algebra dei circuiti

L’algebra dei circuiti associa agli elementi “0” e “1” i valori “basso” e “alto”.

Le reti unilaterali sono date da tre porte fondamentali che prendono il nome di AND, OR e NOT.

Esiste una corrispondenza biunivoca tra la forma algebrica e il circuito.

• È detto letterale il corrispettivo di una variabile booleana.
• È detto termine elementare o clausola un elemento costituito da n letterali in AND.
• È detto fattore elementare un elemento costituito da n letterali in OR.
• Data una funzione di n variabili esprimibile come somma di prodotti tra le n variabili, ciascun termine della somma si dirà mintermine (P).
• Data una funzione di n variabili esprimibile come prodotto di somme tra le n variabili, ciascun termine del prodotto si dirà maxtermine (S).

È possibile servirsi dei pedici per poter riferirsi ad uno specifico mintermine o maxtermine.

Nel caso dei mintermini si associa a ciascun letterale affermato il valore 1 e a ciascun letterale negato il valore 0 per ottenere poi il valore decimale complessivo ricavato dalla rappresentazione binaria. Nel caso dei maxtermini le associazioni sono invertite (0 -> affermato, 1 -> negato).

Esistono alcune proprietà relative ai mintermini e ai maxtermini da tenere in considerazione:

1. Il complemento del mintermine i-esimo equivale al maxtermine i-esimo.
2. Il prodotto di due mintermini diversi è sempre nullo.
3. La somma di due maxtermini diversi è sempre nulla.
4. La somma di tutti i mintermini vale 1.
5. Il prodotto di tutti i maxtermini vale 0.

Tabelle di verità (esempio sul quaderno)

Se l’algebra è finita, qualsiasi funzione può essere rappresentata mediante una tabella di verità.

Dato n, il numero di variabili indipendenti di una funzione, e k, il numero di valori del supporto dell’algebra, il numero di punti che costituiscono la funzione è: N = kⁿ.

Il numero di funzioni possibili conoscendo i dati precedentemente enunciati sarà quindi: M = k^N.

Una funzione di n variabili, assegnata mediante una tabella di verità, può essere espressa, algebricamente, da una somma di prodotti, ovvero in forma normale di tipo P. Qualsiasi funzione algebrica può essere posta in forma normale P “aggiungendo” i letterali mancanti.

Una funzione di n variabili, assegnata mediante una tabella di verità, può essere espressa, algebricamente, da un prodotto di somme, ovvero in forma normale di tipo S. È possibile passare dalla forma P alla S negando tutti i mintermini e applicando De Morgan.

Il numero specifico è la stringa ordinata di valori, tipica di ciascuna funzione, coincidente con la colonna di "0" e "1" nella tabella di verità.

Quando il valore che assume una funzione è irrilevante ai fini del funzionamento del sistema si parla di punti di non specificazione della funzione.

Mappe di Karnaugh (esempi sul quaderno)

Le mappe di Karnaugh sono una rappresentazione “tabellare” delle funzioni booleane in alternativa alle tabelle di verità e consentono di individuare facilmente i “consensi” (uno o più letterali che assumono sia il valore 0 che il valore 1 nel raggruppamento) nell’espressione algebrica. È possibile utilizzare le mappe di Karnaugh per funzioni dotate al più di 5 variabili.

Funzioni di due variabili

Si dimostra che anche le operazioni NAND e NOR costituiscono, da sole, un insieme funzionalmente completo.

Minimizzazione

Forme ridotte

Le forme ridotte consentono di realizzare circuiti più economici ed ottimizzati.

• Per costo di letterali (CL) si intende il numero delle variabili indipendenti della funzione anche ripetute.
• Per costo di funzioni o di porte (CP) si intende il numero complessivo di porte adoperate.
• Per costo di ingressi (CI) si intende il prodotto tra ciascuna porta e il numero di ingressi di cui essa è costituita.

Gli algoritmi di minimizzazione consentono sempre di ricondursi ad una rete a due livelli.

Implicanti di una funzione

Un implicante f di una funzione f è a sua volta una funzione tale che la somma tra l’implicante negato e la funzione stessa vale 1.

Un implicante primo implica esclusivamente la funzione a cui fa riferimento.

Una funzione può essere espressa come somma dei suoi implicanti primi e, qualora vi fossero implicanti non primi nella somma, questi possono essere facilmente rimossi.

Qualsiasi mintermine di una forma P di una funzione è un implicante della funzione stessa.

Una clausola B implica una clausola A se e solo se B contiene almeno tutti i letterali di A.

La somma di due clausole di ordine n che contengono n-1 letterali uguali ed in cui il letterale di una sia il complemento di quella dell’altra è la clausola di ordine n-1 formata dai letterali comuni (consenso).

Ad una funzione può essere aggiunto un suo implicante senza alterarne il valore.

Un implicante E primo è detto essenziale se è l’unico ad essere implicato da un mintermine i di una funzione, ovvero se è l’unico a “coprire” un certo mintermine della funzione.

Il nucleo N di una funzione è dato dalla somma di tutti i suoi implicanti primi essenziali.

Ogni forma minima di una funzione booleana è data dalla somma dei suoi implicanti primi essenziali (N) e dei suoi implicanti primi non essenziali (R) eventualmente nulli.

Minimizzare una funzione vuol dire, quindi:

1. Ricercare tutti gli implicanti primi di una funzione (vedi McCluskey);
2. Selezionare tutti gli implicanti primi essenziali per ricavare il nucleo N (vedi copertura minima);
3. Determinare il residuo R da aggiungere ad N per poter minimizzare (vedi linee dominanti).

Ricerca degli implicanti primi essenziali e non essenziali (esempi sul quaderno)

• Col metodo di McCluskey è possibile rappresentare ciascun mintermine come una stringa contenente i caratteri per trovare gli implicanti primi:
  • “1” per le variabili in forma affermata;
  • “0” per le variabili in forma negata;
  • “-” per le variabili che non compaiono nel prodotto.

Nello specifico, in una colonna si suddividono i mintermini in classi sulla base del numero di variabili affermate che li compongono. Successivamente si analizzano i consensi che possono generarsi tra i mintermini di una classe e quelli della successiva, andando a riportare i risultati ottenuti in una colonna posta accanto alla prima. Questa procedura viene iterata fino a quando non vengono più riscontrati consensi.

• Col metodo della copertura minima è possibile selezionare gli implicanti primi essenziali che costituiscono il nucleo N attraverso la costruzione di una matrice di copertura che presenta sulle righe i mintermini precedentemente ottenuti col metodo di McCluskey e sulle colonne i valori per cui la funzione assume valore 1. Una volta costruita, vengono identificati gli 1 isolati nelle colonne (che genereranno il nucleo N) per poi eliminare l’intera riga e colonna che li ospita oltre alle colonne in corrispondenza degli altri 1 che vengono interessati nell’eliminazione delle righe.
• Col metodo delle righe e delle colonne dominanti è possibile ricavare il residuo R per completare il processo di minimizzazione.
  • Si definisce linea indifferentemente una riga o una colonna della tabella di copertura.
  • Una linea L domina una linea K se L contiene tutti gli 1 di K nella stessa posizione.
  • Eliminando le righe dominate o le colonne dominanti da una matrice di copertura, si otterrà una matrice di copertura equivalente alla precedente.

Nello specifico, una volta ottenuta la matrice ridotta grazie al metodo della copertura minima, vengono eliminate tutte le righe dominate e le colonne dominanti. Gli 1 restanti (eventualmente) andranno a costituire il residuo R che consentirà di completare la procedura di minimizzazione ed esprimere la funzione d’uscita come somma di N ed R.

Codifica delle informazioni e macchine elementari

Classificazione dei circuiti digitali

I circuiti digitali possono essere classificati in due categorie:

1. I circuiti combinatori, in cui l’uscita ad un certo istante dipende unicamente dal valore degli ingressi nello stesso istante;
2. I circuiti sequenziali, in cui l’uscita ad un certo istante dipende sia dal valore degli ingressi nello stesso istante, sia dal valore degli ingressi in istanti precedenti; quindi, per definire il comportamento di un circuito sequenziale, è necessario considerare la storia passata degli ingressi, ovvero lo stato.

Macchine combinatorie

Una macchina combinatoria è una rete logica con n ingressi (x₁, x₂, …, x_n) ed m uscite (y₁, y₂, …, y_m) che ad ogni insieme di valori degli ingressi fa corrispondere un preciso insieme di valori delle uscite. Il comportamento di una macchina combinatoria può essere descritto mediante tabelle di verità oppure con m funzioni booleane dipendenti delle n variabili in ingresso.

È possibile suddividere ulteriormente le macchine combinatorie in due categorie:

1. Le macchine combinatorie ideali, in cui l’associazione ingresso-uscita è istantanea;
2. Le macchine combinatorie reali, in cui tale associazione presenta un ritardo tra l’istante in cui vi è una variazione degli ingressi e l’istante in cui tale variazione si ripercuote sulle uscite.

Un’uscita y può essere decomposta in più funzioni componenti mentre due uscite differenti possono essere caratterizzate dalla stessa funzione componente, permettendo di ridurre il numero di porte elementari da utilizzare per la realizzazione del circuito (questo aspetto non sarà approfondito).

Mentre ad ogni rete combinatoria corrisponde un’unica tabella di verità, ad una tabella di verità possono corrispondere più reti combinatorie; perciò, è possibile porsi l’obiettivo di realizzare circuiti con un tipo specifico di porte elementari o col minimo numero possibile di porte elementari.

Codifica

La codifica è una modalità di rappresentazione di un’informazione appartenente ad un insieme D. Essa può essere vista come un funzione iniettiva dal dominio D ad un codominio R detto direttamente manipolabile.

L’alfabeto origine T è un dominio (tipo) contenente gli elementi necessari per codificare una certa informazione.

L’alfabeto in codice E è invece un insieme contenente elementi nati dalla combinazione degli elementi di T (stringhe).

In una codifica a lunghezza fissa l ad ogni elemento di T corrisponde una stringa costituita da m simboli, con k che è la cardinalità di T. Dunque, per codificare un dato di cardinalità N mediante un alfabeto di k simboli è necessaria una stringa di lunghezza minima l = m = log_kN.

Se l = m ma N non è potenza di k, il codice viene detto incompleto e la differenza k^m - N fornisce il numero di parole codice non assegnate, cioè non associate ad alcun elemento dell’alfabeto origine.

Si ottiene, invece, un codice ridondante quando l > m, ovvero quando si adoperano più caratteri dell’alfabeto in codice di quelli strettamente necessari. Potrebbe essere utile per la rilevazione di errori, pur implicando un maggior impiego di memoria e una maggiore lentezza nella trasmissione dei dati.

Un codice ridondante è anche incompleto.

La codifica a lunghezza variabile viene utilizzata quando non tutti gli elementi di T hanno la stessa probabilità di occorrenza. Dato un insieme T = {x₁, x₂, …, x_n} e dette p₁, p₂, …, p_n le probabilità di occorrenza associate a ciascun elemento di T, la lunghezza variabile l_i viene scelta in modo da minimizzare la lunghezza media del codice: L_m = Σ_i=1,n (p_i * l_i). Nello specifico, ad elevate probabilità di occorrenza di un elemento di T corrisponderà una lunghezza breve, mentre a basse probabilità corrisponderà una lunghezza maggiore.

In questo modo si ottiene un codice a minima ridondanza che consente un minor impiego di memoria anche se i tempi di elaborazione dell’informazione potrebbero allungarsi poiché, non essendo stata definita a priori una lunghezza, l’elaboratore non sarà a conoscenza della dimensione del dato da gestire.

Decodificatore (esempi sul quaderno)

Un decodificatore binario o decoder è una macchina combinatoria che ad n ingressi codice in binario associa m ≤ 2 uscite