circuiti elettronici

esempi:

• circuito che codifica una pulsantiera numerica in binario
• circuito che controlla le barrette numeriche di un display
• circuito che sceglie un ingresso video
• sommatore a due e tre, senza e con riporto
• ascensore, segnalatori di piano e chiamata, uscite su e giu
• circuito a maggioranza fra 3, per sensori di allarme
• sintesi

codifica binaria

ingressi espressi in binario
quindi booleani

anche le uscite

le uscite dipendono dagli ingressi

una formula per uscita:

variabili della formula

gli ingressi

valore della formula

quanto vale una uscita con quegli ingressi

pulsantiera numerica

ingressi

un bit per pulsante 1-9

• falso = tasto non premuto
• vero = tasto premuto

uscita

un numero a tre bit

• tasto uno ⇒ bit 001
• tasto due ⇒ bit 002
• …
• tasto nove ⇒ bit 101

ingressi e uscite per la pulsantiera

ingressi p1 … p9
uno per pulsante

uscite n2 n1 n0
un numero a tre bit

primo bit della pulsantiera

• vero se è premuto il tasto otto o il nove
• falso per tutti gli altri

qual è la formula?

formula per il primo bit della pulsantiera

nessun tasto premuto

0 (falso)

tasto premuto, da uno a sette

0 (falso)

tasto otto premuto oppure tasto nove premuto

1 (vero)

qual è la formula?

formula per il primo bit della pulsantiera

p1=falso … p9=falso

0 (falso)

p1=vero … p7=vero

0 (falso)

p8=vero oppure p9=vero

1 (vero)

il primo bit vale uno (vero) quando
l'ottavo pulsante viene premuto oppure
il nono pulsante viene premuto

p8 ∨ p9

secondo bit della pulsantiera

tutti gli ingressi a 0

uscita 0

primo ingresso vero

uscita 0

secondo ingresso vero

uscita 1

terzo ingresso vero

…

formula complicata
tabella ingresso-uscita

ingressi e uscite

pulsanti p1 … p9

secondo bit uscita u2

selezione ingressi e uscite

seconda uscita

l'uscita vale 1
se uno dei pulsanti p4 … p7 viene premuto

u2 = p4 ∨ p5 ∨ p6 ∨ p7

tutte le formule

u1 = p8 ∨ p9
u2 = p4 ∨ p5 ∨ p6 ∨ p7
u3 = p2 ∨ p3 ∨ p6 ∨ p7
u4 = p1 ∨ p3 ∨ p5 ∨ p7 ∨ p9

barrette numeriche di un display

ognuna può essere accesa (true) o spenta (false)

schema delle barrette

ingressi

la cifra, da zero a nove
rappresentato in binario con quattro bit

uscite

una per ogni barretta
dice se deve essere accesa o spenta

cifre sul display

ingressi e uscite

barretta orizzontale in alto

accesa per i numeri 0, 2, 3, 5, 6, 7, 8, 9

barretta verticale in alto a sinistra

accesa per i numeri 0, 4, 5, 6, 8, 9

…

barretta verticale in alto a sinistra

vera per i valori 0, 4, 5, 6, 8, 9
falsa altrimenti

barretta: nomi delle variabili

cifre dell'ingresso: c3, c2, c1, c0
valore dell'uscita: as

vera per i valori 0, 4, 5, 6, 8, 9
falsa altrimenti

formula as=…?

formula per l'uscita

uscita vera quando gli ingressi valgono:

• 0000
• 0100
• 0101
• 0110
• 1000
• 1001

formula per un valore di ingresso

uscita vera quando gli ingressi valgono:

• 0000
• 0100
• 0101
• 0110
• 1000
• 1001

l'ingresso vale 0000 quando c3=false, c2=false, c1=false, c0=false

¬c3 ∧ ¬c2 ∧ ¬c1 ∧ ¬c0

l'ingresso vale 0100 quando c3=false, c2=true, c1=false, c0=false

¬c3 ∧ c2 ∧ ¬c1 ∧ ¬c0

formula complessiva

la barretta in alto a sinistra è accesa quando

(¬c3 ∧ ¬c2 ∧ ¬c1 ∧ ¬c0) ∨ (¬c3 ∧ c2 ∧ ¬c1 ∧ ¬c0) ∨ (¬c3 ∧ c2 ∧ ¬c1 ∧ c0) ∨ (¬c3 ∧ c2 ∧ c1 ∧ ¬c0) ∨ (c3 ∧ ¬c2 ∧ ¬c1 ∧ ¬c0) ∨ (c3 ∧ ¬c2 ∧ ¬c1 ∧ c0)

semplificazione

