More bit stuff

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.

What I did in my holidays

During the quiet(er) days around the end of the old and beginning of the new year, I’ve been playing around a bit with symbolic bit expressions.

Note: the contents of these post(s) should not be confounded with anything like ‘a paper’. It’s more like ‘my lab notes’: it’s not concise, and I am writing all kinds of stuff down, including wrong turns and mistakes. A proper paper is filtered – this stuff is unfiltered mucking around. Just sayin’.

I’ve only done a cursory search, but by the looks of it there is not much publicly available around manipulating symbolic bit expressions.

E.g. I wanted to do things like: if a and b are some bits, simplify a.b.c | !a.b, where | stands for ‘or’ and . stands for ‘and’.

Or, prove that the two expressions a.b.c | !a.b and b.(c | !a) are equivalent.

I am sure this software exist, as any Verilog or VHDL compiler must have this kind of code inside of it to compile complex schematics, but I did not find much during a quick search.

I’ve been attempting this kind of stuff before, but always ran out of time before it got interesting.

This time around, I managed to get the software into a more advanced state: it’s a Java program that can handle complex bit expressions.

In case you’re wondering: if a[3]…a[0] and b[3]…b[0] are two 4-bit words, and you add them, then the carry bit, fully expanded will amount to:

(a[0].a[1].a[2].b[0].b[3].!a[3]
 | a[0].a[2].b[0].b[1].b[3].!a[3]
 | a[0].a[1].b[0].b[2].b[3].!a[3]
 | a[0].b[0].b[1].b[2].b[3].!a[3]
 | a[0].a[1].a[2].a[3].b[0].!b[3]
 | a[0].a[2].a[3].b[0].b[1].!b[3]
 | a[0].a[1].a[3].b[0].b[2].!b[3]
 | a[0].a[3].b[0].b[1].b[2].!b[3]
 | a[1].a[2].b[1].b[3].!a[3]
 | a[1].b[1].b[2].b[3].!a[3]
 | a[1].a[2].a[3].b[1].!b[3]
 | a[1].a[3].b[1].b[2].!b[3]
 | a[2].b[2].b[3].!a[3]
 | a[2].a[3].b[2].!b[3]
 | a[3].b[3])

or, converted to a tree-like format:

a[0].(
  b[0].(
    a[1].(
      a[2].(
        a[3].!b[3] | b[3].!a[3]
      ) 
      | b[2].(
        a[3].!b[3] | b[3].!a[3]
      )
    ) 
    | b[1].(
      a[2].(
        a[3].!b[3] | b[3].!a[3]
      ) 
      | b[2].(
        a[3].!b[3] | b[3].!a[3]
      )
    )
  )
) 
| a[1].(
  b[1].(
    a[2].(
      a[3].!b[3] | b[3].!a[3]
    ) 
    | b[2].(
      a[3].!b[3] | b[3].!a[3]
    )
  )
) 
| a[2].(
  b[2].(
    a[3].!b[3] | b[3].!a[3]
  )
) 
| a[3].b[3]

I have the expressions for 8 bits too, but they’re even more boring. I don’t think any of this is useful, but I had fun writing and optimizing the Java code to handle arbitrary expressions of symbolic bits; the 8-bit addition takes a few minutes to resolve, and does not run out of memory.

2015 Resolution

My New Year’s Resolution for 2015: staying off Facebook. It sucks up way too much ‘real life’ time, and I am tired of glancing over irrelevant stuff, and I generally dislike the direction of where social media is going, Facebook being one of the worst offenders. This lobster is out of the pot!

However, I occasionally want to share stuff with family and friends. So that’s what this blog is about.

It’s simply about stuff that I want to share. Any stuff – there is no rhyme nor reason to what might pique my interest.

And rather than push it down everybody’s throat on Facebook: on the odd chance that you’re interested in what I am up to in real life, you’ll have to come and visit this site; I won’t be in your news feed.