Геометрический подход к негрупповым плотно упакованным кодам тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

АКАДЕМИЯ НАУК СССР СИБИРСКОЕ ОТЛЗЛ^ШЕ ИНСТИТУТ МАТЕМАТИКИ

На прав?-' рукописи УДК 519.725

СОЛОВийА Фаина Иваноииа

ПОМКТРИЧЕС'^К ПОДОД К НЕГ7УПП0ВЫМ ПЛОТНО УПАКОЗАШШ КОДАМ (СПОСОБЫ ПОСТРОЕНИЯ, СЮ .''С ТВ А ПРОЕКЦИЮ

'0I.0I.G9 - математическая кибернетика

Азторэферат

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

/О

' /

Новосибирск ЬЭЭ

Работа выполнена в Институте математики СО АН СССР

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

Ю.Л.Васильев

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

В.А.Зиновьев,

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

Ведущая организация - ¿орьковский государственный ордена

Трудового красного Знамени университет им.Н.И.ЛобРчевского

Защита состоится "_"__ 1990 г. в_ ча-

"ов на- заседании Специализированного совета К 002.23.01 в Институте математики СО АН СССР по адресу: 630090, Новосибирск,90, Университетский пр., Члстнтут математики.

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

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

Ученый секретарь Специализированного совета, кандидат фазико-матоматичес1 IX наук

'/¿\ ^/ • Васильев

Объектом исследования в данной работе являются плотно упакованные С и.у.), или совершенные., коды с кодовым расстоянием 3 в а-мерном е-шичном кубе •• 3 диссертации пред-ага-ктся несколько способов построения я.,у..-кодов и иса/.е-дутлен свойства проекции п.у. (а , 50 -кодов по лк/5ому из п. направлений, а именно,проводится систематическое изучение факторизации кодообразующлх д.н.ф., позволяющих расширять запа^ имеющихся колон.

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

I)

рии корректиру; !.;::х кодов ' и до настоящего времени из-за свое., трудности голностью не решена. Например, до сих пор не удалось найти не только классификацию всех п.у. кодов, но и нетривиальную верхнюю/ оценку их количества как Функцию от П , 3 работах, исследующих эту задачу, ограничиваются пока построением отдельных классов кодов и изучением различных свойств п.у. кодов, в частности, с долью изыскания возможностей построения новых кодов из известных. К этому,направлению относится и данная диссертация.

Из результатов авторов, изучавших п.у. коды, отметим еле-дутг 1.

Г.С.Н!апиро и Д.Л.йлотник"^ установили замечателыг„ " симметрию двоичных п.у. кодов: в п.у. 0 -коде число кодовых точек, находящихся на расстоянии й 1. < , от данной кодовой вер&.ли, не зависит ни от выбора этой вершш.ы, ни от выбора кода. В связи с оти", они высказали предположение о единственности существования п.у. (.п., а,) -кода при данк 'X П. и й. с точностью ..до эквивалентности. Ото предположение олро-

1J Мне '.Vililano Sloiine Vi.J.k, The thoorj of зггог

- с. .тсс U соцоз: 1,1-., liorth-Hollcnd publinhinn со. - ^T.rj-tordwa York - Oxford, 1977. - 744 p. .Мак-Бильпкс Ф.Дк.,

Cjio.oh Д. Теория кодов,испывляпд'п ошибки: Пер. с а"гл -

;.:.: Оля } I'j7j. - 744 с. '

2) ,

„ляпро Г.С., плотник Д.Л. К математической теории кодов с погрньлеш- v. ошиСмс // Кибер-.о-кпескиИ сборник. - Гл., - > ' . - <:. Shapiro ¡I.e., Cilo.nifc D.L. On the aa-

thematical theory of error correctir.r codeis /, Ib.ii J. of Ken. and vi5:J. - v. з, ;; 1. - p.;?5-34.

вс.г Ю.Л.Васильев1^, предложив класс кзгрупповых п.у.(а,3)~

ко-О в Г.ЮЩ1К зти 2 , £аг»-0 при а-» оо. Класс кодов

оказался рекордным в том плане, что позднее чи один из авторов (О.Хеден, л.И.Соловьева, К.-М..1яборд, К.Т.Оелпс), предлагавших конструкции двоичных п.у. -кодов, не с угле л построить бо-

л^е мощного -ласса п.у.код^в. Изучения различных свойств двоичных п.у. кодов проводились также в работах Ю.Л.Васильева, Х.Бауэра, Г.Гг_.;тера, Ф.Хергерта, К.Т.Фелпса.

В.А.Зиновьев и В.К.Леонтьев (а также К. вал Линт и А.Тит-вайнен) доказали,что • зтривиальный плотно упакованный код над любым полем Галуа с^. 2., должен име'.ь те же параметры:

