[math-fun] optimum logic circuit to compute "count>=2" binary threshold function (and LIFE)
Consider the threshold=k binary function on N bits. That is, it is 1 if at least k of the N input bits are 1, otherwise it is 0. How many logic gates do you need to compute these functions? ======k=1======== Obviously, when k=1, just a big logical-OR does the job, i.e. only 1 gate with N inputs, or if you insist on 2-input gates only, then a tree with N-1 OR gates will do, and with depth<=lg(N) where lg(x)=log2(x). ======k=2======== When k=2, I discovered an optimal solution yesterday. Let G(N) be the number of 2-input gates needed. When N=2: output=AND(a,b) hence G(2)=1. G(3)<=5 since majority(x,y)=x*y + y*z + z*x which works regardless of whether the symbol + is interpreted as inclusive or exclusive OR. (*=AND.) If this is rewritten majority(x,y)=(x+z)*y + x*z then G(3)<=4. When N=4: compute z=OR(AND(a,b), AND(c,d)), y=AND(OR(a,b), OR(c,d)), output=OR(y,z). This shows G(4)<=7. When N=even: compute z=OR(thresh2(left N/2 bits), thresh2(right N/2 bits), y=AND(ORtree(left N/2 bits), ORtree(right N/2 bits), output=OR(y,z) which shows G(N)<=2*G(N/2)+N-2+1+1+1=2*G(N/2)+N+1 hence G(8)<=23 G(16)<=63 etc, G(N)<=N*lg(N)-1 is the general formula. But meanwhile, googling found this paper Ilan Newman & Avi Wigderson: Lower Bounds on Formula Size of Boolean Functions using Hypergraph Entropy, SIAM J. Discrete Mathematics 8,4 (1996) 78-87 http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/HNW96/entropy.pdf and the theorem they mention on page 7 which they re-prove but also say was previously proven by Marc Snir: The covering problem of complete uniform hypergraphs, a note, Discrete Maths. 27 (1979) 103-105 shows (by taking k=2 and also using the fact a binary tree with L leaves must have L-1 internal nodes including the root) G(N)>=N*lg(N)-1. Hence G(2)>=1 G(3)>=4 G(4)>=7 G(8)>=23 G(16)>=63 etc which shows my threshold=2 circuit-constructions are exactly optimal when N=2, 4, 8, 16 and actually forever. It also shows these are optimal: G(3)=4 G(6)=15 G(12)=43 but we only have 110<=G(24)<=111. It would be surprising if this were not already known, but I did not see any mention of any circuit construction in Newman+Wigderson. =======k=3======== Moving on, what about threshold=3? By the way, if you need a use for this, since everyone on this group seems in love with the "game of LIFE" I point out that is defined entirely using binary threshold functions, so a fast "bitboard" implementation of LIFE would want to know about these circuits. Letting H(N) be the number of 2-input AND and OR gates needed, I can show H(3*N) <= 3*H(N) + 3*N + 3*G(N) + 12 and as a base case H(3) = 2 by using a 3-input AND gate. -- Warren D. Smith http://RangeVoting.org <-- add your endorsement (by clicking "endorse" as 1st step)
It must be a coincidence, but I recently wrote an article on my website about this. Though I don't attempt to discuss minimal circuits. However, I do write a code generator and optimizer in Lisp for these threshold gates, which I call "M-of-N circuits". See the article here: http://symbo1ics.com/blog/?p=1352 preferably in a browser with JavaScript. The code for the post is here: https://bitbucket.org/tarballs_are_good/lisp-random/raw/c8258e2e5a81/m-of-n-... Cheers, Robert Smith On 6/27/2012 8:26 AM, Warren Smith wrote:
Consider the threshold=k binary function on N bits. That is, it is 1 if at least k of the N input bits are 1, otherwise it is 0.
How many logic gates do you need to compute these functions?
======k=1======== Obviously, when k=1, just a big logical-OR does the job, i.e. only 1 gate with N inputs, or if you insist on 2-input gates only, then a tree with N-1 OR gates will do, and with depth<=lg(N) where lg(x)=log2(x).
======k=2======== When k=2, I discovered an optimal solution yesterday. Let G(N) be the number of 2-input gates needed. When N=2: output=AND(a,b) hence G(2)=1.
G(3)<=5 since majority(x,y)=x*y + y*z + z*x which works regardless of whether the symbol + is interpreted as inclusive or exclusive OR. (*=AND.) If this is rewritten majority(x,y)=(x+z)*y + x*z then G(3)<=4.
When N=4: compute z=OR(AND(a,b), AND(c,d)), y=AND(OR(a,b), OR(c,d)), output=OR(y,z). This shows G(4)<=7. When N=even: compute z=OR(thresh2(left N/2 bits), thresh2(right N/2 bits), y=AND(ORtree(left N/2 bits), ORtree(right N/2 bits), output=OR(y,z) which shows G(N)<=2*G(N/2)+N-2+1+1+1=2*G(N/2)+N+1 hence G(8)<=23 G(16)<=63 etc, G(N)<=N*lg(N)-1 is the general formula.
But meanwhile, googling found this paper Ilan Newman & Avi Wigderson: Lower Bounds on Formula Size of Boolean Functions using Hypergraph Entropy, SIAM J. Discrete Mathematics 8,4 (1996) 78-87 http://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/HNW96/entropy.pdf
and the theorem they mention on page 7 which they re-prove but also say was previously proven by Marc Snir: The covering problem of complete uniform hypergraphs, a note, Discrete Maths. 27 (1979) 103-105 shows (by taking k=2 and also using the fact a binary tree with L leaves must have L-1 internal nodes including the root) G(N)>=N*lg(N)-1. Hence G(2)>=1 G(3)>=4 G(4)>=7 G(8)>=23 G(16)>=63 etc
which shows my threshold=2 circuit-constructions are exactly optimal when N=2, 4, 8, 16 and actually forever. It also shows these are optimal: G(3)=4 G(6)=15 G(12)=43 but we only have 110<=G(24)<=111.
It would be surprising if this were not already known, but I did not see any mention of any circuit construction in Newman+Wigderson.
=======k=3======== Moving on, what about threshold=3? By the way, if you need a use for this, since everyone on this group seems in love with the "game of LIFE" I point out that is defined entirely using binary threshold functions, so a fast "bitboard" implementation of LIFE would want to know about these circuits.
Letting H(N) be the number of 2-input AND and OR gates needed, I can show H(3*N) <= 3*H(N) + 3*N + 3*G(N) + 12 and as a base case H(3) = 2 by using a 3-input AND gate.
participants (2)
-
Robert Smith -
Warren Smith