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

1 1 о 3 "911!

' ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР АН РЕСШЫИКИ АРМЕНИИ

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

ОСИПЯН ВАЛЕРИЙ ОСИПОВИЧ

УДК 519.1:612 621.391.15

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

( 05.13.17 - теоретические основы информатики )

АВТОРЕФЕРАТ

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

йрезан - 1ЭЭС г.

• I ■ /

Г ! /

Работа выполнена в Армения. <Xf

Вычислительно! центре Академии наук Реепубяш

Научный руководитель: Официальные оппоненты:

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

академик АН Армении Варшамов P.P.

доктор технических наук Дддаев Ю.Г. кавддат физико-математических наук Мхитарян А.Г.

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

Задита диссертации состоится "2fr сре6[>йл$ las i г. в 4чЧ сов на заседании специализированного сове^а л 005.21.01 по присуждени ученой степени кандидата физико-математических наук по специальности Ob.13.17 "Теоретические основы информатики" при ВЦ АН Армении по адре су: 375044, Ереван-44, ул.П.Севака, I.

С диссертацией можно ознакомиться в научной библиотеке ВЦ Ali Армении.

Автореферат разослан

г.

БЩЛЛ ХАРАлЧЪР/ОТИКА РАБОТЫ

Актуальность темы. На современном этапе развития научно-. TtAiij.'ifcCKOi'o ьрогрбсоа прьдтльдйэкм-. все более высокие требо-ьан1л к ^«лггльности i: надежности работа сложных щодоекх wj.ctws перваче, хранения к обработки информации. Уювяетюре-ш'.е утпл. тре^оьанпд достигается, как правило, применением аппарата помехоустойчивого кодирования. Б частности, на практике преимущественно используются линеиные коды,- которые обладают простыми алгоритмами кодирования и декодирования.

Широкое распространение ь последнее время, получили циклические коды, которые обладая особой алгебраическом структурой, наиболее приспособлены для технической реализации. Б свою очередь проблема построения циклических кодое упирается ь проблему синтеза в явном виде неприводимых над конечными полями полиномое с заренее заданными свойства!«:. Можно назвать еще рад областей / в теории лине иных рекурсивных последовательностей, в теории кольцевых счетчиков, в радиолокации,б телеметрии и др./, где теория приводимости играет решающую роль.

Одновременно отметим, что наиболее трудной проблемой утоп теории является проблема синтеза неприводкмьЛ над конечными полями полиномов заданной степени б явно»« ЕИде, а также определение показателей, к которым они принадлежа'.

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

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

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

1 вечных шлях с заданными свойствами;

- разработка эффективных алгоритмов разложения полиномов ; на н вправо дмые ияожитедя над юне<ошми тлями;

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

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

Научная новизна, основные результаты, полученные в диссертации, являются ношде и состоят в следующей:

- разработан рекуррентный метод синтеза полиномов деления круга Уп(х)< особенно удобный для больших П, швеяцих два и более простых нечетных делителя;

- и случена конечная фородла для коэффициентов полинома де-

| ления круга, представляющая собой ыэдифицироъанкый вариант схеш ! Горнера, допускающий эффективную алгоритмизацию;

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

- получена рекуррентная формула для подсчета числа перестановочных в полях Галуа полиношв заданной степени;

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

Практическая ценность. Шзработанные в диссертации ьх'Тодш ьюгут найти применения в алгебраической теории кодирования, в частности, при синтезе циклических кодов БЧХ , в теории линейных рекурсивных последовательностей, ь теории кольцевых счетчяюв, ь радиолокации, ь телеметрии и ь других областях, где теория приводимости играет оущестьишу» роль.

Тема диссерташи соответствует плану научных работ-ЬЦ АН Рсспублия Армения и неиос] ддстьенно сытна о темой "Обеспе-

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

Апробация работы. Полученные по теме диссертации результаты докладывались и обсуждалась на Всесоюзной штле "Конструктивные метода и алгоритмы теория чисел" Лйнск,1589г./, на се-кинарах факультета ЕЖ КОТУ /гзосква, 1582-1950г./, ВЦ АН рес-публшси Ариения /Бреши, 1985-1990Г./, Кубанского государотизн-ного университета /Краснодар, 1979-1390г./.

Дубли каша. основные результаты диссертации опубликованы б работах [1] - [в].

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

СОДЕШАЖЕ РАБОТЫ

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

Хп(х™)> ' гле Хп(*) = П(х£-1)

С^/'И

- полином деления круга, имеющий своими корнями ЧТ'п) элементов поля галуа одного и того же порядка. Здесь и далее УЫ- функция Эйлера, функция Мёбиуса.

рассматривается таша-задача синтеза циклических кодов с порождающим полиномом и описывается арке метические А /V- кода для простых генераторов 74-.

