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

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

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

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

1.8. Модулярное представление блоковых кодов и их эквивалентность

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

Пусть задана специальная матрица  размерности , содержащая в качестве столбцов все возможные векторы из  двоичных элементов, исключая нулевой вектор. Тогда j-й столбец матрицы можно рассматривать как столбец типа j, а код может быть задан вектором, образованным  положительными целыми числами. Пусть, где  – число столбцов типа i.  Известно  [8, 15, 84], что матрица  размерности  в качестве строк содержит все возможные ненулевые линейные комбинации строк матрицы . Следовательно, строками матрицы  являются все ненулевые кодовые векторы.

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

и пусть задана порождающая матрица укороченного кода Хэмминга (6,3,3)

.

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

.

 

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

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

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

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

Пусть  – любая невырожденная матрица размерности . Если  vi и  vj – векторы с  компонентами каждый,   то   vivj (vivj)  есть линейная комбинация строк матрицы , и поскольку строки матрицы  линейно зависимы, то  (vivj)  тогда и только тогда, когда  (vivj)=0. Поэтому если векторы  vi и  vj   не совпадают, то не совпадают и векторы vi и vj. Следовательно, все  строк матрицы  будут различны.

Так как имеется ровно  различных ненулевых векторов, то матрица  должна отличаться от матрицы только расстановкой строк

,

 

где  – некоторая матрица перестановки.

Если  и  – невырожденные матрицы размерности , то

,

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

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

                                   ,      

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

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

Пусть задана перестановка вида

,

с соответствующей матрицей перестановки . Пусть задана порождающая матрица (6,3,3)-кода вида

.

Заметно, что нумераторы столбцов матрицы  совпадают с операндом  перестановки . Результатом произведения  будет новая матрица .

,

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

.

 

Совпадение вторых строк  матрицы   и  следует считать случайным. 

Сравним  результаты произведений    и  :

 

    ;             .

 

                      .                

 

Обе матрицы  и  представляют один и тот же код, но с разными проверочными соотношениями.  Заметно, что весовые значения векторов в  и  распределены не одинаково, поэтому обратные преобразования в   должны в первую очередь соответствовать  весовым  показателям в . Рассмотрим  вектор    vi = из .  Выполнив   vi, получим значение vj = из . Из рис. 1.10 становится ясно, что эквивалентные коды образуют множество подстановок вида

 

!

поскольку  векторы веса  могут перейти только в векторы аналогичного веса, при этом значение !.

Рис. 1.10. Принцип подстановок в эквивалентных кодах

 

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

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

.

После применения подстановки к порождающей матрице кода получим

.

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

 

         и         .

 

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

Весовые показатели остались неизменными, но в первых   столбцах  заметен повтор отдельных наборов, например, 110; 011 и 101. Именно в этом проявляется линейная зависимость строк матрицы  . Поскольку весовые показатели матрицы  остались неизменными, то для получения эквивалентного кода необходимо изменить подстановку (изменить порядок следования столбцов в произведении ). Эту процедуру можно выполнить нескольким путями.

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

.

Во-вторых, возможно получить невырожденную матрицу, если выполнить транспозицию -го элемента подстановки с -м элементом.

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

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

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

Общее число отрицательных исходов может быть найдено из выражения

,

тогда суммирование по всем строкам матрицы   определит общее число  отрицательных исходов

                           при .

Вероятность перехода к итеративным преобразованиям матрицы эквивалентного кода будет определяться как

.

Например, для кода (7,4,3)  с   значение  составит , здесь – весовая матрица порождающей матрицы кода.

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

 

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