[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

751.0. "logic design: 'square root' of boolean matrix operator" by EAGLE1::BEST (R D Best, Systems architecture, I/O) Wed Aug 19 1987 15:17

UNSOLVED PROBLEM

Consider a set of boolean functions:

z1 = f1(x1, x2, ... , xn)
z2 = f2(x1, x2, ... , xn)
.
.
zm = fm(x1, x2, ... , xn)

Is there an algorithm for splitting this operator up into two IDENTICAL
boolean operators that produce the same effect as the f's ?

Stated another way, how can I find gk such that

[1]

y1 = g1(x1, x2, ... , xn)
y2 = g2(x1, x2, ... , xn)
.
.
ym = gm(x1, x2, ... , xn)

AND

[2]

z1 = g1(y1, y2, ... , yn)
z2 = g2(y1, y2, ... , yn)
.
.
zn = gm(y1, y2, ... , yn)

The operation is to take a 'boolean square root' of operator f.

The problem arises in trying to increase the number of stages in
a pipelined logic design.  If one or more sets of gk can be found
such that the longest delay through any gk is less than the longest
delay through any fk, then fk is a potential candidate for subdividing into
two stages (namely duplicated g stages).  (More is needed to make this
practical; for example the latch delay and skew has to be figured in, etc.)

Because of the nature of the problem, the given conditions are more stringent
than they have to be.  What is really wanted is a way to split f into a pair
of identical g's, but the outputs from the first g stage can be PERMUTED
in passing to the second stage.  That is, the gk must be the same for
both stages, but you may REARRANGE the order of the arguments in the
second stage to achieve the desired result.  This is because rearranging
the order of the arguments is simply rewiring the inputs to the second
stage (this generally comes for free in implementing).

Please don't kill yourself trying because this looks really hard to me.

------------------------------------------------------------------------
Example:

f1 = x1 + x2 + x3

f2 = x1'.x2'.x3'

f3 = x1 + x2 + x3'

one g that satisfies the relation is:

g1 = x1 + x2

g2 =  x1'. x2'.x3

g3 = x2' + x3'

as can be verified by substitution.
------------------------------------------------------------------------

My example may not be the best, since in my example g might well be more
complex to implement in most technologies, but I hope it helps to clarify the
idea.

I'm interested in knowing just about anything related to this problem.

For example, is there always a set of gk that satisfies [1] and [2] ?

Is there a way to tell from looking at f if a set of gk exists ?

Is there a way to tell from looking at f if there is a possibility that
the gk will be somehow 'simpler' (e.g. each gk will have fewer OR gates
or will have variables appear only in primed or unprimed forms (unary?)) ?
T.RTitleUserPersonal
Name
DateLines
751.1CIMNET::KOLKERConan the LibrarianWed Aug 19 1987 17:594
    re .0
    
    The way you stated the problem m must = n. Is that correct?
    
751.2no, n and m are unrelatedEAGLE1::BESTR D Best, Systems architecture, I/OWed Aug 19 1987 18:2217
re .1:
    
>    The way you stated the problem m must = n. Is that correct?

No; n and m are arbitrary and unrelated.  In my example, n = m = 3
coincidentally.

However, a solution that works only for n = m would still be of interest.
In fact, I think if the solution works for n = m, all the other cases are
degenerate (gotten by making n = m = max( n_given, m_given)).

n is the number of boolean variables; m is the number of functions of these
variables.  In the most general case, each function will depend upon all of the
boolean variables.

Another interesting question: is the set of gk unique for a given set of
fk ?
751.3correction to .0EAGLE1::BESTR D Best, Systems architecture, I/OWed Aug 19 1987 19:4610
>[2]

>z1 = g1(y1, y2, ... , yn)
>z2 = g2(y1, y2, ... , yn)
>.
>.
>zn = gm(y1, y2, ... , yn)

The 'zn' above should be a 'zm'.
751.4Part way thereCIMNET::KOLKERConan the LibrarianTue Sep 01 1987 19:1037
    re .0

Let us define some notation that will save room. 
B_N = {<x_1,..,x_i,..,x_N> | x_i in [0,1] the simple Boolean Lattice}

BF_N = { functions f | f : B_N -> [0,1]} i.e. the N_addic Boolean Functions

BF_2^N = { functions f | f :B_N -> B_N}

NxBF_N = BF_N X ... X BF_N ( The N-fold cartesian prod of BF_N with itself}

Thus if g in NxBF_N then g = <g_1,...,g_N> where g_1,...g_N in BF_N

Let g = <g_1,...,g_N>. Let x in B_N, where x = <x_1,...,x_N>

Define g * x = <g_1(x_1,...,x_N),...,g_N(x_1,...,x_N)> 
thus for x in B_N, g*x in B_N

Your question can now be stated as follows. If f in BF_2^N, does there exist
g in BF_2^N such that f*x = g*(g*x) for all x in B_N.

How many elements in BF_2^N?  Answer: (2^N)^(2^N)

Maximum number of values the functional g*(g*x) can have? Answer:

Cardinality of NxBF_N which is (2^(2^N))^N which = (2^(N*(2^N)) = (2^N)^(2^N)

Thus your problem has an affirmative answer if it can be shown that
the functional g*(g*x) is a 1-1 mapping from BF_2^N onto BF_2^N.
That is for each distinct choice of g_1,....,g_N, plugging the N_tuple
g=<g_1,...,g_N> gives distinct values for g*(g*x), x runs thru B_N, which is
equivalent to saying that if g # g' then for some N tuple x, we have
g*(g*x) # g'*(g'*x). 

I am currently working on this reduction of the problem.
 

751.5KIRK::KOLKERConan the LibrarianFri Sep 04 1987 15:0623
re .0, .4

Bad news. Not all boolean functions have sqare roots. Simple counter example:

	There are four possible function of a single variable:
	1. ALL_TRUE where ALL_TRUE (x) = TRUE (or 1)
	2. ALL_FALSE where ALL_FALSE (x) = FALSE (or 0)
	3. IDENT where IDENT (x) = x
	4. NEG   where NEG (x) = ~x

	ALL_TRUE*ALL_TRUE = ALL_TRUE
	ALL_FALSE*ALL_FALSE = ALL_FALSE
	IDENT*IDENT = IDENT
	NEG*NEG = IDENT

	The function NEG has no boolean square root.

I have not yet shown this for numbers of variables > 1, but I am working on
it. Amusing side light.  You can't compute the square root of minus 1 in the 
domain of Boolean Functional :8>).

More results as I derive them.

751.6Imaginary Logic?CHOVAX::YOUNGBack from the Shadows Again,Sat Sep 05 1987 04:368
    Re .5:
    
    Hmmm, guess we should be looking for something like imaginary roots
    for boolean operations huh?  Sounds like something I read ever so
    long ago in "Laws of Form" by G. Spencer Brown.
    
    
    --  Barry
751.7a 'by hand' procedure .. need an algorithmEAGLE1::BESTR D Best, sys arch, Negotium perambulans in tenebrisFri Oct 30 1987 18:18157
I've made some progress towards getting an algorithm for the Boolean
square root algorithm.  What I have is a hand procedure for doing this
that I'll describe.  I think this procedure might be easy to
implement in something like Prolog because it's a 'cut and try'
algorithm with occasional backtracking needed.  I'm just a neophyte
Prolog programmer, so I may need some help.

Incidentally, the procedure I came up with is relatively simple and
is probably easily extensible to higher order 'roots'.

Here goes:

First, make a truth table of the functions to be computed.
I'll use the following as an example (I'm an engineer, so I understand
things best by example).


