Главная страница  Алгебраическая теория кодирования 

[0] [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]

арифметические операции порождают дробно-линейную группу, состоящую из преобразований и -> {аи + Ь) /{си + d), где и GF {п) [j оо, а, Ь, с, d GF {п), ad Ф сЪ. Эта дробно-линейная группа трижды транзитивна: любая упорядоченная тройка может быть переведена в любую другую упорядоченную тройку с помощью преобразования из группы. Для того чтобы это показать, заметим предварительно, что .шюбую упорядоченную тройку можно перевести в (оо. О, 1). Для , этого достаточно перевести первый элемент тройки в О, прибавив к нему подходящий элемент, и сдвинуть его затем в оо путем перехода к обратному. Для перевода второго элемента тройки в О достаточно прибавить к нему подходящую величину. Наконец, третий элемент тройки может быть переведен в 1 путем выполнения соответствующего умножения. Таким образом, дробно-линейная группа содержит преобразование, переводящее любую упорядоченную тройку в (оо, О, 1). Так как в группе содержится и обратное преобразование, то тройка (оо, О, 1) может быть переведена в любую упорядоченную тройку. Следовательно, любой вектор {и, v, w) может быть переведен в произвольный вектор {х, у, z) путем последовательных преобразований {и, V, w) (оо. О, 1) ->- {х, у, z).

Так как единственным преобразованием дробно-линейной группы, оставляющим на месте каждую координату вектора (оо. О, 1), является тождественное преобразование, то порядок этой группы равен N {N - i) {N - 2). Дробно-линейная группа содержит подгруппу индекса 2 всех подстановок вида

и -> {аи -f b)/{cu + d),

где ad - сЪ = i. Ее порядок равен N {N - i) {N - 2)12. Эта подгруппа называется проективной унимодулярной группой. Она порождается подстановками w->w + l; и-> - и~ и и -v аи, где о - примитивный элемент поля GF (п).

Каждый 1-удлиненный двоичный циклический код инвариантен относительно подстановки Са ->- Cui-i, так как эта подстановка есть циклический сдвиг. Согласно теореме 15.25, 1-удлиненный двоичный КВ-код инвариантен также относительно подстановки С- Cu-i, а по теореме 5.81 этот код инвариантен также относительно всех подстановок вида Си ->- Сги, г 6 0- Это дает теорему 15.26.

15.26. Теорема. Каждый i-удлиненный двоичный КВ-код инвариантен относительно дважды транзитивной проективной унимодулярной группы Си-> Cau+b)j(cu+d)> дс и GF {п) и оо, а, Ъ, с, deCF {п), ad - Ьс = 1.

15.27. Следствие. Минимальный вес d расширенного двоичного КВ-кода с блоковой длиной п есть четное число, удовлетворяющее неравенству d > п, если п = -fl mod 8, и неравенству d {d - i) п - i, если п = -1 mod 8.

Следствие 15.27 немедленно вытекает из теорем 15.26, 10.39, 15.22 и 15.23.

В силу следствия 15.27 минимальное расстояние расширенного двоичного КВ-кода с блоковой длиной 23 (кода Голея) равно но меньшей мере 7. Согласно границе сферической упаковки (разд. 13.1), ни один двоичный код с такой же блоковой длиной и скоростью передачи информации не может иметь большее минимальное расстояние, так как () -- (J) + (Sj 23j Поэтому коды Голея

совершенны: на них достигается граница сферической упаковки.

Скорость передачи информации для всех 1-удлиненных КВ-кодов равна R = 1/2. Эти коды включают в себя 1-удлиненный двоичный код Хэмминга с блоковой длиной 8, исправляющий одну ошибку, 1-удлиненный двоичный код Голея с блоковой длиной 27 и 1-удли-иенный троичный код Голея с блоковой длиной 12. Минимальное расстояние, которое гарантирует следствие 15.27, слабо растет с ростом N. Однако КВ-коды часто имеют минимальный вес, превосходящий эту границу. Например, мы видели (теорема 16.33), что минимальное расстояние 1-удлиненного двоичного КВ-кода с блоковой длиной 48 равно 12, а следствие 15.27 гарантирует минимальный вес d = 10.

Так как 2-укороченные КВ-коды также имеют хорошие пара-!\1етры, то много исследований посвящено определению минимального веса 2-удлинепных двоичных КВ-кодов. Лучшие из известных результатов в этом направлении были получены Глизоном, Прейнджем (неопубликовано); Ассмусом, Мэттсоном и Турином [1965, 19661; Плесе [1963] и Карликом [1969]. Большинство из них подытожено на рис. 15.2. Результаты для п 761 получены Ассмусом и Мэттсоном [1966[ на основе хитроумного метода, использующего таблицы круговых чисел, построенные Маскетом. Этот метод позволил им определить кодовые слова малого веса в некоторых КВ-кодах длины /I ~ i mod 4 при больших п.

В общем случае минимальное расстояние КВ-кодов с умеренными блоковыми длинами незначительно лучше минимального расстояния с)авнимых БЧХ-кодов. Однако, к сожалению, КВ-коды значительно труднее декодировать. Теоремы 15.22, 15.23, 15.27 и 16.33 дают нижнюю границу для минимального расстояния некоторых КВ-кодов, но их доказательства пе приводят к реализуемым алгоритмам декодирования.

В общем случае декодеру нет необходимости определять ошибки в проверочных позициях. Это замечание лежит в основе так называемого перестановочного декодирования, введенного Мак-Вильямс [1964]. Декодер подходящим образом переставляет позиции полученного слова до тех пор, пока ошибки не окажутся сдвинутыми в проверочные позиции кода, после чего слово исправляется. Перестановочное декодирование хорошо применять к кодам, инвариантным относи-



1361

1 381

6 841

8 821

21401

30 941

<13

49 921

2 521

8 089

47 521

49 681

<,19

<21

S221

18 541

<23

22 621

<27

25 261

<27

44 269

<31

<,31

1289

<25

6 301

<39

49 057

<41

4 801

15 937

47 713

8 821

9 601

18 433

21 313

34 849

37 057

42 961

48 817

10

<

<

<

< <

<

я -1 12

ге-1 12

ге-1 14

ге-1 16

ге-1 20

ге-1 24

Р и с. 15.2. Минимальное расстояние Хэмминга для некоторых расширенных!

КВ-кодов длины п над GF (д).При ге>761 результаты получены Ассму- сом и Мэттсоном [1966].

тельно большой группы подстановок. Как будет видно из задачи 15.3, некоторые 1-удлиненные КВ-коды инвариантны относительно зна- чительно более мощной группы подстановок, чем проективная унимо* дулярная группа. Однако, как показал Шаугнесси [1968], некоторые! другие 1-удлиненные КВ-коды инвариантны только относительно! простой ) проективной унимодулярной группы. Хотя перестановоч!

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

15.3. Коды Рида - Маллера - слабые коды с легким декодированием

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

Обобщение кодов Рида - Маллера на недвоичный случай было дано Казами, Липом и Питерсоном [1967а].

15.31. Определения. 2-укороченным обобщенным кодом Рида - Маллера порядка г с блоковой длиной п = д" - 1 (обозначается через ОРМ-код) называется циклический код над GF (q), порождающий многочлен которого задается равенством

.OU)(j)<(9-I) m-r. 0«;з<9™-1

где w (/) -- сумма цифр в д-ичном представлении числа /, а а - примитивный элемент поля GF (д").

ОРМ-код порядка г с блоковой длиной N = <f получается из 2-укороченного ОРМ-кода путем добавления единичного вектора к его порождающей матрице.

РЖ-кодом порядка г называется ОРМ-код порядка г над GF (2).

15.32. Св ойства ОРМ-к о д о в,

15.321. РЖ-код порядка г является -удлиненным ВЧХ-кодом с констриктивным расстоянием d = 2".

} == 1, 2, 3,

2""-" - 2, то

1) Простой называется группа, не имеющая нормальных делителей, робнее см., например, Диксон [1901].

конструктивным расстоянием

Доказательство. Если w (/) <:т - г.

15.322. 0РМ-К05 порядка г есть подкод 1-удлиненного ВЧХ-кода с конструктивным расстоянием d = (q - R) qm-Q-i где Q и R - соответственно частное и остаток от деления г на q - \.

