numbering systems section

numbering systems

\part{Number Systems, Operations, and Codes}

\section{Number Systems}

For most of us we have only ever known one numbering system, decimal
and for that reason it can be easy to overlook the arbitrary nature
of such a system but more importantly it can be easy to overlook the
fact it isn't the only one.


\subsection{Decimal}

The decimal numbering system is the system we use every day to count
our change at stores and measure our lives. We've been taught to add,
subtract, multiply and divide in decimal so we should be pretty comfortable
with it by now.

Decimal has 10 digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9, this is also
known as a base 10 numbering system, meaning each position is weighted
with a factor of 10.

\begin{table}[ht] 
\centering 
\begin{tabular}{|l|c|c|c|c|c|}   
  \hline
  Column Values & 10000 & 1000 & 100 & 10 & 1 \\
  \hline
  Weighted Base & 10\textsuperscript{4} & 
    10\textsuperscript{3} & 10\textsuperscript{2} & 
    10\textsuperscript{1} & 10\textsuperscript{0} \\
  \hline
\end{tabular} 
\caption{Decimal Values} 
\label{tab:Decimal} 
\end{table}

For example: $9280=9*1000(or10^{3})+2*100(or10^{2})+8*10(or10^{1})+0*1(or10^{0})$


\subsection{Binary}

Binary is the language of digital devices it has two digits 0 and
1, this is also known as a base 2 numbering system, meaning each position
is weighted with a factor of 2.

\begin{table}[ht] 
\centering 
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|}   
  \hline
  Column Values & 16 & 8 & 4 & 2 & 1 & $\frac{1}{2}$ &
     $\frac{1}{4}$ & $\frac{1}{8}$ & $\frac{1}{16}$ \\
  \hline
  Weighted Base & 2\textsuperscript{4} & 
    2\textsuperscript{3} & 2\textsuperscript{2} & 
    2\textsuperscript{1} & 2\textsuperscript{0} & 
    2\textsuperscript{-1} & 2\textsuperscript{-2} &
    2\textsuperscript{-3} & 2\textsuperscript{-4} \\
  \hline
\end{tabular} 
\caption{Binary Values} 
\label{tab:Binary} 
\end{table}

For Example: $1011=1*2^{3}+0*2^{2}+1*2^{1}+1*2^{0}$


\subsection{Hexadecimal}

Hexadecimal uses sixteen characters to represent numbers: the numbers
0 through 9 and the alphabetic characters A through F. Large binary
number can easily be converted to hexadecimal by grouping bits 4 at
a time and writing the equivalent hexadecimal character. For example
if we wished to express 1001 0110 0000 11102 in hexadecimal: Group
the binary number by 4-bits starting from the right. Thus, 960E.

Hexadecimal is a weighted number system. The column weights are powers
of 16, which increase from right to left so the process to convert
hex to decimal is similar to our previous methods.

\subsection{Octal}

Octal is also a weighted number system. The column weights are powers
of 8, which increase from right to left. 

\subsection{BCD}

Binary coded decimal (BCD) is a weighted code that is commonly used
in digital systems when it is necessary to show decimal numbers such
as in clock displays. BCD represents each decimal digit with a 4-bit
code. Notice that the codes 1010 through 1111 are not used in BCD. 

\subsection{Gray Code}

Gray code is an unweighted code that has a single bit change between
one code word and the next in a sequence. Gray code is used to avoid
problems in systems where an error can occur if more than one bit
changes at a time.

\subsection{ASCII}

ASCII is a code for alphanumeric characters and control characters.
In its original form, ASCII encoded 128 characters and symbols using
7-bits. The first 32 characters are control characters, that are based
on obsolete teletype requirements, so these characters are generally
assigned to other functions in modern usage. 

%\begin{figure}[p]
%\begin{picture}(150,0)(130,300)
%\includegraphics[scale=0.75]{files/Ascii.png}
%\end{picture}
%\vspace{10cm}
%\caption{Ascii reference table}
%\label{fig:Ascii}
%\end{figure}

