Optimizing "bitblt" functions using Xor

[Serge A. Winitzki]

[... in a previous post about optimizing logical functions:]
>>There is a technique in circuit design that guarantees the
>>minimum number of AND and OR operations necessary to
>>reduce all possible input states.
>>(I don't remember the exact details, but we used
>>pencil and graph version that involved drawing rectangles
>>around a table of transition states.)

>Karnaugh maps, they are called.
>Here is a (very badly drawn) 4x4 K-Map:
>
> AB
> 00 01 11 10
> ------------------
>CD| /---|---| Explanation:
>00| | 1 | X | 0 0 There is a 2x2 box drawn in the top-left corner.
> | | \---/---\ There is a 1x2 box drawn in col.3 (rows 2-3)
>01| | 1 1 | 1 | 0 There is a 1x2 box drawn in col.2 (rows 4-1)
> | \-------/ | Note that this last box wraps-around and appears
>11| 0 0 | X | 0 at the top of the diagram again.
> | /---\---/
>10| 0 | 1 | 0 0
> | |

>This defines the outputs (in the table) given the inputs (listed on edges).
>The X symbol means a don't care state, which can safely be enclosed in boxes
>if it means that the result will be simpler.

[... and the final formula was: (using / for Not, * for And, + for Or)]

> (/A * /C) + (A * B * D) + (/A * B * /D)

My comment:

The optimized formula takes 11 operations.
But this is only using And, Or and Not. A very useful Xor operation
is left out! With help of this operation, the above formula becomes

(/A * /C) + B * ((A * D) + (/A * /D)) = (/A * /C) + B * (/A Xor D)

which only requires 7 operations.

The Xor operation drastically cuts down the number of operations when
dealing with totalistic CA rules. For example, a function of four variables
a, b, c, d, returning 1 iff there are exactly two ones and two zeros among
its arguments, is represented by this Karnaugh diagram:

AB
00 01 11 10
------------------
CD|
00| 0 0 1 0 Returns 1 if exactly two among a, b, c, d
|
01| 0 1 0 1 are 1 and two others are 0; returns 0 otherwise
|
11| 1 0 0 0
|
10| 0 1 0 1
|

The method of drawing boxes gives no simplification to this
formula,because there are no boxes to draw anywhere, and the formula
looks like its normal form:

a*b*/c*/d + a*/b*c*/d + /a*b*c*/d + a*/b*/c*d + /a*b*/c*d + /a*/b*c*d

requiring 35 operations. Now if we try to use the Xor operation, the
formula will be easily simplified to

(a Xor b)*(c Xor d) + a*b*/c*/d + /a*/b*c*d [15 operations]

or even further to

(a Xor b)*(c Xor d) + (a Xor c)*(b Xor d) [7 ops]

As one can see, the Xor operation cuts down 80% of the original
operations.

My old question is, how can one generate optimized formulas with Xor?
Every logic design book only concentrates on And/Or formulas... I did the
above derivations by hand, but there should be an algorithmic way to do
that. Such an algorithm could be used for automatic rule generation in a CA
simulator, so a rule table could be input, and the program would then
generate the optimized bit operation sequence needed for the calculation.
I would appreciate any comments on this.

Regards,
Serge
--
Serge Winitzki

[Serge A. Winitzki]

Right. If we see a diagonal square, it's a XOR. But this is not the only
situation possible, and I don't know a general way to incorporate Xor into
the formula.

[ku...@cdf.ca.gov]

I'm not sure that there actually is an algorithmic way to recognize
XOR conditions... on the K-map, we see it when we see a 2x2 square
with 2-1s in one diagonal line and 2-0s in the other. But it was
always by recognition of that condition visually... nothing that
automagically evolved into it.
Then again, all of my teachers have been old people! ;-)

Kurt Perkins
ku...@cdf.ca.gov

[Rudy Rucker]

I wonder if you can apply these thoughts to improve our current record
of 30 BitBlts for life?
Suppose we go ahead and use eight bit blts to start with to get the
NW, N, NE, W, C, E, SW, S, SE bits.
What is wanted is the fewest number of ops equivalent to saying that
( Exactly 3 of the eight neighbors are 1) + (C is on and exactly
2 of the eight neighbors are 1).
If you can do this in less than 21 operations, I can make the
program run faster.

[Serge A. Winitzki]

Well, I am sure that the formula for Life is already using Xor. I strongly
doubt that one can make it in 21 ops without Xor. I have tried to do this
some time ago and couldn't make much progress, my best try was about 30
ops. The theoretical value is 32 ops, so one doesn't have to worry about
it. My guess is that anything between 20 and 30 ops is pretty optimal as it
is, and one can't make it much faster than that.