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.