mark@mips.COM (Mark G. Johnson) (02/26/89)
In article <1827@valhalla.ee.rochester.edu>, badri@valhalla.ee.rochester.edu (Badri Lokanathan) writes: >In any case, from the comp.lsi viewpoint, this [using lots of AND >gates & OR gates but minimal inverters] is really quite a useless >exercise since in most cases, inverted logic is the norm rather >than the exception. Today, true. But back in the early to mid 60's, when the problem was apparently widely circulated and studied, they were fiddling with a (theoretical) family of *non*inverting logic called Threshold Logic. In fact the published N-inverters paper gives a solution in Threshold Logic gates [Sheldon B. Akers, "On Maximum Inversion with Minimum Inverters", IEEE Transactions on Computers, vol. C-17, no. 2, pp. 134-135, February 1968.] Threshold Logic operated on binary data (values = 0 or 1) but its operators weren't AND, OR, INV. Instead, each gate had a "threshold" number, t, associated with it. If t or more if the gate's inputs were logic-1, then the output was logic-1; otherwise the output was logic-0. It takes 2 pieces of data to describe a gate: (I,T) where I is the number of inputs and T is the threshold {hopefully T<=I or you've got a constant `0' out}. It's pretty easy to see how to implement Threshold Logic gates using resistive voltage summation networks and voltage comparators with settable thresholds. You can also build them out of standard Boolean gates too. For example here's all of the 4-input threshold gates (inputs are A, B, C, D): (4,0) OUT = constant_logic_1 (4,1) OUT = A + B + C + D (4,2) OUT = AB + AC + AD + BC + BD + CD (4,3) OUT = ABC + ABD + ACD + BCD (4,4) OUT = ABCD (4,5) OUT = constant_logic_0 Note that the gate computes only *non*inverting functions. You can't put in X and get out X-bar. Presumably that's why theoreticians liked to toy with problems calling for as few inverters as possible. aside remark: The Threshold Logic model can be extended so that each input to a gate has a "weight" associated with it, and the gate computes whether or not SUMMATION(weight[i]) >= t (t is the threshold value). If you permit weights and thresholds to be negative numbers, then you can build inverting logic. Dertouzos of MIT developed lots of theory about Threshold Logic in his Ph.D. -- -- Mark Johnson MIPS Computer Systems, 930 E. Arques, Sunnyvale, CA 94086 ...!decwrl!mips!mark (408) 991-0208