[CS61C FA20] Lecture 38.4 - Dependability- Parity, ECC, RAID: Error Detection and Correction — Transcript

Full transcript

1. 0:04[Music]
2. 0:09hello
3. 0:09and welcome back to our dependability
4. 0:11module
5. 0:13so we have just seen how we
6. 0:16introduce parity bits to detect
7. 0:20errors in memory essentially what we did
8. 0:24we increased the hamming distance from
9. 0:26one to two
10. 0:27such that a half of our possible words
11. 0:29that that are stored in memory
12. 0:32are invalid so if we read an invalid
13. 0:36word
14. 0:38we know that there has been at least one
15. 0:41bit
16. 0:41in error but
17. 0:45we don't know which is the correct word
18. 0:48that has been written into a memory
19. 0:49because having distance of two is not
20. 0:52large enough
21. 0:53to help us perform the correction simply
22. 0:57there are multiple words that are
23. 1:00one bit away from correct words
24. 1:04so hamming thought of ways how to add a
25. 1:07little bit more redundancy
26. 1:09in order to perform error correction so
27. 1:12he came up with a concept of error
28. 1:13correction codes
29. 1:15and the minimum distance that he needed
30. 1:17for that is the hamming distance of
31. 1:18three
32. 1:19so there is a class of codes that
33. 1:21performs that they essentially do single
34. 1:24error correction double error detection
35. 1:26or
36. 1:27are also called segment codes
37. 1:30and hamming codes are an example of
38. 1:33those
39. 1:34he actually it's interesting how he
40. 1:38figured that out he was using mechanical
41. 1:40car card
42. 1:41readers on all the uh
43. 1:45style relay computers um and
44. 1:50constantly had errors when reading his
45. 1:53punch cards
46. 1:54so he encoded his inputs such that he
47. 1:57doesn't
48. 1:58have to deal with continuous retries
49. 2:01of reads conceptually here is how it
50. 2:06works
51. 2:06let's say that we have n bits um
52. 2:10to encode and therefore there are two to
53. 2:12the unpossible bit patterns
54. 2:14so for example let's say that we have
55. 2:15eight bits
56. 2:17and therefore there will be possible 256
57. 2:20bit patterns
58. 2:22so you know we can represent that you
59. 2:24know there would be 256 possible
60. 2:27dots in this space
61. 2:30if we pick a subset of those
62. 2:35words as valid code words
63. 2:38any other word would be a word that has
64. 2:41an error
65. 2:42so we would have to come up with some
66. 2:45way of
67. 2:46checking the legality of words and then
68. 2:49we
69. 2:50would perform the error correction by
70. 2:52choosing
71. 2:53the nearest legal code word to that
72. 2:56illegal code word
73. 2:59well you know and we are counting there
74. 3:00the probability that a
75. 3:02shorter bit error pattern is much much
76. 3:05more likely than a longer bit error
77. 3:07pattern so we would like to just
78. 3:09go back to the closest
79. 3:12legal codeword or a valid code word so
80. 3:15if we have the space of 256 possible
81. 3:18codewords and we just pick eight out of
82. 3:20them
83. 3:21generally that is a very sparsely
84. 3:24populated
85. 3:25pattern here and if there is a
86. 3:28bit in error we would essentially go and
87. 3:31snap back
88. 3:32to the closest bit that closest word
89. 3:36that is next
90. 3:39to that invalid code word and that would
91. 3:42be most likely the word
92. 3:43that we have written in in the first
93. 3:46place
94. 3:47let's take a look at a little bit more
95. 3:48illustrative example on a much simpler
96. 3:50case this is a simple
97. 3:52case of and there are eight code words
98. 3:55that correspond to three bits um and
99. 3:58they're here represented
100. 4:00on a cube to show that they're you know
101. 4:02which ones are
102. 4:03actually adjacent to each other and have
103. 4:05a hamming distance so of one
104. 4:07and those that are not adjacent to each
105. 4:09other are going to have
106. 4:11a distance that is greater than one
107. 4:15so if you look uh these that
108. 4:18have um an edge that
109. 4:22the chair and edge they have hamming
110. 4:26distance so one if they're connected
111. 4:27they have a hamming distance one so for
112. 4:29example zero zero zero
113. 4:30and zero zero one are one
114. 4:33bit away from each other
115. 4:37so if you would like to design a code
116. 4:39with a hamming distance of
117. 4:40two that allows us to detect single bit
118. 4:43errors
119. 4:44we would have to pick a half of the
120. 4:47possible code words in here
121. 4:50so we would pick those that have even
122. 4:53parity so 0 0 0
123. 4:551 1 0 1 0 1 and 0 1
124. 4:591. notice that we have basically
125. 5:02avoided picking any of the nearest
126. 5:05neighbors
127. 5:05and this is our parity code
128. 5:09so these code words are invalid
129. 5:12but they're simply just one bit away
130. 5:15from their nearest neighbor so if we
131. 5:17take a look at this
132. 5:18code word zero one zero we do not if we
133. 5:21read that we do not know which one um
134. 5:24which word we actually wrote into the
135. 5:26memory was it as 0 0 0
136. 5:290 1 1 or 1 1 0. there are all three are
137. 5:33equi-probable
138. 5:34so in order to do that we need to have a
139. 5:36little bit in order to be able to
140. 5:38perform
141. 5:38correction we have to have a little bit
142. 5:41more sparsity or a little bit more
143. 5:43redundancy
144. 5:44in our code so um we need to pick
145. 5:47less words so if we reduce the number of
146. 5:50words to a quarter
147. 5:52we can pick the two of them that are on
148. 5:54the opposite edges of this cube
149. 5:57so this would be a zero zero zero
150. 6:00and one one one so we
151. 6:03have two redundant bits out of the
152. 6:07you know we are using only two out of
153. 6:10eight possible patterns
154. 6:13like we are using two redundant bits out
155. 6:15of three
156. 6:16but now if there is an error and if we
157. 6:21read
158. 6:21any of these bits we know
159. 6:24what was the most likely pattern that we
160. 6:27have
161. 6:27written into the memory these
162. 6:31bit patterns 0 1 0 1 0 0
163. 6:34and 0 0 1 are most likely
164. 6:38caused by the word 0 0
165. 6:410 because they have a hamming distance
166. 6:43of 1.
167. 6:45similarly the other three are closer to
168. 6:48one one one
169. 6:50and therefore we would by performing
170. 6:53error correction
171. 6:54we would go back to one one one we're
172. 6:57going to see an example how we do that
173. 6:58after a break see you then