diff options
| author | hardythe1 | 2015-05-05 14:21:39 +0530 |
|---|---|---|
| committer | hardythe1 | 2015-05-05 14:21:39 +0530 |
| commit | 435840cef00c596d9e608f9eb2d96f522ea8505a (patch) | |
| tree | 4c783890c984c67022977ca98432e5e4bab30678 /Elements_of_discrete_mathematics/Chapter10.ipynb | |
| parent | aa1863f344766ca7f7c20a395e58d0fb23c52130 (diff) | |
| download | Python-Textbook-Companions-435840cef00c596d9e608f9eb2d96f522ea8505a.tar.gz Python-Textbook-Companions-435840cef00c596d9e608f9eb2d96f522ea8505a.tar.bz2 Python-Textbook-Companions-435840cef00c596d9e608f9eb2d96f522ea8505a.zip | |
add books
Diffstat (limited to 'Elements_of_discrete_mathematics/Chapter10.ipynb')
| -rwxr-xr-x | Elements_of_discrete_mathematics/Chapter10.ipynb | 353 |
1 files changed, 353 insertions, 0 deletions
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 |