Реализация параллельного метода кодирования кода Лагранжа
Разработаны алгоритмы программ и схемы устройств для реализации параллельного метода кодирования кодов Лагранжа. Определены операционная сложность алгоритмов, а также аппаратурная и временная сложности схем устройств кодирования. Розроблено алгоритми програм та схеми пристроїв для реалізації паралел...
Збережено в:
| Опубліковано в: : | Электронное моделирование |
|---|---|
| Дата: | 2014 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Russian |
| Опубліковано: |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України
2014
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/101014 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Реализация параллельного метода кодирования кода Лагранжа / В.И. Кубицкий, И.А. Жуков // Электронное моделирование. — 2014 — Т. 36, № 4. — С. 67-80. — Бібліогр.: 7 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-101014 |
|---|---|
| record_format |
dspace |
| spelling |
Кубицкий, В.И. Жуков, И.А. 2016-05-29T18:28:58Z 2016-05-29T18:28:58Z 2014 Реализация параллельного метода кодирования кода Лагранжа / В.И. Кубицкий, И.А. Жуков // Электронное моделирование. — 2014 — Т. 36, № 4. — С. 67-80. — Бібліогр.: 7 назв. — рос. 0204-3572 https://nasplib.isofts.kiev.ua/handle/123456789/101014 621.391.3:681.3.06 Разработаны алгоритмы программ и схемы устройств для реализации параллельного метода кодирования кодов Лагранжа. Определены операционная сложность алгоритмов, а также аппаратурная и временная сложности схем устройств кодирования. Розроблено алгоритми програм та схеми пристроїв для реалізації паралельного методу кодування кодів Лагранжа. Визначено операційну складність алгоритмів, а також апаратурну та часову складність схем пристроїв кодування. Algorithms of programs and schemes of devices for implementation of the parallel method of encoding the Lagrange codes have been designed. Operational complexity of algorithms as well as the instrumental and temporal complexity of schemes have been determined. ru Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України Электронное моделирование Параллельные вычисления Реализация параллельного метода кодирования кода Лагранжа 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 |
2014 |
| language |
Russian |
| container_title |
Электронное моделирование |
| publisher |
Інститут проблем моделювання в енергетиці ім. Г.Є. Пухова НАН України |
| format |
Article |
| description |
Разработаны алгоритмы программ и схемы устройств для реализации параллельного метода кодирования кодов Лагранжа. Определены операционная сложность алгоритмов, а также аппаратурная и временная сложности схем устройств кодирования.
Розроблено алгоритми програм та схеми пристроїв для реалізації паралельного методу кодування кодів Лагранжа. Визначено операційну складність алгоритмів, а також апаратурну та часову складність схем пристроїв кодування.
Algorithms of programs and schemes of devices for implementation of the parallel method of encoding the Lagrange codes have been designed. Operational complexity of algorithms as well as the instrumental and temporal complexity of schemes have been determined.
|
| issn |
0204-3572 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/101014 |
| citation_txt |
Реализация параллельного метода кодирования кода Лагранжа / В.И. Кубицкий, И.А. Жуков // Электронное моделирование. — 2014 — Т. 36, № 4. — С. 67-80. — Бібліогр.: 7 назв. — рос. |
| work_keys_str_mv |
AT kubickiivi realizaciâparallelʹnogometodakodirovaniâkodalagranža AT žukovia realizaciâparallelʹnogometodakodirovaniâkodalagranža |
| first_indexed |
2025-11-25T23:52:41Z |
| last_indexed |
2025-11-25T23:52:41Z |
| _version_ |
1850588705234878464 |
| fulltext |
ÓÄÊ 621.391.3:681.3.06
Â.È. Êóáèöêèé, êàíä. òåõí. íàóê
Âñåðîññèéñêèé íàó÷íî-èññëåäîâàòåëüñêèé èí-ò ðàäèîàïïàðàòóðû
(Ðîññèÿ, 125212, Ìîñêâà, Ëåíèíãðàäñêîå øîññå, 43-à,
òåë. +7(499) 1597847, e-mail: vkubitski@mail.ru),
È.À. Æóêîâ, ä-ð òåõí. íàóê
Íàöèîíàëüíûé àâèàöèîííûé óíèâåðñèòåò
(Óêðàèíà, 03680, Êèåâ, ïð-ò Êîñìîíàâòà Êîìàðîâà, 1,
òåë. +38(044) 4977257, e-mail: zhuia@ukr.net)
Ðåàëèçàöèÿ ïàðàëëåëüíîãî
ìåòîäà êîäèðîâàíèÿ êîäà Ëàãðàíæà
Ðàçðàáîòàíû àëãîðèòìû ïðîãðàìì è ñõåìû óñòðîéñòâ äëÿ ðåàëèçàöèè ïàðàëëåëüíîãî
ìåòîäà êîäèðîâàíèÿ êîäîâ Ëàãðàíæà. Îïðåäåëåíû îïåðàöèîííàÿ ñëîæíîñòü àëãîðèòìîâ, à
òàêæå àïïàðàòóðíàÿ è âðåìåííàÿ ñëîæíîñòè ñõåì óñòðîéñòâ êîäèðîâàíèÿ.
Ðîçðîáëåíî àëãîðèòìè ïðîãðàì òà ñõåìè ïðèñòðî¿â äëÿ ðåàë³çàö³¿ ïàðàëåëüíîãî ìåòîäó êî-
äóâàííÿ êîä³â Ëàãðàíæà. Âèçíà÷åíî îïåðàö³éíó ñêëàäí³ñòü àëãîðèòì³â, à òàêîæ àïà-
ðàòóðíó òà ÷àñîâó ñêëàäí³ñòü ñõåì ïðèñòðî¿â êîäóâàííÿ.
Ê ë þ ÷ å â û å ñ ë î â à: êîäû, êîäèðîâàíèå, àëãîðèòìû, ñõåìû óñòðîéñòâ.
Äëÿ ñðåäñòâ è ñèñòåì, ñîçäàâàåìûõ íà îñíîâå ÝÂÌ è êàíàëîâ ïåðåäà÷è
äàííûõ, àêòóàëüíà ïðîáëåìà äîñòîâåðíîñòè èíôîðìàöèè, êîòîðàÿ îñîáåí-
íî âàæíà ïðè ñîçäàíèè àâèàöèîííûõ, êîñìè÷åñêèõ, òðàíñïîðòíûõ, ýíåðãå-
òè÷åñêèõ è äðóãèõ ñèñòåì. Èñêàæåíèå èíôîðìàöèè â òàêèõ ñèñòåìàõ âåäåò
ê ñíèæåíèþ êà÷åñòâà èõ ôóíêöèîíèðîâàíèÿ, à â ñèñòåìàõ æèçíåîáåñ-
ïå÷åíèÿ — ê ñíèæåíèþ óðîâíÿ áåçîïàñíîñòè. Ïîýòîìó òðåáîâàíèÿ ê òî÷-
íîñòè ïåðåäà÷è, ââîäà, îáðàáîòêè è õðàíåíèÿ èíôîðìàöèè â íèõ çíà÷èòåëüíî
âûøå, ÷åì â îáû÷íûõ ïðîèçâîäñòâåííûõ èëè êîììåð÷åñêèõ ñèñòåìàõ.
 êîìïüþòåðíûõ ñèñòåìàõ îäíîé èç íàèáîëåå àêòóàëüíûõ ïðîáëåì
