Cyclic Redundancy Check (CRC) - Part 1 — Transcript

Full transcript

1. 0:00hello everyone welcome back to the next
2. 0:02lecture in the computer Network series
3. 0:04and we are now in the last error
4. 0:07detection technique the cyclic
5. 0:09redundancy check CRC in part 1 we will
6. 0:13be focusing on the sender side that is
7. 0:15the CRC generation let's start the
8. 0:18session with the outcomes what we are
9. 0:21going to learn in today's session in
10. 0:23today's session we are going to know the
11. 0:25types of error detection I am we are
12. 0:27going to understand how to generate the
13. 0:29CRC the generation of CRC is mainly the
14. 0:33responsibility of the sender let's start
15. 0:36the session by knowing the types of
16. 0:38error detection we have basically for
17. 0:40error detection methods in the previous
18. 0:43lectures we have discussed VRC LRC and
19. 0:45checksum the final error detection
20. 0:48method is the CRC that is the cyclic
21. 0:51redundancy check and we know that any
22. 0:53error detection technique we are going
23. 0:55to append the redundant bits with the
24. 0:57message because this redundant bit only
25. 1:00will enable the receiver to detect
26. 1:02whether there is an error or not so
27. 1:05likewise CRC is also going to generate
28. 1:07some bits and these bits are called as
29. 1:10the redundant bits and in this technique
30. 1:12these redundant bits are specifically
31. 1:14called as CRC let's solve a problem now
32. 1:18find the CRC for the data block one
33. 1:21double zero one double zero with the
34. 1:24divisor one one zero one the protocols
35. 1:27that the sender and the receiver
36. 1:29mutually agree upon will decide the
37. 1:31divisor so the divisor will be known to
38. 1:33the sender the receiver so based on the
39. 1:36divisor the crc is going to be
40. 1:38calculated or the crc is going to be
41. 1:41generated in the sender side and
42. 1:43verified in the receiver side now for
43. 1:45time being let's assume the divisor is 1
44. 1:481 0 1 and we are given with the data
45. 1:51block that is 1 0 0 1 0 0 let's look at
46. 1:55the generation of crc in the sender side
47. 1:57formerly the crc generation of the
48. 1:59sender side involves 4 steps basically
49. 2:01step number 1 find the length of the
50. 2:05divisor
51. 2:05and we are naming it as l and after
52. 2:08finding the length of the divisor in
53. 2:10step number 2 we are going to append L
54. 2:14minus 1 bits to the original message
55. 2:16suppose if the length of the divisor is
56. 2:195 then we are going to append 4 bits to
57. 2:22the original message don't get confused
58. 2:24this appending 4 bits to the original
59. 2:27message is not the crc for doing the
60. 2:29operation we are going to append L minus
61. 2:311 bits to the original message and then
62. 2:34perform binary division operation so we
63. 2:37have a divisor and we have a message
64. 2:39that is appended with L minus 1 bits now
65. 2:42let's start performing the binary
66. 2:44division after performing the binary
67. 2:46division we will get two results one is
68. 2:49the quotient another one is the
69. 2:51remainder then whatever we get as the
70. 2:53remainder that's the crc and please note
71. 2:57we are appending L minus 1 bits so the L
72. 3:01minus 1 bits must be the CRC code
73. 3:03suppose if we are appending four zeros
74. 3:06then four bits must be the CRC bits and
75. 3:09when we want to perform the binary
76. 3:12division operation we must be knowing
77. 3:14about the exclusive or operation so we
78. 3:17will just have a recapture on exclusive
79. 3:19or operation
80. 3:21and B are the two variables so the
81. 3:23possibilities for a and B in binaries
82. 3:25are 0 0 0 1 1 0 and 1 1 we are gonna
83. 3:31perform a XOR B that is a exclusive
84. 3:33orbit B so for same inputs it won't
85. 3:37produce any output so for 0 0 and 1 1
86. 3:40there will be 0 output for different
87. 3:44inputs we will get 1 as the output so
88. 3:47this is the logic behind exclusive odd
89. 3:49you may be wondering we are actually
90. 3:52going to perform binary division
91. 3:53operation only what is the need for
92. 3:55knowing about exclusive odd you will
93. 3:58understand the significance of exclusive
94. 4:00or when we see an example let's see an
95. 4:02example
96. 4:03in the question message is given and the
97. 4:06divisor is given just in the binary
98. 4:08division operation just place the
99. 4:10divisor here and the message here what
100. 4:13is this part this is the divisor and
101. 4:16what is this part this is the message on
102. 4:18top of this we will be getting the
103. 4:21quotient at the bottom will be getting
104. 4:23the remainder now step number 1 just
105. 4:26recall step number 1 how many number of
106. 4:28bits are there in the divisor we have
107. 4:31four bits so L is equal to 4 here so L
108. 4:35is equal to 4 means how many zeros we
109. 4:37are going to append L minus 1 that is 3
110. 4:40zeros are appended to the message so
111. 4:42this is our message and three zeros we
112. 4:45are appending with the message after
113. 4:47appending the zeros let's start the
114. 4:49binary division how many times it is
115. 4:51going to divide one time 1 1 0 1 1 times
116. 4:55is 1 1 0 1 now let's start the division
117. 4:59actually polynomial division this binary
118. 5:01division involves exclusive or operation
119. 5:04and that's why in the previous slide I
120. 5:07just recaptured the exclusive or
121. 5:09operation for same input 1 1 will be
122. 5:11getting 0 for same input 0 0 will be
123. 5:14getting 0 for different input will be
124. 5:16getting 1 and will be ignoring this
125. 5:19anyway it has no role to play in the
126. 5:21operation so the answer for this is same
127. 5:24input 0 0 different input 1 we will
128. 5:28ignore this then the division involves
129. 5:30bringing the next bit so the next bit is
130. 5:33brought here now how many
131. 5:351:01 will be dividing this one time 1 1
132. 5:390 1 1 x is 1 1 0 1 let's perform the
133. 5:42exclusive or operation this is going to
134. 5:45be 1 0 1 0 and we'll be ignoring this
135. 5:49and we'll be getting 1 0 1 let's bring
136. 5:52this bit here now when we bring this bit
137. 5:55here how many times 1 1 0 1 takes it
138. 5:58takes one time when we do the exclusive
139. 6:00or operation and we get 1 1 1 because
140. 6:04for different inputs will be getting 1
141. 6:06now let's bring the next bit how many
142. 6:09times 1 time 1 1 0 1 now the answer is 0
143. 6:141 1 yes as usual let's bring the next
144. 6:18bit now we are required to use the
145. 6:20number of times it is dividing but when
146. 6:23we observe here this is starting with 0
147. 6:25anyway this has no role but this is 0
148. 6:29this is starting with 0 so we'll be
149. 6:31putting a 0 now when we divide it is
150. 6:33going to be 1 1 0 and bring the next bit
151. 6:37divide it 1 times and we'll be getting 1
152. 6:401 0 1 and finally we are getting the
153. 6:43remainder as 0 0 1 and what is start 0 0
154. 6:471 it is actually the remainder in fact
155. 6:51in CRC this is the CRC code
156. 6:54so this CRC code only is going to be
157. 6:56appended with the original message now
158. 6:59let's see what's the CRC 0 0 1 is the
159. 7:02CRC let's check it out yes 0 0 1 is the
160. 7:06CRC and what is the actual message it's
161. 7:091 0 0 and 1 0 0 and this CRC is going to
162. 7:13be appended with the message just C 1 0
163. 7:160 1 0 0 this is what the actual message
164. 7:19and we are appending 0 0 1 this is the
165. 7:22data part that is the original message
166. 7:24what is the other part this is the CRC
167. 7:26part so the actual data that is
168. 7:28transmitted is 1 double 0 1 double 0 0 0
169. 7:321 and that's it guys there is a homework
170. 7:35problem for you just try this find the
171. 7:38CRC for one one one double 0 1 0 1 0 1
172. 7:43with the divisor X cubed plus x squared
173. 7:46plus 1 is anything
174. 7:49your Takeo yes we are finding something
175. 7:51new here instead of having binary digits
176. 7:54as the divisor we are having a
177. 7:56polynomial expression
178. 7:58no worries guys I will be providing you
179. 8:00a hint to solve this the hint is just
180. 8:03take this if we are given a polynomial
181. 8:06like X power 7 plus X power 5 plus x
182. 8:09squared plus X plus 1 just see one
183. 8:13because we have X 7 here do we have X
184. 8:16power 6
185. 8:17no so place a 0 here so X power 6 is
186. 8:20taking 0 do we have X power 5 yes put a
187. 8:231 here
188. 8:24do we have X power 4 here No so put a 0
189. 8:27do we have X cube here no so put a 0 do
190. 8:31we have x squared yes
191. 8:33we have X square so put a 1 do we have X
192. 8:36power 1 yes so we put a 1 here
193. 8:39do we have X power 0 anything power 0 is
194. 8:421 do we have any constant here yes if we
195. 8:45have a constant put a 1 so try this and
196. 8:48solve this problem
197. 8:49post your answers in the comment section
198. 8:52I hope you guys enjoyed the session and
199. 8:54thank you for watching
200. 8:56[Applause]
201. 8:58[Music]
202. 9:02you
203. 9:06[Music]