{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "*The following is one of my notes from the course ITI 1100 (Digital Systems) (taken at the University of Ottawa during the winter of 2017). It describes how to convert numbers in any base to base-10 and back again. The course emphasised hand calculation methods (the kind needed on an exam), but I found writing code helped with the learning process.* \n", "\n", "
\n", "\n", "# Base Conversions\n", "\n", "## Converting any Base to Base 10 (i.e. Decimal)\n", "\n", "Given a number and its base, converting to decimal can be achieved by expanding the number into a sum of terms. Each term is the digit multiplied by the base of the number to the exponent of the place value of the digit -1. Written instructions for this process are hard to follow; analyzing examples and trying to write a function to do the conversion helped me get a better handle on how to do these conversions.\n", "\n", "For example, converting the binary number \"111\" into decimal:\n", "\n", "$$ \\begin{align}\n", "(111)_2 &= (1 \\times 2^2) + (1 \\times 2^1) + (1 \\times 2^0) \\\\\n", "&= 4 + 2 + 1 \\\\\n", "&= 7 \\\\\n", "\\end{align} $$\n", "\n", "Python code:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "collapsed": true }, "outputs": [], "source": [ "import math\n", "\n", "def toBase10(n, b):\n", " '''Converts a number (n) in base (b) to base 10'''\n", "\n", " # convert n into a list where each element is a digit in n\n", " # e.g. 111 -> [1, 1, 1]\n", " nS = str(n)\n", " nL = [int(x) for x in nS]\n", "\n", " result = 0\n", " i = len(nL) - 1 # i represents the place value of the digit - 1\n", " for digit in nL:\n", " result+= digit * b**(i)\n", " i -= 1\n", " return result" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "7" ] }, "execution_count": 3, "metadata": {}, "output_type": "execute_result" } ], "source": [ "toBase10(111, 2)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Converting Between Binary, Octal, Decimal, and Hex\n", "\n", "### Whole Number Conversion\n", "\n", "Converting from a higher base to a lower base is more involved.\n", "\n", "One method is to divide the number we are converting by the desired base over and over again until the integer quotient reaches 0. The digits of the converted number can be derived by the value of the remainders (with the hitch that the digits will be backwards unless read from bottom to top).\n", "\n", "Example from [\"Digital Design\" by Mano and Ciletti](https://www.amazon.ca/Digital-Design-5th-Morris-Mano/dp/0132774208) depicting the conversion of 41 (in base 10) to base 2:\n", "\n", "\n", "\n", "The same example, $(41)_{10} \\rightarrow (?)_2$, with Python:" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[1, 0, 1, 0, 0, 1]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "n = 41\n", "digits = []\n", "\n", "# Conversion is complete when n has been integer divided down to 0\n", "while (n != 0):\n", " # Each digit is the remainder of n // 2\n", " digits.append(n % 2)\n", " n = n // 2\n", "\n", "# digits are in reverse order, so set them right\n", "digits.reverse()\n", "digits" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So $(41)_{10} \\rightarrow (101001)_2$.\n", "\n", "### Fractional Conversion\n", "\n", "Now, the above only works for whole numbers. If the number being converted has a fractional part, then the operation becomes a two-step process.\n", "\n", "1. Convert the whole part using the method described previously.\n", "2. Convert the fractional part using the method described next.\n", "\n", "For fractions, we take the fractional part of the number and multiply it by the desired base--this returns an integer and a new fraction. The integer represents the first place digit of the converted number while the fraction can either be discarded or multiplied again to return another integer/fraction pair. Sometimes the fractional part will end as 0.0 and the process will terminate, but most of the time the process can be continued indefinitely (for arbitrary precision).\n", "\n", "Another Mano & Cilleti example:\n", "\n", "\n", "\n", "So the answer is $(0.6875)_{10} = (0.a_1 a_2 a_3 a_4)_2 = (0.10110)_2$.\n", "\n", "Now to do it with code. Note that the fractional part will be represented by a float; this is probably not the best way to do it, but it was enough for my purposes.\n", "\n", "e.g. $(41.23)_{10} \\rightarrow (101001.?)_2$.\n", "\n", "The whole part was determined earlier, so only the fractional part needs to be converted." ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[0.0, 0.0, 1.0, 1.0]" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The decimal fraction we are converting\n", "n = 0.23\n", "\n", "temp = []\n", "\n", "# Storage for converted digits \n", "digits = []\n", "\n", "# The method will be repeated four times\n", "for i in range(4):\n", " # multiply by destination base\n", " n = n * 2\n", " \n", " # split into fractional and integer parts\n", " n_split = math.modf(n)\n", " n_fractional = n_split[0]\n", " n_integer = n_split[1]\n", " \n", " # Save digit and set n to the fractional part\n", " digits.append(n_integer)\n", " n = n_fractional\n", "\n", "\n", "digits" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "So $(41.23)_{10} \\rightarrow (101001.0011)_2$.\n", "\n", "Splitting $n$ into fractional and integer parts is accomplished with [`modf()`](https://docs.python.org/3.5/library/math.html#math.modf), a nifty function from Python's math library.\n", "\n", "Another example with a different base:\n", "\n", "$$(0.513)_{10} \\rightarrow (0.?)_8 $$" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "data": { "text/plain": [ "[4.0, 0.0, 6.0, 5.0, 1.0, 7.0]" ] }, "execution_count": 8, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# The decimal we are converting\n", "n = 0.513\n", "\n", "# Storage for converted digits \n", "digits = []\n", "\n", "# The method will be repeated six times\n", "for i in range(6):\n", " # multiply by destination base (8 this time!)\n", " n = n * 8\n", " \n", " # split into fractional and integer parts\n", " n_split = math.modf(n)\n", " n_fractional = n_split[0]\n", " n_integer = n_split[1]\n", " \n", " # Save digit and set n to the fractional part\n", " digits.append(n_integer)\n", " n = n_fractional\n", "\n", "\n", "digits" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "$$(0.513)_{10} \\rightarrow (0.406517)_8 $$\n", "\n", "### Binary, Octal, and Hex Conversion\n", "\n", "There is a shortcut for converting between binary, octal, and hexadecimal numbers. Since octal and hex have a base that is a power of two, conversion can be done by grouping.\n", "\n", "The following methods are based on the fact that each **octal** digit corresponds to three binary digits and each **hexadecimal** digit corresponds to four binary digits.\n", "\n", "#### Binary -> Octal\n", "\n", "$$(10111110010.001)_2 \\rightarrow (?)_8$$\n", "\n", "Break up into groups of three (*tip*: starting from right-most digit makes this eaiser).\n", "\n", "$$10 \\ 111 \\ 110 \\ 010 \\ . \\ 001$$\n", "\n", "If a group lacks three digits, add a 0 to the left-most place.\n", "\n", "$$010 \\ 111 \\ 110 \\ 010 \\ . \\ 001$$\n", "\n", "Now convert each 3-bit group into its octal equivalent (e.g $(010)_2 = (2)_8$).\n", "\n", "$$2 \\ 7 \\ 6 \\ 2 \\ . \\ 1$$\n", "\n", "The conversion is complete.\n", "\n", "$$(10111110010)_2 \\rightarrow (2762.1)_8$$\n", "\n", "#### Binary -> Hex\n", "\n", "Binary to hexadecimal is handled the same way as Octal, except with groups of four instead of three.\n", "\n", "$$(10111110010.001)_2 \\rightarrow (?)_{16}$$\n", "\n", "Break up into groups of four.\n", "\n", "$$0101 \\ 1111 \\ 0010 \\ . \\ 0010$$\n", "\n", "Note that the fractional group had a zero concatenated from the **right** instead of the **left** (as with groups from the whole part). Remember that we do not want to change the value, just create groups. Adding a zero to the left of a whole number does not change its value ($125 = 0000125$), but this is not true once we move past the decimal point $(0.5 \\ne 0.0005)$. This is obvious, but it's a silly mistake I made typing this out.\n", "\n", "Now convert each 4-bit group into its hexadecimal equivalent. I like to convert to decimal first.\n", "\n", "$$5 \\ 15 \\ 2 \\ . \\ 2$$\n", "\n", "$$5 \\ F \\ 2 \\ . \\ 2$$\n", "\n", "The conversion is complete.\n", "\n", "$$(10111110010)_2 \\rightarrow (5F2.2)_{16}$$\n", "\n", "#### Octal/Hex -> Binary\n", "\n", "Converting to binary from octal or hex is just the same procedure described above except done backwards. Starting with an octal/hex value, convert each digit into its binary equivalent, and then concatenate the binary groups together." ] } ], "metadata": { "anaconda-cloud": {}, "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.6.0" } }, "nbformat": 4, "nbformat_minor": 1 }