Главная > Кодирование с исправлением ошибок в системах цифровой связи
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
След.
Макеты страниц

Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

2.1.7. Задача о взвешивании монет

К настоящему времени уже введены основные понятия теории двоичных групповых кодов. Здесь разумно сделать паузу и закрепить эти понятия, рассмотрев ряд примеров. Классической задачей, непосредственно связанной с теорией кодов Хемминга, является так называемая задача о взвешивании монет.

Предположим, имеются восемь монет и весы без гирь и известно, что одна из этих монет является фальшивой. Фальшивая

монета по внешнему виду не отличается от настоящих, но имеет другую массу. Вам нужно найти фальшивую монету с помощью всего трех взвешиваний. Решение, которое легко найти, рассматривая проверочную матрицу -кода Хемминга, состоит в следующем.

Прежде всего занумеруем монеты числами от 1 до 8, и пусть первые 7 из них соответствуют столбцам матрицы Н для -кода Хемминга:

При первом взвешивании нужно взять монеты 1, 2, 3 и 5 (первая строка проверочной матрицы) и положить по две монеты на каждую чашу. При этом неважно, как распределить монеты по чашкам. Если весы находятся в равновесии, то фальшивой является одна из монет 4, 6, 7 или 8, а если они не находятся в равновесии, то фальшивой является одна из монет 1, 2, 3 или 5. Таким образом, после одного взвешивания удается исключить ровно половину возможностей. При втором взвешивании нужно взять монеты 1, 2, 4 и 6 и повторить эксперимент. Равновесие снова означает, что фальшивой является одна из монет 3, 5, 7 или 8, а отсутствие равновесия означает, что фальшивой является одна из монет 1, 2, 4 или 6 Результат этого взвешивания вместе с результатом предыдущего исключает еще две возможности. Например, если весы оба раза оказывались в равновесии, то фальшивой является либо монета 7, либо монета 8, поскольку только они не участвовали ни в одном взвешивании. Наконец, при последнем взвешивании следует взять монеты 1, 3, 4 и 7. Результат этого взвешивания однозначно определяет фальшивую монету. Процесс станет ясным, если рассмотреть дерево решений, показанное на рис. 2.1.

Из рис. 2.1 видно, что каждый возможный исход соответствует одному из столбцов матрицы Н, если интерпретировать равновесие как 0, а неравновесие как 1. Таким образом, множество результатов взвешиваний образует синдром и каждый синдром отвечает одной из возможных фальшивых монет. Единственное различие между задачей о взвешивании монет и задачей декодирования состоит в том, что при взвешивании заранее известно, что одна из монет является фальшивой, а при декодировании может оказаться, что все символы приняты верно. В любом случае мы пытаемся выделить одно из восьми возможных событий. Если бы существовал канал, в котором всегда появлялась одна ошибка, то можно было бы использовать код Хемминга длиной 8 и аналогия была бы полной.

Приведенный пример показывает очень важное свойство хороших кодов. Каждая проверка на четность организована таким

Рис. 2.1. Дерево решений для задачи о взвешивании монет: фальшивая монета

образом, чтобы получить максимальную информацию о положении ошибки. Таким образом, при первой проверке исключается половина возможных символов, при следующей — половина оставшихся и т. д. Большинство кодов, конечно, оказываются не столь эффективными; однако при построении кодов для различных специальных применений следует пытаться использовать этот принцип.

1
Оглавление
email@scask.ru