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.