Содержание к диссертации
Введение
1. Комбинаторное декодирование линейных блоковых кодов 12
1.1. Декодирование по обобщенным информационным совокупностям 12
1.1.1. Понятие обобщенной информационной совокупности. Алгоритм декодирования 13
1.1.2. Построение т-покрытий из кодовых слов 17
1.1.3. Таблица декодеров по обобщенным информационным совокупностям 21
1.2. Табличное декодирование 24
1.2.1. Синдромное декодирование 25
1.2.2. Декодирование по информационным совокупностям 26
1.2.3. Декодирование в надкодах 28
1.2.4. Комбинирование алгоритмов декодирования 30
1.2.5. Декодирование кодов с большой группой симметрии 35
1.2.6. Декодирование квадратично-вычетных кодов 38
1.3. Асимптотика 43
1.3.1. Обзор алгоритмов декодирования линейных блоковых кодов для декодеров с жесткими решениями 43
1.3.2. Сложность декодирования линейных блоковых кодов 48
1.4. Выводы
2. Алгебраическое декодирование 59
2.1. Алгебраическое декодирование по обобщенным информационным совокупностям 59
2.1.1. Основные понятия и определения 60
2.1.2. Укорочения (Ь,д)-кодов 61
2.1.3. Применение декодирования укороченных (Ь5,#5)-кодов 64
2.2. "Генетическая" связь алгебраических методов декодирования 66
2.2.1. Основные понятия и определения 67
2.2.2. Алгоритм Гао 68
2.2.3. Оригинальный алгоритм Велча - Берлекэмпа 70
2.2.4. Интерпретация Чамберса 71
2.2.5. Алгоритм Велча - Берлекэмпа в частотной области 72
2.2.6. Вывод алгоритма Гао 72
2.2.7. Расширенный алгоритм Евклида 73
2.2.8. Корректность алгоритма Гао 74
2.2.9. Пример 78
2.2.10. Замечания к разделу 81
2.3. Декодирование в надкодах 82
2.3.1. Основные определения 82
2.3.2. Дополнительные тождества 84
2.3.3. Алгоритм исправления трех ошибок 85
2.3.4. Декодирование свыше конструктивного расстояния на основе надкодов 89
2.3.5. Пример 91
2.4. Выводы
3. Вычисление дискретного преобразования Фурье над конечным полем 95
3.1. Вычисление корней многочлена 95
3.1.1. Алгоритм быстрого поиска корней многочлена 97
3.1.2. Результаты моделирования 100
3.1.3. Специальные разложения многочленов 101
3.1.4. Гибридный метод 104
3.1.5. Аналитические методы вычисления корней многочленов степени до четырех 106
3.1.6. Сравнение методов вычисления корней многочлена 111
3.21 Циклотомический алгоритм 112
3.2.1. Основные понятия и определения 112
3.2.2. Быстрое вычисление преобразования Фурье 115
3.2.3. Пример 119
3.2.4. Сравнение сложности алгоритмов БПФ 124
3.3. Рекуррентный метод 124
3.3.1. Основные понятия и определения 126
3.3.2. Алгоритм Рейдера 128
3.3.3. Свойства матрицы эквивалентного преобразования 130
3.3.4. Упорядочение чисел из полной системы вычетов 134
3.3.5. Быстрое вычисление ДПФ 139
3.3.6. Примеры вычисления ДПФ 142
3.4. Вычисление синдрома 152
3.4.1. Вычисление неполного ДПФ с помощью циклотомического алгоритма 152
3.4.2. Вычисление неполного ДПФ с помощью рекуррентного метода 160
3.5. Выводы 165
4. Декодирование по кодовым решеткам 166
4.1. Представления кодов с заданной группой симметрии 166
4.1.1. Две конструкции кодов 166
4.1.2. Приведение матриц кода к квазициклическому представлению 1 4.2. Циклические замкнутые решетки 173
4.3. Звездные решетки
4.3.1. Представление кода Голея в виде звездной решетки 177
4.3.2. Декодирование кода Голея по звездной решетке 182
4.3.3. Замечания к разделу 184
4.4. Декодирование кодов Рида - Соломона по звездным
решеткам 184
4.4.1. Разложение Варди - Беэри 184
4.4.2. Метод декодирования 188
4.5. Выводы 190
5. Вопросы реализации 191
5.1. Приложение методов быстрого декодирования линейных блоковых кодов к системам связи 191
5.1.1. Многошаговое декодирование итеративных кодов Хэмминга 192
5.1.2. Результаты моделирования
5.2. Схема вычисления ДПФ 198
5.3. Реализация циклотомического алгоритма вычисления ДПФ на программируемой логической интегральной схеме 201
5.4. Выводы 206
Заключение 207
Библиографический список 209
- Таблица декодеров по обобщенным информационным совокупностям
- Основные понятия и определения
- Алгоритм быстрого поиска корней многочлена
- Декодирование кода Голея по звездной решетке
Введение к работе
Актуальность проблемы. В настоящее время обмен информацией при помощи технических средств происходит практически во всех областях человеческой деятельности. Обработка информации в приемно-передающих устройствах средств связи осуществляется с помощью алгоритмов кодирования и декодирования, а также быстрого вычисления дискретного преобразования Фурье, что позволяет повысить эффективность работы систем связи. Содержанием настоящей диссертационной работы являются теоретические и прикладные исследования системных связей и закономерностей функционирования систем передачи информации для различных отраслей народного хозяйства с использованием современных методов обработки информации. Для решения ряда научно-технических проблем, осуществляемых в настоящее время, необходимо повысить эффективность анализа обработки информации, надежность и качество используемых технических систем, применяющих современные методы кодирования и декодирования.
Для обеспечения помехоустойчивости передаваемой информации применяют корректирующие коды. Теория кодов, исправляющих ошибки, возникла в середине XX века. С момента возникновения теория была разделена на два направления, изучающие блоковые коды (которые рассмотрены в диссертационной работе) и сверточные коды. Теория блоковых кодов, в свою очередь, содержит комбинаторную и алгебраическую теории кодирования. В 60-е годы прошлого века были введены комбинаторные и алгебраические алгоритмы декодирования. Комбинаторные алгоритмы декодирования применимы ко всем линейным блоковым кодам и исправляют ошибки, если их число не превосходит корректирующей способности кода, однако имеют относительно большую сложность. Алгебраические алгоритмы декодирования проще комбинаторных, но они применимы только для некоторых классов кодов. Приложение алгоритмов декодирования сверточ-ных кодов для декодирования блоковых кодов привело к появлению новых методов декодирования блоковых кодов по кодовым
решеткам.
Корректирующие коды получили широкое применение в задачах обработки, передачи, записи, хранения и защиты информации. В настоящее время блоковые коды представлены в многочисленных технических приложениях, например, в стандартах CCSDS 101.0-В-б (Consultative Committee for Space Data Systems), ITU-T G.975.1 (International Telecommunication Union) и IEEE 802.16 (The Institute of Electrical and Electronics Engineers).
Передача информации с применением корректирующих кодов требует эффективных методов декодирования. В диссертационной работе рассматриваются алгоритмы быстрого декодирования. Под быстрым алгоритмом понимают детальное описание вычислительной процедуры, которая существенно уменьшает количество операций по сравнению с прямым методом вычисления.
Таким образом, разработка новых методов в теории кодирования, позволяющих увеличить надежность обработки, передачи, записи, хранения и защиты информации, является актуальной задачей.
Цель диссертационной работы. Целью настоящей работы является разработка методов быстрого декодирования линейных блоковых кодов на основе теоретических методов системного анализа, оптимизации и обработки информации.
Для достижения поставленной цели в работе исследуются следующие основные задачи.
-
Задача построения декодеров для ряда лучших кодов с наименьшей сложностью среди известных декодеров.
-
Задача построения эффективных декодеров алгебраических кодов.
-
Выявление взаимосвязи различных алгебраических методов декодирования.
-
Методологическая задача вывода и доказательства корректности алгоритма Гао.
-
Задача построения эффективных методов вычисления корней многочленов над конечным полем.
6. Задача построения алгоритмов с низкой вычислительной
сложностью для вычисления преобразования Фурье над конечным полем.
-
Задача построения новых типов решеток для линейных блоковых кодов.
-
Задача построения декодеров кодов Рида - Соломона по кодовым решеткам.
Методы исследования. Для решения поставленных задач в работе использовались методы системного анализа, оптимизации и обработки информации, теории кодирования, комбинаторного анализа, алгебры, теорий групп, конечных полей, матриц. При построении таблиц проводились вычисления с помощью ЭВМ.
Научная новизна работы. Научная новизна работы заключается в следующем.
-
Введены понятия обобщенной информационной совокупности и табличного декодирования, на основе которых построены декодеры для ряда лучших кодов с наименьшей сложностью среди известных декодеров.
-
Разработаны алгебраические методы укорочения кодов, на основе которых предложены эффективные декодеры алгебраических кодов.
-
Выявлена взаимосвязь различных алгебраических методов декодирования, а также представлен оригинальный вывод и доказательство корректности алгоритма Гао.
-
Предложены эффективные методы вычисления корней многочленов над конечным полем.
-
Представлены алгоритмы с низкой вычислительной сложностью для вычисления преобразования Фурье над конечным полем.
-
Разработан новый тип звездных решеток для линейных блоковых кодов.
-
Разработан метод декодирования кодов Рида - Соломона по кодовым решеткам.
Практическая ценность работы. Практическая ценность работы состоит в том, что разработка основных вопросов диссертации позволила:
предложить простые алгоритмы декодирования для ряда хороших кодов;
в несколько раз ускорить алгебраические алгоритмы декодирования.
Результаты диссертационной работы использованы в научно-исследовательских работах и внедрены в ряде организаций. Использование результатов подтверждено соответствующими актами.
Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на:
XI Международном симпозиуме по проблеме избыточности в информационных системах (СПб, 2007);
Международных конференциях по алгебраической и комбинаторной теории кодирования (АССТ, 1990-2006);
Международном симпозиуме по теории информации (ISIT, Лозанна, 2002);
а также на семинарах:
— кафедры информационных систем и кафедры безопасности
информационных систем Санкт-Петербургского государственно
го университета аэрокосмического приборостроения;
— кафедры распределенных вычислений и компьютерных
сетей Санкт-Петербургского государственного политехнического
университета;
— на постоянно действующем семинаре по теории кодирования
Института проблем передачи информации РАН (Москва).
Публикации. По теме диссертации опубликовано более 50 печатных трудов в научно-технических журналах, сборниках докладов и научно-технических сборниках, в том числе: монография, 14 статей в журналах, включенных в Перечень ВАК, и авторское свидетельство СССР.
Основные положения диссертации, выносимые на защиту.
-
Метод декодирования по обобщенным информационным совокупностям и табличное декодирование.
-
Метод декодирования алгебраических кодов на основе ал-
гебраических методов укорочения кодов.
-
Взаимосвязь различных алгебраических методов декодирования.
-
Эффективные методы вычисления корней многочленов над конечным полем.
-
Алгоритмы вычисления преобразования Фурье над конечным полем.
-
Метод построения звездных решеток для линейных блоковых кодов.
-
Метод декодирования кодов Рида - Соломона по кодовым решеткам.
Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы. Работа содержит страниц машинописного текста, а список использованной литературы содержит 116 наименований.
Таблица декодеров по обобщенным информационным совокупностям
Декодирование по информационным совокупностям, предложенное в работе [105], применимо ко всем линейным кодам и имеет различные модификации, исследованные в работах [102, 107, 99], а именно перестановочное декодирование и декодирование с помощью покрывающих полиномов. Для ряда лучших линейных кодов, в частности, для квадратично-вычетных и квазициклических кодов, декодирование по информационным совокупностям является самым простым из известных методов декодирования [20].
В работах [28, 30, 100, 41, 72], по сути дела, рассмотрены обобщения декодирования по информационным совокупностям.
В настоящем разделе вводится метод декодирования, предложенный Круком и Федоренко [34] и основанный на понятии обобщенной информационной совокупности. Метод, сводящий декодирование исходного кода к нескольким декодированиям его уко рочений, был предложен Думером [17] , который также оценил асимптотику сложности декодирования по минимуму расстояния с использованием укорочений кодов [72]. В разделе рассмотрено декодирование при исправлении ошибок кратности до l(d—l)/2\, где d — минимальное расстояние кода. В параграфе описывается понятие обобщенной информационной совокупности и предлагается основанный на этом понятии алгоритм. В1 параграфе 1.1.21 изучается связь задачи построения декодера по обобщенным информационным совокупностям и задачи построения покрытий из кодовых слов, в частности, построения покрытия Турана, а также даны примеры построения покрытий- из кодовых слов. В параграфе 1.1.3 приведены таблицы декодеров по обобщенным информационным совокупностям.
Для введения понятия обобщенной информационной совокупности рассмотрим необходимые определения и обозначения.
Пусть Q — линейный (п, к, е)-код над полем GF(g) (конечное поле порядка q) в метрике Хэмминга. Пронумеруем позиции кодового слова числами из множества N = {1,2, ...,тг}. Множество чисел 7 = {ju---,3k}, 1 Л Зк ni называется информационной совокупностью кода, если задание компонент кодового слова с номерами из 7 однозначно определяет это слово. Для произвольного вектора f = (/і,/г, , fn) длины п и множества J = {л, j2,..., л} 1 Л . . 3 s Щ определим вектор f(J) = (fji,fj2i --ifjs) как подвектор длины s вектора f. Аналогично для произвольной матрицы М — \тп\\ \тп] со столбцами т , і Є [1,п], и множества J определим матрицу M(J) = [rrij! I \rrijs] со столбцами rrij, j Є J, как подматрицу матрицы M, составленную из столбцов этой матрицы с номерами из J. Пусть b — принятое из канала слово: b = с + е, с — переданный кодовый вектор, а е — векторі ошибок. Информацион ная совокупность 7 называется свободной от ошибок для вектора ошибок е, если е(7) = 0. Если во множестве информационных совокупностей Г = {7} для любого вектора ошибок е, вес Хэм-минга которого W(e) , найдется свободная от ошибок информационная совокупность, то множество Г будет достаточным для исправления ошибок кратности до t. Алгоритм декодирования по информационным совокупностям при этом состоит в переборе и кодировании по информационным совокупностям из множества Г и выборе кодового вектора, находящегося на расстоянии t или менее от принятого вектора Ь.
Сложность декодирования по информационным совокупностям определяется мощностью множества Г, достаточного для декодирования ошибок из множества Et — ошибок кратности до L(d-1)/2J.
Для каждой информационной совокупности 7 обозначим через 7 множество позиций, дополнительных к 7: 7 = N\y (мощность множества 7 IJ] — п — к = г). Тогда, чтобы множество Г={7} было достаточным для исправления ошибок из Et, необходимо, чтобы множество Г = {7} было М(п, г, -покрытием (т. е. таким множеством r-подмножеств множества IV, что любое t-подмножество N содержится хотя бы в одном г-подмножестве 7). Введем понятие обобщенной информационной совокупности. Обобщенной (т, А)-информационной совокупностью J назовем множество номеров позиций кодового слова J = {ji,---Jm}, 1 т щ 0 А /с такое, что rank G(J) — к — А. Очевидно, что информационная совокупность 7 = {hi- чЗк} является обобщенной (к, ( -информационной совокупностью. Если J есть (m, А)-информационная совокупность, то любому подвектору с( J), с є Я: соответствует список из не более чем дЛ кодовых слов, совпадающих с вектором с( J) на позициях из множества J. Через L[b( J)] обозначим список из кодовых слов, совпадающих с вектором b на множестве J.
Отыскание (т, Д)-информационной совокупности, свободной от ошибок, не дает при Д 0 декодированного варианта с принятого слова Ь, но дает список L[b(J)] слов, среди которых этот вариант присутствует. Нахождение декодированного варианта в списке может быть осуществлено, например, перебором по словам из списка, результатом которого является такой вектор с Є L[b(J)], что расстояние Хэмминга d(b,c) t. В противном случае производится отказ от декодирования.
Матрицу G{ J) можно рассматривать как порождающую матрицу кода G(J), полученного выкалыванием позиций множества J — N\J. Пусть dj — расстояние кода G{J)- Если число ошибок в подвекторе b(J) не превышает tj — \_(dj — 1)/2J, то, декодируя вектор b(J) в коде G{J), можно получить подвектор c(J), свободный от ошибок. В этом случае среди векторов списка L[c(J)] имеется переданный вектор с.
Множество обобщенных информационных совокупностей Г = {J} является достаточным для декодирования ошибок из Et, если для- любого вектора b = с + е (ее Et) во множестве Г найдется обобщенная информационная совокупность J, декодирование которой дает вектор c(J). Алгоритм декодирования по множеству обобщенных информационных совокупностей Г = {Ji}, і Є [1, s], можно записать в виде последовательности шагов.
Основные понятия и определения
Алгебраические коды, по сравнению с линейными кодами, яв ляются более узким классом кодов, но они имеют важное прак тическое применение при решении задач обработки информации. Под алгебраическим декодированием будем понимать методы де кодирования, основанные на алгебраических свойствах кодов и состоящие в решении уравнений и/или систем уравнений с поли номиальной сложностью. При рассмотрении алгебраических ко дов ограничимся классами БЧХ, Рида - Соломона, Гоппы, обоб щенных Гоппы и альтернантных кодов. В-главе рассматривает ся алгебраическое декодирование по укорочениям кодов (по обоб щенным информационным совокупностям), "генетическая" связь различных алгебраических методов декодирования и декодирова ние в надкодах.
Декодирование по обобщенным информационным совокупностям для произвольных линейных блоковых кодов было введено в работах [100, 34, 32]. Каждая обобщенная информационная совокупность задает линейный код, называемый укорочением основного кода. Алгоритм декодирования по обобщенным информационным совокупностям состоит в декодировании основного кода путем многократных декодирований укороченных кодов. В настоящем разделе рассматривается основанное на работе Мирончико-ва и Федоренко [41] применение декодирования по обобщенным информационным совокупностям к классу обобщенных кодов Гоппы [14, б], который также называется классом (L, д)-кодов. В этом случае укорочения основного кода будут принадлежать этому же классу кодов, а их декодирование можно осуществить известными алгебраическими методами. В качестве примера использования декодирования (L, #)-кодов по обобщенным информационным совокупностям приводится алгоритм декодирования в стирающем канале [40].
Пусть Q — линейный (п,к, с?)-код над полем GF(g) с порождающей матрицей G, где п -— длина кода, к — число информационных символов, ad — расстояние в метрике Хэмминга. Пронумеруем позиции кодового слова числами от 1 до п. Множество чисел J = {ji,..., js}, 1 ji ... js n, s n — d4-1, называется обобщенной информационной совокупностью кода [100, 34], если задание компонент кодового слова с номерами из J однозначно задает это слово. Символом J обозначим дополнение множества J в множестве {1, 2,..., п}. Для произвольного вектора f = (/i /2) j /п) длины п и множества J определим подвектор длины s как вектор f (J) = (fjx, fj2,..., fJn). Аналогично для матрицы G — [7тгі \тп]} где через mj, г Є [1,п], обозначены ее столбцы, и множества J определим подматрицу G(J) — [rrijj \mJa]. Код с порождающей матрицей G( J) назовем укороченным кодом и будем обозначать его через G(J). Укороченный код Q{J) является линейным (s, к, с )-кодом, где dj d— (п — s).
В основе алгоритма декодирования по обобщенным информационным совокупностям лежит идея поиска подвектора принятого вектора, число ошибок в котором не превышает корректирующей способности соответствующего укороченного кода.
Напомним определение (L, д)-кодов. Пусть L — множество линейно-независимых над GF(g) рациональных функций: \ z — а\ z — ач z — ап J щ, hi Є GF(#m), n qm,a, генераторный многочлен g(z) есть приведенный многочлен с коэффициентами из поля GF(gm), причем g(oci) ф 0 для всех і Є [1, п]. С каждым вектором с = (с\, С2,..., сп) над GF(qm) свяжем рациональную функцию 5 J - го 2=1 a% Тогда (Ь: д)-код длины п (или обобщенный код Гоппы [6]) состоит из всех таких векторов с, что } СІ — = 0 mod g(z). ? Z-OLi г=1 Известно [14], что расстояние (Ь,д)-кода не меньше, чем degg(z) + l, где через degg(z) обозначена степень многочлена g{z): а алгебраические алгоритмы декодирования (L, д)-кода позволя ошибок, где через [х] обозначена deg g{z) ют исправлять до t = целая часть числа х.
Пусть Q есть (L, д)-код. Каждое множество чисел J С {1,2, ...,п}, мощность которого J = s п — d + 1, является обобщенной информационной совокупностью и задает укороченный Q( /)-код. Для декодирования Q{ /)-кода алгебраическими методами необходимо описать его как обобщенный код Гоппы [6].
Построим (Ь5,р5)-код, содержащий все кодовые слова c(J) укороченного кода Q(J). Приведенный многочлен gs{z) с коэффициентами из поля GF(gm), степень которого равна deggs(z) = degg{z) — (n — s), является генераторным многочленом (Ls,gs)-кода, если gs(&j) ф 0 для всех j є J. Множество L.-l-b-\ Z-Cij для всех j Є J, где коэффициенты (3j — некоторые элементы поля GF(qm): будет множеством рациональных функций для кода (Ls, gs). Для всех слов (Ls, д3)-код& при фиксированных коэффициентах РІ, і Є J, справедливо тождество ieJ A СІ—: = 0 mod gs(z). Z-OLi (6) Найдем такие коэффициенты Pi, г Є J, что для любого кодового слова с Є Q его укорочение с( J) будет принадлежать (Ls,gs)-коду. Для этого рациональную функцию (5) умножим на дробь, в которой числитель и знаменатель имеют одинаковые степени, причем знаменатель — генераторный многочлен g(z), а числитель — произведение генераторного многочлена (Ls, #5)-кода gs(z) и многочлена ] \(z — aj):
Алгоритм быстрого поиска корней многочлена
Вычисление ДПФ над конечным полем, представляет собой самостоятельную и интересную задачу, приложения которой тесно связаны с алгоритмами кодирования и декодирования алгебраических кодов при решении: задач обработки. информации. Вычисление корней многочлена молено рассматривать как в связи с вычислением ДПФ; так и независимо. Циклотомический и рекуррентный алгоритмы вычисления ДПФ в случае, когда необходимо минимизировать число умножений, являются лучшими алгоритмами- для малых длин, (п 511). Неполное ДПФ применяют при вычислении синдрома для. алгебраических кодов.
В; настоящем разделе вводятся новые методы поиска корней многочленов над конечным полем, основанные на работах автора [85, 86, 70]. Это позволит значительно ускорить декодирование алгебраических кодов, включая БЧХ, Рида - Соломона, Гоппы и альтернантных.
Известно, что одним из самых сложных по времени этапов декодирования алгебраических кодов является поиск корней локаторного многочлена. Обычно для этого используют процедуру Ченя [67], которая состоит из подстановки всех элементов конечного поля в многочлен и сравнения полученных значений с нулем. Эта процедура становится довольно сложной при вычислениях в больших конечных полях и для многочленов большой степени.
В работе [68] было показано, что каждый многочлен степенине выше 5 может: быть, преобразован в каноническую форму с одним или двумя параметрами, так что возможно построить таблицы для поиска корней. Кроме того, если некоторые корни расположены в одном и том же циклотомическом классе, то возможно их вычислить с помощью алгоритма Евклида. Трунг, Дженг и Рид предложили преобразование [112], которое позволяет грушхиро-вать некоторые слагаемые в многочлене степени не выше 11 в произведение аффинных многочленов. Так как значения аффинных многочленов в элементах конечного поля можно легко вычислить, используя предварительно составленные небольшие таблицы, то возможно ускорение вычислений. Однако алгоритм [112] имеет следующие недостатки. 1. Он применим только для многочленов степени не выше, чем 11. 2. Требуется преобразование многочленов. Предложенное пре 11 образование у — x+fe/f7 для многочлена F(x) = V fix1 не г=0 может применяться, если /7 = 0, так что алгоритм поиска корней становится более сложным. 3. После преобразования многочлен содержит слагаемые fioy10 + І9У9 (и /б#6, если преобразование невозможно). Вы числение значений многочленов для этих слагаемых требует применения процедуры Ченя.
В настоящем разделе вводится общий подход к разложению и вычислению значений многочленов. Описание приведено для случая GF(2m), но может быть обобщено для произвольного конечного поля. Эта методика может быть использована для ускорения процедуры Ченя.
Проблема нахождения корней многочлена может быть формально определена как нахождение всех различных Х{ : F{xi) = t 0, F(x) = У fjx i хъ, fj Є GF(2m). Процедура Ченя решает эту 3=0 проблему путем вычисления значений многочлена F(x) во всех элементах конечного поля х Є GF(2m) \0 с временной сложностью = (Cadd + Cmul) (2-l), (25) где Cadd и Сти\ — временная сложность вычисления сложения и умножения элементов в конечном поле соответственно. Вводимый ниже алгоритм [85] уменьшает сложность вычисления значений многочлена в одной точке за счет использования специального упорядочения элементов конечного поля.
Перед описанием алгоритма запишем необходимые понятия и определения. Определение 3.1. Многочлен L(y) над конечным полем GF(2m) называется линеаризованным многочленом, если он может быть представлен в виде L(y) = J2Liy2\ Li є GF(2). г Основное свойство линеаризованных многочленов описывается следующей леммой. Лемма 3.1 [5]. Пусть у Є GF(2m) и с 0,..., а171-1 — стандартный базис конечного поля. Если т—1 У= ІУк хкі 2/fceGF(2), k=0 uL(y) = Y LjV23 , mo з 771 — 1 L(y) = Y, » (« ) k=o Определение 3.2. Многочлен А{у) над GF(2m) называется аффинным многочленом, если он может быть представлен в виде А(у) = Цу)+13, /?6GF(2), где L{y) — линеаризованный многочлен. Описанная выше лемма позволяет вычислять значения аффинного многочлена А (х) для каждого элемента конечного поля Х{ Є GF(2m), затрачивая только одно сложение, если все элементы конечного поля ХІ упорядочены в их векторном представлении как код Грея.
Определение 3.3. Код Грея есть упорядочение всех двоичных векторов длины т таким образом, что два соседних вектора отличаются только в одном бите.
Если векторы Xj є GF(2m) упорядочены как код Грея, т. е. wt( Xi — Xj_i) = 1, где wt(a.) — вес Хэмминга вектора а, то справедлива следующая цепочка равенств: А(щ) = А( і-і) + ЦАІ), АІ = ХІ- Xi-i = а -1 , где 5(xi,Xj_i) указывает на позицию вектора Xj, отличающуюся от вектора Хг-1. Если хо = 0, то положим -А(хо) = /3, и записанное выше правило позволяет описать алгоритм вычисления значений многочлена А{х) во всех точках конечного поля GF(2m).
Пример. Рассмотрим конечное поле GF(23), заданное примитивным многочленом 7г(а) = си3 + а 4- 1 над GF(2). Одним из возможных вариантов кода Грея является последовательность 000, 001, 011, 010, 110, 111, 101, 100 или 0,1, а3, а, а4, а5, а6, о;2. Для выполнения алгоритма быстрого вычисления корней многочлена необходимо предварительно запомнить таблицу величин ЦаР Ца Ца2). Тогда А{1) = А(0) + L(oP), А(а3) = А(1) + Ь{аг) и так далее.
Декодирование кода Голея по звездной решетке
В работе [39] описана конструкция Сі, позволяющая строить код Голея. Порождающая матрица кода Голея конструкции С\ задается следующим образом: G = Сі 0 Gi О d Gi Gi Gi Gi где G\ и Gi — порождающие матрицы эквивалентных самодуальных (8, 4, 4)-кодов Хэмминга. Использование этой конструкции для построения кодовой решетки специального вида позволяет получить алгоритм декодирования, кода Голея [109]. Конструкция позволяет также описать ряд хороших кодов. Вопрос о существовании других конструкций, подобных.Сі, которые дают хорошие коды, остается открытым [39].
Для обобщения этой конструкции введем необходимые определения. Матрица вида С = CQ Сі Cv-1 Со сі с2 Cv-1 Cv-2 со называется циркулянтной матрицей. Если элементы co,ci,..., Cy-i матрицы С в свою очередь являются матрицами, то матрицу С назовем блочно-циркулянтной. Пусть Р есть перестановка, сохраняющая линейный блоковый (п, к, і)-код G, причем порядком перестановки называется такое минимальное целое число I = ord(P) 1, что Р1 = J, где / — тождественная перестановка. Тогда можно попытаться найти представление порождающей (или проверочной) матрицы кода в блочно-циркулянтном виде. Это представление может использоваться при построении кодовых решеток и для декодирования.
Рассмотрим двоичные коды с перестановкой порядка 3, к которым относятся все двадратично-вычетные и некоторые БЧХ-коды [39]. Тогда блочно-циркулянтное представление для порождающих матриц квадратично-вычетных кодов [80] в виде конструкции Сч примет вид нальны, а не самоортогональны, как в конструкции С\. n матрицы размера — х —, причем для дважды четных самодуальных квадратично-вычетных кодов эти матрицы ортого 167 Введенная конструкция Сі позволяет исследовать свойства квадратично-вычетных кодов, разрабатывать алгоритмы декодирования, а также строить по порождающей матрице кодовые решетки. Кроме того, эта конструкция позволяет строить новые коды с хорошими свойствами. Среди кодов, удовлетворяющих конструкции С2, существуют коды, лежащие на границе Варшамова-Гилберта.
Рассмотрим подстановку ST на множестве {0,1,..., п — 2, со}. Так как подстановка S определена как у — у + 1 (mod п), а подстановка Т — как у — —у г, то подстановка ST: у — — (у + 1) имеет порядок 3 [39]. Пример. Подстановка ST при п = 7. При п = 7 первое отображение есть ST{0, 1,2,3,4,5, б, со) = (6,3,2,5,4,1,оо,0). Второе — 5Т(6,3,2,5,4,1,со,0) = (оо,5,2,1,4,3,0,6). Третье -Т(оо, 5,2,1,4,3,0,6) = (0,1,2,3,4, 5,6, оо). Так как п = 7 не делится на 3, то подстановка распадается в произведение четырех циклов: ST = (0, 6, оо)(1, 3, 5) (2) (4) длины Зи 1. ть Пусть п — длина кода Q, к = — — число информацион ных символов кода, d — минимальное расстояние Хэмминга кода. Для существования квадратично-вычетных кодов в виде конструкции Сч необходимо, чтобы подстановка ST, сохраняющая квадратично-вычетный код, разбивала множество позиций кода {0,1,..., п — 2,со} на — цикла длины 3 [39]. Такая подстановка существует для всех рассмотренных квадратично-вычетных кодов при п 200, если п делится на 3.
В таблице 8 [80] приведены параметры расширенных двоичных квадратично-вычетных кодов, представленные в виде конструкции С2, а также параметры подкодов Q\ и Q2, задаваемых порождающими матрицами G\ и G2 соответственно.
Очевидно, что для подматриц самодуальных квадратично-вычетных кодов выполняются соотношения G\G\ = 0 и G\G\ = G2&2, Заметим, что для квадратично-вычетных кодов имеется много различных представлений конструкции С2, а подкоды Q\ и С/2 можно выбрать с различными минимальными расстояниями d\ И С?2 Для кодов с параметрами (24, 12, 8) и (48, 24, 12) найдено представление с эквивалентными подкодами Q\ и С/2.
Рассмотрим приведение порождающей матрицы G квадратично-вычетного кода к квазициклическому представлению конструкции (72. В соответствии со структурой циклов подстановки ST разобьем множество позиций кода на три непересекающихся подмножества Jo, Ji, J2 так, что {0,1,..., п - 2, оо} = J0 U J\ U J2, г = {Сг,1,Сг,2,-.-,Яп}5 г Є [0,2], ST(ci,j) = c((i+l)mod3),j 170 В соответствии с рассмотренным разбиением переставляем столбцы порождающей матрицы G и получаем порождающую матрицу G эквивалентного кода: Jo J\ J2 G = [G(J0) ЭД) G(J2)], где G{Ji) — подматрица матрицы G, составленная из столбцов с номерами из множества J І. ТІ Приводим матрицу G к единичному виду на первых — пози о циях. В результате получаем матрицу G" = N0 N1 N2 О Gi G Очевидно, что rank[GiG2] = —. Применяя подстановку для о о нижних строк матрицы G", получаем порождающую матрицу ее подкода к п зхз где No,Ni,N2 — некоторые матрицы. 2k п У х 3 к матрицы; G±,G2 к G = Gi G2 0 G2 0 GX 0 Gx G2 Если det Gi G2 0, (36) то rank G = rank G2 + rank[GiG2] = fc, а коды, задаваемые матрицами G" и G , совпадают, т. е. представление С2 построено. Если условие (36) не выполняется, то это означает, что под-коды Q\ и Я2, задаваемые порождающими матрицами G\ и G2 соответственно, имеют общие ненулевые кодовые слова. Заметим, что для самодуальных квадратично-вычетных кодов будет выполняться соотношение G\(j2 — О, т- е- коды Q\ и С/2 ортогональны. Учитывая это, а также запись матрицы G\ в систематическом виде, переписываем матрицу G в виде то коды Q\ и Q2 не имеют общих ненулевых слов и условие (36) выполняется. Алгоритм приведения порождающей матрицы G квадратично-вычетного кода к виду конструкции Сг состоит из следующих шагов. Шаг 1. В соответствии со структурой циклов подстановки ST разбиваем множество позиций кода на три непересекающихся подмножества Jo, Ji, /2 Шаг 2. Записываем эквивалентное представление порождающей матрицы G" кода Q в виде (37). Шаг 3. Вычисляем rank[I + FFT]. Если условие (38) выполнилось, то G — искомое представление порождающей матрицы. Шаг 4. Иначе модифицируем подмножества