ÿâëÿåòñÿ ïðîáëåìà ïîòåðü è çàäåðæåê ïàêåòîâ.  ñèñòåìàõ ïåðåäà÷è äàí-
íûõ è ñåòåâûõ ïðèëîæåíèÿõ, ðàáîòàþùèõ â ðåæèìå ðåàëüíîãî âðåìåíè,
çàäåðæêè ïàêåòîâ ðàâíîçíà÷íû ïîòåðÿì, òàê êàê íåò âîçìîæíîñòè ïðèîñ-
òàíîâèòü ïðîöåññ îáðàáîòêè, ïåðåäà÷è è îòîáðàæåíèÿ äàííûõ â îæèäàíèè
ïàêåòà èëè åãî ïîâòîðíîé ïåðåäà÷è. Êðîìå òîãî, çàïðîñû íà ïåðåñûëêó,
îñîáåííî â òîïîëîãèè «îäèí—ìíîãèì», ïðèâîäÿò ê äîïîëíèòåëüíûì
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 4 67
� Â.È. Êóáèöêèé, È.À. Æóêîâ, 2014
íàãðóçêàì íà êàíàë ïåðåäà÷è äàííûõ, âñëåäñòâèå ÷åãî óìåíüøàåòñÿ îáúåì
òðàôèêà â ñåòè. Ïðè ýòîì ìåõàíèçì îáðàòíîé ñâÿçè ìîæåò äàòü ïîëîæè-
òåëüíûé ðåçóëüòàò, åñëè îøèáêè â ïàêåòàõ èëè ïîòåðè ïàêåòîâ íîñÿò
ñëó÷àéíûé õàðàêòåð.  ïðîòèâíîì ñëó÷àå, ïðè ñèñòåìàòè÷åñêèõ îøèáêàõ
è ïîòåðÿõ ïàêåòîâ, âîññòàíîâèòü ïîòåðÿííûå ïàêåòû â îòâåäåííîå âðåìÿ ñ
èñïîëüçîâàíèåì îáðàòíîé ñâÿçè âåñüìà çàòðóäíèòåëüíî.
Ïîýòîìó â ñîâðåìåííûõ êîìïüþòåðíûõ ñåòÿõ ñ áîëüøèìè îáúåìàìè
öèôðîâûõ äàííûõ è æåñòêèìè îãðàíè÷åíèÿìè íà ìàêñèìàëüíî äîïóñ-
òèìóþ çàäåðæêó äàííûõ â öåïè îòïðàâèòåëü—ïîëó÷àòåëü íåîáõîäèìî
ïðèìåíÿòü ìåòîäû îáìåíà áåç èñïîëüçîâàíèÿ îáðàòíûõ êàíàëîâ. Ýòî ïðè-
âîäèò ê íåîáõîäèìîñòè ðàçðàáîòêè ìåòîäîâ çàùèòû îò îøèáîê, êîòîðûå
íå ïðåäóñìàòðèâàþò íàëè÷èÿ îáðàòíîãî êàíàëà. Òàêèå ìåòîäû ìîãóò áûòü
îñíîâàíû íà ïðèìåíåíèè ïîìåõîóñòîé÷èâîãî êîäèðîâàíèÿ.
Ñóùåñòâóåò ìíîæåñòâî êîäîâ (CRC, Õýììèíãà, Á×Õ, Ðèäà—Ñîëîìîíà
è äð.), ïðåäíàçíà÷åííûõ äëÿ êîíòðîëÿ è èñïðàâëåíèÿ îøèáîê â ïðîöåññàõ
ïåðåäà÷è è õðàíåíèÿ èíôîðìàöèè. Êîäû CRC (Cyclic Redundancy Code),
ïðèìåíÿåìûå â ñåòåâûõ ïðèëîæåíèÿõ â êà÷åñòâå îáíàðóæèâàþùèõ êîäîâ,
ñïîñîáíû îáíàðóæèâàòü êàê íåçàâèñèìûå áèòîâûå îøèáêè, òàê è ñåðèè
îøèáîê â ïîñëåäîâàòåëüíî ðàñïîëîæåííûõ áèòàõ. Êîððåêòèðóþùèé êîä
Õýììèíãà èñïîëüçóþò äëÿ èñïðàâëåíèÿ îòäåëüíûõ áèòîâûõ îøèáîê â
ïàêåòå, ïðè ýòîì îáðàòíûé êàíàë íå èñïîëüçóåòñÿ.
Îäíàêî ïðèìåíåíèå óêàçàííûõ êîäîâ äëÿ êîäèðîâàíèÿ ïàêåòîâ íå
ðåøàåò ïðîáëåìó âîññòàíîâëåíèÿ âñåãî ïîòåðÿííîãî ïàêåòà áåç èñïîëü-
çîâàíèÿ îáðàòíîãî êàíàëà. Íå ìîãóò ðåøèòü ýòó ïðîáëåìó è äðóãèå êëàñ-
ñè÷åñêèå ïîìåõîóñòîé÷èâûå êîäû: ñâåðòî÷íûå êîäû èñïðàâëÿþò îòäåëüíûå
áèòîâûå îøèáêè, ìíîãèå áëîêîâûå êîäû ñïîñîáíû èñïðàâëÿòü ïà÷êè îøèáîê
â îòäåëüíî âçÿòîì ïàêåòå. Êðîìå òîãî, ðàññìîòðåííûå êîäû íå ïðèñïîñîá-
ëåíû äëÿ çàùèòû äàííûõ ïðè îáðàáîòêå â êîìïüþòåðíûõ ñèñòåìàõ.
 ðåçóëüòàòå èññëåäîâàíèé óñòàíîâëåíî, ÷òî ïåðñïåêòèâíûìè äëÿ ïðè-