дтыну кода п. , мощность кода М , расстояние ме: ду кодовыми словами (1 , что и один из кодов Хэмминга шн Голея. Коды Хэмминга над исправляющие одиночные она' 'ки, имек/г параметры

ОАг1); А-Ь).

Д эичный (23,2^,7) и троичный (II,З6,5) - ко/я Голея единственны с точностью до эквивалентности.

й.шонхейм и БЛин...,от_ зм, обобщи, коды Ю.Л.Васильева, построили для любого и т.-^2. негрупповые коды над врС^ с параметрами кодов Хэмминга. Позднее появился ряд работ по построению п.у. кодов над смешанными алфсэитами (подробный перечень итих раЗот приводится в монографии Ф.Дж.Мак-Вильямс и Н.Дк.А.Слоэна).

Перейди 1 к описанию результатов диссипации, упомянутых вг'ие. касается способов построения и.у. , ^ -кодов, то отметим класс п.у. К'"цов обозначим его через С ), играющий особую роль среди прочих классов. Класс кодов С построен новым, преддокенн .м автором, способом объединения декартовых про-кзвс ;ений кодов (коды г.„рутсч из разбиений на и.у.

(0г-1У2.,Ь) -коды). Он оказался неэквивалентным ранее извест-

т\

Е-склт.ев Ю.Л. О негрупповых плотно "пакованных кодах // Проблемы кибернетип. - 1962. Выи. 0. - С. 337-339.

г» \

Васильев Ю.Л. 0 срав ении сложности аупаковк и минимальных дйзъшк'ывных нормальных форм // Проблемы кибернетики.-х963. - Вып. 10. - С. 5-61.

ним кодам Ю.Л.Васильева и 0.Холена. Кроме того изучение этого класса кодов позвол ло получить нетривиальную информащг- о свойствах пшекций произвольных п.у.^п.,5) -кодоп по любому из П. направлений: удалось установить точнне верхнюю л нипюю границы связности (границы количества компонент) произвольной кодообразукнцей д.н.ф., получаемой проектирование" произвольного п.у. кода, -ч также верхний и нижний зкетремуми мощностей решеток (решетюй назнваем мнотестьо версии пг он:; вольно'1 компоненты кодоойразуюи'чй д.н.ф.). Нпмалогакнум роль в диссертации играют решетка максга-гльноп мощности, в их конструировании, существенно использован способ построения класса кодов £ , а

с IV

именно, проекция по определенному напряжению в С. пе;шаль~ ним образом вибрашоги п.у. С*1, 20 -кода чз .С дала возможность получить разбиение на две максимальных решетки. Д.н.ф.,задавдно решетки максимальной мощности,оказались асимптотически максимальными по длине егхгдя д.н.ф. с ачатогпчкым локальным строением. Посредством каядой кодообразую^ей д.н.ф.,за-вислцеп от переменных, мокк« строить класс п.у. (.П-, ""О -колон, расширяя тем самым запас п.у. колов. По поводу способна построения п.у. кодов добави:.. такхц, что построена коцосбразу-«щач д.н.ф., позволяемая строить класс п.у. СП-, -ко, т.и.'л^-

хху.й мовдость 2 ) О при а-»-оо , раънуь моидсо--

стп класса кодов Ю.Д.Васильева. Наконец, заметим, что в работе предложен еще один ¡сласс п.у. -кодов, " простой конструкции которого используются С^ -кчниа кода Хмммипга и разбиении Е.* на двоичные п.... СК»^) -коли, '< = /Ты-Т -1.

Что касается кодообразуущих д.н.ф., то в дополнение к сказанному вьт:» добавим следующее. Так кпк кавдая кодообразущая Д. н., зап^ся^оя от п- аеремоышх, по спадает класс я.у. (а, 5) .-ксдоз, то йсо кодообра^угдне д.н.ф. ;:з разбива-

ет :-'-~ас , чеох п.у. С"-) 1) -кодоа "а пс яя. зеи кодов. 'Гакам образам, -остро-.-япе кодов т едуциручтея к построении кодообразую-ии'.у. д.н., кот"р ■» составлены ;;з р-^уляркых частей - комгт-нен?, б* Л' об<-'зр,:.".н л лотом/ в дальнейшем могут тлуиить основой г.г:чссп¡'.икации ьссх ¡¡.у. кодоп, В работе сделано первое нр:!бд::я:-г»к-.' г. описали/; кодообра:<у>щйл д.н.^., а следовательно, и г.од')я, - '.чагак-оризочанц упгкяпгуие втлз экстремальные ситу-

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

