Модификация метода Питерсона—Горенстейна—Цирлера приведением матрицы к треугольному виду (двоичный случай)
Сформулирована теорема о числе ошибок в принятых сообщениях при передаче по каналам связи двоичных кодов Боуза—Чоудхури—Хоквингема (БЧХ). Для обнаружения и исправления произошедших ошибок в двоичных кодах БЧХ предложена модификация метода Питерсона—Горенстейна—Цирлера, основанная на приведении матри...
Збережено в:
| Опубліковано в: : | Электронное моделирование |
|---|---|
| Дата: | 2016 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2016
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/115838 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Модификация метода Питерсона—Горенстейна—Цирлера приведением матрицы к треугольному виду (двоичный случай) / Ф.Г. Фейзиев, М.Р. Мехтиева, З.А. Самедова // Электронное моделирование. — 2016. — Т. 38, № 5. — С. 11-21. — Бібліогр.: 6 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-115838 |
|---|---|
| record_format |
dspace |
| spelling |
Фейзиев, Ф.Г. Мехтиева, М.Р. Самедова, З.А. 2017-04-14T09:15:34Z 2017-04-14T09:15:34Z 2016 Модификация метода Питерсона—Горенстейна—Цирлера приведением матрицы к треугольному виду (двоичный случай) / Ф.Г. Фейзиев, М.Р. Мехтиева, З.А. Самедова // Электронное моделирование. — 2016. — Т. 38, № 5. — С. 11-21. — Бібліогр.: 6 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/115838 519.725 Сформулирована теорема о числе ошибок в принятых сообщениях при передаче по каналам связи двоичных кодов Боуза—Чоудхури—Хоквингема (БЧХ). Для обнаружения и исправления произошедших ошибок в двоичных кодах БЧХ предложена модификация метода Питерсона—Горенстейна—Цирлера, основанная на приведении матрицы к треугольному виду. Разработана методика ускорения вычисления согласно этой модификации. Приведен алгоритм декодирования принятых сообщений на основе предложенной модификации. Сформульовано теорему про число похибок в прийнятих повідомленнях при передачі по каналах зв’язку двоічних кодів Боуза—Чоудхурі—Хоквінгема (БЧХ). Для виявлення та виправлення похибок, що сталися, в двоічних кодах БЧХ запропоновано модифікацію методу Пітерсона—Горенстейна—Цирлера, базовану на приведенні матриці до трикутної форми. Розроблено методику прискорення обчислень згідно з цією модифікацією. Наведено алгоритм декодування прийнятих повідомлень на базі запропонованої модифікації. The theorem on the number of errors, which occurred in the received messages in the case of transmission of the binary Bose-Chaudhuri-Hocquenghem codes over communication channels, has been formulated. A modification of the Peterson-Gorenstein-Zierler method, based on the reduction of the matrix to triangular form, for detecting and correcting errors in the binary Bose-Chaudhuri-Hocquenghem codes has been proposed. The technique has been developed for accelerating calculation in accordance with this modification. A detailed description of the algorithm of decoding the received messages based on the above modifications and techniques is given. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Математическое моделирование и вычислительные методы Модификация метода Питерсона—Горенстейна—Цирлера приведением матрицы к треугольному виду (двоичный случай) Modification of Peterson-Gorenstein-Zierler Method, Bringing the Matrix to Triangular Form (Binary Case) 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 |
2016 |
| language |
Russian |
| container_title |
Электронное моделирование |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| format |
Article |
| title_alt |
Modification of Peterson-Gorenstein-Zierler Method, Bringing the Matrix to Triangular Form (Binary Case) |
| description |
Сформулирована теорема о числе ошибок в принятых сообщениях при передаче по каналам связи двоичных кодов Боуза—Чоудхури—Хоквингема (БЧХ). Для обнаружения и исправления произошедших ошибок в двоичных кодах БЧХ предложена модификация метода Питерсона—Горенстейна—Цирлера, основанная на приведении матрицы к треугольному виду. Разработана методика ускорения вычисления согласно этой модификации. Приведен алгоритм декодирования принятых сообщений на основе предложенной модификации.
Сформульовано теорему про число похибок в прийнятих повідомленнях при передачі по каналах зв’язку двоічних кодів Боуза—Чоудхурі—Хоквінгема (БЧХ). Для виявлення та виправлення похибок, що сталися, в двоічних кодах БЧХ запропоновано модифікацію методу Пітерсона—Горенстейна—Цирлера, базовану на приведенні матриці до трикутної форми. Розроблено методику прискорення обчислень згідно з цією модифікацією. Наведено алгоритм декодування прийнятих повідомлень на базі запропонованої модифікації.
The theorem on the number of errors, which occurred in the received messages in the case of transmission of the binary Bose-Chaudhuri-Hocquenghem codes over communication channels, has been formulated. A modification of the Peterson-Gorenstein-Zierler method, based on the reduction of the matrix to triangular form, for detecting and correcting errors in the binary Bose-Chaudhuri-Hocquenghem codes has been proposed. The technique has been developed for accelerating calculation in accordance with this modification. A detailed description of the algorithm of decoding the received messages based on the above modifications and techniques is given.
|
| issn |
0204-3572 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/115838 |
| citation_txt |
Модификация метода Питерсона—Горенстейна—Цирлера приведением матрицы к треугольному виду (двоичный случай) / Ф.Г. Фейзиев, М.Р. Мехтиева, З.А. Самедова // Электронное моделирование. — 2016. — Т. 38, № 5. — С. 11-21. — Бібліогр.: 6 назв. — рос. |
| work_keys_str_mv |
AT feizievfg modifikaciâmetodapitersonagorensteinacirleraprivedeniemmatricyktreugolʹnomuvidudvoičnyislučai AT mehtievamr modifikaciâmetodapitersonagorensteinacirleraprivedeniemmatricyktreugolʹnomuvidudvoičnyislučai AT samedovaza modifikaciâmetodapitersonagorensteinacirleraprivedeniemmatricyktreugolʹnomuvidudvoičnyislučai AT feizievfg modificationofpetersongorensteinzierlermethodbringingthematrixtotriangularformbinarycase AT mehtievamr modificationofpetersongorensteinzierlermethodbringingthematrixtotriangularformbinarycase AT samedovaza modificationofpetersongorensteinzierlermethodbringingthematrixtotriangularformbinarycase |
| first_indexed |
2025-11-26T19:04:15Z |
| last_indexed |
2025-11-26T19:04:15Z |
| _version_ |
1850769068202655744 |
| fulltext |
ÓÄÊ 519.725
Ô.Ã. Ôåéçèåâ, ä-ð ôèç.-ìàò. íàóê
Ñóìãàèòñêèé ãîñóíèâåðñèòåò
(Àçåðáàéäæàí, AZ5008, Ñóìãàèò, 43 êâàðòàë, óë. Áàêó, 1,
òåë.(+994018) 6448906, e-mail: FeyziyevFG@mail.ru),
Ì.Ð. Ìåõòèåâà, êàíä. ôèç.-ìàò. íàóê
Áàêèíñêèé ãîñóíèâåðñèòåò
(Àçåðáàéäæàí, AZ1148, Áàêó, óë. Àêàäåìèêà Çàõèäà Õàëèëîâà, 23,
òåë.(+994012) 5390535),
Ç.À. Ñàìåäîâà, ä-ð ôèëîñîôèè ïî ìàòåìàòèêå
Àçåðáàéäæàíñêèé óíèâåðñèòåò ÿçûêîâ
(Àçåðáàéäæàí, AZ1014, Áàêó, óë. Ðàøèäà Áåõáóäîâà, 134,
òåë.(+994012) 4412278, å-mail: zamina68@hotmail.com)
Ìîäèôèêàöèÿ ìåòîäà
Ïèòåðñîíà—Ãîðåíñòåéíà—Öèðëåðà ïðèâåäåíèåì
ìàòðèöû ê òðåóãîëüíîìó âèäó (äâîè÷íûé ñëó÷àé)
Ñôîðìóëèðîâàíà òåîðåìà î ÷èñëå îøèáîê â ïðèíÿòûõ ñîîáùåíèÿõ ïðè ïåðåäà÷å ïî
êàíàëàì ñâÿçè äâîè÷íûõ êîäîâ Áîóçà—×îóäõóðè—Õîêâèíãåìà (Á×Õ). Äëÿ îáíàðóæåíèÿ
è èñïðàâëåíèÿ ïðîèçîøåäøèõ îøèáîê â äâîè÷íûõ êîäàõ Á×Õ ïðåäëîæåíà ìîäèôèêàöèÿ
ìåòîäà Ïèòåðñîíà—Ãîðåíñòåéíà—Öèðëåðà, îñíîâàííàÿ íà ïðèâåäåíèè ìàòðèöû ê òðå-
óãîëüíîìó âèäó. Ðàçðàáîòàíà ìåòîäèêà óñêîðåíèÿ âû÷èñëåíèÿ ñîãëàñíî ýòîé ìîäèôèêà-
öèè. Ïðèâåäåí àëãîðèòì äåêîäèðîâàíèÿ ïðèíÿòûõ ñîîáùåíèé íà îñíîâå ïðåäëîæåííîé
ìîäèôèêàöèè.
Ñôîðìóëüîâàíî òåîðåìó ïðî ÷èñëî ïîõèáîê â ïðèéíÿòèõ ïîâ³äîìëåííÿõ ïðè ïåðåäà÷³ ïî
êàíàëàõ çâ’ÿçêó äâî³÷íèõ êîä³â Áîóçà—×îóäõóð³—Õîêâ³íãåìà (Á×Õ). Äëÿ âèÿâëåííÿ òà
âèïðàâëåííÿ ïîõèáîê, ùî ñòàëèñÿ, â äâî³÷íèõ êîäàõ Á×Õ çàïðîïîíîâàíî ìîäèô³êàö³þ ìå-
òîäó ϳòåðñîíà—Ãîðåíñòåéíà—Öèðëåðà, áàçîâàíó íà ïðèâåäåíí³ ìàòðèö³ äî òðèêóòíî¿
ôîðìè. Ðîçðîáëåíî ìåòîäèêó ïðèñêîðåííÿ îá÷èñëåíü çã³äíî ç ö³ºþ ìîäèô³êàö³ºþ. Íàâå-
äåíî àëãîðèòì äåêîäóâàííÿ ïðèéíÿòèõ ïîâ³äîìëåíü íà áàç³ çàïðîïîíîâàíî¿ ìîäèô³êàö³¿.
Ê ë þ ÷ å â û å ñ ë î â à: äâîè÷íûå êîäû Áîóçà—×îóäõóðè—Õîêâèíãåìà, ìåòîä Ïèòåð-
ñîíà—Ãîðåíñòåéíà—Öèðëåðà, òðåóãîëüíûå ìàòðèöû, ïðèìèòèâíûé ýëåìåíò êîíå÷íîãî
ïîëÿ, ëîêàòîð îøèáîê.
Êîäû Áîóçà—×îóäõóðè—Õîêâèíãåìà (Á×Õ) ÿâëÿþòñÿ ýôôåêòèâíûìè ïî-
ìåõîóñòîé÷èâûìè êîäàìè [1—4]. Êîä Á×Õ ñòðîèòñÿ äëÿ çàäàííîãî íàòó-
ðàëüíîãî ÷èñëà, êîòîðîå ïðåäñòàâëÿåò ñîáîé ìàêñèìàëüíîå ÷èñëî èñïðàâ-
ëÿåìûõ îøèáîê. Äëÿ äåêîäèðîâàíèÿ êîäîâ Á×Õ, ò.å. îáíàðóæåíèÿ îøèáîê
â ïðèíÿòûõ ñîîáùåíèÿõ, èõ èñïðàâëåíèÿ è âûäåëåíèÿ èç íèõ èíôîðìà-
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 5 11
� Ô.Ã. Ôåéçèåâ, Ì.Ð. Ìåõòèåâà, Ç.À. Ñàìåäîâà, 2016
öèîííûõ ñîîáùåíèé, èñïîëüçóþòñÿ ðàçëè÷íûå ìåòîäû, íàïðèìåð ìåòîä
Ïèòåðñîíà—Ãîðåíñòåéíà—Öèðëåðà (ÏÃÖ) [1]. Ýòîò ìåòîä îñíîâàí íà ðå-
øåíèè ñïåöèàëüíîé ñèñòåìû ëèíåéíûõ àëãåáðàè÷åñêèõ óðàâíåíèé (ÑËÀÓ)
îòíîñèòåëüíî íåèçâåñòíûõ ëîêàòîðîâ îøèáîê ñ ïðèìåíåíèåì îáðàùåíèÿ
ìàòðèöû.
 ðàáîòå [5] ïðåäëîæåíà ìîäèôèêàöèÿ àëãîðèòìà ÏÃÖ, â êîòîðîé äëÿ
