Теория и методы построения системы модулей модифицированной совершенной формы системы остаточных классов
Розглянуто теоретичні основи та методи пошуку системи модулів модифікованої досконалої форми системи залишкових класів для зменшення обчислювальної складності.
Gespeichert in:
| Datum: | 2016 |
|---|---|
| Hauptverfasser: | , , |
| Format: | Artikel |
| Sprache: | Russian |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2016
|
| Schriftenreihe: | Проблемы управления и информатики |
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/208194 |
| 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: | Теория и методы построения системы модулей модифицированной совершенной формы системы остаточных классов / М.Н. Касянчук, Я.Н. Николайчук, И.З. Якименко // Проблемы управления и информатики. — 2016. — № 4. — С. 109-116. — Бібліогр.: 17 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-208194 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-2081942025-10-21T00:10:13Z Теория и методы построения системы модулей модифицированной совершенной формы системы остаточных классов Теорія та методи побудови системи модулів модифікованої досконалої форми системи залишкових класів Theory and methods of constructing of system of modules of modified forms of a perfect system of residual classes Касянчук, М.М. Николайчук, Я.М. Якименко, И.З. Методы обработки информации Розглянуто теоретичні основи та методи пошуку системи модулів модифікованої досконалої форми системи залишкових класів для зменшення обчислювальної складності. Theoretical backgrounds and methods for forming a modified perfect system of residual classes are considered, reducing computational complexity. 2016 Article Теория и методы построения системы модулей модифицированной совершенной формы системы остаточных классов / М.Н. Касянчук, Я.Н. Николайчук, И.З. Якименко // Проблемы управления и информатики. — 2016. — № 4. — С. 109-116. — Бібліогр.: 17 назв. — рос. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/208194 519.7 10.1615/JAutomatInfScien.v48.i8.60 ru Проблемы управления и информатики application/pdf Інститут кібернетики ім. В.М. Глушкова НАН України |
| 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 |
2016 |
| topic_facet |
Методы обработки информации |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/208194 |
| citation_txt |
Теория и методы построения системы модулей модифицированной совершенной формы системы остаточных классов / М.Н. Касянчук, Я.Н. Николайчук, И.З. Якименко // Проблемы управления и информатики. — 2016. — № 4. — С. 109-116. — Бібліогр.: 17 назв. — рос. |
| series |
Проблемы управления и информатики |
| work_keys_str_mv |
AT kasânčukmm teoriâimetodypostroeniâsistemymodulejmodificirovannojsoveršennojformysistemyostatočnyhklassov AT nikolajčukâm teoriâimetodypostroeniâsistemymodulejmodificirovannojsoveršennojformysistemyostatočnyhklassov AT âkimenkoiz teoriâimetodypostroeniâsistemymodulejmodificirovannojsoveršennojformysistemyostatočnyhklassov AT kasânčukmm teoríâtametodipobudovisistemimodulívmodifíkovanoídoskonaloíformisistemizališkovihklasív AT nikolajčukâm teoríâtametodipobudovisistemimodulívmodifíkovanoídoskonaloíformisistemizališkovihklasív AT âkimenkoiz teoríâtametodipobudovisistemimodulívmodifíkovanoídoskonaloíformisistemizališkovihklasív AT kasânčukmm theoryandmethodsofconstructingofsystemofmodulesofmodifiedformsofaperfectsystemofresidualclasses AT nikolajčukâm theoryandmethodsofconstructingofsystemofmodulesofmodifiedformsofaperfectsystemofresidualclasses AT âkimenkoiz theoryandmethodsofconstructingofsystemofmodulesofmodifiedformsofaperfectsystemofresidualclasses |
| first_indexed |
2025-10-21T01:21:47Z |
| last_indexed |
2025-10-22T01:10:26Z |
| _version_ |
1846642398353948672 |
| fulltext |
© М.Н. КАСЯНЧУК, Я.Н. НИКОЛАЙЧУК, И.З. ЯКИМЕНКО, 2016
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 4 109
МЕТОДЫ ОБРАБОТКИ ИНФОРМАЦИИ
УДК 519.7
М.Н. Касянчук, Я.Н. Николайчук, И.З. Якименко
ТЕОРИЯ И МЕТОДЫ ПОСТРОЕНИЯ СИСТЕМЫ
МОДУЛЕЙ МОДИФИЦИРОВАННОЙ
СОВЕРШЕННОЙ ФОРМЫ
СИСТЕМЫ ОСТАТОЧНЫХ КЛАССОВ
Введение
В настоящее время известно, что двоичная система исчисления, которая чрезвы-
чайно распространена в современных компьютерных системах, имеет несколько су-
щественных недостатков (большая разрядность используемых чисел, строгая после-
довательность выполнения арифметических операций, наличие междуразрядных пе-
реносов) [1], которые заметно уменьшают быстродействие вычислительных машин.
Поэтому в связи с активным развитием технологий параллелизма [2] приобретают ак-
туальность методы вычислений, базирующиеся на непозиционных системах исчис-
ления. Наиболее приемлемая среди них — система остаточных классов (СОК) [3],
которая позволяет существенно улучшить параметры компонентов вычислительных
систем по сравнению с устройствами, построенными на той же физико-
технологической базе и работающими в позиционных системах исчисления [4].
Несмотря на недостатки (сложность при выполнении операций деления и сравне-
ния чисел [5], определение переполнения разрядной сетки), СОК дает возмож-
ность эффективно распараллеливать выполнение арифметических операций сло-
жения, вычитания, умножения, возведения в степень [6], что особенно актуально
при работе с многоразрядными числами [7] в современных асимметрических крип-
тосистемах (RSA, Рабина, Эль–Гамаля, использования электронной цифровой под-
писи [8] и т.д.). Перспективно также применение СОК в средствах помехозащищен-
ного кодирования [9] для повышения надежности цифровых многоканальных систем
передачи информации [10]. Сочетание СОК и нейронных сетей, которые дополняют
одна другую, вызывает интерес, поскольку можно реализовать принципы обменных
операций между быстродействием, точностью и надежностью для создания отказо-
устойчивого нейрокомпьютера [11].
Любое десятичное число N в СОК представляется наименьшими неотрица-
тельными остатками
ib при делении этого числа на каждый из системы попарно
взаимно простых модулей ,ip т.е. ii pNb mod [12], причем N должно быть огра-
ничено неравенством ,10 PN где .
1
n
i
ipP
Одна из причин, которые замедлили развитие СОК, — значительная вычис-
лительная сложность преобразования числа из СОК в десятичную систему исчис-
ления, которая базируется на использовании китайской теоремы об остатках [12]:
110 ISSN 0572-2691
,mod
1
PBbN
n
i
ii
(1)
где ,iii MmB ,
i
i
p
P
M базисные числа im находим из выражения
.mod1
iii pMm
Следует отметить, что при использовании многоразрядных чисел все из-
вестные методы поиска обратного элемента im (полный перебор всех возмож-
ных вариантов, использование алгоритма Евклида или теоремы Эйлера) имеют
большую вычислительную сложность. Задача упрощается в совершенной форме
СОК (СФ СОК) [13], когда модули рi подобраны таким образом, что все .1im
Это исключает необходимость поиска обратного элемента по модулю и уменьша-
ет вычислительную сложность использования СОК. Однако в случае ограничен-
ного количества модулей или необходимости использования модулей, которые
мало отличаются один от другого, СФ СОК неприменима. В [14] рассмотрены
условия для аналитического вычисления базисных чисел. В [15] предложена мо-
дифицированная СФ СОК (МСФ СОК), в которой базисные числа ,1im и ана-
логично СФ СОК нет надобности вычислять обратный элемент по модулю. Одна-
ко
в настоящее время неизвестны методы построения системы модулей для МСФ СОК.
Исходя из вышесказанного, цель настоящей работы — развитие теории и мето-
дов нахождения системы модулей для МСФ СОК для уменьшения вычислитель-
ной сложности задач путем использования СОК.
Теория и метод построения системы модулей
Для упрощения ограничимся тремя модулями. Пусть ,1 ap bap 2
(причем a и b взаимно простые). Согласно условиям МСФ СОК [15] должна вы-
полняться система
.1mod)(
,1mod)(
,1)mod(
3
3
3
pbaa
apba
baap
(2)
Рассмотрим сначала первые два уравнения (2), которые с учетом преобразо-
ваний )(mod)(mod 33 babpbaap и abpapba modmod)( 33 представим
таким образом:
,1mod
,1)(mod
ay
bay
(3)
где .3bpy
Далее необходимо использовать расширенный алгоритм Евклида и китай-
скую теорему об остатках для чисел а и (a+b). Обратные элементы будем искать
методом, предложенным в [16], т.е. к единице добавляется модуль и проверяется,
делится ли нацело полученный результат на соответствующее число. Если нет, то
опять добавляется модуль и выполняется указанная проверка. Итак,
,
1)(
)mod()mod( 111
b
bak
babbaa
(4)
,
1
modmod)( 211
b
ak
ababa
(5)
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 4 111
где 21, kk равняются количеству добавленных модулей (a b) и а соответственно.
Равенство коэффициентов kkk 21 в обоих выражениях подтверждается
записью результата для расширенного алгоритма Евклида:
.1
)1)(()1)((
b
baka
b
kaba
(6)
Используя (6) и китайскую теорему об остатках для четырех случаев, запи-
санных в (3): (1; 1), (1; – 1), (– 1; 1), (– 1; – 1), получим:
1) ;1)(mod baay
2)
)(mod
222
)(mod
2
baa
b
bakabka
baay
);(mod
)1(2
12)(mod
2)(2
baa
b
kaa
kabaa
b
babaka
3)
)(mod
222
)(mod
2
baa
b
bakabka
baay
);(mod
12
12)(mod
2)(2
baa
b
kaa
kabaa
b
babaka
4) .1)(mod baay
Второй и третий случаи сложные для анализа, и, как показывает практика,
для них получается или ,23 pp или вообще не выполняется третье уравнение
системы (2). По аналогии с (4), (5) первый и четвертый случаи приводят к таким
результатам:
,
1)(
)(mod 31
3
b
baak
baabp
(7)
,
1)()(1)(
)(mod 331
3
b
baakb
b
baak
baabp
(8)
где 3k равняется количеству добавленных модулей ).( baa
Из третьего уравнения системы (2), учитывая (7), (8), получаем:
,1
1)(
mod)( 3
b
baak
baa (9)
.1
1)()(
mod)( 3
b
baakb
baa (10)
Выражение под функцией mod в (9), (10) надо умножить на b, и это произве-
дение должно быть на единицу больше или меньше ).( baa Это возможно при
13 k или .13 kb Итак, получаем окончательное выражение для нахождения
третьего модуля:
,
12
3
b
a
ap
(11)
который по абсолютной величине на
b
a 12
больше первого.
Отсюда следует условие, при выполнении которого существует третий мо-
дуль для МСФ СОК:
112 ISSN 0572-2691
.1mod2 ba (12)
Уравнение (11) объясняет, почему при заданном а не для всех b можно подобрать
третий модуль для МСФ СОК. Кроме того, из (11) видно, что ,ab иначе .23 pp
На рис. 1 показана поверхность, которая ха-
рактеризует зависимости р3 от значений модулей
р1 и р2 согласно (11) при условии .12 pp
Как видно из графика, р3 достигает макси-
мума, когда 1p и 2p приблизительно однаковы
(при этом р1 максимально). С увеличением 2p
модуль 3p уменьшается и при максимальном
значении второго модуля 2p и 3p принимают
приблизительно одинаковые значения.
В табл. 1 представлены возможные наборы
для трех модулей МСФ СОК при 111 p и их произведение (в скобках — разряд-
ность этих чисел), которое указывает условие переполнения разрядной сетки.
Таблица 1
№ b p2 p3
P
1 1 12(4) 133(8) 17556(15)
2 1 12(4) 131(8) 17292(15)
3 2 13(4) 72(7) 10296(14)
4 2 13(4) 71(7) 10153(14)
5 3 14(4) 51(6) 7854(13)
6 4 15(4) 41(6) 6765(13)
7 5 16(5) 35(6) 6160(13)
8 6 17(5) 31(5) 5797(13)
9 7 18(5) — —
10 8 19(5) 26(5) 5434(13)
11 9 20(5) — —
12 10 21(5) 23(5) 5313(13)
Проанализировав табл. 1, можно сделать вывод, что при использовании трех
модулей МСФ СОК разрядность чисел, над которыми выполняются арифметиче-
ские операции, уменьшается в 22,5 раза. Кроме того, значению 1b отвечает
два значения ,3p которые на единицу отличаются от произведения двух преды-
дущих модулей. Это следует из (11), поскольку в этом случае .1)1(3 aap
Также два значения 3p получается при ,2b поскольку р1 нечетное, поэтому оба
числа 12
1 p делятся без остатка на 2. При 7b и 9b целого значения р3 не
существует, поскольку 11
2
mod 7 1 и 11
2
mod 9 1.
Для дальнейшего исследования модулей 2p и 3p табл. 1 необходимо транс-
формировать (табл. 2).
Таблица 2
№ p2 p3 № p2 p3
1 12 133 6 15 41
2 12 131 7 16 35
3 13 72 8 17 31
4 13 71 9 19 26
5 14 51 10 21 23
900
700
10
500
300
30
100
50
30
25 20 15 10 5
p2
p1
p3
Рис. 1
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 4 113
На рис. 2 показан график значений модулей 2p и 3p в зависимости от их номе-
ра согласно табл. 2, где ось абсцисс — номер модуля, ось ординат — его значение.
140
0
20
40
60
80
100
120
1 3 2 5 7 9 4 6 8 10
Рис. 2
Как видно из графика, модуль 2p медленно увеличивается с увеличением его
номера. В то же время значение 3p уменьшается намного интенсивнее, и в конце
рассматриваемого диапазона оба модуля практически одинаковы.
Метод построения системы модулей модифицированной
совершенной формы системы остаточных классов
с использованием последовательности Фибоначчи
Интересен случай, когда третий модуль равняется сумме абсолютных вели-
чин двух предыдущих. Тогда из (11) можно получить .2
12
ba
b
a
a
Пере-
ходя к квадратному уравнению 0)1( 22 aabb относительно b и упуская его
отрицательные корни, находим
.
2
45 2
aa
b (13)
Это означает, что в (13) подкорневое выражение )45( 2 a должно быть пол-
ным квадратом некоторого числа. Численные исследования показывают, что дан-
ному условию удовлетворяет последовательность Фибоначчи: 1, 1, 2, 3, 5, 8, 13,
21, 34, 55, 89, 144, 233, 377, … . Этот ряд возникает не только в самых разнооб-
разных математических ситуациях — комбинаторных, численных, геометриче-
ских, но и в биологических системах. Использование данной последовательности
для вычислительных систем приведено, например, в [17].
Аналитически n-й элемент ряда представляется с помощью формулы Бине:
.
52
)51()51(
n
nn
nF
Поэтому целесообразно в общем случае рассмотреть три последовательных
элемента ряда Фибоначчи. Учитывая, что каждый следующий элемент равняется
сумме двух предыдущих )( 12 nnn FFF и квадрат каждого элемента на еди-
ницу отличается от произведения предыдущего и следующего членов
),)1(( 1
11
2
n
nnn FFF получим такую систему:
114 ISSN 0572-2691
.1modmod
,1modmod
,1modmod
2
2
121
1
2
12
2
121
nnnnn
nnnnn
nnnnn
FFFFF
FFFFF
FFFFF
(14)
Итак, чтобы получить набор из трех модулей для МСФ СОК, в котором
третий модуль равняется сумме абсолютных величин двух предыдущих, необ-
ходимо выбрать любые три последовательные элемента из ряда Фибоначчи,
начиная c третьего. На рис. 3 изображены графические зависимости Fn, Fn+1 и Fn+2
для первых 12 элементов последовательностей.
250
0
25
50
75
150
200
225
1 3 2 5 7 9 4 6 8 10
100
125
175
250
F(n)
F1(n)
F2(n)
1
11 12
12 n
Рис. 3
Из рис. 3 видно, что функции быстро возрастают с увеличением числа n.
Следует заметить, что модули МСФ СОК находятся на пересечении вертикальных
линий сетки с построенными графиками, где функции принимают целочисленные
значения, удовлетворяющие условиям системы (14).
Заключение
Теоретические основы и методы поиска системы модулей МСФ СОК, предло-
женные в настоящей работе, позволяют уменьшить вычислительную сложность
СОК за счет избежания наиболее трудоемкой операции — нахождения обратного
элемента по модулю. Приведенный пример и возможный диапазон вычислений по-
казывают, что разрядность чисел, над которыми выполняются арифметические опе-
рации, уменьшается в 22,5 раза. Предложенная теория представлена на примере
трехмодульной системы и является базовой для расчета модифицированной совер-
шенной формы системы остаточных классов для большего количества модулей.
Международный научно-технический журнал
«Проблемы управления и информатики», 2016, № 4 115
М.М. Касянчук, Я.М. Ніколайчук, І.З. Якименко
ТЕОРІЯ ТА МЕТОДИ ПОБУДОВИ СИСТЕМИ
МОДУЛІВ МОДИФІКОВАНОЇ ДОСКОНАЛОЇ
ФОРМИ СИСТЕМИ ЗАЛИШКОВИХ КЛАСІВ
Викладено теоретичні основи та методи пошуку системи модулів модифікова-
ної досконалої форми системи залишкових класів, що дозволяє зменшити об-
числювальну складність за рахунок уникнення найбільш трудомісткої опера-
ції — знаходження оберненого елемента за модулем. Запропонована теорія
представлена на прикладі трьохмодульної системи і є базовою для розрахунку
модифікованої досконалої форми системи залишкових класів для більшої кіль-
кості модулів.
M.N. Kasianchuk, Ya.N. Nykolaychuk, I.Z. Yakymenko
THEORY AND METHODS OF CONSTRUCTING
OF SYSTEM OF MODULES OF MODIFIED FORMS
OF A PERFECT SYSTEM OF RESIDUAL CLASSES
The paper contains the theoretical backgrounds and methods of finding the system
of modules of modified perfect form of a system of residual classes thus reducing the
computational complexity by avoiding of the most labor-intensive operations — find-
ing of the inverse element by module. The proposed theory is presented on examples
of triplemodules system and is the background for the calculation of modified forms
of a perfect system of residual classes for greater number of modules.
1. Рабинович З.Л., Раманаускас В.А. Типовые операции в вычислительных машинах. — Киев:
Техніка, 1980. — 264 с.
2. Исупов К.C., Мальцев А.Н. Способ представления чисел с плавающей точкой большой раз-
рядности, ориентированный на параллельную обработку // Вычислительные методы и про-
граммирование. — 2014. — 15. — С. 631–643.
3. Omondi A. Premkumar B. Residue number systems: theory and implementation. — London :
Imperial College Press, 2007. — 296 p.
4. Червяков Н.И. Арифметическое устройство в системе остаточных классов. А.С. №857992,
БИ № 31. — 1981.
5. Полисский Ю.Д. Алгоритмы выполнения немодульных операций сравнения чисел в моду-
лярной системе остаточных классов // Технологический аудит и резервы производства. —
2012. — 5, № 2(7). — С. 43–44.
6. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных классах. — М. : Сов.
радио, 1968. — 440 с.
7. Задирака В.К. Олексюк А.С. Компьютерная арифметика многоразрядных чисел. — Киев :
Научное издание, 2003. — 264 с.
8. Теория алгоритмов RSA и Эль-Гамаля в разграниченной системе исчисления Радемахера–
Крестенсона / М.Н. Касянчук, И.З. Якименко, О.И. Волынский, И.Р. Питух // Вестник
Хмельницкого национального университета — 2011. — № 3. — С. 265–273.
9. The use of modified correction code based on residue number system in WSN / V. Yatskiv,
N. Yatskiv, Su Jun, A. Sachenko, H. Zhengbing // Proceedings of the 7-th IEEE International Con-
ference on Intelligent Data Acquisition and Advanced Computing Systems (IDAACS’2013). —
Berlin, Germany. — 2013. — 1. — P. 513–516.
10. Цокур Э.А. Использование системы остаточных классов для повышения надежности циф-
ровых многоканальных систем передачи информации: Дис. … канд. техн. наук: 05.13.17.
— Красноярск, 2001. — 179 с.
11. Модулярные параллельные вычислительные структуры нейропроцессорных систем // Н.И.
Червяков, П.А. Сахнюк, А.В. Шапошников, С.А. Ряднов. — М. : Физматлит, 2002. — 288 с.
12. Бухштаб А.А. Теория чисел. — М. : Просвещение, 1966. — 384 с.
13. Николайчук Я.Н. Теория источников информации. — Тернополь: ООО «Терно–граф»,
2010. — 536 с.
116 ISSN 0572-2691
14. Nykolaychuk Ya.M. Kasianchuk M.M., Yakymenko I.Z. Theoretical Foundations for the Analytical
Computation of Coefficients of Basic Numbers of Krestenson’s Transformation // Cybernetics
and Systems Analysis. — 2014. — 50, N 5. — P. 649–654.
15. Касянчук М.Н. Теория и математические закономерности совершенной формы системы
остаточных классов // Труды Международного симпозиума «Вопросы оптимизации вычис-
лений (ПОО–ХХХV)». — Кацивели. — 2009. — С. 306–310.
16. Касянчук М.М., Николайчук Я.М., Якименко І.З. Теорія алгоритмів перетворень китайскої
теореми про залишки в матрично-розмежованому базисі Радемахера–Крестенсона // Вісник
Національного університету «Львівська політехніка». Комп’ютерні системи та мережі. —
2010. — № 688. — С. 118–125.
17. Stakhov A. The generalized principle of the golden section and its applications in mathematics,
science and engineering. — Chaos, Solitons & Fractals. — 2005. — 26, N 2. — Р. 263–289.
Получено 30.10.15
После доработки 18.01.2016
http://link.springer.com/search?facet-author=%22Ya.+M.+Nykolaychuk%22
http://link.springer.com/search?facet-author=%22M.+M.+Kasianchuk%22
http://link.springer.com/search?facet-author=%22I.+Z.+Yakymenko%22
http://link.springer.com/journal/10559
http://link.springer.com/journal/10559
http://link.springer.com/journal/10559/50/5/page/1
|