{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Chapter 8 Error Control Coding"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example8.1 page 384"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "generator matrix\n",
      "[[ 1.  1.  1.  1.  1.]]\n",
      "\n",
      "parity-check matrix\n",
      "[[ 1.  0.  0.  0.  1.]\n",
      " [ 0.  1.  0.  0.  1.]\n",
      " [ 0.  0.  1.  0.  1.]\n",
      " [ 0.  0.  0.  1.  1.]]\n",
      "\n",
      "code word for binary one input\n",
      "[[ 1.  1.  1.  1.  1.]]\n"
     ]
    }
   ],
   "source": [
    "from __future__ import division\n",
    "from numpy import ones,zeros,identity,transpose,hstack,mat\n",
    "\n",
    "n =5# #block of identical 'n' bits\n",
    "k =1# #one bit\n",
    "m = 1## bit value = 1\n",
    "I = identity(n-k) #Identity matrix\n",
    "P = ones(n-k)##coefficient matrix\n",
    "I=mat(I)\n",
    "P=mat(P)\n",
    "H = hstack([I,transpose(P)])##parity-check matrix\n",
    "G = hstack([P, mat([1])])##generator matrix \n",
    "x = m*G# #code word\n",
    "print 'generator matrix\\n',G\n",
    "print '\\nparity-check matrix\\n',H\n",
    "print '\\ncode word for binary one input\\n',x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example8.2 page 386"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "identity matrix Ik\n",
      "[[ 1.  0.  0.  0.]\n",
      " [ 0.  1.  0.  0.]\n",
      " [ 0.  0.  1.  0.]\n",
      " [ 0.  0.  0.  1.]]\n",
      "\n",
      "coefficient matrix P\n",
      "[[1 1 0]\n",
      " [0 1 1]\n",
      " [1 1 1]\n",
      " [1 0 1]]\n",
      "generator matrix G\n",
      "[[ 1.  1.  0.  1.  0.  0.  0.]\n",
      " [ 0.  1.  1.  0.  1.  0.  0.]\n",
      " [ 1.  1.  1.  0.  0.  1.  0.]\n",
      " [ 1.  0.  1.  0.  0.  0.  1.]]\n",
      "parity chechk matrix H\n",
      "[[ 1.  0.  0.  1.  0.  1.  1.]\n",
      " [ 0.  1.  0.  1.  1.  1.  0.]\n",
      " [ 0.  0.  1.  0.  1.  1.  1.]]\n",
      "Code words of (7,4) Hamming code\n",
      "[[ 0.  0.  0.  0.  0.  0.  0.]\n",
      " [ 1.  0.  1.  0.  0.  0.  1.]\n",
      " [ 1.  1.  1.  0.  0.  1.  0.]\n",
      " [ 0.  1.  0.  0.  0.  1.  1.]\n",
      " [ 0.  1.  1.  0.  1.  0.  0.]\n",
      " [ 1.  1.  0.  0.  1.  0.  1.]\n",
      " [ 1.  0.  0.  0.  1.  1.  0.]\n",
      " [ 0.  0.  1.  0.  1.  1.  1.]\n",
      " [ 1.  1.  0.  1.  0.  0.  0.]\n",
      " [ 0.  1.  1.  1.  0.  0.  1.]\n",
      " [ 0.  0.  1.  1.  0.  1.  0.]\n",
      " [ 1.  0.  0.  1.  0.  1.  1.]\n",
      " [ 1.  0.  1.  1.  1.  0.  0.]\n",
      " [ 0.  0.  0.  1.  1.  0.  1.]\n",
      " [ 0.  1.  0.  1.  1.  1.  0.]\n",
      " [ 1.  1.  1.  1.  1.  1.  1.]]\n"
     ]
    }
   ],
   "source": [
    "from __future__ import division\n",
    "from numpy import ones,zeros,identity,multiply,mat,concatenate,hstack,transpose\n",
    "\n",
    "\n",
    "k = 4# #message bits length\n",
    "n = 7# #block length\n",
    "m = n-k##Number of parity bits\n",
    "I = identity(k)  #identity matrix\n",
    "I=mat(I)\n",
    "print 'identity matrix Ik\\n',I\n",
    "P =[[1,1,0],[0,1,1],[1,1,1],[1,0,1]]##coefficient matrix\n",
    "P=mat(P)\n",
    "print '\\ncoefficient matrix P\\n',P\n",
    "G = hstack([P,I]) #generator matrix\n",
    "print 'generator matrix G\\n',G\n",
    "\n",
    "H = hstack([identity(k-1),transpose(P)])##parity check matrix\n",
    "print 'parity chechk matrix H\\n',H\n",
    "\n",
    "#message bits\n",
    "m = [[0,0,0,0],[0,0,0,1],[0,0,1,0],[0,0,1,1],[0,1,0,0],[0,1,0,1],[0,1,1,0],[0,1,1,1],[1,0,0,0],[1,0,0,1],[1,0,1,0],[1,0,1,1],[1,1,0,0],[1,1,0,1],[1,1,1,0],[1,1,1,1]]\n",
    "\n",
    "C = m*G#\n",
    "C = (C%2)#\n",
    "print 'Code words of (7,4) Hamming code\\n',C\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example8.3 page 389"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "remainder in polynomial form: \n",
      "   2\n",
      "1 x + 1 x\n",
      "Parity bits are: [ 1.  1.  0.]\n",
      "G:\n",
      "[1, 1, 0, 1, 0, 0, 0]\n",
      "[0, 1, 1, 0, 1, 0, 0]\n",
      "[0, 0, 1, 1, 0, 1, 0]\n",
      "[0, 0, 0, 1, 1, 0, 1]\n",
      "\n",
      "Generator Matrix G =\n",
      "[1, 1, 0, 1, 0, 0, 0]\n",
      "[0, 1, 1, 0, 1, 0, 0]\n",
      "[1, 1, 1, 0, 0, 1, 0]\n",
      "[1, 0, 1, 0, 0, 0, 1]\n",
      "\n",
      "Partiy Check matrix H =\n",
      "\n",
      "[1, 0, 0, 1, 0, 1, 1]\n",
      "[0, 1, 0, 1, 1, 1, 0]\n",
      "[0, 0, 1, 0, 1, 1, 1]\n"
     ]
    }
   ],
   "source": [
    "from numpy import poly1d, polydiv\n",
    "#message sequence = [1,0,0,1]\n",
    "g = poly1d([1,0,1,1]) #generator polynomial\n",
    "m = poly1d([1,0,0,0])*poly1d([1,0,0,1]) #message sequence\n",
    "q = polydiv(m,g)[0]\n",
    "r = polydiv(m,g)[1]\n",
    "p = r.coeffs\n",
    "print 'remainder in polynomial form: \\n',r\n",
    "print 'Parity bits are:',p\n",
    "\n",
    "def rev_coeffs(x):\n",
    "    X=[]\n",
    "    for i in reversed(x):\n",
    "        X.append(i)\n",
    "    return X\n",
    "\n",
    "\n",
    "G = [rev_coeffs(g.coeffs),rev_coeffs((g*poly1d([1,0])).coeffs),rev_coeffs((g*poly1d([1,0,0])).coeffs),rev_coeffs((g*poly1d([1,0,0,0])).coeffs)]\n",
    "M=len(G[-1])\n",
    "for gg in G:\n",
    "    while len(gg)<M:\n",
    "        gg.append(0)\n",
    "print \"G:\"        \n",
    "for gg in G:\n",
    "    print gg\n",
    "\n",
    "def fun1(a,x,y):\n",
    "    import numpy as np\n",
    "    z=[]\n",
    "    for xx,yy in np.nditer([a[x-1],a[y-1]]):\n",
    "        z.append(xx+yy)\n",
    "    a[x-1]=z\n",
    "    return a    \n",
    "\n",
    "def modulo(a,i):\n",
    "    bb=[]\n",
    "    for aa in a[i-1]:\n",
    "        bb.append(aa%2)\n",
    "    a[i-1]=bb    \n",
    "    return a\n",
    "\n",
    "G=fun1(G,3,1)#G(3,:) = G(3,:)+G(1,:);\n",
    "G=modulo(G,3)#G(3,:) = modulo(G(3,:),2);\n",
    "G=fun1(G,4,1)\n",
    "G=fun1(G,4,2)#G(4,:) = G(1,:)+G(2,:)+G(4,:);\n",
    "G=modulo(G,4)#G(4,:) = modulo(G(4,:),2);\n",
    "print '\\nGenerator Matrix G ='\n",
    "for ggg in G:\n",
    "    print ggg\n",
    "\n",
    "\n",
    "#h = 1+D^-1+D^-2+D^-4;\n",
    "#H_D = [D^4*h;D^5*h;D^6*h];\n",
    "H_D=[poly1d([1,1,1,0,1]),poly1d([1,1,1,0,1,0]),poly1d([1,1,1,0,1,0,0])] \n",
    "\n",
    "\n",
    "#H_num =numer(H_D);\n",
    "#H = coeff(H_num);\n",
    "H=[rev_coeffs(aa.coeffs) for aa in H_D]\n",
    "\n",
    "M=len(H[-1])\n",
    "for hh in H:\n",
    "    while len(hh)<M:\n",
    "        hh.append(0)\n",
    "H=fun1(H,1,3)\n",
    "H= modulo(H,1)        \n",
    "print '\\nPartiy Check matrix H =\\n'\n",
    "for hh in H:\n",
    "    print hh"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example8.4 page 395"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "remainder in polynomial form: \n",
      "   2\n",
      "1 x + 1 x\n",
      "Parity bits are: [ 1.  1.  0.]\n",
      "Table 8.3 Contents of the Shift Register in the Encoder of fig8.7 for Message Sequence(1001)\n",
      "__________________________________________________________________________________________\n",
      "Shift            Input            Register Contents\n",
      "__________________________________________________________________________________________\n",
      "1                  1              1 1 0\n",
      "2                  0              0 1 1\n",
      "3                  0              1 1 1\n",
      "4                  1              0 1 1\n",
      "____________________________________________________________________________________________\n"
     ]
    }
   ],
   "source": [
    "from numpy import poly1d,polydiv\n",
    "#message sequence = [1,0,0,1]\n",
    "g = poly1d([1,0,1,1]) #generator polynomial\n",
    "m = poly1d([1,0,0,0])*poly1d([1,0,0,1])# #message sequence\n",
    "q= polydiv(m,g)[0]\n",
    "r= polydiv(m,g)[1]\n",
    "p = r.coeffs\n",
    "print 'remainder in polynomial form: \\n',r\n",
    "print 'Parity bits are:',p\n",
    "print 'Table 8.3 Contents of the Shift Register in the Encoder of fig8.7 for Message Sequence(1001)'\n",
    "print '__________________________________________________________________________________________'\n",
    "print 'Shift            Input            Register Contents'\n",
    "print '__________________________________________________________________________________________'\n",
    "print '1                  1              1 1 0'\n",
    "print '2                  0              0 1 1'\n",
    "print '3                  0              1 1 1'\n",
    "print '4                  1              0 1 1'\n",
    "print '____________________________________________________________________________________________'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example8.5 page 396"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "remainder in polynomial form : \n",
      "   2\n",
      "2 x + 2 x\n",
      "Syndrome bits for error free codeword are: [0.0, 0.0, 0.0]\n",
      "remainder in polynomial form for errored codeword : \n",
      "   2\n",
      "2 x + 3 x + 1\n",
      "Syndrome bits for errored  codeword are: [0.0, 1.0, 1.0]\n"
     ]
    }
   ],
   "source": [
    "from numpy import poly1d,polydiv\n",
    "\n",
    "#message sequence = [0,1,1,1,0,0,1]\n",
    "\n",
    "g = poly1d([1,0,1,1]) # #generator polynomial\n",
    "C1 = poly1d([1,0,0,1,1,1,0]) #error free codeword\n",
    "C2 = poly1d([1,0,0,0,1,1,0]) #middle bit is error\n",
    "#[r1,q1] = pdiv(C1,g)#\n",
    "\n",
    "q1 = polydiv(C1,g)[0]\n",
    "r1 = polydiv(C1,g)[1]\n",
    "\n",
    "S1 = (r1).coeffs\n",
    "S1 = [xx%2 for xx in S1]\n",
    "print 'remainder in polynomial form : \\n',r1\n",
    "print 'Syndrome bits for error free codeword are:',S1\n",
    "q2 = polydiv(C2,g)[0]\n",
    "r2 = polydiv(C2,g)[1]\n",
    "S2 = (r2).coeffs\n",
    "S2 = [xx%2 for xx in S2]\n",
    "print 'remainder in polynomial form for errored codeword : \\n',r2\n",
    "print 'Syndrome bits for errored  codeword are:',S2"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example8.6 page 399"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "n = 3\n",
      "n-k = 2\n",
      "Code rate:r = k/n = 0.333\n",
      "It can correct any error upto = 2\n"
     ]
    }
   ],
   "source": [
    "from __future__ import division\n",
    "#Single-error-correcting RS code with a 2-bit byte\n",
    "\n",
    "m =2# #m-bit symbol\n",
    "k = 1**2# #number of message bits\n",
    "t =1# #single bit error correction\n",
    "n = 2**m-1# #code word length in 2-bit byte\n",
    "p = n-k# #parity bits length in  2-bit byte\n",
    "r = k/n# #code rate\n",
    "print 'n =',n\n",
    "print 'n-k =',p\n",
    "print 'Code rate:r = k/n = %.3f'%r\n",
    "print 'It can correct any error upto =',(2*t)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example8.7 page 401"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Result:\n",
      "[1.0, 1.0] \n",
      "\n",
      "[1.0, 0.0] \n",
      "\n",
      "[1.0, 1.0] \n",
      "\n",
      "[1.0, 1.0] \n",
      "\n",
      "[0.0, 1.0] \n",
      "\n",
      "[0.0, 1.0] \n",
      "\n",
      "[1.0, 1.0] \n",
      "\n"
     ]
    }
   ],
   "source": [
    "from numpy import convolve,ones\n",
    "g1 = [1,1,1] # The input Top Adder Sequence\n",
    "g2 = [1,0,1] #The input Bottom Adder Sequence\n",
    "m =[1,1,0,0,1] # The message sequence\n",
    "x1 = [round(xx) for xx in convolve(g1,m)]\n",
    "x2 = [round(xx) for xx in convolve(g2,m)]\n",
    "x1 = [xx%2 for xx in x1]\n",
    "x2 = [xx%2 for xx in x2]\n",
    "N = len(x1)\n",
    "x=[]\n",
    "for i in range(0,len(x1)):\n",
    "  x.append([x1[N-i-1],x2[N-i-1]])\n",
    "print 'Result:'  \n",
    "for xx in x:\n",
    "    print xx,'\\n'"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example8.8 page 404"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "top output sequence\n",
      "1 \t1 \t1 \t1 \t0 \t0 \t1 \t\n",
      "bottom output sequence\n",
      "1 \t0 \t1 \t1 \t1 \t1 \t1 \t"
     ]
    }
   ],
   "source": [
    "from numpy import poly1d\n",
    "g1D=poly1d([1,1,1]) #generator polynomial 1\n",
    "g2D=poly1d([1,0,1]) #generator polynomial 2\n",
    "mD=poly1d([1,1,0,0,1]) #message sequence polynomial representation\n",
    "x1D=(g1D*mD) #top output polynomial\n",
    "x2D=(g2D*mD) #bottom output polynomial\n",
    "x1=x1D.coeffs\n",
    "x2=x2D.coeffs\n",
    "x1=x1.tolist()\n",
    "X1=[]\n",
    "for i in reversed(x1):\n",
    "    X1.append(i)\n",
    "X2=[]\n",
    "for i in reversed(x2):\n",
    "    X2.append(i)\n",
    "print 'top output sequence'\n",
    "for xx in X1:\n",
    "    print xx%2,'\\t',\n",
    "print '\\nbottom output sequence'    \n",
    "for xx in X2:\n",
    "    print xx%2,'\\t',"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example8.11 page 409"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "branch metric for correct reception : 0.8822\n",
      "branch metric for any one correct recption: -3.7027\n",
      "branch metric for no correct reception : -8.2877\n"
     ]
    }
   ],
   "source": [
    "from __future__ import division\n",
    "from math import log\n",
    "\n",
    "r = 1/2# #code rate\n",
    "n =2# #number of bits\n",
    "pe = 0.04# #transition probility \n",
    "p = 1-pe## probability of correct reception\n",
    "gama_1 = 2*log(p,2)+2*(1-r)# #branch metric for correct reception\n",
    "gama_2 = log(pe*p,2)+1# #branch metric for any one correct recption\n",
    "gama_3 = 2*log(pe,2)+1# #branch metric for no correct reception\n",
    "print 'branch metric for correct reception : %.4f'%gama_1\n",
    "print 'branch metric for any one correct recption: %.4f'%gama_2\n",
    "print 'branch metric for no correct reception : %.4f'%gama_3"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}