ìåíåíèÿ â ñèñòåìàõ îáðàáîòêè, ïåðåäà÷è è õðàíåíèÿ èíôîðìàöèè ÿâëÿþòñÿ
ïîëèíîìèàëüíûå êîäû Ëàãðàíæà [1]. Ýòè êîäû èìåþò ïàðàëëåëüíóþ ñòðóê-
òóðó, îáëàäàþò ìèíèìàëüíîé èçáûòî÷íîñòüþ è âûñîêèìè ñâîéñòâàìè ïîáàé-
òîâîé êîððåêöèè ïðè ïåðåäà÷å è õðàíåíèè èíôîðìàöèè, à òàêæå îáåñïå-
÷èâàþò çàùèòó ôóíêöèîíàëüíûõ ïðåîáðàçîâàíèé, ëîãè÷åñêèõ è ñäâèãîâûõ
îïåðàöèé. Òàêèå âîçìîæíîñòè êîäîâ Ëàãðàíæà ïîçâîëÿþò ñîçäàâàòü ïîäñèñ-
òåìû îáåñïå÷åíèÿ ïîìåõîçàùèùåííîñòè èíôîðìàöèè â êîìïüþòåðíîé ñèñ-
òåìå, èñïîëüçóÿ ìåíüøå ðàçëè÷íûõ êîäîâ, ÷òî èñêëþ÷àåò ïåðåêîäèðîâàíèå
ïðè ïåðåõîäå ìåæäó çâåíüÿìè ñèñòåìû, èìåþùèìè ðàçíûå êîäû.
Êîä Ëàãðàíæà ìîæíî èñïîëüçîâàòü â êà÷åñòâå âíåøíåãî êîäà ïðè
äâóõóðîâíåâîì êàñêàäíîì êîäèðîâàíèè â ñåòè ñ êîììóòàöèåé ïàêåòîâ (íà-
ïðèìåð, ñ äåéòàãðàììíîé ïåðåäà÷åé ïî êàíàëó áåç îáðàòíîé ñâÿçè). Ïðè
Â.È. Êóáèöêèé, È.À. Æóêîâ
68 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 4
ýòîì âíóòðåííèì êîäîì ìîãóò áûòü êîíòðîëüíàÿ ñóììà, êîä CRC è äðóãèå
êîäû, èñïîëüçóåìûå â ñåòè. Â [2] îïèñàíà îáùàÿ ïðîöåäóðà äâóõóðîâíå-
âîãî êîäèðîâàíèÿ ïåðåäàâàåìîãî ñîîáùåíèÿ. Äëÿ òàêîãî êîäèðîâàíèÿ ïà-
êåòû ñ îøèáêàìè ïðè äåêîäèðîâàíèè îïðåäåëÿþòñÿ äåêîäèðîâàíèåì âíóò-
ðåííåãî êîäà, ïîòåðÿííûå è îøèáî÷íûå ïàêåòû îòìå÷àþòñÿ êàê ñòåðòûå è
äåêîäèðóþòñÿ âíåøíèì êîäîì. Êîä Ëàãðàíæà ïðåäñòàâëÿåò ñîáîé áëîêî-
âûé êîä, â êîòîðîì ñèìâîëû ñîñòîÿò èç m áèò. Ïîýòîìó åãî ìîæíî òàêæå
èñïîëüçîâàòü â ñåòÿõ ñ êîììóòàöèåé ñîîáùåíèé, êîäèðóÿ ñîîáùåíèÿ, ðàç-
áèòûå íà áëîêè (ýëåìåíòû äëèíû m).
Ïîêàæåì, êàê ìîæíî ðåàëèçîâàòü êîäèðîâàíèå êîäà Ëàãðàíæà, èñ-
ïîëüçóÿ àëãîðèòìû è ñõåìû óñòðîéñòâ êîäèðîâàíèÿ äëÿ ïîñëåäîâàòåëüíîé
è ïàðàëëåëüíîé ïåðåäà÷è èíôîðìàöèè. Ïàðàëëåëüíàÿ ïåðåäà÷à ïðåäïî-
ëàãàåò îäíîâðåìåííóþ ïîýëåìåíòíóþ ïåðåäà÷ó ñîîáùåíèÿ, ò.å. êàæäûé
ýëåìåíò (íåäâîè÷íûé) ïåðåäàåòñÿ ïî îòäåëüíîìó êàíàëó. Ñëîæíîñòü êîäè-
ðîâàíèÿ îïðåäåëÿåòñÿ ñëåäóþùèìè ïàðàìåòðàìè:
1) îïåðàöèîííàÿ ñëîæíîñòü — ÷èñëî îïåðàöèé (ìîäóëüíûõ) â êîíå÷-
íîì ïîëå GF (2m): ñëîæåíèå (N �), óìíîæåíèå (N �), èíâåðòèðîâàíèå (N );
2) àïïàðàòóðíàÿ ñëîæíîñòü ñõåì êîäèðîâàíèÿ (S).
3) âðåìåííàÿ ñëîæíîñòü ñõåì êîäèðîâàíèÿ (T) .
Ïàðàëëåëüíûé ìåòîä êîäèðîâàíèÿ êîäà Ëàãðàíæà è åãî ðåàëèçàöèÿ.
Êîä Ëàãðàíæà îïðåäåëÿåòñÿ èíòåðïîëÿöèîííîé ôîðìóëîé Ëàãðàíæà [1]
f f Lj
i
s
i S
i
j( ) ( )( )� ��
�
�
0
, j r�1, , (1)
ãäå f j( )� — çíà÷åíèÿ êîäîâîãî ïîëèíîìà f x( ) â êîíòðîëüíûõ óçëàõ,
êîòîðûå âû÷èñëÿþòñÿ ñ ó÷åòîì çíà÷åíèé ýòîãî ïîëèíîìà òîëüêî â èíôîð-
ìàöèîííûõ óçëàõ; f i — çíà÷åíèÿ êîäîâîãî ïîëèíîìà f x( ) â èíôîðìà-
öèîííûõ óçëàõ; LS
i
j
( ) ( )� — ôóíäàìåíòàëüíûå ïîëèíîìû Ëàãðàíæà â êîíò-
ðîëüíûõ óçëàõ,
L
x
L xS
i
j
l l j
r
i l
j l
T
j
i
( )
,
( )( ) ( )�
�
� �
� �
�
�
� �
�
1
;
S x xs� { , ..., }0 — ìíîæåñòâî èíôîðìàöèîííûõ óçëîâ ìîùíîñòè k; T �
�{ , ..., }� �1 r —ìíîæåñòâî êîíòðîëüíûõ óçëîâ ìîùíîñòè r.
Ìåòîä âû÷èñëåíèÿ êîíòðîëüíûõ ñèìâîëîâ â ñîîòâåòñòâèè ñ ôîðìóëîé
(1) íàçâàí ïàðàëëåëüíûì ìåòîäîì, à ïðîöåäóðà âû÷èñëåíèÿ — ïàðàë-
ëåëüíûì àëãîðèòìîì êîäèðîâàíèÿ êîäà Ëàãðàíæà [3]. Ðàññìîòðèì äâà
ñëó÷àÿ êîäèðîâàíèÿ.
Ðåàëèçàöèÿ ïàðàëëåëüíîãî ìåòîäà êîäèðîâàíèÿ êîäà Ëàãðàíæà
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 4 69
1. Íåîáõîäèìî âû÷èñëÿòü êîýôôèöèåíòû Ëàãðàíæà (ïðè L xi( ) ( ) const).
Òàêàÿ íåîáõîäèìîñòü âîçíèêàåò, íàïðèìåð, ïðè èñïðàâëåíèè ñòèðàíèé,
êîãäà çàðàíåå íåèçâåñòíî, â êàêèõ èíòåðïîëÿöèîííûõ óçëàõ ïîòðåáóåòñÿ
âû÷èñëÿòü çíà÷åíèÿ êîäîâîãî ïîëèíîìà. Ïîýòîìó êîýôôèöèåíòû L xi( ) ( )
âû÷èñëÿþòñÿ òîëüêî ïîñëå îïðåäåëåíèÿ ìåñòîïîëîæåíèÿ ñòèðàíèé.
2. Óçëû èíòåðïîëèðîâàíèÿ ôèêñèðîâàíû. Òîãäà çíà÷åíèÿ L xi( ) ( ) ìîãóò
áûòü âû÷èñëåíû çàðàíåå è õðàíèòüñÿ â ïàìÿòè êàê ïîñòîÿííûå âåëè÷èíû,
êîòîðûå ìîæíî èñïîëüçîâàòü â ïðîöåññå âû÷èñëåíèé.  ýòîì ñëó÷àå [4]
âûðàæåíèå äëÿ âû÷èñëåíèÿ çíà÷åíèé ïîëèíîìà â êîíòðîëüíûõ óçëàõ ïðè-
íèìàåò âèä
f f Aj
i
s
i ij( )� �
�
�
0
, j r�1, , (2)
ãäå A Lij S
i
j� �( ) ( )� const .
Çàïèøåì ôîðìóëó (1) â ñëåäóþùåì âèäå:
f f f xs
l
r
l
i
s
i
l
r
i l( )
( )
( )�
� �
�1 1
2
1
0 2
1
� � �
�
� ��
�
� �
�
� �
�
�
�
�1
2
1
0
2 3
l
r
l
i
s
i i i irf a a a
( )
...
� �
,
f f f xs
l l
r
l
i
s
i
l l
r
i( )
( )
(
,
,
�
� �
�2 2
1 2
2
0 1 2
1
� � �
�
��
�
� �
�
l ) �
� �
�
�
�
�1
1 2
2
0
1 3
l l
r
l
i
s
i i i irf a a a
,
( )
...
� �
,
(3)
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
f f f xr s r
l
r
r l
i
s
i
l
r
i l( )
( )
( )�
� �
�� � �
�
� ��
�
�
� �
�
�
1
1
1
0 1
1
Â.È. Êóáèöêèé, È.À. Æóêîâ
70 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 4
� �
�
�
�
�
�
�1
1
1
0
1 2 1
l
r
r l
i
s
i i i i rf a a a
( )
... ,
� �
,
ãäå a xi i1 1� � � ; a xi i2 2� � � , ...; a xi r i r, � �� �1 1� ; a xir i r� � � .
Ââåäåì îáîçíà÷åíèÿ:
�
�
�
�
1
2
1
1
l
r
l( )� �
� , �
�
�
�
1
1 2
2
2
l l
r
l
,
( )� �
� , ..., �
�
�
�
�
1
1
1
l
r
r l
r
( )� �
� .
Íà ðèñ. 1 ïðèâåäåí ñëåäóþùèé àëãîðèòì êîäèðîâàíèÿ, ïîçâîëÿþùèé
îïðåäåëÿòü çíà÷åíèÿ êîäîâîãî ïîëèíîìà â êîíòðîëüíûõ óçëàõ â ñîîò-
âåòñòâèè ñ ôîðìóëàìè (3):
1. Äëÿ êàæäîãî i s�0, :
à) çàäàâàÿ l r�1, , âû÷èñëÿåì âåëè÷èíû a xil i l� �� è çàïîìèíàåì èõ;
á) äëÿ êàæäîãî j r�1, îïðåäåëÿåì ïðîèçâåäåíèå
ji i
l j
ilf a�
è ñóììó
i
s
i
l j
ilf a
�
�
0
.
2. Äëÿ êàæäîãî j r�1, âû÷èñëÿåì � � �j
l l j
r
j l� � �
�
1
1
/ ( )
,
è f s j� .
×èñëî îïåðàöèé â êîíå÷íîì ïîëå GF m( )2 äëÿ ïàðàëëåëüíîãî àëãî-
ðèòìà êîäèðîâàíèÿ ïðè L xi( ) ( ) const ñîñòàâëÿåò:
N
r n r
n r
� �
� �
�
�
�
�
2 1
2
2( ) ïðè >1,
ïðè =1,
r
N r r n r� � � � �( ) ( )1 1 , N r� .
Çäåñü n k r� � — äëèíà êîäîâîãî ñîîáùåíèÿ. ×èñëî îïåðàöèé îïðåäåëÿ-
ëîñü ñ ó÷åòîì íàëè÷èÿ r ðåãèñòðîâ ïàìÿòè äëÿ õðàíåíèÿ âåëè÷èí ail . Ñ
ó÷åòîì íàëè÷èÿ ïàìÿòè äëÿ õðàíåíèÿ n óçëîâ èíòåðïîëèðîâàíèÿ íåîá-
õîäèìî èìåòü (n r� ) ðåãèñòðîâ.
Íà ðèñ. 2 ïðèâåäåíû ñõåìû óñòðîéñòâ êîäèðîâàíèÿ ïðè ïîñëåäîâàòåëü-
íîì è ïàðàëëåëüíîì ïîñòóïëåíèè èíôîðìàöèè íà óñòðîéñòâà êîäèðîâàíèÿ.
Íà ðèñ. 2, à, êëþ÷è â èñõîäíîì ñîñòîÿíèè çàìêíóòû íà êîíòàêòû a. Ïîñëå
ïîñòóïëåíèÿ ïîñëåäíåãî èíôîðìàöèîííîãî ñèìâîëà è ñîîòâåòñòâóþùèõ
âû÷èñëåíèé êëþ÷è ðàçìûêàþòñÿ è ïîî÷åðåäíî ñ ïðèõîäîì êàæäîãî çíà-
÷åíèÿ � j ïåðåêëþ÷àþòñÿ íà êîíòàêòû b j . Äàëåå âûïîëíÿåòñÿ îïðåäåëåíèå
êîýôôèöèåíòîâ � j è îêîí÷àòåëüíîå âû÷èñëåíèå êîíòðîëüíûõ ñèìâîëîâ
Ðåàëèçàöèÿ ïàðàëëåëüíîãî ìåòîäà êîäèðîâàíèÿ êîäà Ëàãðàíæà
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 4 71
Â.È. Êóáèöêèé, È.À. Æóêîâ
72 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 4
Ðèñ. 1. Áëîê-ñõåìà ïàðàëëåëüíîãî àëãîðèòìà êîäèðîâàíèÿ ïðè L xi( ) ( ) const
f s j� ïîî÷åðåäíî, íà÷èíàÿ ñ f s�1 (ïîñëå ïîñòóïëåíèÿ �1) è çàêàí÷èâàÿ f s r�
(ïîñëå ïîñòóïëåíèÿ �r ). Âû÷èñëåíèå êîíòðîëüíûõ ñèìâîëîâ f s j� (cì.
ðèñ. 2, á) âûïîëíÿåòñÿ îäíîâðåìåííî.
Àïïàðàòóðíàÿ ñëîæíîñòü S ïð ñõåì êîäèðîâàíèÿ (L xi( ) ( ) const) ïðè
ïàðàëëåëüíîì ìåòîäå ñëåäóþùàÿ:
äëÿ ñõåìû, ïðåäñòàâëåííîé íà ðèñ. 2, à ,
S r n s rs r s rs rsïð ÿ ñ ó è ê� � � � � �( )2 2 2 ;
Ðåàëèçàöèÿ ïàðàëëåëüíîãî ìåòîäà êîäèðîâàíèÿ êîäà Ëàãðàíæà
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 4 73
Ðèñ. 2. Ñõåìû óñòðîéñòâà êîäèðîâàíèÿ äëÿ ïàðàëëåëüíîãî àëãîðèòìà ïðè ïîñëåäîâàòåëü-
íîì (à) è ïàðàëëåëüíîì (á) ïîñòóïëåíèè èíôîðìàöèè (L xi( ) ( ) const) (ñì. òàêæå ñ. 74)
Â.È. Êóáèöêèé, È.À. Æóêîâ
74 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 4
Ð
èñ
.2
.Î
ê
î
í
÷
àí
è
å
äëÿ ñõåìû, ïðåäñòàâëåííîé íà ðèñ. 2, á,
� � � � � � � � � �S n s n r rs r n r rs rsïð ÿ ñ ó è[ ( )] / ( ) ( )4 3 1 2 1 1 .
Çäåñü sñ — ñëîæíîñòü ìîäóëÿ ñëîæåíèÿ äâóõ âåëè÷èí; só — ñëîæíîñòü
ìîäóëÿ óìíîæåíèÿ äâóõ âåëè÷èí; sÿ — ñëîæíîñòü ÿ÷åéêè ïàìÿòè; sè —
ñëîæíîñòü ìîäóëÿ èíâåðòèðîâàíèÿ; sê — ñëîæíîñòü êëþ÷à.
Âðåìÿ êîäèðîâàíèÿ (ïðè L xi( ) ( ) const) ñîñòàâëÿåò:
äëÿ ñõåìû, ïðåäñòàâëåííîé íà ðèñ. 2, à,
� �T n r t n r t n r t rt ntïð ÿ ñ ó è ê� � � � � � � � � �( ) ( ) ( log ( ) )2 1 2 1 12 ;
äëÿ ñõåìû, ïðåäñòàâëåííîé íà ðèñ. 2, á,
� � � �� � � � � �T r t n r tïð ó c( log ) ( log ( ) )2 21 1 ïðè � �log2 k t tc è� ,
� �� � � � �T r t t tïð ó c è( log )2 1 ïðè � �log2 k t tc è� .
Çäåñü tc — âðåìÿ ñëîæåíèÿ äâóõ âåëè÷èí; t ó — âðåìÿ óìíîæåíèÿ äâóõ
âåëè÷èí; t è — âðåìÿ èíâåðòèðîâàíèÿ; tÿ — âðåìÿ çàäåðæêè ÿ÷åéêè ïà-
ìÿòè; t ê — âðåìÿ çàäåðæêè êëþ÷à; � �A — áëèæàéøåå ê À öåëîå ÷èñëî,
áîëüøåå èëè ðàâíîå À.
Ñëåäóåò çàìåòèòü, ÷òî êàæäûé èç áëîêîâ ñóììàòîðîâ è óìíîæèòåëåé
èìååò äðåâîâèäíóþ ñòðóêòóðó ñîåäèíåíèÿ ìîäóëåé (ðèñ. 3), ÷òî óìåíü-
øàåò âðåìÿ âû÷èñëåíèÿ â ýòèõ áëîêàõ ïî ñðàâíåíèþ ñ ïîñëåäîâàòåëüíîé
ñõåìîé ñîåäèíåíèÿ ìîäóëåé. Âðåìÿ âûïîëíåíèÿ îïåðàöèé â áëîêå ñîñ-
òàâëÿåò � �log2 m t, ãäå m — ÷èñëî âõîäîâ â áëîê, t — âðåìÿ âûïîëíåíèÿ
îïåðàöèè â ìîäóëå.
Áëîê-ñõåìà ïàðàëëåëüíîãî àëãîðèòìà êîäèðîâàíèÿ ïðè L xi( ) ( ) �const,
ðåàëèçóþùàÿ âûðàæåíèå (2), ïðèâåäåíà íà ðèñ. 4, à áëîê-ñõåìà àëãîðèòìà
âû÷èñëåíèÿ âåëè÷èí L xi( ) ( ) — íà ðèñ. 5.
Ðåàëèçàöèÿ ïàðàëëåëüíîãî ìåòîäà êîäèðîâàíèÿ êîäà Ëàãðàíæà
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 4 75
=�
Ðèñ. 3. Ñõåìà ñîåäèíåíèÿ ìîäóëåé â áëîêàõ ñóììàòîðà è óìíîæèòåëÿ
×èñëî îïåðàöèé â ïîëå GF (2m) äëÿ ïàðàëëåëüíîãî àëãîðèòìà êîäèðî-
âàíèÿ ïðè L xi( ) ( ) �const ñëåäóþùåå:
N n r r� � � �( )1 , N
n r r
� �
��
�
�
( ) ïðè r >1,
ïðè r =1.0
Äëÿ õðàíåíèÿ êîýôôèöèåíòîâ L xi( ) ( ) òðåáóåòñÿ r n r( )� ðåãèñòðîâ.
Ñõåìû óñòðîéñòâ êîäèðîâàíèÿ ïðè ïîñëåäîâàòåëüíîì è ïàðàëëåëüíîì
ïîñòóïëåíèè èíôîðìàöèè ïðåäñòàâëåíû íà ðèñ. 6. Âû÷èñëåíèå êîíòðîëü-
íûõ ñèìâîëîâ f s j� íà ýòèõ ñõåìàõ âûïîëíÿåòñÿ îäíîâðåìåííî.
Â.È. Êóáèöêèé, È.À. Æóêîâ
76 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 4
Ðèñ. 4. Áëîê-ñõåìà ïàðàëëåëüíîãî àëãîðèòìà êîäèðîâàíèÿ ïðè L xi( ) ( ) �const
Ðåàëèçàöèÿ ïàðàëëåëüíîãî ìåòîäà êîäèðîâàíèÿ êîäà Ëàãðàíæà
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 4 77
Ðèñ. 5. Áëîê-ñõåìà àëãîðèòìà âû÷èñëåíèÿ L xi( ) ( ) ïðè ïàðàëëåëüíîì ìåòîäå êîäèðîâàíèÿ
Àïïàðàòóðíàÿ ñëîæíîñòü ñõåì ïðè L xi( ) ( ) �const ñëåäóþùàÿ:
äëÿ ñõåìû, ïðèâåäåííîé íà ðèñ. 6, à,
S r n r s s sïð ÿ ó c� � � � �[( ) ]1 ;
äëÿ ñõåìû, ïðèâåäåííîé íà ðèñ. 6, á,
� � � � �S r n r s s sïð ï ñ c[( ) ( ) ],
ãäå sï — ñëîæíîñòü ìîäóëÿ óìíîæåíèÿ íà ïîñòîÿííóþ âåëè÷èíó.
Â.È. Êóáèöêèé, È.À. Æóêîâ
78 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 4
Ðèñ. 6. Ñõåìû óñòðîéñòâ êîäèðîâàíèÿ ïàðàëëåëüíûì ìåòîäîì ïðè ïîñëåäîâàòåëüíîì (à) è
ïàðàëëåëüíîì (á) ïîñòóïëåíèè èíôîðìàöèè (L xi( ) ( ) �const)
Âðåìÿ êîäèðîâàíèÿ ñîñòàâëÿåò:
äëÿ ñõåìû, ïðèâåäåííîé íà ðèñ. 6, à,
T n r t t t tïð ó ñ ÿ ÿ� � � � �( ) )2 ;
äëÿ ñõåìû, ïðèâåäåííîé íà ðèñ. 6, á,
� �� � � �T t n r tïð ï ñlog ( )2 ,
ãäå t ï — âðåìÿ óìíîæåíèÿ íà ïîñòîÿííóþ âåëè÷èíó.
Óñòàíîâëåíî, ÷òî âðåìÿ êîäèðîâàíèÿ äëÿ ñõåì, ðåàëèçóþùèõ ïàðàë-
ëåëüíûé ìåòîä, ìåíüøå, ÷åì äëÿ ñõåì, ðåàëèçóþùèõ ïîñëåäîâàòåëüíûé
ìåòîä êîäèðîâàíèÿ êîäà Ëàãðàíæà.
Âûâîäû
Ðàçðàáîòàííûå àëãîðèòìû è ñõåìû ìîãóò áûòü èñïîëüçîâàíû íå òîëüêî
äëÿ êîäèðîâàíèÿ èíôîðìàöèè â êîìïüþòåðíûõ ñèñòåìàõ, íî è äëÿ âû÷èñ-
ëåíèÿ êîíòðîëüíûõ ñèìâîëîâ ïðè äåêîäèðîâàíèè [5]. Ñõåìû óñòðîéñòâ
êîäèðîâàíèÿ èìåþò áëî÷íóþ íàðàùèâàåìóþ ñòðóêòóðó è ìîãóò áûòü
àäàïòèðóåìû ê äëèíå ñîîáùåíèÿ è êîëè÷åñòâó îøèáîê. Ïðåäëîæåííûå
ïðîãðàììíûå àëãîðèòìû è ñõåìû óñòðîéñòâ êîäèðîâàíèÿ ðåàëèçîâàíû ñ
èñïîëüçîâàíèåì ïîëîæåíèé àðèôìåòèêè â êîíå÷íûõ ïîëÿõ [6, 7].
Ïîëó÷åííûå àíàëèòè÷åñêèå âûðàæåíèÿ ñëîæíîñòè ðàçðàáîòàííûõ
àëãîðèòìîâ è ñõåì óñòðîéñòâ êîäèðîâàíèÿ, ðåàëèçóþùèõ ïàðàëëåëüíûé
ìåòîä êîäèðîâàíèÿ êîäîâ Ëàãðàíæà, ïîçâîëÿò ïðîâîäèòü ñðàâíåíèå è âû-
áèðàòü ëó÷øèå ìåòîäû, àëãîðèòìû è ñõåìû êîäèðîâàíèÿ ïî íåîáõîäèìûì
ïàðàìåòðàì (÷èñëó ìîäóëüíûõ îïåðàöèé, àïïàðàòóðíûì çàòðàòàì, âðåìå-
íè âû÷èñëåíèÿ).
Algorithms of programs and schemes of devices for implementation of the parallel method of en-
coding the Lagrange codes have been designed. Operational complexity of algorithms as well as
the instrumental and temporal complexity of schemes have been determined.
ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ
1. Àìåðáàåâ Â.Ì. Òåîðåòè÷åñêèå îñíîâû ìàøèííîé àðèôìåòèêè. — Àëìà-Àòà: Íàóêà,
1976. — 324 ñ.
2. Êóáèöêèé Â.È. Âîññòàíîâëåíèå ñòåðòûõ ïàêåòîâ â êîìïüþòåðíûõ ñåòÿõ // Íàó÷. âåñòí.
ÌÃÒÓ ÃÀ. — 2011. — ¹ 169 (7). — Ñ. 65— 72.
3. Êóáèöêèé Â.È. Èñïðàâëåíèå ñòèðàíèé è îøèáîê êîäàìè Ëàãðàíæà // Óïðàâëåíèå-82:
Ìîñêîâñêàÿ íàó÷.-òåõí. êîíô. ìîëîäûõ ñïåöèàëèñòîâ è ó÷åíûõ. Ìàðò 1982 ã.: Ìàòå-
ðèàëû êîíô. ×. 2. — Ì. : ÂÍÈÈÏÎÓ, 1982. — Ñ. 125— 130.
4. Êóáèöêèé Â.È. Ïðîöåäóðû êîäèðîâàíèÿ è äåêîäèðîâàíèÿ äëÿ ïîëèíîìèàëüíûõ êîäîâ //
Ýêñïëóàòàöèÿ ïðîãðàììíîãî îáåñïå÷åíèÿ ñèñòåì ðåàëüíîãî âðåìåíè, ïîñòðîåííûõ íà
áàçå ìèêðî- è ìèíè-ÝÂÌ: Ñá. íàó÷. òð. — Êèåâ: ÊÈÈÃÀ, 1989. — Ñ. 67— 71.
Ðåàëèçàöèÿ ïàðàëëåëüíîãî ìåòîäà êîäèðîâàíèÿ êîäà Ëàãðàíæà
ISSN 0204–3572. Ýëåêòðîí. ìîäåëèðîâàíèå. 2014. Ò. 36. ¹ 4 79
5. Æóêîâ È.À., Êóáèöêèé Â.È. Âû÷èñëåíèå ñèíäðîìîâ ïðè äåêîäèðîâàíèè êîäîâ Ëàãðàíæà //
Ìåòîäè òà çàñîáè êîäóâàííÿ, çàõèñòó é óùiëíåííÿ iíôîðìàöi¿: Òðåòÿ ìiæíàð. íàóê.-
ïðàêò. êîíô., 20—22 êâiòíÿ 2011 ð. Òåçè äîïîâ. — Âiííèöÿ: ÂÍÒÓ, 2011. — Ñ. 24— 25.
6. Æóêîâ È.À., Êóáèöêèé Â.È., Äðîâîâîçîâ Â.È. Àëãîðèòìû âûïîëíåíèÿ îïåðàöèé íàä
ýëåìåíòàìè êîíå÷íîãî ïîëÿ GF (2m) â âû÷èñëèòåëüíûõ óñòðîéñòâàõ // Àâià — 2007:
VIII Ìiæíàð. íàóê.-òåõí. êîíô., 25—27 êâiòíÿ 2007 ð. Ìàòåðiàëè êîíô. Ò. 1. — Êè¿â :
ÍÀÓ, 2007.— Ñ. 13.5—13.8.
7. Ïàò. ¹ 43629 Óêðàèíà, ÌÏÊ (2009) H03M 7/00. Ïðèñòðié äëÿ ìíîæåííÿ åëåìåíòiâ
ñêií÷åííèõ ïîëiâ GF (2n) / Æóêîâ È.À., Êóáèöêèé Â.È., Ñèíåëüíèêîâ À.À. — ¹ u 2009.
02754. Îïóáë. 25.08.2009, Áþë. ¹ 16.
Ïîñòóïèëà 26.12.13;
ïîñëå äîðàáîòêè 05.05.14
ÊÓÁÈÖÊÈÉ Âàëåðèé Èâàíîâè÷, êàíä. òåõí. íàóê, çàì. äèðåêòîðà íàó÷íî-òåõíè÷åñêîãî öåíòðà
Âñåðîññèéñêîãî íàó÷íî-èññëåäîâàòåëüñêîãî èí-òà ðàäèîàïïàðàòóðû.  1973 ã. îêîí÷èë Êèåâ-
ñêèé èí-ò èíæåíåðîâ ãðàæäàíñêîé àâèàöèè. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ïðîåêòèðî-
âàíèå, ïîìåõîóñòîé÷èâîñòü êîìïüþòåðíûõ ñèñòåì è ñåòåé.
ÆÓÊÎÂ Èãîðü Àíàòîëüåâè÷, ä-ð òåõí. íàóê, ïðîôåññîð, çàâ. êàôåäðîé êîìïüþòåðíûõ ñèñòåì
è ñåòåé Íàöèîíàëüíîãî àâèàöèîííîãî óíèâåðñèòåòà Óêðàèíû.  1972 ã. îêîí÷èë Êèåâñêèé èí-ò
èíæåíåðîâ ãðàæäàíñêîé àâèàöèè. Îáëàñòü íàó÷íûõ èññëåäîâàíèé — ðàçðàáîòêà è èññëåäî-
âàíèå ìåòîäîâ è àïïàðàòíî-ïðîãðàììíûõ ñðåäñòâ ïîâûøåíèÿ ïðîèçâîäèòåëüíîñòè âû÷èñëè-
òåëüíûõ ñòðóêòóð, ñèñòåì è êîìïüþòåðíûõ ñåòåé äëÿ ðåøåíèÿ çàäà÷ áîëüøîé ðàçìåðíîñòè è
ñèñòåì ðåàëüíîãî âðåìåíè.
Â.È. Êóáèöêèé, È.À. Æóêîâ
80 ISSN 0204–3572. Electronic Modeling. 2014. V. 36. ¹ 4
|