Результаты настоящей ,-иссертации докладывались на У Всесоюзной конференции по проблемам теоретической кибернетики (Новосибирск, т980), на У1 Мекдународном симпозиуме по теории информации (Ташкент, 1984), на Ш школе по синтезу и сложности управляющих систем (Новосибирск, 1989), на семинарах ИМ СО АН ССР и ИГУ.

Основные результаты диссертации опубликованы в работах а- тора [ I-5J.

Диссертация состоит из введения и трех глав. Глава I состоит из одного параграфа, глава 2 - из пяти параграфов,глава 3 - из двух параграфов.

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

Пусть и Ltn-;VZ=Cil"SAt: - два пронзив довольных разбиения множества на и.у. ССп.-^")Д>2>)-коды. сп-т

Тогда множество С= U гД8 "^к ~ k^» J > lJ" Ole,

Crjco^ , К. - 0„t >...,(.»-0/2- , Ж - произвольная подстановка длины Cn.+ i)¡1 % является п.у. (as 5") -кодом. В процессе докаг .тельства неэквивалентности этого класса кодов построенным ранее кодам, выяснилось,- что коды О.Хедена^ можно описать предложенным вше способом объединения декартовых дро-кзведе: ий кодов. Оказалось,■ что класс колов О.Хедена строго со-, держится I С Позднее предложенный авторог метод построения и.у. (а, 3) -кодов oiui переоткрыт, с некоторыми отличиями (последние состоят р построении сходных разбиений), дву..ш авто-

H»den 0. A new const-auction of group and nongroup perfect oo-eu, - Tnform. Contr. - 1977.'- V. 1,4. - P. 314-323.

рами: З.-М.Лябордом и К.Т.Феллсом (ус .ышкт. ноз .с спой результат) .

В главе 2 исследуются проекции произвольных п..у. С п., Ъ) -коде в го лк.оому из а направлений: вводится понятие кодоо^та-зуицей д.н.ф., изучаются общие свойства отих д.н.ф. и осуществляется их конструирование. Проекция каждого п.у, СП-,5) -код; по любому из а направлений определяет свою кодссбргзурщю д.н.ф. о пг компонентами, из кото, ой, в свою очередь, мокко получить класс п.у. (а, 3) -кодов, имещий мощность 2. " и содержащий исходны!! п.у. к'д. Кодообразуыцая д.н.ф., таким образом, позволяет охватить целый класс п.у. кодов, оправддиая тем самым свое название. Глава в основном посвящена изу^нид Факторизации кодообразуь.;их д.н.ф. В не;! конструируются '•одообра-зуклцие д.н.ф., имеквде максимальное и минимальное количество компонент. конструкция кодоооразукцей д.н.ф. с максимальней по мощности компонентами оказалась нетриачальной и доя ее осуществления потребовались постановка и решение отдельной комбинаторной задачи для пары слоцис .ъних систем троек ¡Лгс-Й'"зра. 3 главе допаивается, что количество компонент каадой кодооб--

разумей д.н.ф. но больше ^ /(.кл- \) . Таким образом,уда-

лось .установить точные верхнюю и никкюю границы связно^ л (то"~ ные границы числа Компонент) произвольной кодаобразувдей д.н.ф.

примечательно, чго в торг.-лнах исходных п.у. -кодов

оба зкетремума связности достигаются на одном и том *:е объекте. Л именно, проекции но разном напраат-чням сн цкального вида п.у. (п.,3) -кода, £}, = "Н,--, определяют лга кодсобразуадио д.н.ф., одн . из которых дает тс ¡ую верхнюю, г-другая - точную никнкю оцени: связности.

Ъ 5 2.1 вводятся необходима*? определения, обозначения, устыанллгчотся азгалоияз!. кодообрапугдпх д.л.ф. и л.у.кодов, Пу'.вс-дс-:.: краткоо слрчдсдоние кодообразукалх д.н.ф. 11усть С* - •'■'>■::к:п;,чл:..'>оль.чого л,у (п 3) -кода С ( С ,

2 1, ), я 1 по произвольному ¿-мерному на-

щаа-сн;::? ^ ,2.,..., п\ ("-.е. результат вичерклврчия

коор;:д' -та и к''0рднн£.т;!0Я перая.. кода С ). Введзм

граф Г СС*), цострое.'лшй ¡'ч С ;:зк на множестве вершин с Р'-'!1'-'*:. Г<тг><-л'п®у:.гх том парам »«»{т.. из Г.* , в которых вер-окг др'т от пту. га •!« рксс.оякил 2 по Xuw.ii. .гу чт.е.

