# Sintesi reti combinatorie Obiettivo? Ridurre complessitá di reti combinatorie. Metodologie di sintesi: - Karnaugh - Quine-Mc Cluskey ## Karnaugh Basically formula di riduzione $az + a'z = z$ applicato in maniera grafica. ### Distanza di Hamming > "The purpose of computation is insight, not numbers" > - Richard Hamming La distanza di Hamming è il numero di bit che cambiano tra due numeri espressi in binario. La regola di riduzione consiste nel identificare i termini che hanno distanza di Hamming unitaria. Karnaugh segue un procedimento grafico, basato su una tabella. La tabella é come se fosse infinita, cioé la prima riga in alto segue l'ultima riga in basso, la prima colonna a sinistra segue l'ultima colonna destra. Le colonne differiranno per una unitá sulla distanza di Hamming, esempio a due dimensioni: 00, 01, 11, 10 ; Due tipi di implicanti: - **Implicante primo** = raggruppamento massimo di uni. - **Implicante primo essenziale** = implicante primo unico (tra tutti gli implicanti primi) a coprire uno specifico uno.  Divido l'algoritmo in 2 fasi principali: - l'**espansione** in cui identifico gli implicanti e gli implicanti essenziali. - la **copertura**, cioé scelta del minor numero di implicanti primi. Chiaramenti dovró per forza prendere quelle essenziali, in quanto al termine di questa fase non ci dovranno essere 1 scoperti. Potremmo utilizzare i simboli di _don't care_ "-" per indicare bit che non ci interessano. Come trattiamo i DC? all'inizio come se fossero 1 (espansione), poi dopo (copertura) come se fossero 0. Quando utilizziamo i DC? ad esempio quando in una rete combionatoria non é osservabile sotto certe configurazioni o non é necessario calcolarne la funzione. Karnugh viene utilizzato con poche variabili, di piú dovremmo ricorrere a piú dimensioni .. cioé piú tabelle. ## Metodo di Quine McCluskey In sostanza é come Karnaugh ma utilizzando solo tabelle e 'skippando' l'uso di un metodo grafico, concentrandosi su un metodo tabulare. Passaggi risolutivi sono: 1. Riordino dei mintermini. 2. Si notano i mintermini non marcati (di conseguenza non sono implicanti primi). 3. Successivamente si possono trovare le configurazioni non marcate; questi costituiscono degli implicanti primi. 4. Si passa alla tabella di copertura. 5. Si cerca di ridurre la tabella di copertura, notando che alcune colonne hanno una sola marca: sono gli **implicanti essenziali**. Di conseguenza applico tutte le regole di dominanza*. 7. La tabella di copertura ridotta e’ vuota, è una copertura minima e (magari) unica. ### Dominanza La 'dominanza' esiste di due tipi: - **Dominanza di riga**: $P_i$ domina $P_j$ sse copre almeno i termini di $P_j$ e il costo di $P_j$ é maggiore o uguale a quello di $P_i$. Rimuovo quindi tutta la riga dominata mantenendo la dominante. - **Dominanza di colonna**: quando la copertura di un mintermine induce la copertura di un altro mintermine. Quella piú scomoda da imparare. Rimuovo quindi la copertura del mintermine dominato. Il senso è 'mantengo solo la colonna del mintermine il quale sono sicuro, coprendolo, implica anche la copertura del mintermine corrispondente alla colonna eliminata'. ### McCluskey con funzioni non completamente specificate Fai come al solito e arrivato alla tabella di copertura non consideri affatto il mintermine del $DC_{set}$ (Don't Care Set).