Out of curiosity, I worked out the carry bit for the addition of two 8-bit symbolic words, a[7]…a[0] and b[7]…b[0].
I intend to work out some method of intelligently re-collapsing common subexpressions.
For all I know, that’ll be a non-effective, circular endeavor; i.e. what I started with might be no more complex than whatever end result I come up with.
I am currently mucking around with what I call ‘tree expressions’: a complex expression gets reduced to a tree of
expression = symbol . primarySubTree | secondarySubtree
where symbol is an atomic symbolic bit (e.g. either ‘x’ or ‘!x’), and both primarySubTree and secondarySubTree don’t contain that symbol.
I.e. I first simplify the expression to a list of terms, each term a ‘flat’ list of symbolic factors.
a.b.c | a.b.!c | a.!b.d … | b.c.d | … or whatever
then find the most common symbol (e.g. a), and convert the expression to
a.(b.c | b.!c | !b.d…) | (b.c.d | …)
then repeat recursively on both subtree, until everything is either expressed as a tree or of a simpler form.
To get a feel for how re-collapsing would work: I let my program express the carry as a tree expression, then manually reduced the carry expression to (using lower case x, y, … for intermediate results):
x = a[7].!b[7] | !a[7].b[7] y = x.(a[6] | b[6]) z = y.(a[5] | b[5]) t = z.(a[4] | b[4]) u = t.(a[3] | b[3]) v = u.(a[2] | b[2]) w = v.(a[1] | b[1]) carry = a[0].b[0].w | a[1].b[1].v | a[2].b[2].u | a[3].b[3].t | a[4].b[4].z | a[5].b[5].y | a[6].b[6].x | a[7].b[7]
which has a nice symmetry to it.
The ‘normal’ carry expressions work out as follows (using upper case X, Y,… for intermediate results):
X = a[0].b[0] Y = a[1].b[1] | X.(a[1].!b[1] | !a[1].b[1]) Z = a[2].b[2] | Y.(a[2].!b[2] | !a[2].b[2]) T = a[3].b[3] | Z.(a[3].!b[3] | !a[3].b[3]) U = a[4].b[4] | T.(a[4].!b[4] | !a[4].b[4]) V = a[5].b[5] | U.(a[5].!b[5] | !a[5].b[5]) W = a[6].b[6] | V.(a[6].!b[6] | !a[6].b[6]) carry = a[7].b[7] | W.(a[7].!b[7] | !a[7].b[7])
which seems to be about the same complexity.
Note: If we write the XOR operator as ^, then a ^ b == (a.!b | !a.b)
This is the same, using the XOR operator:
x = a[7] ^ b[7] y = x.(a[6] | b[6]) z = y.(a[5] | b[5]) t = z.(a[4] | b[4]) u = t.(a[3] | b[3]) v = u.(a[2] | b[2]) w = v.(a[1] | b[1]) carry = a[0].b[0].w | a[1].b[1].v | a[2].b[2].u | a[3].b[3].t | a[4].b[4].z | a[5].b[5].y | a[6].b[6].x | a[7].b[7]
The ‘normal’ carry expressions:
X = a[0].b[0] Y = a[1].b[1] | X.(a[1] ^ b[1]) Z = a[2].b[2] | Y.(a[2] ^ b[2]) T = a[3].b[3] | Z.(a[3] ^ b[3]) U = a[4].b[4] | T.(a[4] ^ b[4]) V = a[5].b[5] | U.(a[5] ^ b[5]) W = a[6].b[6] | V.(a[6] ^ b[6]) carry = a[7].b[7] | W.(a[7] ^ b[7])
What I like about the new form is that it starts down from the high bits. If we read it in pseudocody words, it says:
– if both a[7] and b[7] are set there is a carry (a[7].b[7] in the carry expression)
– else if a[7] and b[7] are clear there is no carry (x is 0, hence y, z,.. are all 0)
– else if a[6] or b[6] are set there is a carry (y is 1)
– else if a[5] or b[5] are set there is a carry (z is 1)
…
It’s not very exciting, and I don’t see any practical uses for it, but it’s satisfying to see that the program came up with a nice, symmetrical alternate expression for the carry.