wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> How Many Logic Functions (II)
        
(Message started by: Mike_V on Oct 3^rd, 2003, 1:16am)

Title: How Many Logic Functions (II)
Post by Mike_V on Oct 3^rd, 2003, 1:16am

Hope you don't mind me expanding on your topic title (from the easy section).

So, you have a large number of possible logic functions with 5 boolean variables. How many of those function are essential? That is, how many functions are necessary so that using only those functions you can generate all possible functions?

Sorry if this is unclear. I'll give a 2 variable example.

Three (of the 16) functions with 2 boolean variables are:

a b|f ₁ f₂ f₃
T T| T F F
T F| F T T
F T| F F T
F F| F T T

Here it is apparent that f₃(a,b) = f₂(f₁(a,b),f₁(a,b)). Thus you can generate f₃ from the other two, so it is not necessary if you already have f₁ and f₂.

So, how many functions (and which ones) are essential in 5-variables? K-variables?

Title: Re: How Many Logic Functions (II)
Post by BNC on Oct 3^rd, 2003, 1:36am

I beleive [hide]a single function[/hide] is required for all K.

Title: Re: How Many Logic Functions (II)
Post by towr on Oct 3^rd, 2003, 2:31am

I think BNC is right. [hide]You can make any arity function from one two-arity function, notably NAND or NOR, if I recall correctly..)[/hide]

Title: Re: How Many Logic Functions (II)
Post by william wu on Oct 3^rd, 2003, 11:32am

[hide]Yes, 2-input NAND and 2-input NOR are universal, because you can make the functions AND, OR, and NOT using only NANDs (or NORs), and every Boolean function can be represented using ANDs, ORs, and NOTs. (The set of operators {AND, OR, NOT} is thus called functionally complete.) Thus if I recall correctly, most technology nowadays is built out of NAND gates.

Maybe someone will be inclined to prove that you can make AND, OR, and NOT out of NANDs -- actually that was an interview question I once saw nVidia give during a career fair. As for me I'm going to lunch.
[/hide]

Title: Re: How Many Logic Functions (II)
Post by BNC on Oct 3^rd, 2003, 3:14pm

on 10/03/03 at 11:32:29, william wu wrote:

Thus if I recall correctly, most technology nowadays is built out of <hidden> gates.

Not quite. Some years back, ASIC (application specific integrate circuit) technology had the "gate array" (GA) or "sea of gates" that where just many many [hide]NAND[/hide] gates.
Today, the popular ASIC (term used in the wide sense) are (simplified):
- PAL (programmable array of logic) are basically "standard" complex function (actual function depends upon specific component), with selectable inputs.
- FPGA (field-programable GA) are RAM lookup table-based
- Standard cell devices have a library of common functions optimised at the silicon level
- Full custom devices work in the single transistor level.

Quote:

Maybe someone will be inclined to prove that you can make AND, OR, and NOT out of <hidden>

OK::[hide]
NOT(A) = NAND (A, A)
AND (A, B) = NOT( NAND (A, B))
and utilizing De-Morgan's rule:
OR(A,B) = NAND( NOT(A), NOT(B))
[/hide]

In he original question, to finish the "proof", we need to show that [hide]a two-input NAND (for example) may be obtained from a K-input NAND[/hide], but that's trivial by [hide]shortening (K-1) inputs togeter[/hide]
The fact its possible to [hide]create K-input functions (K>2) from 2-input functions[/hide] is actually by-definition in the case of [hide]primitive (basic) functions[/hide].

Title: Re: How Many Logic Functions (II)
Post by towr on Oct 4^th, 2003, 11:01am

on 10/03/03 at 11:32:29, william wu wrote:

Thus if I recall correctly, most technology nowadays is built out of <hidden> gates.

It's much too inefficient to do that, XOR for instance has a much, much more efficient implementation. Specialized subcircuits can safe a lot of time, energy in computation and space and connection-problems in chip-manufacturing.

Title: Re: How Many Logic Functions (II)
Post by william wu on Oct 6^th, 2003, 1:39am

on 10/04/03 at 11:01:09, towr wrote:

The most efficient CMOS implementation of NAND I know of uses 4 transistors: 2 PMOS in parallel and 2 NMOS in series.

I've only seen XOR made from six CMOS transistors, but according to this google search result http://www.ap-asic.org/2000/proceedings/2-2.pdf there are 4 transistor implementations for single-rail inputs, which is the most efficient implementation as of the year 2000. (Which to me begs the question, why was it not until the year 2000 that someone figured out how to make XOR from 4 transistors with single-rail inputs? It seems like there's only so many ways to hook up a small number of transistors, I would've thought all the possibilities had been explored long ago -- if not by analytical methods, then by brute force. I'm not a circuits guy though, so maybe someone could explain to me why this is hard.) I couldn't find what the most efficient implementation is for double-rail.

The double-rail vs. single-rail distinction is new material to me, but if I understand it correctly, the NAND implementation with 4 CMOS transistors is also single-rail, since it doesn't assume that complements of the inputs exist. Thus the transistor count is 4 for both XOR and NAND, which makes me wonder how XOR can have a "much, much more efficient implementation". (Maybe in the double-rail comparisons for which I could find no information?)

Attachment: NAND in CMOS

Title: Re: How Many Logic Functions (II)
Post by towr on Oct 6^th, 2003, 5:37am

on 10/06/03 at 01:39:10, william wu wrote:

Thus the transistor count is 4 for both XOR and NAND, which makes me wonder how XOR can have a "much, much more efficient implementation".

I think you misunderstood me.
Consider this, how many NANDS does it cost you to make a XOR ? Since it's more than one, it's more efficient to implement the XOR seperately, and not as a bunch of NANDs put together. The same goes for many other subcircuits.

Making subcircuits from NANDs makes them rather large quickly. And even though it has the benefit of only having to create the same simple gate over and over at different locations, it makes the circuits slower, and makes them use more energy.

I can't see you attachment btw. It shows up rather black.

Title: Re: How Many Logic Functions (II)
Post by william wu on Oct 9^th, 2003, 5:31am

OK, fair enough. I thought you were arguing that XOR + something else would be a better alternative for NAND in making a universal set, because somehow XOR uses less transistors than NAND. Repeating NAND over and over makes layout simpler, but is perhaps only acceptable in low-frequency designs.