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



МИНИСТЕРСТВО ВЫСШЕГО И СРЕДНЕГО СПЕЦИАЛЬНОГО ОБРАЗОВАНИЯ Р Е С П У Б Л И К И УЗБЕ К ИСТА Н

ТАШКЕНТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени в. И. ЛЕНИНА

АБДУРАХМАНОВ Жамолидин Комолдииовнч

О ГЕОМЕТРИЧЕСКОЙ СТРУКТУРЕ КОДОВ, ИСПРАВЛЯЮЩИХ ОШИБКИ

01.01.09 — математическая кибернетика

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

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

АВТОРЕФЕРАТ

Ташкент —

1991

Работа выполнена и Ташкентском государственном университете имени В. И. Ленина.

Научный руководитель —

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

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

кандидат физико-математических наук, доцент Пулатов А. К.

доктор технических наук, профессор Трофимов В. К.

кандидат физико-математических наук, доцент Шестеро-ва Н. А/

Институт математики СО АН СССР.

Защита диссертации состоится « /£ » ^{.¡^¿¡Л 199^.г. в е>ь' часов на заседании специализированного совета К 067.02.13 в Ташкентском государственном университете им. В. И. Ленина по адресу: 700095, Ташкент, ВУЗгородок, ТашГ'У, факультет прикладной математики и механики, ауд. А-205.

С диссертацией можно ознакомиться в научной библиотеке ТашГУ им. В. И. Ленина (ВУЗгородок).

Автореферат разослан « » 199 / г.

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

кандидат физ.-мат. наук, доцент^/^г^^^^ИРЗАЕВ И.

— - э -

Г, - { ОЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

М-мерного {^-ичного куба с^,.или, что то же самое, (^-ичннх корректирующих кодов длины И, глубже раскрывает строение кодов а помогает более адекватному созерцанию их природы. Этим и объясняется актуальность исследований диссертационной работы.

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

ЕЛ

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

О б я а я методика выполнения и с с л а д о в а н и й."Методика исследования состоит в)применении подходов, базнруввдхся на методах дискретной математики, теории графов, алгебры.

Научная новизна диссертации состоит в следу-вчен: *

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

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

- получены комбинаторные соотновения, характеразуюсше зависимость

ЕП

от размерностей подмножеств кода;

- выписана некоторая реккурентная формула для весового спектра кода, инвариантного относительно расстояния;'

- изучено распределение кодовых слов п.у. (М^-кода по сферам куба Е^, затронут и частично освещен вопрос о распределении вер-иин двоичного п.у. (И^-кода по граням единичного И -мерного куба;

- приведены явные формулы для вычисления количества некоторых кодовых треугольников двоичного п.у. (И-кода;

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

- описаны конструкции совершенных кодов на графах выпуклых многогранников. :

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

Апробация работы. Результаты диссертации док-ладивались и обсуждались на ПИ Всесоюзной конференции по теоретической кибернетики (Горький, 1986), на IX Всесоюзной-конференции по теоретической кибернетики (Волгоград, 1990), не научных семинарах "Дискретная математика" ИМ СО АН СССР (1986," 1990 гг.), на семинарах "Дискретная математика и ее приложения1' (ТавГУ, 1986-1991).

Публикации. По теме диссертации четыре работч.

Структура и объем работы. Диссерта-нная работа состоит из введения, трех глав и списка литературы 38 наименований. Общий объем работы - 66 машинописных страниц.

. СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

В первой главе содержатся результаты, связанные с размер-юты; подмножества и распределением кодовых слов по граням куба. 1П0КННМ, что куб представляет собой П.-ею декартову степень рабства , В случав С|,-X куб Е^ принято на-

звать П -мерным единичным кубом и обозначать через Е*1. Понятие азмерности подмножества куба вводится как мера плотности реа-азации его собственной метрической структуры, а именно: размер-остьв подиноиества А С Е^, называется размерность

шнии&ль'коа (по числу вершин) грани куба Е.^ , содержащей подмно-1ество А • Хотя такоэ определение размерности не базируется на реа-шзяцив метрической структуры, связь так определ^шой размерности в последней становится очевидной из следующих соображений. Пусть подмноиества А и В куба Ё^ являются изометричными (в метрике Хэмминга), т.е. реализуют одну и ту же метрическую структуру, причем размерность Д меньше размерности В.. Тогда естественно считать, что метрическая структура этих подмножеств реализуется более плотно (или, ещё точнее, компактно) подмножеством А , чем подинояеством В . Если метрическая структура подмножества А не реализуется подмножеством меньшей размерности чем размерность А ,

- б -

то А называется плотным подмножеством. Примечательно, что двоичные линейные коды, оказывается, является плотными подмнояест-

ЕП.

. Далее, если мысленно предположить, что локальная изометрия, рассмотренная А.А.Евдокимовы занимает место "левее" от обычной (т.е. полной) изометрии, то в случае куба наличие понятия размерности подмножества лозвол ет обнаружить "правее" от нее сильную изометрив, которая опреде ляется следующим образом. Подмножества А и В куба Е^, назы веются сильно изометричными, если существует отображение такое, что для1 любого А<^А имеет место R(А') = RА• Очевидно, что если подмножества А и В эквивалентны, то они си но изометричны. (Подмножества А и В по определению эквивале ны, если существует автоморфизм' куба Е^, сохраняющий расстояни Хэмминга и отображающий А на В .) Вёрно ли.обратное? На этот интересный вопрос не удается ответить, однако, можно указать еле дующий веский довод в пользу утвердительного ответа. Пусть

V(A> обозначает число всех $ -мерных граней куба Ё^

каждая из которых содержит ровно по € вершин подмножества А • Если А и В эквивалентны, то очевидно V(A,ft,¿) = V(В,^, б)

при любых к и е , о^Шп, о 4 е4 min{IAI,

Го же самое остается верным тогда, когда.А и ß сильно изоме ричны. Этот факт вытекает из теоремы 1.3, которая является цент ральной теоремой первой главы. Эта.георема гласит, что верно ра венство р / í \

e=s Be A, IBM . v

где Ц и S - целые, 0 4 П, i 6

справа суммирование производится по всем S-элементным подмноже

к ВсА • терреиы 1.3 вытекает также, что для инвариант-го относительно расстояния кода AdЕ^ справедлива реккурент-я формула •

Ai~ IAI '

i5- е-5.

де . IAI - мощность кода А . А^ - число

одовых слов, находящихся на расстоянии i от некоторой фиксировала кодовой вериины o¿£ А (так ках А инвариантен откоситель-ю расстояния, то A¿ не зависит от выбора ote Д ). Разумеется, )та реккурентная формула не.решает проблему вычисления весовых с-1ектров кодов, однако она наглядно указывает на зависимость между распределениями кодовых слов по граням и сферам куба

Вторая глава диссертации посвящена изучении некоторых общих свойств п.у. (П., 3Í)-кодов. В первом параграфе отой главы обобщен резулмат Г.С.Шапиро и Д.Л.Злотника для произвольного '-ty-ичного л.у. (П,3) -кода в следуюяем смысле: в произвольном С^-ичном со-верзеннон (^1,3)-коде число кодовых слов, находящихся на рассто-

яяии i от данной веряины куба Ьл зависит (помимо ÍL и (I ) то' с П

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

представляет такхе и самостоятельный интерес. Первая лемма позво-

ЕП а

Ем '

^ названы касающимися, если расстояние Хэмминга между их

централи равно сумив радиусов или разности мевду большим и меньшим

Еа

л - метрическое пространство с расстоянием СП.

Хоииинга, то лобоа подмножество куба Ь.^ также является метрическим пространством с тем ие расстоянием. Вторая лемма позволяет по-

дочитать мощности шара и сферы заданного радиуса в метрическом. I остранстве, которое является сферой в . Обобщение же резул! тага Г.С.Шапиро и Д.Л.Злотника показывает, что невозможно обнарз жить различие двух неэквивалентных п.у. (Ц,^) -кодов, наблюдая 1 лько за распределением кодовых вершин по сферам (или шарам) кубг Во втором параграфе второй главы показано, что можно пров(

ти определенное различие между двоичными п.у. (Н, 3) -кодами, нас

Ей

. Из ДО!

занной А.К.Пулатовым теоремы вытекает, что при (П+1)/2£ кё; 1Ъ кодовые слова произвольного двоичного п.у. (Н,3) -кода равноме{ (по числу) распределены по Д -мерным граням единичного Ц -мернс куба Е* (при ^ (1Я+-|)/2," это свойство уже не выполняется) . Отсюда следует, что при (П+1)/Л ¡^ к ^ Л число У (С, к, £) не зависит от выбора двоичного п.у. (П,3)-кода С . Указанное е ше различие обнаруживается именно в том, что при 5¿кк число уже зависит от С . (Если же 0 к 5

то число \/(С,А,в) опять не зависит от выбора двоичного п.у (11,3) -кода С .) Этот факт доказан прямым указанием таких п. (Л,3)-кодов С' и С" » что при 5 имеет ме

Л/(С'Хе)Ф У(СЛ,е), .

для некоторого 6 . Отсюда как следствие получается,.что коды С

и С не являются сильно изометричными. Отметим, 'что С - ото

Си

- код Васильева. . • ' '

Последний параграф второй главы, посвящен подсчету кодовых еугольников с заданными.сторонами в п.у. {й73)-коде. Любое трех ементное подмножество п.у. (|1;3)-кода С назовем кодовым треу льником. Стороной кодового треугольника назовем расстояние Хомми между его двумя вершинами. Обозначим через с!^, с)^, С^} чис

кодовых треугольников со сторонами С^ , с!^ , для заданного п

(ft>3) -код» С • Зависит ли число t^C,^, от выбора

С ? Еслп для п.у. (М,3)-кодов Cf и Сд и для некоторых^,

н«вет место t(Cj, dj) ф t(Ca c/j , то очевидно, что Cj и не будут изпмвтричными. Следовательно, подсчет кодовых треугольников может рассматриваться как попытка опровергнуть следующую гипотезу: все п.у. (tl,3)-коды изометрич-на друг другу. Оказывается, что числа t(C,3,

t(C,W), t(c, 3,5,5), t(C,3,n-W), t(CAh-5,h-i\

t(C,3,ft-5,rt-5-), t(CAft-5,M), t ft-5), t(e, 5; n- 6,h-3), t(Ct6,n-s,n- 3),

t(CXn-l,fi), .....(>w)A,

• не зависят от' выбора двоичного п.у. (/1,3)-кода С • Приведены явные формулы для вычисления этих чисел.

В третьей глава диссертации вводятся некоторые понятия, но*

сладе обобщающий характер, и изучаются их свойства. Рассматривая

Eft

^ , связанные с линейными и совершенными кодами, можно обнаружить интересную симметрию этих разбиений: вершшы любого множества, участвующего в разбиении, весьма регул-,яр!Н} разбросаны по шарам с центрами из другого множества, участвующего в том же разбиении. Разбиения любого конечного множества, -обладавшие этим свойством, в диссертации названы совершенными. Да. длм более.точное определение. Пусть М - произвольное непустое конечное множество, «¿^ - множество всех его подмножеств. Отоб--. ,ражеяие называется обобщенным шаром множества

. Н , если условие <sC€.^(j}) выполняется тогда и только тогда,.ко-' гда выполняется условие ß G . Разбиение множества М на

попарно непересекающиеся .классы М^Мд,»*'.'» Нд называ-

ется сопериепным относительно обобщенного шара vp , если для любых I ¡1 , 1'i i £ к, 1 ^ j к И ДЛЯ любых и ß из

м^ имеет место (ИАМ^Н1^/)/) - Ь § 3.1 выявлены

некоторые свсистиа обобщенных шаров и соиерденных разбиений конечного нноаесгва. а в § 3.2 приводятся примеры совершенных разбиений, связанных с лннеиныни и совершенными кодами. Совершенное разбиение. связанное с линейным кодом I* С. Еп , может быть описанс

гЛ

следующим образом. Обобщенный шар и> куба Со назовем линейным,

П*

если для любых оС и £ из С^ имеет место

где » левой части стоит "сдвиг" шара на вектор по модулю

. В & 3.2 доказано, что разоиение куба Е^ на смежные классы по подгруппе 1« является совершенным разбиением относительно любого линейного обосвбнного вара. Показано также, что совершенное разбиение может Сыть порождено ссвераешшм кодом.

Очевидно, что понятие совершенного кода может быть распространено на люые Наличие совершенного кода на .множестве версии некоторого графа свидетельствует о разбиении его на специальные области с центрами в кодовых вериинах. В третьем параграфе последней главы диссертации рассмотрен^ конструкции соверзанных кодов графах выпуклых кногограинмкоь. Построена последовательном многогранников с расгуан« числом верами, имеюадх совершенные коды. Проведено некоторое наблюдение за распределением кодовых варзац по граням многогранника. Из-за неоднородносты(в обаеи случае) графов многогранников, обнаруживается суявствэшюв различие в реаещы вопросов существования совервенных ходов на многогранниках и па Л.-мерном {^-ичном кубе Е^ . Оказывается; что при двйои натуральном ¿1 имеется бесконечное число цногограшшков, имевшая соверзешше коды с ходовым расстоянием с! . Кроме того, покапано. что на одном и том же многограннике могут существовать совершенные коды с одиим и тем же кодовым расстоянием, но с Существенно различными мощностями. Подобные факты не инект кесто при рассмотрении совершенных ■

•хации,

Работы, опубликованные по теме диссертации. I Абдурахманов «.К. Обоб.енные „ары. сов.ртен-в системы

с кодами // Комбинаторно-алгебраические и

подмножеств и их связь с кодами //

»— -г- ТоГ"»г;::, г-

тр. /. Под ред: а.А.Маркова; Горьк. гос. УН 1

_ Т Абдурахманоз 1.К. Распределение вериин подмножества И -мерного'куба по его граням и вычисление весовых спектров кодов / /1 университет.;- 1*1. - 20 с. - Бнблиогр. 7 назв. -

"Рус . Деп. в УзНИИНТИ 22.02.91, * 1399 - >з91.

У „и Пулатов А.К. Конструкция совершенных

3. Абдурахманов Ж.К-. "У-Л!»ив КОДОв на выпуклы, многогранниках // -оды —^^. решении, окстрекальннх зада,. - Новосибирск. 1990...

' АбдурахнанОв ЬК.. Кондратьева'0.Б., Пулатов А.К Совер-

' л н 4 на многогранниках // Тез. Докл.-.УШ Всессз-.

, шенные коды и.Д.н-Ф- - Р дабвр1втя. часть I.

■ ной конференции по проблема* теоретич

Горький, июль 1988 г.' - Горький, 1988. - С. 3.