Appunti corso Reti logiche

Introduzione

Una macchina digitale è un oggetto artificiale che elabora informazioni. All’interno della macchina digitale le informazioni sono rappresentate da grandezze fisiche che possono assumere un numero finito di valori. Se questo numero è 2, allora la macchina digitale è detta: macchina digitale binaria.

Una rete logica (RL) è una rappresentazione astratta di una macchina digitale binaria. In una RL le informazioni sono rappresentate con zeri e uni.

Molti oggetti «artificiali» contengono al loro interno una o più macchine digitali (solitamente calcolatori), interconnesse tra loro. Alla base di ogni macchina digitale c’è la codifica delle informazioni tramite codici binari.

L’informazione è un attributo di un messaggio.

Esempio: lo stato di una porta - possiamo codificare l’informazione con una variabile binaria (bit) [0 → Porta Aperta; 1 → Porta Chiusa]. Allora, se mi arriverà il messaggio «1» saprò che la porta è chiusa.

La codifica è arbitraria ma ricevitore e trasmettitore devono conoscere entrambi la codifica assegnata. L’informazione è una scelta tra più alternative possibili, se le alternative possibili sono due, si può codificare l’informazione con una sola variabile binaria (variabile che può assumere solo due valori).

Con quattro alternative con una sola variabile ci sono ambiguità!

X X_{1 2} dobbiamo aggiungere al codice una seconda variabile binaria

• 0 0 Nord
• 0 1 Est

Esempio: se il messaggio segnala il quadrante da cui proviene il vento e mi arriva il messaggio «11» so che il vento è Ponente.

• 1 0 Sud
• 1 1 Ovest

Altro esempio: se le alternative aumentano, aumenta l’informazione che porta il messaggio, e devono aumentare le variabili binarie necessarie a codificare il messaggio. Quindi, il numero di variabili binarie necessarie a codificare un messaggio può essere considerata una misura della quantità di informazione portata dal messaggio.

Una stringa di n simboli 0 e 1 si chiama configurazione binaria di n bit.

Ogni volta che aggiungo un bit, raddoppio le informazioni che posso codificare.

n(2 = quantità di informazioni, con n = quantità di bit) x … x x x_{n-1 2 3 0}

Visti i due esempi precedenti, si può anche dire che l’informazione è diminuzione di incertezza, poiché l’informazione esprime una scelta tra un insieme di alternative possibili; ed è un’entità misurabile, la cui unità di misura è il bit (da binary digit), una variabile che può assumere solo due valori: 1 e 0. Un messaggio porta un bit di informazione se rappresenta una scelta (cioè, una riduzione di incertezza) tra due alternative possibili. L’informazione, quindi, può essere rappresentata in bit e la “quantità di informazione” associata a un messaggio è data dal numero minimo di bit necessari a rappresentarlo.

Qualunque informazione si può rappresentare sotto forma di sequenza di zeri e uni. L’operazione di traduzione di un’informazione in una sequenza di “0” e “1” si chiama codifica delle informazioni.

Elaborazione delle informazioni

L’informazione codificata con una sequenza di bit è una entità intangibile, mentre, l’elaborazione è una azione fisica svolta da un dispositivo fisico e richiede quindi: energia, tempo e spazio. Per elaborare, ma anche per trasmettere e memorizzare bit dobbiamo far corrispondere agli zeri e agli uni valori diversi di una grandezza fisica che possa essere rilevata e modificata (es. grandezze elettriche, in particolare tensioni). Queste grandezze fisiche misurabili che rappresentano un’informazione si chiamano segnali.

La ricerca nell’ambito delle tecnologie elettroniche mira a ridurre spazio (es. superficie di silicio), energia e tempo necessari a parità di elaborazione (carico computazionale).

Ottimizzazione di un progetto: un progetto non può essere ottimo in assoluto. Invece, può essere ottimo rispetto a un determinato parametro (energia, tempo, spazio). Il progettista deve sapere rispetto a quale di questi parametri si vuole ottimizzare il proprio progetto.

Segnali e trasporto dell’informazione

