Come risolvere reti logiche con algoritmo Quine McCluskey

Tramite: O2O
Difficoltà: media
15

Introduzione

Parte importante dello studio delle Reti Logiche riguarda come risolvere il problema della sintesi delle reti combinatorie. Per farlo ci sono diversi metodi, uno di questi è l'algoritmo di Quine McCluskey. Esso permette di sintetizzare funzioni complesse, anche a più uscite, ed inoltre si presta benissimo ad essere utilizzato da un computer. L'algoritmo si divide in due fasi: espansione e copertura.

Andiamo a vederle una per una.

N. B. Per riuscire a capire al meglio gli argomenti si presuppone tu abbia chiari concetti come mintermine, implicante primo ed essenziale e distanza di Hamming.

25

Espansione - Prima parte

Prima di tutto dobbiamo trovare, se non ci sono stati già dati, tutti i mintermini della funzione. Dopodiché bisogna inserirli tutti in una tabella, raggruppandoli per numero di "1" che li compongono e ordinandoli in numero crescente di "1" (come in immagine). Ora bisogna confrontare ogni mintermine di un gruppo, con ogni mintermine del gruppo successivo.
Se hanno distanza di Hamming pari a 1, bisogna marcare entrambi, espandere ed ottenere un nuovo implicante. La variabile eliminata (cioè quella che differiva) viene sostituita dal simbolo di don't care (-).

35

Espansione - Seconda parte

Terminata la prima espansione, si costruisce allo stesso modo un'altra tabella, con i nuovi implicanti trovati e, con lo stesso procedimento, si cerca di espanderli. Bisogna ricordare che ulteriori raccoglimenti sono possibili solo se il simbolo di don't care si trova nella stessa posizione.
Si procede finché non sono possibili ulteriori espansioni.
Tutti gli implicanti che non sono stati marcati sono gli implicanti primi della funzione.
N. B.: è possibile che il procedimento porti ad avere lo stesso implicante più volte, in tal caso va considerato una volta sola.

Continua la lettura
45

Copertura

Siamo arrivati ora alla fase di copertura.
Anche in questo caso bisogna costruire una tabella, che si chiamerà "tabella di copertura". Essa avrà tante righe quanti sono gli implicanti e tante colonne quanti sono i mintermini.

In ogni casella (i, j) si inserisce una X se l'implicante Pi copre il mintermine Mj. Se in una colonna c'è solo una X, l'implicante che lo copre è essenziale. Si aggiunge quindi all'insieme di copertura e si eliminano tutte le colonne coperte da esso. Si elimina inoltre la riga dell'implicante. Nel caso in cui non ci siano implicanti essenziali si procede applicando due criteri: la dominanza di riga e la dominanza di colonna. Una riga "i" domina una riga "j" se l'implicante Pi copre tutti i mintermini che copre l'implicante Pj più almeno uno. La colonna "i" domina la colonna "j" se il mintermine Mj è coperto dagli stessi implicanti da cui è coperto Mi più almeno uno. In entrambi i casi la riga/colonna dominata può essere eliminata dalla tabella.

Si procede finché avremo svuotato la tabella.
Tutti gli implicanti trovati costituiranno l'insieme di copertura della funzione.

55

Consigli

Non dimenticare mai:
  • Il metodo è estremamente laborioso e meccanico. Può risultare noioso, ma non affrettare i calcoli e controlla sempre i risultati. Un solo errore all'inizio e sarà tutto da rifare!
Alcuni link che potrebbero esserti utili:

Potrebbe interessarti anche

Segnala contenuti non appropriati

Tipo di contenuto
Devi scegliere almeno una delle opzioni
Descrivi il problema
Devi inserire una descrizione del problema
Si è verificato un errore nel sistema. Riprova più tardi.
Verifica la tua identità
Devi verificare la tua identità
chiudi
Grazie per averci aiutato a migliorare la qualità dei nostri contenuti

Guide simili

Programmazione

Come programmare un algoritmo in C++

Il c++ è un linguaggio creato da Bjarne Stroustrup nel 1983, uno strumento per la programmazione ad oggetti che si basa sullo sviluppo del linguaggio C (a sua volta progettato per sfruttare al massimo le caratteristiche dell'hardware). In questo modo,...
Programmazione

Come creare un algoritmo con Excel

Il pacchetto Office di casa Microsoft ci ha sempre aiutato a realzzare diversi tipi di progetti, sia per lavoro che per altre destinazioni. Grazie ai programmi appartenenti alla suite, si possono difatti organizzare grafici, presentazioni, testi, raccolte...
Programmazione

Programma c++ per risolvere equazioni di secondo grado

Il linguaggio di programmazione C++ è stato inventato da Bjarne Stroustrup sulla base di quello C, sviluppato, invece, da Dennis Ritchie. Esso presenta un'ampia gamma di funzionalità e si presta benissimo a diverse applicazioni, come la risoluzione...
Programmazione

Come utilizzare al meglio Fortran

Il linguaggio Fortran è un linguaggio di programmazione utilizzato dai matematici principalmente per risolvere problemi computazionali come ad esempio equazioni differenziali. Esso infatti semplifica il linguaggio aritmetico che viene comunemente utilizzato....
Programmazione

Regole per progrmmare in Axum

Microsoft ha stilato un nuovo progetto denominato Axum. Di cosa si tratta? Axum si pone l'obiettivo di creare un moderno ed avveniristico linguaggio per consentire a tutti gli utenti di creare in modo semplice e veloce applicazioni parallele di software...
Programmazione

Come programmare in Axum

Con la realizzazione di Axum, è stato originato un linguaggio strutturato in maniera tale da rendere maggiormente semplice la programmazione simultanea e sicura. Ma di cosa si tratta? Innanzitutto occorre chiarire l'obiettivo di questo progetto: quello...
Programmazione

Come programmare al meglio in MIPS

Un evento che ha influito molto sui giorni nostri è sicuramente la rivoluzione industriale. Proprio grazie ad essa si sono sviluppati diversi programmi molto utili, adatti a semplificare le tante cose che noi svolgiamo nella vita quotidiana, i diversi...
Programmazione

Come ordinare una lista in Java

Java in campo informatico rappresenta senza dubbio uno dei sistemi di programmazione più diffusi e conosciuti. Ordinare una lista in Java potrebbe sembrare un'operazione piuttosto complicata, in modo particolare per i meno esperti del settore. In realtà...
I presenti contributi sono stati redatti dagli autori ivi menzionati a solo scopo informativo tramite l’utilizzo della piattaforma www.o2o.it e possono essere modificati dagli stessi in qualsiasi momento. Il sito web, www.o2o.it e Arnoldo Mondadori Editore S.p.A. (già Banzai Media S.r.l. fusa per incorporazione in Arnoldo Mondadori Editore S.p.A.), non garantiscono la veridicità, correttezza e completezza di tali contributi e, pertanto, non si assumono alcuna responsabilità in merito all’utilizzo delle informazioni ivi riportate. Per maggiori informazioni leggi il “Disclaimer »”.