wu :: forums « wu :: forums - How Many Logic Functions (II) » Welcome, Guest. Please Login or Register. Feb 22nd, 2024, 5:26pm RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    medium (Moderators: Icarus, Eigenray, Grimbal, SMQ, ThudnBlunder, towr, william wu)    How Many Logic Functions (II) « Previous topic | Next topic »
 Pages: 1 Reply Notify of replies Send Topic Print
 Author Topic: How Many Logic Functions (II)  (Read 139433 times)
Mike_V
Junior Member

Gender:
Posts: 60
 How Many Logic Functions (II)   « on: Oct 3rd, 2003, 1:16am » Quote Modify

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 1  f2  f3
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 f3(a,b) = f2(f1(a,b),f1(a,b)). Thus you can generate f3 from the other two, so it is not necessary if you already have f1 and f2.

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

Don't specify the unspecified.
BNC
Uberpuzzler

Gender:
Posts: 1732
 Re: How Many Logic Functions (II)   « Reply #1 on: Oct 3rd, 2003, 1:36am » Quote Modify

I beleive a single function is required for all K.
 IP Logged

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: How Many Logic Functions (II)   « Reply #2 on: Oct 3rd, 2003, 2:31am » Quote Modify

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

Wikipedia, Google, Mathworld, Integer sequence DB
william wu

Gender:
Posts: 1291
 Re: How Many Logic Functions (II)   « Reply #3 on: Oct 3rd, 2003, 11:32am » Quote Modify

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.
 « Last Edit: Oct 3rd, 2003, 11:33am by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
BNC
Uberpuzzler

Gender:
Posts: 1732
 Re: How Many Logic Functions (II)   « Reply #4 on: Oct 3rd, 2003, 3:14pm » Quote Modify

on Oct 3rd, 2003, 11:32am, william wu wrote:
 Thus if I recall correctly, most technology nowadays is built out of 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 NAND 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

OK::
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))

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

 « Last Edit: Oct 3rd, 2003, 3:21pm by BNC » IP Logged

towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: How Many Logic Functions (II)   « Reply #5 on: Oct 4th, 2003, 11:01am » Quote Modify

on Oct 3rd, 2003, 11:32am, william wu wrote:
 Thus if I recall correctly, most technology nowadays is built out of 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.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
william wu

Gender:
Posts: 1291
 Re: How Many Logic Functions (II)   cmos_nand.gif « Reply #6 on: Oct 6th, 2003, 1:39am » Quote Modify

on Oct 4th, 2003, 11:01am, towr wrote:
 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.

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
 « Last Edit: Oct 6th, 2003, 4:01am by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: How Many Logic Functions (II)   « Reply #7 on: Oct 6th, 2003, 5:37am » Quote Modify

on Oct 6th, 2003, 1:39am, 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.
 « Last Edit: Oct 6th, 2003, 5:43am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
william wu

Gender:
Posts: 1291
 Re: How Many Logic Functions (II)   « Reply #8 on: Oct 9th, 2003, 5:31am » Quote Modify

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.
 IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy => medium   - hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »