Метод реализации арифметической операции сложения в системе остаточных классов на основе использования принципа кольцевого сдвига

Рассмотрен метод реализации арифметической операции сложения в системе остаточных классов (СОК). Метод основан на использовании принципа кольцевого сдвига (ПКС). Особенность данного метода состоит в том, что результат реализации операции сложения чисел можно определить путем последовательных цикличе...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2019
Автори:	Краснобаев, В.А., Кошман, С.А.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут кібернетики ім. В.М. Глушкова НАН України 2019
Назва видання:	Кибернетика и системный анализ
Теми:	Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/181024
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Метод реализации арифметической операции сложения в системе остаточных классов на основе использования принципа кольцевого сдвига / В.А. Краснобаев, С.А. Кошман // Кибернетика и системный анализ. — 2019. — Т. 56, № 4. — С. 194-202. — Бібліогр.: 14 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-181024
record_format	dspace
spelling	irk-123456789-1810242021-10-27T01:26:48Z Метод реализации арифметической операции сложения в системе остаточных классов на основе использования принципа кольцевого сдвига Краснобаев, В.А. Кошман, С.А. Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Рассмотрен метод реализации арифметической операции сложения в системе остаточных классов (СОК). Метод основан на использовании принципа кольцевого сдвига (ПКС). Особенность данного метода состоит в том, что результат реализации операции сложения чисел можно определить путем последовательных циклических сдвигов двоичных разрядов информационного содержимого блоков данных по соответствующим модулям СОК. Использование ПКС позволяет исключить влияние межразрядных связей между слагаемыми, что способствует повышению быстродействия выполнения операции сложения двух чисел в СОК. Розглянуто метод реалізації арифметичної операції додавання у системі залишкових класів (СЗК). Метод базується на використанні принципу кільцевого зсуву (ПКЗ). Особливість методу полягає у тому, що результат реалізації операції додавання чисел можна визначити шляхом послідовних циклічних зсувів двійкових розрядів інформаційного вмісту блоків даних за відповідними модулямями СЗК. Використання ПКЗ дозволяє позбутися впливу міжрозрядних зв'язків між доданками, що підвищує швидкодію виконання операції додавання двох чисел у СЗК. The method of realization of the arithmetic operation of addition in the system of residual classes (SRC) is considered in the paper. The method is based on the use of the principle of circular shift (PCS). The peculiarity of this method is that the result of the operation of adding the numbers can be determined by successive cyclic shifts of the bits of the information content of the data blocks by the corresponding modules of SRC. Using PCS allows you to get rid of the influence of inter-bit relationships between the terms, which allows you to increase the speed of the operation of adding two numbers to SRC. 2019 Article Метод реализации арифметической операции сложения в системе остаточных классов на основе использования принципа кольцевого сдвига / В.А. Краснобаев, С.А. Кошман // Кибернетика и системный анализ. — 2019. — Т. 56, № 4. — С. 194-202. — Бібліогр.: 14 назв. — рос. 1019-5262 http://dspace.nbuv.gov.ua/handle/123456789/181024 681.04 ru Кибернетика и системный анализ Інститут кібернетики ім. В.М. Глушкова НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу
spellingShingle	Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу Краснобаев, В.А. Кошман, С.А. Метод реализации арифметической операции сложения в системе остаточных классов на основе использования принципа кольцевого сдвига Кибернетика и системный анализ
description	Рассмотрен метод реализации арифметической операции сложения в системе остаточных классов (СОК). Метод основан на использовании принципа кольцевого сдвига (ПКС). Особенность данного метода состоит в том, что результат реализации операции сложения чисел можно определить путем последовательных циклических сдвигов двоичных разрядов информационного содержимого блоков данных по соответствующим модулям СОК. Использование ПКС позволяет исключить влияние межразрядных связей между слагаемыми, что способствует повышению быстродействия выполнения операции сложения двух чисел в СОК.
format	Article
author	Краснобаев, В.А. Кошман, С.А.
author_facet	Краснобаев, В.А. Кошман, С.А.
author_sort	Краснобаев, В.А.
title	Метод реализации арифметической операции сложения в системе остаточных классов на основе использования принципа кольцевого сдвига
title_short	Метод реализации арифметической операции сложения в системе остаточных классов на основе использования принципа кольцевого сдвига
title_full	Метод реализации арифметической операции сложения в системе остаточных классов на основе использования принципа кольцевого сдвига
title_fullStr	Метод реализации арифметической операции сложения в системе остаточных классов на основе использования принципа кольцевого сдвига
title_full_unstemmed	Метод реализации арифметической операции сложения в системе остаточных классов на основе использования принципа кольцевого сдвига
title_sort	метод реализации арифметической операции сложения в системе остаточных классов на основе использования принципа кольцевого сдвига
publisher	Інститут кібернетики ім. В.М. Глушкова НАН України
publishDate	2019
topic_facet	Нові засоби кібернетики, інформатики, обчислювальної техніки та системного аналізу
url	http://dspace.nbuv.gov.ua/handle/123456789/181024
citation_txt	Метод реализации арифметической операции сложения в системе остаточных классов на основе использования принципа кольцевого сдвига / В.А. Краснобаев, С.А. Кошман // Кибернетика и системный анализ. — 2019. — Т. 56, № 4. — С. 194-202. — Бібліогр.: 14 назв. — рос.
series	Кибернетика и системный анализ
work_keys_str_mv	AT krasnobaevva metodrealizaciiarifmetičeskojoperaciisloženiâvsistemeostatočnyhklassovnaosnoveispolʹzovaniâprincipakolʹcevogosdviga AT košmansa metodrealizaciiarifmetičeskojoperaciisloženiâvsistemeostatočnyhklassovnaosnoveispolʹzovaniâprincipakolʹcevogosdviga
first_indexed	2025-07-15T21:32:44Z
last_indexed	2025-07-15T21:32:44Z
_version_	1837750198976118784
fulltext	Â.À. ÊÐÀÑÍÎÁÀÅÂ, Ñ.À. ÊÎØÌÀÍ ÓÄÊ 681.04 ÌÅÒÎÄ ÐÅÀËÈÇÀÖÈÈ ÀÐÈÔÌÅÒÈ×ÅÑÊÎÉ ÎÏÅÐÀÖÈÈ ÑËÎÆÅÍÈß Â ÑÈÑÒÅÌÅ ÎÑÒÀÒÎ×ÍÛÕ ÊËÀÑÑÎÂ ÍÀ ÎÑÍÎÂÅ ÈÑÏÎËÜÇÎÂÀÍÈß ÏÐÈÍÖÈÏÀ ÊÎËÜÖÅÂÎÃÎ ÑÄÂÈÃÀ Àííîòàöèÿ. Ðàññìîòðåí ìåòîä ðåàëèçàöèè àðèôìåòè÷åñêîé îïåðàöèè ñëîæå- íèÿ â ñèñòåìå îñòàòî÷íûõ êëàññîâ (ÑÎÊ). Ìåòîä îñíîâàí íà èñïîëüçîâàíèè ïðèíöèïà êîëüöåâîãî ñäâèãà (ÏÊÑ). Îñîáåííîñòü äàííîãî ìåòîäà ñîñòîèò â òîì, ÷òî ðåçóëüòàò ðåàëèçàöèè îïåðàöèè ñëîæåíèÿ ÷èñåë ìîæíî îïðåäå- ëèòü ïóòåì ïîñëåäîâàòåëüíûõ öèêëè÷åñêèõ ñäâèãîâ äâîè÷íûõ ðàçðÿäîâ èí- ôîðìàöèîííîãî ñîäåðæèìîãî áëîêîâ äàííûõ ïî ñîîòâåòñòâóþùèì ìîäóëÿì ÑÎÊ. Èñïîëüçîâàíèå ÏÊÑ ïîçâîëÿåò èñêëþ÷èòü âëèÿíèå ìåæðàçðÿäíûõ ñâÿ- çåé ìåæäó ñëàãàåìûìè, ÷òî ñïîñîáñòâóåò ïîâûøåíèþ áûñòðîäåéñòâèÿ âû- ïîëíåíèÿ îïåðàöèè ñëîæåíèÿ äâóõ ÷èñåë â ÑÎÊ. Êëþ÷åâûå ñëîâà: ñèñòåìà ñ÷èñëåíèÿ, ñèñòåìà îñòàòî÷íûõ êëàññîâ, êîëüöå- âîé ðåãèñòð ñäâèãà, áûñòðîäåéñòâèå ðåàëèçàöèè àðèôìåòè÷åñêèõ îïåðàöèé, äîñòîâåðíîñòü âû÷èñëåíèé, êîìïüþòåðíûå ñèñòåìû è êîìïîíåíòû. ÂÂÅÄÅÍÈÅ Â ïîçèöèîííîé äâîè÷íîé ñèñòåìå ñ÷èñëåíèÿ (ÏÄÑÑ) âûïîëíåíèå àðèôìåòè- ÷åñêîé îïåðàöèè ñëîæåíèÿ ïðåäïîëàãàåò ïîñëåäîâàòåëüíóþ îáðàáîòêó ðàçðÿ- äîâ ÷èñåë ïî ïðàâèëàì, îïðåäåëÿåìûì ñîäåðæàíèåì äàííîé îïåðàöèè [1–3]. Îáðàáîòêà îïåðàöèé ïðîäîëæàåòñÿ äî òåõ ïîð, ïîêà íè áóäóò ïîñëåäîâàòåëüíî îïðåäåëåíû çíà÷åíèÿ âñåõ ïðîìåæóòî÷íûõ ðåçóëüòàòîâ (îò ìëàäøèõ ðàçðÿäîâ ÷èñëà ê ñòàðøèì) ñ ó÷åòîì âñåõ ëîãè÷åñêèõ ñâÿçåé ìåæäó äâîè÷íûìè ðàçðÿ- äàìè ñëàãàåìûõ. Òàêèì îáðàçîì, ÏÄÑÑ, â êîòîðîé ïðåäñòàâëÿþòñÿ è îáðàáà- òûâàþòñÿ äàííûå â ñîâðåìåííûõ êîìïüþòåðíûõ ñèñòåìàõ è êîìïîíåí- òàõ (ÊÑÊ), îáëàäàåò ñóùåñòâåííûì íåäîñòàòêîì — íàëè÷èåì ìåæðàçðÿäíûõ ñâÿçåé ìåæäó äâîè÷íûìè ðàçðÿäàìè ñëàãàåìûõ, ÷òî âëèÿåò íà áûñòðîäåéñòâèå è äîñòîâåðíîñòü âû÷èñëåíèé ÊÑÊ. Ïîýòîìó åñòåñòâåííî èçûñêàíèå âîçìîæ- íîñòåé ñîçäàíèÿ è èñïîëüçîâàíèÿ òàêîé ìàøèííîé àðèôìåòèêè, ïðèìåíÿåìîé â ÊÑÊ, â êîòîðîé ïîðàçðÿäíûå ëîãè÷åñêèå ñâÿçè ìåæäó îáðàáàòûâàåìûìè äâîè÷íûìè ðàçðÿäàìè ñëàãàåìûõ áûëè áû îñëàáëåíû ëèáî âîîáùå îòñóòñòâî- âàëè. Â ýòîì àñïåêòå îáðàùàåò íà ñåáÿ âíèìàíèå íåïîçèöèîííàÿ ñèñòåìà ñ÷èñëåíèÿ â îñòàòî÷íûõ êàññàõ (ÑÎÊ) [4–6]. ÏÎÑÒÀÍÎÂÊÀ ÇÀÄÀ×È Ìåòîä ïðåäñòàâëåíèÿ öåëûõ ÷èñåë â ÑÎÊ âìåùàåò òðè îñíîâíûõ ñâîéñòâà íåïî- çèöèîííûõ êîäîâûõ ñòðóêòóð (ÍÊÑ): íåçàâèñèìîñòü, ðàâíîïðàâíîñòü è ìàëîðàç- ðÿäíîñòü îñòàòêîâ, ñîâîêóïíîñòü êîòîðûõ îïðåäåëÿåò ÍÊÑ â ÑÎÊ. Èñïîëüçîâà- 194 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 4 © Â.À. Êðàñíîáàåâ, Ñ.À. Êîøìàí, 2019 íèå ýòèõ ñâîéñòâ îòêðûâàåò øèðîêèå âîçìîæíîñòè â ïîñòðîåíèè íå òîëüêî íîâîé ìàøèííîé àðèôìåòèêè è ìåòîäîâ ðåàëèçàöèè ìîäóëüíûõ àðèôìåòè÷åñêèõ îïåðà- öèé, íî è ïðèíöèïèàëüíî íîâîé ñõåìíîé ðåàëèçàöèè ÊÑÊ â ÑÎÊ [7–9]. Ðåàëèçàöèÿ àðèôìåòè÷åñêîé îïåðàöèè ñëîæåíèÿ äâóõ ÷èñåë A a a� ( , , ...1 2 ..., , ..., )a ai n è B b b b bi n� ( , , ..., , ..., )1 2 â ÑÎÊ îñóùåñòâëÿåòñÿ ñëîæåíèåì ñîîòâåòñòâóþùèõ îñòàòêîâ ai è bi ïî îñíîâàíèÿì (ìîäóëÿì) mi ( , )i n�1 íåçàâè- ñèìî ïî êàæäîìó èç n îñíîâàíèé. Ìàëîðàçðÿäíîñòü îñòàòêîâ ai è bi â ïðåäñòàâ- ëåíèè ñëàãàåìûõ ÷èñåë A a a a ai n� ( , , ..., , ..., )1 2 è B b b b bi n� ( , , ..., , ..., )1 2 äàåò âîçìîæíîñòü îñóùåñòâèòü ìîäóëüíóþ îïåðàöèþ ñëîæåíèÿ ( )a b mi i i� mod íà îñíîâå èñïîëüçîâàíèÿ ìàëîðàçðÿäíûõ ñóììàòîðîâ ïî ìîäóëþ. Â ýòîì ñëó÷àå âðåìÿ âûïîëíåíèÿ îïåðàöèè ñëîæåíèÿ ÷èñåë A a a a ai n� ( , , ..., , ..., )1 2 è B b b b bi n� ( , , ..., , ..., )1 2 îïðåäåëÿåòñÿ âðåìåíåì, íåîáõîäèìûì äëÿ ïîëó÷åíèÿ ðå- çóëüòàòà îïåðàöèè ( )a b mn n n� mod ïî íàèáîëüøåìó mn îñíîâàíèþ óïîðÿäî÷åííîé ÑÎÊ (a ai i� �1, ãäå i n�1, ). Îòìåòèì îñíîâíûå íåäîñòàòêè ñóììàòîðíîãî âàðèàíòà ðåàëèçàöèè ìîäóëüíîé àðèôìåòè÷åñêîé îïåðàöèé ( )a b mi i i� mod ñëîæåíèÿ â ÑÎÊ. 1. Ñëîæíîñòü ñèíòåçà äâîè÷íûõ k i -ðàçðÿäíûõ ñóììàòîðîâ ( [ log ( )]k mi i� � �2 1 1) ïî ìîäóëþ mi . 2. Çíà÷èòåëüíûå âðåìåííûå çàòðàòû, èñïîëüçóåìûå ïðè ñëîæåíèè ( )a b mn n n� mod äëÿ áîëüøèõ ðàçðÿäíûõ ñåòîê ÊÑÊ, îïðåäåëÿåìûå â ÑÎÊ çíà- ÷åíèåì mn — íàèáîëüøèì èç îñíîâàíèé. 3. Íèçêàÿ äîñòîâåðíîñòü âû÷èñëåíèé ( )a b mi i i� mod ââèäó âîçìîæíûõ îøè- áîê, âîçíèêàþùèõ â ïðîöåññå îïðåäåëåíèÿ âåëè÷èí S a b ci i i i� � � �( ) mod 2 1 ñóìì â îäíîðàçðÿäíûõ äâîè÷íûõ ïîçèöèîííûõ ñóììàòîðàõ; çà ñ÷åò âîçìîæíûõ îøèáîê, âîçíèêàþùèõ â ïðîöåññå ôîðìèðîâàíèÿ çíà÷åíèé C a bi i i� � �� 1 1 1 � � �� ( )a b ci i i1 1 ïåðåíîñîâ ìåæäó îäíîðàçðÿäíûìè äâîè÷íûìè ñóììàòîðàìè, îò ìëàäøåãî ðàçðÿäà ÷èñëà ê ñòàðøåìó ðàçðÿäó, ñîâîêóïíîñòü êîòîðûõ ñîñòàâëÿåò k i -ðàçðÿäíûé äâîè÷íûé ñóììàòîð ïî ìîäóëþ mi (k mi i� � �[ ( )]log 2 1 1), à òàêæå çà ñ÷åò âîçìîæíîãî èñêàæåíèÿ çíà÷åíèÿ Ci�1 ïåðåíîñîâ ïðè îñóùåñòâëåíèè ïðîöåñ- ñà ïåðåíîñîâ ïðîìåæóòî÷íûõ çíà÷åíèé ïîðàçðÿäíîãî ñóììèðîâàíèÿ ( )a b mi i i� mod â ïðåäåëàõ äàííîãî îñòàòêà ïî îñíîâàíèþ mi ÑÎÊ [2, 9]. ÌÅÒÎÄ ÐÅÀËÈÇÀÖÈÈ ÀÐÈÔÌÅÒÈ×ÅÑÊÎÉ ÎÏÅÐÀÖÈÈ ÑËÎÆÅÍÈß Â ÑÈÑÒÅÌÅ ÎÑÒÀÒÎ×ÍÛÕ ÊËÀÑÑÎÂ Â [10] ñôîðìóëèðîâàí ïðèíöèï òåõíè÷åñêîé ðåàëèçàöèè öåëî÷èñëåííûõ àðèô- ìåòè÷åñêèõ îïåðàöèé ïî ìîäóëþ mi — ïðèíöèï êîëüöåâîãî ñäâèãà (ÏÊÑ). Îñîáåííîñòü ìåòîäîâ ðåàëèçàöèè àðèôìåòè÷åñêèõ îïåðàöèé, îñíîâàííûõ íà èñïîëüçîâàíèè ÏÊÑ, ñîñòîèò â òîì, ÷òî ðåçóëüòàò, íàïðèìåð, ìîäóëüíîé îïå- ðàöèè ñëîæåíèÿ ÷èñåë ìîæíî îïðåäåëèòü ïóòåì ïîñëåäîâàòåëüíûõ öèêëè÷åñ- êèõ ñäâèãîâ äâîè÷íûõ ðàçðÿäîâ èíôîðìàöèîííîãî ñîäåðæèìîãî áëîêà äàííûõ. Êàê áûëî îòìå÷åíî, ÏÊÑ ìîæíî èñïîëüçîâàòü ïðè ðåàëèçàöèè àðèôìåòè÷åñêîé îïåðàöèè ñëîæåíèÿ ÷èñåë A a a a ai n� ( , , ..., , ..., )1 2 è B b b b bi n� ( , , ..., , ..., )1 2 â ÑÎÊ. Â ýòîì ñëó÷àå ðåçóëüòàò àðèôìåòè÷åñêîé îïåðàöèè ñëîæåíèÿ â ÑÎÊ îïðåäå- ëÿåòñÿ ñîâîêóïíîñòüþ îñòàòêîâ ( )a b mi i i� mod ïî ïðîèçâîëüíîìó ìîäóëþ mi ÑÎÊ, êîòîðàÿ çàäàíà íàáîðîì { }mi ( , )i n�1 îñíîâàíèé. Ðåçóëüòàò îïåðàöèè â îñòàòêå ïî ìî- äóëþ mi ÑÎÊ â ñõåìå ñëîæåíèÿ ( )a b mi i i� mod îïðåäåëÿåòñÿ òîëüêî çà ñ÷åò öèêëè- ÷åñêèõ ñäâèãîâ èíôîðìàöèîííîãî ñîäåðæèìîãî ðàçðÿäîâ ðåãèñòðà (ñäâèãàþùåãî ðåãèñ- òðà) êîëüöåâîãî ñäâèãà (ÐÊÑ). Â ýòîì ñëó÷àå îòñóòñòâóåò íåîáõîäèìîñòü (êîòîðàÿ ñóùåñ- òâóåò â ÏÄÑÑ) îïðåäåëåíèÿ âåëè÷èí S a b ci i i i� � � �( ) mod 2 1 è C a bi i i� � �� 1 1 1 � � �� ( )a b ci i i1 1 . Ýòî äàåò âîçìîæíîñòü ïîâûñèòü áûñòðîäåéñòâèå ðåàëèçàöèè àðèôìåòè÷åñêîé îïåðàöèè ñëîæåíèÿ ÷èñåë A a a� ( , , ...1 2 , , ..., )a ai n è B b b� ( , , ...1 2 ..., , ..., )b bi n â ÑÎÊ, à òàêæå ïîâûñèòü äîñòîâåðíîñòü ðåàëèçàöèè ýòîé îïåðàöèè. ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 4 195 Ïóñòü G Z1 � �( ,{ }) — àääèòèâíàÿ àáåëåâà ãðóïïà öåëûõ ÷èñåë è G Zmi2 � �( , ) — àääèòèâíàÿ àáåëåâà ãðóïïà âû÷åòîâ öåëûõ ÷èñåë ïî ìîäóëþ mi . Çàäàäèì îòîáðàæåíèå F àääèòèâíîé àáåëåâîé ãðóïïû öåëûõ ÷èñåë G1 íà àääè- òèâíóþ àáåëåâóþ ãðóïïó âû÷åòîâ öåëûõ ÷èñåë G2 ïî ìîäóëþ mi . Äëÿ ëþáîãî öåëîãî ÷èñëà A îáðàç F A( ) ðàâåí îñòàòêó a A mi i ( )mod îò äåëåíèÿ ÷èñëà A íà ìîäóëü mi ÑÎÊ. Ëåãêî ïðîâåðèòü, ÷òî äëÿ ëþáûõ öåëûõ ÷èñåë (ñëàãàåìûõ) A è B èìååò ìåñòî ñëåäóþùåå ðàâåíñòâî: F A B F A F B( ) ( ) ( )� � � , ò.å. äëÿ öåëûõ ÷èñåë îñòàòîê ( )A B mi� mod îò äåëåíèÿ ñóììû ÷èñåë A B� íà ìî- äóëü mi ðàâåí ñóììå ïî ìîäóëþ mi îñòàòêîâ a A mi i ( )mod è b B mi i ( )mod îò äåëåíèÿ íà ìîäóëü mi êàæäîãî ñëàãàåìîãî A è B. Ñëåäîâàòåëüíî, äàííîå îòîáðàæåíèå F àääèòèâíîé àáåëåâîé ãðóïïû öåëûõ ÷èñåë G1 íà àääèòèâíóþ àáå- ëåâóþ ãðóïïó âû÷åòîâ öåëûõ ÷èñåë ïî ìîäóëþ mi åñòü ãîìîìîðôèçì. Èñõîäÿ èç ýòîãî ìîæíî îðãàíèçîâàòü ïðîöåññ îïðåäåëåíèÿ ðåçóëüòàòà àðèô- ìåòè÷åñêîé ìîäóëüíîé îïåðàöèè ñëîæåíèÿ ( )a b mi i i� mod ïîñðåäñòâîì èñïîëü- çîâàíèÿ ÏÊÑ. Òàê, ÷èñëî â ÑÎÊ ïðåäñòàâëÿåòñÿ íàáîðîì èç n îñòàòêîâ { }ai , îáðà- çîâàííûõ ïóòåì ïîñëåäîâàòåëüíîãî äåëåíèÿ èñõîäíîãî ÷èñëà A íà n ïîïàðíî ïðî- ñòûõ ÷èñåë (ìîäóëåé) { }mi , äëÿ i n�1, [1, 3]. Òàê, èç ÷èñëà, çàäàííûõ n ðàçëè÷íûõ íàòóðàëüíûõ ÷èñåë m1 , m2 , …, mn (ìîäóëè ÑÎÊ), ïîïàðíî ïðîñòûìè ÷èñëàìè íà- çûâàþòñÿ òå èç íèõ, äëÿ êîòîðûõ íàèáîëüøèé îáùèé äåëèòåëü (ÍÎÄ) ëþáûõ äâóõ ðàçíûõ ÷èñåë ðàâåí åäèíèöå, ò.å. ÍÎÄ ( , )m mi j �1 ïðè i j . Îòìåòèì íåêîòîðûå âàæíûå ñâîéñòâà äàííûõ â òàáëèöå Êýëè (òàáë. 1). Èç ñó- ùåñòâîâàíèÿ íåéòðàëüíîãî ýëåìåíòà â ïîëå GF mi( ) ñëåäóåò, ÷òî â òàáëèöå Êýëè äëÿ ðåàëèçàöèè ñëîæåíèÿ ( )a b mi i i� mod åñòü ñòðîêà, â êîòîðîé ýëåìåíòû äàííî- ãî ïîëÿ ñòîÿò â ïîðÿäêå âîçðàñòàíèÿ. Èç òîãî ôàêòà, ÷òî â ïîëå âû÷åòîâ GF mi( ) ýòè ýëåìåíòû ðàçëè÷íû (ïîðÿäîê ãðóïïû ðàâåí mi ), ñëåäóåò, ÷òî â êàæäîé ñòðîêå (ñòîëáöå) òàáë. 1 ñîäåðæàòñÿ âñå ýëåìåíòû ïîëÿ òîëüêî åäèíîæäû. Ñîãëàñíî òàá- ëèöå Êýëè íåîáõîäèìàÿ ñòðîêà òàáëèöû ( )a b mi i i� mod ìîäóëüíîãî ñëîæåíèÿ ìîæåò áûòü ïîëó÷åíà ïóòåì ïîñëåäîâàòåëüíîãî öèêëè÷åñêîãî ñäâèãà ýëåìåíòîâ ïåðâîé ñòðîêè. Ñèñòåìîòåõíè÷åñêîé îñíîâîé äëÿ ñèíòåçà ñðåäñòâ (óñòðîéñòâ) ðåà- ëèçàöèè ìåòîäà àðèôìåòè÷åñêîé îïåðàöèè â ÑÎÊ íà îñíîâå ÏÊÑ ìîãóò ïðèìå- íÿòüñÿ ÷àñòî èñïîëüçóåìûå â ÏÄÑÑ ðåãèñòðû êîëüöåâîãî ñäâèãà. Ïðè èçîëæåíèè ìåòîäà ðåàëèçàöèè àðèôìåòè÷åñêîé îïåðàöèè ñëîæåíèÿ ÷è- ñåë A a a a ai n� ( , , ..., , ..., )1 2 è B b b b bi n� ( , , ..., , ..., )1 2 â ÑÎÊ äîñòàòî÷íî ðàñ- ñìîòðåòü âàðèàíò äëÿ êîíêðåòíîé ïðèâåäåííîé ñèñòåìû âû÷åòîâ ïî ìîäóëþ mi (ìíîæåñòâî âñåõ ÷èñåë ïîëíîé ñèñòåìû âû÷åòîâ ïî ìîäóëþ mi , âçàèìíî ïðîñòûõ ñ mi ). Ïóñòü äëÿ çàäàííîé îïåðàöèè ìîäóëüíîãî ñëîæåíèÿ ( )a b mi i i� mod ñî- ñòàâëåíà òàáëèöà Êýëè (ñì. òàáë. 1). Äëÿ çíà÷åíèÿ ìîäóëÿ mi � 5 òàáëèöà Êýëè ïðåäñòàâëåíà â òàáë. 2. 196 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 4 Ò à á ë è ö à 1 Çíà÷åíèå � Ðåçóëüòàòû ðàñ÷åòîâ îïåðàöèè ìîäóëüíîãî ñëîæåíèÿ ( )a b mi i i� mod � � 0 � � 1 � � 2 … � � mi � 1 � � 0 � � 1 � � 2 … � � mi � 1 0 1 2 … mi � 1 1 2 3 … 0 2 3 4 … 1 … … … … … mi � 1 0 1 … mi � 2 Ïåðå÷èñëåííûå ñâîéñòâà òàáëèöû Êýëè ïîçâîëÿþò ðåàëèçîâàòü îïåðàöèþ ìîäóëüíîãî ñëîæåíèÿ ÷èñåë A a a a ai n� ( , , ..., , ..., )1 2 è B � ( , , ...,b b1 2 b bi n, ..., ) â ÑÎÊ ïóòåì èñïîëüçîâàíèÿ ÏÊÑ â ñõåìå ñëîæåíèÿ ( )a b mi i i� mod äëÿ êàæäîãî èç n îñòàòêîâ ai ÷èñëà A a a� ( , ,1 2 ..., , ..., )a ai n . Äëÿ êàæäîãî îñòàòêà ai èç ÷èñ- ëà n ôîðìèðóåòñÿ mi ðàçðÿäîâ (îò íóëåâîãî ðàçðÿäà äî (mi -1)-ãî ðàçðÿäà) ÐÊÑ. Êîëè÷åñòâî äâîè÷íûõ ðàçðÿäîâ êàæäîãî ðàçðÿäà ÐÊÑ ðàâíà [log ( )]2 1 1mi � � . Ïðåäñòàâëåííûé â ñòàòüå ìåòîä ðåàëèçàöèè àðèôìåòè÷åñêîé îïåðàöèè ñëî- æåíèÿ ÷èñåë A a a a ai n� ( , , ..., , ..., )1 2 è B b b b bi n� ( , , ..., , ..., )1 2 â ÑÎÊ íà îñíî- âå èñïîëüçîâàíèÿ ÏÊÑ ñîñòîèò â ñëåäóþùåì. 1. Ïî ÷èñëó n îñòàòêîâ ÷èñåë A a a a ai n� ( , , ..., , ..., )1 2 è B b b� ( , , ...1 2 ..., , ..., )b bi n â n ñõåìàõ ñëîæåíèÿ ( )a b mi i i� mod ( , )i n�1 óñòàíàâëèâàåòñÿ èñõîäíîå ñîñòîÿíèå êàæäîãî ðàçðÿäà ÐÊÑ. Äëÿ ýòîãî â ñîîòâåòñòâóþùèå ðàçðÿäû ÐÊÑ (îò íóëåâîãî äî ( )mi �1 -ãî äâîè÷íîãî ðàçðÿäà) çàíîñÿòñÿ çíà÷åíèÿ ïåðâîé ñòðîêè òàáë. 1 ìîäóëüíîãî ñëîæåíèÿ ( )a b mi i i� mod â äâîè÷íîì êîäå. 2. Ïî çíà÷åíèþ ai — ïåðâîãî ñëàãàåìîãî ñóììû ( )a b mi i i� mod ÷èñëà A a a a ai n� ( , , ..., , ..., )1 2 îïðåäåëÿåòñÿ íîìåð ðàçðÿäà èñõîäíîãî èíôîðìàöèîí- íîãî ñîäåðæèìîãî ÐÊÑ, êîòîðûé è áóäåò ïðåäñòàâëÿòü ðåçóëüòàò ìîäóëüíîé îïå- ðàöèè ( )a b mi i i� mod â i-ì îñòàòêå ÑÎÊ. 3. Ïî çíà÷åíèþ bi — âòîðîãî ñëàãàåìîãî ñóììû ( )a b mi i i� mod ÷èñëà B b b b bi n� ( , , ..., , ..., )1 2 ïóòåì bi ñäâèãîâ èñõîäíîãî ñîäåðæèìîãî êàæäîãî ðàç- ðÿäà ÐÊÑ â ïîëîæèòåëüíîì (ïðîòèâ ÷àñîâîé ñòðåëêè) íàïðàâëåíèè óñòàíàâëèâà- åòñÿ îêîí÷àòåëüíîå èíôîðìàöèîííîå ñîäåðæèìîå ÐÊÑ. 4. Ïîëó÷åííîå èíôîðìàöèîííîå ñîäåðæèìîå ðàçðÿäîâ (îò íóëåâîãî äî ( )mi �1 -ãî äâîè÷íîãî ðàçðÿäà) âñåõ n ÐÊÑ îïðåäåëÿåò ðåçóëüòàò îïåðàöèè ñëîæå- íèÿ äâóõ ÷èñåë A a a a ai n� ( , , ..., , ..., )1 2 è B b b b bi n� ( , , ..., , ..., )1 2 â ÑÎÊ. Ðå- çóëüòàò ñëîæåíèÿ äâóõ ÷èñåë A a a a ai n� ( , , ..., , ..., )1 2 è B b b b bi n� ( , , ..., , ..., )1 2 îïðåäåëÿåòñÿ êàê ñîâîêóïíîñòü èç n çíà÷åíèé ñóìì îñòàòêîâ ( )a b mi i i� mod ( , )i n�1 , ïîëó÷åííûõ â ñîîòâåòñòâóþùèõ ðàçðÿäàõ ÐÊÑ (ñì. ï. 2). Â îáùåì ñëó÷àå äëÿ ïðîèçâîëüíîãî îñíîâàíèÿ mi ÑÎÊ èñõîäíàÿ öèôðîâàÿ ñòðóêòóðà ðàçðÿäîâ ÐÊÑ îïðåäåëÿåòñÿ â âèäå ñîäåðæèìîãî ïåðâîé ñòðîêè òàáëè- öû ìîäóëüíîãî ñëîæåíèÿ ( )a b mi i i� mod (ñì. òàáë. 1) è ìîæåò áûòü ïðåäñòàâëå- íà â ñëåäóþùåì âèäå: P P a P a P a P a m m m i i ièñõ ( ) [ ( ) ( ) ( ) (\|\| \|\| \|\| \|\| \|\|� � �0 0 1 1 1� �� 1 )] , (1) ãäå \|\| — îïåðàöèÿ êîíêàòåíàöèè (ïðèñîåäèíåíèÿ, ñêëåèâàíèÿ); P a� �( ) — �-é ( , )� � �0 1mi ðàçðÿä ÐÊÑ; a� — èíôîðìàöèîííîå ñîäåðæèìîå �-ãî ðàçðÿäà ÐÊÑ, ïðåäñòàâëåííîå k-ðàçðÿäíûì äâîè÷íûì êîäîì (k mi� � �[log ( ) ]2 1 1 ), êî- òîðûé ñîîòâåòñòâóåò âîçìîæíîìó çíà÷åíèþ a�-ãî îñòàòêà ( , )a mi� � �0 1 â äâîè÷íîì êîäå ÷èñëà ïî ìîäóëþ mi . ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 4 197 Ò à á ë è ö à 2 Çíà÷åíèå � Ðåçóëüòàòû ðàñ÷åòîâ îïåðàöèè ñëîæåíèÿ ïî ìîäóëþ mi � 5 � � 0 � � 1 � � 2 � � 3 � � 4 � � 0 � � 1 � � 2 � � 3 � � 4 0 1 2 3 4 1 2 3 4 0 2 3 4 0 1 3 4 0 1 2 4 0 1 2 3 Â îáùåì âèäå äëÿ ìîäóëÿ mi � 5 èñõîäíàÿ öèôðîâàÿ ñòðóêòóðà ñîäåðæèìîãî ðàçðÿäîâ P a� �( ) ( , )� � 0 4 ÐÊÑ èìååò âèä (ñì. òàáë. 2) P P a P a P a P a P aèñõ ( ) [ ( ) ( ) ( ) ( ) ( )]\|\| \|\| \|\| \|\|5 0 0 1 1 2 2 3 3 4 4� èëè Pèñõ ( ) [ ]\|\| \|\| \|\| \|\|5 000 001 010 011 100� . (2) Òàêèì îáðàçîì, ïîñðåäñòâîì øèðîêî èñïîëüçóåìûõ â ÏÄÑÑ ðåãèñòðîâ êîëüöå- âîãî ñäâèãà (â ÷àñòíîñòè, â êðèïòîãðàôèè [11–13]) ëåãêî ðåàëèçîâàòü àðèôìåòè- ÷åñêóþ îïåðàöèþ ñëîæåíèÿ ÷èñåë â ÑÎÊ. Ïðè ýòîì ñòåïåíü Z öèêëè÷åñêèõ ïå- ðåñòàíîâîê (ñäâèãîâ) èñõîäÿ èç (1) îïðåäåëÿåòñÿ ñëåäóþùèì âûðàæåíèåì: [ ( ) ( ) ( )]\|\| \|\| \|\| ( )P a P a P am m Z i i0 0 1 1 1 1� � � � � � � � � � �[ ( ) ( ) ( ) (\|\| \|\| \|\| \|\| \|\|P a P a P a P az z z z m m z zi i1 1 1 1 1� � 1 )] . (3) Ïðè òåõíè÷åñêîé ðåàëèçàöèè ïðåäëîæåííîãî ìåòîäà ïåðâîå èç ai ñëàãàåìîå îïðåäåëÿåò íîìåð ðàçðÿäà ÐÊÑ, ñîäåðæèìîå êîòîðîãî ÿâëÿåòñÿ ðåçóëüòàòîì îïå- ðàöèè ( )a b mi i i� mod . Âòîðîå èç bi ñëàãàåìîå îïðåäåëÿåò ÷èñëî Z ðàçðÿäîâ ÐÊÑ (b ki i� äâîè÷íûõ ðàçðÿäîâ), íà êîòîðîå íåîáõîäèìî ñäâèíóòü èñõîäíîå (1) ñî- äåðæèìîå ÐÊÑ â ñîîòâåòñòâèè ñ âûðàæåíèåì (3). Äëÿ ñðàâíèòåëüíîãî àíàëèçà âðåìåíè ðåàëèçàöèè öåëî÷èñëåííîé àðèôìåòè- ÷åñêîé îïåðàöèè ñëîæåíèÿ â ÏÄÑÑ è â ÑÎÊ ðàññ÷èòàåì âðåìÿ âûïîëíåíèÿ îïå- ðàöèè ñëîæåíèÿ äâóõ ÷èñåë A a a a ai n� ( , , ..., , ..., )1 2 è B b b b bi n� ( , , ..., , ..., )1 2 â ÑÎÊ ñ èñïîëüçîâàíèåì ÏÊÑ. Äëÿ ÏÊÑ â ñõåìå îïðåäåëåíèÿ çíà÷åíèÿ ( )a b mi i i� mod ( , )i n�1 âðåìÿ t ìîäóëüíîãî ñëîæåíèÿ äâóõ îñòàòêîâ ai è bi îïðåäåëÿåòñÿ â îñíîâíîì âðåìåíåì tc ñäâèãà èñõîäíîãî ñîäåðæèìîãî ðàçðÿäîâ ÐÊÑ (â äàëüíåéøåì ïîëàãàåì t t� c). Âðåìÿ ñäâèãà öèôðîâîãî ñîäåðæèìîãî ðàçðÿäîâ ÐÊÑ îïðåäåëÿåòñÿ âûðàæå- íèåì t Z k ic � � ��, (4) ãäå Z — êîëè÷åñòâî ñäâèãàåìûõ ðàçðÿäîâ ÊÑÐ; k mi i� � �[log ( )]2 1 1 — êîëè- ÷åñòâî äâîè÷íûõ ðàçðÿäîâ â îäíîì ðàçðÿäå ÐÊÑ ñõåìû îïðåäåëåíèÿ îñòàòêà ( )a b mi i i� mod ; � �� 3 â — âðåìÿ ñäâèãà îäíîãî äâîè÷íîãî ðàçðÿäà (âðåìÿ ñðàáàòûâàíèÿ îäíîãî òðèããåðà); �â — âðåìÿ ñðàáàòûâàíèÿ îäíîãî ëîãè÷åñêîãî âåíòèëÿ (ýëåìåíòà È, ÍÅ, ÈËÈ). Ó÷èòûâàÿ âûøåèçëîæåííîå, à òàêæå ÷òî t t� c, âðåìÿ t ìîäóëüíîãî ñëîæåíèÿ ( )a b mi i i� mod äâóõ îñòàòêîâ ai è bi îïðåäåëÿåòñÿ ñëåäóþùèì îáðàçîì: t b mi i� � � � � �3 1 12{[log ( )] } �â. (5) Ïîñêîëüêó b mi i� �0 1, , òî ìàêñèìàëüíî âîçìîæíîå çíà÷åíèå t äëÿ ïðîèçâîëü- íîãî ìîäóëÿ mi ÑÎÊ (b mi i� � �1 max) îïðåäåëÿåòñÿ êàê t m mi i� � � � � � �3 1 1 12( ) [log ( )]{ } â� , (6) à ìèíèìàëüíîå âðåìÿ t ðàâíî íóëþ (bi � 0). Î÷åâèäíî, ÷òî âðåìÿ t ìîäóëüíîãî ñëîæåíèÿ ( )a b mi i i� mod äâóõ îñòàòêîâ ai è bi ïðè èñïîëüçîâàíèè ÏÊÑ çàâè- ñèò îò âåëè÷èíû bi . Î÷åâèäíî, ÷òî âðåìÿ T ÑÎÊ ( )� ñëîæåíèÿ äâóõ ÷èñåë A a a a ai n� ( , , ..., , ..., )1 2 è B b b b bi n� ( , , ..., , ..., )1 2 â ÑÎÊ íà îñíîâå èñïîëüçîâàíèÿ ÏÊÑ îïðåäåëÿåòñÿ âðåìåíåì t ðåàëèçàöèè ìîäóëüíîé îïåðàöèè ( )a b mi i i� mod , äëÿ êîòîðîé âûïîëíÿåòñÿ óñëîâèå b ki i� � max (7) 198 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 4 èç âñåõ âîçìîæíûõ çíà÷åíèé ïàðíûõ ïðîèçâåäåíèé b kj j� ( , ; )j n i j� 1 . Óñëî- âèå (7) ëåæèò â îñíîâå îïðåäåëåíèÿ âðåìåíè T ÑÎÊ ( )� ðåàëèçàöèè îïåðàöèè ñëîæå- íèÿ äâóõ ÷èñåë: A a a a ai n� ( , , ..., , ..., )1 2 è B b b b bi n� ( , , ..., , ..., )1 2 â ÑÎÊ. ÏÐÈÌÅÐÛ ÂÛÏÎËÍÅÍÈß ÎÏÅÐÀÖÈÈ ÑËÎÆÅÍÈß ÄÂÓÕ ×ÈÑÅË Â ÑÎÊ Ðàññìîòðèì ïðèìåðû êîíêðåòíîãî âûïîëíåíèÿ îïåðàöèè ñëîæåíèÿ äâóõ ÷èñåë A a a a ai n� ( , , ..., , ..., )1 2 è B b b b bi n� ( , , ..., , ..., )1 2 â ÑÎÊ äëÿ îäíîáàéòîâîãî ( )l �1 ñóììàòîðà. Ïóñòü çíà÷åíèå � � �8 l — âåëè÷èíà â äâîè÷íûõ ðàçðÿäàõ îáðà- áàòûâàåìûõ â ïîçèöèîííîì ñóììàòîðå l-áàéòîâûõ ìàøèííûõ ñëîâ (ðàçðÿäíàÿ ñåòêà ñóììàòîðà). Â ÏÄÑÑ äëÿ l �1 (� � � � � �8 8 1 8l äâîè÷íûõ ðàçðÿäîâ) îñíîâà- íèÿ ÑÎÊ ìîãóò îïðåäåëÿòüñÿ ñëåäóþùèìè çíà÷åíèÿìè: m m m1 2 33 4 5� � �, , , m4 7� . Ïðèìåð 1. Ïóñòü èìååì âòîðîå ñëàãàåìîå B � ( )\|\| \|\| \|\|10 10 100 001 . Òîãäà: — äëÿ m1 3� èìååì b1 2 10� ( ), k m1 1 1 1 2� � � �[log( )] ; b k1 1 2 2 4� � � � ; — äëÿ m2 4� èìååì b2 2 10� ( ), k m2 2 1 1 2� � � �[log( )] ; b k2 2 2 2 4� � � � ; — äëÿ m3 5� èìååì b3 4 100� ( ), k m3 3 1 1 3� � � �[log( )] ; b k3 3 4 3 12� � � � ; — äëÿ m4 7� èìååì b4 1 001� ( ), k m4 4 1 1 3� � � �[log( )] ; b k4 4 1 3 3� � � � . Êàê âèäíî, íàèáîëüøåå êîëè÷åñòâî, ò.å. 12, ñäâèãàåìûõ äâîè÷íûõ ðàçðÿäîâ âûïîëíÿåòñÿ â ñõåìå ñëîæåíèÿ ( )a b m3 3 3� mod ïî ìîäóëþ m3 5� . Òàêèì îáðàçîì, äëÿ ïðèìåðà 1 âðåìÿ ñëîæåíèÿ äâóõ ÷èñåë À è Â â ÑÎÊ íà îñíîâå ÏÊÑ îïðåäåëÿåòñÿ âåëè÷èíîé T b k ÑÎÊ â â â ( )� � � � � � � � � � �3 3 3 4 3 3 36� � � . Ïðèìåð 2. Ïóñòü èìååì âòîðîå ñëàãàåìîå B � ( , , , )10 11 001 001 . Òîãäà — äëÿ m1 3� èìååì b1 2 10� ( ) , k m1 1 1 1 2� � � �[log( )] ; b k1 1 2 2 4� � � � ; — äëÿ m2 4� èìååì b2 3 11� ( ), k m2 2 1 1 2� � � �[log( )] ; b k2 2 3 2 6� � � � ; — äëÿ m3 5� èìååì b3 1 001� ( ), k m3 3 1 1 3� � � �[log( )] ; b k3 3 1 3 3� � � � ; — äëÿ m4 7� èìååì b4 1 001� ( ), k m4 4 1 1 3� � � �[log( )] ; b k4 4 1 3 3� � � � . Êàê âèäíî, íàèáîëüøåå êîëè÷åñòâî (ò.å. 6) ñäâèãàåìûõ äâîè÷íûõ ðàçðÿäîâ âûïîëíÿåòñÿ â ñõåìå ñëîæåíèÿ ( )a b m2 2 2� mod ïî ìîäóëþ m2 4� . Âðåìÿ ñëî- æåíèÿ äâóõ ÷èñåë A è B â ÑÎÊ íà îñíîâå ÏÊÑ îïðåäåëÿåòñÿ âåëè÷èíîé T b k ÑÎÊ â â â ( )� � � � � � � � � � �2 2 3 3 2 3 18� � � . Îñîáåííîñòü èñïîëüçîâàíèÿ â ÑÎÊ ÏÊÑ çàêëþ÷àåòñÿ â òîì, ÷òî âðåìÿ âû- ïîëíåíèÿ îïåðàöèè ñëîæåíèÿ çàâèñèò îò âåëè÷èíû âòîðîãî bi ñëàãàåìîãî ñóììû ( )a b mi i i� mod è ìîæåò áûòü ðàçëè÷íûì. Âðåìÿ T ÑÎÊ ( )� ñëîæåíèÿ äâóõ ÷èñåë A a a a ai n� ( , , ..., , ..., )1 2 è B b b b bi n� ( , , ..., , ..., )1 2 â ÑÎÊ ìîæíî õàðàêòåðèçîâàòü êàê ìàêñèìàëüíûì T ÑÎÊÌÀÊÑ ( )� âðåìåíåì, òàê è âîçìîæíûì ñðåäíèì T ÑÎÊÑÐÅÄ ( )� âðå- ìåíåì ñëîæåíèÿ. Äàëåå âðåìÿ ñëîæåíèÿ äâóõ ÷èñåë A a a a ai n� ( , , ..., , ..., )1 2 è B b b b bi n� ( , , ..., , ..., )1 2 â ÑÎÊ áóäåò îïðåäåëÿòüñÿ âûðàæåíèåì T ÑÎÊÌÀÊÑ ( )� . Èñõîäÿ èç âûðàæåíèÿ (6) ìàêñèìàëüíîå âðåìÿ ñëîæåíèÿ äâóõ ÷èñåë A a a a ai n� ( , , ..., , ..., )1 2 è B b b b bi n� ( , , ..., , ..., )1 2 â ÑÎÊ îïðåäåëèòñÿ êàê T m mn nÑÎÊÌÀÊÑ â{ }( ) ( ) [log ( )]� � � � � � � �3 1 1 12 � . (8) Îòìåòèì, ÷òî ñóùåñòâóþò àëãîðèòìû, êîòîðûå ïîçâîëèëè ñèíòåçèðîâàòü ðÿä òåõíè÷åñêèõ ðåøåíèé (óñòðîéñòâ) äëÿ ðåàëèçàöèè öåëî÷èñëåííîé ìîäóëüíîé àðèôìåòè÷åñêîé îïåðàöèè ñëîæåíèÿ íà îñíîâå èñïîëüçîâàíèÿ ÏÊÑ. Ïðè ýòîì ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 4 199 ìàêñèìàëüíîå âðåìÿ T ÑÎÊÌÀÊÑ ( )� âûïîëíåíèÿ îïåðàöèè ñëîæåíèÿ ãàðàíòèðîâàíî óìåíüøàåòñÿ êàê ìèíèìóì â äâà ðàçà [14]. Â ýòîì ñëó÷àå âðåìÿ T ÑÎÊ ( )� ñëîæåíèÿ äâóõ ÷èñåë A a a a ai n� ( , , ..., , ..., )1 2 è B b b b bi n� ( , , ..., , ..., )1 2 â ÑÎÊ îïðåäå- ëèòñÿ âûðàæåíèåì T ÑÎÊ ( )� = T ÑÎÊÌÀÊÑ ( )� /2. Òîãäà âðåìÿ ñëîæåíèÿ äâóõ ÷èñåë â ÑÎÊ îïðåäåëèòñÿ êàê T m mn nÑÎÊ â{ }( ) ( ) [log ( )] /� � � � � � � �3 1 1 1 22 � . (9) Èçâåñòíî [9], ÷òî âðåìÿ T ÏÑÑ ( )� ñëîæåíèÿ ÷èñåë À è Â â ÏÑÑ îïðåäåëÿåòñÿ ïî ôîðìóëå T t l ÏÑÑ c â ( ) ( ) ( )� � � � � � � � �2 1 16 1 3� � , (10) ãäå � � �8 l — ðàçðÿäíàÿ ñåòêà ïîçèöèîííîãî ñóììàòîðà; tc â� �3 � — âðåìÿ ñóììèðîâàíèÿ â ( )i �1 -ì äâîè÷íîì ðàçðÿäå ïîçèöèîííîãî ñóììàòîðà çíà÷åíèé a b ci i i� �� 1 1 , ò.å. âðåìÿ îïðåäåëåíèÿ çíà÷åíèé Ci�1 è S i�1. Ïðîâåäåì îöåíî÷íûé ðàñ÷åò è ñðàâíèòåëüíûé àíàëèç âðåìåíè âûïîëíåíèÿ àðèôìåòè÷åñêîé îïåðàöèè ñëîæåíèÿ äâóõ ÷èñåë â ÏÄÑÑ è â ÑÎÊ äëÿ îäíîáàéòî- âîãî ( )l �1 è äâóõáàéòîâîãî ( )l � 2 ìàøèííûõ ñëîâ. Äëÿ l �1 (� � 8 äâîè÷íûõ ðàç- ðÿäîâ) ÑÎÊ ïðåäñòàâëÿåòñÿ íàáîðîì ñëåäóþùèõ îñíîâàíèé: m1 3� , m2 4� , m4 5� , m4 7� , à äëÿ l � 2 (� �16 äâîè÷íûõ ðàçðÿäîâ) ÑÎÊ ïðåäñòàâëÿåòñÿ íàáîðîì îñíîâàíèé m m m m1 2 3 42 3 5 7� � � �, , , , m m5 611 13� �, . Ïðè ðàñ÷åòàõ èñïîëüçóåì ôîðìóëû (8)–(10). Ðåçóëüòàòû ðàñ÷åòîâ ñðàâíèòåëüíîãî àíàëèçà âðåìåíè T ( )� ðåà- ëèçàöèè îïåðàöèè ñëîæåíèÿ ÷èñåë â ÑÎÊ ïðåäñòàâëåíû â òàáë. 3. Ñðàâíèòåëüíûé àíàëèç ðåçóëüòàòîâ ðàñ÷åòîâ ïîêàçàë ýôôåêòèâíîñòü èñïîëü- çîâàíèÿ ÏÊÑ ïðè ðåàëèçàöèè àðèôìåòè÷åñêîé îïåðàöèè ñëîæåíèÿ â ÑÎÊ. ÇÀÊËÞ×ÅÍÈÅ Ìîäóëüíîñòü ñòðóêòóðû âû÷èñëèòåëüíîãî ïðîöåññà â ÑÎÊ äàåò âîçìîæíîñòü èñïîëüçîâàòü ÏÊÑ äëÿ ðåàëèçàöèè îñíîâíûõ ìîäóëüíûõ öåëî÷èñëåííûõ àðèô- ìåòè÷åñêèõ îïåðàöèé. Íà îñíîâàíèè ýòîãî â íàñòîÿùåé ñòàòüå ðàçðàáîòàí ìå- òîä ðåàëèçàöèè àðèôìåòè÷åñêîé îïåðàöèè ñëîæåíèÿ â ñèñòåìå îñòàòî÷íûõ êëàññîâ íà îñíîâå èñïîëüçîâàíèÿ ïðèíöèïà êîëüöåâîãî ñäâèãà. Èñïîëüçîâàíèå ÏÊÑ â ÑÎÊ ïîçâîëÿåò óñòðàíèòü îñíîâíîé íåäîñòàòîê ñóùåñòâóþùèõ ÊÑÊ, ôóíêöèîíèðóþùèõ â ÏÄÑÑ, à èìåííî èçáàâèòüñÿ îò âëèÿíèÿ ìåæðàçðÿäíûõ ñâÿçåé ìåæäó äâîè÷íûìè ðàçðÿäàìè ÷èñåë ai è bi ïðè âûïîëíåíèè îïåðàöèè ñëîæåíèÿ ( )a b mi i i� mod , ò.å. èñêëþ÷èòü âëèÿíèå ìåæðàçðÿäíûõ ñâÿçåé ìåæ- äó îäíîðàçðÿäíûìè ïîçèöèîííûìè ñóììàòîðàìè íà ðåçóëüòàò îïåðàöèè ñëî- 200 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 4 Ò à á ë è ö à 3 Âåëè÷èíà l ðàçðÿäíîé ñåòêè êîìïüþòåðíîé ñèñòåìû Ñîâîêóï- íîñòü îñíîâàíèé ñèñòåìû îñòàòî÷íûõ êëàññîâ Ìàêñè- ìàëüíîå mn îñíîâà- íèå ÑÎÊ Ðàçðÿäíîñòü ìàêñè- ìàëüíîãî mn îñíî- âàíèÿ ÑÎÊ Îòíîñèòåëüíîå T � âðåìÿ ñëîæåíèÿ Âûèãðûø âî âðåìåíè, %ÏÄÑÑ ÑÎÊ Îäíîáàéòîâàÿ ( )l � 1 ðàçðÿäíàÿ ñåòêà (� � 8) m1 3� , m2 4� , m3 5� , m4 7� m4 7� k4 3� 15 9 40 Äâóõáàéòîâàÿ ( )l � 2 ðàçðÿäíàÿ ñåòêà (� � 16) m1 2� , m2 5� , m3 7� , m4 9� , m5 11� , m6 13� m6 13� k6 4� 31 24 22 æåíèÿ A B� äâóõ ÷èñåë. Â ñòàòüå ïîêàçàíî, ÷òî ïðèìåíåíèå ÏÊÑ ïîçâîëÿåò ïîâûñèòü áûñòðîäåéñòâèå âûïîëíåíèÿ îïåðàöèè ñëîæåíèÿ A B� äâóõ ÷èñåë. Èñïîëüçîâàíèå ÏÊÑ ìîæåò ïîâûñèòü äîñòîâåðíîñòü âû÷èñëåíèé (ò.å. âûïîëíå- íèÿ îïåðàöèè ìîäóëüíîãî ñëîæåíèÿ â ÑÎÊ) çà ñ÷åò èñêëþ÷åíèÿ èç ïðîöåññà ðåàëè- çàöèè àðèôìåòè÷åñêîé îïåðàöèè ñëîæåíèÿ ( )a b mi i i� mod âîçìîæíûõ îøèáîê, êî- òîðûå ìîãóò èìåòü ìåñòî ïðè îïðåäåëåíèè çíà÷åíèé ñóìì S i è çíà÷åíèé Ci ñèãíà- ëîâ ïåðåíîñîâ. Äîñòîâåðíîñòü âû÷èñëåíèé ìîæåò óâåëè÷èòüñÿ òàêæå çà ñ÷åò èñêëþ÷åíèÿ âîçìîæíîãî âëèÿíèÿ èñêàæåííîãî çíà÷åíèÿ Ci ñèãíàëà ïåðåíîñà â ïðî- öåññå ïåðåíîñà ýòîãî ñèãíàëà îò i-ãî ê ( )i �1 -ìó îäíîðàçðÿäíîìó ïîçèöèîííîìó äâî- è÷íîìó ñóììàòîðó. Îäíàêî óòâåðæäåíèå î âîçìîæíîì ïîâûøåíèè äîñòîâåðíîñòè âûïîëíåíèÿ îïåðàöèè ñëîæåíèÿ â ÑÎÊ çà ñ÷åò èñïîëüçîâàíèÿ ÏÊÑ òðåáóåò äîïîë- íèòåëüíûõ èññëåäîâàíèé. Îòìåòèì, ÷òî ñèñòåìîòåõíè÷åñêîé îñíîâîé äëÿ ñèíòåçà ñðåäñòâ (óñòðîéñòâ) ðåàëèçàöèè ìåòîäà àðèôìåòè÷åñêîé îïåðàöèè ñëîæåíèÿ â ÑÎÊ íà îñíîâå ÏÊÑ ìîãóò áûòü øèðîêî èñïîëüçóåìûå â ÏÄÑÑ ðåãèñòðû ñäâèãà. ÑÏÈÑÎÊ ËÈÒÅÐÀÒÓÐÛ 1. Àêóøñêèé È.ß., Þäèöêèé Ä.È. Ìàøèííàÿ àðèôìåòèêà â îñòàòî÷íûõ êëàññàõ. Ìîñêâà: Ñîâ. ðàäèî, 1968. 440 ñ. 2. Êðàñíîáàåâ Â.À. Ìåòîäû ïîâûøåíèÿ íàäåæíîñòè ñïåöèàëèçèðîâàííûõ ÝÂÌ ñèñòåì è ñðåäñòâ ñâÿçè. Õàðüêîâ: ÌÎ ÑÑÑÐ, 1990. 172 ñ. 3. Êîëÿäà À.À., Ïàê È.Ò. Ìîäóëÿðíûå ñòðóêòóðû êîíâåéåðíîé îáðàáîòêè öèôðîâîé èíôîðìà- öèè. Ìèíñê: Óíèâåðñèòåòñêîå, 1992. 256 ñ. 4. Ôèëèïïåíêî È.Ã. Âçàèìîäåéñòâóþùèå íåéðîàâòîìàòû è íåéðîàâòîìàòíî-âû÷èñëèòåëüíûå ñòðóêòóðû. Ïîä ðåä. Ðóäåíêî Î.Ã. Êèåâ: Êàðàâåëëà, 2015. 440 ñ. 5. Krasnobayev V.A., Koshman S.A., Mavrina M.A. A method for increasing the reliability of verification of data represented in a residue number system. Cybernetics and Systems Analysis. 2014. Vol. 50, N 6. P. 969–976. 6. Krasnobayev V.A., Yanko A.S., Koshman S.A. A method for arithmetic comparison of data represented in a residue number system. Cybernetics and Systems Analysis. 2016. Vol. 52, N 1. P. 145–150. 7. Îíèùåíêî Ñ.Ì. Ïðèìåíåíèå ãèïåðêîìïëåêñíûõ ÷èñåë â òåîðèè èíåðöèàëüíîé íàâèãàöèè. Àâòîíîìíûå ñèñòåìû. Êèåâ.: Íàóê. äóìêà, 1983. 208 ñ. 8. Íèêîëàé÷óê ß.Í., Âîçíà Í.ß., Êðóëèêîâñêèé Á.Á., Ïèõ Â.ß. Ìåòîä ñòðóêòóðèçàöèè äèñêðåòíî- ãî êîñèíóñíîãî ïðåîáðàçîâàíèÿ Ôóðüå â ìîäóëüíîé àðèôìåòèêå òåîðåòèêî-÷èñëîâîãî áàçèñà Õààðà–Êðåñòåíñîíà. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç. 2018. Ò. 54, ¹ 3. Ñ. 178–188. 9. Ìàëèíîâñêèé Á.Í., Áðþõîâè÷ Å.È., Äåíèñåíêî Å.Ë. è äð. Ñïðàâî÷íèê ïî öèôðîâîé âû÷èñëèòåëü- íîé òåõíèêå (ïðîöåññîðû è ïàìÿòü). Ïîä ðåä. Ìàëèíîâñêîãî Á.Í. Êèåâ: Òåõí³êà, 1979. 366 ñ. 10. Êðàñíîáàåâ Â.À. Ïðèíöèï ðåàëèçàöèè àðèôìåòè÷åñêèõ îïåðàöèé â ñèñòåìå îñòàòî÷íûõ êëàñ- ñîâ. ÀÑÓ è ïðèáîðû àâòîìàòèêè. 1988. Âûï. 86. Ñ. 82–85. 11. Stasev Yu.V., Kuznetsov A.A., Nosik A.M. Formation of pseudorandom sequences with improved autocorrelation properties. Cybernetics and Systems Analysis. 2007. Vol. 43, N 1. P. 1–11. 12. Kuznetsov O., Lutsenko M., Ivanenko D. Strumok stream cipher: Specification and basic properties. Third International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PICS&T). Kharkiv, 2016. P. 59–62. 13. Gorbenko I., Kuznetsov A., Lutsenko M., Ivanenko D. The research of modern stream ciphers. 4th International Scientific-Practical Conference Problems of Infocommunications. Science and Technology (PICS&T). Kharkov, 2017. P. 207–210. 14. Andrushkevych A., Gorbenko Y., Kuznetsov O., Oliynykov R., Rodinko M. A prospective lightweight block cipher for green IT engineering. In: Green IT Engineering: Social, Business and Industrial Applications. Kharchenko V., Kondratenko Y., Kacprzyk J. (Eds.). Cham: Springer. 2018. Vol. 171. P. 95–112. DOI: https://doi.org/10.1007/978-3-030-00253-4_5. Íàä³éøëà äî ðåäàêö³¿ 19.10.2018 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 4 201 Â.À. Êðàñíîáàºâ, Ñ.Î. Êîøìàí ÌÅÒÎÄ ÐÅÀË²ÇÀÖ²¯ ÀÐÈÔÌÅÒÈ×ÍÎ¯ ÎÏÅÐÀÖ²¯ ÄÎÄÀÂÀÍÍß Ó ÑÈÑÒÅÌ² ÇÀËÈØÊÎÂÈÕ ÊËÀÑ²Â ÍÀ ÎÑÍÎÂ² ÂÈÊÎÐÈÑÒÀÍÍß ÏÐÈÍÖÈÏÓ Ê²ËÜÖÅÂÎÃÎ ÇÑÓÂÓ Àíîòàö³ÿ. Ðîçãëÿíóòî ìåòîä ðåàë³çàö³¿ àðèôìåòè÷íî¿ îïåðàö³¿ äîäàâàííÿ ó ñèñòåì³ çàëèøêîâèõ êëàñ³â (ÑÇÊ). Ìåòîä áàçóºòüñÿ íà âèêîðèñòàíí³ ïðèíöè- ïó ê³ëüöåâîãî çñóâó (ÏÊÇ). Îñîáëèâ³ñòü ìåòîäó ïîëÿãàº ó òîìó, ùî ðåçóëü- òàò ðåàë³çàö³¿ îïåðàö³¿ äîäàâàííÿ ÷èñåë ìîæíà âèçíà÷èòè øëÿõîì ïîñë³äîâ- íèõ öèêë³÷íèõ çñóâ³â äâ³éêîâèõ ðîçðÿä³â ³íôîðìàö³éíîãî âì³ñòó áëîê³â äà- íèõ çà â³äïîâ³äíèìè ìîäóëÿìÿìè ÑÇÊ. Âèêîðèñòàííÿ ÏÊÇ äîçâîëÿº ïîçáóòèñÿ âïëèâó ì³æðîçðÿäíèõ çâ’ÿçê³â ì³æ äîäàíêàìè, ùî ï³äâèùóº øâèäêîä³þ âèêîíàííÿ îïåðàö³¿ äîäàâàííÿ äâîõ ÷èñåë ó ÑÇÊ. Êëþ÷îâ³ ñëîâà: cèñòåìà ÷èñëåííÿ, ñèñòåìà çàëèøêîâèõ êëàñ³â, ê³ëüöåâèé ðåã³ñòð çñóâó, øâèäêîä³ÿ ðåàë³çàö³¿ àðèôìåòè÷íèõ îïåðàö³é, äîñòîâ³ðí³ñòü îá÷èñëåíü, êîìï’þòåðí³ ñèñòåìè òà êîìïîíåíòè. V.A. Krasnobayev, S.A. Koshman THE METHOD OF OPERATIONAL DATA DIAGNOSING REPRESENTED IN THE RESIDUE NUMBER SYSTEM Abstract. The method of realization of the arithmetic operation of addition in the system of residual classes (SRÑ) is considered in the article. The method is based on the use of the principle of circular shift (PCS). The peculiarity of this method is that the result of the operation of adding the numbers can be determined by successive cyclic shifts of the bits of the information content of the data blocks by the corresponding modules of SRÑ. Using PCS allows you to get rid of the influence of inter-bit relationships between the terms, which allows you to increase the speed of the operation of adding two numbers to SRÑ. Keywords: number system, residue number system, circular shift register, speed of implementation of arithmetic operations, reliability of calculations, computer systems and components. Êðàñíîáàåâ Âèêòîð Àíàòîëüåâè÷, äîêòîð òåõí. íàóê, ïðîôåññîð êàôåäðû Õàðüêîâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èì. Â.Í. Êàðàçèíà, e-mail: v.a.krasnobaev@gmail.com. Êîøìàí Ñåðãåé Àëåêñàíäðîâè÷, êàíäèäàò òåõí. íàóê, äîöåíò êàôåäðû Õàðüêîâñêîãî íàöèîíàëüíîãî óíèâåðñèòåòà èì. Â.Í. Êàðàçèíà, e-mail: s_koshman@ukr.net. 202 ISSN 1019-5262. Êèáåðíåòèêà è ñèñòåìíûé àíàëèç, 2019, òîì 55, ¹ 4

Метод реализации арифметической операции сложения в системе остаточных классов на основе использования принципа кольцевого сдвига

Репозитарії

Схожі ресурси