## More bit stuff

Out of curiosity, I worked out the carry bit for the addition of two 8-bit symbolic words, a…a and b…b.

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.!b | !a.b
y = x.(a | b)
z = y.(a | b)
t = z.(a | b)
u = t.(a | b)
v = u.(a | b)
w = v.(a | b)
carry = a.b.w | a.b.v | a.b.u | a.b.t | a.b.z | a.b.y | a.b.x | a.b
```

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.b
Y = a.b | X.(a.!b | !a.b)
Z = a.b | Y.(a.!b | !a.b)
T = a.b | Z.(a.!b | !a.b)
U = a.b | T.(a.!b | !a.b)
V = a.b | U.(a.!b | !a.b)
W = a.b | V.(a.!b | !a.b)
carry = a.b | W.(a.!b | !a.b)
```

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 ^ b
y = x.(a | b)
z = y.(a | b)
t = z.(a | b)
u = t.(a | b)
v = u.(a | b)
w = v.(a | b)
carry = a.b.w | a.b.v | a.b.u | a.b.t | a.b.z | a.b.y | a.b.x | a.b
```

The ‘normal’ carry expressions:

```X = a.b
Y = a.b | X.(a ^ b)
Z = a.b | Y.(a ^ b)
T = a.b | Z.(a ^ b)
U = a.b | T.(a ^ b)
V = a.b | U.(a ^ b)
W = a.b | V.(a ^ b)
carry = a.b | W.(a ^ b)
```

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 and b are set there is a carry (a.b in the carry expression)
– else if a and b are clear there is no carry (x is 0, hence y, z,.. are all 0)
– else if a or b are set there is a carry (y is 1)
– else if a or b 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…a and b…b are two 4-bit words, and you add them, then the carry bit, fully expanded will amount to:

```(a.a.a.b.b.!a
| a.a.b.b.b.!a
| a.a.b.b.b.!a
| a.b.b.b.b.!a
| a.a.a.a.b.!b
| a.a.a.b.b.!b
| a.a.a.b.b.!b
| a.a.b.b.b.!b
| a.a.b.b.!a
| a.b.b.b.!a
| a.a.a.b.!b
| a.a.b.b.!b
| a.b.b.!a
| a.a.b.!b
| a.b)```

or, converted to a tree-like format:

```a.(
b.(
a.(
a.(
a.!b | b.!a
)
| b.(
a.!b | b.!a
)
)
| b.(
a.(
a.!b | b.!a
)
| b.(
a.!b | b.!a
)
)
)
)
| a.(
b.(
a.(
a.!b | b.!a
)
| b.(
a.!b | b.!a
)
)
)
| a.(
b.(
a.!b | b.!a
)
)
| a.b
```

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.