From 435840cef00c596d9e608f9eb2d96f522ea8505a Mon Sep 17 00:00:00 2001 From: hardythe1 Date: Tue, 5 May 2015 14:21:39 +0530 Subject: add books --- Elements_of_discrete_mathematics/Chapter10.ipynb | 353 +++++++++++++++++++++++ 1 file changed, 353 insertions(+) create mode 100755 Elements_of_discrete_mathematics/Chapter10.ipynb (limited to 'Elements_of_discrete_mathematics/Chapter10.ipynb') diff --git a/Elements_of_discrete_mathematics/Chapter10.ipynb b/Elements_of_discrete_mathematics/Chapter10.ipynb new file mode 100755 index 00000000..8b7fc5fa --- /dev/null +++ b/Elements_of_discrete_mathematics/Chapter10.ipynb @@ -0,0 +1,353 @@ +{ + "metadata": { + "name": "", + "signature": "sha256:6e9582656e16b2ddb2a1a599466d473ed1824284ac996f30e627d64aae2d0daa" + }, + "nbformat": 3, + "nbformat_minor": 0, + "worksheets": [ + { + "cells": [ + { + "cell_type": "heading", + "level": 1, + "metadata": {}, + "source": [ + "10 Groups and rings" + ] + }, + { + "cell_type": "heading", + "level": 2, + "metadata": {}, + "source": [ + "Example 09:Page 457" + ] + }, + { + "cell_type": "code", + "collapsed": false, + "input": [ + "print \"(3,4) parity check code.\"\n", + "def parity_checker(word):\n", + " count=0#Initially the number of 1s is zero\n", + " for i in range(0,4):#Ranges till 4 as the size of the received word is 4\n", + " if word[i]!='0':\n", + " count=count+1#Counts the number of 1s in the given code\n", + " \n", + " if count%2==0:#Even weight can only be detected by this checker\n", + " return \"No, error cannot be detected\"\n", + " else:\n", + " return \"Yes, error can be detected\"\n", + "print \"0010-\",parity_checker(str('0010'))\n", + "print \"1001-\",parity_checker(str('1001'))\n" + ], + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": [ + "(3,4) parity check code.\n", + "0010- Yes, error can be detected\n", + "1001- No, error cannot be detected\n" + ] + } + ], + "prompt_number": 1 + }, + { + "cell_type": "heading", + "level": 2, + "metadata": {}, + "source": [ + "Example 10:Page 457" + ] + }, + { + "cell_type": "code", + "collapsed": false, + "input": [ + "print \"(6,7) parity check code.\"\n", + "def parity_checker(word):\n", + " count=0#Initially the number of 1s is zero\n", + " for i in range(0,7):#Ranges till 7 as the received word consists of 7 digits\n", + " if word[i]!='0':\n", + " count=count+1#Counts the number of 1s in the given code\n", + " \n", + " if count%2==0:#Even weight can only be detected by this checker\n", + " return \"No, error cannot be detected\"\n", + " else:\n", + " return \"Yes, error can be detected\"\n", + " \n", + "\n", + "print \"1101010-\",parity_checker(str('1101010'))\n", + "print \"1010011-\",parity_checker(str('1010011'))\n", + "print \"0011111-\",parity_checker(str('0011111'))\n", + "print \"1001101-\",parity_checker(str('1001101'))\n" + ], + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": [ + "(6,7) parity check code.\n", + "1101010- No, error cannot be detected\n", + "1010011- No, error cannot be detected\n", + "0011111- Yes, error can be detected\n", + "1001101- No, error cannot be detected\n" + ] + } + ], + "prompt_number": 2 + }, + { + "cell_type": "heading", + "level": 2, + "metadata": {}, + "source": [ + "Example 11:Page 457" + ] + }, + { + "cell_type": "code", + "collapsed": false, + "input": [ + "print \"Consider (2,6) encoding function\"\n", + "encode=[\"00\",\"01\",\"10\",\"11\"]#Set of data to be encoded\n", + "k=0#Value for filling the distance is initially set to zero\n", + "distance=[\"\" for i in range(7)]#Array that can hold all possible combinations of distance value ie. 6 combinations\n", + "def e(word):#Function that returns the encoded value\n", + " \n", + " if word==\"00\":\n", + " return str(\"000000\")\n", + " elif word==\"10\":\n", + " return str(\"101010\")\n", + " elif word==\"01\":\n", + " return str(\"011110\")\n", + " elif word==\"11\":\n", + " return str(\"111000\")\n", + "def d(word1,word2):\n", + " \n", + " count=0#Variable that counts the number of 1s\n", + " data1=str(e(word1))\n", + " \n", + " data2=str(e(word2))#Convert into string for indexing which facilitates bitwise operation\n", + " \n", + " for i in range(0,6):\n", + " if data1[i]!=data2[i]:\n", + " count=count+1#XOR implementation\n", + " return count\n", + "for i in range(0,4):\n", + " for j in range(i+1,4):\n", + " \n", + " distance[k]=d(encode[i],encode[j])\n", + " print \"d(e(\",encode[i],\"),e(\",encode[j],\"))=\",distance[k]\n", + " k=k+1\n", + "print \"Minimum distance is\",min(distance)#Finds the minimum distance\n", + "print \"Since the minimum distance is\",min(distance),\"the code will detect\",(min(distance)-1),\"or fewer errors\"\n", + " \n", + " \n" + ], + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": [ + "Consider (2,6) encoding function\n", + "d(e( 00 ),e( 01 ))= 4\n", + "d(e( 00 ),e( 10 ))= 3\n", + "d(e( 00 ),e( 11 ))= 3\n", + "d(e( 01 ),e( 10 ))= 3\n", + "d(e( 01 ),e( 11 ))= 3\n", + "d(e( 10 ),e( 11 ))= 2\n", + "Minimum distance is 2\n", + "Since the minimum distance is 2 the code will detect 1 or fewer errors\n" + ] + } + ], + "prompt_number": 3 + }, + { + "cell_type": "heading", + "level": 2, + "metadata": {}, + "source": [ + "Example 12:Page 458" + ] + }, + { + "cell_type": "code", + "collapsed": false, + "input": [ + "print \"Consider (3,9) encoding function\"\n", + "encode=[\"000\",\"001\",\"010\",\"011\",\"100\",\"101\",\"110\",\"111\"]#Set of data to be encoded\n", + "k=0#Value for filling the distance is initially set to zero\n", + "distance=[\"\" for i in range(28)]#Array that can hold all possible combinations of distance value ie. 6 combinations\n", + "def e(word):#Function that returns the encoded value\n", + " \n", + " if word==\"000\":\n", + " return str(\"000000000\")\n", + " elif word==\"001\":\n", + " return str(\"011100101\")\n", + " elif word==\"010\":\n", + " return str(\"010101000\")\n", + " elif word==\"011\":\n", + " return str(\"110010001\")\n", + " elif word==\"100\":\n", + " return str(\"010011010\")\n", + " elif word==\"101\":\n", + " return str(\"111101011\")\n", + " elif word==\"110\":\n", + " return str(\"001011000\")\n", + " elif word==\"111\":\n", + " return str(\"110000111\")\n", + "def d(word1,word2):\n", + " \n", + " count=0#Variable that counts the number of 1s\n", + " data1=str(e(word1))\n", + " \n", + " data2=str(e(word2))#Convert into string for indexing which facilitates bitwise operation\n", + " \n", + " for i in range(0,9):#Since it is a (3,9) encoder\n", + " if data1[i]!=data2[i]:\n", + " count=count+1#XOR implementation\n", + " return count\n", + "for i in range(0,8):#Since there are eight possibilities with three digits\n", + " for j in range(i+1,8):\n", + " \n", + " distance[k]=d(encode[i],encode[j])\n", + " print \"d(e(\",encode[i],\"),e(\",encode[j],\"))=\",distance[k]\n", + " k=k+1\n", + "print \"Minimum distance is\",min(distance)#Finds the minimum distance\n", + "print \"Since the minimum distance is\",min(distance),\"the code will detect\",(min(distance)-1),\"or fewer errors\"\n", + " \n", + " \n" + ], + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": [ + "Consider (3,9) encoding function\n", + "d(e( 000 ),e( 001 ))= 5\n", + "d(e( 000 ),e( 010 ))= 3\n", + "d(e( 000 ),e( 011 ))= 4\n", + "d(e( 000 ),e( 100 ))= 4\n", + "d(e( 000 ),e( 101 ))= 7\n", + "d(e( 000 ),e( 110 ))= 3\n", + "d(e( 000 ),e( 111 ))= 5\n", + "d(e( 001 ),e( 010 ))= 4\n", + "d(e( 001 ),e( 011 ))= 5\n", + "d(e( 001 ),e( 100 ))= 7\n", + "d(e( 001 ),e( 101 ))= 4\n", + "d(e( 001 ),e( 110 ))= 6\n", + "d(e( 001 ),e( 111 ))= 4\n", + "d(e( 010 ),e( 011 ))= 5\n", + "d(e( 010 ),e( 100 ))= 3\n", + "d(e( 010 ),e( 101 ))= 4\n", + "d(e( 010 ),e( 110 ))= 4\n", + "d(e( 010 ),e( 111 ))= 6\n", + "d(e( 011 ),e( 100 ))= 4\n", + "d(e( 011 ),e( 101 ))= 5\n", + "d(e( 011 ),e( 110 ))= 5\n", + "d(e( 011 ),e( 111 ))= 3\n", + "d(e( 100 ),e( 101 ))= 5\n", + "d(e( 100 ),e( 110 ))= 3\n", + "d(e( 100 ),e( 111 ))= 5\n", + "d(e( 101 ),e( 110 ))= 6\n", + "d(e( 101 ),e( 111 ))= 4\n", + "d(e( 110 ),e( 111 ))= 8\n", + "Minimum distance is 3\n", + "Since the minimum distance is 3 the code will detect 2 or fewer errors\n" + ] + } + ], + "prompt_number": 4 + }, + { + "cell_type": "heading", + "level": 2, + "metadata": {}, + "source": [ + "Example 13:Page 458" + ] + }, + { + "cell_type": "code", + "collapsed": false, + "input": [ + "print \"To prove the given set to be a group code\"\n", + "print \"Since 00000 belongs to the set, identity is satisfied\"\n", + "result=[\"\" for i in range(5)]#List that holds the result of xor\n", + "word=['00000','10101','01110','11011']#Initial set of encoded words\n", + "count=0#Variable that counts the number of pairs that satisfies the closure property\n", + "for i in range(0,4):\n", + " for j in range(i+1,4):#Possible combinations of words\n", + " data1=word[i]\n", + " data2=word[j]\n", + " print \"\\n\"\n", + " print data1,\"exor\",data2,\"=\",\n", + " for k in range(0,5):#XOR gate operations\n", + " if data1[k]!=data2[k]:\n", + " result[k]=1\n", + " print result[k],\n", + " else:\n", + " \n", + " result[k]=0\n", + " print result[k],\n", + " result1=''.join(str(e) for e in result)#Converts list to string for comparing purpose\n", + " for r in range(0,4):#Checks if it belongs to the given set of words\n", + " \n", + " if result1==word[r]:\n", + " count=count+1\n", + "if count==6:#Since there are 6 possible pairs of words\n", + " print \"\\nClosure property is satisfied as we found that if x and y belongs to the set, then x xor y also belongs to the set.\"\n", + "else:\n", + " print \"Closure property is not satisfied\"\n", + " \n", + "print \"Associativity can be satisfies and also each element has an inverse.\"\n", + "print \"Hence, it is a group code\"\n" + ], + "language": "python", + "metadata": {}, + "outputs": [ + { + "output_type": "stream", + "stream": "stdout", + "text": [ + "To prove the given set to be a group code\n", + "Since 00000 belongs to the set, identity is satisfied\n", + "\n", + "\n", + "00000 exor 10101 = 1 0 1 0 1 \n", + "\n", + "00000 exor 01110 = 0 1 1 1 0 \n", + "\n", + "00000 exor 11011 = 1 1 0 1 1 \n", + "\n", + "10101 exor 01110 = 1 1 0 1 1 \n", + "\n", + "10101 exor 11011 = 0 1 1 1 0 \n", + "\n", + "01110 exor 11011 = 1 0 1 0 1 \n", + "Closure property is satisfied as we found that if x and y belongs to the set, then x xor y also belongs to the set.\n", + "Associativity can be satisfies and also each element has an inverse.\n", + "Hence, it is a group code\n" + ] + } + ], + "prompt_number": 5 + } + ], + "metadata": {} + } + ] +} \ No newline at end of file -- cgit