\begin{table}[ht]
\centering
\begin{tabular}{|c||c|c|c|c|c|}
\hline
Decimal & Octal & Hexadecimal & Binary & Gray & BCD \\
\hline\hline
0  & 0  & 0 & 0000 & 0000 & 0000      \\
1  & 1  & 1 & 0001 & 0001 & 0001      \\
2  & 2  & 2 & 0010 & 0011 & 0010      \\
3  & 3  & 3 & 0011 & 0010 & 0011      \\
4  & 4  & 4 & 0100 & 0110 & 0100      \\
5  & 5  & 5 & 0101 & 0111 & 0101      \\
6  & 6  & 6 & 0110 & 0101 & 0110      \\
7  & 7  & 7 & 0111 & 0100 & 0111      \\
8  & 10 & 8 & 1000 & 1100 & 1000      \\
9  & 11 & 9 & 1001 & 1101 & 1001      \\
10 & 12 & A & 1010 & 1111 & 0001 0000 \\
11 & 13 & B & 1011 & 1110 & 0001 0001 \\
12 & 14 & C & 1100 & 1010 & 0001 0010 \\
13 & 15 & D & 1101 & 1011 & 0001 0011 \\
14 & 16 & E & 1110 & 1001 & 0001 0100 \\
15 & 17 & F & 1111 & 1000 & 0001 0101 \\
\hline
\end{tabular}
\caption{Numbering System reference table}
\label{tab:numbering}
\end{table}

\section{Arithmetic and Conversions}

\subsection{Binary to Decimal (Decoding)}

To convert from binary to decimal you merely have to add the column
values of all the bits that are 1 and discarding any that are 0.

For Example: 100101.01

\begin{table}[ht] 
\centering 
\begin{tabular}{|l|c|c|c|c|c|c|c|c|c|c|c|}   
  \hline
  Column Values & 32 & 16 & 8 & 4 & 2 & 1 & . & $\frac{1}{2}$ & $\frac{1}{4}$ &&\\
  \hline
  Binary Number & 1 & 0 & 0 & 1 & 0 & 1 & . & 0 & 1 && \\
  \hline\hline
   & 32 &&& 4 && 1 & && .25 & Total & 37.25 \\
  \hline
\end{tabular} 
\caption{Binary to Decimal Conversion} 
\label{tab:Binary2Decimal} 
\end{table}


\subsection{Decimal to Binary (Encoding)}

You can convert from decimal to any other base by repeatedly dividing
by that base, in this case we do left division by two placing the
remainders above.

\begin{figure}[ht] % TODO Replace decimal to binary diagram
\centering 
\includegraphics[width=0.95\textwidth]{files/decimal_to_binary.png} 
\caption{Decimal to binary conversion via division} 
\label{fig:decimal to binary} 
\end{figure}

You can convert a decimal fraction to binary by repeatedly multiplying
the fractional results of successive multiplications by 2 and taking
any carried 1s similar to before.

\begin{figure}[ht] % TODO replace fraction dec to bin diagram
\centering 
\includegraphics [width=0.95\textwidth]{files/decimal_fraction_to_binary.png} 
\caption{Decimal fraction to binary conversion via multiplication} 
\label{fig:decimal fraction to binary} 
\end{figure}


\subsection{Standard Binary Arithmetic}


\subsubsection{Binary Addition}

When adding two binary numbers we follow the rules below:

0 + 0 = 0 Sum = 0, carry = 0

0 + 1 = 0 Sum = 1, carry = 0

1 + 0 = 0 Sum = 1, carry = 0

1 + 1 = 10 Sum = 0, carry = 1

When an input carry = 1 due to a previous result, the rules are:

1 + 0 + 0 = 01 Sum = 1, carry = 0

1 + 0 + 1 = 10 Sum = 0, carry = 1

1 + 1 + 0 = 10 Sum = 0, carry = 1

1 + 1 + 1 = 10 Sum = 1, carry = 1


\subsubsection{Binary Subtraction}

The rules for binary subtraction are 

0 - 0 = 0 

1 - 1 = 0 

1 - 0 = 1 

