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



" "1&АНКТ-ПЕТЕРБУРГСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ 'Ь ь.. АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ

►п Й1Н Ш?

I. П V Правах рукописи

ФЕДОРЕНКО Сергей Валентинович

ДЕКОДИРОВАНИЕ ЛИНЕЙНЫХ БЛОКОВЫХ КОДОВ ПО ОБОБЩЕННЫМ ИНФОРМАЦИОННЫМ СОВОКУПНОСТЯМ

Специальность 05.13.01 - Управление в технических

системах

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

С. -Петербург 1994

! / . »

Работа выполнена в Государственной академии аэрокосмического приборостроения, г. Санкт-Петербург •.•

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

профессор Е. Т. Мирончиков

Официальные оппоненты:

доктор технических наук, профессор И.Л. Ерош

кандидат технических наук, старший научный сотрудник В.Н. Степано!

Ведущая организация - Санкт-Петербургский институт

информатики и автоматизации РАН

Защита диссертации состоится ■ _ " _ " 1994 г.

в _ час._ мин. на заседании специализированного совета

К 063.2i.03 Государственной академии аэрокосмического приборостроения по адресу:

190000, Санкт-Петербург, ул. Большая Морская, 6? С диссертацией можно ознакомиться в библиотеке института. Автореферат разослан ■ _ ■ _ " 1994 г.

Ученый секретарь специализированного совета

д. т. н., профессор В. В. Фильчаков

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Методы исследования. Основными методами исследования являются теоретические исследования с использованием методов теории кодирования и комбинаторной теории. При построении таблиц проводились вычисления с помощью ЭВМ.

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

- предложены алгоритмы декодирования по обобщенным информационным совокупностям:

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

- оценена сложность алгоритмов декодирования для почти всех блоковых линейных кодов;

- предложено использовать укороченные коды для декодирования основных кодов;

- предложены алгебраические методы укорочения кодов-,

- введен новый класс кодов, включающий в себя классы абелевых кодов и -кодов (кодов Гоппы);

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

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

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

- построить новые коды с простыни алгоритмами декодирования.

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

Апробация работы. Основные положения и результаты диссертации докладывались и обсуждались на v Международной конференции по теории информации (Москва. 1991), на конференции по защите информации (Москва, 1993), а также на семинарах пс теории информации и кодирования кафедры информационных систеь СПГААП.

Публикации. По теме диссертации опубликовано и печатных трудов в научно-технических журналах, сборниках докладо! и научно-технических сборниках, в том числе получено 1 авторское свидетельство.

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

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

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

- класс многомерных сь,о-кодов.

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

ОСЕОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Пусть £ - линейный <п,к,а)-код над полем в метрике

Хэмминга со скоростью рик/п. Пронумер\ч-н позиции кодового слова

числами из множества N = {1,2.....п). Множество чисел

.....к.^ < ■ • • называется информационной

совокупностью кода, если задание компонент кодового слова с элементами из V однозначно определяет это слово. Для произвольного вектора /'-(г .с,.....г > длины п и множества

12 п

.....<■ • • определим вектор /и> как

подвектор длины 5 вектора / *■(.)) = ((• , г .....г >. Аналогично

м ■}г _

ДЛЯ произвольной матрицы вида М-Ст ; .. . ; т ], где через т , 1 = 1,п,

1 п I

обозначены столбцы этой матрицы, и множества J определим матрицу ми> как подматрицу матрицы м, составленную из столбцов этой матрицы с номерами ИЗ .1 ми> = 1т ;...;т 1. Пусть ь - принятое

из канала слово ь=а+е. а - переданный кодовый вектор, а е -вектор ошибок. Информационная совокупность ? называется свободной от ошибок для вектора ошибок е, -если е(?>-о. По свободной от ошибок информационной совокупности можно правильно восстановить переданный кодовый вектор. Если во множестве информационных совокупностей Г~=с -р > Для любого вектора ошибок е, вес Хэмминга которого у/(е)<*. найдется свободная- от ошибок информационная совокупность, то множество Г будет достаточным для исправления ошибок кратности до Алгоритм декодирования по информационным совокупностям при этом состоит в переборе по информационным совокупностям из множества Г с целью поиска информационной совокупности, свободной от ошибок.

Пусть Г = } - множество информационных совокупностей, достаточное для исправления ошибок кратности до са-и/г! в коде где через 1x1 обозначена целая часть числа х. Для каждой

информационной совокупности 6 Г построим порождающую матривд кода Gt. в которой на позициях из содержится единична? подматрица

G1 = t G С 9f ) Г1 G,

где iGC^n"1 - матрица, обратная к G(? ), a.G - произвольна; порождающая матрица кода S. Тогда алгоритм декодирования пс информационным совокупностям состоит из следующих шагов. 1. Для каждой 9 б Г вычисляем расстояние Хэмминга межд)

А 1 А

векторами Ь И at=bCVj)-Gj : d(b,a ).

г. Если для некоторого i выполняется неравенство «нь.а > < t, тс единственным декодированным вариантом принятого вектора i является вектор а( ;

иначе считаем, что произошла неисправляемая ошибка.

Сложность декодирования по информационным совокупности) определяется модностью множества Г. достаточного длJ декодирования ошибок из множества Et - ошибок кратности до t.

Для каждой информационной совокупности у обозначим через : множество позиций, дополнительных к у: i-Nx? (мощность множеств; у |v|-n-k=r>. Тогда, чтобы множество Г={?) было достаточным дл)

исправления ошибок из Et необходимо, чтобы множество Г = {?> был< мсп,г.t>-покрытием (то есть таким множеством г-подмножест1 множества N. что любое t-подмножество N содержится хотя бы ] одном г-подмножестве ?).

Обобщенной информационной совокупностью j назовем множеств! номеров позиций кодового слова

J = (j .....j }, 1 < m < п.

1 И

такое, что rank G(J) = k-Д, ГДв 0 < Д < к. Очевидно, ЧТ1

информационная совокупность .....является обобщенно]

информационной совокупностью. Если J есть обобщенна: информационная совокупность, то любому подвектору a(J), а € § соответствует СПИСОК ИЗ q' КОДОВЫХ СЛОВ В ТОМ смысле, ЧТО В КОД1 существует ровно q^ слов, совпадающих между собой и с векторо!

аи> на позициях из множества Через сь? обозначим список из кодовых слов, совпадающих с вектором ь на множестве з.

Отыскание обобщенной информационной совокупности, свободной от ошибок не дает при Д>о декодированного варианта а принятого слова ь, но дает список слов, среди которых этот вариант

присутствует. Нахождение декодированного варианта в списке может быть осуществлено, например, перебором, результатом которого

Л А

является такой вектор а е 1.^<ь>, что снь.ахи

Матрицу во) можно рассматривать как порождающую матрицу кода §и>, полученного укорочением 5 на позиции из I (J=NsJ). Пусть л - расстояние кода Если число ошибок в подвекторе

принятого слова ьи> не превышает ^»пй -п/21, то декодируя вектор ьо) в коде можно получить подвектор вектора ошибок еО). Наложив на вектор ь покрывающий вектор <з, совпадающий с ей) на J и имеющий нули на остальных позициях, получим вектор ь-<з, для которого обобщенная информационная совокупность л свободна от ошибок. Среди векторов списка имеется

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

Множество обобщенных информационных совокупностей Г=и) является достаточным для декодирования ошибок из . если для любого вектора ь=а+е Се е еь>, во множестве Г найдется обобщенная информационная совокупность для которой !^сь-<3) содержит вектор а.

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

1.1. Производим декодирование вектора ьи э в вектор аи >.

А I I

Если « г, то в качестве ао^ берем ьс^).

1.2. Строим покрывающий вектор <?1 по вектору ьо( ) - аи ).

1.3. Образуем список векторов кода I. сь-<? >.

\ 1

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

8

I. (Ь1 = и L, (Ь-() ). «.X

-6' А А

3. Выбираем В I. (Ь) такой вектор а, что <НЬ.а><1; иначе считаем, что произошла неисправляемая ошибка.

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

Расстояние Варшамова-Гилберта с!вг в метрике Хэмминга есть минимальное целое число, удовлетворяющее неравенству

"вг

1С)

, . п(1-И)

(ч-1) > Ч

1 = 0

Семейство р-подмножеств множества N. содержащее все 1-подмножества (п>р>1> называется мсп,р.1>-покрытием. Известно, что существует мсп,р,1)-покрытие с мощностью

(?) ,р, С

М ( п, р, 1) < —;----( 1 + 1п| £ ) С оСп)

(?) (?)

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

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

Справедлива следующая теорема об алгоритме построенш неслучайного мсп.р,1)-покрытия.

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

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

= 11Л1

п -» а

1од Т ч

X

где т - сложность алгоритма, то есть минимально возможное числс операций над ч-ичными символами при реализации алгоритм;

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

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

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

Для каждого 1 е [1, м<п, < 1-юп.<1 > 1 выполняем следующие действия.

1. Методом построения неслучайного мсп, с 1-Юп,<1„„)-покрытия

_ вг

выбираем множество ^ . |1( | = яп.

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

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

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

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

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

Пусть а - кодовое слово линейного (п,к,<п-кода а ч/(а) и

i - его вес и множество нулевых позиций соответственно. Тогдг укороченный код su > является cn-w(a),k-n-кодом с расстоянием

- [-^<4

dj > d - | W(a)|. С1 :

а

если W(a) <

4-1

Множество I задает таким образом обобщенную информационну! совокупность. Если вес вектора ошибок е с Iа > не превышает ^ - г с 1 -1)/2 з, то соответствующий список (ь-о), получаемый I

а а а

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

Поэтому для построения множества обобщенных информационны: совокупностей, обеспечивающего декодирование ошибок из Еь достаточно выбрать множество а-(а) кодовых слов кода ! <и(а> < ^1 d>, удовлетворяющее следующему свойству.

Если для любого вектора е (е е > найдется слово а е , такое, что вес вектора е<7а>

ШСе(Т >) > х = 1-1, , а а I

а

где т° множество Г = Па | а е а) будет достаточным дл:

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

Для построения т-покрытия используем покрытия Турана Покрытием Турана кп.^г) называется такое семейств' г-подмножеств множества n. что всякое i-подмножество множества ] содержит по крайней мере одно из этих т-подмножеств.

В большинстве работ, посвященных построению покрытий Турана множество ы определенным образом разбивается на подмножества vJ _ 1

^1,1, и = II V . В т с п, и г)-покрытие включаются все J

т-подмножества множества V для всех ^1.1.

Кодовое слово а € s назовем вложенным в множество чисел

V с N, если Та с v. Произвольное множество кодовых слов сf > е §.

называется вложенным в множество, чисел v, если каждое слово

f б if) вложено в множество v.

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

Лемма 1. Все слова Cn,k.d)-кода 5 с проверочной матрицей н,

вложенные в некоторое множество v. образуют линейный

с|V|. V - rank нсV),d )-код ^ с проверочной матрицей нсV), где

d >d. V

Лемма г. Пусть а - слово двоичного кода & веса 2d и rank

H(Ta)=2d-ü, тогда все слова веса d кода с проверочной матрицей

нсТ ) образуют м(2d,d,Л-1)-покрытие, вложенное в множество Т . а а

Лемма з. Для любого q-ичного (п.к)-кода 5 и множества ve ы

|V| - rank GCV> = г - rank HCV),

где v-Nsv, r=n-k, g и н - порождающая и проверочная матрицы кода 5 соответственно.

Следствие. Для любого самодуального (п,п/2>-кода 5 с порождающей матрицей с и произвольного множества v с ы,

I V| = п/2,

rank GСV) = rank GСV).

Для построения декодера по обобщенным информационным совокупностям (п,к)-кода исправляющего t ошибок, необходимо построить т-покрытие кодовыми словами веса v, t=t-i<d -n/2i,

а

где d( определяется соотношением <п.

а

Будем искать r-покрытие в два этапа.

1. На первом этапе строится т(n,t.г)-покрытие Турана как объединение г-подмножеств множеств чисел v^,vz.....v .

2. На втором этапе на каждом блоке v , i =771, строится M(|vi I.WCa^ ),г)-покрытие из кодовых слов.

Для сокращения перебора на втором этапе могут быть использованы приведенные выше леммы.

При этом в качестве множеств v.....на первом этапе

должны быть выбраны множества I .....Т , где I - множество

ai ai ai

ненулевых позиций вектора е S и 2d. j = i. а. Тогда в силу

леммы 2 векторы веса d кода . j = 1.1, образуют

j

мс2d. d,Aj-n-покрытие из кодовых слов, вложенное во множество v ,

Где Aj = 2d - rank H(V ).

Множество покрытий M<2d,dtA -п задает декодер кода *§ по обобщенным информационным совокупностям, исправляющий t ошибок, если

min С Л - 1) > Т.

J J

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

В третьей главе рассматриваются алгебраические укорочения и вводятся многомерные (l,g>-коды.

Рассмотрим класс CL,g)-кодов (обобщенных кодов Гоппы). Напомним определение cL.g)-кодов. Пусть l - множество линейно-независимых над gf cq) рациональных функций

l =

h h h 12 n

Z —oi ' Z-d ..... Z-ol

12 n

«(, е этся"), п < q°, а генераторный многочлен д(г> есть

приведенный многочлен с коэффициентами из поля GF(q°), причем

д(о( для всех 1 = 1,п. С каждым вектором а = Са ,а .....а ) над

I 1 г п

GFcq) свяжем рациональную функцию

h,

L^ 1 z-d '—1 1 1 = 1

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

0 mod g(z).

Известно, что расстояние (L.gj-кода не меньше, чем deg g(z) + i. где через deg g(z) обозначена степень многочлена g<z), а алгебраические алгоритмы декодирования <1..д>-кода

ПОЗВОЛЯЮТ исправлять ДО = [ deg^g(z) j ошибок_

Если для некоторого кода 5 его укорочение so) допускает алгебраические методы декодирования, то код &и> назовем алгебраическим укорочением кода S. Любое укорочение типа выкалывание кодовых координат при |j| = s > n-d+i. применяемое к классу (L,g)-кодов, приводит также к (L.g)-кодам и, следовательно, допускает алгебраические методы декодирования.

Пусть & есть (L,g)-код. Каждое множество чисел

j с (1,2.....п>, модность которого |j| = s > n-d + i, является

обобщенной информационной совокупностью и задает укороченный 5(j)-kofl. Для декодирования кода scj> алгебраическими методами необходимо описать его как (L.g)-код.

Теорема г. Если |j|=s>n-d+i, то код S(J) принадлежит классу с l,g)-кодов.

Пусть принятый из канала вектор ь=а+е, а - кодовый вектор, а е - вектор ошибки. Рассмотрим задачу исправления до t ошибок с l,g)-кодом, если его. укороченые cls,g^)-коды допускают

[deg g (z) -i

-~- ошибок.

Если вес Хэмминга вектора ошибки wcext, то для декодирования достаточно задать семейство обобщенных информационных совокупностей с J >, в котором для некоторой обобщенной информационной совокупности j е {j> выполняется неравенство wcecj))<r. Каждой обобщенной информационной совокупности j е {j} соответствует свой укороченный (Ьа,д>)-код, а алгоритм декодирования основного кода будет состоять в декодировании всех сl ,g )-кодов, причем после каждого декодирования укороченного кода вычисляется декодированный вариант кодового вектора а и проверяется выполнение условия не превышения расстоянием Хэмминга между принятым вектором и а числа t. Сложность данного алгоритма

n h

L 3 1=1

определяется мощностью семейства и) и сложностью декодировани укороченного сь , д )-кода. Задача построения минимальног

3 з

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

Рассмотрим задачу исправления ошибок и стираний. Введе! алгебраический алгоритм декодирования, основанный н; декодировании укороченных (I. .д^>-кодов. Известно, что код * исправляет р ошибок и V стираний, если гр+у ч ¿ед д<г>. Выбере* обобщенную информационную совокупность как множество все? нестертых позиций, тогда <1. ,д )-код, соответствующий это* обобщенной информационной совокупности, способен исправлять дс

г = ^ -9е** " v j > Р ошибок. Итак, декодирование основногс

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

Сформулируем алгоритм декодирования с I..д^)-кода в стирающее канале.

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

2. Построим с^.д )-код для множества }.

3. Некоторым алгебраическим методом декодируем укороченный <1. ,д )-код и исправляем в нем до г > р ошибок.

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

Введем класс многомерных и.д)-кодов (на примере двумерных). Пусть и - множество линейно-независимых над егсд) рациональных функций, 1=1,п.

где г <х,у) и ь1(х,у) - взаимно-простые Многочлены от двух переменных с коэффициентами из поля срсд"), а генераторный

многочлен дСх,у)=х'у* взаимно-прост со всеми ь1(х.у>. С каждым вектором а=<а1.аг.....ап) над сгсср свяжем рациональную функцию

г- Г^х.у) а1 Ь^х.у)

Тогда двумерный (ь.д)-код длины п состоит из всех таких векторов

а , ЧТО

®1 Ь1(х.у)

1 = 1

О той д(х,у).

Обобщим класс многомерных (1-,д)-кодов на многомерные (1..б>-коды. Пусть генераторное множество многочленов <х,у>),

1 к _

где д (х.у)-х J у . j = l.l. причем все д^х.у) взаимно-простые со всеми ь1(х.у). Определим множество индексов синдрома

=

<1. Л

<!.,]>£ П

т= 1

К 1

П

•1<к_

Вектору а-са ,а .....а^ > над огсд) поставим в соответствие

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

Г Г1(х,у) Г Г ч

а1 Ь^х.у) - 2- Ъ 5п х у •

1=0 J =о

Двумерный си-код длины п состоит из всех таких векторов а, для которых Б -0 при всех <1.л е 1Б.

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

Матрице а=(а1 ),

1=о,р-1, j=o,p-l, над бгсд) поставим в

соответствие многочлен от двух переменных

р-1 Р;>1

а<х,у) = ^ ^ а1к х1 у" . 1=0 к = 0

Пара элементов с a1) называется нулем абелева кода если aj любого а е s

аСс/ ,(3-1 )=0.

Пусть и - множество локаторов нулей кода Абелев код состоит у всех таких матриц а, для которых аы1 при всех а,,)) е I

<2Ю-1)/р

Если ыр-эр-1 и с<-|3-0 . где в - примитивный элемент пол

бгсг"). то абелев код 5 называется двоичным абелевым (р.р)-кодои Сформулируем несколько утверждений про свойства абелевь кодов.

Теорема з. Если множество линейно-независимых над эр ее] рациональных функций

L =

( ltd' X) ( U0J у)

(2

1=о.р-1. j=o,p-1, сг-рр-1 и в - генераторное множество, т с I., о-код является абелевым с р. р) -кодом.

Теорема 4. Если абелев (р.р)-код 5 задан множество линейно-независимых над бг^) рациональных функций (2)

1 к _

генераторным множеством в=1д (х.у)), д[(х,у)-х у 1=1,г, т конструктивное расстояние кода 5 равно

1

d = miri d.

l = i , г

где

d

1

1 к > 2(1 ♦к ) ПРИ g (х.у)-х 1 у . 1 ,к >о

Ii 1 11

1+1 ill- нечетное число

х|+2 при Я|<х.у)-х ИЛИ У . . четное число.

Теорема 5. Так асе как и классические (1.,д>-коды. многомерные (I.,д)-коды допускают алгебраические укорочения.

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ РАБОТЫ

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

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

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

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

5. Получена оценка конструктивного расстояния для абелевых кодов, являющихся многомерными (1,о-кодами с простым алгоритмом декодирования.

По теме диссертации опубликованы следующие работы-.

1. Федоренко C.B. Сложность декодирования линейных блоковь кодов // Пробл. передачи информ. 1993. Т.гэ. NU. С.18-23.

г. Мирончиков Е.Т., Федоренко C.B. Декодирование (L.g)-KOflc по обобщенным информационным совокупностям // Пробл. переда1 информ. 1993. Т.29. №4. С.94-99.

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

4. Федоренко C.B. К оценке сложности программной реализавд блоковых кодов // В сб. Пробл. обработки и передачи информации СПб.: ЛИАП, 1991. С.66-72.

5. Крук E.ff., Трояновский Б. К. , Федоренко C.B. О сложност программной реализации блоковых кодов //Тр. X симпозиума п проблеме избыточности в информационных системах. Тез.докл. Ч.i Л.: ЛИАП, 1989. С. 38.

6. Крук Е.А., Мирончиков Е.Т., Федоренко C.B. Декодировани по s-совокупностям // Тр. V Междунар. семинара по теори информации -Сверточные коды; связь с многими пользователями" Тез.докл. Москва, 1ээо. С.113-115.

7. Мирончиков Е.Т., Федоренко C.B. Декодирование сь,д)-кодо в стирающем канале // Тр. v Совещания по распределении вычислительным системам и сетям. Тез.докл. Москва, 1992 С.190-191.

8. Крук E.ff., Федоренко C.B. Табличные декодеры блоковь кодов // Тр. 16 всесоюзной школы-семинара по вычислительны сетям. Тез.докл. 4.2. Москва-Винница, 1991. С.49-52.

9. Asnis I.L., Fedorenko S.V. Tables of coverings fo decoding by S-sets // In: The Workshop on Information Protection Moscow, 1993. P.22.

10. Авторское свидетельство 1396933. СССР. Устройство дл декодирования циклических кодов./ Евсеев Г.С., Крук Е.А. Самуйлова C.B., Федоренко C.B.