Definizione formale
Una rete combinatoria è definita da un insieme di variabili di ingresso $X = {x_1, x_2, …, x_n}$, un insieme di variabili di uscita $Y = {y_1, y_2, …, y_m}$, e una funzione logica che collega gli ingressi con le uscite. Questa relazione è espressa da una funzione booleana $f: X \rightarrow Y$, dove ogni uscita $y_i$ dipende esclusivamente dai valori correnti delle variabili di ingresso.
Caratteristiche delle Reti Combinatorie
Le reti combinatorie sono caratterizzate da diverse proprietà:
- Assenza di stati interni: Non hanno memoria. Il comportamento del circuito è completamente determinato dagli ingressi attuali.
- Tempo di propagazione: Il tempo necessario affinché i segnali di ingresso si propaghino fino alle uscite.
- Non ciclicità: I circuiti combinatori non hanno cicli di retroazione, il che garantisce che ogni uscita sia determinata esclusivamente dagli input e non da uscite passate.
Un esempio di rete combinatoria è la sommatrice (adder), che somma due numeri binari in parallelo utilizzando porte logiche. Altri esempi includono i moltiplicatori binari, i decoder e i multiplexer.
Costruzione e Implementazione
La progettazione di una rete combinatoria segue una serie di fasi standard:
- Descrizione del problema: La prima fase prevede la specifica del comportamento desiderato, ovvero come gli input devono essere trasformati in output.
- Espressione logica: Viene definita una funzione booleana che esprima la relazione tra input e output. Questa funzione può essere rappresentata utilizzando tabelle di verità o equazioni logiche.
- Ottimizzazione: L’ottimizzazione della funzione booleana consente di ridurre il numero di porte logiche necessarie per implementare il circuito, riducendo così la complessità e i costi del circuito.
- Implementazione fisica: Una volta definita e ottimizzata la funzione logica, si procede all’implementazione fisica utilizzando componenti come porte logiche, transistor e altri dispositivi elettronici.
Porte Logiche
Le reti combinatorie utilizzano porte logiche elementari come AND, OR, NOT, XOR, NAND e NOR per realizzare la funzione logica desiderata. Queste porte sono i mattoni fondamentali per la costruzione di qualsiasi circuito combinatorio.
Esistono diverse tipologie di porte logiche, ognuna delle quali implementa una specifica funzione booleana. Le più comuni includono:
Porta AND
La porta AND restituisce un’uscita alta (1) solo se tutti gli ingressi sono alti (1). La sua funzione booleana è:
$X = A \cdot B$
Dove $Y$ è l’uscita e $A$ e $B$ sono gli ingressi. La tabella di verità per la porta AND è la seguente:
A | B | X |
---|---|---|
0 | 0 | 0 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 1 |
Porta OR
La porta OR restituisce un’uscita alta (1) se almeno uno degli ingressi è alto (1). La sua funzione booleana è:
$X = A + B$
La tabella di verità per la porta OR è:
A | B | X |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
Porta NOT
La porta NOT inverte il valore dell’ingresso: se l’ingresso è 0, l’uscita sarà 1, e viceversa. La sua funzione booleana è:
$X = \overline{A}$
La tabella di verità per la porta NOT è:
A | X |
---|---|
0 | 1 |
1 | 0 |
Porta XOR
La porta XOR (OR esclusivo) restituisce un’uscita alta (1) se uno e solo uno degli ingressi è alto (1). La funzione booleana è:
$X = A \oplus B = (A \cdot \overline{B}) + (\overline{A} \cdot B)$
La tabella di verità per la porta XOR è:
A | B | X |
---|---|---|
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Porta NAND
La porta NAND è l’operazione inversa della porta AND: restituisce un’uscita bassa (0) solo se tutti gli ingressi sono alti (1). La sua funzione booleana è:
$X = \overline{A \cdot B}$
La tabella di verità per la porta NAND è:
A | B | X |
---|---|---|
0 | 0 | 1 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 0 |
Porta NOR
La porta NOR è l’operazione inversa della porta OR: restituisce un’uscita alta (0) solo se tutti gli ingressi sono bassi (0). La sua funzione booleana è:
$X = \overline{A + B}$
La tabella di verità per la porta NOR è:
A | B | X |
---|---|---|
0 | 0 | 1 |
0 | 1 | 0 |
1 | 0 | 0 |
1 | 1 | 0 |
Porte Logiche Universali
Le porte NAND e NOR sono chiamate porte universali perché possono essere utilizzate per implementare qualsiasi altra funzione logica. In pratica, è possibile costruire qualsiasi circuito logico utilizzando solo porte NAND o solo porte NOR, il che offre flessibilità nella progettazione hardware.
Applicazioni delle Reti Combinatorie
Le reti combinatorie sono utilizzate in una vasta gamma di applicazioni, sia nel campo dell’elettronica che dell’informatica. Alcune delle principali applicazioni includono:
- Unità Aritmetico-Logiche (ALU): Le reti combinatorie sono utilizzate per implementare le ALU nei processori, che eseguono operazioni aritmetiche e logiche come addizione, sottrazione, moltiplicazione e confronto.
- Controllo di flusso nei processori: In molti sistemi, i multiplexer e decoder combinatori determinano il flusso dei dati all’interno di un processore.
- Convertitori di codice: I circuiti combinatori possono essere utilizzati per convertire tra diverse rappresentazioni di dati, come binario-decimale, binario-BCD o binario-Grigio.
- Automazione industriale: Le reti combinatorie sono fondamentali nei sistemi di controllo industriali, dove vengono utilizzate per prendere decisioni in tempo reale in base agli input forniti dai sensori.
- Sistemi di crittografia: Le reti combinatorie vengono impiegate nei sistemi di cifratura, dove le trasformazioni logiche degli input possono essere utilizzate per generare chiavi crittografiche o per implementare algoritmi di codifica e decodifica.
Esercizi
Codificare in diagramma con le corrispondenti porte logiche e tabelle di verità le seguenti funzioni booleane ad una sola uscita:
NOT (A)
- Ingressi: 1
- Descrizione: Restituisce il valore negato dell’ingresso.
- Formula:
f(A) = ¬A
AND (A, B)
- Ingressi: 2
- Descrizione: Vero solo se entrambi gli ingressi sono veri.
- Formula:
f(A, B) = A ∧ B
OR (A, B)
- Ingressi: 2
- Descrizione: Vero se almeno uno degli ingressi è vero.
- Formula:
f(A, B) = A ∨ B
NAND (A, B)
- Ingressi: 2
- Descrizione: Vero se almeno uno degli ingressi è falso.
- Formula:
f(A, B) = ¬(A ∧ B)
NOR (A, B)
- Ingressi: 2
- Descrizione: Vero solo se entrambi gli ingressi sono falsi.
- Formula:
f(A, B) = ¬(A ∨ B)
XOR (A, B)
- Ingressi: 2
- Descrizione: Vero se uno solo dei due ingressi è vero.
- Formula:
f(A, B) = A ⊕ B
Majority (A, B, C)
- Ingressi: 3
- Descrizione: Vero se almeno due ingressi sono veri.
- Formula:
f(A, B, C) = (A ∧ B) ∨ (A ∧ C) ∨ (B ∧ C)
Parity (A, B, C)
- Ingressi: 3
- Descrizione: Vero se il numero di ingressi veri è dispari.
- Formula:
f(A, B, C) = A ⊕ B ⊕ C
AND-OR (A, B, C)
- Ingressi: 3
- Descrizione: Vero se
A ∧ B
è vero oC
è vero. - Formula:
f(A, B, C) = (A ∧ B) ∨ C
AND-OR-NOT (A, B, C, D)
- Ingressi: 4
- Descrizione: Vero se
A ∧ B
è vero o¬C ∧ D
è vero. - Formula:
f(A, B, C, D) = (A ∧ B) ∨ (¬C ∧ D)
OR-AND-NOT (A, B, C)
- Ingressi: 3
- Descrizione: Vero se
A ∨ B
è vero e¬C
è vero. - Formula:
f(A, B, C) = (A ∨ B) ∧ ¬C
Implicazione (A, B)
- Ingressi: 2
- Descrizione: Vero se
A
implicaB
(cioè¬A ∨ B
). - Formula:
f(A, B) = ¬A ∨ B
XOR-AND (A, B, C)
- Ingressi: 3
- Descrizione: Vero se
A ⊕ B
è vero eC
è vero. - Formula:
f(A, B, C) = (A ⊕ B) ∧ C
Multiplexer (A, B, S)
- Ingressi: 3
- Descrizione: Seleziona tra
A
oB
in base al selettoreS
. - Formula:
f(A, B, S) = (S ∧ A) ∨ (¬S ∧ B)
Sommatore completo (A, B, Cin)
- Ingressi: 3
- Descrizione: Somma binaria dei tre ingressi, senza riporto.
- Formula:
f(A, B, Cin) = A ⊕ B ⊕ Cin
Carry-out (Sommatore completo) (A, B, Cin)
- Ingressi: 3
- Descrizione: Restituisce il riporto in uscita della somma completa.
- Formula:
f(A, B, Cin) = (A ∧ B) ∨ (B ∧ Cin) ∨ (A ∧ Cin)
Controllo parità (A, B, C, D)
- Ingressi: 4
- Descrizione: Vero se il numero di ingressi veri è pari.
- Formula:
f(A, B, C, D) = ¬(A ⊕ B ⊕ C ⊕ D)
Majority con 4 ingressi (A, B, C, D)
- Ingressi: 4
- Descrizione: Vero se almeno tre ingressi sono veri.
- Formula:
f(A, B, C, D) = (A ∧ B ∧ C) ∨ (A ∧ B ∧ D) ∨ (A ∧ C ∧ D) ∨ (B ∧ C ∧ D)
AND-NAND (A, B, C)
- Ingressi: 3
- Descrizione: Vero se
A ∧ B
è vero e¬(A ∧ B ∧ C)
è vero. - Formula:
f(A, B, C) = (A ∧ B) ∧ ¬(A ∧ B ∧ C)
Funzione “minoritario” (A, B, C, D)
- Ingressi: 4
- Descrizione: Vero se al massimo uno degli ingressi è vero.
- Formula:
f(A, B, C, D) = ¬(A ∨ B ∨ C ∨ D) ∨ (A ∧ ¬B ∧ ¬C ∧ ¬D)
OR esclusivo con 3 ingressi (A, B, C)
- Ingressi: 3
- Descrizione: Vero se un numero dispari di ingressi è vero.
- Formula:
f(A, B, C) = A ⊕ B ⊕ C
Funzione di selezione (A, B, C, S)
- Ingressi: 4
- Descrizione: Seleziona
A ∧ B
seS
è vero, altrimenti¬C
. - Formula:
f(A, B, C, S) = (S ∧ (A ∧ B)) ∨ (¬S ∧ ¬C)
Funzione bilanciata (A, B, C, D)
- Ingressi: 4
- Descrizione: Vero se il numero di ingressi veri è uguale al numero di falsi.
- Formula:
f(A, B, C, D) = (A ⊕ B ⊕ C ⊕ D)
Funzione “Maggiore o uguale a 2” (A, B, C, D)
- Ingressi: 4
- Descrizione: Vero se almeno due degli ingressi sono veri.
- Formula:
f(A, B, C, D) = (A ∧ B) ∨ (A ∧ C) ∨ (A ∧ D) ∨ (B ∧ C) ∨ (B ∧ D) ∨ (C ∧ D)
AND-OR con 4 ingressi (A, B, C, D)
- Ingressi: 4
- Descrizione: Vero se
A ∧ B
oC ∨ D
è vero. - Formula:
f(A, B, C, D) = (A ∧ B) ∨ (C ∨ D)
NAND-OR con 4 ingressi (A, B, C, D)
- Ingressi: 4
- Descrizione: Vero se
A ∧ B
è falso oC ∨ D
è vero. - Formula:
f(A, B, C, D) = ¬(A ∧ B) ∨ (C ∨ D)
Funzione soglia con 5 ingressi (A, B, C, D, E)
- Ingressi: 5
- Descrizione: Vero se almeno 3 dei 5 ingressi sono veri.
- Formula:
f(A, B, C, D, E) = (# ingressi veri ≥ 3)
Sommatore parziale con carry (A, B, C, D, Cin)
- Ingressi: 5
- Descrizione: Somma dei 4 ingressi con il carry-in.
- Formula:
f(A, B, C, D, Cin) = A ⊕ B ⊕ C ⊕ D ⊕ Cin
AND-XOR con 3 ingressi (A, B, C)
- Ingressi: 3
- Descrizione: Vero se
A ∧ (B ⊕ C)
è vero. - Formula:
f(A, B, C) = A ∧ (B ⊕ C)
Multiplexer 4 a 1 (A, B, C, D, S0, S1)
- Ingressi: 6
- Descrizione: Seleziona uno tra i 4 ingressi
A
,B
,C
,D
in base ai selettoriS0
eS1
. - Formula:
f(A, B, C, D, S0, S1) = (S0 ∧ S1 ∧ D) ∨ (S0 ∧ ¬S1 ∧ C) ∨ (¬S0 ∧ S1 ∧ B) ∨ (¬S0 ∧ ¬S1 ∧ A)
XOR con 4 ingressi (A, B, C, D)
- Ingressi: 4
- Descrizione: Vero se un numero dispari di ingressi è vero.
- Formula:
f(A, B, C, D) = A ⊕ B ⊕ C ⊕ D
OR-NAND (A, B, C)
- Ingressi: 3
- Descrizione: Vero se
A ∨ B
è vero e¬(A ∧ B ∧ C)
è vero. - Formula:
f(A, B, C) = (A ∨ B) ∧ ¬(A ∧ B ∧ C)
Funzione simmetrica (A, B, C, D)
- Ingressi: 4
- Descrizione: Vero se il numero di ingressi veri è uguale a quello dei falsi.
- Formula:
f(A, B, C, D) = (A ⊕ B ⊕ C ⊕ D) ∧ ((A ∧ B) = (C ∧ D))
Somma maggiore di 2 (A, B, C, D)
- Ingressi: 4
- Descrizione: Vero se almeno due degli ingressi sono veri.
- Formula:
f(A, B, C, D) = (A ∧ B) ∨ (A ∧ C) ∨ (A ∧ D) ∨ (B ∧ C) ∨ (B ∧ D) ∨ (C ∧ D)
AND-OR con 4 ingressi (A, B, C, D)
- Ingressi: 4
- Descrizione: Vero se
A ∧ B
oC ∨ D
è vero. - Formula:
f(A, B, C, D) = (A ∧ B) ∨ (C ∨ D)
NAND-OR con 4 ingressi (A, B, C, D)
- Ingressi: 4
- Descrizione: Vero se
A ∧ B
è falso oC ∨ D
è vero. - Formula:
f(A, B, C, D) = ¬(A ∧ B) ∨ (C ∨ D)
Funzione soglia con 5 ingressi (A, B, C, D, E)
- Ingressi: 5
- Descrizione: Vero se almeno 3 dei 5 ingressi sono veri.
- Formula:
f(A, B, C, D, E) = (# ingressi veri ≥ 3)
AND-XOR con 3 ingressi (A, B, C)
- Ingressi: 3
- Descrizione: Vero se
A ∧ (B ⊕ C)
è vero. - Formula:
f(A, B, C) = A ∧ (B ⊕ C)
NOR-AND con 4 ingressi (A, B, C, D)
- Ingressi: 4
- Descrizione: Vero se
¬(A ∨ B ∨ C ∨ D)
e¬(A ∧ B ∧ C ∧ D)
sono veri. - Formula:
f(A, B, C, D) = ¬(A ∨ B ∨ C ∨ D) ∧ ¬(A ∧ B ∧ C ∧ D)
Multiplexer a 8 ingressi (A, B, C, D, E, F, G, H, S0, S1, S2)
- Ingressi: 11
- Descrizione: Seleziona uno degli 8 ingressi
A
fino aH
in base ai selettoriS0, S1, S2
. - Formula:
f(A, B, C, D, E, F, G, H, S0, S1, S2) = (S2 ∧ S1 ∧ S0 ∧ H) ∨ (S2 ∧ S1 ∧ ¬S0 ∧ G) ∨ …