ðåøåíèÿ ÑËÀÓ âìåñòî ìåòîäà îáðàùåíèÿ ìàòðèöû ïðèìåíåí ìåòîä Ãàóñ-
ñà.  ìîäèôèêàöèè ìåòîäà ÏÃÖ, êàê è â ñàìîì ìåòîäå ÏÃÖ, ÷èñëî ïðîèçî-
øåäøèõ îøèáîê ïðåäïîëàãàåòñÿ ðàâíûì ìàêñèìàëüíî âîçìîæíîìó ÷èñëó
�îøèáîê. Çàòåì ñòðîèòñÿ ÑËÀÓ ñ �íåèçâåñòíûìè è ïðîâåðÿåòñÿ, èìååò ëè
îíà ðåøåíèå. Åñëè íåò, òî èç ÷èñëà îøèáîê âû÷èòàåòñÿ åäèíèöà. Ñíîâà
ñòðîèòñÿ ÑËÀÓ è ïðîâåðÿåòñÿ, èìååò ëè îíà ðåøåíèå, è òàê äàëåå.
 ïðåäëàãàåìîé íîâîé ìîäèôèêàöèè ìåòîäà ÏÃÖ íàõîæäåíèå ÷èñëà
îøèáîê îñóùåñòâëÿåòñÿ áåç èõ ïîñëåäîâàòåëüíîãî âûáîðà è ïðîâåðêè.
Ïîñòàíîâêà çàäà÷è. Ïóñòü m — çàäàííîå íàòóðàëüíûå ÷èñëî, � —
ïðèìèòèâíûé ýëåìåíò ïîëÿ GF m( )2 [4], ò.å. ýëåìåíò ïîðÿäêà n m� �2 1 ,
P x( ) — ïðèìèòèâíûé ìíîãî÷ëåí íàä ïîëåì GF ( )2 ñòåïåíè m, ñ ïîìîùüþ
êîòîðîãî ïîñòðîåíî ïîëå GF m( )2 . Â ïîëå GF m( )2 ïðèìèòèâíîìó ýëåìåí-
òó � ñîîòâåòñòâóåò ìíîãî÷ëåí x [1].
Ðàññìîòðèì êîä Á×Õ, èñïðàâëÿþùèé ìàêñèìóì � îøèáîê, êîòîðûé
ÿâëÿåòñÿ öèêëè÷åñêèì êîäîì äëèíû n ñ ïîðîæäàþùèì ìíîãî÷ëåíîì g x( ).
Ïóñòü 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 è � äîëæíî áûòü óäîâëåòâîðåíî ñîîòíîøåíèå 2� � �n k [4].
Ïóñòü ïî êàíàëó ñâÿçè ïåðåäàí ìíîãî÷ëåí c x( ), íà äðóãîì êîíöå ïðèíÿò
ìíîãî÷ëåí � � � �( ) ...x x xn
n� � � ��
�
1
1
1 0, à e x e x e x en
n( ) ...� � � ��
�
1
1
1 0 åñòü
ìíîãî÷ëåí îøèáîê è íå áîëåå � êîýôôèöèåíòîâ ðàâíû åäèíèöå. Ïðåäïîëî-
æèì, ÷òî â äàííûé ìîìåíò ïðîèçîøëî v îøèáîê, ãäå 0� �v �, è ÷òî ýòèì
îøèáêàì ñîîòâåòñòâóþò íåèçâåñòíûå ïîçèöèè p p pv1 2, , ..., .  ýòîì ñëó÷àå
e x x xp pv( ) ...� � �1 , ãäå ïîêàçàòåëè ñòåïåíåé p p pv1 2, ,..., è ÷èñëî v ïðîèçî-
øåäøèõ îøèáîê íåèçâåñòíû. Äëÿ îáíàðóæåíèÿ è èñïðàâëåíèÿ îøèáîê
íåîáõîäèìî íàéòè ýòè íåèçâåñòíûå. Äëÿ èõ íàõîæäåíèÿ èñïîëüçóþòñÿ
êîìïîíåíòû ñèíäðîìà S S1 2, ...,
�
, ãäå [1]
S c e e p p p
� � � � � � � �� � � � � � � �( ) ( ) ( ) ( ) ( ) ( ) ... ( )1 2 v . (1)
Âû÷èñëåíèÿ S ïî ôîðìóëå (1) ïðîâîäÿòñÿ íàä ïîëåì GF m( )2 . Ýòî
îçíà÷àåò, ÷òî ïîñëå âûïîëíåíèÿ îïåðàöèé, óêàçàííûõ â ïðàâîé ÷àñòè ðà-
âåíñòâà, ïîëó÷åííûé ðåçóëüòàò äåëèòñÿ íà ìíîãî÷ëåí P ( )� è áåðåòñÿ
Ô.Ã. Ôåéçèåâ, Ì.Ð. Ìåõòèåâà, Ç.À. Ñàìåäîâà
12 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 5
îñòàòî÷íûé ìíîãî÷ëåí. Èç ôîðìóëû (1) âèäíî, ÷òî åñëè S �0, �1 2, �, òî â
ïðèíÿòîì ñîîáùåíèè îøèáîê íåò, â ïðîòèâíîì ñëó÷àå — îøèáêè (èñêà-
æåíèÿ) åñòü.
Ïóñòü X j
pj�� (ëîêàòîðû îøèáîê), j v�1, ..., . Ïîñêîëüêó ïîðÿäîê ýëå-
ìåíòà � ðàâåí n, âñå ëîêàòîðû ðàññìàòðèâàåìîé êîíôèãóðàöèè îøèáîê
ðàçëè÷íû. Äëÿ êàæäîãî �1 2, ..., � èç ôîðìóëû (1) ïîëó÷àåì ñëåäóþùóþ
ñèñòåìó èç 2� óðàâíåíèé îòíîñèòåëüíî íåèçâåñòíûõ ëîêàòîðîâ îøèáîê
X X v1 , ..., :
S X X X v
� � � �
1 2
... , �1 2, � . (2)
Äëÿ ðåøåíèÿ ñèñòåì íåëèíåéíûõ óðàâíåíèé (2) èñïîëüçóåòñÿ ìíîãî÷-
ëåí ëîêàòîðîâ îøèáîê
( ) ...x x xv
v� � � �1 1, êîðíÿìè êîòîðîãî ÿâëÿþò-
ñÿ X
�
�1, � �1, ..., v [1]. Åñëè êîýôôèöèåíòû ìíîãî÷ëåíà
( )x èçâåñòíû, òî
äëÿ âû÷èñëåíèÿ ëîêàòîðîâ îøèáîê íåîáõîäèìî íàéòè åãî êîðíè. ÑËÀÓ,
ñâÿçûâàþùàÿ êîìïîíåíòû ñèíäðîìà ñ êîýôôèöèåíòàìè ìíîãî÷ëåíà
( )x ,
èìååò ñëåäóþùèé ìàòðè÷íûé âèä [1]:
A S S Sv v v v vcol col( , , ..., ) ( , , ..., )
� � ��1 1 1 2 2 . (3)
Çäåñü A a� ( ),� , � �1, v, �1, v, ãäå a S� ��� , � � . Åñëè ìàòðèöà A — íåâû-
ðîæäåííàÿ, òî ýòà ñèñòåìà èìååò åäèíñòâåííîå ðåøåíèå îòíîñèòåëüíî
1 2, , ..., v .
Äëÿ îáíàðóæåíèÿ è èñïðàâëåíèÿ îøèáîê ñíà÷àëà íàõîäèì ÷èñëî ïðîè-
çîøåäøèõ îøèáîê. Çàòåì óòî÷íÿåì èõ êîîðäèíàòû, ò.å. íàõîäèì íîìåðà
êîìïîíåíòîâ ïðèíÿòîãî ñëîâà, êîòîðîå èìååò îøèáêè, è âíîñèì â íèõ
êîððåêòèâû. Îïðåäåëåíèå ÷èñëà ïðîèçîøåäøèõ îøèáîê òðåáóåò äîñòà-
òî÷íî ìíîãî âðåìåíè. ×åì áûñòðåå îïðåäåëÿåòñÿ ÷èñëî ïðîèçîøåäøèõ
îøèáîê, òåì ýôôåêòèâíåå ìåòîä äåêîäèðîâàíèÿ.
Èçâåñòíî, ÷òî åñëè M S� �( )��� ,�
�1, ,
�1, , è åñëè
� v, òî ìàòðèöà
M — íåâûðîæäåííàÿ, à åñëè
� v, òî ìàòðèöà M — âûðîæäåíà [1]. Â
ïðåäëàãàåìîé ìîäèôèêàöèè ìåòîäà ÏÃÖ, íà îñíîâå ýòîãî ôàêòà è âèäà
ìàòðèöû À ñôîðìóëèðîâàíà òåîðåìà î ÷èñëå ïðîèçîøåäøèõ îøèáîê â
ïðèíÿòûõ ñîîáùåíèÿõ.
Ìîäèôèêàöèÿ ìåòîäà ÏÃÖ. Êîìïîíåíòû S S1 2, ...,
�
âû÷èñëÿåì ïî
ñëåäóþùåìó àëãîðèòìó.
À ë ã î ð è ò ì 1 [5].
Øàã 0. S RP n n �
� � �: [ ]( )� �� �1 2 , � �1.
Øàã 1. S RP n n �
�� � �: [ ]( )� �� � �1 2 .
Øàã 2. � � � �� 1. Åñëè n� � �2 0� , òî ïåðåéòè ê øàãó 1, èíà÷å — ê øàãó 3.
Øàã 3. Êîíåö.
Ìîäèôèêàöèÿ ìåòîäà Ïèòåðñîíà—Ãîðåíñòåéíà—Öèðëåðà ïðèâåäåíèåì ìàòðèöû
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 5 13
 ýòîì àëãîðèòìå îïåðàòîð RP( ) [ (� � ��� èñïîëüçóåòñÿ äëÿ íàõîæäåíèÿ
ìíîãî÷ëåíà îñòàòêà îò äåëåíèÿ ìíîãî÷ëåíà � ��( íà ìíîãî÷ëåí P (��.
Íåòðóäíî äîêàçàòü ñëåäóþùèå òåîðåìû.
Òåîðåìà 1. Ïóñòü M a� ( ),� ,�� �1, � , ãäå a S� � , � � �1 . Ïóñòü ìàòðèöà
M ñ ïîìîùüþ ýëåìåíòàðíûõ îïåðàöèé íàä ñòðîêàìè ïðèâîäèòñÿ ê ïîëó-
òðåóãîëüíîìó âèäó
M
d d d d d
d d d d
k k
k k
�
�
�
11 12 1 1 1 1
22 2 2 1 20
0 0
� �
� �
� � � � � � �
�
�
�
,
,
d d d
d d
d
kk k k k
k k k
k
,
, ,
,
�
� � �
�
1
1 1 1
1
0 0 0
0 0 0
�
� �
� � � � � � �
� �
�
�
�
d
��
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
�
,
ãäå dii � 0, i k�1, , è âåêòîð-ñòîëáåö d d dk k k� � � �col ( ,..., ), ,1 1 1�
ñóòü íóëåâîé
âåêòîð-ñòîëáåö. Òîãäà ïðè ïåðåäà÷å èíôîðìàöèè ÷èñëî ïðîèçîøåäøèõ
îøèáîê ðàâíî k.
Òåîðåìà 2. Ïóñòü ïðè ïåðåäà÷å èíôîðìàöèè ÷èñëî ïðîèçîøåäøèõ îøè-
áîê åñòü v è ÑËÀÓ (3) èìååò òðåóãîëüíûé âèä A v vcol ( , ,
�1 ..., )
1 � b, ãäå
A
d d d d
d d d
d
v
v
vv
�
�
�
�
�
�
�
�
�
�
�
�
�
11 12 13 1
22 23 20
0 0 0
�
�
� � � � �
�
, b v�col ( , ..., )� �1 .
Òîãäà ðåøåíèå ÑËÀÓ (3) îòíîñèòåëüíî
1 2, , ..., v ìîæíî ïðåäñòàâèòü â
âèäå ñëåäóþùèõ ðåêóððåíòíûõ ñîîòíîøåíèé:
1
1� �( )dvv v� ,
� � � �
�
�
� � � ��� �� � � �
�
� �
�
�
� � � � � ��( ), ,d dv v v v v1 1
1
1
1
1
1 1 �
!
"
#
$
%
, � �2 3, ,..., v.
Íà îñíîâå òåîðåì 1 è 2, èñïîëüçóÿ ìåòîäèêó ïðèâåäåíèÿ ìàòðèöû ê òðå-
óãîëüíîé ôîðìå, ìîäèôèêàöèþ ìåòîäà ÏÃÖ ìîæíî îïèñàòü ñ ïîìîùüþ
ñëåäóþùåãî àëãîðèòìà.
À ë ã î ð è ò ì 2.
Ø à ã 0. Èñïîëüçóÿ ïðèíÿòîå çíà÷åíèå � ( )x , âû÷èñëèòü S
� �� ( ),
�1 2, �, ïî ôîðìóëå (1). Åñëè âñå ÷èñëà S S1 2, ...,
�
ðàâíû íóëþ, òî ïåðåéòè
ê øàãó 10, èíà÷å — ê øàãó 1.
Ô.Ã. Ôåéçèåâ, Ì.Ð. Ìåõòèåâà, Ç.À. Ñàìåäîâà
14 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 5
Ø à ã 1. Ïîñòðîèòü ìàòðèöó A a� ( ),� ,�� �1, �, è âåêòîð b b b�col ( , ..., )1 �
,
ãäå a S� ��� , � � ,�� �1, �; b S v� ��� ,� �1, �. Ïðèíÿòü j �1è ïåðåéòè ê øàãó 2.
Ø à ã 2. Åñëè j � �1 �, òî ïðèíÿòü v �1 è ïåðåéòè ê øàãó 7, èíà÷å
íàèìåíüøèé ýëåìåíò ìíîæåñòâàQ j a j� & �{ | { , ..., }, }' ' '� 0 îáîçíà÷èòü ÷å-
ðåç �.  ñëó÷àå� � j ïîìåíÿòü ìåñòàìè j-þ è �-þ ñòðîêè ìàòðèöû A è j-é è
�-é êîìïîíåíòû âåêòîðà b, ò.å. ïðèíÿòü ïîñëåäîâàòåëüíî: c a j� , a aj � � ,
a c� � , � j, ..., �; c b j� , b bj � �, b c� � . Ïðèíÿòü v j� �1. Åñëè v � �, òî ïå-
ðåéòè ê øàãó 3, èíà÷å — ê øàãó 5.
Ø à ã 3. Óìíîæèòü j-þ ñòðîêó ìàòðèöû A íà a avj jj/ è ïðèáàâèòü ê v-é
ñòðîêå:
a a a a av v vj jj j : ( / )� � , � j, ..., �. (4)
Óìíîæèòü j-þ êîìïîíåíòó âåêòîðà b íà a avj jj/ è ïðèáàâèòü ê v-é êîìïî-
íåíòå âåêòîðà b:
b b a a bv v vj jj j: ( / )� � . (5)
Ø à ã 4. Ïðèíÿòü v v:� �1. Åñëè v � � , òî ïåðåéòè ê øàãó 3, èíà÷å — ê
øàãó 5.
Ø à ã 5. Åñëè j � �1 �, òî ïðèíÿòü v j� è ïåðåéòè ê øàãó 7, èíà÷å —
ïðîâåðèòü âåêòîð-ñòîëáåö d a a aj j j j j� � � � � �col ( , , ..., ), , ,1 1 2 1 1�
. Åñëè îí ñóòü
íóëåâîé âåêòîð-ñòîëáåö, òî ïðèíÿòü v j� è ïåðåéòè ê øàãó 7, èíà÷å — ê
øàãó 6.
Ø à ã 6. Ïðèíÿòü j j:� �1. Åñëè j( �, òî ïåðåéòè ê øàãó 2, èíà÷å
ïðèíÿòü v j� è ïåðåéòè ê øàãó 7.
Ø à ã 7. Ðåøèòü ÑËÀÓ A v vcol ( , ,
�1 ..., )
1 � b è îïðåäåëèòü êîýôôè-
öèåíòû
1 2, , ..., v ìíîãî÷ëåíà
( )x ïî ôîðìóëàì
1
1� �( )a bvv v , (6)
� � � �
�
�
� � � �� �� � � �
�
� �
�
�
� � � � � ��( ), ,a b av v v v v1 1
1
1
1
1
1 1 �
!
"
#
$
%
, � �2 3, , ..., v, (7)
ãäå A a� ( ),� , �� �1, v, è b b bv�col ( , ..., )1 .
Ø à ã 8. Íàéòè êîðíè ìíîãî÷ëåíà ëîêàòîðîâ îøèáîê ïî ôîðìóëå
X x � �1, �1, v .
Ø à ã 9. Íàéòè çíà÷åíèÿ èíäåêñîâ p pv1 , ..., è èñïðàâèòü îøèáêè ïî
ôîðìóëå � �
p p:� �1, � 1, ..., v, GF ( )2 .
Ø à ã 10. Îïðåäåëèòü èíôîðìàöèîííûé ìíîãî÷ëåí ïî ôîðìóëå i x( ) �
�� ( ) / ( )x g x .
Ø à ã 11. Êîíåö.
Ìîäèôèêàöèÿ ìåòîäà Ïèòåðñîíà—Ãîðåíñòåéíà—Öèðëåðà ïðèâåäåíèåì ìàòðèöû
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 5 15
Ìåòîäèêà óñêîðåíèÿ âû÷èñëåíèÿ â ìîäèôèêàöèè ìåòîäà ÏÃÖ.
Ýëåìåíòû ìàòðèöû A â (3) åñòü ýëåìåíòû ïîëÿ GF m( )2 , ò.å. îíè ÿâëÿþòñÿ
ìíîãî÷ëåíàìè íàä ïîëåì GF ( )2 . Íåíóëåâûå ýëåìåíòû ïîëÿ GF m( )2 ÿâëÿ-
þòñÿ ñòåïåíüþ ïðèìèòèâíîãî ýëåìåíòà. Äëÿ âûïîëíåíèÿ îïåðàöèé ñëîæåíèÿ
è óìíîæåíèÿ ýëåìåíòîâ ïîëÿ GF m( )2 ìîæíî èñïîëüçîâàòü ñîîòâåòñòâóþùèå
òàáëèöû, ÷òî ïîçâîëèò ñîêðàòèòü âðåìÿ âûïîëíåíèÿ ýòèõ îïåðàöèé.
Êîìïîíåíòû S S1 2, ...,
�
ïðèíèìàþò çíà÷åíèÿ èç êîíå÷íîãî ïîëÿ GF m( )2 .
Ïîýòîìó îíè ÿâëÿþòñÿ 0 (íóëåâûì ýëåìåíòîì) èëè ñòåïåíüþ ïðèìèòèâ-
íîãî ýëåìåíòà �. Ââåäåì ÷èñëà N N1 2, ...,
�
:
N
S
k S kk m
�
�
� �
� & �
!
"
1 0
0 2 2
, ,
, , { , ..., }.
åñëè
åñëè
Ââåäåì ìàññèâû 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 ïðè x y m, { , , ..., }& � �1 0 2 2 â âèäå ñòåïåíè ïðèìèòèâíîãî ýëåìåíòà �
ïîëÿ GF m( )2 ââåäåì îïåðàöèþ +:
x y
x y
x y xm+ �
� � � �
� � � � �
�� åñëè = 1 èëè (è)
åñëè
1
2 1 1
,
( ), , , ,
, , , .
y x y
x y x y x y
m
m
� � � � �
� � � � � � ( �
!
*
"
*
1 2 1
1 1 2 1åñëè
Åñëè ïðåäâàðèòåëüíî ïîñòðîåíû ìàññèâû M1 è M2, òî àíàëîãè÷íî ïî
àëãîðèòìó 1 ìîæíî âû÷èñëèòü N N1 2, ...,
�
. Åñëè ÷èñëà N , �1 2, �, âû÷èñ-
ëåíû ïî àëãîðèòìó 1, òî
S
N
N k kk m
�
�
� �
� & �
!
0 1
0 2 2
, ,
, , { , ..., }.
åñëè
åñëè ãäå"
Ïîýòîìó â äàëüíåéøåì âìåñòî S S1 2, ...,
�
ìîæíî èñïîëüçîâàòü N N1 2, ...,
�
.
Ô.Ã. Ôåéçèåâ, Ì.Ð. Ìåõòèåâà, Ç.À. Ñàìåäîâà
16 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 5
 ôîðìóëàõ (4)—(7) îïåðàöèè ïðîâîäÿòñÿ íàä ìíîãî÷ëåíàìè. Ðàñ-
ñìîòðèì ïðåîáðàçîâàíèå ýòèõ ôîðìóë ê ôîðìóëàì, â êîòîðûõ âìåñòî
ìíîãî÷ëåíà èñïîëüçóþòñÿ ïîêàçàòåëè ñîîòâåòñòâóþùèõ ñòåïåíåé ïðèìè-
òèâíîãî ýëåìåíòà. Äëÿ ýòîãî íà îñíîâå ìàòðèöû A è âåêòîðà b ââåäåì
ìàòðèöó Z z� ( )� , � �1, v, �1, v è âåêòîð , , ,�col ( , ..., )1 v , ãäå
z
a
a m�
�
�
�� �� �
�
� �
& �
1 0
0 2 2
, ,
, , { , ..., }
åñëè
åñëè ãäå ,
!
"
(8)
,
� �� �
�
�
�
�
�
� �
& �
!
1 0
0 2 2
, ,
, , { , ..., }.
åñëè
åñëè ãäå
b
b m
"
(9)
Èñïîëüçóÿ ïðèìèòèâíûé ýëåìåíò �� ìîæíî çàïèñàòü ôîðìóëû (4) è (5)
ñ ó÷åòîì (8) è (9) â âèäå
� � � � � z z z z zv v vj jj j: ( / )� � , (10)
� � � � �, , ,
v v vj jj jz z
: ( / )� � . (11)
Îòñþäà
z MC z z z zv v
m
jj vj j : ( , ( ) )� � � + +2 1 , (12)
, , ,v v
m
jj vj jMC z z: ( , ( ) )� � � + +2 1 , (13)
ãäå MC x y( , ) — çíà÷åíèå ïîêàçàòåëÿ ñóììû � �x y� ,
MC x y
y x
x y
x y( , )
,
,
, ,
,
�
� �
� �
� � �
�
�
� �
)
åñëè
åñëè
åñëè
1
1
1 0
åñëè = ãäå� � � ))x y m� & �
!
*
*
"
*
* , { , ..., }.0 2 2
Äëÿ êàæäîãî �&{ , , ..., }1 2 v ââåäåì îáîçíà÷åíèå
-
� �� �
�
�
�
�
�
� �
& �
!
1 0
0 2 2
, ,
, , { , ..., }.
åñëè
åñëè ãäå
m
"
(14)
Íà îñíîâå (8)—(14) ìîæíî çàïèñàòü ôîðìóëû (6) è (7) ñîîòâåòñòâåííî
â âèäå
- ,1
1 12 1� � � +� �( )( ) ( )m
vv
v
v
vz , (15)
- , �� � � �
�
�� � � +� � � �
�
� �
�( ) ( , )
,
( ) ( )2 1
1 1
1
1
m
v v
v
v
vz MC , � �2 3, , ..., v. (16)
Ìîäèôèêàöèÿ ìåòîäà Ïèòåðñîíà—Ãîðåíñòåéíà—Öèðëåðà ïðèâåäåíèåì ìàòðèöû
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 5 17
Ìíîæèòåëü 2 1 1m
vv
vz� � �( ) â ïðàâîé ÷àñòè (15) óêàçûâàåò íà òî, ÷òî åñëè
avv
v zvv
v( ) ( )� �
�1 1
� , òî ( )( ) ( )
avv
v zm
vv
v� � � ��
�1 1 2 1 1
� , à â ïðàâîé ÷àñòè ôîðìóëû (16) ��
îïðåäåëÿåòñÿ ðåêóððåíòíî:
�� :� �1; � � -� � � � �
�
� �: ( , )
,
( )� +� � � � �
�
�MC zv v
v
1 1
, � �� �1 1, ..., .
Äëÿ îïðåäåëåíèÿ êîðíåé ìíîãî÷ëåíà
( )x ïîñëå îïðåäåëåíèÿ êîýô-
ôèöèåíòîâ
1 2, , ..., v äëÿ êàæäîãî ýëåìåíòà x GF m& ( )2 íàäî âû÷èñëèòü
( )x è âûäåëèòü òå çíà÷åíèÿ x, ïðè êîòîðûõ
( )x ðàâíî íóëþ. Íà îñíîâå ñõå-
ìû Ãîðíåðà
( )x âû÷èñëÿåòñÿ ðåêóððåíòíî â òàêîé ïîñëåäîâàòåëüíîñòè:
.:� �1,
( ) :x xv v� � �1,
( ) : ( )x x x� � ', ' � � �v v2 3 0, , ..., . (17)
Äëÿ óñêîðåíèÿ âû÷èñëåíèÿ âìåñòî x ìîæíî èñïîëüçîâàòü åãî îïèñàíèå â
âèäå x �� . Òîãäà ñõåìó (17) çàïèøåì â âèäå
-. :�0 , - ( ) : (( ) - �� -� + �MC v v 1 ,
- -( ) : (( ( ) ) �� -'� +MC , ' � � �v v2 3 0, , ..., .
Çäåñü
-
�
� � �� �
�
( )
, ( ) ,
, ( ) , { ,...,
�
� �
&
1 0
0
åñëè
åñëè ãäå
2 2m �
!
" }.
Ïî îïðåäåëåíèþ äëÿ êàæäîãî � �1, ..., v
p
X
X m'
'
'
�� � � �
�
� �
& �
!
1 0
0 2 2
, ,
, , { , ..., }.
åñëè
åñëè ãäå"
Àëãîðèòì îáíàðóæåíèÿ è èñïðàâëåíèÿ îøèáîê â ïðèíÿòîì ìíî-
ãî÷ëåíå. Ïðåäïîëîæèì, ÷òî ìàññèâû (òàáëèöû) M1, M2, MC ïðåäâàðè-
òåëüíî ñîñòàâëåíû. Òîãäà àëãîðèòì äåêîäèðîâàíèÿ ñëåäóþùèé.
À ë ã î ð è ò ì 3.
Ø à ã 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. � �:� �1. Åñëè n� � �2 0� , òî ïåðåéòè ê øàãó 2, èíà÷å — ê øàãó 4.
Ø à ã 4. :� �1. Åñëè � 2�, òî ïåðåéòè ê øàãó 1, èíà÷å — ê øàãó 5.
Ø à ã 5. Åñëè âñå ÷èñëà N N N1 2 2, , ...,
�
ðàâíû – 1, òî ïåðåéòè ê øàãó 35,
èíà÷å — ê øàãó 6.
Ø à ã 6. Ïîñòðîèòü ìàòðèöó D z� ( )� , � � 1, �, �1, �, ãäå z N� ���� � ,
� �1, �, �1, �. Ïîñòðîèòü âåêòîð ,�/, , ,1 2, , ..., )
�
, ãäå ,� ��� N
�
, � �1, �.
Ô.Ã. Ôåéçèåâ, Ì.Ð. Ìåõòèåâà, Ç.À. Ñàìåäîâà
18 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 5
Ïðèíÿòü j �1. Åñëè j � �1 �, òî ïðèíÿòü v �1è ïåðåéòè ê øàãó 19, èíà÷å ïå-
ðåéòè ê øàãó 7.
Ø à ã 7. Íàéòè � ' ' '� & � �min{ | { , ..., }, }j z j� 1 . Åñëè � � j, òî ïðèíÿòü
� j è ïåðåéòè ê øàãó 8, èíà÷å — ê øàãó 10.
Ø à ã 8. Ïîñëåäîâàòåëüíî ïðèíÿòü: c z j� , z aj � � , z c� � .
Ø à ã 9. :� �1. Åñëè � �, òî ïåðåéòè ê øàãó 8, èíà÷å ïðèíÿòü ïîñëå-
äîâàòåëüíî c j�, , , ,�j � , ,� � c è ïåðåéòè ê øàãó 10.
Ø à ã 10. Ïðèíÿòü v j� �1. Åñëè v � � , òî ïåðåéòè ê øàãó 11, èíà÷å — ê
øàãó 15.
Ø à ã 11. Ïðèíÿòü � j.
Ø à ã 12. Ïðèíÿòü z MC z z z zv v
m
jj vj j : ( ,( ) )� � � + +2 1 .
Ø à ã 13. Ïðèíÿòü :� �1. Åñëè � �, òî ïåðåéòè ê øàãó 12, èíà÷å
ïðèíÿòü , , ,v v
m
jj vj jMC z z: ( ,( ) )� � � + +2 1 è ïåðåéòè ê øàãó 14.
Ø à ã 14. v v:� �1. Åñëè v � �, òî ïåðåéòè ê øàãó 11, èíà÷å — ê øàãó 15.
Ø à ã 15. Ïðèíÿòü � �j 1. Åñëè � �, òî ïðèíÿòü� � è ïåðåéòè ê øàãó
16, èíà÷å ïðèíÿòü v j� è ïåðåéòè ê øàãó 19.
Ø à ã 16. Åñëè z� � �1, òî ïåðåéòè ê øàãó 18, èíà÷å — ê øàãó 17.
Ø à ã 17.� �:� �1. Åñëè� � �, òî ïåðåéòè ê øàãó 16, èíà÷å ïðèíÿòü v j�
è ïåðåéòè ê øàãó 19.
Ø à ã 18. j j:� �1. Åñëè j � �, òî ïåðåéòè ê øàãó 7, èíà÷å ïðèíÿòü
v j� �1 è ïåðåéòè ê øàãó 19.
Ø à ã 19. - ,1 2 1� � � +( )m
vv vz . Åñëè v �1, òî ïåðåéòè ê øàãó 20,
èíà÷å — ê øàãó 26.
Ø à ã 20. � :�2 .
Ø à ã 21. � :� �1; � �1.
Ø à ã 22. � �� -� � � � �: ( ),� +� � � � � �MC zv v1 1 .
Ø à ã 23.� �:� �1. Åñëè� � �� � , òî ïåðåéòè ê øàãó 22, èíà÷å — ê øàãó 24.
Ø à ã 24. - , �� ���� ��� ���: ( ) ( , )� � � +� � �2 1m
v v vz MC .
Ø à ã 25. � �:� �1. Åñëè� � v , òî ïåðåéòè ê øàãó 21, èíà÷å — ê øàãó 26.
Ø à ã 26. � �1, - 0 0� , � �0.
Ø à ã 27.- / � - -: (( ), )� + �MC v v 1 ,' � �v 2. Åñëè'( 0, òî ïåðåéòè ê øà-
ãó 30, èíà÷å — ê øàãó 28.
Ø à ã 28. - / � - / � -': (( ), )� +MC .
Ø à ã 29. ' ':� �1. Åñëè' � 0, òî ïåðåéòè ê øàãó 28, èíà÷å — ê øàãó 30.
Ø à ã 30. Åñëè - / � � �1, òî ïåðåéòè ê øàãó 32, èíà÷å — ê øàãó 31.
Ø à ã 31. � �:� �1, x� � . Åñëè � � v,òî ïåðåéòè ê øàãó 33, èíà÷å — ê
øàãó 32.
Ø à ã 32. :� �1. Åñëè � �2 2m , òî ïåðåéòè ê øàãó 27, èíà÷å ïåðåéòè
ê øàãó 33.
Ìîäèôèêàöèÿ ìåòîäà Ïèòåðñîíà—Ãîðåíñòåéíà—Öèðëåðà ïðèâåäåíèåì ìàòðèöû
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 5 19
Øàã 33. Äëÿ êàæäîãî' �1, ..., v îïðåäåëèòü p' ïî ôîðìóëå p xm
' '� � �2 1 .
Ø à ã 34. Ïðèíèìàòü: � �
' 'p p:� �1, GF ( )2 , ' �1, ..., v.
Ø à ã 35. Äåëèòü ìíîãî÷ëåí � ( )x íà ìíîãî÷ëåí g x g xn k
n k( ) ...� ��
�
...� �g x g1 0 ïî ñõåìå [6]:
y� ��[ ]0 � ,� � �0 1 1, , ..., n ;
y y y gn n n n k� � � � � � �� � � � � � � [ ] [ ] [ ]1 1 , � � �1 1, ..., n , 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 , � � �1, ..., n k, GF ( )2 ,
I k y kn k0 1[ ] [ ]� �� .
Ø à ã 36. Îïðåäåëèòü êîìïîíåíòû èíôîðìàöèîííîãî âåêòîðà ïî
ôîðìóëå i Ik k� �� [ ], �1 2, , ..., k.
Ø à ã 37. Êîíåö.
Âûâîäû
Òàêèì îáðàçîì, ïðåäëîæåííàÿ ìîäèôèêàöèÿ ìåòîäà ÏÃÖ, îñíîâàííàÿ íà
ïðèâåäåíèè ìàòðèöû ê òðåóãîëüíîìó âèäó, ìîæåò áûòü ïðèìåíåíà äëÿ
óñêîðåíèÿ îáíàðóæåíèÿ è èñïðàâëåíèÿ îøèáîê â äâîè÷íûõ êîäàõ Á×Õ.
Ðàçðàáîòàííûé ïîäðîáíûé àëãîðèòì äëÿ îáíàðóæåíèÿ è èñïðàâëåíèÿ
îøèáîê â ïðèíÿòîì ìíîãî÷ëåíå ìîæíî ðåàëèçîâàòü ïðîãðàììíî íà ÿçûêå
Àññåìáëåð.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
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. Ôåéçèåâ Ô.Ã. Ìîäèôèêàöèÿ àëãîðèòìà Ïèòåðñîíà—Ãîðåíñòåéíà—Öèðëåðà è åå ýô-
ôåêòèâíàÿ ðåàëèçàöèÿ// Ýëåêòðîí. ìîäåëèðîâàíèå. — 2015. — 37, ¹ 3. — Ñ. 3—16.
6. Ôåéçèåâ Ô.Ã., Ìåãðäàä Áàáàâàíä. Îïèñàíèå äåêîäèðîâàíèÿ öèêëè÷åñêèõ êîäîâ â êëàñ-
ñå ïîñëåäîâàòåëüíîñòíûõ ìàøèí, îñíîâàííîãî íà òåîðåìå Ìåããèòòà// Àâòîìàòèêà è
âû÷èñëèòåëüíàÿ òåõíèêà. — 2012. — ¹ 4. — Ñ. 26—33.
Ô.Ã. Ôåéçèåâ, Ì.Ð. Ìåõòèåâà, Ç.À. Ñàìåäîâà
20 ISSN 0204–3572. Electronic Modeling. 2016. V. 38. ¹ 5
F.G. Feyziyev, M.R. Mekhtiyeva, Z.A. Samedova
MODIFICATION OF PETERSON-GORENSTEIN-ZIERLER METHOD,
BRINGING THE MATRIX TO TRIANGULAR FORM (BINARY CASE)
The theorem on the number of errors, which occurred in the received messages in the case of
transmission of the binary Bose-Chaudhuri-Hocquenghem codes over communication channels,
has been formulated. A modification of the Peterson-Gorenstein-Zierler method, based on the re-
duction of the matrix to triangular form, for detecting and correcting errors in the binary
Bose-Chaudhuri-Hocquenghem codes has been proposed. The technique has been developed for
accelerating calculation in accordance with this modification. A detailed description of the algo-
rithm of decoding the received messages based on the above modifications and techniques is
given.
K e y w o r d s: Binary Bose-Chaudhuri-Hocquenghem code, Peterson-Gorenstein-Zierler
method, matrix in triangular form, primitive element of finite field, error locator.
REFERENCES
1. Bleykhut, R. (1986), Teoriya i praktika kodov, kontroliruyushchikh oshibki [Theory and
practice of error control codes], Translated by Grushina, I.I., and Blinov, B.M., Mir, Moscow,
Russia.
2. Ivanov, M.A. (2001), Kriptograficheskiye 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., Vera, P. (2003), Fundamentals of error-correcting codes, Cambridge Univer-
sity Press, Cambridge, UK.
4. Birkgof, G. and Barti, T. (1976), Sovremennaya prikladnaya algebra [Modern applied alge-
bra], Translated by Manina, Yu.I., Mir, Moscow, Russia.
5. Feyziyev, F.G. (2015), “On one modification of the Peterson-Gorenstein-Zierler algorithm
and its effective realization”, Elektronnoe modelirovanie, Vol. 37, no. 3, pp. 3-16.
6. Feyziyev, F.G., and Babavand, A.M. (2012), “Description of decoding of cyclic codes in the
class of sequential machines based on the Meggitt theorem”, Avtomatika i vychislitelnaya
tekhika, no. 4, pp. 26-33.
Ïîñòóïèëà 10.05.16
ÔÅÉÇÈÅÂ Ôèêðàò Ãþëàëè îãëû, ä-ð ôèç.-ìàò. íàóê, ïðîôåññîð, çàâ. êàôåäðîé äèôôåðåí-
öèàëüíûõ óðàâíåíèé è îïòèìèçàöèè Ñóìãàèòñêîãî ãîñóíèâåðñèòåòà.  1978 ã. îêîí÷èë Àçåð-
áàéäæàíñêèé ãîñóíèâåðñèòåò. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ìàòåìàòè÷åñêàÿ êèáåð-
íåòèêà, òåîðèÿ êîíå÷íûõ àâòîìàòîâ è òåîðåòè÷åñêèå âîïðîñû èíôîðìàòèêè.
ÌÅÕÒÈÅÂÀ Ìàðàë Ðçàáàëà êûçû, êàíä. ôèç.-ìàò. íàóê, äîöåíò êàôåäðû âûñøåé ìàòåìàòèêè
Áàêèíñêîãî ãîñóíèâåðñèòåòà.  1992 ã. îêîí÷èëà Àçåðáàéäæàíñêèé ãîñóíèâåðñèòåò. Îáëàñòü
íàó÷íûõ èññëåäîâàíèé — ìàòåìàòè÷åñêàÿ êèáåðíåòèêà, òåîðèÿ êîíå÷íûõ àâòîìàòîâ è òåî-
ðåòè÷åñêèå âîïðîñû èíôîðìàòèêè.
ÑÀÌÅÄÎÂÀ Çàìèíà Àãàø êûçû, ä-ð ôèëîñîôèè ïî ìàòåìàòèêå, äîöåíò êàôåäðû èíôîð-
ìàöèîííûõ òåõíîëîãèé Àçåðáàéäæàíñêîãî óíèâåðñèòåòà ÿçûêîâ.  1994 ã. îêîí÷èëà Àçåð-
áàéäæàíñêóþ ãîñóäàðñòâåííóþ íåôòÿíóþ àêàäåìèþ. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — òåî-
ðèÿ êîíå÷íûõ àâòîìàòîâ è òåîðåòè÷åñêèå âîïðîñû èíôîðìàòèêè.
Ìîäèôèêàöèÿ ìåòîäà Ïèòåðñîíà—Ãîðåíñòåéíà—Öèðëåðà ïðèâåäåíèåì ìàòðèöû
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2016. Ò. 38. ¹ 5 21
|