[CS61C FA20] Lecture 38.5 - Dependability- Parity, ECC, RAID: ECC Example — Transcript

Full transcript

1. 0:04[Music]
2. 0:08hello and welcome back to our
3. 0:09dependability module
4. 0:11so we have seen that there do exist
5. 0:12codes that not only can detect
6. 0:15errors but can also correct them
7. 0:19but the example that we have shown is
8. 0:21not a very practical one because it has
9. 0:23a lot of
10. 0:24of of overhead in order to
11. 0:28encode what was worth one bit of
12. 0:30information
13. 0:31we used three bits so we had 200
14. 0:35overhead there the trick here and the
15. 0:38science is
16. 0:39how to design these codes such that we
17. 0:42get the desired coverage with minimal
18. 0:45amount of overhead
19. 0:47and desired coverage here is said that
20. 0:50single error detection
21. 0:52single error correction with double
22. 0:55error detection
23. 0:56so hamming came up with those codes as
24. 0:59well
25. 1:01and here is how it goes we will start
26. 1:04with data bits the result of our
27. 1:05calculation
28. 1:07and we are going to interleave parity
29. 1:10bits with those data bits to
30. 1:12form the code word that we're going to
31. 1:13store in the memory
32. 1:15in this case there is a particular
33. 1:19algorithm how
34. 1:20they are being put together
35. 1:24so here is how the interleaving works
36. 1:28on top of this table here we have bit
37. 1:30positions
38. 1:31of the code words that are going to be
39. 1:35stored in the memory
40. 1:36one two three four five and so on and
41. 1:39then
42. 1:40it below that encoded data bits
43. 1:43are sitting at particular bit positions
44. 1:46d1 is at position 3
45. 1:48d5 isn't at position
46. 1:52d2 is at position 5 d3 is positioned at
47. 1:54position 6 and so on
48. 1:56and these other bit positions
49. 2:00are occupied by the parity bits p1 p2 p4
50. 2:03p8 p16 and this is done
51. 2:07in a particular way such that parity
52. 2:09bits are essentially always at bit
53. 2:11positions that correspond
54. 2:12to powers of two so these are bit
55. 2:15positions
56. 2:16um that in binary correspond to 1
57. 2:201 0 1 0 0 relatively easy to remember
58. 2:25but then on the bottom here in this
59. 2:28table is shown
60. 2:30which data bits are covered by which
61. 2:33particular parity bit so
62. 2:38the first parity bit p1 covers all
63. 2:41positions that have an lsb equal to one
64. 2:44so
65. 2:45all odd bits are covered by the first
66. 2:47parity bit
67. 2:48so if we include the p1 in that position
68. 2:52it is going to also cover itself and
69. 2:54produce
70. 2:55um and and even parity
71. 2:58so um essentially every other
72. 3:02bit is included in the first parity what
73. 3:04does it mean included
74. 3:05these are basically inputs in the next
75. 3:07or gate that are generating
76. 3:09p1 p2
77. 3:13covers all bit positions that have
78. 3:17the bit that is next to the least
79. 3:20significant one equal to one
80. 3:21so these are essentially pairs of these
81. 3:24pink fields
82. 3:25that correspond you know d1
83. 3:29and the 3 and 4
84. 3:32and so on and then p3
85. 3:35covers groups of 4 and so on
86. 3:39and this can continue indefinitely but
87. 3:40in practice we generally do this for a
88. 3:42block
89. 3:43so if you have a data word that is eight
90. 3:46bits
91. 3:47wide we would add four parity bits
92. 3:51to encode it let's take a look at the
93. 3:54example of how we actually do that
94. 3:57so we are going to generate these parity
95. 3:59bits
96. 4:01to create even parity for each group
97. 4:03let's say that we would like to
98. 4:05encode a byte of data there are eight
99. 4:07bits in this word here
100. 4:09so we are going to create a coded word
101. 4:11by placing the data bits where they
102. 4:13should be and then we leave
103. 4:15those spaces for our calculated parity
104. 4:18bits
105. 4:19so the these parity bits should be
106. 4:21placed in their appropriate bit
107. 4:23positions
108. 4:24so the first bit first parity bit goes
109. 4:27into a bit position one
110. 4:29so let's calculate them let's go through
111. 4:30that example so
112. 4:32position one is going to be checking
113. 4:34bits one three five
114. 4:36seven nine and eleven
115. 4:40so we are going to mark those bits in
116. 4:43yellow
117. 4:43and count how many ones are there one
118. 4:47two three four therefore
119. 4:50in order to make even parity that parity
120. 4:52bit should be equal to zero
121. 4:54in position 2 it is going to be checking
122. 4:56pairs of bit
123. 4:582 3 6 7
124. 5:0110 11. how many
125. 5:04ones are there there are three therefore
126. 5:07in order to make it even parity we
127. 5:08should make this question mark
128. 5:10equal to one
129. 5:13then we take a look at position four
130. 5:16checks
131. 5:17markup appropriate bits we have only one
132. 5:21uh one among the yellow bits therefore
133. 5:24that should be also equal to one and
134. 5:27finally
135. 5:28um for position eight checks we have the
136. 5:30last
137. 5:31four bits that participate in that xor
138. 5:33there are two ones among them therefore
139. 5:35this question mark should be equal to
140. 5:37zero all right
141. 5:39so this is our final code word
142. 5:43it consists of the data word and the
143. 5:46parity checks
144. 5:48but let's you know don't look at the
145. 5:50correct answer let's suppose we receive
146. 5:52something and we'd like to decode
147. 5:54if the the word is correct if it is not
148. 5:56correct we'll like to
149. 5:57correct it so suppose we receive this we
150. 6:00will map it
151. 6:01to appropriate bit positions and we'll
152. 6:03find out that the bit zero one in the
153. 6:06first two bit positions are parity bits
154. 6:07there is another one over here there is
155. 6:09a parity bit
156. 6:10p4 and finally there is a parity bit p8
157. 6:13at the bit position 8. the rest are the
158. 6:16data bits
159. 6:17let's figure out if the bit if the work
160. 6:19is correct
161. 6:20so we receive this and we're going to
162. 6:23run the parity checks well
163. 6:25for the first parity check we're going
164. 6:26to figure out all the bits that you know
165. 6:28parity bit and the data bits that
166. 6:29correspond in that check
167. 6:31and the number is even so it's good it
168. 6:33passes
169. 6:35the second one has this the p2 parity
170. 6:39has one two three four five once so it's
171. 6:43not good it's not correct
172. 6:44that one does have
173. 6:48an error
174. 6:51then we are going to check the bit p4
175. 6:54it has two ones in that check so that is
176. 6:57going to be correct that
177. 6:58that check is going to be fine and
178. 7:01finally
179. 7:02p8 bit is an error because it has three
180. 7:05ones
181. 7:06and then there is a very simple way how
182. 7:08we calculated which
183. 7:09bit position is the error and you can
184. 7:11work out the algebra it's very simple
185. 7:13it's very uh elegant
186. 7:15um it this implies that the bit position
187. 7:17is equal to the sum
188. 7:19of the two parity bits p2 and p8
189. 7:22so the the error is going to bit be in
190. 7:25the
191. 7:25bit position 10. what should we do to
192. 7:27fix that
193. 7:28we just go ahead and flip that in
194. 7:30correct bit turn it into a zero
195. 7:33then we decode this
196. 7:37to make sure that it is correct
197. 7:39miraculously
198. 7:40all the checks are satisfied and we have
199. 7:43decoded
200. 7:44the correct word very well
201. 7:47now what should we do if
202. 7:51we have to deal with systems that have
203. 7:53that can have more than one bit in error
204. 7:56so if you look at high-end
205. 7:59microprocessors they typically use
206. 8:01seg codes single error correction double
207. 8:05error detection but some of the server
208. 8:07processors
209. 8:08were that they're working with more
210. 8:10valuable work though loads
211. 8:12are going to have protection for to
212. 8:15to to perform correction on two bits
213. 8:18so there is a different type of a
214. 8:21hamming code that is called
215. 8:22double error detection triple error
216. 8:24detection
217. 8:26or dicted we're not going to go into it
218. 8:31and you know there are plenty of
219. 8:32references of that
220. 8:34but generally when we work with
221. 8:36something that is noisier than
222. 8:37microprocessors like
223. 8:38sending data over wi-fi or network
224. 8:40transmissions and so on
225. 8:42we are going to see a lot more errors
226. 8:45and these errors are often going to be
227. 8:47bursty and we are going to see different
228. 8:49ways how
229. 8:49redundancy is added there are generally
230. 8:54things that we're going to encounter
231. 8:56there
232. 8:57like cyclic error correction
233. 9:01for their correction and
234. 9:05things like interleaving to break up
235. 9:08these patterns
236. 9:09and attack them with codes that can
237. 9:12cover fewer errors but that's way
238. 9:18past the content of this course
239. 9:22that is it um this is all what we are
240. 9:25going to cover here
241. 9:26regarding correction of soft errors and
242. 9:29that is typically something that we are
243. 9:31going to do in the memory
244. 9:33we are going to see a different view of
245. 9:36redundancy
246. 9:37just after a quick break