автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Методы быстрого декодирования линейных блоковых кодов

На правах рукописи

Федоренко Сергей Валентинович

Методы быстрого декодирования линейных блоковых кодов

05.13.01 — Системный анализ, управление и обработка информации (в технике и технологиях)

Автореферат диссертации на соискание ученой степени доктора технических наук

Санкт-Петербург 2009

003470214

Работа выполнена в Государственном образовательном учреждении высшего профессионального образования "Санкт-Петербургский государственный университет аэрокосмического приборостроения"

Научный консультант доктор технических наук, профессор

Крук Евгений Аврамович

Официальные оппоненты: доктор технических наук, профессор

Габидулин Эрнст Мухамедович доктор технических наук, профессор Иванова Ирина Владимировна доктор технических наук, профессор Яковлев Виктор Алексеевич

Ведущая организация Институт проблем передачи информации им. A.A. Харкевича Российской академии наук

Защита состоится tA/UAih 2009 г. на заседании диссертационного совета Д 212.233.02 при Государственном образовательном учреждении высшего профессионального образования "Санкт-Петербургский государственный университет аэрокосмического приборостроения" по адресу: 190000, Санкт-Петербург, ул.Болыпая Морская, 67

С диссертацией можно ознакомиться в библиотеке университета. Автореферат разослан ] 2 2009 г.

J-ObJSJ

О ^^ д.Т.н.,

СГ

Ученый секретарь диссертационного совета <гУ ^^^"д.т.н., проф. Осипов JI.A.

Общая характеристика работы

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

Для обеспечения помехоустойчивости передаваемой информации применяют корректирующие коды. Теория кодов, исправляющих ошибки, возникла в середине XX века. Большую роль в развитии помехоустойчивого кодирования сыграли монографии В. Д. Колесника и Е. Т. Мирончикова, Э. М. Габидулина и В. Б. Афанасьева, Е. А. Крука, Р. Блейхута. С момента возникновения теория помехоустойчивого кодирования была разделена на два направления, изучающие блоковые коды (которые рассмотрены в диссертационной работе) и сверточные коды. Теория блоковых кодов, в свою очередь, содержит комбинаторную и алгебраическую теории кодирования. В 60-е годы прошлого века были введены комбинаторные и алгебраические алгоритмы декодирования. Комбинаторные алгоритмы декодирования применимы ко всем линейным блоковым кодам и исправляют ошибки, если их число не превосходит корректирующей способности кода, однако имеют относительно большую сложность. Алгебраические алгоритмы декодирования проще комбинаторных, но они применимы

только для некоторых классов кодов. Приложение алгоритмов декодирования сверточных кодов для декодирования блоковых кодов привело к появлению новых методов декодирования блоковых кодов по кодовым решеткам.

Корректирующие коды получили широкое применение в задачах обработки, передачи, записи, хранения и защиты информации. В настоящее время блоковые коды представлены в многочисленных технических приложениях, например, в стандартах CCSDS 101.0-В-6 (Consultative Committee for Space Data Systems), ITU-T G.975.1 (International Telecommunication Union) и IEEE 802.16 (The Institute of Electrical and Electronics Engineers).

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

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

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

Для достижения поставленной цели в работе исследуются следующие основные задачи.

1. Задача построения декодеров для ряда лучших кодов с наименьшей сложностью среди известных декодеров.

2. Задача построения эффективных декодеров алгебраических кодов.

3. Выявление взаимосвязи различных алгебраических методов декодирования.

4. Методологическая задача вывода и доказательства корректности алгоритма Гао.

5. Задача построения эффективных методов вычисления корней многочленов над конечным полем.

6. Задача построения алгоритмов с низкой вычислительной сложностью для вычисления преобразования Фурье над конечным полем.

7. Задача построения новых типов решеток для линейных блоковых кодов.

8. Задача построения декодеров кодов Рида - Соломона по кодовым решеткам.

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

Научная новизна работы. Научная новизна работы заключается в следующем.

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

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

3. Выявлена взаимосвязь различных алгебраических методов декодирования, а также представлен оригинальный вывод и доказательство корректности алгоритма Гао.

4. Предложены эффективные методы вычисления корней многочленов над конечным полем.

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

6. Разработан новый тип звездных решеток для линейных блоковых кодов.

7. Разработан метод декодирования кодов Рида - Соломона по кодовым решеткам.

Практическая ценность работы. Практическая ценность работы состоит в том, что разработка основных вопросов диссертации позволила:

— предложить простые алгоритмы декодирования для ряда хороших кодов;

— в несколько раз ускорить алгебраические алгоритмы декодирования.

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на:

— XI Международном симпозиуме по проблеме избыточности в информационных системах (СПб, 2007);

— Международных конференциях по алгебраической и комбинаторной теории кодирования (АССТ, 1990-2006);

— Международном симпозиуме по теории информации (Ш1Т, Лозанна, 2002);

а также на семинарах:

— кафедры информационных систем и кафедры безопасности информационных систем Санкт-Петербургского государственного университета аэрокосмического приборостроения;

— кафедры распределенных вычислений и компьютерных сетей Санкт-Петербургского государственного политехнического университета;

— на постоянно действующем семинаре по теории кодирования Института проблем передачи информации РАН (Москва).

Публикации. По теме диссертации опубликовано более 50 печатных трудов в научно-технических журналах, сборниках докладов и научно-технических сборниках, в том числе: монография, 14 статей в журналах, включенных в Перечень ВАК, и авторское свидетельство СССР.

Основные положения диссертации, выносимые на защиту.

1. Метод декодирования по обобщенным информационным совокупностям и табличное декодирование.

2. Метод декодирования алгебраических кодов на основе алгебраических методов укорочения кодов.

3. Взаимосвязь различных алгебраических методов декодирования.

4. Эффективные методы вычисления корней многочленов над конечным полем.

5. Алгоритмы вычисления преобразования Фурье над конечным полем.

6. Метод построения звездных решеток для линейных блоковых кодов.

7. Метод декодирования кодов Рида - Соломона по кодовым решеткам.

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы. Работа содержит 220 страниц машинописного текста, а список использованной литературы содержит 117 наименований.

Основное содержание работы

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

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

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

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

В разделе 1.1 вводится метод декодирования, предложенный Круком и Федоренко и основанный на понятии обобщенной информационной совокупности. В разделе рассмотрено декодирование при исправлении ошибок кратности до [{(1 - 1)/2_|, где (1 — минимальное расстояние кода.

Для введения понятия обобщенной информационной совокупности рассмотрим необходимые определения и обозначения.

Пусть Я — линейный (п,к,с1)-код над полем ОР(д) (конечное поле порядка д) в метрике Хэмминга. Пронумеруем позиции кодового слова числами из множества N = {1,2, ...,п}. Множество чисел 7 = {л, • • •,Л;}, 1 < Зх < ■ ■ ■ < Зк < п, называется информационной совокупностью кода, если задание компонент кодового слова с номерами из 7 однозначно определяет это слово. Для произвольного вектора Г = (/1, /2, • • ■, /п) длины п и множества 3 = {з\-,П, ■ ■ ■Ла}, 1 < Л < • ■ • < Зз < п, определим вектор {(«/) = (/^, /¿2,..., ) как подвектор длины в вектора Г. Аналогично для произвольной матрицы М = [тх| • • • | тп] со столбцами тп¿, г б [1, п], и множества 3 определим матрицу М(,7) = [то_?-11 • • • |т^] со столбцами т^. 3 £ 1, как подматрицу матрицы М, составленную из столбцов этой матрицы с номерами из 3. Пусть Ь — принятое из канала слово: Ь = с + е, с — переданный кодовый вектор, а е — вектор ошибок. Информационная совокупность 7 называется свободной от ошибок для вектора ошибок е, если е(7) = 0. Если во множестве информационных совокупностей Г = {7} для любого вектора ошибок е, вес Хэмминга которого Ще) < найдется свободная от ошибок информационная совокупность, то множество Г будет достаточным для исправления ошибок кратности до Алгоритм декодирования по информационным совокупностям при этом состоит в переборе и кодировании по информационным совокупностям из множества

Г и выборе кодового вектора, находящегося на расстоянии t или менее от принятого вектора Ь.

Сложность декодирования по информационным совокупностям определяется мощностью множества Г, достаточного для декодирования ошибок из множества Et — ошибок кратности до L(d-1)/2J.

Для каждой информационной совокупности 7 обозначим через 7 множество позиций, дополнительных к 7: 7 = N\7 (мощность множества 7 |7| = п - к = г). Тогда, чтобы множество Г={7} было достаточным для исправления ошибок из Et, необходимо, чтобы множество Г = {7} было М(п, г, ^-покрытием (т. е. таким множеством r-подмножеств множества N, что любое i-подмножество N содержится хотя бы в одном г-подмножестве 7).

Введем понятие обобщенной информационной совокупности.

Обобщенной (ш, Д)-информационной совокупностью J назовем множество номеров позиций кодового слова

J- {зъ-'-Лт}, 1<т <п, 0 < Д < fc

такое, что rank G(J) = к — А. Очевидно, что информационная совокупность 7 = {ji,..., jk} является обобщенной (к, (^-информационной совокупностью. Если J есть (ш, Д)-информационная совокупность, то любому подвектору с(J), с 6 Q, соответствует список из не более чем дА кодовых слов, совпадающих с вектором с(J) на позициях из множества J. Через L[b(J)] обозначим список из кодовых слов, совпадающих с вектором b на множестве J.

Отыскание (ш, Д)-информационной совокупности, свободной от ошибок, не дает при Д > 0 декодированного варианта с принятого слова Ь, но дает список £[Ь(/)] слов, среди которых этот вариант присутствует. Нахождение декодированного варианта в списке может быть осуществлено, например, перебором по словам из списка, результатом которого является такой вектор

с е Х[Ь(7)], что расстояние Хэмминга ¿(Ь,с) < В противном случае производится отказ от декодирования.

Матрицу С (7) можно рассматривать как порождающую матрицу кода £(./), полученного выкалыванием позиций множества 3 — N\J. Пусть dJ — расстояние кода Если число ошибок в подвекторе Ь(7) не превышает tJ = [(¿7 - 1)/2_|, то, декодируя вектор Ь(,7) в коде <?(«/), можно получить подвектор c(J), свободный от ошибок. В этом случае среди векторов списка £[с(<7)] имеется переданный вектор с.

Множество обобщенных информационных совокупностей Г = {является достаточным для декодирования ошибок из если для любого вектора Ь = с + е (е £ 1?г) во множестве Г найдется обобщенная информационная совокупность декодирование которой дает вектор с(7).

Алгоритм декодирования по множеству обобщенных информационных совокупностей Г = {./¿}, г б [1, в], можно записать в виде последовательности шагов.

Шаг 1. Для каждой ^ € Г выполняем следующие действия.

1.1. Производим декодирование вектора Ь(«7г) в вектор

ад.

1.2, Образуем список £[с(векторов кода (7.

Шаг 2. Образуем объединение списков

¡=1

Шаг 3. Выбираем в 1г[Ь] такой вектор с, что с1(Ъ,с) < Ц иначе считаем, что произошла неисправляемая ошибка.

Задача построения множества Г = {,7}, достаточного для декодирования ошибок из Et в коде 0, затрудняется необходимостью оценивать расстояние и число информационных символов укороченных кодов £(</). В разделе рассмотрено декодирование по обобщенным информационным совокупностям, основанное на методе укорочения кода, предложенном Хелгертом и Стинаффом

и приведена таблица декодеров для ряда квадратично-вычетных кодов и кодов БЧХ.

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

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

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

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

Введем некоторые обозначения и определения.

Пусть С — двоичный {п, к, <Г)-код, где п — длина кода; к — размерность и число информационных символов; й — минимальное расстояние кода. Число проверочных символов кода обозначим через г = п — к, корректирующую способность кода — через

t =

й- 1

к

а скорость кода — через Я = —. Порождающую мат-

ть

2

рицу кода £ обозначим через <3, а проверочную матрицу — через

Н. Для простоты изложения в этом параграфе рассмотрим только двоичные коды, тогда принятый вектор есть г = с + е mod 2, где с € С — кодовое слово, а е G — вектор ошибок. Декодированный вариант принятого вектора обозначим как с, а соответствующий вектор ошибок — как е.

Порождающая матрица (G(7))-1 G для информационной совокупности 7 должна иметь единичную подматрицу на позициях из множества 7, т. е. rank 6(7) = к.

Синдром для принятого вектора г определяется как s = г Нт = еН7. Вес Хэмминга вектора f обозначается как wt{f), а расстояние Хэмминга между векторами fi и f2 — как d(fi,f2). Взаимосвязь между этими определениями записывается как

Декодирование по информационным совокупностям. Метод декодирования по информационным совокупностям

рассмотрен на примере кода со скоростью R = причем длина кода п — четное число як — —. Предположим, что 7л =

{1,2, и 75 = {/г + 1, к + 2,..., п} являются информаци-

онными совокупностями.

Запишем проверочные матрицы для информационных совокупностей 7а и 7в как

НА = [ А | / ] и Нв = [ I | В ]. (1)

Теперь определим две таблицы Та = (Тл^л)} и Тв — {Tb(sb)} следующим образом:

0,1,2,...,

Та(*а) = jfi е F2fc | wt(fi) = h G

d(sA)fiAr) = 0>l,2,...,i-t1|J

где эд = еЯХ = (в! | е2)

= егА7 + е2;

ТвЫ = е | ы^) = ¿2 е

0,1,2,..

где эв = еЯд = (в! | е2)

"Ж

в! + е2Вт.

Заметим, что для е = (ех | е2) имеем е(7д) = в! и е(ув) = е2.

Поэтому можем различать два случая: ги^ех) < и)^е2) и и;£(ех) > ю1(е2). В первом случае будем использовать для декодирования таблицу Та, а во втором — таблицу Тв. Так же, как и для синдромного декодирования, две таблицы вычисляются заранее и запоминаются.

Алгоритм декодирования по информационным совокупностям для табличного декодирования.

Пусть принятый вектор есть

г = с + е = (гх | г2) = (сх + ех | с2 + е2).

Проверочные матрицы Яд и Нв определяются формулой (1).

Шаг 1. Вычисляются синдромы вд и эв:

вд = гЯ^; = г

Шаг 2. Выбираются два списка {й} и {Г2} из таблиц 7д = (Гд(8д)} и Тв = {Гв(ев)}:

ТаЫ = Ш; Гв(8в) -

Шаг 3. Формируются два списка декодированных вариантов принятого вектора:

{сд} = {(Г! + Ь I (п + Ъ)^)}; {св} = {((г2 + Ь)ВТ | г2 + $,)}.

13

Шаг 4. Декодированный вариант принятого вектора есть

с = arg min día, г), ae{cA}U{cB}

ближайший к принятому вектору вектор в метрике Хэмминга d(с, г). Если объединение списков пусто: ||{сл} U {св}|| = 0, то объявляется отказ от декодирования.

Декодирование в надкодах.

Надкод Cs кода С содержит все кодовые слова кода С, т. е. CcCs.

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

Н =

(2)

НА Нв

где Н/1 — (га х п) матрица и 7/д — (гв х п) матрица, причем Л4+ГВ = п~к. Очевидно, что На — проверочная матрица надкода Сл и Нв — надкода Св. Заметим, что минимальное расстояние надкода не превышает минимального расстояния основного кода.

Для принятого вектора г = с + е синдром в состоит из двух подвекторов вд и вд:

8 = (8д|8в) = (гЯ2|гЯ£).

Таблицы Та = {Т^д)} и Тд = (Гд^в)} для надкодов определяются как

ТаЫ = {Г е ЩI штА = ваМЪ < *}; ТвЫ = {{& I ш1 = 8в>«од < *}■

Теперь сформулируем алгоритм декодирования в надкодах следующим образом.

Алгоритм декодирования в надкодах.

Проверочные матрицы На и Нв определяются формулой (2).

Шаг 1. Вычисляются подвектора ял и ев синдрома

8 = (ел I &в) - гЯТ.

Шаг 2. Выбираются два списка {Га} и из таблиц 7д = {Тл(зЛ)} и Тв = {Тв(вв)}:

ТаЫ = {Ъ}; Тв(зв) =

Шаг 3. Вычисляется пересечение списков

{е} = {Гл}п{ад.

Шаг 4. Декодированный вариант принятого вектора есть

С — I* + етШ)

где етш — ближайший к принятому вектору вектор в метрике Хэмминга из списка {е}. Если пересечение списков {ё} пусто, то объявляется отказ от декодирования.

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

В разделе 1.3 рассматривается асимптотический анализ сложности декодирования линейных блоковых кодов.

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

до ¿о, которые может исправить код, где с/о — расстояние (п, к)-кода, лежащего на границе Варшамова - Гилберта (декодирование почти по максимуму правдоподобия).

Пусть 0 — (п, к, <1) д-ичиый линейный код, где п — длина кода, к — число информационных символов кода, <1 — минимальное расстояние кода в метрике Хэмминга. Пусть Е™ — линейное пространство д-ичных векторов длины п над конечным полем а а, Ь) — расстояние Хэмминга между векторами а и Ь.

Сформулируем принцип декодирования почти по максимуму правдоподобия.

Декодирование почти по максимуму правдоподобия: для данного вектора Ь € Е™, причем с1(Ь, (?) < с2о, найти кодовое слово

а е С?, ближайшее к Ь, где с!(Ь, 0) = гшпс£(Ь, а), ¿о — расстояние

аеб

Варшамова - Гилберта кода ¿о = с/о(п, к).

Обозначим через линейный код с порождающей матрицей £?(«/). Этот подкод имеет параметры (|,7|,гапк <?(./), с^), причем

Списочное декодирование подкода приводит к созданию списка кодовых слов

£ДМ) = {се£Ы(Ь(7),с(/))<г}.

Этот список построен таким образом, что для любого подвек-тора вектора ошибок е(7) с весом Хэмминга до г, т. е. при весе подвектора ошибок Ш(е(3)) < список Ь содержит переданный вектор.

Запишем алгоритм декодирования по обобщенным информационным совокупностям в виде последовательности шагов.

Шаг 1. Выбираем такую обобщенную информационную совокупность что 1У(е(7г)) < t, где Ь — некоторый параметр.

Шаг 2. Образуем список кодовых слов Ь,£), ближайший к Ь вектор из которого считаем декодированным вариантом принятого вектора. Иначе считаем, что произошла неисправляемая ошибка.

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

В параграфе 1.3.2 доказана следующая теорема.

Теорема. Сложность построения неслучайного М(п,р,1)-покрытия асимптотически совпадает с мощностью этого покрытия.

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

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

Алгебраические коды, по сравнению с линейными кодами, являются более узким классом кодов, но они имеют важное практическое применение при решении задач обработки информации. Под алгебраическим декодированием будем понимать методы декодирования, основанные на алгебраических свойствах кодов и состоящие в решении уравнений и/или систем уравнений с полиномиальной сложностью. При рассмотрении алгебраических кодов ограничимся классами БЧХ, Рида - Соломона, Гоппы, обобщенных Гоппы и альтернантных кодов.

В разделе 2.1 рассматривается основанное на работе Мирон-чикова и Федоренко применение декодирования по обобщенным информационным совокупностям к классу обобщенных кодов Гоппы, который также называется классом (£, <?)-кодов. В этом случае укорочения основного кода будут принадлежать этому же классу кодов, а их декодирование можно осуществить известными алгебраическими методами.

В разделе 2.2 рассматривается "генетическая" связь алгебраических методов декодирования. В работе Гао предложен алгоритм декодирования, который представляется самым простым и естественным в классе алгоритмов декодирования алгебраических кодов до их корректирующей способности. Асимптотическая сложность алгоритма совпадает со сложностью лучших алгоритмов декодирования, а описание является самым простым из описаний известных алгоритмов. В разделе рассматривается интерпретация этого алгоритма через цепочку родственных связей от алгоритмов Велча - Берлекэмпа и Евклида, через интерпретацию Чамберса и модификацию Геммеля - Судана, предложенная в работах автора.

Рассмотрим код Рида - Соломона (п, к, d) над конечным полем GF(q) с длиной n = q — 1, числом информационных символов к и конструктивным расстоянием d = п — к + 1, где q — степень простого числа. Корректирующая способность кода равна —^ ,

где [а] — целая часть числа а.

Порождающий многочлен кода Рида - Соломона обозначим через

b+d-2

д(х) = П (*"*')>

г=Ь

где а — примитивный элемент GF(g); Ь — произвольное натуральное число.

Принятый вектор представлен многочленом

п-1 п—1 п~1

R(x) = ]Г rixi = С(х) + Е(х) = ]Г ах* + Y^ ¿=0 ¿=0 ¿=0

где С(х) — кодовое слово; Е(х) — вектор ошибок.

^_j

Пусть Е(х) содержит t < —-— ошибок, которые имеют коор-

¿1

динаты ¿1,¿2, ...,it, причем 0 < < ¿2 < ... < it < n — 1, и значения е^, e*2,..., ejt. Назовем величины Z\ — а'1, Z% — а12,..., Zt = а4 локаторами ошибок, a Y\ = е^, Уг = £i2 j • • • > ^t = ен ~ значениями ошибок.

Многочлен локаторов ошибок обозначим через

t

W(x) = H(x-Zi), »=i

где t < ——^, — число ошибок в векторе ошибок Е(ж); Zi — локатор ошибки в векторе ошибок Е(х). Положим по определению W(x) = 1, если ошибок нет.

Информационный многочлен кода Рида - Соломона обозначим как

fc-i

М(ж) = y^mjx1. i=0

При спектральном кодирован™ компонента Ci кодового слова С(я) вычисляется как

сi = M(ai), г € [0, n — 1].

Алгоритм Гао. Опишем алгоритм Гао, который ранее был введен Шиозаки. Для упрощения изложения будем рассматривать только классические коды Рида - Соломона с параметрами п — q — 1 и 6 = 1.

Шаг 1. Интерполяция. Построим такой интерполяционный многочлен Т(х), что

Т(а') = тч, г € [0,п - 1],

где degT(a;) < п.

Шаг 2. Незаконченное вычисление наибольшего общего делителя. Решаем сравнение

'W(x)T{x) = Р(х) mod хп - 1 ■ deg Р{х) < _ maximize deg Р(х)

применением расширенного алгоритма Евклида к многочленам хп - 1 и Т(х), получая единственную пару многочленов Р(х) и W(x).

Шаг 3. Деление. Информационный многочлен есть Mix) = Ш

Асимптотическая сложность алгоритма 0(n(logn)2) совпадает со сложностью лучших классических алгоритмов декодирования кодов Рида - Соломона.

Первый шаг алгоритма Гао может быть выполнен любым быстрым алгоритмом вычисления дискретного преобразования Фурье (ДПФ) над конечным полем со сложностью O(n(logn)2) операций. В случае, когда необходимо минимизировать число умножений, лучший алгоритм для малых длин (п < 511) описан в разделе 3.2.

Одна из лучших реализаций второго шага есть алгоритм Мёнка со сложностью 0(n(logn)2) операций. Заметим, что при этом второй шаг полностью совпадает с алгоритмом решения ключевого уравнения Сугиямы.

Деление на третьем шаге алгоритма выполняется за 0(n log га log log п) операций.

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

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

В разделе 2.3 рассматривается декодирование в надкодах.

Надкодом 9% линейного блокового кода 0 называется код, содержащий все кодовые слова исходного кода. Пусть 91-02, ■■■ — набор надкодов для кода О, О с г € [1, й]. Алгоритм декодирования ошибок кратности до t в надкодах состоит в следующем.

Шаг 1. Для каждого кода б{ проводится декодирование в список Ьг. Список строится таким образом, что для любых ошибок кратности до £ список ¿¡- содержит переданное кодовое слово.

Шаг 2. Вычисляется список Ь как пересечение списков Ь^.

Шаг 3. Из Ь выбирается слово, наиболее близкое к принятому вектору.

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

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

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

В разделе 3.1 вводятся новые методы поиска корней многочленов над конечным полем, основанные на работах автора. Это позволит значительно ускорить декодирование алгебраических кодов, включая БЧХ, Рида - Соломона, Гопды и альтернантных.

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

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

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

Проблема нахождения корней многочлена может быть формально определена как нахождение всех различных Х{ : х^) =

О, ^(х) = ^ ^х^, е ОЕ(2т). Процедура Ченя решает эту

о

проблему путем вычисления значений многочлена Р{х) во всех элементах конечного поля ж 6 СР(2т) \0 с временной сложностью

где Сас1с1 и Сти1 — временная сложность вычисления сложения и умножения элементов в конечном поле соответственно.

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

Перед описанием алгоритма запишем необходимые понятия и определения.

Определение. Многочлен Ь(у) над конечным полем ОЕ(2т) называется линеаризованным многочленом, если он может быть представлен в виде

I

Определение. Многочлен А(у) надС¥(2т) называется аффинным многочленом, если он может быть представлен в виде

А(у) = Цу) + /3, ¡ЗеС¥(2т), 22

где L(y) — линеаризованный многочлен.

Если векторы хг- е GF(2m) упорядочены как код Грея, т. е. wt(xi — Xi_i) = 1, где wt(а) — вес Хэмминга вектора а, то справедлива следующая цепочка равенств:

A{xi) = A(xi_!) + L{Ai), А{ = x< - Xj_i = c^-^-O

где <5(x,',xj_i) указывает на позицию вектора Xj, отличающуюся от вектора Xj_i. Если хо = 0, то положим Л(хо) = /?, и записанное выше правило позволяет описать алгоритм вычисления значений многочлена А(х) во всех точках конечного поля GF(2m).

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

t

Теорема. Любой многочлен F(x) — У^зЛ fj 6 GF(2m);

j=о

может быть представлен как

Г(*-4)/51 / 3 \

F(x) = f3x3+ Y1 ®И /« + £><+* я* > ¿=0 \ j=о /

где [а] — наименьшее целое число, большее или равное а.

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

Запишем алгоритм поиска корней многочлена в виде последовательности шагов.

Шаг 1. Вычисляем b\k) = Li{ak), к = [0,m - 1],

г 6 [0, f(i - 4)/5~|], где Li(x) — линеаризованный многочлен, пред-

з

ставляемый в виде разложения: Li(x) — ^ fsi+2^ ■

j=о

Шаг 2. Инициализация = /si-

Шаг 3. Представляем каждый элемент Xj е GF(2"1), j £ [0,2m - 1], в стандартном базисе как элемент кода Грея с хо = О, вычисляем А? = a\j~1] + bf >J'x'-l)), j е [1,2т - 1].

Г(«-4)/51

Шаг 4. Вычисляем F(xj) = f$Xj + У^

Xj л{ ,

¿=0

j е [1,2™ - 1], и .Р(О) = /о. Если Р(Х]) = 0, то х^ — корень многочлена. Заметим, что второе слагаемое в этой сумме может быть вычислено с использованием метода Горнера.

Общая временная сложность этого алгоритма, состоящая из сложности предварительных вычислений (первое слагаемое) и сложности вычисления значений многочленов (второе слагаемое), равна

Wfast = т

t + 1

(4Craui + 3Cadd)+

+

t + 1'

(2Cadd + Cmui) + 2Cexp) (2m - 1),

где через Cexp обозначена временная сложность вычисления возведения в степень над конечным полем.

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

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

Предложенный автором метод состоит в разбиении исходного многочлена на сумму линеаризованных многочленов (3) и вычислении их значений в наборе базисных точек (4). Компоненты преобразования Фурье вычисляются как линейные комбинации этих значений с коэффициентами из простого поля (5).

Введем ДПФ над многочленами. За исходный многочлен примем многочлен f(x) степени п — 1, а за результирующий — мно-

гс-1

гочлен F(x) = ^ Fixг той же степени. ¿=о

Определение. Преобразованием Фурье многочлена f(x) =

п-1

Е/гЯг степени deg f(x) = п — 1, п | 2m - 1, в поле GF(2m) назы-

i=О

вается набор значений

п-1

= /(<**) = 3 е [0,n- 1],

г=0

где а — элемент порядка п в поле GF(2m). п-1

Многочлен f(x) = Е /¿ж1, 6 GF(2m), может быть разложен

г=0

как

I mi—1

f(x) = J2Li(xki), НУ) = Е mod пУ2\ (3)

г=0 j=О

где у G GF(2m) — независимая переменная, I — число нетривиальных циклотомических классов по модулю п над GF(2), m* | т.

Выражение (3) будем называть циклотомическим разложением многочлена f(x).

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

774—1

Ч&*) = Е PZfhiар, » е [0,1], я е [0,mj -1]. (4)

р=о

Базисы (0ifl,..., /5-i,m.i—i) для каждого из линеаризованных многочленов Li(y) могут выбираться независимо.

Компоненты преобразования Фурье многочлена /(ж) являются линейными комбинациями этих значений:

I ггч-1

Fj = /И = Е Е =

i=0 s=0

25

I mj-1 /roj-1 \

=EEE. j€[o,n-1]. (5)

i=о 5=0 у p=О У

Таким образом, задача вычисления БПФ разбивается на два этапа: умножение блочно-диагональной матрицы L на исходный вектор f и умножение двоичной матрицы А на полученный вектор Ы-.

F = ALL

Первый этап преобразования Фурье сводится к задаче вычисления I + 1 циклических сверток малой длины т,-.

Второй этап вычисления БПФ может быть выполнен с помощью модифицированного алгоритма "четырех русских" (В. JI. Ар-лазаров, Е. А. Диниц, М. А. Кронрод, И. А. Фараджев) для умножения булевых матриц со сложностью 0(п2/logn) сложений над элементами поля GF(2m) или эвристическим алгоритмом, сложность которого оценить не удалось. Однако для всех рассмотренных примеров сложность эвристического алгоритма меньше сложности модификации алгоритма "четырех русских".

Предложенный автором алгоритм БПФ эффективен при малых значениях длины преобразования, хотя известны асимптотически более эффективные алгоритмы БПФ для конечных полей со сложностью 0(пlog2 п) операций в основном поле.

В разделе 3.3 предложен метод вычисления ДПФ над конечным полем, основанный на разложении матрицы преобразования в произведение двоичной блочно-циркулянтной и диагональной блочно-циркулянтной матриц. Идея сведения вычисления ДПФ длины п к вычислению циклической свертки длины п — 1 была предложена Рейдером для простых длин. Алгоритм Герцеля, модифицированный для конечных полей, в работе автора интерпретирован как сведение ДПФ длины п = 2m - 1 к вычислению циклических сверток длины т. JI. А. Бассалыго первым обратил внимание на регулярную структуру матрицы преобразования, что дает возможность применять блоковые циклические свертки для

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

Введем ДПФ над векторами. За исходный вектор примем вектор f длины п, а за результирующий — вектор F той же длины.

Определение. Дискретным преобразованием Фурье длины п | 2та — 1 вектора f = (/¿), i е [0,п — 1], в поле GF(2m) называется вектор F = (Fj),

п-1 ¿=0

где а — элемент порядка п в поле GF(2m). Запишем ДПФ в матричной форме

F = Wf,

где W = (ау), i, j S [0, n - 1], — матрица Вандермонда.

Заменим ДПФ на эквивалентное преобразование, отличающееся порядком компонент в результирующем и исходном векторах:

Fc =WJC) Fc =HF,

fc =nf,

где Wc — I1WUT, П — перестановочная матрица.

Теорема. Матрица эквивалентного преобразования Wc фак-торизуется в произведение двоичной и блочно-диагональной матриц.

Эквивалентное преобразование Фурье длины п в поле GF(2m)

Fc = Wcic = AcLcfc

состоит из двух этапов. На первом этапе вычисляют I циклических сверток, что при п = 2т — 1 требует не более т2ш nlagn

сложений и умножений в поле СР(2т). На втором этапе вычисляют произведение двоичной матрицы Ас на вектор Ьс{с.

В разделе 3.4 рассматривается задача вычисления синдрома от принятого вектора для классических кодов Рида - Соломона с помощью циклотомического и рекуррентного методов. Коэффициенты синдромного многочлена могут быть вычислены как неполное ДПФ от принятого многочлена.

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

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

В разделе 4.1 вводится конструкция для блочно-циркулянтного представления порождающих матриц квадратично-вычетных кодов

'(?! С2 0' О (З1 р2 0 Ог

к л

и С?2 — матрицы размера - х -, причем для дважды четных самодуальных квадратично-вычетных кодов эти матрицы ортогональны.

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

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

В разделе 4.2 рассматриваются циклические замкнутые решетки.

Известны два различных вида решеток для линейных блоковых кодов: обычные решетки (conventional trellis) и циклические замкнутые решетки (tail-biting trellis). Заметим, что обычные решетки допускают декодирование по минимуму расстояния. Для описания обычных решеток определим ось времени как I = {0,1,...,п}, где п — длина кода. Циклические замкнутые решетки имеют ось времени / = {0,1,...,п — 1}, где индексы вычисляются по mod п.

Фактор-граф кодовой решетки есть граф, вершинами которого являются пространства состояний кодовой решетки Si, i € [О, п], а ребро соединяет вершины Si и Sj, если на кодовой решетке найдется некоторое состояние из пространства состояний Si, которое соединяется кодовым символом с некоторым состоянием из пространства состояний Sj.

Фактор-граф обычной решетки изображен на рисунке 1, а фактор-граф циклической замкнутой решетки — на рисунке 2. Пространство состояний S,- обозначено кругом.

О-О-О- ... —о—о

So Si S2 5n-i Sn

Рисунок 1. Фактор-граф решетки

Пусть I — порядок перестановки, сохраняющей линейный блоковый (тг, к, «¿)-код. Будем искать порождающую матрицу кода в следующем виде:

Рисунок 2, Фактор-граф циклической замкнутой решетки

G\ G2 ... Gi

G[ G\ ... Gi-1

: : : '

G2 G3 ... Gi

n fk n\

где Gt- — некоторые ( — x — 1 матрицы.

Предположим, что l\n и l\k. Таким образом, можно построить циклические замкнутые решетки для квазициклических кодов, какими являются все коды, имеющие представление в виде конструкции из раздела 4.1 при I = 3.

В работах автора построены циклические замкнутые решетки для (24, 12, 8)-кода Голея и (48, 24, 12)-кода. Эти решетки удовлетворяет условию минимальности числа состояний.

В разделе 4.3 водятся звездные решетки.

В работе автора введен новый тип решетки — звездная решетка (star trellis). Она может быть построена, в частности, для кода Голея длины п = 24.

Пусть ось времени состоит из нескольких частей I —

[J/j, которые сходятся в одной точке, например Ij = j

{О, (7 - 1)п/3 + 1,..., ]п/3, оо} для трех частей, где оо обозначает, что в этот момент сходятся все части оси времени. Здесь проводится согласование всех информационных символов кода.

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

Фактор-граф звездной решетки изображен на рисунке 3.

? 50

Рисунок 3. Фактор-граф звездной решетки

Каждая часть оси времени ассоциируется с укорочением обычной решетки. Звездная решетка состоит из объединения всех укороченных решеток в одной точке оо с несколькими конечными состояниями. Пример звездной решетки для кода Голея представлен на рисунке 4.

Каждая укороченная решетка состоит из п/3 — 8 секций и имеет одно начальное состояние и восемь конечных. Объединяя три одинаковые укороченные решетки во множество из восьми состояний, получаем звездную решетку для кода Голея.

Таким образом, каждому кодовому слову кода Голея взаимнооднозначно соответствует путь на звездной решетке, состоящий

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

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

Запишем алгоритм декодирования кода Голея по звездной решетке.

Шаг 1. Декодируем принятый вектор по трем укороченным решеткам Т(0:8) в восемь конечных СП-состояний.

Шаг 2. Выберем из восьми конечных О-состояний два информационных множества ./¿, г 6 [1,3], для которых соответствующие пути на решетке имеют наименьшее расстояние от подвекто-ра принятого вектора.

Шаг 3. Определим для восьми конечных □-состояний последний информационный символ и получаем до восьми полных наборов информационных символов.

Шаг 4. Строим кодовые слова по наборам информационных символов и выбираем из них ближайший к принятому вектору.

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

В разделе 4.4 рассматривается декодирование кодов Рида -Соломона по звездным решеткам.

В работе Варди - Беэри предложено отображение произвольного кода Рида - Соломона KS в его двоичный образ Im(T^S).

Введем обозначения для кода Рида - Соломона. 71S(N,K,D) — код Рида - Соломона над GF(2m) с параметрами N = 2т - 1, D — N - К + 1, где а, а2,..., аD~1 — корни порождающего многочлена G(x), а а — примитивный элемент GF(2m).

Аналогично введем БЧХ-код с той же проверочной матрицей, что и у кода Рида - Соломона. ВСЩп, к, d) — двоичный БЧХ-код, причем выполняются следующие соотношения для параметров п = N, к < К, d> D.

Порождающий многочлен БЧХ-кода д{х) б GF(2)[a;] имеет корни а, а2,..., аи их сопряженные относительно GF(2) элементы. Gbch — порождающая матрица БЧХ-кода.

Очевидно, что G(х) | д{х).

Рассмотрим {71,72, • • -,7т} — произвольный базис GF(2m).

Так как а? = YaLi aHh Т0 введем Im(aJ) = (aj, аг,..., am) — двоичный образ элемента aJ; причем Im(0) = (0,0,..., 0) — двоичный образ 0.

Для упрощения изложения будем использовать стандартный базис {а0, а1, а2,..., ат-1}.

В работе Варди - Беэри показано, что порождающая матрица перестановки двоичного образа кода Рида - Соломона имеет вид

G

Рег(1т(тг5))

" Gbch 0 0 ]

0 Gbch 0

... ...

0 0 Gbch

glue vectors

где подматрица связывающих слов ("glue vectors") имеет размерность т(К — к) х Nm.

В работе автора было отмечено сходство вида порождающей матрицы кода Голея и порождающей матрицы перестановки дво-

ичного образа кода Рида - Соломона. Следовательно, звездная решетка существует не только для кода Голея, но и для кода Рида - Соломона.

Для любого кода Рида - Соломона можно построить звездную решетку, состоящую из m частей, каждой из которых соответствует укороченная решетка с одним начальным состоянием и 2т(к~к) конечными. Конечным состояниям соответствуют "glue vectors".

На первом этапе проводится классическое декодирование с мягкими решениями по т укороченным решеткам. Результатом этого этапа является список, состоящий из не более 2т(К~к) слов кода Рида - Соломона. Из этого списка на втором этапе производится выбор ближайшего к принятому вектору.

Предложенный метод декодирования обеспечивает возможность получения выигрыша на информационный бит до 2-3 дБ в канале с аддитивным белым гауссовым шумом (AWGN) по сравнению с классическим декодером кодов Рида - Соломона. Такой выигрыш обеспечивается тем, что все подкоды двоичного образа кода Рида - Соломона декодируются по минимуму расстояния.

В пятой главе предлагаются методы практической реализации решения задач обработки информации.

В разделе 5.1 рассматривается метод многошагового декодирования итеративных кодов Хэмминга, основанный на работе автора, который был реализован в проекте МАРС-96. Результаты моделирования показали высокую эффективность данного метода. Метод использует преобразование Адамара (Уолша, Фурье), которое относится к Фурье-подобным преобразованиям. Применение быстрого алгоритма вычисления преобразования Адамара приводит к эффективной реализации всего алгоритма декодирования.

В качестве итеративного кода Q в канале с AWGN выберем прямое произведение трех кодов Хэмминга. Код Q имеет параметры (23тп, (2m - 1 - т)3,64), а реализация декодирования сводится к 3 22т декодированиям кодов Хэмминга по трем направлениям.

Сложность алгоритма декодирования итеративного кода Хэмминга с мягкими решениями отличается лишь на множитель от

теоретически минимально возможной и имеет порядок

0(4JjVlogJV),

где J — число шагов декодирования, N — 23т — длина кода Q.

В разделе 5.2 рассматривается схема вычисления ДПФ.

Целью построения схемы вычисления ДПФ в виде потокового графа (в альтернативной терминологии — направленного графа) является получение регулярной структуры схемы, а не минимизация числа умножений. Для реализации вычисления ДПФ над полем комплексных чисел известна схема "бабочка". Так как над конечным полем построить схему "бабочка" нельзя, то в разделе построена отличная от "бабочки" регулярная схема.

Раздел 5.3 содержит реализацию на программируемой логической интегральной схеме циклотомического алгоритма автора вычисления ДПФ из раздела 3.2, выполненную сотрудниками института SUPELEC (Франция).

Реализация выполнена на программируемой логической интегральной схеме (FPGA, Field Programmable Gate Arrays).

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

R- Ncf

где Nc — число ячеек в блоке 4, Nm — число циклотомических классов наибольшей длины m по модулю п над GF(2).

Приведем пример реализации данной схемы. На рисунке 5 изображена архитектура реализации циклотомического алгоритма для длины п = 15. В блоках 1-3 происходит вычисление циклической свертки для каждого циклотомического класса длины 4, т. е. в этих блоках последовательно три раза производятся вычисления четырехточечных циклических сверток. В блоке 4 выполняется умножение на матрицу А. В дополнительном блоке 5 вычисляется двухточечная циклическая свертка.

Рисунок 5. Архитектура реализации циклотомического

алгоритма

Эта схема содержит 10 умножителей на константу в поле GF(24), 109 сумматоров в поле GF(24) и 60 элементов AND для Nm = 15 ячеек в блоке 4. Число логических элементов уменьшается до 10 умножителей, 67 сумматоров и 32 элементов AND при Nm = 8 ячейках в блоке 4.

В таблице 1 приведены результаты вычисления ДПФ длины п — 15 для программируемой логической интегральной схемы STRATIX-II, EP2S15F484C3. Производительности схемы обозначена через R, тактовая частота /т — 500 MHz, число ячеек в бло-

1

ке 4 равно Nc, тактовый интервал равен Тт = — — 2 ns, слож-

1т

ность реализации измеряется числом адаптивных логических блоков табличного типа (ALUT, Adaptive Look Up Table).

Таблица 1

Реализация на FPGA для циклотомического алгоритма вычисления ДПФ длины п = 15

Е, MHz Nc число ALUT

2500 15 343

1250 8 203

Из сравнения схем реализации циклотомического алгоритма и алгоритма Ванга - Жу следует, что число умножителей в первой

logn о с

схеме в —— раз меньше, а производительность в 8.5 раз выше,

чем во второй.

В заключении обобщены полученные в диссертационной par боте результаты и сделаны выводы.

Основные результаты работы

Основные результаты работы можно сформулировать следующим образом.

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

2. Построенные декодеры алгебраических кодов на основе алгебраических методов укорочения кодов эффективны в стирающем канале.

3. Показано, что различные алгебраические методы декодирования тесно взаимосвязаны.

4. Предложенные вывод и доказательство корректности алгоритма Гао являются самыми простыми из известных описаний алгебраических методов декодирования.

5. Предложенные алгоритмы декодирования алгебраических кодов на основе надкодов для некоторых кодов имеют небольшую сложность.

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

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

8. Предложенные методы вычисления неполного преобразования Фурье над конечным полем эффективны для вычисления синдрома алгебраических кодов.

9. Код Голея может быть описан с помощью звездной решетки с наименьшим известным максимальным профилем сложности состояний.

10. Метод декодирования кодов Рида - Соломона по звездным решеткам обеспечивает возможность получения выигрыша на информационный бит до 2-3 дБ в канале с аддитивным белым гауссовым шумом по сравнению с классическим декодером кодов Рида - Соломона.

Основное содержание диссертационной работы изложено в следующих публикациях (статьи 2-16 опубликованы в изданиях, включенных в Перечень ВАК):

1. Федоренко С. В. Методы быстрого декодирования линейных блоковых кодов: Монография. СПб.: ГУАП, 2008. 199 с.

2. Федоренко С. В. Сложность декодирования линейных блоковых кодов// Проблемы передачи информации. 1993. Т. 29. № 4. С. 18-23.

3. Мирончиков Е. Т., Федоренко С. В. Декодирование (Ь, д)-кодов по обобщенным информационным совокупностям// Проблемы передачи информации. 1993. Т. 29. № 4. С. 94-98.

4. Крук Е. А., Федоренко С. В. Декодирование по обобщенным информационным совокупностям// Проблемы передачи информации. 1995. Т. 31. № 2. С. 54-61.

5. Мирончиков Е. Т., Федорвнко С. В. Об алгебраическом декодировании циклических кодов// Проблемы передачи информации. 1999. Т. 35. № 1. С. 44-48.

6. Трифонов П. В., Федоренко С. В. Метод быстрого вычисления преобразования Фурье над конечным полем// Проблемы передачи информации. 2003. Т. 39. № 3. С. 3-10.

7. Федоренко С. В. Метод вычисления дискретного преобразования Фурье над конечным полем// Проблемы передачи информации. 2006. Т. 42. № 2. С. 81-93.

8. Крук Е. А., Мирончиков Е. Т., Федоренко С. В. Декодирование блоковых линейных кодов по обобщенным информационным совокупностям// Радиотехника. 1997. № 2. С. 88-90.

9. Крук Е. А., Федоренко С. В. Комбинаторное декодирование в связи и криптографии// Научно-технические ведомости СПбГТУ. СПб.: Изд. СПбГТУ. 2002. № 3. С. 69-77.

10. Крук Е. А., Федоренко С. В. Самодуальные квазициклические коды// Научно-технические ведомости СПбГПУ. СПб.: Изд. СПбГТУ. 2004. № 1. С. 163-167.

11. Федоренко С. В. Простой алгоритм декодирования алгебраических кодов// Информационно-управляющие системы. 2008. № 3. С. 23-27.

12. Fedorenko S., Trifonov P. Finding roots of polynomials over finite fields// IEEE IVansactions on Communications. 2002. Vol. 50. N. 11. P. 1709-1711.

13. Fedorenko S., Trifonov P., Costa E. Improved hybrid algorithm for finding roots of error-locator polynomials// European Transactions on Telecommunications. 2003. Vol. 14. N. 5. P. 411416.

14. Costa E., Fedorenko S. V., Trifonov P. V. On computing the syndrome polynomial in Reed - Solomon decoder// European

Transactions on Telecommunications. 2004. Vol. 15. N. 4. P. 337342.

15. Fedorenko S. V. A simple algorithm for decoding Reed-Solomon codes and its relation to the Welch — Berlekamp algorithm// IEEE Transactions on Information Theory. Mar. 2005. Vol. 51. N. 3. P. 1196-1198.

16. Fedorenko S. V. Correction to "A simple algorithm for decoding Reed - Solomon codes and its relation to the Welch - Berlekamp algorithm"// IEEE Transactions on Information Theory. 2006. Vol. 52. N. 3. P. 1278.

17. Евсеев Г. С., Крук Е. А., Самуйлова С. В., Федоренко С. В. Устройство для декодирования циклических кодов. А.с. № 1396933 СССР от 15.01.88.

18. Costa Е., Fedorenko S., Krouk Е., Lott М.; Schulz Е., Trifonov P. Method and device for a communication system for finding roots of an error locator polynomial. European patent application, EP1367727 A1 dated 03.12.2003.

19. Крук E. А., Трояновский Б. К., Федоренко С. В, О программной реализации декодеров// Техника средств связи. Сер. ОТ. Вып. 4. М., 1987. С. 5-13.

20. Мирончиков Е. Т., Федоренко С. В. Декодирование {L,g)-кодов в стирающем канале// Тр. V совещания по распределенным вычислительным системам и сетям. Тез. докл. М., 1992. С. 190-191.

21. Krouk Е. A., Mironchikov Е. Т., Fedorenko S. V. Decoding by 5-sets: Proc. of the Fifth Joint Soviet-Swedish International Workshop on Information Theory at Moscow, USSR, January 1991. P. 113-115.

22. Asnis I. L., Fedorenko S. V. Tables of coverings for decoding by 5-sets// The Workshop on Information Protection. M., 1993. P. 22.

23. Asnis I. L., Fedorenko S. V., Krouk E. A., Mironchikov E. T. Tables of coverings for decoding by S-sets// Error control, cryptology, and speech compression: Lecture notes in computer science. Springer-Verlag. 1994. Vol. 829. P. 97-102.

24. Fedorenko S., Kolesnik V. Multi-step decoding of the iteration of Hamming codes: Proc. of the Seventh Joint Swedish-Russian International Workshop on Information Theory, St.Petersburg, Russia, 1995. P. 80-83.

25. Fedorenko S., Krouk E. About block circulant representation of linear codes: Proc. of Sixth International Workshop on Algebraic and Combinatorial Coding Theory, Pskov, Russia, 1998. P. 116— 118.

26. Fedorenko S. On the structure of linear block codes given the group of symmetry: Proc. of IEEE International Workshop on Concatenated codes, Ulm, Germany, 1999. P. 1-2.

27. Fedorenko S., Krouk E. The table decoders of quadratic-residue codes: Proc. of the Seventh International Workshop on Algebraic and Combinatorial Coding Theory at Bansko, Bulgaria, June 2000. P. 137-140.

28. Sorger U., Fedorenko S. The "Star Trellis" of the Golay Code: Proc. of Seventh International Workshop on Algebraic and Combinatorial Coding Theory at Bansko, Bulgaria, June 2000. P. 288-292.

29. Fedorenko S., Krouk E. A survey of the hard decision decoding for linear block codes: Proc. of the workshop on concepts in information theory, Breisach, Germany, June 2002. P. 15-18.

30. Fedorenko S., Krouk E. Decoding beyond the designed error correcting capability on the basis of supercodes: Proc. of the IEEE International Symposium on Information Theory at Lausanne, Switzerland, 2002. P. 89.

31. Fedorenko S., Trifonov P. On computing the fast Fourier transform over finite fields: Proc. of the Eighth International Workshop on Algebraic and Combinatorial Coding Theory at Itearskoe Selo, Russia, September 2002. P. 108-111.

32. Fedorenko S. V. The star trellis decoding of Reed - Solomon codes: Proc. of the XI international symposium on problems of redundancy in information and control systems at St.Petersburg, Russia, July 2007. P. 58-61.

Формат бумаги 60 х 84 1/16. Бумага офсетная. Усл. аеч. л. 2,75. Тираж 100 экз. Зак. ДОЗД!)

Отпечатано в редакционно-издательском центре ГУАП 190000, Санкт-Петербург, Б. Морская ул., 67

Введение

1. Комбинаторное декодирование линейных блоковых кодов

1.1. Декодирование по обобщенным информационным совокупностям.

1.1.1. Понятие обобщенной информационной совокупности. Алгоритм декодирования.

1.1.2. Построение т-покрытий из кодовых слов

1.1.3. Таблица декодеров по обобщенным информационным совокупностям.

1.2. Табличное декодирование

1.2.1. Синдромное декодирование.

1.2.2. Декодирование по информационным совокупностям

1.2.3. Декодирование в надкодах.

1.2.4. Комбинирование алгоритмов декодирования

1.2.5. Декодирование кодов с большой группой симметрии.

1.2.6. Декодирование квадратично-вычетных кодов

1.3. Асимптотика.

1.3.1. Обзор алгоритмов декодирования линейных блоковых кодов для декодеров с жесткими решениями.

1.3.2. Сложность декодирования линейных блоковых кодов.

1.4. Выводы.

2. Алгебраическое декодирование

2.1. Алгебраическое декодирование по обобщенным информационным совокупностям

2.1.1. Основные понятия и определения.

2.1.2. Укорочения (Ь,д)~кодов.

2.1.3. Применение декодирования укороченных (£5,£г5)-кодов.

2.2. "Генетическая" связь алгебраических методов декодирования

2.2.1. Основные понятия и определения.

2.2.2. Алгоритм Гао.

2.2.3. Оригинальный алгоритм Велча - Берлекэмпа

2.2.4. Интерпретация Чамберса.

2.2.5. Алгоритм Велча - Берлекэмпа в частотной области.

2.2.6. Вывод алгоритма Гао.

2.2.7. Расширенный алгоритм Евклида.

2.2.8. Корректность алгоритма Гао

2.2.9. Пример.

2.2.10. Замечания к разделу.

2.3. Декодирование в надкодах.

2.3.1. Основные определения.

2.3.2. Дополнительные тождества.

2.3.3. Алгоритм исправления трех ошибок.

2.3.4. Декодирование свыше конструктивного расстояния на основе надкодов.

2.3.5. Пример.

2.4. Выводы.

3. Вычисление дискретного преобразования Фурье над конечным полем

3.1. Вычисление корней многочлена.

3.1.1. Алгоритм быстрого поиска корней многочлена

3.1.2. Результаты моделирования

3.1.3. Специальные разложения многочленов

3.1.4. Гибридный метод

3.1.5. Аналитические методы вычисления корней многочленов степени до четырех.

3.1.6. Сравнение методов вычисления корней многочлена

3.2: Циклотомический алгоритм.

3.2.1. Основные понятия и определения.

3.2.2. Быстрое вычисление преобразования Фурье

3.2.3. Пример.

3.2.4. Сравнение сложности алгоритмов БПФ

3.3. Рекуррентный метод.

3.3.1. Основные понятия и определения.

3.3.2. Алгоритм Рейдера.

3.3.3. Свойства матрицы эквивалентного преобразования

3.3.4. Упорядочение чисел из полной системы вычетов

3.3.5. Быстрое вычисление ДПФ

3.3.6. Примеры вычисления ДПФ.

3.4. Вычисление синдрома.

3.4.1. Вычисление неполного ДПФ с помощью циклотомического алгоритма.

3.4.2. Вычисление неполного ДПФ с помощью рекуррентного метода.

3.5. Выводы.

4. Декодирование по кодовым решеткам

4.1. Представления кодов с заданной группой симметрии

4.1.1. Две конструкции кодов.

4.1.2. Приведение матриц кода к квазициклическому представлению.

4.2. Циклические замкнутые решетки.

4.3. Звездные решетки.

4.3.1. Представление кода Голея в виде звездной решетки.

4.3.2. Декодирование кода Голея по звездной решетке

4.3.3. Замечания к разделу.

4.4. Декодирование кодов Рида - Соломона по звездным решеткам.

4.4.1. Разложение Варди - Беэри.

4.4.2. Метод декодирования.

4.5. Выводы.

5. Вопросы реализации

Актуальность.проблемы; В.настоящее время обмен информацией при помощи технических средств происходит практически во всех областях человеческой деятельности. Обработка информации в приемно-передающих устройствах средств связи осуществляется с помощью алгоритмов кодирования и декодирования, а также быстрого вьгаисления дискретного преобразования Фурье, что позволяет повысить эффективность работы систем связи. Содержанием настоящей диссертационной работы являются теоретические и прикладные исследования системных связей и закономерностей функционирования систем передачи' информации для различных отраслей народного хозяйства с использованием современных методов обработки информации'. Для решения ряда научно-технических проблем, осуществляемых в настоящее время, необходимо повысить эффективность анализа обработки информации, надежность и качество используемых технических систем, применяющих современные методы кодирования и декодирования.

Для обеспечения помехоустойчивости передаваемой информации применяют корректирующие коды. Теория кодов, исправляющих ошибки, возникла в середине XX века. Большую роль в развитии помехоустойчивого кодирования сыграли монографии В. Д. Колесника и Е. Т. Мирончикова [25], Э. М. Габидулина и В. Б. Афанасьева [12], Е. А. Крука [31] и Р. Блейхута [7, 8, 61]. С момента возникновения теория помехоустойчивого кодирования была разделена на два направления, изучающие блоковые коды (которые рассмотрены в диссертационной работе) и сверточные коды. Теория блоковых кодов, в свою очередь, содержит комбинаторную и алгебраическую теории кодирования. В 60-е годы прошлого века были введены комбинаторные и алгебраические алгоритмы декодирования. Комбинаторные алгоритмы-декодирования применимы ко всем линейным блоковым кодам и исправляют ошибки, если их число не превосходит корректирующей способности кода, однако имеют относительно большую сложность. Алгебраические алгоритмы декодирования проще комбинаторных, но они применимы только для некоторых классов кодов. Приложение алгоритмов декодирования сверточных кодов для декодирования блоковых кодов привело к появлению новых методов декодирования блоковых кодов по кодовым решеткам.

Корректирующие коды получили широкое применение в задачах обработки, передачи, записи, хранения и защиты информации. В'настоящее время блоковые коды представлены в многочисленных технических приложениях, например, в стандартах CCSDS 101.0-В-6 (Consultative Committee for Space Data Systems), ITU-T G.975.1 (International Telecommunication Union) и IEEE 802.16 (The Institute of Electrical and Electronics Engineers).

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

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

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

Для достижения поставленной цели в работе исследуются следующие основные задачи.

1. Задача построения декодеров для ряда лучших кодов с наименьшей сложностью среди известных декодеров.

2. Задача построения эффективных декодеров алгебраических кодов.

3'. Выявление взаимосвязи различных алгебраических методов декодирования.

4. Методологическая задача вывода и доказательства корректности алгоритма Гао.

5. Задача построения эффективных методов вычисления корней многочленов над конечным полем.

6. Задача построения алгоритмов с низкой вычислительной сложностью для вычисления преобразования Фурье над конечным полем.

7. Задача построения новых типов решеток для линейных блоковых кодов.

8. Задача построения декодеров кодов Рида - Соломона по кодовым решеткам.

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

Научная новизна работы. Научная новизна работы заключается в следующем.

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

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

3. Выявлена взаимосвязь различных алгебраических методов декодирования, а также представлен оригинальный вывод и доказательство корректности алгоритма Гао.

4. Предложены эффективные методы вычисления корней многочленов над конечным полем.

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

6. Разработан новый тип звездных решеток для линейных блоковых кодов.

§ 1

7. Разработан метод декодирования кодов Рида - Соломона по кодовым решеткам.

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

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на:

XI Международном симпозиуме по проблеме избыточности в информационных системах (СПб, 2007);

Международных конференциях по алгебраической и комбинаторной теории кодирования (АССТ, 1990-2006);

Международном симпозиуме по теории информации (ЕЗГГ,

Лозанна, 2002); а также на семинарах: кафедры информационных систем и кафедры безопасности информационных систем Санкт-Петербургского государственного университета аэрокосмического приборостроения; кафедры распределенных вычислений и компьютерных сетей Санкт-Петербургского государственного политехнического университета; на постоянно действующем семинаре по теории кодирования

1 Института проблем передачи информации РАН (Москва).

Публикации. По теме диссертации опубликовано более 50 печатных трудов в научно-технических журналах, сборниках докладов и научно-технических сборниках, в том числе: монография, 14 статей в журналах, включенных в Перечень ВАК, и авторское свидетельство СССР.

Основные положения диссертации, выносимые на защиту.

1. Метод декодирования по обобщенным информационным совокупностям и табличное декодирование. 9 1 1

2. Метод декодирования алгебраических кодов на основе алгебраических методов укорочения кодов.

3. Взаимосвязь различных алгебраических методов декодирования.

4. Эффективные методы вычисления корней многочленов над конечным полем.

5. Алгоритмы вычисления преобразования Фурье над конечным полем.

6. Метод построения звездных решеток для линейных блоковых кодов.

7. Метод декодирования кодов Рида - Соломона по кодовым решеткам.

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения и списка литературы. Работа содержит 220 страниц машинописного текста, а список использованной литературы содержит 117 наименований.

Основные результаты работы можно сформулировать следующим образом.

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

2. Построенные декодеры алгебраических кодов на основе алгебраических методов укорочения кодов эффективны в стирающем канале.

3. Показано, что различные алгебраические методы декодирования тесно взаимосвязаны.

4. Предложенные вывод и доказательство корректности алгоритма Гао являются самыми простыми из известных описаний алгебраических методов декодирования.

5. Предложенные алгоритмы декодирования алгебраических кодов на основе надкодов для некоторых кодов имеют небольшую сложность.

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

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

8. Предложенные методы вычисления неполного преобразования Фурье над конечным полем эффективны для вычисления синдрома алгебраических кодов.

9. Код Голея может быть описан с помощью звездной решетки с наименьшим известным максимальным профилем сложности состояний.

10. Метод декодирования кодов Рида - Соломона по звездным решеткам обеспечивает возможность получения выигрыша на информационный бит до 2-3 дБ в канале с аддитивным белым гауссовым шумом по сравнению с классическим декодером кодов Рида - Соломона.

Предложенная работа подводит итог современным методам обработки информации и намечает их новые направления развития.

Заключение

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

1. Арлазаров В. Л., Диниц Е. А., Кронрод М. А., Фараджев И. А. Об экономном построении транзитивного замыкания графа// Докл. АН СССР. 1970. Т. 194. № 3. С. 487-488.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 535 с.

3. Афанасьев В. БГрушко И. И. Алгоритмы БПФ для полей 0^{2гп)// Сб. "Помехоустойчивое кодирование и надежность ЭВМ". М.: Наука, 1987. С. 33-55.

4. Бассалыго Л. А. Частное сообщение, 2003.

5. Берлекэмп Э. Алгебраическая теория кодирования. М.: Мир, 1971. 479 с.

6. Бояринов И. М., Кабатянский Г. А. Обобщенные коды Гоп-пы// Тр. IV Международного симпозиума по теории информации. Тез. докл. Москва Ленинград, 1976. Ч. 2. С. 21-23.

7. Блейхут Р. Теория и практика кодов, контролирующих ошибки. М.: Мир, 1986. 576 с.

8. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1989. 448 с.

9. Блиновский В. М. Нижняя асимптотическая граница для числа слов линейного кода в произвольной сфере с заданным радиусом из Проблемы передачи информации. 1987. Т. 23. № 2. С. 50-53.10. ван дер Варден Б. Л. Алгебра. М.: Наука, 1976. 648 с.

10. Виноградов И. М. Основы теории чисел. СПб.: Изд. Лань, 2004. 176 с.

11. Габидулин Э. М., Афанасьев В. Б. Кодирование в радиоэлектронике. М.: Радио и связь, 1986. 176 с.

12. Гантмахер Ф. Р. Теория матриц. М.: Наука, 1988. 552 с.

13. Гоппа В. Д. Рациональное представление кодов и (X, д)-коды// Проблемы передачи информации. 1971. Т. 7. № 3. С. 41-49.

14. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. М.: Мир, 1998. 703'с.

15. Додунеков С. М. Минимальная блоковая длина линейного д-ичного кода с заданными размерностью и кодовым расстоянием// Проблемы передачи информации. 1984. Т. 20. № 4. С. 11-22.

16. Думер И. И. Частное сообщение, 1986.

17. Думер И. И. Два алгоритма декодирования линейных кодов// Проблемы передачи информации. 1989. Т. 25. № 1. С. 24-32.

18. Евсеев Г. С. О сложности декодирования линейных кодов// Проблемы передачи информации. 1983. Т. 19. № 1. С. 3-8.

19. Евсеев Г. С., Крук Е. А. Об одном алгоритме декодирования КВ кодов// Тр. VI симпозиума по проблеме избыточности в информационных системах. Тез. докл. Л., 1974. Ч. 1. С. 2630.

20. Евсеев Г. С., Крук Е. А., Самуйлова С. В., Федоренко С. В. Устройство для декодирования циклических кодов. А.с. № 1396933 СССР от 15.01.88.

21. Захарова Т. Г. Вычисление преобразования Фурье в полях характеристики 2// Проблемы передачи информации. 1992. Т. 28. № 2. С. 62-77.

22. Захарова Т. Г. Применение преобразования Фурье в декодировании кодов Рида Соломона// Радиотехника. 1996. № 12. С. 55-57.

23. К асами Т., Токура Н., Ивадари Ё., Инагаки Я. Теория кодирования. М.: Мир, 1978. 576 с.

24. Колесник В. Д., Мирончиков Е. Т. Декодирование циклических кодов. М.: Связь, 1968. 252 с.

25. Кормен Т., Лейзерсон Ч.} Ривесгп Р. Алгоритмы: построение и анализ. М.: МЦНМО, 1999. 960 с.

26. Кларк Дж., мл., Кейн Дж. Кодирование с исправлением ошибок в системах цифровой связи. М.: Радио и связь, 1987. 392 с.

27. Кнут Д. Э. Искусство программирования. Т. 2. М.: Вильяме, 2000. 832 с. ;

28. Крук Е. А. Граница для сложности декодирования линейных блоковых кодов// Проблемы передачи информации. 1989. Т. 25. № 3. С". 103-107.

29. Крук Е. А. Комбинаторное декодирование линейных блоковых кодов: Монография. СПб.: ГУАП, 2007. 238 с.

30. Крук Е. А., Мирончиков Е. Т., Федоренко С. В. Декодирование блоковых линейных кодов по обобщенным информационным совокупностям// Радиотехника. 1997. № 2. С. 88-90.

31. Крук Е. А., Трояновский Б. К., Федоренко С. В. О программной реализации декодеров// Техника средств связи. Сер. ОТ. Вып. 4. М., 1987. С. 5-13.

32. Крук Е. А., Федоренко С. В. Декодирование по обобщенным информационным совокупностям// Проблемы передачи информации. 1995. Т. 31. № 2. С. 54-61.

33. Крук Е. А., Федоренко С. В. Комбинаторное декодирование в связи и криптографии// Научно-технические ведомости СПбГТУ. СПб.: Изд. СПбГТУ. 2002. № 3. С. 69-77.

34. Крук Е. А., Федоренко С. В. Самодуальные квазициклические коды// Научно-технические ведомости СПбГПУ. СПб.: Изд. СПбГТУ. 2004. № 1. С. 163-167.

35. Лид л Р., Нидеррайтер Г. Конечные поля. В 2 т. М.: Мир, 1988. 822 с.

36. Липницкий В. А, Стройникова Е. Д. О вычислении дискретного преобразования Фурье в полях Галуа// Сибирский журнал индустриальной математики. 2002. Т. V. № 3(11). С. 131-138.

37. Мак-Вильяме Ф. Дою., Слоэн Н. Дою. А. Теория кодов, исправляющих ошибки. М.: Связь, 1979. 744 с.

38. Мирончиков Е. Т., Федоренко С. В. Декодирование (Ь, д)-кодов в стирающем канале// Тр. V совещания по распределенным вычислительным системам и сетям. Тез. докл. М., 1992. С. 190-191.

39. Мирончиков Е. Т., Федоренко С. В. Декодирование {Ь,д)~ кодов по обобщенным информационным совокупностям// Проблемы передачи информации. 1993. Т. 29. № 4. С. 94-98.

40. Мирончиков Е. Т., Федоренко С. В. Об алгебраическом декодировании циклических кодов// Проблемы передачи информации. 1999. Т. 35. № 1. С. 44-48.

41. Морелос-Сарагоса Р. Искусство помехоустойчивого кодирования. Методы, алгоритмы, применение. М.: Техносфера, 2005. 320 с.

42. Муттер В. М. Основы помехоустойчивой телепередачи информации. Л.: Энергоатомиздат, 1990. 288 с.

43. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток. М.: Радио и связь, 1985. 248 с.

44. Оппенгейм А., Шафер Р. Цифровая обработка сигналов. М.: Техносфера, 2006. 856 с.

45. Питерсон У., Уэлдон Э. Коды, исправляющие ошибки. М.: Мир, 1976. 596 с.

46. Трифонов П. ВФедоренко С. В. Метод быстрого вычисления преобразования Фурье над конечным полем// Проблемы передачи информации. 2003. Т. 39. № 3. С. 3-10.

47. Федоренко С. В. Сложность декодирования линейных блоковых кодов// Проблемы передачи информации. 1993. Т. 29. № 4. С. 18-23.

48. Федоренко С. В. Декодирование линейных блоковых кодов по обобщенным информационным совокупностям: Автореф. дис.: канд. техн. наук. СПб., 1994. 16 с.

49. Федоренко С. В. Метод вычисления дискретного преобразования Фурье над конечным полем// Проблемы передачи информации. 2006. Т. 42. № 2. С. 81-93.

50. Федоренко С. В. Методы быстрого декодирования линейных блоковых кодов: Монография. СПб.: ГУАП, 2008. 199 с.

51. Федоренко С. В. Простой алгоритм декодирования алгебраических кодов// Информационно-управляющие системы. 2008. № 3. С. 23-27.

52. Эрдёш П., Спенсер Дж. Вероятностные методы в комбинаторике. М.: Мир, 1976. 133 с.

53. Afanasyev V. On complexity of FFT over finite field: Proc. of the Sixth Joint Swedish-Russian International Workshop on Information Theory, Molle, Sweden. August 1993. P. 315-3191

54. Asnis I. L., FedorenkoS. V. Tables of coverings for decoding by S-sets// The Workshop on Information Protection. M., 1993. P. 22.

55. Asnis I. L., Fedorenko S. V., Krouk E. A.,. Mironchikov E. T. Tables of coverings for decoding by 5-sets// Error control, cryptology, and speech compression: Lecture notes in computer science. Springer-Verlag. 1994. Vol. 829. P. 97-102.

56. Assmus E. F. Jr., Matbson II. F. Jr. New 5-designs// Journal of Combinatorial Theory. 1969: Vol. 6; N. 6. P. 122-151.

57. Barg A. Complexity issues in coding theory// Handbook of Coding Theory. Vol. 1/ Pless V., Huffman W. C., Eds., Amsterdam, The Netherlands: Elsevier Science, 1998. P. 649 754.

58. Barg A., Krouk E., van Tilborg II. C. A. On the complexity of minimum distance decoding of long linear codes// IEEE Transactions on Information Theory. July 1999. Vol. 45. P. 13921405.

59. Blahut R. E. Algebraic Codes on Lines, Planes, and Curves: An Engineering Approach. Cambridge, U.K.: Cambridge University Press, 2008. 543 p.

60. BossertM. Channel coding for telecommunications. John Wiley & Sons, Ltd, 1999. 496 p. '

61. Calderbank A. R., Forney G. D., Vardy A. Minimal tail-biting trellises: the Golay code and more// IEEE Transactions on Information Theory. 1999. Vol. 45. N. 5. P. 1435-1455.

62. Chambers W. G. Solution of Welch Berlekamp key equation by Euclidean algorithm// Electronics Letters. 1993. Vol; 29. N. 11. P. 1031.

63. Chase D. A class of algorithms for decoding block codes with channel measurement information// IEEE Transactions on Information Theory. Jan. 1972: Vol. 18. P. 170-182;

64. Chen C.-L. Formulas for the1 solutions of quadratic equations over GF(2m)// IEEE Transactions on Information Theory. 1982. Vol. 28. N. 5. P. 792-794.

65. Chien R. T. Cyclic decoding procedures for Bose Chaudhuri -Hocquenghem codes// IEEE Transactions on Information Theory. 1964. Vol. 10. N. 4. P. 357-363.

66. Chien R. T., Cunningham B. D., Oldham I. B. Hybrid methods for finding roots of a polynomial with application to BCH decoding// IEEE Transactions on Information Theory. 1969. Vol. 15. N. 2. P. 329-335.

67. Coffey J. T.; Goodman R. M. F. The complexity of information set decoding// IEEE Transactions on Information Theory. 1990. Vol. 35. N. 5. P. 1031-1037.

68. Costa E., Fedorenko S., Krouk E.} Lott M., Schulz E., Trifonov P. Method and device for a communication system for finding roots of an error locator polynomial. European patent application, EP1367727 A1 dated 03.12.2003.

69. Costa E., Fedorenko S. V., Trifonov P. V. On computing the syndrome polynomial in Reed Solomon decoder// European Transactions on Telecommunications. 2004. Vol. 15. N. 4. P. 337342.

70. Dumer I. On minimum distance decoding of linear codes: Proc. of the Fifth Joint Soviet-Swedish International Workshop on Information Theory at Moscow, USSR, January 1991. P. 50-52.

71. Elia M. Algebraic decoding of the (23,12,7) Golay code// IEEE Transactions on Information Theory. 1987. Vol. 33. N. 1. P. 150151.

72. Eklund a, Marks R. B., Stanwood K. L., Wang S. IEEE standard 802.16: a technical overview of the WirelessMAN air interface for broadband wireless access// IEEE Communications Magazine. June 2002. Vol. 40. N. 6. P. 98-107.

73. Fedorenko S. On the structure of linear block codes given the group of symmetry: Proc. of IEEE International Workshop on Concatenated codes, Ulm, Germany, 1999. P. 1-2.

74. Fedorenko S. V. A simple algorithm for decoding Reed -Solomon codes and its relation to the Welch — Berlekamp algorithm// IEEE Transactions on Information Theory. Mar. 2005. Vol. 51. N. 3. P. 1196-1198.

75. Fedorenko S. V. Correction to "A simple algorithm for decoding Reed Solomon codes and its relation to the Welch - Berlekamp algorithm"// IEEE Transactions on Information Theory. 2006. Vol. 52. N. 3. P. 1278.

76. Fedorenko S., Krouk E. About block circulant representation of linear codes: Proc. of Sixth International Workshop on Algebraic and Combinatorial Coding Theory, Pskov, Russia, 1998. P. 116118.

77. Fedorenko S., Krouk E. The table decoders of quadratic-residue codes: Proc. of the Seventh International Workshop on Algebraic and Combinatorial Coding Theory at Bansko, Bulgaria, June 2000. P. 137-140.

78. Fedorenko S., Krouk E. A survey of the hard decision decoding for linear block codes: Proc. of the workshop on concepts in information theory, Breisach, Germany, June 2002. P. 15-18.

79. Fedorenko S., Krouk E. Decoding beyond; the designed error correcting, capability on the basis of supercodes: Proc. . of the IEEE International Symposium on Information Theory at Lausanne, Switzerland, 2002. P. 89.

80. Fedorenko S., Trifonov P. On computing the fast Fourier transform over finite fields: Proc. of the Eighth International Workshop on Algebraic and Combinatorial Coding Theory at Tsarskoe Selo, Russia, September 2002. P. 108-111.

81. Fedorenko S., Trifonov P. Finding roots of polynomials; over finite fields// IEEE Transactions on Communications. 2002. Vol. 50. N. 11. P. 1709 1711.

82. Fedorenko S., Trifonov P., Costa E. Improved hybrid algorithm for finding roots of error-locator polynomials// European Transactions on Telecommunications. 2003. Vol. 14. N. 5. P. 411416.

83. Feng, G.-L., Tzeng K. K. A new procedure for decoding cyclic and BOH codes up to actual minimum distance// IEEE Transactions on. Information Theory. 1994. Vol. 40. N. 5. P. 1364-1374.

84. Forney G. D. Jr. Generalized minimum distance decoding// IEEE Transactions on Information Theory. Apr. 1966. Vol. 12. P. 125-131.

85. Freudenberger J. On bounded distance list decoding based on supercodes: Proc. of the Seventh International Symposium on Communication Theory and Applications, Ambleside, UK, 2003. P. 7-12.

86. Gao S. A new algorithm for decoding Reed Solomon codes// Communications, Information and; Network Security/ Bhargava V., Poor H. V., Tarokh V., Yoon S., Eds. Norwell, MA: Kluwer, 2003. Vol. 712. P. 55-68.

87. Gemmell PSudan M. Highly resilient correctors for polynomials// Information Processing Letters. 1992. Vol. 43. N. 4. P. 169-174.

88. Hagenauer J., Kolesnik V. On a'posteriori stabilization and multi-step decoding: Proc. of the Seventh Joint Swedish-Russian International Workshop on Information Theory, St.Petersburg, Russia, 1995. P. 96-100.

89. Haiford T. R., Ponnampalam V., Grant A. J., Chugg K. M. Soft-in soft-out decoding of Reed Solomon codes based on Vardy and Be'ery's decomposition// IEEE Transactions on Information Theory. Dec. 2005. Vol. 51. P. 4363-4368.c

90. Heigert H. J., Stinaff R. D. Minimum-Distance Bounds for Binary Linear Codes// IEEE Transactions on Information Theory. 1973. Vol. 19. N. 3. P. 344-356.

91. Hong J., Vetterli M. Computing m DFT's over GF(q) with one DFT over GF {qm)// IEEE Transactions on Information Theory. January 1993. Vol. 39. N. 1. P. 271-274.

92. Justesen J. On the complexity of decoding Reed Solomon codes// IEEE Transactions on Information Theory. Mar. 1976. Vol. 22. N. 2. P. 237-238.

93. Kabatiansky G., Krouk E,, Semenov S. Error correcting coding and security for data networks: Analysis of the superchannel concept. John Wiley & Sons, Ltd, 2005. 278 p.

94. Kasami T. A Decoding Procedure for Multiple-Error-Correcting Cyclic Codes// IEEE Transactions on Information Theory. 1964. Vol. 10. N. 2. P. 134-138.

95. Krouk E. A., Mironchikov E. T., Fedorenko S. V. Decoding by S-sets: Proc. of the Fifth Joint Soviet-Swedish International Workshop on Information Theory at Moscow, USSR, January 1991. P. 113-115.

96. Levitin L.; Hartmann C. R. P. A new approach to the general minimum distance decoding problem: The zero-neighbors algorithm// IEEE Transactions on Information Theory. 1985. Vol. 31. N. 3. P. 378-384.

97. MacWilliams F. J. Permutation Decoding of Systematic Codes// Bell System Technical Journal. 1964. Vol. 43. P. 485505.

98. Moenck R. T. Fast computation of GCDs: Proc. of the 5th Annual ACM Symposium on Theory of Computing, Austin, TX, 1973. P. 142-151.

99. Morii M., Kasahara M. Generalized key-equation of remainder decoding algorithm for Reed Solomon codes// \ IEEE Transactions on Information Theory. Nov. 1992. Vol. 38. N. 6. P.1801-1807.

100. Prange E. The Use of Information Sets in Decoding'Cyclic Codes// IRE Transactions on Information Theory. 1962. Vol. 8. N. 5. P. S5-S9.

101. Rader C. M. Discrete Fourier transforms when the number of data samples is prime: Proc. of the IEEE. 1968. Vol. 56. N. 6. P. 1107-1108.

102. Rudolph L. D., Mitchell M. E. Implementation of Decoders for Cyclic Codes// IEEE Transactions on Information Theory. 1964. Vol. 10. N. 3. P. 259-260.

103. Shiozaki A. Decoding of redundant residue polynomial codes using Euclid's algorithm// IEEE Transactions on Information Theory. Sep. 1988. Vol. 34. N. 5. P. 1351-1354.

104. Sorger U., Fedorenko S. The "Star Trellis" of the Golay Code: Proc. of Seventh International Workshop on Algebraic and Combinatorial Coding Theory at Bansko, Bulgaria, June 2000. P. 288-292.

105. Sugiyama Y., Kasahara MHirasawa S., Namekawa T. A method for solving key equation for decoding Goppa codes// Information and Control. 1975. Vol. 27: P. 87-99.

106. Trifonov P. Matrix-Vector Multiplication via Erasure Decoding: Proc. of the XI international symposium on problems of redundancy in information and control systems at St.Petersburg, Russia, July 2007. P. 104-108.

107. Wang Y., Zhu X. A fast algorithm for the Fourier transform over finite fields and its VLSI implementation// IEEE Journal on Selected Areas in Communications. Apr. 1988. Vol. 6. N. 3. P. 572-577.

108. Welch L., Berlekamp E.R. Error correction for algebraic block codes. U.S. Patent 4,633,470, Sep. 27, 1983.

109. Williamson G. J. Apparatus and method for error correction. U.S. Patent 5,905,740, May 1999.

110. Wolfmann J. A Permutation Decoding of the (24,12,8) Goley Code// IEEE Transactions on Information Theory. 1983. Vol. 29. N. 5. P. 748-751.1991. Vol. 39. P. 440-444.