Symbolic bit vectors

Question

I'd like to see how addition and xoring bitvectors mix together. To do this, I implemented (a primitive) vec_add and vec_xor:

makevar[x_, i_] := ToExpression[StringJoin[x, ToString[i]]]

ClearAll[ADD];
S[x_, y_, c_] := c + x - 2 c x + y - 2 c y - 2 x y + 4 c x y
Ca[x_, y_, c_] := c x + c y + x y - 2 c x y
ADD[fa_, fb_, i_] := Module[
    {CC, SS, obit},
    CC[0] := Ca[fa[0], fb[0], 0];
    CC[n_] := Ca[fa[n], fb[n], CC[n - 1]];
    SS[0] := S[fa[0], fb[0], 0];
    SS[n_] := S[fa[n], fb[n], CC[n - 1]];
    obit := SS[i];
    Return[obit];
    ]
VECADD[fa_, fb_, n_] := Module[
    {o},
    o := Table[ADD[fa, fb, i], {i, 0, n}];
    Return[o];
    ]
xor[a_, b_] := a + b - 2*a*b
BITS := 8
xt := Table[{makevar["x", i]}, {i, 0, BITS}]
yt := Table[{makevar["y", i]}, {i, 0, BITS}]

fx[n_] := xt[[n + 1]]
fy[n_] := yt[[n + 1]]

t1 := VECADD[fx, fy, BITS]

fa[n], fb[n] are functions that return n-th variable from a table. The SS and CC functions are SUM/CARRY respectively. Clearly, this doesn't look like a good implementation so my question is: how to do this nicely? It would be perfect to overload operators for ADD/XOR and just write (a+b)^(b+c).

EDIT: If the implementation isn't clear: the SS/CC functions implement a FULL ADDER

Answer 1

This response will keep the basic strategy of the exhibited code, but it will show some useful Mathematica notations that can shorten the code and emphasize its key features.

See the bottom of this response for the code in textual form.

First, we will use ⊕ to represent XOR, just like in the Wikipedia article. This operator has no built-in meaning in Mathematica. We'll define a couple of identities for XOR that are useful in the present context:

a_ ⊕ 0 := a
a_ ⊕ b_ ⊕ c_ := (a ⊕ b) ⊕ c

We can define single-bit sum and carry operations directly in terms of the XOR operator:

sum[a_, b_, c_] := a ⊕ b ⊕ c
carry[a_, b_, c_] := a b ⊕ c (a ⊕ b)

Following the original code, we can define the result of adding the nth bits out of a multi-bit register:

A few points to note:

• Subscripts are used in place of makevar and the functions that referenced it. We could also have used functions (e.g. c[0], c[i_], s[0], s[i_]), but subscripts look nicer in the final output.
• Return has been removed as the result of functions and modules is the value of the last expression.
• Following Mathematica convention, initial upper case letters are avoided for variable names and ad hoc functions.
• There are other idiomatic ways to express this function in Mathematica (notably involving Nest), but the present recursive form is retained here as it expresses the algorithm directly.

Once again, we now follow the original code and define a function that adds two registers by performing sums over each of the corresponding bits.

addRegisters[a_, b_, n_] := Table[addBits[a, b, i], {i, 0, n}]

There is considerable calculation redundancy in this function definition, but we will tolerate that since simplicity of expression is the issue under discussion here -- not performance.

We can now try out an 8-bit addition (with an additional carry bit):

Note the use of Column to help visually separate the output for each bit.

As requested in the question, we can define an alternate representation for XOR that replaces it with an arithmetic equivalent:

alternateXor[expr_] := expr //. a_ ⊕ b_ :> a + b - 2 * a * b

This alternate representation is very verbose -- we'll only try it on a 3-bit (+ carry) addition:

To match the output of the original code, we can ask Mathematica to expand all products in the output. If we thought the last output was verbose, we'd better fasten our seatbelts for this one (shown for 2+1 bits only):

Code

Here is all of the code again, in a form suitable to copy-and-paste into Mathematica:

ClearAll[CirclePlus, sum, carry, addBits, addRegisters]

a_ ⊕ 0 := a
a_ ⊕ b_ ⊕ c_ := (a ⊕ b) ⊕ c

sum[a_, b_, c_] := a ⊕ b ⊕ c
carry[a_, b_, c_] := a b ⊕ c (a ⊕ b)

addBits[a_, b_, n_] :=
  Module[{c, s}
  , Subscript[c, 0] := carry[Subscript[a, 0], Subscript[b, 0], 0]
  ; Subscript[c, i_] := carry[Subscript[a, i], Subscript[b, i], Subscript[c, i-1]]
  ; Subscript[s, 0] := sum[Subscript[a, i], Subscript[b, i], 0]
  ; Subscript[s, i_] := sum[Subscript[a, i], Subscript[b, i], Subscript[c, i-1]]
  ; Subscript[s, n]
  ]

addRegisters[a_, b_, n_] := Table[addBits[a, b, i], {i, 0, n}]

alternateXor[expr_] := expr //. a_ ⊕ b_ :> a + b - 2 * a * b

(* Test Cases: *)

addRegisters[x, y, 8] // Column[#, Frame -> All]&

addRegisters[x, y, 3] // alternateXor // Column[#, Frame -> All]&

addRegisters[x, y, 2] // alternateXor // ExpandAll // Column[#, Frame -> All]&

Reducing Redundancy

In response to the comment about reducing redundancy, observe that addBits computes the sum and carry of all of the bit pairs up to and including bit pair n. Since addRegisters calls addBits once for each bit, all resultant bits but the last are recomputed several times over. To eliminate this redundancy, we could define a new version of addRegisters that computes each resultant bit only once. For example, an alternative that is in functional form:

addRegisters2[a_, b_, n_] :=
  FoldList[
    { sum[Subscript[a, #2], Subscript[b, #2], #[[2]]]
    , carry[Subscript[a, #2], Subscript[b, #2], #[[2]]]
    } &
  , {0, 0}
  , Range[0, n]
  ][[2;;, 1]]

... or the following semi-imperative variant:

addRegisters3[a_, b_, n_] :=
  Module[{c = 0}
  , Array[
      ( c = carry[Subscript[a, #], Subscript[b, #], c]
      ; sum[Subscript[a, #], Subscript[b, #], #2]
      ) & [#, c] &
    , n + 1
    , 0
    ]
  ]