Tuesday, February 22, 2005

MOD and XOR

...I've been looking into multi-valued logic. If you implement an adder in any _n_ valued logic, you can see distinct differences between the equivalent XOR and AND operations that make up the truth tables in these logics. For instance:

XOR b_2_
---------
0 1

0 0 1
1 1 0

AND b_2_
---------
0 1

0 0 0
1 0 1


Now, let's examine b_3_:

XOR b_3_
---------
0 1 2

0 0 1 2
1 1 2 0
2 2 0 1


AND b_3_
---------
0 1 2

0 0 0 0
1 0 0 1
2 0 1 1


If we generalize this across all _n_ valued logics, we can see that to mathematically implement these truth tables is relatively easy. For some number A and some number B converted to base _n_ (so A in base _n_ will be some set of values {a1, a2, etc.}, as will b), we can find XOR and AND using the following equations:

a(x) XOR b(x) = a(x) + b(x) MOD _n_
a(x) AND b(x) = floor((a(x) + b(x)) / n)

where a(x) and b(x) are members from {a1, a2 .. a(x)) and {b1, b2 .. b(x)} (as defined above) with the same index value x. For example, in base 2 the XOR of a(x) = 1 and b(x) = 1 is:

a(x) + b(x) = 1 + 1 = 2, and

0 = 2 MOD 2 (note: I'm not following the convention where the number immediately following the equal sign represents the result of A MOD B).

AND is computed as:

floor((1 + 1) / 2) = floor(2 / 2) = 1

So, our thought experiment for the week is this -- what does it mean, considering how we've defined XOR above, when we perform some operation x MOD y? Further, does the relationship between the MOD function and XOR lead us to any new methods for carrying out modular arithmetic? I suspect someone has already addressed this but I haven't found anything about it yet. Anyway, I'll report back later with my findings (however trivial they may be).

Comments: Post a Comment

<< Home

This page is powered by Blogger. Isn't yours?