Warning this blog post contains a tiny bit of boolean logic. Don’t be afraid.  Let’s explore the eXclusive-OR  (XOR) logic function, another hidden gem that powers computer and network systems. XOR is a binary logical operation with some very special properties. You’ll find XOR hiding under the covers of most communications systems.  The goal of this post is to tell you why XOR is so special and so heavily used.

XOR Operation

If you’ve never heard of a truth table before then don’t worry. The truth table below just shows the result that XOR would give given the the values of inputs A & B. The XOR output will be ‘true’ when both inputs differ.
A  B   Result
0   0    0
0   1    1
1   0    1
1   1    0
Okay I can hear you yawning already, just another truth table. Wait, wait this is cool!! The XOR function has the fantastic property of being completely reversible. Take an example binary word A and XOR it with a random word B, produces output ‘Result’.  If I take that ‘Result’ and XOR it again with B, I get the the original binary word A.  Tadah!!

Encryption and Scrambling

Let’s look at a practical example. I can XOR an input A with a codeword B (a.k.a. shared secret key) B, producing an encoded result
0 1 0 1  Input word: A
1 1 0 0  Code word: B

1 0 0 1  XOR encoded result of Input A and Codeword
Later we can XOR that result with codeword B again to decode the original value of A.
1 0 0 1  Encrypted string from original XOR

1 1 0 0  Code word: B
0 1 0 1  XOR Result: Input word: A
Both encryption and scrambling functions use this XOR property to allow a transmitter to encode an input signal, and the receiver can decode the result.  In a later post I’ll dig a little deeper into how scrambling is used in Ethernet technology. For now, just note that XOR is at the heart of encryption and scrambling.

Integrity checking

XOR also plays a role in Ethernet frame-level error detection. To be fair, most of the magic of 32-bit CRC is in the choice of the code-word and the way it compresses into a fixed-length code, but rest assured XOR is the fundamental operation for CRC generation.

Parity

Note that if the XOR result from our first example was XORed again with A it would also produce B. So we could lose either A or B and, as long as we had the XOR result we could recover the lost information. In this way the XOR result becomes a parity bit or word. RAID parity technology is built on this concept.

Sherpa Summary

When you stand back and look at XOR you’ll either be impressed or underwhelmed. Either way you’ll see XOR mentioned quite a bit when you dig into network fundamentals.  I hope that this brief introduction will help us built our understanding as we start to look at technologies that rely upon it’s powerful properties.