Segnale = grandezza fisica variabile nel tempo il cui andamento o forma d’onda rappresenta l’informazione che la parte sorgente vuole inviare alla parte destinazione.

Segnali analogici: ogni variazione della grandezza fisica modifica l’informazione trasportata. Un disturbo del segnale potrebbe facilmente causare errori nella codifica.

Segnali digitali: solo a certe variazioni corrisponde una modifica di “significato”. Segnale analogico interpretato come insieme finito di valori.

Segnale digitale binario: segnale analogico interpretato come variabile binaria.

Il segnale digitale viene letto in base alla fascia in cui si trova, questo serve per aggirare i disturbi. È considerato «L» finché il segnale analogico reale resta nella fascia L. Idem per H e N.D.

Il segnale non trasporta alcuna informazione quando si trova nella fascia N.D.

Variabili binarie (bit) e rappresentazione

Il bit è definito come: = | ∈ {0,1} e presenta due alternative di codifica:

Una configurazione di n bit si può trasmettere con:

• I valori di n segnali binari ad un certo istante (BIT PARALLEL)
• I valori di un segnale binario in n istanti successivi (BIT SERIAL)
• Diagrammi ad occhio per rappresentare sinteticamente più forme d’onda binarie.

Esempio: andamento di tre segnali.

Macchina digitale e rete logica – nuova definizione

Una macchina digitale è un oggetto artificiale, composto da blocchi interconnessi che elaborano informazioni. All’interno della macchina digitale le informazioni sono rappresentate da grandezze fisiche che possono assumere un numero finito di valori. Se questo numero è 2 (es.: H e L), allora la macchina digitale è detta: macchina digitale binaria.

Una rete logica è una rappresentazione astratta di una macchina digitale binaria. In una RL le informazioni sono rappresentate con zeri e uni.

La macchina digitale più diffusa è il calcolatore. Il calcolatore è una macchina binaria programmabile. All’interno di un calcolatore l’informazione, rappresentata con segnali binari, viene elaborata, memorizzata e trasmessa. La funzione svolta dal calcolatore è dettata dal software, cioè da un insieme di istruzioni codificate in binario e memorizzate all’interno del calcolatore stesso.

Rappresentazione astratta della struttura dell’hardware di un calcolatore elettronico:

I principali metodi di gestione della complessità utilizzati dagli ingegneri sono: l’astrazione (separazione delle informazioni essenziali dai dettagli) e la decomposizione di entità in entità più semplici interconnesse tra loro.

I livelli di astrazione: livello architettonico > livello logico > livello fisico.

Rete Logica = modello della macchina digitale che consente di astrarre dalla tecnologia e di dettagliarne l’immagine architettonica.

Descrizione e progettazione di macchine digitali

Analisi & sintesi in una macchina digitale

La descrizione del comportamento può essere più e più volte decomposta in comportamenti più semplici. Ogni livello di questa gerarchia individua strutture formate da componenti “astratti” la cui struttura è definita nel livello sottostante. Scendendo dall’alto verso il basso aumenta il numero di componenti, diminuisce la complessità dell’azione svolta da ciascuno.

Proprietà di composizione e decomposizione delle reti logiche:

• Composizione: un numero arbitrario di reti logiche connesse è ancora una rete logica.
• Decomposizione: una rete logica può essere decomposta in un insieme di reti logiche più semplici, fino al raggiungimento di reti logiche non più suddivisibili (dette reti logiche elementari o operatori logici elementari o GATE).

Rappresentazione della struttura di una rete logica

Un modello di rappresentazione della struttura di una rete logica è lo schema a blocchi, che rappresenta la rete logica come insieme di blocchi interconnessi. Esistono due tipi di «blocco»: Black Box (scatola nera), in cui il blocco è descritto in termini comportamentali; e White Box (scatola bianca), in cui il blocco è descritto in termini strutturali, come un insieme di blocchi interconnessi. In una descrizione gerarchica di una rete logica, i blocchi di livello più basso devono essere black box (cioè, blocchi con una descrizione comportamentale).

