Главная > Теория информации и надежная связь
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
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
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
След.
Макеты страниц

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

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

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

4.3. ОБРАЩЕНИЕ ТЕОРЕМЫ КОДИРОВАНИЯ

До сих пор источники и каналы обсуждались в терминах понятий различных энтропий и средних взаимных информаций. Однако в большинстве систем передачи данных взаимная информация представляет меньший интерес, чем вероятность того, что буквы источника неправильно воспроизводятся у адресата. Эта вероятность ошибки определяет содержание основной теоремы теории информации — теоремы кодирования. Для широкого класса источников и каналов эта теорема утверждает, что если энтропия источника на единицу времени меньше, чем пропускная способность канала на единицу времени, то вероятность ошибки может быть сделана сколь угодно малой с помощью использования достаточно сложных кодера и декодера. В этом параграфе нас будет интересовать обращение этого результата: если энтропия источника больше, чем пропускная способность, то нельзя достичь произвольно малой вероятности ошибки.

Рассмотрим вначале последовательность и из букв дискретного источника, изображенного на рис. 4.3.1. Энтропия на букву для последовательности из букв определяется равенством

Как было показано в теореме 3.5.1, для стационарного источника не возрастает вместе с и стремится к пределу при Для дискретного источника без памяти, очевидно, при всех

Рис. 4.3.1. Система связи.

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

Целью системы связи является получение последовательности воспроизводящей последовательность и. Если то считается, что произошла ошибка в 1-й переданном символе. Вероятность такой ошибки определяется совместным ансамблем Средняя вероятность ошибки в последовательности из символов определяется следующим образом:

Математическое ожидание числа ошибок в последовательности равно В последующих главах мы часто будем иметь дело с вероятностью одной или более ошибок в последовательности длины Здесь, однако, мы хотим показать, что надежная передача невозможна, если энтропия источника больше, чем пропускная способность. Таким образом, даже, если бы было показано, что вероятность ошибки в последовательности равна 1 для больших то это бы гарантировало лишь

существование одного ошибочного символа среди или Следовательно, для того чтобы показать, что отлично от нуля в пределе при надо непосредственно рассмотреть а не вероятность ошибки в последовательности.

Начнем с установления соотношений между в частном случае, когда Затем распространим этот результат на случай произвольного наконец, свяжем с пропускной способностью канала.

Теорема 4.3.1. Пусть является совместным ансамблем, в котором выборочные пространства состоят из одних и тех же элементов Пусть является вероятностью того, что случайные величины и и не равны друг другу:

Тогда

где

Рис. 4.3.2. Интерпретация теоремы 4.3.1.


Обсуждение. Функция изображена на рис. 4.3.2. Теорема утверждает, что, если принимает заданное значение, отложенное на оси ординат на рис. 4.3.2, то должно быть не меньше соответствующей абсциссы. Так как то теорема ограничивает с помощью выражения, представляющего собой превышение энтропии источника над средней взаимной информацией. Легко эвристически установить справедливость (4.3.4). Средняя неопределенность и при заданном сможет быть разбита на два члена: первый, представляющий неопределенность, относящуюся к тому, была совершена ошибка или нет при заданном и; и второй, представляющий неопределенность переданной входной буквы в случаях, когда была сделана ошибка. Первый член ограничен сверху значением а второй член — значением, равным умноженным на максимальную неопределенность при условии, что произошла ошибка. Так как неопределенность при условии, что произошла ошибка, состоит в выборе между альтернативами, то второй член ограничен сверху значением

Доказательство. Можно записать как сумму двух слагаемых; одно, включающее пары которые приводят к ошибке,

и и другое, содержащее пары для которых :

Согласно (4.3.3) разность между выражениями, стоящими в разных частях (4.3.4), равна

С помощью неравенства приходим к тому, что правая часть (4.3.7) меньше или равна выражению

Теорема 4.3.2. Пусть обозначает совместный ансамбль последовательностей в котором выборочные пространства для и состоят из одних и тех же элементов Пусть определено в (4.3.2). Тогда


Доказательство. Используя цепное правило для совместного ансамбля [см. равенство (2.2.30)], имеем

Неравенство (4.3.13) следует из общего неравенства [см. неравенство (2.3.13)].

Применяя теорему 4.3.1 к каждому слагаемому в (4.3.13), получаем

Чтобы завершить доказательство теоремы, следует показать, что

Это может быть установлено с помощью неравенства Однако мы не будем вдаваться в детали доказательства, так как (4.3.16) является также простым следствием свойства выпуклости энтропии, которое будет рассмотрено в следующем параграфе.

