# Efficient implementation of logic gates Classic List Threaded 5 messages Open this post in threaded view
|

## Efficient implementation of logic gates

 I was wondering which implementation of Or16 is more efficient. This one: ```CHIP Or16 { IN a, b; OUT out; PARTS: Or(a=a, b=b, out=out); Or(a=a, b=b, out=out); Or(a=a, b=b, out=out); Or(a=a, b=b, out=out); Or(a=a, b=b, out=out); Or(a=a, b=b, out=out); Or(a=a, b=b, out=out); Or(a=a, b=b, out=out); Or(a=a, b=b, out=out); Or(a=a, b=b, out=out); Or(a=a, b=b, out=out); Or(a=a, b=b, out=out); Or(a=a, b=b, out=out); Or(a=a, b=b, out=out); Or(a=a, b=b, out=out); Or(a=a, b=b, out=out); } ``` Or this one: ```CHIP Or16 { IN a, b; OUT out; PARTS: Not16(in=a, out=NOTa); Not16(in=b, out=NOTb); And16(a=NOTa, b=NOTb, out=NOTaAndNOTb); Not16(in=NOTaAndNOTb, out=out); } ``` Is it correct to say that since Or is built from 3 gates (not,not,nand), the first implementation has a total of 48 chips (3*16) so it is more efficient than the second, which has 64 chips total (16*4)?
Open this post in threaded view
|

## Re: Efficient implementation of logic gates

 Administrator You could also build a Nand16 to use in your second version and it would have the same Nand count as the first one. The thing to realize about gate counting is that 2-input Nand can be used to build any logic circuit, not that it must be used as the basic building block. Modern ICs (CMOS) can easily make Nor gates. Both require 4 transistors for 2-input gates, but for reasons of physics, Nand gates are smaller and therefore preferred. Even smaller, only 2 transistors, is a transmission gate which is like a logic controlled switch. They are very handy for building multiplexors. CMOS can also make more complex gates with small transistor counts. For instance and-or-invert not(a&b | c&d) is only 8 transistors, as is or-and-invert. Nand count does make a reasonable first order approximation for circuit complexity, just don't read too much into it. FWIW, I wrote a quick and dirty preprocessor for HDL. My Or16.hdlx consists of the single line     Or(a=a[#], b=b[#], out=out[#]; and the preprocessor replicates it 16 times. --Mark
Open this post in threaded view
|

## Re: Efficient implementation of logic gates

 Thank you for detailed answer. I would like to ask though, on the same note, about an implementation of Mux16, and also a question about HDL in general. Having read and understood your answer that I shouldn't read too much into it, I still have to think that some implementations are much more efficient than others, for example, this Mux16: ```CHIP Mux16 { IN a, b, sel; OUT out; PARTS: Not(in=sel, out=NOTsel); And16(a=a, b=NOTsel, b=NOTsel, b=NOTsel, b=NOTsel, b=NOTsel, b=NOTsel, b=NOTsel, b=NOTsel, b=NOTsel, b=NOTsel, b=NOTsel, b=NOTsel, b=NOTsel, b=NOTsel, b=NOTsel b=NOTsel, out=aAndNOTsel); And16(a=b, b=sel, b=sel, b=sel, b=sel, b=sel, b=sel, b=sel, b=sel, b=sel, b=sel, b=sel, b=sel, b=sel, b=sel, b=sel, b=sel, out=bAndSel); Or16(a=aAndNOTsel, b=bAndSel, out=out); } ``` Versus this Mux16: ```CHIP Mux16 { IN a, b, sel; OUT out; PARTS: Mux(a=a, b=b, sel=sel, out=out); Mux(a=a, b=b, sel=sel, out=out); Mux(a=a, b=b, sel=sel, out=out); Mux(a=a, b=b, sel=sel, out=out); Mux(a=a, b=b, sel=sel, out=out); Mux(a=a, b=b, sel=sel, out=out); Mux(a=a, b=b, sel=sel, out=out); Mux(a=a, b=b, sel=sel, out=out); Mux(a=a, b=b, sel=sel, out=out); Mux(a=a, b=b, sel=sel, out=out); Mux(a=a, b=b, sel=sel, out=out); Mux(a=a, b=b, sel=sel, out=out); Mux(a=a, b=b, sel=sel, out=out); Mux(a=a, b=b, sel=sel, out=out); Mux(a=a, b=b, sel=sel, out=out); Mux(a=a, b=b, sel=sel, out=out); } ``` In the second implementation, I had to use 16 Mux gate to deal with the single bit sel input. However in the first implementation, I just spread that one bit into 15 inputs, basically trading wire count for chip count, am I right? I also wanted to know if there is a shorter way to spread one bit into multiple bits, like I did in the first implementation with sel, something like: ```b[0..15]=sel or maybe b[]=sel ```