Data Coding Theory/Modulo-2 Arithmetic

From Wikibooks, open books for an open world
Jump to: navigation, search

Modulo[edit]

The modulo operation, commonly expressed as a "%" operator, is a useful operation in data coding. What a modulo is, is the remainder of a division operation between two numbers. For instance, if we divide 10 by 3 and we don't calculate decimal points, we get:

\frac{10}{3} = 3

And the remainder would be:

 10 % 3 = 1

In division, we typically have the equation:

s = n \times d + r

Where s is our dividend, d is our divisor, n is our quotient, and r is the remainder. From this equation, we have two operations:

s \div d = n
s % d = r

Notice from these equations that r must always be smaller than d.

Modulo-2 Arithmetic[edit]

Modulo-2 arithmetic is an arithmetic system where every result is taken modulo-2. Here are some examples:

(10 + 5)_{%2} = 1
(2 \times 8)_{%2} = 0

In short, the result of the operation is 1 if the result is odd, and 0 if the result is even. Since we are dealing with individual bits in our data coding, most of our operands will be a 1 or a 0. So long as our operands are 1 or 0, and our results are modulo 2, all the number we write should be 1 or 0.

A common application of modulo-2 arithmetic is in digital circuitry, where logic operations are all performed modulo-2.

Modulo-2 operators[edit]

In our modulo-2 arithmetic system, we define new operators. These operators are frequently very similar to boolean logical operators, so we will discuss those here too.

Add
To add two numbers, we take the modulo-2 of the result. Here is a truth table for an add operation:
+ 0 1
0 0 1
1 1 0
If you are familiar with boolean logic, you will see that addition is identical to the xor operation. Because of this, we will use the terms "add" and "xor" interchangably, and we will denote the modulo-2 addition operation with a "circle-plus":
1 \oplus 1 = 0
Multiply
Multiplication in modulo 2 happens normally, and no new operator needs to be defined. Here is the truth table for a multiplication operation:
× 0 1
0 0 0
1 0 1
This is exactly the same as the boolean "and" operation. We will use the words "multiplication" and "and" interchangably.

Subtraction and division operations are rare in data coding, so we won't discuss them here.