Mappa di Karnaugh
Ho controllato la sezione 3 del regolamento e non mi sembra faccia riferimento ad un numero massimo di messaggi in un certo intervallo di tempo, quindi chiedo:
Come si fa a scegliere i quadrati migliori nella k-mappa? Ad esempio prendo quella spiegata su wiki: link e disegno la mappa più volte per evidenziare che si tratta di un toroide.
0 0 1 1 0 0 1 1 0 0 1 1
0 0 1 1 0 0 1 1 0 0 1 1
0 0 0 1 0 0 0 1 0 0 0 1
0 1 1 1 0 1 1 1 0 1 1 1
0 0 1 1 0 0 1 1 0 0 1 1
0 0 1 1 0 0 1 1 0 0 1 1
0 0 0 1 0 0 0 1 0 0 0 1
0 1 1 1 0 1 1 1 0 1 1 1
0 0 1 1 0 0 1 1 0 0 1 1
0 0 1 1 0 0 1 1 0 0 1 1
0 0 0 1 0 0 0 1 0 0 0 1
0 1 1 1 0 1 1 1 0 1 1 1
Perché su wiki si fa quella particolare scelta? Ad esempio, io avrei considerato anche la coppia \((14,10)\) (da qui link) in quanto la regola dice di scegliere i quadrati più grandi che siano potenze di \(2\) quindi \(2^{0},2^{1},...\):
Ma non dice di scegliere il numero minimo di quadrati che siano potenze di due. Ancora, non capisco gli esempi sotto. Ad esempio il primo img. Se la corrispondenza è
AB
0 00 \(\overline{A}\overline{B}\)
1 01 \(\overline{A}B\)
2 10 \(A\overline{B}\)
3 11 \(AB\)
La funzione è indicata come \(\Sigma(0)\Rightarrow F=\overline{A}\overline{B}\) ed io avrei indicato la mappa
con la tabella
10
00
Dove sbaglio?
Come si fa a scegliere i quadrati migliori nella k-mappa? Ad esempio prendo quella spiegata su wiki: link e disegno la mappa più volte per evidenziare che si tratta di un toroide.
0 0 1 1 0 0 1 1 0 0 1 1
0 0 1 1 0 0 1 1 0 0 1 1
0 0 0 1 0 0 0 1 0 0 0 1
0 1 1 1 0 1 1 1 0 1 1 1
0 0 1 1 0 0 1 1 0 0 1 1
0 0 1 1 0 0 1 1 0 0 1 1
0 0 0 1 0 0 0 1 0 0 0 1
0 1 1 1 0 1 1 1 0 1 1 1
0 0 1 1 0 0 1 1 0 0 1 1
0 0 1 1 0 0 1 1 0 0 1 1
0 0 0 1 0 0 0 1 0 0 0 1
0 1 1 1 0 1 1 1 0 1 1 1
Perché su wiki si fa quella particolare scelta? Ad esempio, io avrei considerato anche la coppia \((14,10)\) (da qui link) in quanto la regola dice di scegliere i quadrati più grandi che siano potenze di \(2\) quindi \(2^{0},2^{1},...\):
The minterms ('minimal terms') for the final expression are found by encircling groups of 1s in the map. Minterm groups must be rectangular and must have an area that is a power of two (i.e. 1, 2, 4, 8…). Minterm rectangles should be as large as possible without containing any 0s. Groups may overlap in order to make each one larger.
Ma non dice di scegliere il numero minimo di quadrati che siano potenze di due. Ancora, non capisco gli esempi sotto. Ad esempio il primo img. Se la corrispondenza è
AB
0 00 \(\overline{A}\overline{B}\)
1 01 \(\overline{A}B\)
2 10 \(A\overline{B}\)
3 11 \(AB\)
La funzione è indicata come \(\Sigma(0)\Rightarrow F=\overline{A}\overline{B}\) ed io avrei indicato la mappa
con la tabella
10
00
Dove sbaglio?
Risposte
Ciao dal momento che non riesco a capire le mappe che hai scritto manualmente ti faccio io un esempio:
Supponiamo tu voglia sintetizzare una funzione combinatoria di $4$ variabili binarie con sintesi canonica $SP$ partendo dalla mappa di Karnaugh (riscrittura della tabella di verità della funzione $F$).
Sostituisco la soprasegnatura con un "punto esclamativo" che precede la variabile ($!b=bar b$) in quanto farla era un delirio.
L'idea è questa:
vogliamo ottenere $F$ come una somma (logica) di implicanti primi essenziali (ovvero termini prodotto particolari).
-Un implicante è un termine prodotto che assume $1$ solo quando la funzione $F$ assume il valore $1$.
Per ora niente di strano, per fare questo di basterebbe cerchiare tutti gli "$1$" e costruirti i mintermini corrispondenti.
-Un implicante primo è un implicante a cui non si può più aggiungere altro (ovvero è ottimizzato).
Per questo ti basta cerchiare i gruppi di "$1$" considerando le adiacenze più grandi possibili in modo che i gruppi siano potenze di $2$.
-Un implicante primo essenziale è un implicante primo che assume solo lui "$1$" per certe configurazioni delle variabili di ingresso.
Per fare questo devi semplicemente verificare che gli tutti gli $1$ siano coperti e ogni cerchio abbia almeno un $1$ che copre solo lui.
Fatto questo per ogni gruppo guardi quali sono le variabili che rimangono costanti:
- se rimangono costanti in positivo allora prendi il loro valore vero.
- se rimangono costanti in negativo allora prendi il loro valore negato.
Esempio:
In figura le frecce indicano i gruppi che devi cerchiare e che sono implicanti primi essenziali. Verifica che rispettino le definizioni che ho scritto sopra.
Consideriamo il gruppo(cerchio) rosso: le variabili costanti sono $d$ e $b$ e sono entrambe costanti a $0$, perciò prendo il loro valore negato: $!b.!d$.
Cosa vuol dire $F=!b.!d$ + .... ??
Vuol dire che se $b=0 ^^ d=0$ (quindi $!b.!d = !0.!0 = 1.1=1$) la funzione $F$ vale $1$. Basta guardare la tabella per convincertene.
Spero di essere stato chiaro
Supponiamo tu voglia sintetizzare una funzione combinatoria di $4$ variabili binarie con sintesi canonica $SP$ partendo dalla mappa di Karnaugh (riscrittura della tabella di verità della funzione $F$).
Sostituisco la soprasegnatura con un "punto esclamativo" che precede la variabile ($!b=bar b$) in quanto farla era un delirio.
L'idea è questa:
vogliamo ottenere $F$ come una somma (logica) di implicanti primi essenziali (ovvero termini prodotto particolari).
-Un implicante è un termine prodotto che assume $1$ solo quando la funzione $F$ assume il valore $1$.
Per ora niente di strano, per fare questo di basterebbe cerchiare tutti gli "$1$" e costruirti i mintermini corrispondenti.
-Un implicante primo è un implicante a cui non si può più aggiungere altro (ovvero è ottimizzato).
Per questo ti basta cerchiare i gruppi di "$1$" considerando le adiacenze più grandi possibili in modo che i gruppi siano potenze di $2$.
-Un implicante primo essenziale è un implicante primo che assume solo lui "$1$" per certe configurazioni delle variabili di ingresso.
Per fare questo devi semplicemente verificare che gli tutti gli $1$ siano coperti e ogni cerchio abbia almeno un $1$ che copre solo lui.
Fatto questo per ogni gruppo guardi quali sono le variabili che rimangono costanti:
- se rimangono costanti in positivo allora prendi il loro valore vero.
- se rimangono costanti in negativo allora prendi il loro valore negato.
Esempio:
In figura le frecce indicano i gruppi che devi cerchiare e che sono implicanti primi essenziali. Verifica che rispettino le definizioni che ho scritto sopra.
Consideriamo il gruppo(cerchio) rosso: le variabili costanti sono $d$ e $b$ e sono entrambe costanti a $0$, perciò prendo il loro valore negato: $!b.!d$.
Cosa vuol dire $F=!b.!d$ + .... ??
Vuol dire che se $b=0 ^^ d=0$ (quindi $!b.!d = !0.!0 = 1.1=1$) la funzione $F$ vale $1$. Basta guardare la tabella per convincertene.
Spero di essere stato chiaro
Eh, non capisco bene il criterio con il quale scegli i quadrati. Ad esempio perché il blocco \((00,11),(00,10)\) invece di \((00,11)\) e basta (ovvero perché tutto il rettangolo blu e non solo il primo quadrato)? Oppure dall'esempio principale della pagina di wikipedia, perché non considera la coppia \((11,10),(10,10)\)? [url=http://it.wikipedia.org/wiki/File:K-map_6,8,9,10,11,12,13,14.svg]img[/url] Il resto del meccanismo mi sembra chiaro.
In entrambi i casi perchè otterresti implicanti non primi ovvero non ottimizzati (riguarda la definizione), vediamo nei tuoi due casi:
${(00,11)}$ può essere espanso con ${(00,11),(00,10)}$ quindi $(00,11)$ non è un implicante primo.
Attenzione: visto che $(00,10)$ sarebbe comunque coperto dall'implicante primo essenziale blu $!a.!b.c$ la rete sintetizzata sarebbe comunque corretta (cioè si comporta logicamente correttamente) ma non sarebbe una rete di costo minimo! (ovvero non è quello che volevamo)!!
Perchè è già coperto dal gruppo verde!
Il gruppo: ${(11,10),(10,10)}$ può essere espanso (diventerebbe il gruppo verde) e dunque è un implicante non primo.
Inoltre gli $1$ coperti da lui sarebbero già coperti dal verde quindi non è neanche essenziale!
"5mrkv":
Ad esempio perché il blocco \((00,11),(00,10)\) invece di \((00,11)\) e basta (ovvero perché tutto il rettangolo blu e non solo il primo quadrato)?
${(00,11)}$ può essere espanso con ${(00,11),(00,10)}$ quindi $(00,11)$ non è un implicante primo.
Attenzione: visto che $(00,10)$ sarebbe comunque coperto dall'implicante primo essenziale blu $!a.!b.c$ la rete sintetizzata sarebbe comunque corretta (cioè si comporta logicamente correttamente) ma non sarebbe una rete di costo minimo! (ovvero non è quello che volevamo)!!
"5mrkv":
Oppure dall'esempio principale della pagina di wikipedia, perché non considera la coppia \((11,10),(10,10)\)? [url=http://it.wikipedia.org/wiki/File:K-map_6,8,9,10,11,12,13,14.svg]img[/url]
Perchè è già coperto dal gruppo verde!
Il gruppo: ${(11,10),(10,10)}$ può essere espanso (diventerebbe il gruppo verde) e dunque è un implicante non primo.
Inoltre gli $1$ coperti da lui sarebbero già coperti dal verde quindi non è neanche essenziale!
"lordb":Giusto.
In entrambi i casi perchè otterresti implicanti non primi ovvero non ottimizzati (riguarda la definizione), vediamo nei tuoi due casi:
${(00,11)}$ può essere espanso con ${(00,11),(00,10)}$ quindi $(00,11)$ non è un implicante primo.
Attenzione: visto che $(00,10)$ sarebbe comunque coperto dall'implicante primo essenziale blu $!a.!b.c$ la rete sintetizzata sarebbe comunque corretta (cioè si comporta logicamente correttamente) ma non sarebbe una rete di costo minimo! (ovvero non è quello che volevamo)!!
Perchè è già coperto dal gruppo verde!
Il gruppo: ${(11,10),(10,10)}$ può essere espanso (diventerebbe il gruppo verde) e dunque è un implicante non primo.
Inoltre gli $1$ coperti da lui sarebbero già coperti dal verde quindi non è neanche essenziale!
Non \((10,11),(10,10)\) ma $(11,10),(10,10)$. Voglio dire perché non posso prendere anche un quadretto da due fra blu e verde?
Esercizio: Realizzare la seguente funzione logica di quattro variabili \(A,B,C,D\) usando un multiplexer con tre linee di indirizzo (o selezione).
ABCD
1010
1011
1101
1110
0001
0010
0100
0101
0110
0111
1000
1001
Questi danno uno nella tabella logica della funzione \(F\) che viene realizzata. Tutti gli altri casi danno zero. Mettendo in tabella con ascisse \(AB\) e ordinata \(CD\) ottengo
\[
\begin{bmatrix}
0&1&0&1 \\
1&1&1&1 \\
0&1&1&1 \\
1&1&0&1 \\
\end{bmatrix}
\]
Che posso raccogliere come
\[
\begin{bmatrix}
0&1&0&1 \\
X&X&X&X \\
0&1&1&1 \\
1&1&0&1 \\
\end{bmatrix}
+
\begin{bmatrix}
0&X&0&1 \\
1&X&1&1 \\
0&X&1&1 \\
1&X&0&1 \\
\end{bmatrix}
+
\begin{bmatrix}
0&1&0&X \\
1&1&1&X \\
0&1&1&X \\
1&1&0&X \\
\end{bmatrix}
+
\begin{bmatrix}
0&1&0&1 \\
1&1&1&1 \\
0&1&1&1 \\
X&X&0&1 \\
\end{bmatrix}
+
\begin{bmatrix}
0&1&0&1 \\
1&1&X&X \\
0&1&X&X \\
1&1&0&1 \\
\end{bmatrix}
\]
Quindi
\[
F=\overline{C}D+\overline{A}B+A\overline{B}+\overline{A}C\overline{D}+AD
\]
Per la parte sul multiplexer, conosco solo il decoder-demultiplexer. Non capisco però come conciliarlo con la richiesta. Ad esempio considero un decoder a due uscite
\[
\begin{split}
F_{0}=\overline{A}\overline{B} \\
F_{1}=\overline{A}B
\end{split}
\]
Da \(1\) sulla prima linea zero se gli danno \(00\), mentre da \(1\) sulla linea uno solo se gli danno \(01\), quindi decodifica i numeri binari. Se metto un \(\mbox{or}(F_{1},F_{2})\) ed aggiungo due variabili in più sugli and ottengo
\[
\begin{split}
F_{0}=X_{1}\overline{A}\overline{B} \\
F_{1}=X_{2}\overline{A}B
\end{split}
\]
E dando ad esempio \(AB=00\) scelgo di trasmettere solo il segnale binario \(X_{0}\).
"5mrkv":
Non \((10,11),(10,10)\) ma $(11,10),(10,10)$. Voglio dire perché non posso prendere anche un quadretto da due fra blu e verde?
"lordb":
-Un implicante primo essenziale è un implicante primo che assume solo lui "$1$" per certe configurazioni delle variabili di ingresso.
Per fare questo devi semplicemente verificare che gli tutti gli $1$ siano coperti e ogni cerchio abbia almeno un $1$ che copre solo lui.
Sono sicuro che ci arrivi
"5mrkv":
Realizzare la seguente funzione logica di quattro variabili $A,B,C,D$ usando un multiplexer con tre linee di indirizzo (o selezione).
Guarda un multiplexer è un simpatico aggeggio che ha $n$ segnali di controllo che pilotano i $2^n$ segnali in ingresso verso una sola uscita. Quindi se hai $3$ segnali di controllo il multiplexer potenzialmente ha $5<=n<=8$ ingressi (altrimenti non ha senso usarne uno con $3$ segnali di controllo!).
Comunque sia ora non mi viene in mente come usarlo.
Argh, non riuscivo ad interpretare la frase. Ho capito.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo