Модификация алгоритма Питерсона—Горенстейна—Цирлера и ее эффективная реализация

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

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Veröffentlicht in:	Электронное моделирование
Datum:	2015
1. Verfasser:	Фейзиев, Ф.Г.
Format:	Artikel
Sprache:	Russian
Veröffentlicht:	Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України 2015
Schlagworte:	Математическое моделирование и вычислительные методы
Online Zugang:	https://nasplib.isofts.kiev.ua/handle/123456789/101129
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Модификация алгоритма Питерсона—Горенстейна—Цирлера и ее эффективная реализация / Ф.Г. Фейзиев // Электронное моделирование. — 2015. — Т. 37, № 3. — С. 3-16 . — Бібліогр.: 5 назв. — рос.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-101129
record_format	dspace
spelling	Фейзиев, Ф.Г. 2016-05-31T13:04:29Z 2016-05-31T13:04:29Z 2015 Модификация алгоритма Питерсона—Горенстейна—Цирлера и ее эффективная реализация / Ф.Г. Фейзиев // Электронное моделирование. — 2015. — Т. 37, № 3. — С. 3-16 . — Бібліогр.: 5 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101129 519.95 Предложена модификация алгоритма Питерсона—Горенстейна—Цирлера на основе метода Гаусса и описан эффективный способ реализации модифицированного алгоритма ускоренного обнаружения и исправления ошибок в принятых двоичных сообщениях. Применены таблицы операций над элементами конечного поля, в которых вместо элемента предложено использовать показатель степени представления выбранного примитивного элемента поля. Приведен алгоритм декодирования принятых двоичных сообщений. Запропоновано модифікацію алгоритма Пітерсона—Горенстейна—Цирлера на основі методу Гауса та описано ефективний спосіб реалізації модифікованого алгоритма прискореного виявлення і виправлення похибок в отриманих двоічних повідомленнях. Застосовано таблиці операцій над елементами кінцевого поля, в яких замість елемента запропоновано використовувати показник ступеня представлення обраного примітивного елемента поля. Наведено алгоритм декодування отриманих двоічних повідомлень. A modification of the Peterson-Gorenstein-Zierler algorithm based on the Gauss method is proposed. The effective method for realization of the modified algorithm is proposed to accelerate the detection and correction of errors in the binary Bose-Chaudhuri-Hocquenghem codes. The tables of operations over the elements of the finite field were used and it was offered to use the exponent of a power of the chosen primitive element representation instead of the element. The detailed description of decoding algorithm of the received messages is given. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математическое моделирование и вычислительные методы Модификация алгоритма Питерсона—Горенстейна—Цирлера и ее эффективная реализация On one modification of the Peterson-Gorenstein-Zierler algorithm and its effective realization Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Модификация алгоритма Питерсона—Горенстейна—Цирлера и ее эффективная реализация
spellingShingle	Модификация алгоритма Питерсона—Горенстейна—Цирлера и ее эффективная реализация Фейзиев, Ф.Г. Математическое моделирование и вычислительные методы
title_short	Модификация алгоритма Питерсона—Горенстейна—Цирлера и ее эффективная реализация
title_full	Модификация алгоритма Питерсона—Горенстейна—Цирлера и ее эффективная реализация
title_fullStr	Модификация алгоритма Питерсона—Горенстейна—Цирлера и ее эффективная реализация
title_full_unstemmed	Модификация алгоритма Питерсона—Горенстейна—Цирлера и ее эффективная реализация
title_sort	модификация алгоритма питерсона—горенстейна—цирлера и ее эффективная реализация
author	Фейзиев, Ф.Г.
author_facet	Фейзиев, Ф.Г.
topic	Математическое моделирование и вычислительные методы
topic_facet	Математическое моделирование и вычислительные методы
publishDate	2015
language	Russian
container_title	Электронное моделирование
publisher	Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
format	Article
title_alt	On one modification of the Peterson-Gorenstein-Zierler algorithm and its effective realization
description	Предложена модификация алгоритма Питерсона—Горенстейна—Цирлера на основе метода Гаусса и описан эффективный способ реализации модифицированного алгоритма ускоренного обнаружения и исправления ошибок в принятых двоичных сообщениях. Применены таблицы операций над элементами конечного поля, в которых вместо элемента предложено использовать показатель степени представления выбранного примитивного элемента поля. Приведен алгоритм декодирования принятых двоичных сообщений. Запропоновано модифікацію алгоритма Пітерсона—Горенстейна—Цирлера на основі методу Гауса та описано ефективний спосіб реалізації модифікованого алгоритма прискореного виявлення і виправлення похибок в отриманих двоічних повідомленнях. Застосовано таблиці операцій над елементами кінцевого поля, в яких замість елемента запропоновано використовувати показник ступеня представлення обраного примітивного елемента поля. Наведено алгоритм декодування отриманих двоічних повідомлень. A modification of the Peterson-Gorenstein-Zierler algorithm based on the Gauss method is proposed. The effective method for realization of the modified algorithm is proposed to accelerate the detection and correction of errors in the binary Bose-Chaudhuri-Hocquenghem codes. The tables of operations over the elements of the finite field were used and it was offered to use the exponent of a power of the chosen primitive element representation instead of the element. The detailed description of decoding algorithm of the received messages is given.
issn	0204-3572
url	https://nasplib.isofts.kiev.ua/handle/123456789/101129
citation_txt	Модификация алгоритма Питерсона—Горенстейна—Цирлера и ее эффективная реализация / Ф.Г. Фейзиев // Электронное моделирование. — 2015. — Т. 37, № 3. — С. 3-16 . — Бібліогр.: 5 назв. — рос.
work_keys_str_mv	AT feizievfg modifikaciâalgoritmapitersonagorensteinacirleraieeéffektivnaârealizaciâ AT feizievfg ononemodificationofthepetersongorensteinzierleralgorithmanditseffectiverealization
first_indexed	2025-11-24T16:02:11Z
last_indexed	2025-11-24T16:02:11Z
_version_	1850850397617389568
fulltext	ÓÄÊ 519.95 Ô.Ã. Ôåéçèåâ, ä-ð ôèç.-ìàò. íàóê, Ñóìãàèòñêèé ãîñóíèâåðñèòåò (Àçåðáàéäæàí, AZ-5008, Ñóìãàèò, 43 êâàðòàë, òåë. (+99418) 6483887, å-mail: FeyziyevFG@mail.ru) Ìîäèôèêàöèÿ àëãîðèòìà Ïèòåðñîíà—Ãîðåíñòåéíà—Öèðëåðà è åå ýôôåêòèâíàÿ ðåàëèçàöèÿ Ïðåäëîæåíà ìîäèôèêàöèÿ àëãîðèòìà Ïèòåðñîíà—Ãîðåíñòåéíà—Öèðëåðà íà îñíîâå ìåòîäà Ãàóññà è îïèñàí ýôôåêòèâíûé ñïîñîá ðåàëèçàöèè ìîäèôèöèðîâàííîãî àëãîðèòìà óñêîðåí- íîãî îáíàðóæåíèÿ è èñïðàâëåíèÿ îøèáîê â ïðèíÿòûõ äâîè÷íûõ ñîîáùåíèÿõ. Ïðèìåíåíû òàáëèöû îïåðàöèé íàä ýëåìåíòàìè êîíå÷íîãî ïîëÿ, â êîòîðûõ âìåñòî ýëåìåíòà ïðåäëîæåíî èñïîëüçîâàòü ïîêàçàòåëü ñòåïåíè ïðåäñòàâëåíèÿ âûáðàííîãî ïðèìèòèâíîãî ýëåìåíòà ïîëÿ. Ïðèâåäåí àëãîðèòì äåêîäèðîâàíèÿ ïðèíÿòûõ äâîè÷íûõ ñîîáùåíèé. Çàïðîïîíîâàíî ìîäèô³êàö³þ àëãîðèòìà Ï³òåðñîíà—Ãîðåíñòåéíà—Öèðëåðà íà îñíîâ³ ìåòîäó Ãàóñà òà îïèñàíî åôåêòèâíèé ñïîñ³á ðåàë³çàö³¿ ìîäèô³êîâàíîãî àëãîðèòìà ïðèñêîðåíîãî âèÿâëåííÿ ³ âèïðàâëåííÿ ïîõèáîê â îòðèìàíèõ äâî³÷íèõ ïîâ³äîìëåííÿõ. Çàñòîñîâàíî òàáëèö³ îïåðàö³é íàä åëåìåíòàìè ê³íöåâîãî ïîëÿ, â ÿêèõ çàì³ñòü åëåìåíòà çàïðîïîíîâàíî âèêî- ðèñòîâóâàòè ïîêàçíèê ñòóïåíÿ ïðåäñòàâëåííÿ îáðàíîãî ïðèì³òèâíîãî åëåìåíòà ïîëÿ. Íàâå- äåíî àëãîðèòì äåêîäóâàííÿ îòðèìàíèõ äâî³÷íèõ ïîâ³äîìëåíü. Ê ë þ ÷ å â û å ñ ë î â à: êîäû Áîóçà—×îóäõóðè—Õîêâèíãåìà, àëãîðèòì Ïèòåðñîíà— Ãîðåíñòåéíà—Öèðëåðà, ïðèìèòèâíûé ýëåìåíò êîíå÷íîãî ïîëÿ, ëîêàòîð îøèáîê. Â íàñòîÿùåå âðåìÿ äëÿ çàùèòû äàííûõ â êîìïüþòåðíûõ ñèñòåìàõ è ñåòÿõ øèðîêî ïðèìåíÿþòñÿ ìåòîäû òåîðèè êîäèðîâàíèÿ, êðèïòîãðàôèè è äð. [1—3]. Ýôôåêòèâíûìè ïîìåõîóñòîé÷èâûìè êîäàìè ÿâëÿþòñÿ êîäû Áîóçà—×îóäõóðè—Õîêâèíãåìà (Á×Õ) [1, 3, 4], äëÿ äåêîäèðîâàíèÿ êîòî- ðûõ, ò.å. îáíàðóæåíèÿ è èñïðàâëåíèÿ îøèáêè â ïðèíÿòûõ ñîîáùåíèÿõ, è âûäåëåíèÿ èç íèõ èíôîðìàöèîííûõ ñîîáùåíèé èñïîëüçóþòñÿ ðàçëè÷íûå ìåòîäû è àëãîðèòìû, íàïðèìåð àëãîðèòì Ïèòåðñîíà—Ãîðåíñòåéíà— Öèðëåðà (ÏÃÖ). Ýòîò àëãîðèòì îñíîâàí íà ðåøåíèè ñïåöèàëüíîé ñèñòåìû ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé (ÑËÀÓ) îòíîñèòåëüíî íåèçâåñòíûõ ëîêàòîðîâ îøèáîê ìåòîäîì îáðàùåíèÿ ìàòðèöû. Â ïðåäëàãàåìîé ìîäèôèêàöèè àëãîðèòìà ÏÃÖ âìåñòî ìåòîäà îáðà- ùåíèÿ ìàòðèöû ïðèìåíåí ìåòîä Ãàóññà. Ïîñêîëüêó ýëåìåíòû ìàòðèöû ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 3 3 �� Ô.Ã. Ôåéçèåâ, 2015 ñèñòåìû ñóòü ýëåìåíòû êîíå÷íîãî ïîëÿ [4], ò.å. ìíîãî÷ëåíû, êàæäûé èç êîòîðûõ ÿâëÿåòñÿ ñòåïåíüþ ïðèìèòèâíîãî ýëåìåíòà êîíå÷íîãî ïîëÿ, âû- ïîëíåíèå îïåðàöèé íàä íèìè ìîæíî óñêîðèòü ïîñðåäñòâîì âûïîëíåíèÿ îïåðàöèé íàä ïîêàçàòåëÿìè ñîîòâåòñòâóþùèõ ñòåïåíåé ïðèìèòèâíîãî ýëåìåíòà [1]. Ïîñòàíîâêà çàäà÷è. Ïóñòü � — ïðèìèòèâíûé ýëåìåíò ïîëÿ GF m( )2 [4], ò.å. ýëåìåíò ïîðÿäêà n m� �2 1, ãäå m — çàäàííîå íàòóðàëüíîå ÷èñëî. Äëÿ íàòóðàëüíîãî ÷èñëà t êîä Á×Õ, èñïðàâëÿþùèé t îøèáîê, ÿâëÿåòñÿ öèêëè÷åñêèì êîäîì äëèíû n ñ ïîðîæäàþùèì ìíîãî÷ëåíîì g x( ), ðàâíûì íàèìåíüøåìó îáùåìó êðàòíîìó [ ( ), ( ), ..., ( )]f x f x f xt1 2 2 , ãäå f x�( ) — ìèíè- ìàëüíûé ìíîãî÷ëåí ýëåìåíòà �� GF m( )2 , � �1 2, t. Ïóñòü k n g x� �deg ( ) è i i i ik� �( , , ..., )0 1 1 åñòü k-ìåðíûé ïðîèçâîëüíûé èíôîðìàöèîííûé âåêòîð íàä ïîëåì GF (2). Òîãäà èíôîðìàöèîííûé âåêòîð i ìîæåò áûòü çàêî- äèðîâàí ïîñðåäñòâîì îïåðàöèè c x i x g x( ) ( ) ( )� â êîäîâûé ìíîãî÷ëåí c x c x c x cn n( ) ...� � � �� 1 1 1 0 , ãäå i x i x i x ik k( ) ...� � � �� 1 1 1 0 . Çàìåòèì, ÷òî äëÿ ÷èñåë n, k è t äîëæíî áûòü óäîâëåòâîðåíî ñîîòíîøåíèå 2t n k � [4]. Ïóñòü ïî êàíàëó ñâÿçè ïåðåäàí ìíîãî÷ëåí c x( ), à íà äðóãîì êîíöå ïðèíÿò ìíîãî÷ëåí ( ) ...x x xn n� � � �� 1 1 1 0 . Ïóñòü e x e xn n( ) ...� �� 1 1 ... � �e x e1 0 åñòü ìíîãî÷ëåí îøèáîê, ò.å. e x x c x( ) ( ) ( )� � , GF ( )2 , è íå áî- ëåå t êîýôôèöèåíòîâ ðàâíû åäèíèöå (çäåñü GF ( )2 óêàçûâàåò, ÷òî ìíîãî- ÷ëåíû ( )x è c x( ) ñëàãàþòñÿ íàä ïîëåì GF ( )2 ). Ïðåäïîëîæèì, ÷òî â äàííûé ìîìåíò ïðîèçîøëî � îøèáîê, ãäå 0 � t, è ÷òî ýòèì îøèáêàì ñîîòâåòñòâóþò íåèçâåñòíûå ïîçèöèè p p p1 2, , ..., � . Â ýòîì ñëó÷àå ìíîãî- ÷ëåí îøèáîê e x( ) ìîæíî çàïèñàòü â âèäå e x x xp pv( ) ...� � �1 , ãäå ïîêà- çàòåëè ñòåïåíåé p p p1 2, ,..., � è ÷èñëî v íåèçâåñòíû. Äëÿ îáíàðóæåíèÿ è èñïðàâëåíèÿ îøèáîê íåîáõîäèìî íàéòè ýòè íåèçâåñòíûå. Äëÿ íàõîæäåíèÿ çíà÷åíèé v è p p p1 2, , ..., � â [1] ïðåäëàãàåòñÿ èñïîëü- çîâàòü êîìïîíåíòû ñèíäðîìà S� , � �1 2, t, ãäå S� � �� ( ). Ïîñêîëüêó c x i x g x( ) ( ) ( )� è �� , � �1 2, t, åñòü êîðíè ïîðîæäàþùåãî ìíîãî÷ëåíà g x( ), òî c ( )�� 0, � �1 2, t. Ñ ó÷åòîì ýòîãî ôàêòà ïîëó÷èì ñëåäóþùóþ ôîðìóëó äëÿ îïðåäåëåíèÿ S� , � �1 2, t: S c e e p p p � � � � � � � � � � � � � � �� ( ) ( ) ( ) ( ) ( ) ( ) ... ( )1 2 v � � � � �( ) ( ) ... ( )� � �� p p pv1 2 . (1) Ïðèìèòèâíûé ìíîãî÷ëåí íàä ïîëåì GF( )2 ñòåïåíè m, ñ ïîìîùüþ êîòîðîãî ïîñòðîåíî ïîëå GF m( )2 , îáîçíà÷èì ÷åðåç P x( ). Çàìåòèì, ÷òî â ïîëå GF m( )2 ïðèìèòèâíîìó ýëåìåíòó � ñîîòâåòñòâóåò ìíîãî÷ëåí x [1]. Ô.Ã. Ôåéçèåâ 4 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 3 Ïîýòîìó âìåñòî P x( ) ìîæíî èñïîëüçîâàòü P ( )� . Âû÷èñëåíèÿ S� ïî ôîð- ìóëå (1) ïðîâîäèì íàä ïîëåì GF m( )2 . Ýòî îçíà÷àåò, ÷òî ïîñëå âûïîë- íåíèÿ îïåðàöèé, óêàçàííûõ â ïðàâîé ÷àñòè ðàâåíñòâà, ïîëó÷åííûé ðåçóëü- òàò äåëèì íà ìíîãî÷ëåí P ( )� è áåðåì îñòàòî÷íûé ìíîãî÷ëåí. Èç (1) âèäíî, ÷òî åñëè S� �0, � �1 2, t, òî â ïðèíÿòîì ñîîáùåíèè íåò îøèáîê, â ïðîòèâíîì ñëó÷àå — åñòü îøèáêè (èñêàæåíèÿ). Ïóñòü X a p � �� (ëîêàòîðû îøèáîê), � �1, ..., v. Ïîñêîëüêó ïîðÿäîê ýëå- ìåíòà � ðàâåí n, âñå ëîêàòîðû ðàññìàòðèâàåìîé êîíôèãóðàöèè îøèáîê ðàçëè÷íû. Äëÿ êàæäîãî ��{ , ..., }1 2t èç ôîðìóëû (1) íàõîäèì S� � �� ( ) � � � �X X X v1 2 � � �... . Òàêèì îáðàçîì, ïîëó÷àåì ñëåäóþùóþ ñèñòåìó 2t óðàâ- íåíèé îòíîñèòåëüíî íåèçâåñòíûõ ëîêàòîðîâ îøèáîê X X v1 , ..., : S X X X v� � � �� 1 2 ... , � �1 2, t . (2) Ñèñòåìó íåëèíåéíûõ óðàâíåíèé (2) ðåøàþò êîñâåííûì ïóòåì [1]. Äëÿ ýòîãî èñïîëüçóþò ìíîãî÷ëåí ëîêàòîðîâ îøèáîê � � �( ) ...x x xv v� � � �1 1, êîðíÿìè êîòîðîãî ÿâëÿþòñÿ X � �1, � �1,..., v. Åñëè êîýôôèöèåíòû ìíîãî÷- ëåíà �( )x èçâåñòíû, òî äëÿ âû÷èñëåíèÿ ëîêàòîðîâ îøèáîê íåîáõîäèìî íàéòè åãî êîðíè. Â [1] ïîëó÷åíà ÑËÀÓ, ñâÿçûâàþùàÿ êîìïîíåíòû ñèíä- ðîìà ñ êîýôôèöèåíòàìè ìíîãî÷ëåíà �( )x , êîòîðàÿ èìååò ñëåäóþùèé ìàò- ðè÷íûé âèä: A S S Scol col( , , ..., ) ( , , ..., )� � �� 1 1 2 . (3) Çäåñü A a� ( ),� � , � �1, v, � �1, v, ãäå a S� � �� , � � . Èçâåñòíî, ÷òî åñëè ìàòðèöà A íåâûðîæäåííàÿ, òî ýòà ñèñòåìà èìååò åäèíñòâåííîå ðåøåíèå îòíîñè- òåëüíî � � �1 2, ,..., v . Äîêàçàíî òàêæå [1], ÷òî: 1) åñëè ïðîèçîøëî � îøèáîê, òî ìàòðèöà A — íåâûðîæäåííàÿ; 2) åñëè M S� �( )�� , � ��1, , � ��1, , è åñëè � ðàâíî ÷èñëó � ïðîèçîøåä- øèõ îøèáîê, òî ìàòðèöà M — íåâûðîæäåííàÿ, à åñëè � áîëüøå �, òî ìàòðèöà M — âûðîæäåíà. Íà îñíîâå ýòèõ ôàêòîâ â [1] ïîñòðîåí àëãîðèòì äåêîäèðîâàíèÿ, ñ ïîìîùüþ êîòîðîãî ÑËÀÓ (3) ðåøàåòñÿ îáðàùåíèåì ìàòðèöû A. Îïèøåì ìîäèôèêàöèþ àëãîðèòìà ÏÃÖ íà îñíîâå ìåòîäà Ãàóññà. À ë ã î ð è ò ì 1. Ø à ã 0. Íà îñíîâå ïðèíÿòîãî ìíîãî÷ëåíà ( )x âû÷èñëèòü S� � �� ( ), � �1 2, t , ïî ôîðìóëå (1). Ø à ã 1. � � t. Ø à ã 2. Ïîñòðîèòü ìàòðèöó A a� ( ),� � , � �1, v, � �1, v, ãäå a S� � �� , � � . Åñëè â ìàòðèöå A ñóùåñòâóþò íóëåâûå ñòðîêè è ñòîëáöû, òî ïåðåéòè ê øàãó 4, èíà÷å — ïðèâåñòè ñëåäóþùóþ ñèñòåìó àëãåáðàè÷åñêèõ óðàâíåíèé ê òðåóãîëüíîìó âèäó: A S S Scol col( , ,..., ) ( , ,..., )� � �� 1 1 2 . (4) Ìîäèôèêàöèÿ àëãîðèòìà Ïèòåðñîíà—Ãîðåíñòåéíà—Öèðëåðà ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 3 5 Ø à ã 3. Åñëè â ïðîöåññå ïðèâåäåíèÿ ìàòðèöû A ê òðåóãîëüíîìó âèäó ñòàëî èçâåñòíî, ÷òî A — âûðîæäåííàÿ ìàòðèöà, òî ïåðåéòè ê øàãó 4, â ïðîòèâíîì ñëó÷àå — ê øàãó 5. Ø à ã 4. � �:� �1. Ïåðåéòè ê øàãó 2. Ø à ã 5. Ðåøèòü ñèñòåìó àëãåáðàè÷åñêèõ óðàâíåíèé A1 1col ( , ,...� �� ..., )� � b è îïðåäåëèòü êîýôôèöèåíòû � � � � �, , ..., ìíîãî÷ëåíà �� x , ãäå âåêòîð-ñòîëáåö b ïîëó÷àåòñÿ èç âåêòîðà-ñòîëáöà col ( , , ..., )S S S� � � �� 1 2 â ðåçóëüòàòå ïðèâåäåíèÿ ñèñòåìû (4) ê òðåóãîëüíîìó âèäó; A1 — òðåóãîëü- íûé âèä ìàòðèöû A. Ø à ã 6. Íàéòè êîðíè x x1, ..., � ìíîãî÷ëåíà ëîêàòîðîâ îøèáîê �� x è ëîêàòîðû îøèáîê ïî ôîðìóëå X x� �� 1 , � ��1, ..., . Ø à ã 7. Íàéòè çíà÷åíèÿ èíäåêñîâ p p1 ,..., � è èñïðàâèòü îøèáêè ïî ôîðìóëå p p� � :� �1, � �1,..., �, GF ( )2 . Ø à ã 8. Îïðåäåëèòü èíôîðìàöèîííûé ìíîãî÷ëåí ïî ôîðìóëå i x( ) � � ( ) / ( )x g x . Ø à ã 9. Êîíåö. Ýëåìåíòû ìàòðèöû A â (4) ÿâëÿþòñÿ ýëåìåíòàìè ïîëÿ GF m( )2 , ò.å. ìíîãî÷ëåíàìè íàä ïîëåì GF ( )2 . Êàæäûé íåíóëåâîé ýëåìåíò ïîëÿGF m( )2 ÿâëÿåòñÿ ñòåïåíüþ ïðèìèòèâíîãî ýëåìåíòà. Äëÿ âûïîëíåíèÿ îïåðàöèé ñëîæåíèÿ è óìíîæåíèÿ ýëåìåíòîâ ïîëÿ GF m( )2 ìîæíî èñïîëüçîâàòü ñîîò- âåòñòâóþùèå çàãîòîâëåííûå òàáëèöû, ÷òî ïîçâîëèò ñîêðàòèòü âðåìÿ âû- ïîëíåíèÿ ýòèõ îïåðàöèé. Ýôôåêòèâíàÿ ðåàëèçàöèÿ ïðîöåññà îáíàðóæåíèÿ è èñïðàâëåíèÿ îøèáîê. Ðàññìîòðèì ðåàëèçàöèþ îòäåëüíûõ øàãîâ îïèñàííîãî àëãîðèò- ìà. Ïî îïðåäåëåíèþ ñïðàâåäëèâî: S n n � � �� 0 2 2... ) � � � � � � n n 1 1) . Òîãäà ïî ñõåìå Ãîðíåðà ïîëó÷èì S n n� � � � �� (...(( )1 2 � � � �� n 3 1 0) ... ) . Ïîýòîìó äëÿ íàõîæäåíèÿ S� , � �1 2,..., t, ìîæíî èñïîëüçîâàòü ñëåäóþùèé àëãîðèòì: À ë ã î ð è ò ì 2. Ø à ã 0. S RP n n� � � � : [ ]( )� �� 1 2 , � �1. Ø à ã 1. S R SP n� � � � �� : [ ]( )� � � �2 . Ø à ã 2. � �:� �1. Åñëè n � � �2 0� , òî ïåðåéòè ê øàãó 1, èíà÷å — ê øàãó 3. Ø à ã 3. Êîíåö. Â ýòîì àëãîðèòìå îïåðàòîð RP( ) [� � �� èñïîëüçóåòñÿ äëÿ íàõîæäåíèÿ ìíîãî÷ëåíà îñòàòêà îò äåëåíèÿ ìíîãî÷ëåíà � �� íà ìíîãî÷ëåí P ( )� . Êîì- ïîíåíòû S� , � �1 2,..., t, ïðèíèìàþò çíà÷åíèÿ èç êîíå÷íîãî ïîëÿ GF m( )2 . Ïîýòîìó êàæäûé èç íèõ ÿâëÿåòñÿ ëèáî íóëåâûì ýëåìåíòîì, ëèáî ñòåïåíüþ ïðèìèòèâíîãî ýëåìåíòà �. Ââåäåì ÷èñëà N� , � �1 2, ..., t: N S k S kk m� � � � � � � � � � � � � 1 0 0 2 2 , , , , { , ..., }. åñëè åñëè (5) Ô.Ã. Ôåéçèåâ 6 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 3 Ââåäåì ìàññèâû M1 è M2. Ýëåìåíò M u v1( , , )� ìàññèâà M1, ãäå u GF� ( )2 , v GF� ( )2 è �� { , ..., }0 2 2m , èñïîëüçóåòñÿ äëÿ íàõîæäåíèÿ ïîêà- çàòåëÿ ñòåïåíè ÷èñëà u v�� è îïðåäåëÿåòñÿ ïî ôîðìóëå M u v u v k u v kk 1 1 0 0 ( , , ) , , , , { ,... � � � � � � � � � � � � � åñëè åñëè , }.2 2m � � � � Ýëåìåíò M v2( , )� ìàññèâà M2, ãäå � � � �{ , ,..., }1 0 2 2m è v GF� ( )2 , èñ- ïîëüçóåòñÿ äëÿ íàõîæäåíèÿ ïîêàçàòåëÿ ñòåïåíè ÷èñëà � � �v è îïðåäå- ëÿåòñÿ ïî ôîðìóëå M v v v v 2 0 1 0 1 0 ( , ) , , , , , � � � � � � � � � � � � åñëè åñëè è åñëè è � �� v m, { ,..., }.0 2 2 Ïðè x y m, { , ,..., }� � �1 0 2 2 äëÿ íàõîæäåíèÿ ïîêàçàòåëÿ ñòåïåíè â ïðîèç- âåäåíèÿõ � �x y â âèäå ñòåïåíè ïðèìèòèâíîãî ýëåìåíòà � ïîëÿ GF m( )2 ââåäåì îïåðàöèþ : x y x y= x y x ym� � � � � � � � � � � � � 1 1 1 2 1 1 1 , , ( ), , åñëè èëè åñëè , , , , , . x y x y x y x y m m � � � � � � � � � � � � � � � � 2 1 1 1 2 1åñëè (6) Ïîñòðîèâ ïðåäâàðèòåëüíî ìàññèâû M1 è M2 ñîãëàñíî àëãîðèòìó 2, ìîæíî âû÷èñëèòü N� , � �1 2, t, ñ ïîìîùüþ ñëåäóþùåãî àëãîðèòìà: À ë ã î ð è ò ì 3. Ø à ã 0. N M n n� � : ( , )� � �1 1 2 , � �1. Ø à ã 1. N M N n� � �� : (( )� � � �2 2 . Ø à ã 2. � �:� �1. Åñëè n � � �2 0� , òî ïåðåéòè ê øàãó 1, èíà÷å — ê øàãó 3. Ø à ã 3. Êîíåö. Åñëè ÷èñëà N� , � �1 2, t, âû÷èñëåíû ïî àëãîðèòìó 3, òî S N N k kk m� � �� 0 1 0 2 2 , , , , { , ..., }. åñëè åñëè Ïîýòîìó äàëåå âìåñòî S� , � �1 2,..., t, ìîæíî èñïîëüçîâàòü N� , � �1 2,..., t. Ðàññìîòðèì ïðèâåäåíèå ÑËÀÓ (4) ê òðåóãîëüíîìó âèäó. Äëÿ ýòîãî ââåäåì ìàòðèöó A a� ( ),� � ,� �1, v,� �1, v, è âåêòîð b b bv� ( ,..., )1 : a S� � �� , � � , Ìîäèôèêàöèÿ àëãîðèòìà Ïèòåðñîíà—Ãîðåíñòåéíà—Öèðëåðà ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 3 7 � �1, v, � �1, v; b S v� �� , � �1, v. Íàèìåíüøèé ýëåìåíò ìíîæåñòâà Q � � � �{ \| { , ..., }, }! ! !1 01v a îáîçíà÷èì ÷åðåç �. Â ñëó÷àå � �1ïîìåíÿåì ìåñòà- ìè ïåðâóþ è �-þ ñòðîêè ìàòðèöû A è ïåðâûé è �-é êîìïîíåíòû âåêòîðà b, ò.å. ïðèìåì c a� 1� , a a1� �� , a c�� , � �1, ..., v; c b� 1, b b1 � �, b c� � . Òàêèì îáðàçîì, â ïîëó÷åííîé íîâîé ìàòðèöå A a11 0� . Ê ñòðîêàì ìàòðè- öû A 2, ..., v-é, óìíîæåííûì íà a11, ïðèáàâëÿåì ïåðâóþ ñòðîêó, óìíîæåííóþ ñîîòâåòñòâåííî íà a av21 1, ..., . Çàòåì â âåêòîðå b ê êîìïîíåíòàì 2, ..., v-é, óìíîæåííûì íà a11, ïðèáàâëÿåì ïåðâûå êîìïîíåíòû, óìíîæåííûå ñîîò- âåòñòâåííî íà a av21 1,..., . Òîãäà ïîëó÷èì " � " " " " # $ % % % % & ' ( ( ( ( A a a a a a a a v v v vv 11 12 1 22 2 2 0 0 � � � � � � � , " � " "b b b bvcol( , ,..., )1 2 , ãäå " � �a a a a a�� 11 1 1, � �2,..., v, � �2,..., v ; (7) " � �b b a b a� � �11 1 1, � �2,..., v. (8) Åñëè â ïîäìàòðèöå " � "A a1 ( ),� � , � �2, v, � �2, v, ñóùåñòâóåò íóëåâàÿ ñòðîêà èëè ñòîëáåö, òî ìàòðèöà "A ÿâëÿåòñÿ âûðîæäåííîé, è ïðèâåäåíèå åå ê òðåóãîëüíîìó âèäó ïðåêðàùàåì. Â ïðîòèâíîì ñëó÷àå íàèìåíüøèé ýëå- ìåíò ìíîæåñòâà Q v a2 22 0� � �{ \| { , ..., }, }! ! ! îáîçíà÷èì ÷åðåç �. Â ñëó÷àå � � 2 ïîìåíÿåì ìåñòàìè âòîðóþ è �-þ ñòðîêè ìàòðèöû "A è âòîðîé è �-é êîìïîíåíòû âåêòîðà "b . Â ìàòðèöå "A ê ñòðîêàì 3, ..., v-é, óìíîæåííûì íà "a22, ïðèáàâëÿåì âòîðóþ ñòðîêó, óìíîæåííóþ ñîîòâåòñòâåííî íà " "a av31 1, ..., . Çàòåì, â âåêòîðå "b ê êîìïîíåíòàì 3, ..., v-é, óìíîæåííûì íà "a22, ïðèáàâëÿåì âòîðóþ êîìïîíåíòó, óìíîæåííóþ ñîîòâåòñòâåííî íà " "a av31 1, ..., è òàê äàëåå. Ïðîäîëæàÿ îïèñàííóþ ïðîöåäóðó, ëèáî âûÿñíÿåì, ÷òî ìàòðèöà A — âûðîæäåííàÿ, è ïîýòîìó ïðåêðàùàåì ïðèâåäåíèå åå ê òðåóãîëüíîìó âèäó, ëèáî íà øàãå ( )v �1 ïîëó÷àåì A a a a a a a a a av v v v ( )� � " " " "" ""1 11 12 13 1 22 23 2 33 3 0 0 0 � � � � � � � � �0 0 0 1avv v( )� # $ % % % % % % & ' ( ( ( ( ( ( , b b b b b v v v ( ) ( ) � � � " "" # $ % % % % % % & ' ( ( ( ( ( ( 1 1 2 3 1 � , Ô.Ã. Ôåéçèåâ 8 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 3 ãäå a a a a a�� ( ) ( ) ( ) ( ) ( )� � �� 1 1 1 1 , � � �� 1,..., v, � � �� 1,..., v ; b b a b a� � � ( ) ( ) ( ) ( ) ( )� � �� 1 1 1 1 , � � �� 1,..., v ; � � �2 1,..., v . (9) Â ìàòðèöå A v( )�1 ñóòü a11 0� , " �a22 0, ..., av v v � � � � 1 1 2 0 , ( ) . Åñëè av v v , ( )� �1 0, òî ìàòðèöà A v( )�1 — âûðîæäåííàÿ è ÑËÀÓ íå èìååò ðåøåíèÿ ïðè äàííîì çíà÷åíèè v. Â ñëó÷àå av v v , ( )� �1 0 ðåøåíèå çàäà÷è (4) ñâîäèòñÿ ê ðåøåíèþ çàäà÷è ñ òðåóãîëüíîé ìàòðèöåé: A bv v( ) ( )( , ,..., )� � ��1 1 1col � � �� . (10) Èç ïîñëåäíåãî óðàâíåíèÿ ñèñòåìû (10) îïðåäåëÿåì � ïî ôîðìóëå � � � � �( ), ( ) ( )a bv v v v v1 1 1 . (11) Ó÷èòûâàÿ (11) â ïðåäïîñëåäíåì óðàâíåíèè ñèñòåìû (10) è ðåøàÿ ýòî óðàâíåíèå, îïðåäåëÿåì íåèçâåñòíûé êîýôôèöèåíò �2 è òàê äàëåå. Åñëè � � � � �, , ..., �1 íàéäåíû, òî íåèçâåñòíûé êîýôôèöèåíò �� ìîæíî îïðåäå- ëèòü èç [ ( )]v � �� 1 -ãî óðàâíåíèÿ ñèñòåìû (10): a a av v v v v v v� � � � � � �� , ( ) , ( ) ...� � 2 � � �� , ( ) ( ) v v v vb� � ��1 , (12) ãäå êîýôôèöèåíòû íåèçâåñòíûõ � �� , ..., �1 — íóëåâûå, ïîýòîìó ýòè íåèç- âåñòíûå çäåñü îòñóòñòâóþò. Èç (12) íàõîäèì �� )( ) , ( ) ( ) , a b av v v v v v 1 1 v v � �� + , �� ( ) � , � �2 3, ,..., v. (13) Ôîðìóëû (11), (13) ÿâëÿþòñÿ ðåêóððåíòíûìè ñîîòíîøåíèÿìè äëÿ ðå- øåíèÿ çàäà÷è (10). Â ôîðìóëàõ (7)—(13) îïåðàöèè ïðîâîäÿòñÿ íàä ìíî- ãî÷ëåíàìè. Ðàññìîòðèì ïðåîáðàçîâàíèå ýòèõ ôîðìóë ê ôîðìóëàì, â êîòî- ðûõ âìåñòî ìíîãî÷ëåíà èñïîëüçóþòñÿ ïîêàçàòåëè ñîîòâåòñòâóþùèõ ñòå- ïåíåé ïðèìèòèâíîãî ýëåìåíòà. Äëÿ ýòîãî íà îñíîâå ìàòðèöû A ââåäåì ìàòðèöó Z z� ( )�� , � �1, v, � �1, v, à íà îñíîâå âåêòîðà b — v-ìåðíûé âåêòîð - - -�col ( ,..., )1 v , ãäå z a a m�� 1 0 0 2 2 , , , , { ,..., }, ,åñëè åñëè � � (14) - � � � � � � � � � � � � � � � � 1 0 0 2 2 , , , , { ,..., }. åñëè åñëè b b m (15) Ìîäèôèêàöèÿ àëãîðèòìà Ïèòåðñîíà—Ãîðåíñòåéíà—Öèðëåðà ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 3 9 Èñïîëüçóÿ (5) ìîæíî îïðåäåëèòü z� �, , � �1, v, � �1, v, è -� , � �1, v, ñ ïîìîùüþ ôîðìóë z N� � �� , � è -� �� N . Íà îñíîâå ìàòðèöû Z v( )�1 è âåêòîðà -( )v�1 ââåäåì ñëåäóþùèå ìàòðèöû è âåêòîðû: Z z z z z z z z z zv v v v ( )� � � " " " � � "" ""1 11 12 13 1 22 23 2 33 3 1 1 1 � � � � � � # $ % % % % % % & ' ( ( ( ( ( (�1 1 1 1 � zvv v( ) , - - - - - ( ) ( ) v v v � � � " "" # $ % % % % % % & ' ( ( ( ( ( ( 1 1 2 3 1 � , ãäå z a a � � � � � � �� , ( ) ( ) ( ) , , , , { ,. � � � � � � � � 1 0 0 åñëè åñëè .., },2 2m � � � � �� 1,..., v, � � �� 1,..., v, (16) - � � � � � � � � � � � � � � � � � � � � � � 1 0 0 2 , , , , { ,..., åñëè åñëè b b m 2}, � � � �� 1,..., v, (17) � �1 1,..., v � . Èñïîëüçóÿ ïðèìèòèâíûé ýëåìåíò �, ôîðìóëû (7), (8) ñ ó÷åòîì (14) è (15) ìîæíî çàïèñàòü â âèäå � � � � �� " � � z z z z z 11 1 1 , � � � � �- - -� � �" � �z z 11 1 1 , îòêóäà âûòåêàåò " � � �z MC z z z z� � � � � �, ( , )11 1 1 , � �2, v, � �2, v, (18) " � � �- - -� � �MC z z( , )11 1 1 , � �2, v, (19) ãäå MC x y( , ) — çíà÷åíèå ïîêàçàòåëÿ ñóììû � �x y� , MC x y y x x y x y( , ) , , , , , , , � � � � � � � åñëè = 1 åñëè åñëè 1 1 0� � � åñëè � � � ��x y m� � � � � � � � � � � , { ,..., }.0 2 2 Àíàëîãè÷íî ïî ôîðìóëàì (18), (19) íà îñíîâå (9) è (16), (17) ïîëó÷àåì z MC z z z z�� ( ) ( ) ( ) ( ) ( )( , )� � �� 1 1 1 1 , � � �� 1,..., v, - - -� � � ( ) ( ) ( ) ( ) ( )( , )� � �� MC z z1 1 1 1 , � � �� 1,..., v, � �1 1, ..., v � . Ñîñòàâèâ ïðåäâàðèòåëüíî ìàññèâ MC x y( , ) äëÿ âñåõ x y GF m, ( )� 2 , ñ ïî- ìîùüþ (11), (13) ((18), (19) ) ìîæíî âû÷èñëèòü "z� �, è "-� (z� � ( )� è -� ( )� ) áûñòðåå ÷åì "a� �, è "b� (a� � ( )� è b� ( )� ). Ô.Ã. Ôåéçèåâ 10 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 3 . . . . . . . . . . . . . . . . . . . . . Äëÿ êàæäîãî � �{ , , ..., }1 2 v ââåäåì îáîçíà÷åíèå . � � � � � � � � � � � � � � � � �� 1 0 0 2 2 , , , , { ,..., }. åñëè åñëè � � m Èç (11) ïîëó÷èì . - � � � �� ( )( ) ( )2 1 1 1m vv v v vz , ãäå ìíîæèòåëü 2 1 1m vv vz� � �( ) ñâè- äåòåëüñòâóåò î òîì, ÷òî åñëè avv v zvv v( ) ( )� � �1 1 � , òî ( )( ) ( ) avv v zm vv v� � � �� 1 1 2 1 1 � . Äåéñò- âèòåëüíî, � � �z q zvv v m vv v m( ) ( )� �� 1 11 2 1 1. Â ïðàâîé ÷àñòè (13) âûðàæåíèå J av v v � � � �� ) 1 1 1( ) � ìîæíî âû÷èñëèòü ðåêóððåíòíî: J� :�0; J J av v v � � �� : ( )� � � � � � , � � � �1 1, ..., � . Ïîýòîìó åñëè J� �� , òî ïîêàçàòåëü �� òàêæå ìîæåò áûòü îïðåäåëåí ðåêóððåíòíî: � � �� : ; : ( , )( )� � � �� 1 MC zv v v . , � �� 1 1, ..., . Ñëåäîâàòåëüíî, ñîãëàñíî (13) . - �� ( ) ( , )( ) ( )2 1 1m v v v v vz MC . Ïîñëå îïðåäåëåíèÿ êîýôôèöèåíòîâ � � � � �, , ..., ìíîãî÷ëåíà �( )x äëÿ îïðåäåëåíèÿ êîðíåé íåîáõîäèìî âû÷èñëèòü �( )x äëÿ êàæäîãî ýëåìåíòà x GF m� ( )2 è âûäåëèòü òå çíà÷åíèÿ x, ïðè êîòîðûõ �( )x ðàâíî íóëþ. Íà îñíîâå ñõåìû Ãîðíåðà �( )x âû÷èñëÿåòñÿ ðåêóððåíòíî â òàêîé ïîñëåäî- âàòåëüíîñòè: �0 1: ,� � � �( ) :x xv v� � �1, � � �( ) : ( )x x x� � � , � � � �v v2 1 0, ,..., . (20) Äëÿ óñêîðåíèÿ âû÷èñëåíèÿ âìåñòî x ìîæíî èñïîëüçîâàòü åãî îïèñàíèå â âèäå x �� . Òîãäà ñõåìó (20) çàïèøåì â âèäå . . � . �� / �� : , ( ): (( )� � �0 MC v . , . � . � �� ( ): (( ( ) ),� �MC . � � � � �v v2 1 0, , ..., , ãäå . �� ( , ( , , ( , { ,..., � � � � � � 1 0 0 2 åñëè åñëè � � � � m 2}. � � � Ìîäèôèêàöèÿ àëãîðèòìà Ïèòåðñîíà—Ãîðåíñòåéíà—Öèðëåðà ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 3 11 Ïî îïðåäåëåíèþ äëÿ êàæäîãî � �1,..., v p X X m� � � � � � � � � � � � 1 0 0 2 2 , , , , { ,..., }. åñëè åñëè� � �� Ýôôåêòèâíîñòü ïðåäëîæåííûõ ìåòîäèê. Ïîñêîëüêó âñå âû÷èñëå- íèÿ ñâÿçàíû ñ ýëåìåíòàìè ìàòðèöû A a� ( ),� � , � �1, v, � �1, v, è âåêòîðà b b bv� ( ,..., )1 , ãäå �� , � � �S 1 è b S� � �� , ñîãëàñíî ôîðìóëå (1) ìîæíî ïîëàãàòü, ÷òî âñå óêàçàííûå ýëåìåíòû ñóòü ìíîãî÷ëåíû îò ïðèìèòèâíîãî ýëåìåíòà �, èìåþùèå ñòåïåíü ìåíüøå m. Ñëåäîâàòåëüíî, îíè òàêæå ÿâ- ëÿþòñÿ ýëåìåíòàìè ïîëÿ GF m( )2 . Ïóñòü � �( ), 0 �( ) ( )� GF m2 è � � � � � � �( ) ...� � � �� 1 0, 0 �( ) � � � � �0 � 0 � 0r r ... 1 0, ãäå �, r m� . Ïóñòü h h h hr r( ) ...� � �� 1 0 è åå êîýôôèöèåíòû îïðåäåëÿþòñÿ ïî ôîðìóëå h j j! � � ! � 0� � ) ( , ) 1 , GF ( )2 , ãäå 1! � � !2� � �{( , )\|j j . Äëÿ âû÷èñëåíèÿ âñåõ êîýôôèöèåíòîâ h ( )� íåîáõîäèìî âûïîëíåíèå îïåðàöèé óìíîæåíèÿ è ñëîæåíèÿ â êîëè÷åñòâå 2 0! ! � � ) � r \| \|1 , ãäå \| \|1! — ÷èñëî ýëåìåíòîâ â ìíîæåñòâå 1!. Ïî îïðåäåëåíèþ êîýôôèöèåíòîâ âèäíî, ÷òî ìíîãî÷ëåí h ( )� ñóòü îáû÷íîå ïðîèçâåäåíèå ìíîãî÷ëåíîâ � �( ) è 0 �( ), à ñòåïåíü h ( )� ìîæåò áûòü ìåíüøå r ��. Ïðîèçâåäåíèå � �( ) è 0 �( ) íàä ïîëåì GF m( )2 îïðå- äåëÿåòñÿ ïî ôîðìóëå � � 0 � ��( ) ( ) [ ( )]( )� R hP . Íàõîäèì ÷èñëî îïåðàöèé äëÿ âû÷èñëåíèÿ R hP( ) [ ( )]� � . Ïðåäïîëîæèì, ÷òî P P P Pm m( ) ...� � �� 1 0, ãäå Pm �1, è ðåàëüíàÿ ñòåïåíü ìíîãî÷ëåíà h ( )� åñòü N. Åñëè N m� , òî ïðè äåëåíèè íà ìíîãî÷ëåí P ( )� ïîëó÷åííûé îñòàòî÷íûé ìíîãî÷ëåí åñòü h ( )� , ñëåäîâàòåëüíî, � � 0 � �( ) ( ) ( )� h . Åñëè N íå ìåíüøå m, òî äëÿ äåëåíèÿ h ( )� íà P ( )� ìîæíî èñïîëüçîâàòü ñëå- äóþùèå ðåêóððåíòíûå ñîîòíîøåíèÿ: y h� �[ ]0 � , � �0 1, ,..., N ; (21) y y y PN N N m� � � � � � � � �� 1 1 11 1� � � � � �� [ ] [ ] [ ] ,� �1,..., ,m GF ( )2 , y yN N� � � � � �� 1 1 1� � � �� [ ] [ ], � �� m N1 1,..., , � � �1 2, ,..., N m ; (22) y N m y N m y N m Pm m m m� � �� [ ] [ ] [ ] ,1 � �1,..., ,m GF ( )2 . (23) Ô.Ã. Ôåéçèåâ 12 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 3 Ïîñëå çàâåðøåíèÿ âû÷èñëåíèÿ êîýôôèöèåíòû îñòàòî÷íîãî ìíîãî÷ëåíà ñ óáûâàþùåé ïîñëåäîâàòåëüíîñòüþ çíà÷åíèé èíäåêñîâ ÿâëÿþòñÿ çíà÷åíèÿìè ýëåìåíòîâ ñîîòâåòñòâåííî y N m y N m y N mm m� �� 1 2 01 1 1[ ], [ ], ..., [ ] . Ñîãëàñíî (21) òðåáóåòñÿ KO N1 1� � îïåðàöèé òèïà ïðèñâàèâàíèå. Â (22) ïåðâàÿ è âòîðàÿ ôîðìóëû âûïîëíÿþòñÿ âìåñòå öèêëè÷åñêè N m� ðàç. Â ïåðâîé ôîðìóëå åñòü äâå îïåðàöèè. Ó÷èòûâàÿ, ÷òî ïåðâàÿ ôîðìóëà â îòäåëüíîñòè âûïîëíÿåòñÿ öèêëè÷åñêè m ðàç, ïîëó÷àåì 2m îïåðàöèé. Âòî- ðàÿ ôîðìóëà âûïîëíÿåòñÿ öèêëè÷åñêè N m� � �1 � ðàç, è êàæäûé ðàç âûïîë- íÿåòñÿ îäíà îïåðàöèÿ ïðèñâàèâàíèÿ, ïîýòîìó âñåãî ïîëó÷àåì N m� � �1 � îïåðàöèé. Òàêèì îáðàçîì, äëÿ (21) ÷èñëî âûïîëíÿåìûõ îïåðàöèé ñîñòàâëÿåò KO m N m m N N m NN m N m 2 1 1 2 2 2 1 1 3 2 � � � � � � � � � � � � � � � � ) ) � � � �( ) ( ) m N m� � 2 . Ñîãëàñíî (23) âû÷èñëåíèÿ ïðîâîäÿòñÿ öèêëè÷åñêè m ðàç, è êàæäûé ðàç âûïîëíÿþòñÿ äâå îïåðàöèè. Ñëåäîâàòåëüíî, òðåáóåòñÿ KO m3 2� îïå- ðàöèé. Òàêèì îáðàçîì, äëÿ äåëåíèÿ h ( )� íà P ( )� òðåáóåòñÿ ÊÎD îïåðàöèé: KO KO KO KO N m N m Nm N m D � � � � � � � � � � � 2 2 2 2 2 1 2 3 2 2 . ×èñëî îïåðàöèé äëÿ âû÷èñëåíèÿ � � 0 � ��( ) ( ) [ ( )]( )� R hP ñîñòàâèò KO N m N m N m Nm r r � � � � � � � � � � � ) ) 2 2 1 2 3 2 0 0 2 2 ! ! ! ! � � \| \|, , \| \| 1 1 � � 3 � � � � � � � N m N m 2 , , îòêóäà âèäíî, ÷òî äëÿ âû÷èñëåíèÿ ïðîèçâåäåíèÿ � �( ) è 0 �( ) íàä ïîëåì GF m( )2 òðåáóåòñÿ âûïîëíåíèå áîëüøåãî ÷èñëà îïåðàöèé. Òåïåðü ïðåäïîëîæèì, ÷òî � � �( ) � � è 0 � �( ) � r . Òîãäà äëÿ âû÷èñëå- íèÿ ïðîèçâåäåíèÿ � ( )x è 0 ( )x íàä ïîëåì GF m( )2 ìîæíî èñïîëüçîâàòü îïåðàöèþ �� r, îïðåäåëåííóþ ôîðìóëîé (6). Ýòà îïåðàöèÿ ïðîâîäèòñÿ íà îñíîâå ïðåäâàðèòåëüíî ñîñòàâëåííîé ñîîòâåòñòâóþùåé òàáëèöû. Ñëåäî- âàòåëüíî, èñïîëüçóÿ çíà÷åíèÿ � è r, ñ ïîìîùüþ îäíîãî ïîäõîäÿùåãî îïåðàòîðà ÿçûêà ïðîãðàììèðîâàíèÿ èç òàáëèöû ìîæíî âûáðàòü ïîêàçà- òåëü ñòåïåíè �, ñîîòâåòñòâóþùèé � � 0 � ��( ) ( ) [ ( )]( )� R hP . Òàêèì îáðà- çîì, íàìíîãî áûñòðåå âû÷èñëÿåòñÿ � � 0 � ��( ) ( ) [ ( )]( )� R hP . Ñëåäóåò çà- ìåòèòü, ÷òî, êðîìå íóëåâîãî ýëåìåíòà, âñå ìíîãî÷ëåíû íàä GF m( )2 ìîãóò Ìîäèôèêàöèÿ àëãîðèòìà Ïèòåðñîíà—Ãîðåíñòåéíà—Öèðëåðà ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 3 13 áûòü ïðåäñòàâëåíû â âèäå � !, ãäå 0 ! n , à â âû÷èñëåíèÿõ äëÿ íóëåâîãî ýëåìåíòà ôîðìàëüíî èñïîëüçóåòñÿ ïîêàçàòåëü ñòåïåíè – 1. Àíàëîãè÷íî ìîæíî ïîêàçàòü, ÷òî èñïîëüçîâàíèå ïðåäâàðèòåëüíî ñîñ- òàâëåííûõ òàáëèö, îñíîâàííûõ íà çíà÷åíèè ïîêàçàòåëÿ ñòåïåíè ïðèìè- òèâíîãî ýëåìåíòà, ìîæåò ïðèâåñòè ê ìíîãîêðàòíîìó óìåíüøåíèþ âðåìå- íè âûïîëíåíèÿ ñëîæåíèÿ ýëåìåíòîâ íàä ïîëåì GF m( )2 . Àëãîðèòì îáíàðóæåíèÿ è èñïðàâëåíèÿ îøèáîê â ïðèíÿòîì ìíî- ãî÷ëåíå. Ïðåäïîëîæèì, ÷òî ìàññèâû (òàáëèöû) M1, M2, MC ïðåäâàðè- òåëüíî ñîñòàâëåíû. Òîãäà àëãîðèòì äåêîäèðîâàíèÿ ìîæíî ïðåäñòàâèòü â ñëåäóþùåì âèäå: À ë ã î ð è ò ì 4. Ø à ã 0. Âûáðàòü n n� �1 2 1 0, , ..., , . Ïðèíÿòü � � 1. Ø à ã 1. N M n n� � � � �1 1 2( , , ) , � �1. Ø à ã 2. N M N n� � �� : (( ), )� � � �2 2 . Ø à ã 3. �4 �� 1. Åñëè n � � �2 0� , òî ïåðåéòè ê øàãó 2, èíà÷å — ê øàãó 4. Ø à ã 4. �4 �� 1. Åñëè � 2t, òî ïåðåéòè ê øàãó 1, èíà÷å — ê øàãó 5. Ø à ã 5. Åñëè ÷èñëà N N N t1 2 2, , ..., ðàâíû – 1, òî ïåðåéòè ê øàãó 36, èíà÷å — ê øàãó 6. Ø à ã 6. v t� . Ø à ã 7. Ïîñòðîèòü ìàòðèöó D z� ( ),� � , � �1, v, � �1, v, ãäå z N� � � �, � � �1 , � �1, v, � �1, v. Ïîñòðîèòü âåêòîð -��- - -1 2, ,..., )v , ãäå -� � �� N , � �1, v. Ø à ã 8. � �1. Ø à ã 9. Åñëè â ìàòðèöå D z1 � ( ),� � , � � �, v, � � �, v, ñóùåñòâóþò íóëåâûå ñòðîêè è ñòîëáöû, òî ïåðåéòè ê øàãó 19, èíà÷å íàéòè � ! ! !� � � �min{ \| { ,..., }, }� �1 1z . Åñëè � � �, òî ïåðåéòè ê øàãó 10, èíà÷å — ê øàãó 13. Ø à ã 10. � � �. Ø à ã 11. Ïîñëåäîâàòåëüíî ïðèíèìàòü: c z� �,� , z z�, ,� � �� , z c� �, � . Ø à ã 12. �4 � � � . Åñëè � � , òî ïåðåéòè ê øàãó 11, èíà÷å ïðèíèìàòü ïîñëåäîâàòåëüíî c � -� , - -�� , -� � c è ïåðåéòè ê øàãó 13. Ø à ã 13.� � �� 1. Åñëè� 3 �, òî ïåðåéòè ê øàãó 18, èíà÷å — ê øàãó 14. Ø à ã 14. � � �. Ø à ã 15. z MC z z z z� � � � � �, , , ,: ( , )� � �� . Ø à ã 16.�4 � � � . Åñëè� � , òî ïåðåéòè ê øàãó 15, èíà÷å — ïðèíèìàòü - - -� � �: ( , ), ,� � �MC z z� � � � è ïåðåéòè ê øàãó 17. Ø à ã 17.� 4 � � � . Åñëè� � , òî ïåðåéòè ê øàãó 14, èíà÷å — ê øàãó 18. Ø à ã 18. � �4 � � . Åñëè � �, òî ïåðåéòè ê øàãó 9, èíà÷å — ê øàãó 20. Ø à ã 19. v v4 � � . Ïåðåéòè ê øàãó 7. Ô.Ã. Ôåéçèåâ 14 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 3 Ø à ã 20. . -1 2 1� � � �( )m vv vz . Ø à ã 21. � 4�2 . Ø à ã 22. � 4� �1; � �1. Ø à ã 23. � � .� � � ��: ( ),� �� MC zv v1 1 . Ø à ã 24.� 4 � � � . Åñëè� � � , òî ïåðåéòè ê øàãó 23, èíà÷å — ê øàãó 25. Ø à ã 25. . - �� : ( ) ( , ),� � � �� 2 1 1 1 1 m v v vz MC . Ø à ã 26.� 4 � � � . Åñëè� � , òî ïåðåéòè ê øàãó 23, èíà÷å — ê øàãó 27. Ø à ã 27. � � � , . 0 0� , � �0. Ø à ã 28. . �� . �� .�: (( )� � �MC v 1 , � � �v 2. Ø à ã 29. . �� . �� .: (( ( )� �MC � . Ø à ã 30. v v4 � � . Åñëè � � 0, òî ïåðåéòè ê øàãó 29, èíà÷å — ê øàãó 31. Ø à ã 31. Åñëè . �� 1, òî ïåðåéòè ê øàãó 33, èíà÷å — ê øàãó 32. Ø à ã 32. � 4 � � � , x� �� . Åñëè � � v, òî ïåðåéòè ê øàãó 34, èíà÷å — ê øàãó 33. Ø à ã 33.�4 �� . Åñëè� �2 2m , òî ïåðåéòè ê øàãó 28, èíà÷å — ê øàãó 34. Ø à ã 34. Äëÿ êàæäîãî � �1,..., v îïðåäåëèòü p� ïî ôîðìóëå p xm � �� 2 1 . Ø à ã 35. Ïðèíèìàòü: p p� � :� �1, GF ( )2 , � �1,..., v. Ø à ã 36. Äåëèòü ìíîãî÷ëåí ( )x íà ìíîãî÷ëåí g x g xn k n k( ) ...� �� ... � �g x g1 0 ïî ñëåäóþùåé ñõåìå [5]: y� � [ ]0 � , � � �0 1 1, ,..., n , y y y gn n n n k� � � � � � �� [ ] [ ] [ ]1 , � � �1,..., n k, GF ( )2 , y yn n� � � �� [ ] [ ]1 , � �� n k n1,..., ; I yk n� �� [ ] [ ]1 , � � �1 2 1, ,..., k ; y k y k y k gn k n k n k n k� � � � � � �� [ ] [ ] [ ]1 , � � �1,..., n k, GF ( )2 ; I k y ko n k[ ] [ ]� �� 1 . Ø à ã 37. Îïðåäåëèòü êîìïîíåíòû èíôîðìàöèîííîãî âåêòîðà ïî ôîðìóëå i Ik k� �� [ ], � �1 2, ,..., k. Ø à ã 38. Êîíåö. Âûâîäû Òàêèì îáðàçîì, íà îñíîâå ìåòîäà Ãàóññà è èñïîëüçîâàíèÿ ñïåöèàëüíûõ òàáëèö äîñòèãíóòî óñêîðåíèå âûïîëíåíèÿ àëãîðèòìà ÏÃÖ äëÿ îáíàðó- æåíèÿ è èñïðàâëåíèÿ îøèáîê â ïðèíÿòîì ìíîãî÷ëåíå. Ýòîò àëãîðèòì ìîæíî ðåàëèçîâàòü ïðîãðàììíî íà ÿçûêå Àññåìáëåð. Ìîäèôèêàöèÿ àëãîðèòìà Ïèòåðñîíà—Ãîðåíñòåéíà—Öèðëåðà ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2015. Ò. 37. ¹ 3 15 ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Áëåéõóò Ð. Òåîðèÿ è ïðàêòèêà êîäîâ, êîíòðîëèðóþùèõ îøèáêè. — Ì. : Ìèð, 1986. — 576 ñ. 2. Èâàíîâ Ì.À. Êðèïòîãðàôè÷åñêèå ìåòîäû çàùèòû èíôîðìàöèè â êîìïüþòåðíûõ ñèñ- òåìàõ è ñåòÿõ. — Ì. : Êóäèö-îáðàç, 2001. — 368 ñ. 3. William C.H., Vera P. Fundamentals of Error-Correcting Codes. — Cambridge University Press, 2003. — 662 p. 4. Áèðêãîô Ã., Áàðòè Ò. Ñîâðåìåííàÿ ïðèêëàäíàÿ àëãåáðà. — Ì. : Ìèð, 1976. — 400 ñ. 5. Ôåéçèåâ Ô.Ã., Ìåãðäàä Áàáàâàíä. Îïèñàíèå äåêîäèðîâàíèÿ öèêëè÷åñêèõ êîäîâ â êëàññå ïîñëåäîâàòåëüíîñòíûõ ìàøèí, îñíîâàííîãî íà òåîðåìå Ìåããèòòà// Àâòîìà- òèêà è âû÷èñëèòåëüíàÿ òåõíèêà. — 2012. — ¹ 4. — Ñ. 26—33. F.G. Feyziyev ON ONE MODIFICATION OF THE PETERSON-GORENSTEIN-ZIERLER ALGORITHM AND ITS EFFECTIVE REALIZATION A modification of the Peterson-Gorenstein-Zierler algorithm based on the Gauss method is pro- posed. The effective method for realization of the modified algorithm is proposed to accelerate the detection and correction of errors in the binary Bose-Chaudhuri-Hocquenghem codes. The ta- bles of operations over the elements of the finite field were used and it was offered to use the ex- ponent of a power of the chosen primitive element representation instead of the element. The de- tailed description of decoding algorithm of the received messages is given. K e y w o r d s: Bose-Choudhuri-Hockwinham code, Peterson-Gorenstein-Zierler algorithms, primitive element of finite field, error locator. REFERENCES 1. Bleikhut, R. (1986), Teoriya i praktika kodov kontroliruyushchikh oshibki [Theory and prac- tice of codes controlling errors], Mir, Moscow, Russia. 2. Ivanov, Ì.À. (2001), Kriptograficheskie metody zashchity informatsii v kompyuternykh sistemakh i setyakh [Cryptographic methods of information protection in computer systems and networks], Kudits-obraz, Moscow, Russia. 3. William, C.H. and Vera, P. (2003), Fundamentals of Error-Correcting Codes, Cambridge Uni- versity Press, Cambridge, U.K. 4. Birkgof, G. and Barti, T. (1976), Sovremennaya prikladnaya algebra [Modern applied alge- bra], Mir, Moscow, Russia. 5. Feyziyev, F.G. and Megrdad Babavand (2012), “Description of decoding of cyclic codes in the klass of successeve machines based on Meggitt theorem”, Avtomatika i vychislitelnaya tekhnika, no. 4, pp. 26-33. Ïîñòóïèëà 06.11.14 ÔÅÉÇÈÅÂ Ôèêðàò Ãþëàëè îãëû, ä-ð ôèç.-ìàò. íàóê, ïðîôåññîð, çàâ. êàôåäðîé «Äèôôåðåí- öèàëüíûå óðàâíåíèÿ è îïòèìèçàöèÿ» Ñóìãàèòñêîãî ãîñóíèâåðñèòåòà. Â 1978 ã. îêîí÷èë Àçåð- áàéäæàíñêèé ãîñóíèâåðñèòåò. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ìàòåìàòè÷åñêàÿ êèáåðíå- òèêà, òåîðèÿ êîíå÷íûõ àâòîìàòîâ è òåîðåòè÷åñêèå âîïðîñû èíôîðìàòèêè. Ô.Ã. Ôåéçèåâ 16 ISSN 0204–3572. Electronic Modeling. 2015. V. 37. ¹ 3

Модификация алгоритма Питерсона—Горенстейна—Цирлера и ее эффективная реализация

Institution

Ähnliche Einträge