{
 "metadata": {
  "name": ""
 },
 "nbformat": 3,
 "nbformat_minor": 0,
 "worksheets": [
  {
   "cells": [
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "# Theory of Coding: Maximum-Likelihood Decoding\n"
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "First define the code $C_1$ as listed in the problem, consisting of eight codewords."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "C1 = [0b00000, \n",
      "      0b00111,\n",
      "      0b01001,\n",
      "      0b01110,\n",
      "      0b10011,\n",
      "      0b10100,\n",
      "      0b11010,\n",
      "      0b11101]"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 1
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Verify that this works. The [format string](https://docs.python.org/2/library/string.html#formatspec) specifies that we should zero-pad the output, it should be five characters wide, and use the binary (base 2) representation."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for each in C1:\n",
      "    print format(each, '05b')  # print leading zeros, width 5, binary representation"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "00000\n",
        "00111\n",
        "01001\n",
        "01110\n",
        "10011\n",
        "10100\n",
        "11010\n",
        "11101\n"
       ]
      }
     ],
     "prompt_number": 6
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "Python seems more painful for bitwise math than I'd like. Perhaps there is an easier way to return a specific bit in the string, but for our purposes it's easiest to AND with a 1 in the proper spot, then move that bit over to the right and return it only. We could do it as a boolean (if it's greater than zero) but that would probably increase the complexity of working with the return value. So we'll just do the math instead."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def bit5(num, pos):\n",
      "    # assume num is codeword in form a1a2a3a4a5 where each a is bit\n",
      "    return (num & (1 << 5-pos)) >> 5-pos"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 67
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "print format(C1[4], '05b')\n",
      "for b in range(1, 6):\n",
      "    print bit5(C1[4], b)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "10011\n",
        "1\n",
        "0\n",
        "0\n",
        "1\n",
        "1\n"
       ]
      }
     ],
     "prompt_number": 68
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## 1: Parity check for $C_1$\n",
      "\n",
      "Verify that every codeword $a_1a_2a_3a_4a_5$ in $C_1$ satisifies the following two parity-check equations: $$a_4 = a_1 + a_3$$ $$a_5 = a_1 + a_2 + a_3$$"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "for word in C1:\n",
      "    print bit5(word, 4) == bit5(word, 1) ^ bit5(word, 3), bit5(word, 5) == bit5(word, 1) ^ bit5(word, 2) ^ bit5(word, 3)"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "True True\n",
        "True True\n",
        "True True\n",
        "True True\n",
        "True True\n",
        "True True\n",
        "True True\n",
        "True True\n"
       ]
      }
     ],
     "prompt_number": 69
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## 2: Designing $C_2$\n",
      "\n",
      "Let $C_2$ be the following code in $\\mathbb{B}^6$. The first three positions are the information positions, and every codeword $a_1a_2a_3a_4a_5a_6$ satisifies the parity-check equations\n",
      "$$a_4 = a_2$$ $$a_5 = a_1 + a_2$$ $$a_6 = a_1 + a_2 + a_3$$."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def bit6(num, pos):\n",
      "    # assume num is codeword in form a1a2a3a4a5a6 where each a is bit\n",
      "    return (num & (1 << 6-pos)) >> 6-pos"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 70
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "*(a)* List the codewords of $C_2$."
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "C2 = []\n",
      "for info in range(0, 8):\n",
      "    word = info << 3\n",
      "    C2.append(word + \\\n",
      "              (bit6(word, 2) << 2) + \\\n",
      "              ((bit6(word, 1) ^ bit6(word, 2)) << 1) + \\\n",
      "              bit6(word, 1) ^ bit6(word, 2) ^ bit6(word, 3))\n",
      "    print format(C2[-1], '06b') "
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "000000\n",
        "001001\n",
        "010111\n",
        "011110\n",
        "100011\n",
        "101010\n",
        "110100\n",
        "111101\n"
       ]
      }
     ],
     "prompt_number": 97
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "*(b)* Find the minimum distance of the code $C_2$."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "From the text:\n",
      "\n",
      "> The *distance* between two binary words is the number of positions in which the words differ... The *minimum distance* in a code is the smallest distance among all the distances between two pairs of codewords.\n",
      "\n",
      "We calculate the *distance* as the weight of the sum of the two words. So we add each pair of codewords in $C_2$ (using bitwise XOR). To calculate their weight in Python, "
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def weight(n):\n",
      "    return bin(n).count(\"1\")"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 98
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mindist = 999\n",
      "for w1 in range(0, 8):\n",
      "    for w2 in range(0,8):\n",
      "        if w1 == w2:\n",
      "            continue\n",
      "        dist = weight(C2[w1] ^ C2[w2])\n",
      "        mindist = min(dist, mindist)\n",
      "print mindist"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2\n"
       ]
      }
     ],
     "prompt_number": 100
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "*(c)* How many errors in any codeword of $C_2$ are sure to be detected? Explain.\n",
      "\n",
      "The minimum distance of 2 means that we will detect any one error, but sometimes two errors can go undetected. This is because two errors (bit flips) may in fact change the codeword into another \"valid\" codeword."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "## 3: Designing a code in $\\mathbb{B}^4$\n",
      "\n",
      "Design a code in $\\mathbb{B}^4$ where the first two positions are information positions. Give the parity-check equations, list the codewords, and find the minimum distance."
     ]
    },
    {
     "cell_type": "markdown",
     "metadata": {},
     "source": [
      "$$a_3 = a_1 ; a_4 = a_1 + a_2$$"
     ]
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "def bit4(num, pos):\n",
      "    # assume num is codeword in form a1a2a3a4 where each a is bit\n",
      "    # in \"real\" code we would have made all of these one function where width is a parameter\n",
      "    return (num & (1 << 4-pos)) >> 4-pos"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [],
     "prompt_number": 103
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "C3 = []\n",
      "for info in range(0,4):\n",
      "    word = info << 2\n",
      "    C3.append(word + \\\n",
      "              (bit4(word, 1) << 1) + \\\n",
      "              (bit4(word, 1) ^ bit4(word, 2)))\n",
      "    print format(C3[-1], '04b')"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "0000\n",
        "0101\n",
        "1011\n",
        "1110\n"
       ]
      }
     ],
     "prompt_number": 111
    },
    {
     "cell_type": "code",
     "collapsed": false,
     "input": [
      "mindist = 999\n",
      "for w1 in range(0, 4):\n",
      "    for w2 in range(0,4):\n",
      "        if w1 == w2:\n",
      "            continue\n",
      "        dist = weight(C2[w1] ^ C2[w2])\n",
      "        mindist = min(dist, mindist)\n",
      "print mindist"
     ],
     "language": "python",
     "metadata": {},
     "outputs": [
      {
       "output_type": "stream",
       "stream": "stdout",
       "text": [
        "2\n"
       ]
      }
     ],
     "prompt_number": 112
    }
   ],
   "metadata": {}
  }
 ]
}