Комбинаторные методы построения и анализа нелинейных корректирующих кодов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

и-с*

вм к

2/Ь

м!

АКАДЕМИЯ НАУК СССР ШЧИСЖГЕШШ ■ ЦЕНТР

/

На правах рукописи УДК 621.391.15

Зиновьев Виктор Александрович КОМБИНАТОРНЫЕ МЕТОДУ ПОСТРОЕНИЯ И АНАЛИЗА

нминешх корржгирущих кодов

(специальность 01.01.09 - математическая кибернетика)

Азто.реферат

диссертации на соискание ученой степени доктора физико-математических наук

Москва - 1Э87

Работа выполнена в Институте проблем передачи информации АН СССР.

Официальные оппоненты: доктор физико-математических наук, профессор КАРАЦУБА A.A.

доктор физико-математических наук СИДЕЛЬНИКОВ В.М.

доктор технических наук, профессор УШАКОВ И.А.

Ведущая организация:

Московский физико-технический институт

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

в "_" часов на заседании специализированного Ученого совета Д 002.32.02 по присуждению ученой степени доктора физико-математических наук при Вычислительном центре АН СССР (II7967, Москва, ГСП-I, ул.Вавилова 40, конференц-зал).

С диссертацией можно ознакомиться в библиотеке Института.

Автореферат разослан "_"_198 г.

Ученый секретарь спецссвета Д 002.32.02 при ВЦ АН СССР кандидат физико-математических наук LAÜiH) С.М.ШВАРТИН

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

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

Пусть р1 - конечное множество из ^ элементов, называемое алфавитом, где один из элементов назван нулевым элементом (нулем) и обозначен О , а Р*п - множество всех последовательностей длины п> над Р . Для х^&р"^ , х , ... , # = Су,,.. Уп.) , определим расстояние

Хэмминга с1(х,%) как число позиций, в которых х. и у различаются, т.е.

Мх.р ~ I { ; : X; Фу. , j И,} / ,

где 1X1 обозначает мощность конечного множества X , и вес Хэмминга и>Ь(т.) , как число ненулевых элементов ос Произвольное подмножество С £■ Р*1^ назовем блоковым

-ичным кодом (или кодом над ) с параметрами

, п/, с1) N , где - основание кода, П/ - дли-

на кода, Ж -г. тСъ {с1(а,£ )}■ , где минимум берстся по всем векторам а,(, е С - минимальное расстояние

кода, N - \ 0\ - мощность кода или число кодовых слов. Для такого кода С примем обозначение: С Ы)

и С = (и,, (С, М) , если ^ = ¿. . Максимально воз-

можную мощность /V кода С у; А/) обозначим через Л/С^л,, или , если ^ = £ . Код (^; Л/( $ ; о1)) будем называть максимальным.

Кодированием кода С называется любое взаимно-однозначное отображение : {1,../V } С .

Обозначим через Вг(а) £ И1^ , о« г^н- . а, е Я* , шар радиуса с центром в О/ ,

Вг(ь) - { х ; осбг р1* сССа.х) £*с} .

Пусть £ = ] , где - целая часть числа

А, . Тогда для любых о-^е С , где С -(<1', и ауфй , шары В^Са) и не пересекаются* Этот факт

обычно интерпретируется как возможность кода С исправлять любые Ь или меньше ошибок.

Любое отображение ¥с : С такое, что

= ы для любых х е В^С**) и <е С .называется декодированием кода С , реализуицим его минимальное расстояние.

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

I, если х. в С , О, если х ^ С

Под конструктивным построением понимается задание- у^ со

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

Основными проблемами теории корректирующих кодов являются определение для всех возможных с(/ числовой функции /V С £; п, &) , построение максимальных кодов для этих £ > и построение таких кодов с минимально возможной сложностью кодирования и декодирования. Кроме того, с точки зрения технической реализации необходимо решать все эти задачи при некоторых ограничениях на коды, в частности, в классе линейных кодов (т.е. когда С - линейное пространство над полем Галуа ~ Р ). Иногда накладываются ограничения (связанные с минимизацией вероятности ошибочного декодирования) на весовой спектр ч , ■■■ > *2) кода, где ч . - число слов кода С веса с . Рассматриваются также равновесные коды, спектр которых состоит из одной ненулевой компоненты, т.е. , где £м в Д/ ф о - Это, конечно, далеко не все. Дело в том, что к настоящему времени в рамках теории коррек-тирущих кодов возникло новое направление - алгебраическая теория кодирования, рассматривающая математические вопросы теории кодов. Предметом исследования этого направления являются проблемы существования, построения и перечисления всех неизоморфных максимальных кодов с заданными параметрами г^ , Ж

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

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

к ним кодов, сложность кодирования и декодирования которых невелика.

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

объясняется прежде всего удобством описания таких кодов с помощью порождающих и проверочных матриц. В настоящей работе упор делается на те комбинаторные методы анализа и построения кодов, для которых свойство линейности кода не является существенным. Так, например, свойство совершенности кода позволяет нам достаточно подробно описать совершенный код независимо от того, линейный он или нет. В точности то же самое можно сказать о равномерно упакованных кодах, являющихся естественным обобщением совершенных кодов. Такому анализу нелинейных кодов посвящены в основном главы 2,3 диссертации. Главы 4,5 связаны главным образом с нелинейными комбинаторными конструкциями в теории кодирования. Наиболее существенными здесь для нас являются свойство вложимости одного кода в другой и более сильное свойство разбиения кода на одинаковые или разные подкода.

Прежде чем перейти к изложению содержания работы, введем несколько необходимых нам определений и обозначений. Обозначим через С {у} произвольный сдвиг кода С , в котором минимальный вес кодовых слов равен ^ , где j -о,1, п- . Условимся, что С£0у = С » т.е. С содержит нулевой вектор. Весовой спектр кода С обозначим через £ ф (¡1, >¿^1] /) ..причем . Многочлен

(здесь = ) называется весовой функцией кода

. В общем случав спектр £ кода С зависит от выбора нулевого вектора. Поэтому чаще используют (средний) спектр расстояний X = Хп-1)» где

Аь. - ¿1 {(*,&)' А (о¿} I г

Определение. Код С регулярен, если независимо от выбора нулевого вектора % \ , и полностью регулярен, если £ ) для любого j однозначно определяется ] и параметрами кода , уъ , & , N .

Если С - ( Н-, сЬ, N) - двоичный код с расстоянием оС , то обозначим через С* расширенный код

Сп + с1 +■ , полученный из С добавлением общей про-

верки на четность. Для произвольного множества Д , Д £ обозначим через А ; множество всех векторов из А веса с . В этой терминологии Р<,г" - множество всех векторов юр"1 веса I . Для двух векторов и.^&р**

где и 9- ^(а) , скажем, что покры-

вает IX , если условие влечет £ - ± .

Определение. Пусть /г,¿, <1 - натуральные числа, го £ и- , и . Совокупность Т векторов из

Я^ (где один и тот же вектор может встретиться, вообще говоря, несколько рал) называется тактической конфигурацией и обозначается Т - Т'(п,'и:, ^ ,<1) . если для любого а- & Р*^ найдутся точно ^ векторов йиз Т . каждый из

которых покрывает а

Определение. Конфигурация Т'С ^ ь^, О называется иначе системой Штейнера и обозначается ^ (^)

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

Вторая глава посвящена кодам, достигающим следующей верхней границы. Хэмминга: ■

. Если в коде С — ; п>, Ж, А/) с сС ~ Н +1 мощ- • ность № соответствует равенству в (!), то код С называется совершенным или плотно упакованным (так как любой вектор х из Р1^ принадлежит некоторому шару В. .

С

с центром, в кодовой точке (X/ & С ). Иначе говорящее множество р* ^ полностью разбивается на шары одинакового радиуса Ь , а центры шаров являются кодовыми словами. Совершенный код с параметрами ^, и-, сЬ - обозначим через , или Р(гг^) в двоичном случае. Мощность Д/ этого кода выражается через £, п-', £ :

N . 12)

с-о ■

Первые примеры таких кодов были описаны в 1347 г. Хэм-мингом: коды Р (ср 1) , где ^ . - степень простого числа, а п> ^С^-^/С^-х) , - ¿)3> . -. , и Голеем в 1949 г.: коды Р(23,3) и Р (3; 11,2). Тогда же возникло предположение о несуществовании других нетривиальных совер- , шенных кодов. Основными результатами второй главы являются три теоремы несуществования совершенных-кодов. В частности,.'

в п.2.2 получено полное решение этой проблемы для совершенных кодов над полями Галуа С, ?(<р~) , а в п.2.4 также для случая <£,= . , — произвольные натуральные

числа и £ И '. Кроме того, для произвольного в п.2.3 доказано существование эффективно вычисляемой константы С(<£) такой, что при Ь >£(<},) кодов Р(у/", гь^Ь) не существует. Для доказательства используются необходимые условия существования совершенных кодов. .Одно из них - целочис-ленность правой части (2), называемое условием Хэммйнга. Другое - следующая теорема Ллойда. Из существования кода следует, что многочлен (п<) ^ ■Ь

Ь (х;/г) -¿7 КЛх.;*-) , (3)

с-О

называемый многочленом Ллойда, имеет £ различных целых

корней среда чисел ..., ги . Здесь А'¿Сзс-уп) ~ многочлен Кравчука,

/С, *)( ?>(4)

где

х (х--1) ■ - - (х-а+1) / а < , если ос - натуральное число,

Са-)~~] 1- > если Сс-О ,

Со .в остальных случаях.

Анализ целых корней Ьь(ос,^ п.) , а также учет условия (2) дают верхнюю оценку на длину п> возможного совершенного кода. Комбинаторный анализ слов минимального веса такого кода приводит к ряду нижних оценок на длину IV

Сравнение этих оценок и дает несуществование совершенного кода.

Отметим, что проблема существования совершенных кодов полностью до сих пор не решена. Случаи "Ь у, — произ-

вольное натуральное число, остались открытыми. Для всех остальных случаев усилиями целого ряда авторов доказано несуществование неизвестных нетривиальных совершенных кодов. Чем вызван неослабевающий интерес к совершенным кодам в течение вот уже более 35 лет ? Во-первых, такие коды чрезвычайно интересны с технической точки зрения. Декодирование такого кода, реализующее его расстояние, в симметричном -ичном канале без памяти минимизирует вероятность ошибки декодирования среди всех кодов с теми же параметрами с^, кЛ Во-вторых, это изящная математическая проблема теории кодирования, связанная со многими другими отраслями математики, в частности, с комбинаторным анализом, теорией групп, теорией графа в и др. Совершенные коды имеют интересную комбинаторную структуру. Так по известной теореме Ассмуса и Мэттсона множество Ръг кода гу » I*> 2.Ы-1 , приводит к тактической конфигурации Т( «•, Ь+±, . В частном случае ^ = & множество Р^ кода р , г&ЪгЗЬ+З., (т.е. кода, полученного расширением Р(п,^) ) является

• а при и> - множество

является системой Штейнера ¿>(>1'^-tJ Ь +2) . Совершенные коды регулярны и полностью регулярны, а двоичные такие коды имеют симметричный относительно «./г весовой'

спектр £ ~(ЧР г - • Ч1*1п-С' для лйб0_

го I .., п/£ . Весовая санкция \А/. I Ъ) лю-

бого кода Р{с£ (<1,1 выписывается в явном виде:

К < -»г) -гЛ-

где "¿5 - корни многочлена Ллойда, а константы С3 определяются решением соответствующей- системы линейных уравнений с учетом следующих начальных условий: ^ ,(с) -о для , .и у (£) .

В связи с этим представляют интерес такие обобщения совершенных кодов, которые сохраняют все их интересные комбинаторные свойства. Такие обобщения, названные равномерно упакованными кодами, введены и исследованы в главе 3. Определим доя кода С - ; уъ, А/) радиус покрытия как

Г* н.

максимальное удаление точек множества р от кодовых слов. 1{усть (х.) - число кодовых слов, находящихся на расстоянии с от заданного вектора х . Код С равномерно унакован, если существуют такие рациональные числа К ' я ~ ' что для люб0Г0 -Х-- ,

ос е Р ^ , шеет место равенство Г

Л Г. .

С=о 4

Напомним геометрическую интерпретацию совершенного кода как полную укладку шаров одинакового радиуса t л множестве Р*Л • Равномерно упакованный код /V)

с параметрами > ■ • ., представляет собой

взвешенную укладку шаров радиуса с коэффициентами

К % • Означим такой код 21-; £ , .цу)

а И>(п1с11 £ ^ , У^) 3 двоичном случае. Мощность Л/

такого кода однозначно определяется параметрами:

с-О с с у *

Для случая совершенных кодов, когда - £ и у у = 1 выражение (6) сводится к (2). Целочис-

ленность правой части (6) является необходимым условием существования равномерно упакованного кода. Другое необходимое условие, рассмотренное в п.3.2, является естественным обобщением теоремы ^ойда для совершенных кодов: если существует код 1 то обобщенный многочлен Ллойда

f

и. с*;*) - Ну. кл*:*) _

имеет р различных целых корней среди чисел 1 . п, .

И» J % * J

.В п.3.2 показано также, что весовой спектр равномерно упакованного кода- с $ ^ & однозначно определяет-

ся параметрами кода и корнями обобщенного многочлена .Нлойда, а для его"весовой функции справедливо выражение типа (5). Поэтому равномерно упакованные коды с £ ^ оЬ регулярны, а с £ -[(оЬ(т.е. квазисовершенные такие коды) полностью регулярны.

Определение. Для вектора Л (ь10 , ... у <=1^) рациональных чисел Х- , где ¿о + . . . + ^ М фО » определим преобразование Мак-Вильямс ^ •= , ... , «б-^ ) }

•С- ¿-¿¿/Кг'У'*), (7)

Определение. Для кода С — (<р ; п, А/) ■ со спектром расстояний X - СХ о, ^ь,) и его преобразованием

Мак-Вильямс . А"*" ~ С А а , ..., Х"^ ) определим внешнее

расстояние X с кода С :

= К' : К/ > 1 =1>>--< / . С8)

В п.3.3 получен рдц необходимых и достаточных условий существования равномерно упакованных кодов. В частности, доказана теорема: код . С с радиусом покрытия fc и внешним расстоянием . равномерно упакован, если и толь-

ко если - . При расширении двоичного кода свой-

ство равномерной упакованности, вообще говоря, не сохраняется. Доказано утверждение: код ус,У^») при расширении остается равномерно упакованным тогда и только тогда, когда его многочлен Ллойда ¡_, ^ (х;т.)нараду с корнем j имеет корень ъ + ^ -j

Интересны равномерно упакованные коды с параметрами

О)

называемые строго равномерно упакованными. Коды такого типа, как показано в л.3.2 полностью регулярны. Все такие коды описаны усилиями целого ряда авторов.

Частным случаем строго равномерно упакованных кодов являются почти совершенные коды, предельно близкие по мощности к совершенным кодам. В двоичном случае (а только такие коды и существуют, как показали Геталс и Тилборг) этим кодам соответствует параметр т - > причем значение ж- = (пц)/а + 1) отвечает совершенным кодам. Напомнил, что совершенные кода связаны с границей Хэмминга

(I), т.е. код (у,; И/,il, Ы) совершенен, если и только если N удовлетворяет равенству в (I), где ~t = [(d-i)/zj . Обобщением оценки Аэмминга является следующая оценка Джонсона, которую мы приведем только в двоичном случае:

(ю)

1=0 '

где t - [(ot -l)/ij . Следующий результат, доказанный

в п.3.3 является естественным обобщением соответствующего утверждения для совершенных кодов: код (tv>d)N) почти совершенен, если и только если /V удовлетворяет равенству в (10), где t -[U-i)/i] .

В п.3.4 изучены комбинаторные свойства равномерно упакованных кодов. В частности, получено следующее обобщение теоремы Ассмуса и Мэттсона: если ob-f >о , то множество 'К/и„ w>,oi, кода $> К > прводат к кон-

Фигурации T(h<i ci ~fj U (■*})) . Согласно известному результату Дельсарта, если-в коде С « (tv, eL, А/) с внешним расстоянием at выполняется неравенство Ж < оЬ , то любое непустое множество С w является Т( h-^jd-X} J.(w)) .В расширенных кодах получается выигрыш на I: если в коде С - Сotj fl/J с внешним расстоянием X , все слова которого имеют четный вес, выполняется неравенство

3t < oi , то любое непустое множество С м является Tctv/uj, cL-x+i г «¿(u>j) . В атом же разделе доказано также, что двоичные равномерно упакованные кода с f < (oit t)/i имеют симметричный относительно л/г весовой спектр.

Параграф 3.5 посвящен существованию равномерно упакован-

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

К «з, V,<п)

b^i^-i,*?*-, ¿ = . (12)

Коды с параметрами (II) получаются редукцией одной позиции двоичных совершенных кодов Хэмминга, а коды с параметрами (12) - это нелинейные коды Препарата. Доказано, что двоичные примитивные в узком смысле кода БЧХ длины п с расстоя-

нием ct/~5~ являются строго' равномерно упакованными кодами.

В разделе 3.6 рассмотрены почти совершенные коды с параметрами {12). Мы будем различать два типа таких кодов: произвольные коды, имеющие параметры (L2) (обозначим их Р(к)) , и частный случай таких кодов - собственно коды, построеннные Препарата (обозначим их РсЦ ). Оказалось, что любой код

нелинеен. Обозначим через множество всех векто-

ров f"* , , находящихся на расстоянии 3 от слов

кода , т.е.

уем - (и

леРМ)

Пусть кроме того СИ) обозначает произвольный (линейный или нелинейный) совершенный код лэмминга донны 3,^-1 , обозначает линейный, такой код. Следующий результат, доказанный в п.3.6.2, является уникальным свойством двоичных почта совершенных кодов с d ~ S" :

рек) и Ya) ~ 76с i.) . (i3)

Было бы интересно ответить на следующие два вопроса. Существуют ли еще коды с подобным метрическим описанием ? В таких случаях код У&СЬ) линеен ? Ниже мы увидим, что код ^рСК) содержится в линейном коде Хэмминга СЬ] .

Почти совершенные коды приводят к системам Штейнера. В . п. 3.6.1 доказано, что в коде (слова веса 4 образуют систему Штейнера . В л. 3.6.3 код представлен в виде, разбиения на сдвиги кода , т.е.

pay и и .- сj = Ш)

где , i = i,..., i, - сдвиги кодов Препарата

перенумерованные некоторым образом, и 1 - . Интерес-

но сравнить (14) с (13). Разбиение (14) приводит к важному следствию. Перейдем в (14) к расширенным кодам длины По теореме Ассмуса и Мэттсона слова кода 'Ж образуют

систему Штейнера I^ Ч, 3) . Нами же доказано (п.3.6.1), . что слова веса 4 кода Р^^уСЬ) (а значит и кода С Д/)) образуют систему Штейнера У, 2) • Но это означает,

что данная система 4,3) полностью разбивается на

системы Ч, £) для любого К = } ■. • э т.е. эта

система ¿(Л^, Ч, 3) дважды разрешима. До этого результата были известны только дважды разрешимые системы и-,3.3) , п =. ЗСмсо/ 6) , для некоторых значений п . Интересно, существуют ли трижды разрешимые системы Штейнера 4,4) ? Необходимые.условия дяя существования такой системы удовлетворяются уже при fV'-iC . . ~ Помимо кодов Препарата

РСЬ)

известна еще их обобще-

ния, предложенные Думером И.И., обозначаемые нами с) ,

С ~ X, ..., Я"£ • Для кодов Думера также имеет место разложение (14). Существуют ли еще другие коды РсЬ) , не изоморфные кодам Думера I) и Препарата ?

Что дало понятие равномерно упакованных кодов ? Таких кодов значительно больше, чем совершенных. Только для случая' - 2, известно 5 бесконечных семейств равномерно упакованных кодов с > 5" . Среди них такие классические коды как коды БЧХ с сЬ-5~ и с1> - 7- и два замечательных семейства нелинейных кодов - коды Препарата а коды Геталса. Поэтому понятие равномерной упакованности позволяет в общем виде исследовать достаточно широкий класс корректирующих кодов. В частности, это позволило

- найти возможные параметры новых кодов, решая соответствующие диофантовы уравнения Ь^, Сх-' = О , и построить некоторые из них, в том числе линейные коды

Г^; Ь, £ к ] . ь-Оь^^+Я/З , , имеющие

максимально возможное число информационных символов к ;

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

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

- построить ряд нових бесконечных семейств тактических конфигураций с б ~ Ъ , в частности, построить уникальное семейство двавды разрешимых систем Штейнера £3) , ^ я V, £} ■ -. .

В отличие от глав 2,3, посвященных в основном исследованию кодов, достигающих верхних границ Хэмминга и Джонсона, главы 4,5 посвящены прямым методам построения новых кодов. Один из таких методов - это обобщенное каскадное кодирование, рассмотренное в главе 4. Линейные обобщенные каскадные коды (кратко ОК-коды) были введены Блохом ЭЛ. и Зябловым В.В. Они изучили их корректирующие свойства при исправлении независимых ошибок как для конечных длин, так и в асимптотическом случае, когда п> —о*=> , и разработали каскадный алгоритм декодирования, реализующий их расстояние и имеющий степенную сложность от п-

В главе 4 описана общая схема построения нелинейных ОК-кодов в несколько более простом виде, чем конструкция Блоха-Зяблова. ОК-код порядка т ■ строится на основе двух семейств исходных кодов: гл произвольных кодов Ас - .' па > , ) , называемых внешними, и м кодов (у пе . ^¿,1 * • • называешх внутренними,

С ...} ^ . Мощности внутренних кодов удовлет-

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

жен полностью разбиваться на £ подмножеств в (Ч

Каждый из кодов 8 (¿) должен полностью разбиваться на подмножеств ¿З'3;е <•',/; :

в= и ,в(3)<;.])*сг> »V-

Всего должно быть т -х шагов подобных разбиений. Результирующий ОК-код С гр,с6,А/) имеет параметры

Л- ^^, ^ ' { £а,С <¿6,1 }, м = Л/о,, " • ^.

Ути

Накладывая те или иные ограничения на исходные кода, удается получать ОК-коды с нужными свойствами. Разработан (л.4.2.2) универсальный каскадный алгоритм декодирования таких кодов, более простой, чем алгоритм Блоха и Зяблова. Напомним, что под каскадным алгоритмом декодирования мы понимаем такое декодирование ОК-кода, когда решение о принятом слове длины П' принимается только на основе декодирования внут-

ренних кодов длины П/£ и внешних кодов длины П-а, Подчеркнем, что именно в этом заключается принципиальное преимущество каскадных кодов: декодируя исходные короткие (внешние и внутренние) коды, мы декодируем длинные результирующие ОК-коды. Это дает прежде всего выигрыш в сложности декодирования по сравнению с другими кодами. Это было исследовано в работах Блоха Э.Л., Зяблова В.Ь. к Думера К.И.

Разработанный касхадш;; алгоритм декодирования не только реализует расстояние ОК-кода, но и позволяет также хорошо исправлять более сложные конфигурации ошибок, в частности, одиночные или многократные пакеты ошибок, а также одновременно многократные пакета ошибок и независимые ошибки. Эти вопросы рассмотрены в н.4.2.4, Кроме того в п.4,2.3 предложен

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

