diff options
Diffstat (limited to 'Digital_Communications_by_S._Haykin/Chapter8.ipynb')
| -rw-r--r-- | Digital_Communications_by_S._Haykin/Chapter8.ipynb | 577 |
1 files changed, 577 insertions, 0 deletions
diff --git a/Digital_Communications_by_S._Haykin/Chapter8.ipynb b/Digital_Communications_by_S._Haykin/Chapter8.ipynb new file mode 100644 index 00000000..1b04d843 --- /dev/null +++ b/Digital_Communications_by_S._Haykin/Chapter8.ipynb @@ -0,0 +1,577 @@ +{ + "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 +} |