XOR Through Algebra
Written on October 4th, 2022 by Mouse
What is XOR?
In this post, I will be exploring the bitwise XOR function through the tools of abstract algebra and group theory. XOR, or eXclusive OR, is a Boolean logical operator. It takes in two strings of bits, and outputs their exclusive disjunction. Formally, XOR is a binary operation between binary vectors of length \(n\), denoted by \(\oplus\):
\[\oplus : \{0,1\}^n \times \{0,1\}^n \to \{0,1\}^n\]When \(n > 1\), XOR operates pairwise on each index.
The output of XOR is encapsulated in the below truth table:
| A | B | Output |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
The XOR operation can be summarised as “either one, but not both nor none”. As an analogy, imagine you and a friend each have a Dominos Meatilicious Pizza, and decide to have a pizza-eating race. Only one of you can eat the Meatilicious Pizza fastest - only one of you will win. There cannot be two winners and there cannot be no winner.
The XOR operation can also be defined using the primitive Boolean algebra operations - AND (\(\land\)), NOT (\(\lnot\)), and OR (\(\lor\)). We can express \(a\) XOR \(b\) as:
\[a \oplus b \equiv (\lnot{a} \land b) \lor (a \land \lnot{b})\]or equivalently:
\[a \oplus b \equiv (\lnot{a} \lor \lnot{b}) \land (a \lor b)\]One interesting aspect of the XOR operation is its cyclic nature. If you XOR together two bit strings, and XOR the result with one of the original strings, you get the other string back. More precisely:
\((A \oplus B) \oplus A = B\) and \((A \oplus B) \oplus B = A\)
This feature of XOR makes it useful for encoding data, and is used in many modes of operation for cryptographic block ciphers. When we XOR data, no information is lost - XOR it again and you get the data back. For a concrete example, consider the binary strings \(110011\), and \(001101\). When you XOR these together, you get \(111111\). When you compute \(111111\) XOR \(110011\), you get \(001101\) - the other original string.
Abelian Groups
It turns out that the XOR operator with binary vectors forms not just a group, but an abelian group! We will now prove this using the group axioms. For a refresher on the definition and axioms of a group, check out the Defining Geometric Shapes with Group Theory article.
We first note that since XOR is a binary operation, it is closed. This can be trivially seen with the truth table above - using just \(1\)s and \(0\)s, there is not way to get another symbol.
Next, we consider associativity. For associativity to hold, we need \((a \oplus b ) \oplus c = a \oplus (b \oplus c)\) for any \(a, b, c \in \{0,1\}^n\). Since XOR operates pairwise, we only need to consider \(2^3 = 8\) possibilities. They are listed below.
\[(0 \oplus 0) \oplus 0 = 0 = 0 \oplus (0 \oplus 0)\] \[(0 \oplus 0) \oplus 1 = 1 = 0 \oplus (0 \oplus 1)\] \[(0 \oplus 1) \oplus 0 = 1 = 0 \oplus (1 \oplus 0)\] \[(0 \oplus 1) \oplus 1 = 0 = 0 \oplus (1 \oplus 1)\] \[(1 \oplus 0) \oplus 0 = 1 = 1 \oplus (0 \oplus 0)\] \[(1 \oplus 0) \oplus 1 = 0 = 1 \oplus (0 \oplus 1)\] \[(1 \oplus 1) \oplus 0 = 0 = 1 \oplus (1 \oplus 0)\] \[(1 \oplus 1) \oplus 1 = 1 = 1 \oplus (1 \oplus 1)\]We see that associativity holds for every possible case.
The \(n\)-bit string of \(0\)s is the identity element, \(e\). Indeed: \(0 \oplus 0 = 0\) and \(0 \oplus 1 = 1\). So the identity property is satisfied.
Each element is its own inverse. Indeed: \(0 \oplus 0 = 0 = e\) and \(1 \oplus 1 = 0 = e\). So each element has an inverse.
Hence we have shown that XOR with binary vectors indeed forms a group. We can also note that this group is commutative - \(0 \oplus 1 = 1 = 1 \oplus 0\). Hence we have an abelian group.
Other Boolean Operators
It is worth pointing out that XOR is special. Other Boolean operators, such as AND and OR, do not form such nice structures.
If we try form a group with the AND operator, the identity element will have to be \(1\): \(0 \land 1 = 0\) and \(1 \land 1 = 1\). But if this is the case, \(0\) does not have an inverse. So AND does not form a group.
Similarly, the identity for OR would have to be \(0\): \(0 \lor 0 = 0\) and \(0 \lor 1 = 1\). But then we note that \(1\) does not have an inverse.
If we consider the NAND operator, neither \(0\) nor \(1\) can be the identity. The NOT operator isn’t even a binary operation. Despite this, we do note that AND and OR form monoids.
Monoids are algebraic structures consisting of a set and a binary operation satisfying associativity, and which contains an inverse.
Since no other Boolean operators form nice enough structures, we sadly cannot create a ring with Boolean operators. However, we can create a field. If we consider XOR as our ‘addition’ and AND as our ‘multiplication’ over binary vectors, we don’t just get any field, but the field \(\Bbb{F_2}\) - the integers \(\mod 2\).
Elementary Abelian Groups
The group that we have found can be generalised to the so-called elementary abelian \(p\)-groups. These are abelian groups where every non-trivial element has order \(p\), where \(p\) is a prime number. The XOR group we have found is isomorphic to the case when \(p=2\). Indeed, we saw that every element had order \(2\) - each element is its own inverse.
By the classification of finitely generated abelian groups, we see that the XOR group must be of the form \(\{\Bbb{Z}/2\Bbb{Z}\}^n\) for some positive integer \(n\). In particular, this is a cyclic group. This can explain the cyclic phenomenon we see in the XOR operation, as discussed at the start.
Another feature of the XOR group is that it can be extended to an infinite abelian group. If we consider our set to be the binary representations of all integers, we can use the same XOR operation. Since XOR works on each component of a vector separately, it doesn’t matter how large our vectors are. If they are of different sizes, we can simply pad the smaller vector with zeros. Hence, we have found another abelian groups on the integers - and a much more exciting one than the usual additive group!
Finally, we can examine subgroups of the XOR group. Consider taking a subset of binary vectors where some indices are fixed at 0, for example the set \(\{w \in \{0,1\}^n : w = 000\{0,1\}^3\}\) of length \(6\) vectors, with the first three bits fixed to \(0\). Since the XOR operation will keep the first three bits fixed at \(0\), this will form a subgroup. Hence we can see that the XOR group on the integers is not a simple group - it contains infinite subgroups.
We can do one better - since the XOR group is abelian, all these subgroups are normal.
Conclusion
In this article, we have explored the group consisting of the Boolean operator XOR. We have proven that this is indeed a group and that it is abelian. We explored the cyclic nature of XOR, and touched on the elementary abelian groups. We saw some nifty features of the XOR group - we can extend it to an infinite group, and found that it is not simple. Who knew the humble XOR function had so much to hide!
