Hardware – XOR

XOR

XOR Symbol

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.

 

(Visited 1 times, 1 visits today)
Tweet about this on TwitterShare on FacebookShare on Google+Share on LinkedInShare on RedditBuffer this pageShare on StumbleUpon

6 thoughts on “Hardware – XOR

  1. I find Boolean logic quite interesting. Another application where XOR can become useful is when trying to create a wildcard mask to match discontiguous addresses. For example, given the following:

    A 172.31.5.0/24
    B 172.31.7.0/24
    C 172.31.13.0/24
    D 172.31.15.0/24

    Let’s say we want to match addresses A and C only. All we need to do is to XOR the interesting octet (3rd one in this particular case) to get the appropriate wildcard mask.

    – Binary | Decimal
    A 0 0 0 0 0 1 0 1 | 05
    B 0 0 0 0 0 1 1 1 | 07
    C 0 0 0 0 1 1 0 1 | 13
    D 0 0 0 0 1 1 1 1 | 15
    —————————-
    – 0 0 0 0 1 0 0 0 | 08 (A xor C)

    So 172.31.5.0 0.0.8.0 would then match A and C whilst leaving B and D alone.

    As a side note, I’ve found this to be quite powerful specially when like a lot of people I used to mistakenly assume that a wildcard mask had somehow to be contiguous as in 0.0.0.3.255 or 0.0.0.255 for example and used to incorrectly refer to it as ‘reversed network mask’.

    • Ha, that’s cool. Didn’t realise the XOR trick for discontiguous masks. Mind you, I think the fact that many people don’t understand discontinuous masks is a really good reason for not using them. Thanks for the example. good stuff!!

  2. Nice article. Can you explain the basics of a scrambler ? How it works and how we can implement the parallel version of a serial scrambler ?

    • Hi Network Enthusiast,
      I’m sure I can do a basic introduction to scrambling. I don’t have the depth of knowledge on parallel scrambling to do it justice though. Thanks for the feedback.

      Regards,
      John Harrington.

Leave a Reply

Your email address will not be published. Required fields are marked *