на мш-гимально воамо8;ьом расстоянии) .введем тапке д.н.ф. DСС.*)} которая составлена из элементарных конъюнкций,отвечающих 2-мерным граням куба 1 натянутым как юз на те пары вершин из с*, которые п графе Г (С*) t эеданены ребрами; эту д.н.ф. назовем "одообраяутсгй. Компоненты связности графа Г С С. ) индуцируют рас ле"ение д.н.ф. С С С*) на части, которые назовем компонентами кодообрязумдей д.н.ф. DCC.*). На рис. 2 см. примеры компонент из Г С С*") и из D С С*).

Смысл введенного понятия кодообра^ущей д.н.ф. раскрывается егс ге летрическо" интерпретацией. Трудность формализации геометрического материал" оправдывает нек торую многословность, к ¡OTopoií п~чшлосъ прибегнуть.

В силу плотной упакованности кода С в Е."" для каждой С мнокество координат {, 2. ,..., \ «=> \ однозначно разбивается на т~кие неупорядоченные пары {_ I к , Sj-.n--^, что X 3KL* Тагам образом, около вер-

шины X' (проекции X по S -му направо нию) группируется Сп-0/2 вершин на расстоянии 2 от нее. Тем са'шм в Е"-"1 образуется звезда 26СX ) из (пМУ2. пересекающихся лишь по X' двумерных граней (этот че^нднын факт дкляется частным случаем теоремы 3 Г.С.Шапиро, Д.Л.Злотника о п.у. кодах с произвольным расстоянием (см. сноску ^ на с. 3). Это означает, что каждая компонента графа Г (С*) регулярна, степень каждой вершины равна О-0/2. . Для звезды , где X' » <¿S-1>0L: возможны 2 расположения относительно кодовых'вершин кода С : лхС > J, —С • > О, ^s-m «¿oT) (см.рисЛа), ли^о X - C°¿1> «¿s-ь "í j •• j "¿n-^ (си. рио. 16). Отсюда каждая компонента графа ГСС*) является двудольным графом.

5*1,

Рис. 1а

Рис. Гб

К звезде по каждому ее лучу - двумерной грани,

присоединяется звезда из (.И--0/2. лучей, ио какдому лучу пос-

ледней вновь присоединяются звезды днуисрннх "•ране1* и т.д., щ тех поп, пока какдля звезда не будет присоединена по ка\<до,му лучу к какой-то друюй звезде (последнее п;юизойдот и сил;' плотной уппкгзалноотн проецируемого кода С /. ü результате получается связное н замкнутое множество звезд дпумеринх граней. Полученное множество двумерных граней образует д.н.ф. (обозначим ео через ZL ), отвечаьцую одной из компонент графа Г(С*). Глзъуль4дию таких д.н.ф. по всем I, I ^ Lim., где ГЛ- - количество ки.хоначт графа Г (С*), назовем кодообразумцой д.л.ф. D сс*), а сага д.н.ф. Z1 назовем компонентами ¡содсобрчзукс;ей д.н.ф. DC С*), hu рис. 2 приведен пример компоненты кодообра-jyKiuei: a.u.;. » Е-С с выделенными в ней двумя заездами: звезда Z 6 (jiприсоодпн-.-па звезде но двумерной гпакл,на-

тянутой на aoju:;jhu <L' и J>' .

Хомлон знта из DCC*) Компонента из Г (С.*)

Z^Z'y

Рис. 2

Множество neju-'Hii д.н.ф. ZL назовем решеткой и обозначил через Rl . Плотная }лакопалнос?ь кода С при переходе к кс.,о-образупцой д.н.ф. трансформп.уотся в исчерпанное"*) куба Po-otk.-i.vj: r<>...> r,^ так что д.н.ф. d(c*) токдест^онно на Г. i;:i вс;га илоте клаанпого след/от,что,пользуясь одним яздки геор/!,: грЦоп, но. >зхомо mvrco охарактеризовав ^ сч рук-туру ;:.у. коде:) (:,то с^отоятельство хорош аро:иш>от~

р/.ровано 'ч рис. 2).

Совок;, лность ье;;::пн г; г секции С* кола С . при.чадюслщи.х данной : •:::отко , чп^огк-м узлами г той решоткц и обозначим ■ еров С- . "а-дай у о ел рок<?гга R^ опоучеек шаром радиуса 1,зер~ mmpzi-o содержался л R;, . Т.о. С* являзтеч как бы "вну-т»-'л..if.'jtj.г." ро:..'огк:: ; ро/;;от;:а R;, , .j слою очередь, явля-

'гкго-;;;< Cf . С* , С|\ j , j.are-н

дру1 от друга в Е.л~1 па расстоянии не меньше 3. Поэтому решетки К; Я-, не пересекаются. Последние дза обстоятельства с

1 1 л* л*

учетом строения множеств С^,..., , позволяют производить

независимые варьирования кода 0. на компонентах д.н.ф. О С С*). Действительно, сопоставив вершины С* с вершинами кеда С ,убеждаемся , что множество узлов С* каждой кошоненты 2Ь разбивается ча две части: одной части вершин отвечают в С вершины, в-я координата которых равна 0, другой - вершины, Б-я коор-ди!^ га которых равна I. Ясно, что код С можно проварьировать на компонента 2й , приписав й -й координате противоположные зк .че ия. В силу отмеченной выше удаленности друг от друга множеств С*,..., С^ , такие варьирования кода С можно произ-во, дть на различных компонентах д.н.ф. Г £С*) независимо.Каждое варьирование задаст свою функцию принимающую значения 0 или I на 2й из множества ..., Совокупность всех варьирован^4 охватывает класс всех п.у. кодов с данной проекцией о* . В силу специфики функции ХСЙ1") мощность этого

л (И

класса равна ¿. .

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

тивоположные) .

.?*Г.„За_........................Гпс. 36

Решетку назовем однородной^, если порождаемое звездой 2:<;(<£) разбиенир пучка ¡¿-мер-ых ребер, выходмих из -зла X ,

Введенное выше опредрление решетки отличается от ооще-принятого. но " случае однородных решеток с ;о аналогично.

на пары ребе; ¡5 зависит от выбора узла <¿ ; в зтом случае вое

звезды полуиаются одна из другой сдвигом Kj^a Е. 1 . Кодооб-

разукщую д.н.4. назовем однородной, если псе ее компоненты пост л-'

лучаются друг из друга сдьигом куба с. , ка>удя компонента задает однородную решетку.

Первоначально рассматривался класс однородных кодообразу-вдих д.н.ф. V (Z.p, введении" кчЛ.Хйсалмаыч! ¡^ породивший из i лчшй класс п. у. (П-, 2>) -кодов (см.с.чс-;и с. 4). Однородность служит при этом целям реализацииименно, индуктивному построению друт через друта п.у. (tt 3 3) -кедов к кодо-образундих д.н.ф. при П. = 7У~\ ,

Формальный переход отсыда к общему понятия; кодсобразуг/дей д.н.ф. не представляет каких-либо затруднений,бы. виден ¡J.Л.Васильеву^ еще в начале (">-х годов л привел егс к постановке задачи об отыскании неоднородных кодооЗразугацих д.н.ф.. Последняя имела целью не только расширение запаса кодсобразувднх д.н.ф. и п.у. кодов, но и анализ самого понятия -- выяснение tro целесообразное!., и содержательности, о которых следует судить по количественному и структурному богатству его реализаций. Например, переход к общему логтгию был бы бессод расатель-ним, если бы оказалось, что кодообразуюздх д.н.ф., отличны:: от однородных, не существует. Первоначально более слндае.'.щм представлялся этот вариант решения задачи, долгое вре.-w ситуация оставалась невыясненной, а затем оказалось, что на самом деле имеет место другой вариант, а "менно - автором настоящей работы были обнаружены кодообразующие д.н.ф., ре'зко отл/ алциеся от однородных, я тем самым найдены весомее основания для взе-

^ В работе ЮЛ.Васильепа (см.сноску ^ на с.4) уже фигурируют все основные моменты общего понятия - проекция С кода С в виде д.н.ф. Убц ; звезды и ко.лпоненты .шгност!» как сцепления звезд в виде д.н.ф. с|-с >' ГРа'£

ГСП в виде д.н.ф.Vie-L

и д.н.ф. D (.С ,)в виде VlJ-t ; взаимоотношение С* и \)(.С*\) как "внутренности" и ее "окрестности"; независимые варьирования на компонентах, задаваемые каждое своей функ лей ХСс) на компонентах и охватывающие вое коды с данной проекцией G*. Отсутствует лишь очевидное указание, что при нарушений однородности замкнутость компонент обеспечивается плотной улак-чанностью проецируемого кода (в случае кэ однородности зг-чену сть компонент имеет ¡vihoto по их опр-^деле! ю).

денпя и исследования общего понятия.

Понятие :«ш>ооразуьдей д.н.ф. с одной стороны яс шоляст ставит' задачу к 1струпровг. .:я и изучения конкретных классов ходообр зущих д.н.ф. и связанных с ниш; п.у. кодов,а с другой стороны открнаас- возможность установления общих закономерностей,присущ;;/ .¡>сым проекциям л.16ых п.у. (п., -кодов и в свою очередь дасг ориентиры для упсг/лнутого кс г7;>уироьанкя. Пср&аи сторона от аз:она в пос?:>сенн.; неоднородных кодообразующпх д.,!.]. В ЕЛ-1, , максимально и мннимашю