z2 = x2 + x0
z1 = x2' + x1
z0 = x0

x2 x1 x0 | z2 z1 z0
---------|---------
0  0  0  | 0  1  0
0  0  1  | 1  1  1
0  1  0  | 0  1  0
0  1  1  | 1  1  1
1  0  0  | 1  0  0
1  0  1  | 1  0  1
1  1  0  | 1  1  0
1  1  1  | 1  1  1

Add a middle column for the 'square root' (y) and convert to decimal:

x	y	z
-----------------	Any entry made in the 'y' column will be used
0	-	2	as an index into the table to locate the value
1	-	7	of y that must correspond to z in the original
2	-	2	entry.  The constraint is y(y(x)) = z(x).
3	-	7	So we start by assigning y(0) arbitrarily and
4	-	4	proceed until we encounter a contradiction
5	-	5	or produced a self consistent subgrouping.
6	-	6	If we encounter a contradiction, then we
7	-	7	backtrack and reassign y(0).  If we produce
			a self consistent subgrouping, then we find
the next unassigned y and make an arbitrary assignment, repeating the
above process.  This is not a great explanation, so I'll work the
example:

0	0	2
; assigned y(0)=0 and encountered a contradiction,
; since y(y(0))=y(0)=0 <> z(0), so we try a new assignment for y(0)