(¬c3 ∧ ¬c2 ∧ ¬c1 ∧ ¬c0) ∨ (¬c3 ∧ c2 ∧ ¬c1 ∧ ¬c0) ∨ (¬c3 ∧ c2 ∧ ¬c1 ∧ c0) ∨ (¬c3 ∧ c2 ∧ c1 ∧ ¬c0) ∨ (c3 ∧ ¬c2 ∧ ¬c1 ∧ ¬c0) ∨ (c3 ∧ ¬c2 ∧ ¬c1 ∧ c0)

ultimi due termini:

(c3 ∧ ¬c2 ∧ ¬c1 ∧ ¬c0) ∨ (c3 ∧ ¬c2 ∧ ¬c1 ∧ c0) = (c3 ∧ ¬c2 ∧ ¬c1 )

altre semplificazioni

(¬c3 ∧ ¬c2 ∧ ¬c1 ∧ ¬c0) ∨ (¬c3 ∧ c2 ∧ ¬c1 ∧ ¬c0) ∨ (¬c3 ∧ c2 ∧ ¬c1 ∧ c0) ∨ (¬c3 ∧ c2 ∧ c1 ∧ ¬c0) ∨ ( c3 ∧ ¬c2 ∧ ¬c1 )

primo e secondo termine:

(¬c3 ∧ ¬c2 ∧ ¬c1 ∧ ¬c0) ∨ (¬c3 ∧ c2 ∧ ¬c1 ∧ ¬c0) ∨ = (¬c3 ∧ ∧ ¬c1 ∧ ¬c0)

secondo e terzo

secondo e quarto

formula semplificata

(¬c3 ∧ ¬c1 ∧ ¬c0) ∨ (¬c3 ∧ c2 ∧ ¬c1 ) ∨ (¬c3 ∧ c2 ∧ ∧ ¬c0) ∨ ( c3 ∧ ¬c2 ∧ ¬c1 )

si semplifica ancora, ma in un altro modo

( c3 ) ∨ ( ¬c1 ∧ ¬c0) ∨ ( c2 ∧ ¬c1 ) ∨ ( c2 ∧ c1 ∧ ¬c0)

valori degli input

0 … 9 ⇒ 0000 … 1001

i valori 1010 … 1111 non si possono presentare in ingresso

si può scegliere arbitrariamente se l'uscita vale 0 oppure 1

( c3 ) ∨ ( ¬c1 ∧ ¬c0) ∨ ( c2 ∧ ¬c1 ) ∨ ( c2 ∧ c1 ∧ ¬c0)

altri circuiti

• sommatore a tre ingressi
• confronto fra due interi
• circuito che sceglie un ingresso video fra due
• ascensore, segnalatori di piano e chiamata, uscite su e giù
• circuito a maggioranza fra 3, per sensori di allarme

sommatore a tre ingressi

prima uscita vera se:
¬a ∧ b ∧ c oppure a ∧ ¬b ∧ c oppure…

seconda uscita vera se:
¬a ∧ ¬b ∧ c oppure ¬a ∧ b ∧ ¬c oppure…

semplificazioni?

semplificazioni, dalla tabella

prima uscita vera se
a ∧ b ∧ ¬c oppure a ∧ b ∧ c

quindi a ∧ b

i due termini vengono dalla tabella

semplificazioni direttamente dalla tabella

dalla tabella:

a ∧ b ∧ ¬c

viene da 110

a ∧ b ∧ c

viene da 111

a ∧ b sono i primi due uno
¬c e c sono l'ultima cifra, 0 e 1

semplificazioni direttamente dalla tabella

regola:

se ci sono due uscite 1 per due righe che differescono di un solo bit
quel bit si elimina

altre semplificazioni

righe simili per prima uscita true:

• 011 e 111 ⇒ .11 ⇒ b ∧ c
• 101 e 111 ⇒ 1.1 ⇒ a ∧ b
• 011 e 111 ⇒ .11 ⇒ b ∧ c

prima e terza uguali, basta tenerne una

(a ∧ b) ∨ (b ∧ c)

sintesi di circuiti

mappe di Karnaugh

metodo manuale, comodo fino a quattro ingressi

metodo di Quine-McCluskey

algoritmo, anche molte variabili

mappe di Karnaugh

differente disposizione degli 0 e 1 della prima uscita

11 prima di 10 non è un errore!
garantisce che valori di ab simili sono vicini

metodo manuale
righe simili ⇒ caselle vicine
più facile trovare le semplificazioni

metodo di Quine-McCluskey

metodo automatizzabile

il problema teorico

data una funzione booleana,
ne esiste una più piccola per la stessa tabella?
se esiste trovarla

algoritmi veloci con poche variabili
rallentano quando le variabili sono tante

complessità computazionale:
quanto rallentano?

l'argomento verrà ripreso più avanti