Главная > Теоретические основы техники связи
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
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
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
След.
Макеты страниц

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

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

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

СВЕРТОЧНЫЕ КОДИРУЮЩИЕ УСТРОЙСТВА

Сверточные коды для использования в ДСК можно получить кодирующими устройствами, подобными изображенным на фиг. 6.32; эти устройства несколько проще, чем блоковые кодеры. Так же как блоковый кодер, изображенный на фиг. 6.6, рассматриваемый кодер имеет -регистр на К разрядов. Однако у-регистр отсутствует, а вместо сумматоров по модулю 2 имеется только сумматоров, где обычно невелико.

Устройство кодера определяют коэффициенты Как и в блоковых кодерах, равенство означает, что 1-й разряд -регистра связан с сумматором, а равенство означает, что эти разряд и сумматор не связаны. Как и ранее, удобно представить совокупность связей разряда -регистра в виде вектора, который обозначим через

Например, кодирующее устройство, изображенное на фиг. 6.33, у которого определяется коэффициентами

(кликните для просмотра скана)

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

где может быть больше К. До передачи все К разрядов -регистра заполнены нулями. Затем первый символ вектора сдвигается в первый разряд -регистра. Коммутатор, изображенный на фиг. 6.32, считывает один за другим выходные значения сумматоров по модулю 2 и образует из них сигнал для передачи по После считывания и передачи выходного значения сумматора второй символ сообщения сдвигается в первый разряд -регистра, а первый символ во второй разряд этого регистра. Выходные значения сумматоров снова считываютсн и передаются. Эта процедура продолжается до тех пор, пока последний символ вектора не сдвинется в первый разряд -регистра. После этого в -регистр последовательно поступают К нулей, тем самым возвращая его в первоначальное положение. Каждый сдвиг сопровождается считыванием и передачей выходных значений сумматоров; после каждого сдвига число, покидающее разряд -регистра, сбрасывается

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

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

соответствует следующая последовательность на выходе кодирующего устройства:

(Занятые введены здесь для наглядности как указания на сдвиги регистра; они будут опускаться в дальнейшем.)

Обычно в приложениях длина сообщения гораздо больше числа разрядов в -регистре, т. е. Так как при этом «хвост» из нулей, вводимых в -регистр после сообщения гораздо короче самого вектора то отношение числа символов сообщения к числу передаваемых символов приблизительно равно Следовательно, скорость передачи сообщений двоичным сверточпым кодом описанного тина 2) определяется формулой

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

Древовидная структура. Теперь рассмотрим более детально процесс построения выходного кодового слова у по входному сообщению:

Фиг. 6.34. Представление в виде дерева возможных сообщений совокупности входных векторов

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

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

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

Фиг. 6.35. Кодовое дерево для кодера, изображенного на фиг. 6.33 .

перед поступлением в него нового символа сообщения, а состояние -регистра непосредственно после поступления этого символа определяет следующие символов вектора у. Поэтому можно поставить в соответствие верхнему ребру, выходящему из любого промежуточного узла дерева сообщений, передаваемых символов, которые генерирует х-регистр, когда вновь поступивший в него символ сообщения является нулем, а нижнему ребру — символов, генерируемых -регистром, когда вновь поступивший символ является единицей. Записав вдоль каждого ребра дерева сообщений и символов сообщения у, соответствующие данному ребру, получим кодовое дерево. Например, для сообщений длины кодовое дерево, заданное представленным на фиг. 6.33 сверточным кодером, у которого изображено на фиг. 6.35.

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

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

Соотношение по форме аналогично соотношению для блоковых кодов с проверкой на четность

где каждый из -мерных векторов описывает связь между сумматорами по модулю разрядом -разрядпого х-регистра (фиг. 6.6). Однако для снерточных кодов интерпретация иная — они не являются векторами связей.

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

и учитывая, что, согласно соотношению вектор определяет связи разряда -регистра с сумматорами по модулю 2, получим, согласно фиг. 6.32, в качестве результирующего выходного вектора вектор

Здесь символ 0 используется для обозначения -мерного вектора, каждая компонента которого равна нулю. Как и выше, запятые используются для обозначения моментов, когда происходит сдвиг вправо -регистра.

Из фиг. 6.32 и описания операций сверточного кодирования легко понять, что сигнал у, соответствующий сообщению у которого все символы, кроме второго, равны 0, а второй символ равен 1, получается простым сдвигом сигнала, соответствующего сообщению, у которого все символы, кроме первого, равны 0, а первый равен 1. Поэтому сообщению

соответствует сигнал

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

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

Принято называть -мерный вектор

Фиг. 6.36. Представление векторов для сверточного кодера с Пустым клеткам соответствуют нулей. (Десятый столбец, целиком состоящий из нулей, опущен.)

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

ВЕРОЯТНОСТЬ ОШИБКИ

При любых конкретных значениях порождающей последовательности формула выражает выходной вектор у сверточного кодера через значения и входную последовательность Поэтому совокупность возможных выходных векторов может порождаться не только рассмотренным нами сверточным кодером, но и [согласно соотношению ] блоковым кодером с проверкой на четность, в который поступает входной вектор длины и который генерирует выходной вектор длины Определяющая сверточный кодер совокупность (фиг. 6.36) для этого эквивалентного блокового кодера будет являться множеством векторов связей.

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

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

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

Для сверточных кодов трудно (а может быть, и невозможно) использовать при анализе оптимального декодера те же рассуждения, что и при рассмотрении случайного кодирования; это объясняется тем, что последовательные символы влияют на перекрывающиеся сегменты вектора у. Поэтому вместо оптимального мы рассмотрим субоптимальный декодер. Для этого декодера найдем оценку средней по ансамблю вероятности ошибки, которая действительно будет экспоненциально убывать с ростом К. Знакомство с субоптимальной процедурой декодирования послужит введением к пониманию методов последовательного декодирования.

Субоптимальное декодирование. Рассмотрим процедуру декодирования сообщений, закодированных сверточным кодером (предполагается, что число двоичных сообщений передаваемых по ДСК, равно Декодер последовательно принимает решения относительно компонент вектора, поступившего в кодер. Каждое решение зависит только от: а) предыдущих решений и б) отрезка, состоящего из символов принятого вектора сигнала, который непосредственно определяется компонентой Этот отрезок принятых символов обозначим как -мерный вектор а промежуточпыи узел кодового дерева, определяемый числами назовем исходным узлом. Каждый символ декодируется в свою очередь путем определения, для какого из выходящих из исходного узла сегментов кодового слона из К ребер вероятность перехода в максимальна. Для этого, согласно соотношению декодер вычисляет расстояние Хемминга между каждым из таких сегментов кодового слова, состоящих из символов, и Если первое ребро сегмента кодового слова, начинающегося в исходном узле и имеющего минимальное расстояние от оказывается верхним, декодер полагает в противном случае декодер полагает Типичный процесс декодирования для сверточного кода с показан на фиг. 6.37.

Рассмотрим вначале какой-либо сверточный код; последующие подразделы посвящены нахождению оценки для вероятности того, что в последовательности решений субоптимальный декодер сделает по меньшей мере одну ошибку. Обозначим через вероятность ошибки в решении при условии, что исходный узел найдеп правильно. Оценку (безусловной) вероятности найдем, используя следующую цепочку соотношений:

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

(кликните для просмотра скана)

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

Соотношение IV представляет собой верхнюю оценку для средней вероятности того, что при декодировании информационной последовательности из двоичных символов, закодированной сверточным кодером и переданной по ДСК, описанный выше субоптимальный декодер сделает одну или более ошибок. Длина кодовых ограничений равна параметр представляет собой показатель экспоненты вероятности ошибки ДСК, определяемый соотношением

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

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

Если увеличивается, стремится к нулю и неравенства (6.87а) и (6.87б) по существу становятся эквивалентными

Доказательство соотношений I, II, III, IV, которое приведено ниже, несколько перегружено деталями и может быть опущено при первом чтении.

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

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

• Доказательство соотношения II. Чтобы доказать, что вероятность неправильного декодирования символа при правильно найденном

Фиг. 6.38. (см. скан) Структура сегментов кодового слова


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

Структуру передаваемого сегмента из символов можно описать, как это следует из фиг. 6.38, а, формулой

где по определению

Соотношение (6.90а) следует из если «усечь» обе части равенства а следовательно, и каждый из векторов до символов. Легко видеть, что где порождающая последовательность сверточного кодера.

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

Для любого как это видно из рассмотрения фиг. 6.38, б,

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

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

с каждым из сегментов, которые могут быть переданы:

Здесь совокупность символов шума в канале, накладывающихся на мы обозначили как вектор Но решение не изменится, если к и к каждому из векторов прибавить по модулю 2 вектор (обратимая операция!). Прибавим этот вектор. Из соотношений (6.93а) и (6.936) видно, что решение основанное на сравнении с каждым из векторов имеет ту же вероятность ошибки, что и решение для случая переданного сигнала у. Это следует из того, что шумы в канале стационарны, т. е.

Отсюда получим

Если все векторы на входе кодера равновероятны, то

Отсюда, усредняя обе части соотношения получим

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

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

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

• Доказательство соотношения III. Покажем теперь, что для нашего субоптимального приемника

Доказательство этого факта основано на свойстве замкнутости совокупности усеченных сегментов кодового слова Как и в случае блоковых кодов с проверкой на четность, в силу линейности соотношения (6.90а)

так что сумма по модулю 2 любых двух векторов множества также принадлежит Однако для сверточных кодов мы получаем также следующее более сильное свойство замкнутости:

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

тогда как

Кроме того, если вектор принадлежит. при и, принимающем значения на множестве векторов вектор также принимает значения на множестве векторов . С другой стороны, если принадлежит то при V, принимающем значения на множестве векторов вектор также принимает значения на множестве векторов

Субоптимальный декодер определяет, какой из векторов совокупности имеет минимальное расстояние Хемминга от и полагает если этот вектор принадлежит и если он принадлежит

Поэтому если переданный в действительности сигнал принадлежит то решение будет правильным, если в множестве не существует вектора для которого

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

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

Но принадлежит , тогда принимает значении на множестве векторов Поэтому соотношение (6.100) снова является условием появления ошибки. Вероятность того, что наличие шума приведет

к выполнению соотношения (0.100) и, следовательно, к ошибке в решении не зависит от к; тем самым доказательство соотношения III завершено.

• Доказательство соотношения IV. Из результатов предыдущих трех подразделов следует неравенство

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

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

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

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

является РР-вектором, то -мерные векторы [определяемые соотношением также обязательно являются РР-векторами и статистически независимы. Но любое кодовое слово, принадлежащее например соответствует вектору на входе кодера, для которого Следовательно, согласно соотношению (6.90а) и фиг. 6.36, вектор можно записать в виде

где

Каждый из векторов представляет собой сумму по модулю 2 РР-вектора и вектора (заключенного в скобки), статистически независимого от

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

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

Пренебрегая тем, что может быть декодировано правильно, даже если соотношение (6.103) не удовлетворяется (из-за наличия в векторов, отличных от мы найдем верхнюю оценку для вероятности для каждой системы в ансамбле, а следовательно, и для Поэтому не превышает вероятности того, что по крайней мере для одного из РР-векторов, принадлежащих переход в более вероятен, чем переход в переданного сегмента

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

где

и в силу соотношения

Доказательство соотношения IV закончено.

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