10 - 1 = 1 with a borrow of 1 


\subsection{Binary Complements and Sign bits}


\subsubsection{1s Complement}

The 1\textquoteright{}s complement of a binary number is just the
inverse of the digits. To form the 1\textquoteright{}s complement,
change all 0\textquoteright{}s to 1\textquoteright{}s and all 1\textquoteright{}s
to 0\textquoteright{}s. For example, the 1\textquoteright{}s complement
of 11001010 is 00110101.

In digital circuits the 1s complement is formed using NOT gates (inverters)
on each of the input lines.

\begin{figure}[ht]
\centering
\begin{circuitikz}
\draw (0,0)   node[not port] (mynot0) {} (mynot0.in) node[anchor=east] {0} (mynot0.out) node[anchor=west] {1} ;
\draw (0,1.2) node[not port] (mynot1) {} (mynot1.in) node[anchor=east] {1} (mynot1.out) node[anchor=west] {0} ;
\draw (0,2.4) node[not port] (mynot2) {} (mynot2.in) node[anchor=east] {1} (mynot2.out) node[anchor=west] {0} ;
\draw (0,3.6) node[not port] (mynot3) {} (mynot3.in) node[anchor=east] {0} (mynot3.out) node[anchor=west] {1} ;
\end{circuitikz}
\caption{NOT gates forming 1s complement}
\label{fig:NOT gates forming 1s complement}
\end{figure}

\subsubsection{2s Complement}

The 2\textquoteright{}s complement of a binary number is found by
adding 1 to the least significant bit of the 1\textquoteright{}s complement.
Recall that the 1\textquoteright{}s complement of 11001010 is 00110101
therefore the twos complement of 11001010 would be 00110110.

\begin{figure}[ht] % TODO Replace 2s via adder diagram
\centering 
\includegraphics [width=0.95\textwidth]{files/2s_via_adder.png} 
\caption{Converting binary to 2s complement via an adder} 
\label{fig:2s via adder} 
\end{figure}

\subsubsection{Signed Binary Numbers}

The most significant bit in a signed number is the sign bit, that
tells you if the number is positive or negative. Computers use a modified
2\textquoteright{}s complement for signed numbers. Positive numbers
are stored in true form (with a 0 for the sign bit) and negative numbers
are stored in complement form (with a 1 for the sign bit). For example,
the positive number 58 is written using 8-bits as 00111010 (true form)
and the negative number -58 is written as 11000110 (complement form).

An easy way to read a signed number that uses this notation is to
assign the sign bit a column weight of -128 (for an 8-bit number).
Then add the column weights for the 1\textquoteright{}s. 

\begin{figure}[ht] % TODO replace signed bin to dec
\centering 
\includegraphics [width=0.95\textwidth]{files/signed_binary_to_decimal.png} 
\caption{Converting negative (signed) binary to decimal} 
\label{fig:signed to decimal} 
\end{figure}

\subsection{Arithmetic Operations with Signed Numbers }

Using the signed number notation with negative numbers in 2\textquoteright{}s
complement form simplifies addition and subtraction of signed numbers.
The rule for addition is to add the two signed numbers. Discard any
final carries and your result will be in signed form.

\begin{figure}[ht] % TODO replace signed adition
\centering 
\includegraphics [width=0.95\textwidth]{files/Addition_signed.png} 
\caption{Addition of signed numbers} 
\label{fig:signed addition} 
\end{figure}

\begin{figure}[ht] % TODO replace signed addition
\centering 
\includegraphics [width=0.95\textwidth]{files/Signed_subtraction.png} 
\caption{Subtraction of signed numbers} 
\label{fig:signed subtraction} 
\end{figure}

Note that if the number of bits required for the answer is exceeded,
overflow will occur. This occurs only if both numbers have the same
sign. The overflow will be indicated by an incorrect sign bit. 

\begin{figure}[ht] % TODO replace overflow diagram
\centering 
\includegraphics [width=0.95\textwidth]{files/Overflow.png} 
\caption{Binary Overflow} 
\label{fig:binary overflow} 
\end{figure}

\newpage