Построенные ОК-коды для небольших значений длин п,й5Ц и расстояний с0?30 часто имеют наибольшую мощность А/ среди других известных кодов с теми же П/ и сЬ , т.е. предложенный метод построения кодов существенно улучшает нижние оценки на М(к, Ж) для конечных значений Н/ . Это можно увидеть из таблицы наилучших известных кодов в книге Мак-Вильямс и Слоэна. В указанном диапазоне ги и Ы/ построено около 100 ОК-кодов, имеющих наибольшую мощность среди других известных кодов. Кроме того в п.4.3 показано, что целый рдц известных максимальных кодов, а именно, двоичные расширенные совершенные кода Хэмминга и Голея, коды Адамара и год Нордстрома-Робинсона представимы в виде ОК-кодов. Поэтому для всех этих кодов можно использовать разработанной каскадный алгоритм декодирования. Это часто дает выигрыш либо в сложности декодирования, либо в корректирующей способности по сравнению с другими известными методами декодирования этих кодов.

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

них кодов. Обозначим через {гь^.го^) двоичный код С и,, оС^ /V) , все слова которого имеют вес уУ . Все расстояния между словами такого кода необходимо четны и, в частности, Ж ~ 2.оР . Обозначим через оС, г&) мак-

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

N1», V») ^ УС, , ои - *<Л (15)

Заметим, что равенство в (15) соответствует случаю, когда код ( Л-, сС, Щ А/) является системой Штейн ера ¿¡(¡р/М, ы+1) . В л.4.4 построен широкий

кла.сс каскадных равновесных кодов (п^сС^^Ы) с параметрами Ги = ^ Ы , А/ ■= , где - степень •простого числа такая, что ^ , , сР -любое натуральное число, причем с/1 £ ъ? . Мощность Д/ этих кодов отличается от оценки (15) лишь на мультипликативную константу:

а сложность построения не превышает С л 3 , где с не зависит от IV . При н*-**»* и соответствующих ограничениях на порядок роста го и сР от /г- получаются асимптотически оптимальные относительно оценки (15) равновесные коды. Тем самым.получен конструктивный положительный ответ для растущих и сР на известную гипотезу Эрдеша и Аанани о том, что оценка (15) асимптотически достижима при оо и фиксированных г^ и

