Created
July 25, 2012 13:02
-
-
Save anonymous/3176065 to your computer and use it in GitHub Desktop.
numbering systems section
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
\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 | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment