Главная > Высокоскоростная передача сообщений в реальных каналах
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
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
След.
Макеты страниц

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

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

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

5.3. ДЕКОДИРОВАНИЕ СИГНАЛЬНО-КОДОВЫХ КОНСТРУКЦИЙ ПО ЕВКЛИДОВУ РАССТОЯНИЮ

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

нованных на декодировании внешних кодов с исправлением ошибок и стираний или только ошибок, так как последние имеют полиномиальный характер роста сложности от длины кода.

Наиболее естественным и простым является алгоритм декодирования СКК с приемом в целом внутренних сигналов и исправлением ошибок внешними кодами. Легко убедиться, что принятое слово будет декодировано правильно, если квадрат расстояния между переданным и принятым словами удовлетворяет неравенству

причем это справедливо как для CKKI, так и для CKKII.

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

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

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

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

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

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

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

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

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

В результате всех декодирований получаем вектор набор чисел (считаем,

что они упорядочены по убыванию) и векторов

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

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

При декодировании внутреннего кода для нас существенно понятие правильного декодирования

Определение 5.1. Пусть истинный вектор, принятый вектор, а — результат декодирования Тогда скажем, что правильное декодирование, если

В противном случае скажем, что неправильное декодирование.

Каждому вектору апоставим в соответствие число вычисляемое по (5 6), где

Далее алгоритм Чмер ничем не отличается от Чмер. В общем виде независимо от типа конструкции (I или II) алгоритм декодирования будем называть Чмер. Теперь рассмотрим его корректирующие способности.

Утверждение 5.1. Пусть передавалось слово у, а принято слово у. Пусть первые векторов кодов найдены правильно. Тогда если выполняется неравенство

то при использовании алгоритма Чмер строка будет декодирована правильно.

Доказательство утверждения приводится в [19, 85].

Следствие 5.1. Пусть передавалось слово а принято слово у. Декодирование по алгоритму Чер будет правильным, если, квадрат расстояния между переданным и принятым словами удовлетворяет неравенству

Рис. 5.5 Иллюстрация декодирования по алгоритму

Таким образом, видим, что использование данного алгоритма по сравнению с жестким декодированием внешних кодов (5.5) приводит к асимптотическому энергетическому выигрышу 3 дБ.

Пример 5.2 Пусть имеется при с внутренним ансамблем сигналов КАМ16 и внешним корректирующим кодом РМ ( Проиллюстрируем работу алгоритма с Параметры Эта СКК соответствует вектору разбиений и в данном случае не является оптимальной (возможна с вектором разбиений Но данная СКК выбрана потому, что у нее и можно проиллюстрировать все сложности алгоритма

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

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

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

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