мо:з;:мп компонентами, вторая - п обнаружении как простых, так и нетривиальных, геометрически интересных с^.ойстз произвольных кодосбразуд.н.ф. К гмюстым свойствам относятся следо>гае: код;-честно ¿смпонент каклой кодообразувдей д.н.ф. че меньше 2; в случае с на:ц;гньпд;.1, равным двум, количеством компонент.сами кскг.снзатг: ла-ягяся максимально мощными. Какдая компонента графа Г (.С*) (а следовательно, а компонента д.н.ф. ОС С.*)) является двудольным графом, т.е. все ее ве^нпы (соответственно, все уздоьпз ьерц:п;:ы любой компоненты д.н.ф. О (.С*)) разбиаа-и:^.. ¡;а четные и нечетные (соответственно, кратные и не кратные •;). !,!логеег.'ю ^'злоб каждой ко/.-лоненты произвольной кодгю ра?\".ией д.н.ф. отстоит от множеств узлов лксой другой ее

ы на гассто ¡ни не меньше 3. Каждая т/ешетка содержит, помимо вершины £ , икьзрсиук верспну ^ где 1

ед/нк'.'иа1? верщина длн:._ П.-4 . Нетривиальная закономерность, присущая лъсой проекции льйого г..у. (П.,3) -кода, состоит в том, что рещ^т^, отвйч.ах.дак произвольней компоненте произвольной ко-

дообразухщо^ г.п.р. в Е.""-1 , имеет мощность не меньше мощно-,

Lг*.—1

... . Чередование п излокенн.. в

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

Заметим, что понятие рещетки аналогично лонятиь цикла в

— •> 1 (.то;4 2). Цикл - ото связное замкнутое множество,из :с.г 'дой верит г . которого выходит "звезда" ...ч дь'ух одномерных граней, решетка - связное, замкнуто'0 млокостио, из катдого у?...а которой выходит звезда из (Пдвумерных граней. .Тягача п^трсендя цикла максимальной длины в Е.п~1 выделяе.ся своей трудное. и до сих пор известен только порядок максима.:!

ной длины цпкла^. В случае решеток удалое построить рслэтку максимальной мощности з Е"-'1 , п.^2.^-1 , Зшлетпм, что

эта решетка отпечает ког"'оненте некоторой колооСразукей д.н.ср. Но можно рассматривать а Е. для лкбого к. д. 1)00, локально устроенную так so, как любая комлонен.а нодообразуик ; д.н.ф. D (С*),но не являющуюся компонентой кодосоглзухцеч! д.к.Л, (обра1 ^зана из звезд, состоящих из К. дпум'^ных л'ракой, присоединенных друг к другу по одному лучу - двумерной грани; связна и замкнута). Оказалось, что оценка сверху мощности множества вершин и мощность упомянутой вшие решетки асимп-тотичоски равны (§ 2.3).

Конструирован:!" -¡ешстки максимальной мощности, которому посвящены §§ 2.2 и ¿.3, предполагает посменно з Е , П.»2.^-i, как можно более протякешсого,связного,замк-

нутого множества звезд двумерных граней, присоединенных друг к другу. Конструирование решетки было проведено "снизу": автору удалось, зная,,что специальные системы троек Штейн ера (СТП1) порождает кода Хомминга^, выбрать пару неперзсекахщигоя СТ'Л таких, что порожденные ими коды Хомминга и их сдвиги, "оложенныэ в ос: эву конструкции кода из £ , позволили построить регаетну максимальной мощности. Кон.груирование решетки прозодигся индуктивно. Двумерные грани, из которых будет составлена решетка, окажутся не чем иным, как совокупностью связанных друг с другом перемычек между верлинами из различных декартовых произведений сдвигов кодов Хэмминга.

Евдокимов A.A. О макопмалы.^й длине цепи в п. - дерном единичном кубе и некоторых, родственных задачах: Автореф.дис... канд.ф.13.-мат.наук: 009. ~ Новосибирск; 1971. - 9 с.

Соловьева Ф.И. Веохняя оценка длик_ цикла з П. -мерном единичном кубе // Мзтоды дискретного анализ^ в решения комбинаторных задач. - Новосибирск", 1987, - Выл. 45. - С. 71-76.

^ По лемме В.В.Глаголева (см. статью Я.М.Курляндчика^) для любого группового (п.>й)-кода ^гцЛ существует групповой (п,(1) -код С n.,d. той же мощности,базу эторого можно -убрать среди вершин веса (L .

о)

Курляндчик Я.М. 0 логарифмической асг -птотике длины максимального цикла разброса '/ Дискоетный анализ. Новосибирск, 1971. - Вып. 19. - С. 48-55. "

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

мно- угй 1ГХ = ,, Х 6 С< ,

Множества , по своей декартовости, разбивают множество координат куба Ена два равномо'дных мкокества, что существенно облегчает : ст;>о лне кодообразуюшх д.н.ф.

3 2.2 псстг она наследственная пара нэпересекавдихсл СП;. Др и Д , т.е. такая, что: I) каждая из '¿тих систем со-дорудт ссстьетстжзкно непересекающиеся пг -системы порядка Ср-1 У-2, построенные нз одном и то ке множестве ■{_ 1,2.,...,