В § 1.1 приводится рекуррентный метод построения полинома в полях Галуа Р«, основанный на разложении в функ-

циональную цепную дробь (0)у'<<3»»]. где Рц,е\г - ДБа различных простых делителя числа -И. Предварительно доказывается следующая

лемма.

Леша 1.1.1. Пусть Р2х,Ег - простые числа. Тогда над Ре разлагается в цешгув дробь вида

v / ч/X» / ч ле<-ч)/р, ib.-ii)/i, и*-*. т

K-l ' ' ' z-i

где i определяется из сраиненна:

Pj = -z, (tWfJ , P, = faocl i<)> - > = ° ('moä О •

Затем на основании свойств полишш }?ц(х) & Дешшх Дробей доказывается.

Теорема I.I.I« Пусть Рк< "' ^ч - вое различные простые делгтели числа <П~ В, 8av Вк. Тогда над» Рр

^р, •»\Сх) = Xg« Ек._1 (ос+

где и с юбки Эйдера для разложения Хе, •

ь цешУ° дробь.

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

Б § 1.2 приводится алгоритм синтеза жшшо;да PcViW для произвольного 41 , который Легко реализовать на ЭН5. Метод такой реализации сводится к многократному применению теоремы I.I.I.

Б § 1.3 выводится конечная формула для коэффициентов Ли., U - i, vff'n ) полинома для fi представляющего coöof произ-

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

Si I о1,. ч о о

£>г sj. 2 •• • чэ о

Svi Su-1 Sm-J'"^ где = Su,£-„ ,

с, _f ß-1если' u.-^ol'ynoci £v), __

lPv-1, если и ~ ofaooiev ), ir-i.tC/ r •^-w,¡>v- сумма u-rux степеней корней полинома Су) > ;

р - характеристика рассматриваемого шля.

ir

Приведенная форлула ша$ици-.гнтоь CU, легка про г ранжируете я и сводится к ¡/адифицаровалноцу варианту ext-n« Горне pa.

Б S 1.4. пргдлагается конструктшньи метод синтеза полиномов вида Хя , что дает возможность несколько расширить класс непригюдош в полах. Галуа полиномов заданной степени.