Мы уже ограничили вероятность ошибки, связанной с источником, с помощью неопределенности Теперь рассмотрим канал в сочетании с источником.

По определению будем считать, что последовательность источника связана с адресатом при N-кратном использовании канала, если совместный ансамбль [соответствующий выходу источника и, входу канала выходу канала и декодированному выходу (сообщению на выходе) обладает тем свойством, что у не зависит от и при условии, что задано не зависит от и их при условии, что задано у.

Для дискретных ансамблей это условие означает, что . В общем случае, как показывает рис. 4.3.1, оно означает, что выход канала статистически зависит от последовательности источника лишь через последовательность на входе канала, а декодированный выход зависит от лишь через выход канала у. Другими словами, эти условия являются математическим выражением того, что нет вспомогательного «скрытого» канала, передающего декодеру информацию о и.

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

Теорема 4.3.3. (Теорема переработки информации.) Пусть последовательность источника связана с адресатом каналом, используемым N раз. Тогда

где [является средней взаимной информацией между последовательностью источника и и декодированной

выходной последовательностью является средней взаимной информацией при Л-кратиом использовании канала.


Доказательство. Первое условие приведенного выше определения совместно с теоремой 2.3.3 дает: Из (2.3.19) теперь получим

Второе условие определения дает используя вновь (2.3.19), имеем

Объединяя (4.3.18) и (4.3.19), получаем (4.3.17).

Из доказанных двух теорем следует, что

где

Если канал является то будем иметь отсюда получаем

Свяжем теперь значения с помощью интервала времени между двумя последовательными буквами источника и интервалом времени между двумя последовательными буквами канала Предположим, что число возможных использований канала задается величиной где означает наибольшее целое число, меньшее или равное х.

Теорема 4.3.4. (Обращение теоремы кодирования.) Пусть дискретный стационарный источник с алфавитом объема имеет энтропию и производит буквы со скоростью одна буква за секунд. Пусть дискретный канал без памяти имеет пропускную способность С и передача по нему ведется со скоростью одна буква за секунд. Пусть последовательность источника длины связана с адресатом каналом, используемым N раз, где

Тогда для любого вероятность ошибки на букву источника удовлетворяет неравенству


Доказательство. Согласно теореме и (4.3.22) является непосредственным следствием (4.3.21).

Для того чтобы дать соответствующую интерпретацию доказанной теореме, рассмотрим как общее время, в течение которого

происходит пёредача. В течение этого времени кодер может использовать кодирование с фиксированной длиной или неравномерное кодирование для источника и блоковое или неблоковое кодирование для канала. Независимо от того, какое кодирование и какая обработка данных производились, средняя вероятность ошибки на символ источника должна удовлетворять (4.3.22) и, таким образом, она отлична от нуля, если (скорость источника) больше, чем (пропускная способность канала на букву источника). Следует заметить, что теорема ничего не говорит о вероятностях ошибок отдельных букв С помощью подходящего выбора кодера и декодера мы можем сделать малым для одних значений I и большим для других.

Хотя теорема в том виде, как она здесь сформулирована, приложима лишь к дискретным каналам без памяти, можно заметить, что это ограничение было использовано только при переходе от (4.3.20) к (4.3.21). Для того чтобы доказать справедливость теоремы для более общих каналов, нужно найти способ определения совместного ансамбля а также определить С таким образом, чтобы в пределе при с». Эта задача будет рассмотрена в § 4.6.

В частном случае канала без шума с буквами во входном и выходном алфавитах условие (4.3.22) является просто обращением теоремы кодирования для источника. Оно отличается от (3.1.20) тем, что ограничивает снизу вероятность ошибки на символ, а не вероятность ошибки в блоке.

Можно заметить, что граница, задаваемая (4.3.22), довольно слабая при большом объеме алфавита источника. Для того чтобы показать, что эта слабость границы неизбежна, построим источник, для которого произвольно велика, а произвольно мала даже при Пусть источник без памяти и его алфавит составляют буквы Пусть сколь угодно малое положительное число и пусть ей при Тогда, если декодер декодирует каждый символ в букву то ошибки появляются только тогда, когда источник вырабатывает буквы, отличные от Таким образом, вероятность ошибки равна Вместе с тем

При любом можно сделать сколь угодно большим, выбирая достаточно большое Можно заметить, что эта «система связи» удовлетворяет условию (4.3.22) с равенством, если

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