2) существу. подстанопг; X на кноксстве^З.,...^, п^фодякъя Ар в Др и раз^чвакцаяся на произведение двух цикле'о не единичной дд'-чы с фиксированном значением на злементо р . Ласлед •'веннос-ь пари С'ГШ обеспечивает проведение индукции, !1е::ере ячейке Д^ и Д р и указанный специальный вид подстановки % беслечкпах/г лротяхеннегть и связность строящейся -■'петкн. замкнутость и число двумерных граней в каждой звезде, Г ьное сСеспечкваг.тси плотной улаксванностъд исход-

ного кода.

Гара СТи; Др и Др порождает пару кодов Хэммлнга С0 и Со такух,, что качдая пара крисоед-нешшх друг к другу звезд двумерных граней в ^тро/гдей'репетке оказывается су'щест* ;нно различно-;-., т.е. присоединение звезды не нмекл- двумерных гра-■'.?■'.■ (кроме , луча присоединения), в которых залети одинаковые 1-мер ,ые ¡¡аправле.'.кя. 3 то ке время все звезды двумерных граней с центр ..и ил (к. фиксировано) устроены одинакового, разбчь-нне пучк^. 1~мерних нал;.аг' телий, разстых на пары по принадлежности к лучам одно., звезды, повторяется для всех звезд (но для разных , "Пг разбиения различны). Разливе звезд и регулярное их устройство да>тг возможность выбрать базу подмножеств?. всех ч». 'них вери...н множества из таких верили, что от одной моки перебраться к другой через аепииш К* , СП--О/Я . Моачэсть зтого подмнокптва обеспечивает, народу с использованными в качестве "мостиков" т-г/нам.;: из , протя-к "ность решетки. Т.е. удалое.. последоипч-льно нараздватъ,начиная с одной звезды, звезды дг»"мег,"чх граней так, что репей а максимально пасиидт^тсп .на кл: :м ечто при проема? зип-дчи:: ее от

нулевого уровня до максимального среднего в 1 и дало» ведет себя симметрично, сууаясь к единичной вершине.Остается добавить,. что мощность построенной решетки максимальна, так как достигает верхней оценки мощности решетки, от/ чаххцой компоне1'-те произвольной кодообразущей д.н.ф. Заметим, что дополнение этой р^четки в Е*1-'' такае является решеткой, причем она :ю-лучаеты! из первой сдвигом куба Е.Л~\

Таким образом, построение двух решеток максимальной мощности, исчерпывающих Е.""-1 , свелось к решению отдельной комбинаторной задачи, а именно, к построению наследственной пары непересекающихся СТШ.

Исходя из этой пары СТШ, в § 2.3 указан п.у. Сгц'Ъ") --код £^=3,4,...3 проекции которого а Е."" 1 по разным направлениям определяют две неоднородные кодообразувдие д.н.ф., первая из которых (§ 2,3) имеет максимально мощные компоненты, вторая (§ 2.4) - компоненты, задающие однородные решетки. Вторая д.н.ф. содержит 2О компонент и поэтому зада-

^п-С: -¿»Л

ет 1слс зс п.у. (П^З) -кодов, имеющий мощность 2. }

> 0 при Заметим, что среди решеток этого ранолешш

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

Максимальность мощности построенных в §§ 2.2 и 2.3 решеток привлекла внимание к выяснению в § 2.5 противоположной ситуации, а именно - к поиску ротеток г.-ишмальной мощности. Дело в том, :то если бы нашлась кодообразуюцал д.н.ф. з Еа * , мощность какдой компоненты которой была бы меи'ше моигости однородной решетки в Е.4"1 , то автоматически бьь.а бы улучшена известная нижняя сценка числа п.у. (гъ, 3) -кодов (см. сноску^ на с. 4). Однако выяснилось, что мощность решетки, отвечающей любой компоненте произвольной кодообразующей д.н.ф., зависящей от |г-1 переменных, не меньше СИ-+1) , эта граница

получена индуктивно, она оказалась точной, так как неоднородная кодообразующая д.н.ф. из § 2.4 и однородная кодообразующая д.н.ф. содержат в точности 2 компонент, каждая