0	1	2
1	2	7
; with y(0) = 1, we must have y(1) = 2 so that y(y(0)) = z(0).  We continue.

0	1	2
1	2	7
2	7	2
; with y(1) = 2, we must have y(2) = 7 so that y(y(1)) = z(1).  We continue.

0	1	2
1	2	7
2	7	2
7	2	7
; with y(2) = 7, we must have y(7) = 2 so that y(y(2)) = z(2).  We continue.

0	1	2
1	2	7
2	7	2
7	2	7
; with y(7) = 2, we must have y(2) = 7, so that y(y(7)) = z(7).  At this point,
; we can no longer follow the 'chain' of constraints, but must arbitrarily
; assign a new one.  We'll try y(3) = 0.

0	1	2
1	2	7
2	7	2
7	2	7
3	0	7
; y(3) = 0 doesn't work, because y(y(3)) = y(0) = 1 <> z(3) = 7, so we must
; try something else.  y(3) = 1 obviously doesn't go either, so try y(3) = 2.

0	1	2
1	2	7
2	7	2
7	2	7
3	2	7
; y(3) = 2 does work because y(y(3)) = y(2) = 7 does equal z(3). There is
; no new constraint to chain to, so we arbitrarily assign y(4).  The first
; assignment that works is y(4) = 4.

0	1	2
1	2	7
2	7	2
7	2	7
3	2	7
4	4	4
; There is no chain to follow, so we next arbitrarily assign y(5).
; y(5) = 5 is the first assignment that works.

0	1	2
1	2	7
2	7	2
7	2	7
3	2	7
4	4	4
5	5	5
; Again, there is no chain, so arbitrarily assign y(6).  y(6) = 6 is
; the only one that works.

0	1	2
1	2	7
2	7	2
7	2	7
3	2	7
4	4	4
5	5	5
6	6	6
; Now we should convert back to binary and identify the boolean function.
x	y	z
000	001	010
001	010	111
010	111	010
011	010	111
100	100	100
101	101	101
110	110	110
111	010	111

y2 = x1.x0' + x2.x1'
y1 = x1 + x2'.x0
y0 = x2'.x0' + x2.x1'.x0


I know that the square root is not unique (I know this because my sample
z functions were generated by squaring a different function of y).

It's also easy to show that there are functions that do not have square
roots.

I'd like to get this written as a program so that I can play with it some
more.
------------------------------------------------------------------------
It seems that the problem may be isomorphic to one that may be amenable to
results from abstract algebra on finite sets.

For given mapping z: { 0..2^n ) --> { 0..2^n },
find another mapping y: { 0..2^n } --> { 0..2^n }
such that For_all x | (x is_in { 0..2^n }) implies z( x ) = y( y( x ) )

This almost looks like permutation groups may be applicable.

Does THIS problem look familiar to anyone ?

What branch of algebra studies this kind of problem ? 
751.8CLT::GILBERTBuilderMon Nov 02 1987 15:23145
The following Pascal program should suffice.  When you run it, the input
would be something like:

	$ RUN SQX
	2 7 2 7 4 5 6 7
	1 3 2 2

It only displays the first 50 square roots.

program sqx (input, output);

const
    k_n = 6;			{ up to 6 variables }
    k_twon = 64;		{ 2**n }

type
    bfunc = array [0..k_twon-1] of integer;

procedure dump_bfunc (twon: integer; f: bfunc);
    var
	i:	integer;
    begin
    write ('(');
    for i := 0 to twon-1 do
	begin
	if i <> 0 then write (',');
	write (f[i]:0);
	end;
    write (')');
    end;

