# Symbolic bit vectors

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]]]

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
{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];
]
{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]]



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

-
Can you tell us a little more about what you're trying to do, or give us some background information on your exploration? This looks really interesting, but I feel like I'm missing context. – sblom Jul 2 '12 at 21:05
The ADD/XOR combination is often used in ciphers to introduce nonlinear dependencies between the output and input bits. crypto.stackexchange.com/questions/2608/why-addition-mod-32 – qwe Jul 2 '12 at 21:09

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)

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]
]

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
]
]

-
Can you show how to make addRegisters faster? – qwe Jul 3 '12 at 6:31
@Mr.Wizard I'm using images as a lazy way to retain the visual appearance of the subscripts in the code. I'd love to learn a better way. – WReach Jul 3 '12 at 12:33
@Mr.Wizard They don't need to be images. I only did it that way for consistency given that I added a copyable text block at the bottom. However, I have no objection to their replacement with plain text. – WReach Jul 3 '12 at 12:40
@qwe As to removing the redundancy in the calculations, it might be a day or two until I can work on this problem again. However, you might try posting that request as a new question and I know you'll get lots of good ideas very quickly. – WReach Jul 3 '12 at 12:41
I believe you can replace the line Subscript[c, 0] := carry[Subscript[a, 0], Subscript[b, 0], 0]; with Subscript[c, -1] = 0; and likewise Subscript[s, -1] = 0; – Mr.Wizard Jul 3 '12 at 12:50