компонента задает однородную решетку мощности (Ч.+ Г, ¿^"^У2-Тем самым была установлена верх!, .я граница связно -"и произвольной кодообразующей д.н.ф.

¿ля установления упомянутой границы доказываются три лем-леммы 2.5 •* 2.6 лозьс -йот установить свойство равномерной распт^дзленности множества С0 (множества вершин кода С , которые при проектировании С по направлению Э переходят в С0), содот»аац»п\. нулевую вершину, в пределах »> -гс и (Л+1)-го уровней куба ЕЛ, к.= 0(гпоо12), 0 6 К < СП--0/2 , а имени.: ка'ичес""1с аоши!. С0 , имеющих веса К и К.Л- \ , не меньше

Ца-0/2 • :-'го позволяет, с учетом того, что каздая решетка со-

д^Р^'.т, помимо вершины «¿ , инверсную вершину о1 © IП ^ (лемма 2.7), получить минимальную гран:*",у мощности производной ре-

шс г ки, ¡йьнуг сп-+1; -

В главе. 3 приводятся до! мнительные результаты: в ней прс-длагахтсл два класа двоичных кодов. Первый класс п.у.

(22|<-1,3)-кодов сличается простотой описания и связан с главой I пег. ель? ^ванном ¡азбпений куба Е "* на п.у. коды, ¡(оды второго класса пмек/г большие расстоянл>! и строятся методом объединения декартовых произведешь кодов, описанным в главе I. И § 3.1 прелагается масс двоичных п.у. (.22л_ 1>3)-:т доь,

.".стсрые строятся из ( 1, 2*2 ~ * } 5) -кодов Хоммлнга над с^-2 } и из разбиений (2*- 1)-мерного куба Е.**"1 на п.у. (2К- 1, 3) -код1- Идея ; ^строения этих кодов аналоги ,на идее построения каскадных ко. ^в и ее модификации. ' Заметим, что способы построения (18, 10456, 3)-кода^ и предлозанного в § 3.1 лер.?:<л;:;:?^гся с методом построения смеиа^шых кодов О.Хе-дзка и тем >..« яьлякте;: развитием натр лленкя, предложенного М.Ге'цогсм и ¿.„енхеймом, Ь.-Ь^дстремом я гоо дол конного О.Хеде-нсм.

Пуст> Е. = Си > К.= 2,3)...) есть разбиение куба

на двои.яые л.у. (2 -1,3)-кол» Со.С,,-.^^. Пусть О - Произвольный код с параметрами (2*-1} ^ ¿^ _кола

..эишшга над 6.Р(<у), К=2,3,..„ Тсгди мк т.егьо

Н ¿¡Tibial г: fir. И.О. Two v Ъ1 'ary codea v/ith r.inlnu:n tn-jo three // Xi'iS Tr&rc. on ln^'orai. "Theory. - 1938. -■ V. 34, N 4, july. - P. 575.

1С

Изъявляется п.у.(2. -кодом. Вершины кода Са - ¿тс

всевозможные вершины вида £ = ' ^до ^ -

произвольная вершина из кода Сд,^ , т.е. -го кодч из разбиения Е.2""1 на С0)С,,...,С^^а Со.,,^^,..., й.^- произвольная вершинп из кода Ц .

Подложенный в § 1.1 подход позволяет в § 3.2 получить класс кодов, имеющих те же параметры, что и коды Рица-^аллера и отличающихся от введенных ранее Ц.Л.Ли, З.Н.Снгом, '¿.Р.Рутом, а также в работе А.К.Пулатова.

В заключение автор выражает глубокую благодарность У.Л.Васильеву, под руководством которого была выполнен^ эта работа.

Список работ, в которых опубликованы основные результаты диссертации:

1. Соловьева Ф.И. О двоичных негрупповых кодах // Методы дискретного анализа в изучении булевых функций и гра^в. - Новосибирск, 1981. - Вып. 37. - С. 6^-76.

2. Соловьева Ф.К. Реше-ки, отвечающие кодам с расстоянием 3 // Тез.докл. У1 Мандунар.симпозиума по теории информации, часть 2, Ташкент, сентябрь 1984 г. - Москва-Ташкент, 1934. -С. 177-178.

3. Соловьева О.И. О факторизации кодообразуюднх д.н.ф. // Методы двекг тного анализа в исследовании функциональных систем. - Новосибирск, 1988. - Вып. 47. - С. 66-38.

4. Соловьева Ф.И. Класс двоичных плотно упакованных кодов, порождаемых -нчннми кодами // Метода дискретного анализа в изучении булевых функций и граф з. - Ьопосиби^ск, 1989. -Выи. 48. - С. 70-72.

5. Соловьева Ф.И. Точные границы связности кодообразуыцих д.н.ф. - Новосибирск, 1990. - 15 с.-препринт / СО АН СССР. Ин-т математики; № 10).

¿и