Operator - Generalized Symmetric Difference

If you take binary xor and generalize it to other radices you can do so by the absolute value of the difference of each element in a radix vector. However this doesn't have the same properties as the binary symmetric differene. The reason is that in throwing away the "sign" of the difference we are unable to reconstruct an operaand given the result and the other as we can in binary xor. So we lose the nice property


However we keep other nice properties like

A0 = A

AA = 0

There is a way to maintain this property. However, as far as I can tell it involves emitting 3 vectors for any result. The first vector is the usual symmetric difference, the other two vectors are binary vectors of equal length to the first that record the sign of the result, one such vector for each order of the operands, on being the binary complement of the other. In this way, an original operand can be recovered, given the result and the other opernad, AND that other operands "sign" vector.

For example :

Say we have 2 base 10 vectors corresponding to the numbers 1137 and 9284, what i s the xor of these two numbers in base 10?

        7  3  1  1              4  8  2  9

        4  8  2  9              7  3  1  1

Result  3 -5 -1 -8             -3  5  1  8

Vector  0  1  1  1              1  0  0  0

Difference              3 5 1 8

Recover 1137 given 8153 and 9284

3  5  1  8
+  -  -  -
4  8  2  9

7  3  1  1

My question is : is there a better construction of generalized symmetric difference in any radix > 2 such that we don't need to 'remember the sign' ?


The most common definition of xor is $a\oplus b=(a+b)\bmod 2$, on vertices applied to every coordinate seperately of course. In base-10 case, you have to introduce two operations: $a\oplus b=(a+b)\bmod 10$ and $a\ominus b=(a-b)\bmod 10$. (Notice that in base-2 case they coincide). Now you have

$$c=a\ominus b \quad\text{for coding}\quad\text{and}\quad a=c\oplus b \quad\text{for decoding.}$$

Actually, you can use $\ominus$ for both operations, just a bit cleverer:

$$c=b\ominus a \quad\text{for coding}\quad\text{and}\quad a=b\ominus c \quad\text{for decoding.}$$

This works because $a=b\ominus c=(b-c)\bmod 10=(b-(b\ominus a))\bmod 10 $ $= (b-(b-a)\bmod 10)\bmod 10=a\bmod 10=a$.

  • $\begingroup$ I like this. This is great. Much better. Can you elaborate a little bit on your thinking for how you derived this combined operator from the two operators, such as "why does 5 work?" Also is there anything possible for odd bases like ternary? $\endgroup$ – Cris Stringfellow Feb 20 '13 at 13:12
  • $\begingroup$ @Cris I just found that any number does work in this case, therefore $0$, too ;) see the edit. $\endgroup$ – yo' Feb 20 '13 at 13:15
  • $\begingroup$ so what you are saying is that subtraction mod the base works as xor in any base? $\endgroup$ – Cris Stringfellow Feb 20 '13 at 13:20
  • $\begingroup$ Yes. In sense of cryptography/coding, yes. Just be careful that $\ominus$ is not symmetrical. Still, given $b$ is a fixed code and defining $f_b(x)=b\ominus x$, we have that $f_b$ is an involution, i.e., $f_b(f_b(x))=x$ for all $x$. (Well, $f_b$ defined this way will be an involution is any abelian group, so why not in $\mathbb Z_{10}$?) $\endgroup$ – yo' Feb 20 '13 at 13:26
  • $\begingroup$ @tohecz Any idea if it is possible to do this for the entire number? E.g. Is there a succinct operation f(7311, 4829) = 3518? $\endgroup$ – user16859 Apr 17 '14 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.