The Math Citadel

Group Theory, XOR, and Binary Codes: Introducing Coding Theory

R. Traylor

This article gives an introduction to coding theory by looking at the group structure of binary words under the exclusive-or operation. Binary codes and bit-wise operations are fundamental in computer science. Whatever device you are running today works because of binary codes, and the bit-wise operations AND, OR, NOT, and XOR. The reader should consider proving to himself that each of these rules is an operation. If you need a refresher, check out this post.) We can also look at binary codes and the bit-wise operations in a more algebraic way. The previous post discussed operations on sets and explored concatenation as an example. Here, we will build on this and look at a set $G$ combined with an operation $\ast$ that satisfies three axioms. This operation/set combination is a special algebraic object called a group. We'll look at binary codes with the XOR operation to illustrate. Another post examines modulo arithmetic on finite groups of integers as another example of a group.

Terminology and Setup

We currently (until the advent of quantum or DNA computers, or something else entirely) transmit information by coding it into binary strings - strings of 1s and 0s. We call these binary words. 100111 is a binary word, as are 001, 1, and 10110. A general binary word can have any length we want. When we send these binary words via some communication channel, we always run the risk of errors in transmission. This means we need to devise some way to detect and correct transmission errors in binary codes. One way to do this is the XOR operation. Let $\mathbf{a} = a_{1}a_{2}\ldots a_{n}$ and $\mathbf{b} = b_{1}b_{2}\ldots b_{n}$  be binary words of length $n$, where $a_{i},b_{i} \in \{0,1\}$ for $ i=1,..,n$. We define the XOR operation, which we will denote by the symbol $\oplus$, on each bit. For two bits $a_{i}, b_{i}$ in a word, $$a_{i}\oplus b_{i} = (a_{i} + b_{i}) \bmod 2$$ For two words $\mathbf{a}$ and $\mathbf{b}$, the XOR operation is done bit-wise (component by component). That is, $$\mathbf{a} \oplus \mathbf{b} = (a_{1}\oplus b_{1})(a_{2}\oplus b_{2})\ldots (a_{n}\oplus b_{n})$$ For example, $$110010 \oplus 110001 = 000011$$ Notice that the result of the XOR operation shows us the positions in which $\mathbf{a}$ and $\mathbf{b}$ differ. Another way to look at it is if $\mathbf{a}$ was transmitted, and $\mathbf{b}$ was received, there was an error in the last two positions. We can call the result of XORing two binary words the error pattern.

Showing Binary Words with the XOR operation is a Group

Now we'll look at the set of all binary words of length $n$, called $\mathbb{B}^{n}$ coupled with the operation XOR. How many binary words are there of length n? Each slot has two possibilities, 0 and 1, and there are $n$ slots, so there are $2^{n}$ words of length $n$. We call the number of elements in a set the cardinality of a set. So, the cardinality of the set of binary words of length $n$ is $2^{n}$. You see how quickly the number grows as $n$ grows. We want to show that this set along with the XOR operation forms an algebraic structure called a group. A group is one of the most basic algebraic structures we can study.
(Pinter (1982)) A group is a set $G$ coupled with an operation $\ast$, denoted $\langle G, \ast \rangle$ that satisfies the following three axioms:
It's important to note that a group is a set and an operation. If we change one of these, then we either have a different group, or we lose the group classification. Real numbers under addition are a group, as are nonzero real numbers under multiplication, but those are two different groups. Integers under addition are also a group, but a different group than real numbers under addition. Let's prove $\langle\mathbb{B}^{n}, \oplus \rangle$ is a group. Showing a set and operation is a group is pretty algorithmic, in a sense. We just have to show that all three axioms are satisfied.

Bonus round: showing that $\langle \mathbb{B}^{n}, \oplus \rangle$ is an abelian group

Notice that we are missing one property that all of you likely take for granted in regular arithmetic: being able to add and multiply in any order you like. You take for granted that 2+3 = 3+2. This property is called commutativity, and groups with this bonus property are called abelian groups. Not all groups are abelian. Square matrices under matrix multiplication not abelian. We will show that $\langle \mathbb{B}^{n}, \oplus \rangle$ is an abelian group. This actually can be done quite simply by exploiting two things we already know: modulo arithmetic and bit-wise operations. We know that XOR is basically bit wise addition modulo 2. Addition is absolutely commutative, and modding out by 2 doesn't change that, since we add in the regular fashion, then divide by 2 and take the remainder. That means that XORing binary words of length 1 is commutative. Now, since XORing is done bit-wise, which we noted while proving associativity, we can use that same reasoning again (in fact, it looks almost exactly the same), to conclude that XOR is indeed a commutative operation, and thus we have an abelian group.


We explored the definition of a group using a common operation and set from computer science. We needed this foundation to be able to study more. The next post in the coding theory and algebra series will take an in depth look at maximum likelihood decoding. This decoding process is a way to attempt to decode and correct errors in transmission when the communication channel is noisy (and most are, somewhat).Abstract algebra is a powerful branch of mathematics that touches many more things than most of us realize. Now that we know binary words under the XOR operation is a group, we can start extending this and studying it as a structure, or skeleton, rather than focusing on the individual elements. The elements and operation are really just the drywall. The algebraic structure is the frame of beams inside. We learn a lot more by studying the structure than the covering, which is why it is important to enter that abstract realm. We will uncover similarities in strange places, and applications we didn't know were possible.