function init (var twon: integer; var f: bfunc): boolean;
    var
	i,j:	integer;
	b:	boolean;
    begin

    twon := 0;
    while (not eoln) and (twon < k_twon) do
	begin
	read (f[twon]);
	while (not eoln) and not (input^ in ['0'..'9']) do get (input);
	twon := twon + 1;
	end;
    readln;

    b := true;
    for i := 0 to twon-1 do
	if (0 <= f[i]) and (f[i] < twon) then else b := false;

    if not b then writeln ('an input error occurred')
    else if twon = 0 then b := false
    else
	begin
	dump_bfunc (twon, f);
	writeln (' <-');
	end;

    init := b;
    end;

function sqrt_x (
		twon:	integer;
	    var	x:	bfunc;
		f:	bfunc;
		limit:	integer
	): integer;
    var
	xxx:	integer;

    procedure recurse (var x: bfunc);
	var
	    i,j,ii,jj,m,tt:	integer;
	    any:	boolean;
	begin
	any := false;
	{ }
	{   Find an entry to set
	{ }
	for i := 0 to twon-1 do if x[i] < 0 then if not any then
	    begin
	    any := true;
	    for j := 0 to twon-1 do
		begin
		{ Assert that x[i] = j }
		ii := i;
		jj := j;
		m := 0;			{ no implications yet }
		while x[ii] < 0 do
		    begin
		    x[ii] := jj;	{ assert that x[ii] = jj }
		    jj := f[ii];	{ and assert that x[jj] = f[ii] }
		    ii := x[ii];	{ next time through the loop }
		    m := m + 1;
		    end;
		if x[ii] = jj then	{ if no contradiction }
		    recurse (x);
		ii := i;
		jj := j;
		while m > 0 do
		    begin
		    tt := x[ii];	{ fetch as a temporary }
		    x[ii] := -1;
		    jj := f[ii];
		    ii := tt;
		    m := m - 1;
		    end;
		end;
	    end;
	if not any then
	    begin
	    if xxx < limit then
		begin
		dump_bfunc (twon, x);
		writeln;
		end;
	    xxx := xxx + 1;
	    end;
	end;

    begin

    for xxx := 0 to twon-1 do x[xxx] := -1;
    xxx := 0;
    recurse (x);
    sqrt_x := xxx;

    end;

procedure main;
    var
	i,twon:	integer;
	x,f:	bfunc;
    begin
    while init (twon, f) do
	begin
	i := sqrt_x (twon, x, f, 50);
	dump_bfunc (twon, f);
	writeln (' has ', i:0, ' square roots ***');
	end;
    end;

begin
main;
end.
751.9Amazing ! (sigh)EAGLE1::BESTR D Best, sys arch, Negotium perambulans in tenebrisMon Nov 02 1987 21:094
  Thank you (extensively) !

I've tried this program and it seems to run flawlessly.  Oh, how I wish
I could program that quickly and effectively !
751.10CLT::GILBERTBuilderTue Nov 03 1987 14:1245
re .5

	The following demonstrates that some sets of functions don't
	have square roots.  It does this by demonstrating two square
    	roots for a single set of functions.

	Note .5 showed this for functions of a single variable.

	Let
	    f (x , x , ... , x ) = x .
	     i  1   2         n     i

	Then the set of functions has (at least) 4 square roots, viz:

	    g (x , x , ... , x ) = x ,
	     i  1   2         n     i

	    g (x , x , ... , x ) = not x ,
	     i  1   2         n         i

	    g (x , x , ... , x ) = x     ,
	     i  1   2         n     n+1-i
	and
	    g (x , x , ... , x ) = not x     .
	     i  1   2         n         n+1-i


	Here's a question -- how many square roots does the set of identity
	functions (the f's above) have?  What is the general formula?
	The program in .8 gives:

		 n	# of square roots
		 1	     1
		 2	     2
		 3	     4
		 4	    10
		 5	    26
		 6	    76
		 7	   232
		 8	   764
		 9	  2620
		10	  9496
		11	 35696
		12	140152
		13	568504
751.11CLT::GILBERTBuilderWed Nov 11 1987 14:015
None of the replies have addressed the rest of the problem in .0:

>                       What is really wanted is a way to split f into a pair
>of identical g's, but the outputs from the first g stage can be PERMUTED
>in passing to the second stage.
751.12dragged off temporarily ...EAGLE1::BESTR D Best, sys arch, I/OThu Nov 12 1987 18:3025
re .11:

The restricted procedure generated so many roots for some of
the functions that I was interested in that I thought it might be beneficial
to see if any of roots were easily reduced to simpler functions than
the original Boolean function before enlarging the number of possibilities
combinatorially ! (pardon the length of that last sentence).

Some interesting observations:
Z = X + 1 has 0 roots
Z = X + 2, Z = X + 4, ... have monotonically increasing numbers of roots.

Note: Z is the decimal interpretation of bit vector Z and X is the decimal
interpretation of bit vector X.

I have been dragged off this problem temporarily, but I will take a
shot at the second part sometime soon.

There are yet two other parts:
(1) The reduction of the boolean g vector function generated by SQX to minimal
realisations.  But that's a standard problem and I'm sure there are scads of
algorithms around to do it (Socrates can probably do this).
(2) The evaluation of the reduced g realisation against some criterion of
maximum path delay.  This requires specific knowledge of the implementation
technology (AUTODLY maybe ?).
751.13one more thoughtEAGLE1::BESTR D Best, sys arch, I/OThu Nov 12 1987 18:4628
One more brief qualitative observation:

I've tried hand reducing several of the candidate g functions
(individually, not sharing terms) and the results are somewhat
disappointing.  All of the ones examined have equal or greater
'complexity' than the original boolean function.

By 'complexity' I mean my seat of the pants estimate of the
worst case path length from any gate input to any network output.
In other words, g seems to require more gates and longer path
lengths than Z.

A proviso: I only did a few and I haven't tried reducing with
shared terms, so I wouldn't necessarily rule out possibilities for
this method yet.

Nonetheless, I wonder if there is some kind of a 'general systems'
theorem at work here.  Maybe something like:

'Breaking things up introduces additional overhead or the parts
sum up to more than the whole.'

Just for fun, I'm going to post a pointer to the hand procedure and
Mr. Gilbert's Pascal in the Prolog conference to see if someone can generate
a really compact elegant implementation.

Afterthought: by 'g' I mean the boolean vector square root of the original
function Z.  I hope the change in terminology didn't confuse anybody.
751.14Sq. root function and Sq. root permutationHPSRAD::KUNDUFri Feb 26 1988 16:21135

PROBLEM STATEMENT.  Given f = (f1, f2, ..., fn), find a g = (g1, g2,
..., gn) such that g*g = f.  Each fi, and gi are functions of n
boolean variables.  Operator "*" means composition.  g will be called
a square root of f.

It is not clear if one can provide a general closed form solution
when f is arbitrary.  However, we do have a solution when we
restrict f to a class of functions, to be defined later.  First,
however, we need some properties of permutaions.

Every permutation can be expressed as compositions of cycles.  A
permutation (cycle) Q is called a "square-root permutation (cycle)"
of P if Q*Q = P.  That is to say, composition of two Q's produces
P.  Composition of cycles is commutative.  Length of a cycle is the
number of elements in it.

LEMMA1.  If C = (c  c  c  ....   c  ) is a cycle of ODD length m, then
		  0  1  2         m-1
the square-root cycle of C also has the length m, and is given by,

	(c   c   c     .....  c   )  where  k = ceiling(m/2).
	  0   k  (2k)mod m    (jk)mod m


LEMMA2.  No cycle of even length has a square-root cycle.

LEMMA3.  A composition of two cycles (c11 c12 c13 ...  c1n) and
(c21 c22 c23 ...  c2n) with equal lengths and no common elements
has the square-root cycle (c11 c21 c12 c22 c13 c23 ....  c1n c2n).


From the above lemmas, we can show:

THEOREM1.  A permutation P has a square-root permutation if and only
if either of the following is true:
	(a) every cycle in P is odd
	(b) number of even cycles of equal lengths are even.


Now, we return to the original square-root function problem.

DEFINITION.  A set of n functions {g1, g2, ..., gn} is called a
"basis set" of all n-variable functions iff any h(x1,x2,...,xn) can
be synthesized starting from the gi's, by using a collection of
complete primitives (eg., NAND).

LEMMA4:  A set {g1, g2, ..., gn} is a basis iff the implied mapping
(x1,x2,...,xn) |---> (g1,g2,...,gn) is 1-1 and onto defined on the
2^n points of the n-cube.

For our purpose, we view the mapping in lemma4 as a permutation.
Theorem1 and lemma4 together solve the original problem of
square-root function when the components f1, f2, f3, ..., fn of f
are restricted to form a basis set.

ALGORITHM1:  Given a f = (f1,f2,...,fn) where the fi's form a
basis, the square-root of f can be found in the following way:

	(1) Let f be the 1-1 mapping from (x1,...,xn)  --> (f1,...,fn)
	    and let P be the permutation defined by f.  If P satisfies
	    theorem1, then apply step2.  Otherwise, there is NO
	    square-root function of f.

	(2) Obtain the square-root permutation Q of P by using Lemmas
	    1 and 3.  Q defines the 1-1 mapping (x1,...,xn)  ---->
	    (g1,...,gn).  The set of gi's so obtained defines the
	    square-root g for f.


EXAMPLE1:  Lets take f1 = x1 xor x2 xor x1x2 xor x2x3 xor x3x1,
		     f2 = x2 xor x3 xor x1x2 xor x2x3 xor x3x1,
		     f3 = 1 xor x2 xor x3x1.

Then, f = (f1,f2,f3) defines the 1-1 mapping,

     (x1,x2,x3) (f1,f2,f3)
	--------------------------
	(000)	(001)
	(001)   (011)	f1 = x1'x2x3' + x1x2'x3' + x1x2x3' + x1x2x3
	(010)	(110)	f2 = x1'x2'x3 + x1'x2x3' + x1'x2x3 + x1x2x3
	(011)	(010)	f3 = x1'x2'x3'+ x1'x2'x3 + x1x2'x3'+ x1x2x3
	(100)	(101)
	(101)	(000)
	(110)	(100)
	(111)	(111)

Converting 3-tuples to decimals, the map f can be viewed as a
permutation, P = (0 1 3 2 6 4 5)*(7).  P is a composition of
cycles of length 7 and 1.

The square-root permutation by using Lemma1,
	Q = (0 6 1 4 3 5 2)* (7).

Permutation Q defines (x1,x2,x3) --> (g1,g2,g3) as follows,

	(x1,x2,x3)	(g1,g2,g3)
	--------------------------
	(000)		(110)
	(001)		(100)
	(010)		(000)
	(011)		(101)
	(100)		(011)
	(101)		(010)
	(110)		(001)
	(111)		(111).

Expressing gi's in terms of xi's, we get,

	g1 = x1'x2' + x2x3, g2 = x2'x3' + x1x3, g3 = x2x3 + x1x3'.

Hence, g1(g1,g2,g3) = g1'g2' + g2g3
		    = x1'x2x3' + x1x2'x3' + x1x2x3' + x1x2x3
		    = f1.

Similarly, one can verify, g2(g1,g2,g3) = f2, and g3(g1,g2,g3) = f3.


EXTENSIONS
----------

While looking at the original square-root problem, it occurs that
our approach could be used for finding "r-th-root" g of f such that

	(g*g*....g) = f.
	 r-times.

The machinery to do so hinges on finding a r-th root of a cycle in
a way similar to finding a square-root of a cycle.  The results for
the r-th-root cycle are not reported here.

	Snehamay Kundu	(HPSRAD::KUNDU)
	Yu Wang		(HPSCAD::WANG)
	26-Feb-1988.
751.15Can simplify a bitAKQJ10::YARBROUGHWhy is computing so labor intensive?Fri Feb 26 1988 16:379
>From the above lemmas, we can show:
>
>THEOREM1.  A permutation P has a square-root permutation if and only
>if either of the following is true:
>	(a) every cycle in P is odd
>	(b) number of even cycles of equal lengths are even.

Note that (a) => (b), so (a) v (b) = (b); thus condition (b) is necessary 
and sufficient.