% looks like it's done! AC 6-7-06 \documentclass[12pt]{article} \usepackage{ifthen,fullpage} \usepackage{graphicx} \usepackage{amsmath} \usepackage{fancyhdr} \pagestyle{fancy} \setlength{\textheight}{8.5in} \headheight 16pt \headsep 12pt \lhead[Numbering Systems]{June 26, 2006} \rhead[June 26, 2006]{Numbering Systems} \begin{document} \section{Lecture plan} \begin{itemize} \item 20 min \begin{itemize} \item Introduce myself, tutors, students \item Hand out the syllabus \item Talk about projects \item Explain lecture notes (handouts with lots of room to write) \item Talk about homework \end{itemize} \item 15 min \begin{itemize} \item Decimal System \item Octal System \item Binary System \end{itemize} \item 25 min Human Computer Activity \item 20 min Base Conversion \begin{itemize} \item To Decimal \item From Decimal (including shortcut) \item Hexadecimal System \end{itemize} \item 20 min Get started on problem set \end{itemize} \newpage \section{The Math Class} \begin{enumerate} \begin{enumeration} \item This is NOT a class related to Calculus! It's applied discrete math. It will give you some tools you'll use in the CS and EE classes. It has some overlapping topic with the CS course... well, I'm in CS after all! In general the class pace will be slower than a typical MIT class: for those of you willing to experience a real MIT-type of class, you'll either have to wait, or you could ask us to overload you with homework :)\\ \item Lectures structure: concept problem, puzzles, student notes, online lecture notes and hw-solutions, Psets (mainly to be solved in class), grading, final project.\\ \item Participation in class: HIGHLY encouraged!! Fill the blanks, 1 or 2 people problem solving, explain solution to the class. At the beginning of each class we'll ask you to pick a new seat next to a new class mate. For that class you'll be teammates and will work together each time (if any) you'll be asked to solve a 2-people in-class problem.\\ \item Goal: expose you to some new material and perhaps some familiar topics too you'll have a chance to dig deeper into. For the ones among you that had covered some of the material I'll be presenting, there will be extra problems made available during the class so that you can still challenge yourself on the topic in discussion in class.\\ \item Collaboration: encouraged to a point: the solutions have to be your own.\\ \item Final project and work group: within a week, you'll be given a set of possible topic for your final project; to these you can add your favorite discrete-math related topics. Then you'll have a week to pick a project and one team mate to develop the project and then present it to the class during the last two lectures. We'll ask you to submit the project abstract and team members by the end of the second week of classes.\\ \item Don't be afraid to ask questions during class or after; we don't expect you to always know the answers to questions asked in class, but rather spend some time thinking about the problem proposed.\\ \end{enumerate} \newpage \section{Lecture Notes} To represent numbers in base n the numbers 0 through n-1 are available for each digit. (in base 10, we use 0-9, in base 2, 0-1) Each digit has a different place holder value: the first digit to the left of the decimal point represents $n^0$ place, the next digit to the left represents the $n^1$ place, the next to the left the $n^2$ place, etc. The pattern also extends in the other direction. The first digit to the right of the decimal point represents the $n^{-1}$ place, the next the $n^{-2}$ place, etc. \subsection{Decimal System} For the decimal system, we're working in base 10 (base is also known as radix). As we said earlier, the numbers 0-9 are used, and each digit is in a powered place: the 1000s place, the 100s place, the 10s place, the 1s place, the 0.1 place, etc. \begin{equation*} 489.36 = \underbrace{4\times10^2 + 8\times10^1 + 9\times10^0 }_{Integer\:Part}+ \underbrace{3\times10^{-1} + 6\times10^{-2}}_{Fraction\:Part} \end{equation*} \subsection{Octal System} The Octal System is base 8, so we use numbers 0-7. Now digits are in the 64s place, the 8s place, 1s place, 1/8 place, 1/64 place, etc. \begin{align*} &563_8 = 5\times8^2 + 6\times8^1 + 3\times8^0 \\ &26.4_8 = 2\times8^1 + 6\times8^0 + 4\times8^{-1} \end{align*} Note: this example is just to show decimal (or octal in this case) points are used. In standard form, octal usually represents only integers \subsection{Binary System} Each binary (base 2) digit is known as a bit. Only two digits, 0 and 1, are used. This system is especially important in digital logic, which we'll be discussed in detail tomorrow and in your electrical engineering class. Typically one byte is 8 bits, and 4 bytes together makes a word (on a 32-bit computer system). The digits are in the places corresponding to powers of 2. In each of the examples below, notice how the notation gets simpler (lazier). \begin{align*} &10110_2 = 1\times2^4 + 0\times2^3 + 1\times2^2 + 1\times2^1 + 0\times2^0 \\ &1101011_2 = 2^6 + 2^5 + 2^3 + 2^1 + 2^0 \\ &101_2 = 4 + 1 \\ &111001_2 = 32 + 16 + 8 + 1 \\ \end{align*} \subsection{Human Computer Activity} %This is an activity from http://imagine.gsfc.nasa.gov/docs/teachers/lessons/slap/slap_main.html.% Explain to students that computers receive signals that are either on (1) or off (0). To demonstrate how a computer reads a number, place seven students in a line for the initial demonstration, and have each student wear a different power of 2 on signs around their necks. For example: First student would have a card with 1 ($2^0$) taped to his or her shirt, second student's card has a 2 ($2^1$) on it. The third student has a 4 ($2^2$), the next student has 8 ($2^3$), the next student has 16 ($2^4$), next is 32 ($2^5$), and the last student's card has 64 ($2^6$). Students are side-by-side with student 1's left hand in his or her pocket. All other students have their left hands facing palm up and their right hands facing palm down. Students' right hands are positioned over the top of their neighbors' left hands. The rule is: do not react unless your left hand has been slapped. If a student's left hand has been slapped, then he or she raises his or her right hand if it is down, or lowers it (slapping the person's hand to his or her right) if it was up. The teacher or a designated student counts out loud numbers from 0 to 32 while the demonstration group models each number. This is very confusing at first and you have to walk students through several numbers before they catch on. After students understand the basics of this activity, ask other groups of seven students to model each number from 0 to 64. (You might want to make this a competition and time each group.) Ask students to notice any patterns. (Student 1 will raise or lower his or her hand every time. His or her hand will be raised for odd numbers and lowered for even numbers.) The second student (2 or $2^1$) raises and lowers his or her hand up for two then down for two. \begin{figure} \centering \includegraphics[width=3in]{human_binary} \end{figure} \newpage \subsection{Converting To Decimal} We've already begun to do this when we talked about octal and binary numbers. To complete the conversion, simply evaluate the sum: \begin{align*} 563_8 &= 5\times8^2 + 6\times8^1 + 3\times8^0 \\ &= 5\times64 + 6\times8 + 3\times1 \\ &= 320 + 48 + 3 \\ &= 371 \end{align*} \subsection{Converting From Decimal} For the new base $n$, remember to only use digits 0 through $n$-1 as we convert a number $x$ to decimal. Determine the highest place holder value (largest power of $n$ that is smaller than $x$), and subtract it out. Continue subtracting out the lower place holder values until you get to $n^0$. For example, convert $231_{10}$ to base 6. 231 is less than $6^4$ ($6^4 = 1296$), so try $6^3$ as the largest place holder. \begin{equation*} 231 = 1\times6^3 + 15 \end{equation*} 15 is less than $6^2$, so use $6^1$ as the next largest place holder. \begin{align*} &15 = 0\times6^2 + 15 \\ &15 = 2\times6^1 + 3 \end{align*} Finally, the largest place holder is $6^0$. \begin{equation*} 3 = 3\times6^0 \end{equation*} So the answer is $231_{10}$ = $1023_6$. \subsection{Converting From Decimal Shortcut} There is an additional method to easily convert numbers from decimal to a different base. We repeatedly divide the decimal number by the base in which it is to be converted, until the quotient becomes zero. As the number is divided, the remainders - in reverse order - form the digits of the number in the other base. For example, if we want to convert $115_{10}$ to base 7: \begin{align*} 115\div7 &= 16\:R\:3 \\ 16\div7 &= 2\:R\:2 \\ 2\div7 &= 0\:R\:2 \end{align*} The result is $223_7$. To check our work: \begin{equation*} 223_7 = 2\times7^2 + 2\times7^1 + 3\times7^0 = 98 + 14 + 3 \end{equation*} \subsection{Hexadecimal System} Hexadecimal is base 16. The numbers 0 though 9 are used, and also the letters A-F. (Remember, each digit, even if its value is greater than 10, can only use one place, and 10 through 15 each use two places, so we need new symbols for these values.) Other bases greater than 10 must use letters in addition to digits as well. Each hexadecimal digit represents 0 to 15. Each four binary digits also represent 0 to 15. We can easily translate binary to hexadecimal by dividing the binary number into blocks of four digits, and translating each of these blocks to hexadecimal. As an example, let's convert 1101011001111001 to hexadecimal without having to go through decimal. \begin{equation*} \underbrace{1101}_{Block 1}\underbrace{0110}_{Block 2}\underbrace{0111}_{Block 3}\underbrace{1001}_{Block 4} \end{equation*} \begin{align*} &1101_2 = D_{16} \\ &0110_2 = 6_{16} \\ &0111_2 = 7_{16} \\ &1001_2 = 9_{16} \end{align*} So in hexadecimal, this number is D679. We can do the same thing translating between binary and any other base that is a power of 2, using a corresponding block size, for example, blocks of size 3 for translating to base 8 ($2^3$=8), blocks of size 2 for base 4 ($2^2$=4), etc.\\ One common use of the hexadecimal system is the definition of RGB colors (e.g. in html pages, proceeded by the pound sign). Each color is expressed as a combination of Red (R), Green (G) and Blue (B). Each red, green or blue component is a numerical value that represents the amount of each color present and is a number between 0 and 255. A shorter way to express a color is by dedicating two hexadecimal digit per color: for example DD0F9A means: R = DD$_{16} = 208 + 13 = 221_{10}$, G = 0F$_{16} = 0 + 15 = 15_{10}$ and B = 9A$_{16} = 144 + 10 = 154_{10}$ which is: 221 of red, 15 of green and 154 of blue. Some standard colors: red is encoded as FF0000, green as 00FF00 and blue as 0000FF; white is FFFFFF, black is 000000, yellow is FFFF00, magenta is FF00FF. \begin{figure}[hb] \centering \includegraphics[width=2in]{dd0f9a_color.pdf} \caption{The color DD0F9A} \end{figure} \end{document}