с/* . Аналогичный не-

конструктивный результат (т.е. теорема, существования) ранее был получен Кузюриным H.H.

Итак, нелинейное обобщенное каскадное кодирование

- существенно расширило класс OK-кодов, для которых справедлив универсальный каскадный алгоритм декодирования;

- привело дли конечных длин к большому числу новых кодов с наилучшими известными параметрами; .

- дало эффективный метод кодирования для каналов со сложным характером ошибок;

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

Глава 5 диссертации посвящена двум комбинаторным мето-,дам построения кодов, которые часто позволяют улучшать нижние оценки на N{п,сС) для конечных длин. Очень легко придумать различные способы комбинирования кодов. Этому посвящена обширная литература, например, глава 18 известной книги Мак-Вильямс и Слоэна. В частности, рассмотренное в главе 4 обоощенное каскадное кодирование является, конечно, одним из таких способов. К ним же относятся различные суммы и произведения кодов. Рассмотренные в главе 5 две общие конструкции отличает то, что с их помощью было построено.чрезвычайно большое число новых кодов с наилучшими известными параметрами. Эти конструкции противоположны друг другу в следующем смысле: о,дна конструкция - это удлинение кодов, а другая- укорочение.кодов.

Первый, метод, рассмотренный в п.5.1, объединяет различные способы удлинения вложенных систем кодов. Идею удлинения проиллюстрируем на простейшей конструкции такого рода - добавление одного суффикса. Пусть задан код Ж*, Mi) , ко торый разбивается на подкоды С. - (п>, d3 ,А/Х) , .$ ■, /V, =• //Vj , где cL^ > df . Удлинение состоит в достройке кода Сf1} до некоторого нового кода с расстоянием с1/г Достройка заключается в приписывании некоторых символов к каждому слову кода С(i> . Так как каждый из кодов имеет расстояние , то для всех слов этого подкода добавка может быть одной и той же. Отсюда мы сразу же заключаем, что для достройки кода С (i) ■ необходим специальный код \\Г - Спи,, (¿w, /Ч.>) » называемый суффиксным кодом, где '

oCw >dl-ot1 , N^, » / , 'а длина (ъ^ минимально возможна. Итак, идея этой конструкции состойт в кодировании всех подкодов Сс,Л> , кода C(f> с помощью суффиксного ко-

ч r> с

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

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

ния, такие, как добавление суффиксов, метода комбинирования кодов, дециклическое удлинение кодов, удлинение многомерных вложенных систем кодов. Используя вложенную систему кодов, образованную кодами Хэмминга, Препарата, обобщенными кодами Преларата-Думера и кодами Геталса, в п.5.1.2 построено несколько семейств новых кодов с ф = ? , имеющих наилучшие известные параметры и, в частности, новое семейство квазисовершенных кодов с ск ~ . В п.5.1.3 показано, что можно строить хорошие одномерные и двумерные системы вложенных 0К-кодов. Всего такими методами удлинения построено более 400 новых кодов, улучшающих нижнюю оценку величины А/для значений п- ¿г б'И и сО ^ 30 из таблицы наилучших известных кодов в книге Мак-Вильямс и Слоэна.

Другим подходом к построению новых кодов из заданных являются методы укорочения кодов, рассмотренные в пп.5.2 и 5.3, и которые фактически представляют собой обменные соотношения между мощностями кодов и их лодкодов. Задача ставится следующим образом: какой код мы можем построить на длине , л, < л- , если нам задан код О — С к, Ы) ? Рассмотрены три случая, а именно, когда о коде С нет никакой дополнительной информации, когда известно дуальное расстояние кода с!/2" и когда известно максимальное значение модуля характера уш С С.) кода С относительно векторов веса гоЬ (и) ^ с1м . Здесь -^о, j ъ-1 ]•

г>ес

где - скалярное произведение векторов ¿¿-, ¿^ .

В л.5.2.1 рассмотрены две общие конструкции укорочения, кото-

рые включают все известные конструкции такого типа. Приведем одну из них. Пусть существует код С -Сп, c¿¿ А/) с дуальным расстоянием d/J~ и характером у. ,

¡J.( - fn otX. (fu. СО/ пл>Ь (и,) — h cL ,

Пусть $, % - произвольные целые числа, причем

Ой^ 4 ьч'уь {б> к 12. } ; £ < т . Тогда существует код

Сг ^(н-Ь-б, (¿-И^, И/,) мощности

>- (2 (№"+*'■>!)%('))/*

где

, если

о

С-Ос . если уС-1)*<0 .

В п.5.2.2 рассмотрено укорочение ОК-кодов, а в л.5.2.3 рассмотрено укорочение двоичных кодов БЧХ. Для этого там же получена новая верхняя граница дуального расстояния этих кодов. Обозначим через В (<&,)*£) двоичный примитивный в узком смысле код БЧл длины л- = 2 "*"- £ с конструктивным расстоянием сО , где оС - нечетное число. В частности,, получен следующий результат. Пусть гп, € - произвольные натуральные числа, £ ? < . Тогда, если Ж Ц £ ) то КОд ¿¡.{об,»*) имеет дуальное расстояние

1 ± , _ м-* с1 ^ 2, . (16)

Вели же м кратно , то оценка (16) имеет место для .

любого оО Ъ 2, 1/2 } + % • Следствием

этой границы явилась новая нижняя оценка для полных рациональных тригонометрических сумм, рассмотренная в л.5.2.4. Всего методами укорочения построено более 200 новых кодов, улучшающих нижнюю оценку Л/С*, в таблице Мак-Вильямс и Слоэна.

Б п.5.3 развивая идеи укорочения кодов, получены новые верхние и нижние оценки на мощность равновесных кодов конечной длины. Следующий результат является естественный обобщением/оценки Джонсона (15). Пусть & - произвольные целые числа, о¿д й & й )г-г& , ипусть 3 {о,£,... > , если у & , * Э- , если £ ^ £/2 . Тогда

(Х(Г)(пе:Г))/(П

¿еЭ

Используя неравенство (17), удалось построить ряд новых равновесных кодов, улучшащих нижнюю оценкутаблице наилучших известных равновесных кодов. Грэхема и Слоэна.

Сформулируем основные результаты диссертации.

1) Решена проблема существования совершенных кодов над конечными полями Галуа, а также для случая алфавита размера

• - произвольные натуральные числа, и

расстояния сЬ 5"

2) .Введено и подробно исследовано новое понятие в теории кодирования - равномерно упакованные кода. Эти коды естественным образом обобщают совершенные коды и включают ряд дру-

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

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

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

с заданным.максимумом модуля характера кода, укорочение равновесных кодов. С помощью этих общих конструкций построено большое, число новых кодов, имеющих наилучшие известные параметры. Для двоичных примитивных.в узком смысле кодов БЧХ.по-

лучена новая верхняя оценка дуального расстояния.

Основные результаты работы докладывались на семинарах по теории информации и по алгебраической теории кодирования ИППИ АН СССР, на семинарах по теории кодирования, по комбинаторному анализу и'по дискретной математике.Московского Государственного университета им.М.В.Ломоносова, на Международных симпозиумах по теории информации в 1971 г, в Цахкад-зоре, в 1973 г. в Таллине, в 1975 г. в Кестхен (ВНР), в 1976 году в Лидице (ЧССР) и в Ленинграде, в 1981 г. в,Будапеште (ВНР), в 1982 г. в Праге (ЧССР) и в Обервольфахе (ФРГ), в 1983 г. в Сочи, в 1984 г. в Ташкенте, в 1985 г. в Гране (Швеция), на Всесоюзных конференциях по теории передачи и кодирования информации в 1972 г. в Горьком, в 1978 г. в Вильнюсе.и в 1981 г. в Куйбышеве, на Всесоюзных симпозиумах по проблеме избыточности в инфордационных системах в Ленинграде в 1974 г., 1977, 1983 гг., на Всесоюзных семинарах по комбинаторному анализу в Москве в 1979, 1981, 1983 гг. и опубликованы в следующих работах.

1. Бассалыго Л.А., Зайцев Г.В., Зиновьев В.А. О равномерно упакованных кодах. - Проблемы передачи информации, 1974, т.10, № I, с.9-14.

2. Бассалыго Л.А., Зиновьев В.А. Замечание о равномерно упакованных кодах. - Проблемы передачи информации, 1977,

т.13, Л 3, с.22-25.

3. Бассалыго Л.А., Зиновьев В.А., Леонтьев В.К. Совершенные коды над произвольным алфавитом. - В кн.: Третий международный симпозиум по теории информации, тезисы докладов, Москва-Таллин, 1973, часть 2, с.23-28.

4. Бассалыго Л.А., Зиновьев В.А., Леонтьев В.К., Фельдман Н.И. Несуществование совершенных кодов для некоторых составных алфавитов. - Проблемы передачи информации, 1975,

т.II, Л 3, с.3-13.

5. .Пумер И.И., Зиновьев ,В.А. Некоторые новые максимальные коды над полем Галуа СРСЧ) . - Проблемы передачи информации, 1978, т.14, № 3, с.24-34.

6. Зиновьев В'.А. Обобщенные каскадные коды. - Проблемы передачи информации, 1976, т.12, № I, с.5-15.

7. Зиновьев В.А. Алгебраическая теория блочных кодов, исправляющих независимые ошибки. - В кн.: Итоги науки и техники. Серия "Теория вероятностей. Математическая статистика. Теоретическая кибернетика". М.: ВИНИТИ, 1976, т.13, с.189-234.

8. Зиновьев В.А. О корректирующих способностях обобщенных-каскадных- кодов. - В кн.: Пятая всесоюзная школа-семинар по вычислительным сетям, тезисы докладов, часть 4, Москва-Владивосток, 1980, с.106-110.

9. Зиновьев В.А. Обобщенные каскадные коды для каналов с пакетами ошибок и независимыми ошибками. - Проблемы передачи информации, 1981, г.17, № 4, с.53-62.

10. Зиновьев В.А. Коды постоянного веса и максимальные упаковки. - В кн.: УШ Всесоюзная конференция по теории кодирования -и передачи информации, тезисы докладов, ч.2, Москва-Куйбышев, 1981, с.75-80.

П. Зиновьев В.А. Об обобщении оценки Джонсона для равновесных кодов'. -В-кн.: Международный семинар "Сверточные кода; связь с многими пользователями", тезисы докладов,

Сочи, 1983, с.203-208. 12.Зиновьев В.А. Об обобщении оценки Джонсона для равновесных кодов. - Проблемы передачи информации, 1984, т.20, № 3, с.105-108.

13. Зиновьев В.А., Леонтьев В.К. Несуществование соверщенных кодов над полями Галуа. - Проблемы управления и теории информации, 1973, т.2, №2, с.123-132.

14. Зиновьев В.А., Лицын С.Н. Общая конструкция укорочения кодов. - В кн.: Шестой международный симпозиум по теории информации, тезисы докладов, ч.П, Москва-Ташкент, 1984, с.86-88.

15. Семаков Н.В., Зиновьев В.А., Зайцев Г.В. Равномерно упакованные коды. - Проблемы передачи информации, 1971,

т.7, № I, с.38-50.

16. Zaitsev G.V., Zinoviev V.A., Semakov U.V. Interrelation of Preperata and Hamming codes and Kxtfir.aion of Hamming codes to new double-exror-correcting codes. - Ins 2 nd Intern. Symp. Inform. Theory, Thsahkadsor, Armenia, USSR, 1971, Akademiai Kiado, Budapest, 1973, p.257-263.

17. ■Zinoviev V.A. On generalized concatenated codcis. - In:

Coll. Math. Soc. Janos Bolyai. 16. Topics in Inform. Theory, Keszthely, Hungary, 1975, p.587-592.

18. Zinoviev V.A. Bqual-weight codes and maximal packings.-Ins Mathematisches Forschungsinstitut Oberwolfach. Tagungsbericht, 14/1Э82, Informationstheorie, 1982,p.23.

19. Zinoviev V.A. Cascade equal-weight codcs and maximal packings. - Probl. of Control and Inform. Theory, 1983, v.12, N 1, p. 3-10. . . 4

20. Zinoviev V.A., Litsin S.N. On a general method of increa-8ing the length of codes. - Probl. of Control and Inform. Theory, 1934, v.13, N 2, p. 79-87. •

21. Zinoviev V.A., Litsin S.N. On an upper bound for the dual distance of binary BCH codes. - In : Second. Joint Swedish - USSR Intern. i/orkshop on Inform. Theory, April 14-19, at Granna, Swedish, 1985, p.61-64.

В работах [l-5, 13-16, 20, 2lJ имеет место нераздельное соавторство.