Porta XOR con 4 porte NAND

[ezio1400]

Salve a tutti,
stavo studiano come costruire da una funzione logica un circuito con sole porte NAND e mi sono imbattuto nella funzione della porta XOR. Prima di sbirciare la soluzione del circuito ho provato a costruirla da me. Nella soluzione ho utilizzato 5 porte NAND. Guardando la soluzione ho visto che era formata da sole 4 porte NAND. Pensando fosse sbagliata o girovagato per internet trovando la mia soluzione con 5 porte NAND, la prima mostrata qui http://i.stack.imgur.com/8kmj4.gif.
La mia domanda è se esiste qualche metodo che permette da una funzione logica di costruire il circuito con un numero di porte NAND che sia il MINIMO, oppure se invece la soluzione ottimale derivi da esperienza e tentativi.
Grazie.

[harpefalcata]

La riduzione delle equazioni nell'algebra di boole è costituita in larga parte dall'esperienza del progettista, nel senso che non esiste un algoritmo di riduzione ottima per questo ambito.

Tieni comunque presenteche le reti logiche, stanno cominciando a perdere utilità, in quanto ora tutte le combinazioni logiche sono risolte da microcontrollori od FPGA, che sempre più prendono piede.

Resta comunque un ottimo esercizio accademico.

[spummel]

Scusate l'intrusione.
harpefalcata perch dici che le reti logiche sono sostituite dai microcontrollori?
Non sono essi stessi formati da porte logiche?

[Brianz]

Non ci sono formule specifiche: si tratta di utilizzare le regole dell'algebra di Boole e i teoremi connessi. Per minimizzare occorre sia una conoscenza di questi che delle funzioni disponibili, in quanto lo scopo non è solamente teorico, ma è quello di ottimizzare il numero degli integrati necessari. Così, si può avere un XOR anche con 3 gates, ma si tratta di un AND, un NAND e un OR che nella pratica richiedono la presenza di 4 ic dversi, mentre 4 NAND sono contenute in un solo package (es. 7400).

Se tieni presenti :
!(!A) = A
!A A = 0
!(A + B) = !A !B
!(AB) = !A + !B
!(AB) = AB
de Morgan !(A + B) = !A !B

