Mar 092016
 

This is going to be another one of my “selfish” posts – written primarily for me to refer back to in the future and not because I believe it will benefit anyone other than me. The idea is one that I always took for granted but had a hard time proving to myself once I decided to try.

Theorem: Suppose we have an M bit unsigned binary integer with value A. Consider the first (least significant) N bits with value B. Then:

A \equiv B \bmod{2^N}

Put another way, arithmetic with unsigned binary integers of a fixed length N is always performed modulo 2^N.

This is actually true regardless of the radix, but we’ll focus solely on binary numbers since the underlying reason for this post is to study binary representations of integers in digital systems. If our system represents integers using N bits, and a mathematical operation causes an overflow with a result needing M bits, then that answer is congruent to the N bit answer (with overflow discarded) modulo 2^N.

A simple example may help to illustrate this. Let’s add two 4 bit integers: 7 and 13. A 4 bit number can encode 2^4, or 16 integers, 0 through 15. So we won’t have any problem representing the two addends, but we know that the sum, 20, exceeds what we can represent with 4 bits.

\begin{tabular}{cccccc} & 0 & 1 & 1 & 1 & (7)\\ + & 1 & 1 & 0 & 1 & (13)\\ \cline{1-5} \cancel{1} & 0 & 1 & 0 & 0 & (4)\\ \end{tabular}

We see that if we can extend our answer to 5 bits, we’d get the correct sum of 20. Because we are limiting ourselves to 4 bits, we discard the overflow bit that resulted from a carry of the most significant, left-most, bits, and are left with a value of 4.

But to my point, 20 is congruent to 4 modulo 16 (2^4), and, again, in general, arithmetic operations on unsigned binary integers of fixed length N is always performed module 2^N. Now we’ll take a look at why.

Proof

Suppose we have a binary integer with length M and value A. The first (least significant) N bits have a value B. We want to prove:

A \equiv B \bmod{2^N}

Or equivalently:

A \bmod{2^N} = B \bmod{2^N}

Let’s start by defining the difference between A and B as C. So, A – C = B, or equivalently, B + C = A. So,

A \bmod{2^N} = (B + C) \bmod{2^N}

The modular addition rule tell us that:

(B + C) \bmod{2^N} = (B \bmod{2^N} + C \bmod{2^N}) \bmod{2^N}

Substituting for (B + C) \bmod{2^N} gives us:

A \bmod{2^N} = (B \bmod{2^N} + C \bmod{2^N}) \bmod{2^N}

Because B is the value of the first N bits, B must be less than 2^N, and therefore B \bmod{2^N} = B.

Since C is the value of bits N+1 through M, we can define it as the following summation:

    \[C = \sum_{i=N+1}^{M}j_i2^{(i-1)}\]

where j is the value of the ith bit, either 0 or 1.

To determine the value of C \bmod{2^N} we need to divide that summation by 2^N and calculate the remainder.

    \[\sum_{i=N+1}^{M}j_i2^{(i-1)} \div 2^N = \sum_{i=1}^{M-N}j_{N+i}2^{(i-1)}\]

Since \sum_{i=1}^{M-N}j_{N+i}2^{(i-1)} is a whole number, the remainder is 0, and therefore, C \bmod{2^N} = 0. Substituting B and C back in to our original equation gives us:

A \bmod{2^N} = (B + 0) \bmod{2^N}

A \bmod{2^N} = B \bmod{2^N}

Which is the definition of congruence. So, restating the equation as a congruence relation:

A \equiv B \bmod{2^N}

And with that, our proof is complete.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

(required)

(required)