Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

ABA = B

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

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

Sign
Vector  0  1  1  1              1  0  0  0

Symmetric
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' ?

share|improve this question
add comment

1 Answer

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$.

share|improve this answer
    
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? –  Cris Stringfellow Feb 20 '13 at 13:12
    
@Cris I just found that any number does work in this case, therefore $0$, too ;) see the edit. –  tohecz Feb 20 '13 at 13:15
    
so what you are saying is that subtraction mod the base works as xor in any base? –  Cris Stringfellow Feb 20 '13 at 13:20
    
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}$?) –  tohecz Feb 20 '13 at 13:26
    
@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? –  user16859 Apr 17 at 16:34
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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