{ "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 }