Главная > Теория кодов, исправляющих ошибки
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
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
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
След.
Макеты страниц

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

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

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

17.6. ПОСТРОЕНИЕ ЛИНЕЙНЫХ КОДОВ; АНТИКОДЫ

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

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

Замечательный способ построения хороших линейных кодов заключается в следующем надо взять матрицу или несколько экземпляров и вычеркнуть некоторые столбцы (см рис 17 1а и

Вычеркиваемые столбцы сами образуют порождающую матрицу так называемого антикода (согласно Фореллу и др [418, 420, 421], см также [889], [1098] Антикод представляет собой код, у которого расстояния между кодовыми словами ограничены сверху Допускается даже нулевое расстояние между кодовыми словами, и поэтому антикод может содержать одинаковые кодовые слова

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

Пример (1) Матрица

порождает антикод

длины с 23 кодовыми словами и максимальным расстоянием Каждое кодовое слово встречается дважды Аналогично для любого легко строится антикод длины 3 с кодовыми словами и максимальным расстоянием 2

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

Рис. 17.la Использование антикода для построения новых кодов

Рис. 17.lb Случай, когда антикод содержит повторяющиеся столбцы

Пример (2) Если то, вычеркивая из матрицы столбцы антикода из примера (1), мы получим -код

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

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

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

Примеры (3) Вычеркнем прямую (состоящую из трех точек) из матрицы

(4) Образуем для антикод, столбцами которого являются 15 точек проективного подпространства размерности 3 и еще одна точка, не лежащая в этом подпространстве, как изображено на рис. 17.2

Рис. 17.2 Порождающая матрица антикода с параметрами

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

(5) Выберем в проективное подпространство размерности -плоскость), содержащее 31 точку, и -плоскость содержащую 15 точек Эти подпространства пересекаются по плоскости (состоящей из 7 точек) Выберем плоскость которая не пересекается с пересекаются по прямой пересекаются в точке Выберем прямую которая не пересекается с или (и пересекается с в точке Наконец, выберем точку которая не принадлежит ни одному из выбранных В качестве столбцов порождающей матрицы антикода возьмем точек конфигураций Столбцы встречаются в этой матрице дважды Максимальный вес равен Вычеркнем столбцы этого антикода из двух экземпляров матрицы как показано на рисунке

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

Результирующий код имеет параметры и удовлетворяет границе Грайсмера.

Упражнения. (23). Используя прямую и -плоскость в получить аитикод с параметрами следовательно, получить -код.

(24). Построить -код.

Общий метод пдстроения (Соломон и Стиффлер [1257], Белов и др. [102]; см. также Оллтоп [25]). Следующий способ построения антикодов из подпространств обобщает предыдущие примеры и приводит к широкому классу кодов, достигающих границы Грайсмера.

Для заданных положим

где

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

Пересечение любых подпространств В,- пусто. (17.54)

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

размерность минимальное расстояние, определяемое формулой (17.53), и достигает границы Грайсмера. На рис. ПА.2 эти коды обозначаются буквами

Теорема 25. (Белов и др. Описанное построение возможно тогда и только тогда, когда

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

Нам надо показать, что если любое -подмножество множества (когда ) или если (когда ), то Действительно,

так как по условию теоремы

(Достаточность). Предположим, что построение возможно, т. е. условие (17.54) выполняется. Если то ничего доказывать не надо. Предположим, что Тогда согласно (17.54) для любого -множества I выполняется условие . Но в силу упражнения (27)

Следовательно,

Следствие 26. Если для заданных выполняется неравенство

где числа определяются условиями (17.53), то существует -код, достигающий границы Грайсмера.

Заметим, что -код из всех слов четного веса достигает границы Грайсмера. В этом случае Поэтому условия, сформулированные в следствии, не являются необходимыми для того, чтобы код достигал границы Грайсмера. Как показали Баумерт и Мак-Элис [87], для заданного граница Грайсмера достигается при всех достаточно больших

Задача (нерешенная). (17.7). Найти необходимые и достаточные условия, которым должны удовлетворять числа чтобы граница Грайсмера (17.52) была точной.

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

Теорема 27. (Вентурини [1369]; переоткрыто Пейтлом [1027]. Обобщение на см. в работе Пейтла [1028].) Пусть для заданных

где целые положительные числа и или 1, и пусть

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

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

и из (17.55) следует, что

Теперь для каждого такого, что образуем антикод, состоящий из проективного подпространства (в котором точек). Вычеркнем этот антикод из экземпляров матрицы что возможно в силу (17.57). Наконец, добавим произвольных столбцов. Результирующий код имеет длину (согласно (17.58)), размерность и минимальное расстояние (по крайней мере) согласно (17.55).

Упражнение. (25). Показать, что Таким образом, может быть намного меньше чем

Теорема 28. Если -код достигает границы Грайсмера, то не имеет одинаковых столбцов.

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

Обозначим через -код, порожденный матрицей Тогда согласно оценке (17.52)

поэтому код не достигает границы Грайсмера.

Определение. Оптимальным называется антикод наибольшей длины для заданных значений размерности и максимального расстояния 8.

Предположим, что вычеркиваем антикод из соответствующего числа экземпляров симплексного кода. Ясно, что если результирующий код достигает границы Грайсмера, то этот антикод оптимален. Таким образом, описанные выше способы построения дают много оптимальных антикодов, образованных из подпространств. В частности, антикоды, рассмотренные в примерах 3, 4, 5, оптимальны. Форрел и Форрег [420, 421] привели таблицы оптимальных антикодов.

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

Доказательство. По условию теоремы

Из (17.59) и равенства

справедливого для любого —1, вытекает, что

и, следовательно, код достигает границы Грайсмера.

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

Простое геометрическое описание имеют не все оптимальные антикоды. Так, -код из всех слов четного веса

достигает границы Грайсмера. Таким образом, представляет собой оптимальный антикод длины с 2 кодовыми словами и максимальным расстоянием —2. Согласно теореме 29 для всех мы получаем оптимальные антикоды, имеющие кодовых слов, и, следовательно, новые коды, достигающие границы Грайсмера.

Пример. (6).

Первые два антикода состоят из трех точек одной прямой. Однако другие антикоды не имеют подобного геометрического описания. Например, антикод из второго примера состоит из 10 точек и 10 прямых в причем каждая прямая состоит из трех точек и через каждую точку проходят три прямые, как изображено на рис. 17.3. На рисунке изображена конфигурация Дезарга; так она называется потому, что возникает при доказательстве теоремы Дезарга (см. книгу Гильберта и Кон-Фоссена [654, рис. 135, с. 123]).

Рис. 17.3 Конфигурация Дезарга

Задача (нерешенная). (17.8). Имеется ли естественное описание геометрических конфигураций, соответствующих другим оптимальным антикодам?

Упражнение. (26). ([420].) Так как антикод может содержать одинаковые слова, то антикоды можно «объединять», чтобы получать новые.

(a). Построить антикоды с параметрами соответственно.

(b). Показать, что конструкции

(где 0 и 1 обозначают столбцы из нулей и единиц соответственно) образуют антикоды с параметрами

Получить, следовательно, и -коды.

В заключение на рис. 17.4 перечислены некоторые

оптимальные линейные коды с k = 6 (дающие, таким образом, значения

Намного более полную таблицу привели Хелгерт и Стинафф [636].

Рис. 17.4. Оптимальные коды с

Упражнения. (27). ([102].) Пусть — двоичный линейный код для Показать, что

{Указание. Использовать индукцию по .]

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

(29). ([889].) Пусть код имеет порождающую матрицу где А — матрица размера строки которой имеют вес не более единицы, а столбцы имеют четный вес более нуля. Отсюда следует, что Показать, что представляет собой

-код с максимальным весом

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