Fondamenti di informatica - Laurea triennale Informatica/Circuiti combinatori

Porta logica OR

Porta logica AND

Porta logica NOT

I circuiti combinatori sono circuiti digitali il cui output dipende solo dagli input presenti in quel momento. A differenza dei circuiti sequenziali, i circuiti combinatori non hanno memoria: gli input precedenti o lo stato passato del sistema non influenzano il risultato.

Alla base dei circuiti combinatori ci sono i bit, che possono assumere solo due valori: 0 e 1. Nei computer digitali, dati e programmi sono rappresentati tramite combinazioni di bit. I bit possono essere trasmessi nei circuiti elettronici attraverso livelli di tensione, ad esempio una tensione alta per rappresentare 1 e una tensione bassa per rappresentare 0.

Le porte logiche fondamentali

AND

Riceve due input e produce 1 solo se entrambi gli input sono 1. In tutti gli altri casi produce 0. È equivalente a prendere il minimo tra due bit.

OR

Riceve due input e produce 1 se almeno uno degli input è 1. Produce 0 solo quando entrambi gli input sono 0. È equivalente a prendere il massimo tra due bit.

NOT

Riceve un solo input e lo inverte: se l’input è 1 produce 0, se l’input è 0 produce 1. È chiamata anche inverter.

La tabella logica

Per descrivere il comportamento di un circuito si usa una tabella logica, che elenca tutte le possibili combinazioni degli input e il corrispondente output. Per esempio, se un circuito ha tre input, bisogna considerare tutte le combinazioni possibili di 0 e 1, quindi 8 righe.

INPUT		OUTPUT
$A$	$B$	$A\wedge B$
0	0	0
0	1	0
1	0	0
1	1	1

INPUT		OUTPUT
$A$	$B$	$A\vee B$
0	0	0
0	1	1
1	0	1
1	1	1

INPUT	OUTPUT
A	NOT A
0	1
1	0

Un circuito è combinatorio solo se, per ogni combinazione di input, l’output è determinato in modo univoco. Un esempio di circuito non combinatorio è un circuito in cui l’output viene reinserito come input: in questo caso il risultato può dipendere dallo stato precedente del circuito, quindi il circuito può funzionare come una memoria.

Un altro concetto importante è che più circuiti combinatori possono essere interconnessi per formarne uno più grande. Se i singoli circuiti sono combinatori e vengono collegati correttamente, anche il circuito risultante resta combinatorio.

I circuiti combinatori sono collegati alle espressioni booleane. Ogni circuito combinatorio con un output può essere rappresentato tramite un’espressione costruita con variabili, operatori AND, OR e NOT. Per esempio, seguendo il percorso del circuito, si può scrivere un’espressione che descrive esattamente il valore dell’output.

Le espressioni booleane sono definite in modo ricorsivo: le variabili sono espressioni booleane, e se due espressioni sono booleane, allora anche la loro combinazione tramite AND, OR o NOT è una nuova espressione booleana. Una variabile o la sua negazione viene chiamata letterale.

Proprietà dei circuiti combinatori

Le proprietà fondamentali degli operatori booleani usati nei circuiti combinatori: AND (∧), OR (∨) e NOT ( ), definiti sull’insieme B={0,1} sono qui illustrate.

Le principali leggi dell’algebra booleana includono:

• Leggi associative: permettono di raggruppare più operazioni AND o OR senza ambiguità. Esempio: (A∨B)∨C =A∨B∨C
• Leggi commutative: l’ordine degli operandi non cambia il risultato. Esempio: A∨B=B∨A
• Leggi distributive: AND e OR si distribuiscono l’uno sull’altro. Esempio: A∧(B∨C)=(A∧B)∨(B∧C)
• Leggi dell’identità: usare 0 o 1 in certe operazioni lascia invariato il valore. A∨0=A, A∧1=A
• Leggi del complemento: combinano una variabile con la sua negazione. A∨NOT(A)=1, A∧NOT(A)=0

Per dimostrare queste proprietà, si possono usare le tabelle di verità, verificando che due espressioni producano lo stesso risultato per tutti i possibili valori delle variabili.

Due espressioni sono uguali se hanno lo stesso valore per ogni possibile assegnazione di bit alle variabili. Per esempio, si può dimostrare con una tabella di verità che due formule diverse sono equivalenti se producono sempre gli stessi output.

Due circuiti con gli stessi input e un solo output sono equivalenti se, dati gli stessi input, producono sempre lo stesso output. Questo significa che circuiti fisicamente diversi possono rappresentare la stessa funzione logica.

Un esempio importante mostra che il circuito corrispondente a: NOT(a∨b) è equivalente al circuito corrispondente a: NOT(a)∧NOT(b) perché le due espressioni hanno la stessa tabella di verità. Questo è un caso delle leggi di De Morgan.

Due circuiti combinatori sono equivalenti se e solo se le espressioni booleane che li rappresentano sono uguali. Questo collega direttamente il comportamento dei circuiti alla manipolazione algebrica delle espressioni booleane.