Оскоь.-i.e {чгзультаты § 1.4 cqo рмули ¡кланы в вида теоремы 1.4.1 к лемм 1-4.1 - 1.4.4 и заключавтея в следующем.

Ле.т'д I.4.I. Дня произвольного некркводЕМЧГО в Fp полинома f(х) степени -П ъ 2 a Mix) С [х], М(у.) $ О имеет Ы':сто разложение „ .

где f (">(*) - формальная W -я производная юлмнока fi«). Лемма 1.4.2. Пусть /щ, - • • • В?s . тогда

d 11'->>1, <u «/J™, сЦлп,/^ Z »

Хр(х^) = П ¿Х^ндЫ-

1.4.3. Пусть г^Р^-Р/5 .тогда

¿емиа 1.4.4. Пусть г e^VS*'" Ps * . тогда

Ур^а*"»)

Теорема 1.4.1. Пусть £. Лу >«-1> 5 - раалич-

ше между ообой простые числа, ,<кч, Дг - неотрицательные ..алле чипа, /щ v .• , -П = ••• £4 •

Гогда над полем рациональных чжсел имеет »ото следуювео риз-лохвкве

»: '^ил.дки ллш. при Д = -«/Ч -' О»

(ine^/ T от—< тлть, что пемучекаье в i 1.4 ргаультаты о и«— лт-глт-лно.«!- rt» i:jnmu« cujbwjuuuiu к для «оден Гнлуь.

Б v 1.5. рассматривается алгоритм синтеза неприводимых. , в р£> полиномов заданной степени методом анализа, использую-, щий результаты § 1.3. Предлагается метод анализа, основанной на следующей лемме.

Лемма I.5.I. Для любого nfZ существует циклическая последовательность периода ti , шторой соответствует неприводимый в Рр юлином степени <Yt.

Ь § 1.6 приводится синтез цикличесиогоюда с порождающим по^-.'юмм деления круга •

УказыБь:тс,- методика построения такого кода.

В § 1.7 п. зарительно рассматривается задача существования примитивных ^ элементов! ¡L ,*3 и других, а затем приводится синтез циклических АУ - кодов для простых генераторов Л вида:Zp*i , fy+i , zmíe^i и •

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

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

Пусть CfoCzJ,j О.2-1Ы) -произвольные

алементы кольца Pg/Xí • При v/f определим по

рекуррентной формуле -

а^ш-хи u=[v р-1], яг-, ир +¿., о £ ос < м.

Пусть далее А о ¿ Ai , "' , Ag-t • _ класс операто- ' ров, областью определения которых являются полиномы кольца PglXi , причем если Д(=0 = ^ 9^ эс » 10

'u = 0 л *-AK~l(A I

Ш определению для любого, натурально го числа К4 , A<v/ - /Тг/ V*v/ и А«/- £ > где .Е - единичный; оператор, то-есть - <д(ос)Е = - cj (/.) для произвольного , б- pg [pcj.. л .

¡Г/сть^наконец,сеперабельный полином сте-яеш1-П7/1.

Тогда осношые результаты § 2.1 заключаются в следующем.

Лемма 2.1.1. Пусть Л(х) > %>(*) - два произвольных шлиноиа из Рр [х] , делящихся на полином Ч) fa), ^ р [Ъс j . Тогда полином

№^(ли «од е-* J (*-*>

тасте будет делиться на-тлином Si*).

При Jl(x)~ CC^-Jl , 'fe(x) - доказывается.

Teopem 2.1.1. Для любого натурального чиста Фл £ П, цолином

степени .£■ 'М является пропзведениец всех простых делителей ^f(ot) степень которых делит ли.

Пусть --

— С^ф'Ш

гдеч Xifr) - , тогда из теоремы 2.1.1. непосред-

ственно следует.

_ Теорема'2.1.2. Для любого натурального чист Фг, полином

ЛщвО является произведением всех простых делителей •f(cc) степени {Ш .

В заключение данного параграфа рассматриваются пример! синтеза для полиномов вида : + £ ^

В § 2.2 предлагается способ построения неприводимых над р полиномов с заданным периодом. Этот способ описывается

s

- в -

о помощью следующей теорема.

Teopetoa ¿..'¿.1. Пусть fy - простое число, \) = Oidty простои Ha^i рсу по-шном степени 0X7/1 периода , "-ffc) - HO-JrihOM степени -rt;v 1 , удовлетворяющий условию ?)=0(*пос1-¥Ы)). ТогАа полином

ире^стаь^ет собой произведение^

• (£-1)0,0)-О'1 непри-кыьмих нал Pq, полиномов, период кавдэго из которых равен Pi.

Отметил, что ь условиях теоремы 2.2.1 ири }= (£-i)('tt,>i) ]> полшок б/^tT неприводимым над Pq полиномом степени

'И ^Оил))'1 iJepi.0M P-i .

Е ' 2.J с помощью аппарата функциональных пепных дробей ь Pjpfxj рассматривается метод разложения полиномов на шкмкичели ь Рр .

Пусть ФСх)^:^ ицОС <*2.<т - 1 ' - норияро—

taHHb.ii полином четной степени /2<т над р£ , причем он не рьъьн квадрату другого полинома.

По оп^елелению иод Vgjfoj

— оо '

понимается нормальный степенной ряд, удовлетворяющий условию

—оо У <U-0

Ji6Mi,a 2.3.1. Пусть

Cat) = ДМ,

<tl - i, t-i - последовательность полных частных в разложении \/2>{х) t цепную „¡обь над рр , тогда полиномы Д|*)

1. \P<n-t(x) Ь^е'ЛЬО li{X).;Ta L Pg .

0or.oi.HOi. реоулыы I 2.0 сформулирован Б теореме 2.3.1.

Tsopeya З.Д.Г. а/ Если длина периода разложения i/2)farj :> гун^шомадьнуа ценную дробь над р0 равна i .то

Ж*.) = ¿KH (X) Д (*), (¿KVÍ (*) , iWl^J = ■1 >

-7 Если зе даша пертода разложения в функ-

цзппуз дробь над /ъ дакна. 2 к*+2 , то

3 (эО - Д»-и

¿W*) = , Мг+4 (St)- O-K+iW^+tí*),

":;с Т решение синения

5 заказчэние § 2.3 приводятся прпиеры разложения годиао-!-ов ^ гзучавтся свойства разложения упазашшх выез и других.

В §§ 2.4 п 2.5 предлагается гатод перестановочных функций, сахрааявдях г - .^дшэсть в р^ , и щаводитоя рекуррентная фордула для подсчета часла перестало нгчных целых функ-цнй таей Р^ .

Легяа 2.5-4. Число перестановочных полиномов ^(ос) степени И?/В поля рр определяется формулой:

=CB-J) e-i (% ,

где A/t.B-i (<) -р- число перестановочных полиномэв золя Рр степени не шше В-i , порожденных полиномом -f(x).

Рассматриваются.нематоде частные случая лекмы 2.5.4, в частности доказывается, что

[ЯО, при лг-i, JO, при <п-Ms,и (f(*)) = J400, При -и = 3,

I. тгстьей главе приводятся многопараэзэтхшеские ретеши. .•отс:;екннх л кругах систеи дао$антошх уравнений, имеь-

прения в алгебраической теория »дарования. 1 ^ Г-,.1 приводятся кногопараметрические решения дно-у;авненя£

■т .. /V- р

^ .■ о.2. рассматриваются шо гост еденные системы диофан------- некий и их »аогопарамзтрические решения.

■К-орема 3.2.4. Цго» (Лф С , ё ф с1, ¡р/ф/^^

а, с,о1, р, ч,

1°. ЕСЛИ а+С - %+А , то = > «-¿Л 3, что досташшет шогопараметрические решения нормальной многостепенной системы дносрантоБЫх уравнений.

с наименьшим решением 1 + Ч +•> > }

2°. ЕСЛИ аЬас+сг=вЧМ\ то ^^ что доставляет многопараметрические решения многостепенной систеда диофантовых уравнений

с наименьшим решением ~> +*и э ± "

у.

Здесь .те приводятся и -решения системы:

Ъ V 3.3 предлагается ноша сшааб решения нормальной ■ люгостепенной системы 5-ой степени гида:

Теорема 3.3.1» Цусть

'УЬ 2., Ъ, ^> 5 нормальная маогостепен-

кая система 5-ой степени, для которой выполняются следующие

гаьенства

• ,¿1 си & (си-8,)=о, ¿Ък О*4- =

I - ( (-1

¿ а( & = о, ¿аЪХ^О-<: = { с-~1

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

¿-I с = 1

Ь наложениях со держатся: таблица коэффициентов простых ^ Р р полиномов вида эс3-* Л*-*- £ при

;л.-ет.роБанном 0.6 рр , программы реализации методов'общего-"¿дхс^а ана.-.;;за.

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

I. ЮзраЗотан рещ?рреипш& цетод построения яолздомьь ¿.■¿¿.¿mil. круга, особенно удобанй для больших п , имеющих -и. :: простых нечетные делителя.

к. Получена конечная формула для нзадаициентов X*i(x) , .) (.¿^аьляудая со .Зой юдафдцирэ ванный вариант схема Горнер^, . ¿и/сшкзи!. эу^ектишую алгоритмизацию.

3. Разработаны канструкгиьше методы синтеза непркюдк-Рр 1юлиномов заданной степени в явной -виде.

4- Получена ре!?уррентная формула для подсчета числа пере-стаигьочных в полях Рр полиномов заданной степени.

^ 6. Г&зработаны метода многолараыетричесиэго решения 1с:огостепьнных систем диофантовых уравнений, имеющих приложения ь теория иодирования.

Автор шракает глубокую благодарность и признательность ciiO'-:,ry научному руководителю академику Р.р.ВаршадаЕу за посто-ялкое внимание и поддержку при выполнении данной работы.

Основные положения диссертации опубликованы в следукипк раоотах;

1. Осишш Б.О. Решение в целых числах некоторых дио-фантоь^х и систем дш^антовых уравнений /^бан. гос. ун.-т -Краснодар, 197S. - 13 с. - Деп. в ВИНИТИ 04.01.79, 91-79 Деп.

i.. Осишш O.K., Осшшн В.О. 0 некоторых свойствах много-

чли:а деления круга и их арифметических приложения ч.1 /;-йтбан.гос.ун.-т. - Краснодар, 1981. - 25 с. - Деп. в ESirr.i 07.07.81, J* 37S6-8I Деп.

3. Осидян О.Н., Осилян В.О. О неюторых свойствах ¡йогсчлена деления круга и их арифметических приложениях ч.П /КУбан.гос. ун.-т. - Краснодар, 1981. - 21с. - Деп. в . ЫЗГГИ 07.07.81, J* 3737-81 Деп.

4. Ссипян О.Н., Осилян В.О. О целых решениях многостепенной системы даофантовых уравнений (^-Х"1 — 'Ч,*1-»-

/куоан. гос.уй.-т. - Краснодар, 1982.- 19с,-Деп. в ВИНИТИ 31.12.82, Я 6552-82 Деп.

5. Осипян В.О. О некоторых границах величины

тм)

/К^бан.гос.ун.-т. - Краснодар, 1984. - 7С. - Деп. в ВИНИТИ 09Д34.84, .4 2556-84 Деп.

6. Осипян В.О. О примитивных агементах простых шлей// !,йте!.!&тические Бопросы кибернетики и вычислительной техники. - Ереван /в печати/.

7. Ссипян В.О. Об одном рекуррентном методе нахождения ::агцшс!..ов деления круга над конечными полями// Тезисы докда-лзб Всесоюзной школы "конструктивные методы и алгоритмы теории чисел". Минск, l£S9. - с.114.

£. ЕарсамоБ P.P., Осипян ь.О. Об одном методе приводимости полиломов над пешечными полят.о; //ДАН РА /ь печати/.