A xor B = A!B + B!A (definizione)
=!((!A+B)(A+!B)
=!( (!(A(!A+!B)) (!(B(!A+!B) )

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

se&o

[Brianz]

Dire che microcontrollori sono formati da porte logiche è meno corretto che dire che sono formati da transistor.

Gate logici discreti, genere CMOS 40xx o TTL 74xx sono una cosa: si tratta di funzioni che svolgono una ben determinata azione e solo quella.
I microcontroller sono dispositivi a logica programmata, che è ben diverso. Le funzioni logiche sono eseguite da una ALU, non da pezzi separati (anche se integrati su un unico supporto).

Intermedi tra i due precedenti, si trovano FPGA (field programmable gate array) che sono, come dice il nome, array di gate. Qui possiamo intendere che ci siano reali "gates", a cui si aggiunge una programmabilità. Si tratta però di una programmabilità diversa da quella dei microcontroller, dato che non esistono istruzioni e neppure una ALU; si tratta di una matrice di blocchi logici configurabili (CLB) in cui la programmazione modifica le interconnessioni reciproche.

[ezio1400]

Edit: Non usare il tasto cita, usa il tasto rispondi per rispondere normalmente.

Il procedimento che tu mi hai mostrato l'ho già visto e l'ho capito. Il problema era il fatto che quando ho proposto la mia soluzione ovviamente pensavo che fosse ottimale invece non era cosi. Volevo solo sapere se la soluzione corretta e ottimizzata derivi esclusivamente da tentativi e/o esperienza oppure c'è qualche logica da seguire. Probabilmente ora se mi viene data una funzione logica da "tramutare" in circuito con porte logiche NAND fare dei tentativi prima di andare dritto spedito come fatto con la funzione logica della porta XOR. Per arrivare dalla definizione della funzione logica XOR alla funzione che minimizza il numero di porte NAND per implementarla penso sia stata raggiunta con dei tentativi o sbaglio?

[Brianz]

Come ho detto, non esiste, mi pare, una formula generale per minimizzare questi casi.
Certamente attraverso teoremi e mappe si può arrivare anche in via puramente teorica, ma non con una formula, piuttosto parlerei di un metodo.

Ma se come "tentativi" intendi una cosa del genere try&error (volgare, andare a caso) non penso proprio che il primo che ha sviluppato questa soluzione abbia percorso questa strada.
La faccenda, a mio parere, è molto meno semplice.
Innanzitutto, per fare qualcosa occorre una motivazione, vuoi una pura curiosità teorica, vuoi, come detto, la necessità di minimizzare o sfruttare a pieno gli ic che compongono una certa logica.
Chi ha progettato qualcosa all'epoca d'oro dei TTL & CMOS, sicuramente è stato afflitto dall'obbligo "morale" di non lasciare gate inutilizzati; tanto da arrivare ad usare ff come inverter o, appunto, realizzare gate di un tipo come array di gate di altro tipo.
Secondo, occorre una profonda conoscenza dell'argomento (senza questa,allora si che, sicuramente, si va solo a caso).
Per fare di un ff un inverter o usare dei gate come ff o fare una funzione con gate di altre funzioni occorre avere una chiara idea di come operano.
Suppongo, quindi, che l'ideatore ci sia arrivato in un mix di varie cose e non con una formula magica.

Il fatto che non esista una formulazione unica per "minimizzare" deriva dal fatto che che si può arrivare ad una soluzione in diverse vie; nel caso del XOR abbiamo visto che si possono usare 5 o 4 NAND, ma non è una "minimizzazione", se non in relazione al fatto che usiamo un gate di un solo tipo (e che, all'atto pratico, ci sono 4 NAND a due ingressi in un package). perché abbiamo detto che una vera "minimizzazione" del numero di
gate ne richiede solo 3, ma di tipo diverso.

A mio parere, esaurito l'aspetto del divertissement logico, che è comunque un ottimo esercizio di conoscenza e della logica booleana e della sua algebra, c'è da considerarne l'utilità effettiva.
Sicuramente, attraverso il divertissement si apprende anche solo che esiste la possibilità di ottenere una funzione booleana attraverso l'uso di altre funzioni, cosa che si trova supportata direttamente e rappresentata chiaramente in termini matematici dai vari teoremi e regole.
Questo può venire utile nel momento in cui si debba progettare un circuito utilizzando i componenti reali resi disponibili dal mercato.

Comunque, a mio parere, esiste certamente la possibilità di realizzare un programma per PC che permetta di "automatizzare" queste minimizzazioni, dato che si tratta di combinazioni di un numero finito di elementi.
Il problema è che si tratterebbe di una cosa di limitata utilità, dato che da tempo l'impiego di logiche estese in TTL o CMOS è stato soppiantato dalle logiche programmabili.

[Stokes]

Gate logici discreti, genere CMOS 40xx o TTL 74xx sono una cosa: si tratta di funzioni che svolgono una ben determinata azione e solo quella.
I microcontroller sono dispositivi a logica programmata, che è ben diverso. Le funzioni logiche sono eseguite da una ALU, non da pezzi separati (anche se integrati su un unico supporto).

E di cosa sono fatte le ALU?

[Flamber]

Penso che Brianz intendesse che, ormai, nessuno progetta nulla con mappe di karnaugh e teoremi vari. Tutto viene ottimizzato dagli IDE, meglio di quanto possa fare qualsiasi essere umano. Scrivi il circuito in VHDL, e a fare il resto ci pensa Quartus (Xilinx ecc.). Poi chiaramente ci vuole anche chi scriva i programmi di ottimizzazione, ma questo è un altro discorso.

Ma non si può negare, che nessun ingegnere, oggi, si può sognare di progettare qualcosa di serio lavorando sulle singole porte logiche, se non per applicazioni molto particolari. l'80% dei progettisti di sistemi embedded lavora in C.

Chi invece scrive circuiti in VHDL, visti i potenti algortimi di ottimizzazione, ormai utilizza sempre più un approccio "behavioral" invece che strutturale.

[Brianz]

Esattamente.

Dire che una ALU è composta da gate logici è una visione naif. E' molto meno corretto che dire che è composta da transistor. Tutti i gate logici, le ALU, gli operazionali, le GPU sono composti da transistor; questo vuol dire che progettiamo tenendo come base il transistor e i problemi di polarizzazione? Organizziamo uno ad uno milioni di transistor su un solo chip, raccogliendoli in NAND e XOR e poi queste in macro funzioni?

Certamente ci sono i transistor, ma questo non ha niente a che fare direttamente con transistor e funzioni TTL o CMOS come i 7400 o i 4001. Ne tanto meno il progettista usa mappe di karnaugh o sostituisce xor con nand.

Personalmente, nel secolo scorso, ho partecipato alla realizzazione di un sistema logico con componenti discreti. Ne è venuto fuori un armadio rack da 40U con molte, molte decine di schede europa e molte, molte centinaia di TTL e con un consumo di più 200A. La realizzazione commerciale della funzione è risultata una coppia di chip DIP con qualche decina di mA di consumo!

Proprio perché, come dice flamber, si parte da presupposti completamente diversi. La complessità di queste strutture non si può più seguire "a mano": occorre un supporto da parte di cad specifici. E non solo per la parte logica.

Questo non toglie che occorra conoscere NAND, XOR, latch, ecc., né tanto meno che il progettista non conosca i principi dell'algebra booleana, dato che gli LSI non nascono dal nulla, ma come ogni progresso tecnologico, derivano dal perfezionamento di fasi precedenti, la conoscenza dei quali facilità l'evoluzione.

Per curiosità, ad esempio, potrebbe essere interessante sapere che si faceva riferimento ai NAND in quanto era la funzione più semplicemente realizzabile in forma di integrato.