Architettura dei Calcolatori: Reti Combinatorie - Introduzione

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à:

1. Assenza di stati interni: Non hanno memoria. Il comportamento del circuito è completamente determinato dagli ingressi attuali.
2. Tempo di propagazione: Il tempo necessario affinché i segnali di ingresso si propaghino fino alle uscite.
3. 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:

1. Descrizione del problema: La prima fase prevede la specifica del comportamento desiderato, ovvero come gli input devono essere trasformati in output.
2. 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.
3. 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.
4. 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:

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 è:

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 è:

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 è:

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 è:

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 è:

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:

1. 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.
2. Controllo di flusso nei processori: In molti sistemi, i multiplexer e decoder combinatori determinano il flusso dei dati all’interno di un processore.
3. Convertitori di codice: I circuiti combinatori possono essere utilizzati per convertire tra diverse rappresentazioni di dati, come binario-decimale, binario-BCD o binario-Grigio.
4. 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.
5. 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:

1. NOT (A)

   • Ingressi: 1
   • Descrizione: Restituisce il valore negato dell’ingresso.
   • Formula: f(A) = ¬A

2. AND (A, B)

   • Ingressi: 2
   • Descrizione: Vero solo se entrambi gli ingressi sono veri.
   • Formula: f(A, B) = A ∧ B

3. OR (A, B)

   • Ingressi: 2
   • Descrizione: Vero se almeno uno degli ingressi è vero.
   • Formula: f(A, B) = A ∨ B

4. NAND (A, B)

   • Ingressi: 2
   • Descrizione: Vero se almeno uno degli ingressi è falso.
   • Formula: f(A, B) = ¬(A ∧ B)

5. NOR (A, B)

   • Ingressi: 2
   • Descrizione: Vero solo se entrambi gli ingressi sono falsi.
   • Formula: f(A, B) = ¬(A ∨ B)

6. XOR (A, B)

   • Ingressi: 2
   • Descrizione: Vero se uno solo dei due ingressi è vero.
   • Formula: f(A, B) = A ⊕ B

7. 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)

8. Parity (A, B, C)

   • Ingressi: 3
   • Descrizione: Vero se il numero di ingressi veri è dispari.
   • Formula: f(A, B, C) = A ⊕ B ⊕ C

9. AND-OR (A, B, C)

   • Ingressi: 3
   • Descrizione: Vero se A ∧ B è vero o C è vero.
   • Formula: f(A, B, C) = (A ∧ B) ∨ C

10. 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)

11. 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

12. Implicazione (A, B)

    • Ingressi: 2
    • Descrizione: Vero se A implica B (cioè ¬A ∨ B).
    • Formula: f(A, B) = ¬A ∨ B

13. XOR-AND (A, B, C)

    • Ingressi: 3
    • Descrizione: Vero se A ⊕ B è vero e C è vero.
    • Formula: f(A, B, C) = (A ⊕ B) ∧ C

14. Multiplexer (A, B, S)

    • Ingressi: 3
    • Descrizione: Seleziona tra A o B in base al selettore S.
    • Formula: f(A, B, S) = (S ∧ A) ∨ (¬S ∧ B)

15. Sommatore completo (A, B, Cin)

    • Ingressi: 3
    • Descrizione: Somma binaria dei tre ingressi, senza riporto.
    • Formula: f(A, B, Cin) = A ⊕ B ⊕ Cin

16. 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)

17. 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)

18. 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)

19. 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)

20. 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)

21. 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

22. Funzione di selezione (A, B, C, S)

    • Ingressi: 4
    • Descrizione: Seleziona A ∧ B se S è vero, altrimenti ¬C.
    • Formula: f(A, B, C, S) = (S ∧ (A ∧ B)) ∨ (¬S ∧ ¬C)

23. 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)

24. 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)

25. AND-OR con 4 ingressi (A, B, C, D)

    • Ingressi: 4
    • Descrizione: Vero se A ∧ B o C ∨ D è vero.
    • Formula: f(A, B, C, D) = (A ∧ B) ∨ (C ∨ D)

26. NAND-OR con 4 ingressi (A, B, C, D)

    • Ingressi: 4
    • Descrizione: Vero se A ∧ B è falso o C ∨ D è vero.
    • Formula: f(A, B, C, D) = ¬(A ∧ B) ∨ (C ∨ D)

27. 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)

28. 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

29. 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)

30. 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 selettori S0 e S1.
    • Formula: f(A, B, C, D, S0, S1) = (S0 ∧ S1 ∧ D) ∨ (S0 ∧ ¬S1 ∧ C) ∨ (¬S0 ∧ S1 ∧ B) ∨ (¬S0 ∧ ¬S1 ∧ A)

31. 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

32. 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)

33. 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))

34. 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)

35. AND-OR con 4 ingressi (A, B, C, D)

    • Ingressi: 4
    • Descrizione: Vero se A ∧ B o C ∨ D è vero.
    • Formula: f(A, B, C, D) = (A ∧ B) ∨ (C ∨ D)

36. NAND-OR con 4 ingressi (A, B, C, D)

    • Ingressi: 4
    • Descrizione: Vero se A ∧ B è falso o C ∨ D è vero.
    • Formula: f(A, B, C, D) = ¬(A ∧ B) ∨ (C ∨ D)

37. 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)

38. 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)

39. 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)

40. 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 a H in base ai selettori S0, S1, S2.
    • Formula: f(A, B, C, D, E, F, G, H, S0, S1, S2) = (S2 ∧ S1 ∧ S0 ∧ H) ∨ (S2 ∧ S1 ∧ ¬S0 ∧ G) ∨ …