Доказательство. Полагая г = Q {q - \) + R, получаем, что {q - \) т - г = {q - i) (jn - Q - \) + q - i - R; w {{q - R] qm-Q-l - i) = (q - i) (m - Q - 1) {q - R - I), но если / = 1, 2, 3, . . ., {q - R) qr-Q-i - 2, то w (j) < {q - 1) m - r.



15.323. Код, дуальный ОРШ-коду порядка г, эквивалентен ОРМ-коду порядка [{q - ]) т - г - 1].

Доказательство.

(g-l) m-reu(3)<(«-l) т. 0<u)(3)<i4-l.

15.324. Число информационных символов РЖ-кода порядка г равно

Доказательство. Существует точно "I j чисел /, таких, что О < / < 2™ и и; {]) = i.

15.325. Число информационные символов ОРШ-кодов порядка г равно

,2 P{i + rn, т, q),

где Р (i т, т, q) - число разбиений числа i т на т слагаемые, каждое из которых не превосходит q.

Доказательство. Количество целых чисел / = 2 }кЯ та-

ft=0

ких, что о < /ft < g для всех А; и 2 /ft = (или 2 (1 + /ft) = i + т) равно Р {i т, т, q).

15.326. ОРМ-ко5 нулевого порядка - код с повторением.

15.327. ОРМ-ко5 первого порядка - i-удлиненный регистровый код максимальной длины.

15.328. ОРМ-кос? порядка [{q - 1) то - 2] есть i-удлиненный ВЧХ-код, исправляющий одну ошибку.

15.329. 0РМ-К05 порядка 1{т - к) {q - 1)] содержит точно

{q-i)q-4[

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

ства GF (д") над GF [q). А именно

С{х) = 1 2 х\

где I, GF (q) \ О и А есть к-мерное аффинное подпространство в GF (д™) над GF (д). Если а°° А, то общая проверка на четность ..адается равенством Соо = ; если а°°А, то = 0.

Утверждение 15.329 является непосредственным следствием теорем 11.64, 11.61 и 11.52. Читатель, пропустивший отмеченные звездочкой разделы в гл. 11, должен принять это предложение без доказательства.

Свойство 15.329 показывает, что минимальное расстояние каждого РМ-кода (и некоторых ОРМ-кодов) не превосходит границы 15.322 для БЧХ-кодов. Используя теорему 11.61, можно доказать, что \гинимальное расстояние каждого ОРМ-кода не превосходит границы для БЧХ-кодов. Так как доказательство этого факта аналогично доказательству теоремы 11.66, то оно опускается.

Согласно 15.327 и 15.328, класс ОРМ-кодов содержит некоторые хорошие коды как для малых, так и для больших скоростей. Однако при умеренных скоростях ОРМ-коды становятся плохими. При чет-пом т минимальное расстояние РМ-кода порядка {т - 1)/2 с блоковой длиной N = 2™ равно d= V2N. Этот код содержит N12 про-]!ерочных символов, а 1-удлиненный БЧХ-код с блоковой длиной N и расстоянием d = y2N - только i -{- {d - 2)12 = 1 -Ь \- {\NI2 - 1) loga N проверочных символов. При iV-> оо РМ-код со скоростью 1/2 обеспечивает такое же минимальное расстояние, как и БЧХ-код со скоростью, стремящейся к 1. Даже при умеренных iV разница весьма существенна. РМ-код третьего порядка длины 128 имеет скорость 64/128, а 1-удлиненный БЧХ-код длины 128, исправляющий 7 ошибок, имеет скорость 78/128. Минимальное расстояние обоих кодов равно 16.

Тем не менее имеются две причины, благодаря которым РМ-коды .шнимают важное место в алгебраической теории кодирования: (1) изучение РМ-кодов дало дополнительную информацию о некоторых связанных с ними БЧХ-кодах; (2) скорость РМ-кодов незначительно меньше скорости сравнимых БЧХ-кодов, но зато РМ-коды .чопускают более легкий алгоритм декодирования.

Кодовые слова любого РМ-кода интересным образом связаны с кодовыми словами РМ-кода первого порядка. Пусть и, и, . . . . ., Um - некоторый базис пространства GF (2"*) над GF (2), а Ai{i = i, 2, . . ., т) - его {т - 1)-мерное подпространство,

состоящее из всех элементов вида 2 jj где Uj GF (2) и С/,- =0.




[0] [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]

0.0146