Modello black box. I processi di elaborazione sono descrivibili tramite: tabelle, diagrammi, frasi (es. datasheet), linguaggi formali ad hoc (es. VHDL, Verilog), funzioni d’onda.

Esempio di rappresentazione della relazione di causa/effetto in un ipotetico blocco con 3 ingressi binari e 2 uscite binarie:

Esempio di black box con descrizione del comportamento mediante tabella di verità.

In questa tabella per ogni configurazione d’ingresso c’è un’unica configurazione di uscita. Questa tdv (tabella di verità) definisce una funzione binaria di tre variabili binarie. Con la tabella di verità non si possono descrivere le reti sequenziali (RS).

Una rete sequenziale ha memoria, quindi l’uscita non dipende solo dagli ingressi correnti ma anche dallo stato interno precedente. Per descriverla servono tabelle o grafi degli stati, non una semplice tabella di verità.

Descrizione della struttura: regole “elementari” di composizione di RL

a) In serie → Funzione composta()) = (2 1

Deve operare prima il blocco a sinistra e poi quello a destra.

Ritardi nella realizzazione fisica: = + 1 2

b) In parallelo () = 1 1 → Sistema di funzioni { () = 2 2

I due blocchi operano contemporaneamente = ( , )_{1 2}

c) In retroazione = (, )₁ () = → Funzione ricorsiva 2 ()) = (, 1 2: è necessario che l’anello completi un calcolo prima di avviarne uno nuovo.

La retroazione è possibile solo nelle reti sequenziali.

s rappresenta lo “stato presente” o “stato interno”.

Modello white box. Lo schema logico è un insieme di reti logiche (blocchi G_i) interconnesse. Ad ogni blocco dello schema logico verrà associato nella realizzazione fisica un «componente hardware».

Modalità di descrizione della struttura alternativa allo schema logico: linguaggio formale.

Algebra della commutazione

Descrizione del comportamento. I valori dei segnali d’uscita dipendono solo dai valori contemporanei dei segnali d’ingresso. Il comportamento di una RC con m uscite può essere assegnato mediante m funzioni binarie (funzioni booleane). La black box di una RC va associata a una o più funzioni binarie di variabili binarie.

Una funzione completamente specificata di n variabili binarie z = F(x₁, x₂, …, x_n) è l’insieme di tutte le 2ⁿ coppie ordinate {x, z | x ∈ Bⁿ, z ∈ B} formate da una configurazione di valori delle n variabili indipendenti x_i (cioè, x₁, x₂, …, x_n) e dal corrispondente valore della variabile dipendente z. Una funzione può essere scritta in diversi modi (es: tdv o mappe di Karnaugh).

Descrizione di una funzione mediante tabella di verità

La tabella di verità è una descrizione tabellare di una funzione di variabili binarie.

Funzioni non completamente specificate (funzioni incomplete) = Funzioni di n variabili il cui dominio è un sottoinsieme di Bⁿ.

Quando il valore della funzione F non è specificato in almeno uno dei 2ⁿ punti di Bⁿ si dice che la funzione è incompleta.

(tdv: con un trattino nella colonna di uscita si indicano i punti di Bⁿ in cui la funzione non è definita).

La distanza D tra due configurazioni binarie di n bit è il numero di bit omologhi che hanno valore diverso (distanza di Hamming).

Esempi:

• 1 0 1 e 1 1 1 hanno distanza 1 perché differiscono per un solo bit (il secondo).
• 1 0 1 e 1 1 0 hanno distanza 2 perché differiscono per due bit (il primo da destra e il secondo).
• 0 0 0 e 1 1 1 hanno distanza 3 perché sono configurazioni di 3 bit e i bit omologhi sono tutti diversi.

La massima distanza tra due configurazioni binarie di n bit è n. Due configurazioni binarie che differiscono per un bit (D=1) si dicono adiacenti.

Descrizione di una funzione mediante mappe di Karnaugh

Una mappa di Karnaugh è una rappresentazione bidimensionale della tabella di verità di una funzione di 1,2,3,4 variabili. I valori delle variabili indipendenti vengono elencati sui bordi della mappa osservando la seguente regola: le configurazioni di queste variabili assegnate a righe o a colonne vicine devono essere a distanza 1. Così a ogni configurazione delle n variabili di ingresso (punto di Bⁿ) resta associata una casella all’interno della quale si mette il valore della funzione in quel punto.

La funzione di parità pari a 4 variabili è un controllore di parità, lo stesso principio che si usa nei codici di rilevamento errori (es. trasmissione dati).

Altri esempi (funzioni di due variabili a e b).

Esempio di forme d’onda:

Si dicono coppia di celle adiacenti su mappe di Karnaugh due celle le cui coordinate differiscono per un solo bit (sono cioè, a distanza 1). In una mappa che descrive una funzione di n variabili ogni cella ha n celle adiacenti. Regola grafica per l’adiacenza: sono adiacenti celle aventi un lato in comune o poste all’estremità di una stessa riga o colonna.

Ulteriore regola di adiacenza: sono adiacenti celle che occupano la stessa posizione in sotto-mappe adiacenti.

Comportamento & struttura di una rete logica combinatoria

Le operazioni dell’algebra della commutazione sono il prodotto logico, la somma logica e la complementazione. I corrispondenti blocchi G_i si chiamano AND OR e NOT.

Descrizione algebrica della struttura delle reti logiche combinatorie

Se riuscissimo a costruire l’espressione booleana associata a una funzione booleana, allora riusciremmo sicuramente a disegnare lo schema logico.

Algebra della commutazione = è un sistema matematico che consente di eseguire l’analisi e la sintesi di reti logiche combinatorie. L’algebra della commutazione consente infatti di passare dallo schema logico alla tabella della verità e viceversa.

C’è una corrispondenza biunivoca tra le operazioni dell’algebra di commutazione e gli operatori logici elementari (cioè, i GATE): AND OR e NOT. Ogni GATE viene realizzato con un circuito elettronico digitale.

Definizione dei simboli e delle operazioni dell’algebra della commutazione

1) Operazioni:

• Somma logica (+) (4 postulati)
• Prodotto logico (.) (4 postulati)
• Complementazione (’) (2 postulati)

Le operazioni dell’algebra agiscono su costanti e variabili.

2) Costanti: {0, 1} → questo insieme è l’alfabeto binario su cui le operazioni dell’algebra agiscono.

3) Variabili: simboli sostituibili o con 0 o con 1.

Definizione delle tre operazioni dell’algebra di commutazione e dei corrispondenti operatori logici

Complementazione: = , = ¯ , = ¬. Funzione Operatore NOT.

Somma logica: = + , = ∨. Funzione Operatore OR.

Prodotto logico: = · , = , = ∧. Funzione Operatore OR.

C’è una corrispondenza biunivoca tra gli operatori logici NOT, OR, AND e le tre operazioni dell’algebra complementazione, somma logica e prodotto logico (rispettivamente rappresentate con i caratteri ‘ + ·). C’è una corrispondenza biunivoca tra ingressi dell’operatore logico e operandi dell’operazione algebrica; e anche, tra l’uscita dell’operatore logico e il risultato dell’operazione algebrica.

Definizione di espressione dell’algebra di commutazione

Espressione = stringa finita di costanti, variabili, operatori e parentesi, formata in accordo con le seguenti regole:

• 0 e 1 sono espressioni.
• Una variabile è un’espressione.
• Se A è un’espressione, lo sono anche (A’) e A’.
• Se A, B sono espressioni, lo sono anche (A+B), (A·B).

L’operazione di prodotto è prioritaria rispetto alla somma e non è obbligatorio racchiuderla tra parentesi. La notazione AB indica A·B. Le parentesi sono obbligatorie solo se omettendole cambia l’ordine in cui le operazioni sono applicate agli operandi.

Analisi di reti combinatorie

L’analisi di una rete combinatoria si esegue in tre passi:

1. Dallo schema logico all’espressione.

Per individuare l’espressione corrispondente ad un dato schema si parte dai gate che elaborano solo s