Швидкодіючий алгоритм та процесор порівняння чисел у системі залишкових класів базису Крестенсона
У статті досліджено можливості СЗК для побудови алгоритму порівняння чисел, а також створення
 схемотехнічної моделі повнофункціонального 16-розрядного процесора. В статье исследованы возможности системы остаточных классов для создания алгоритма сравнения
 чисел, а также создание схе...
Збережено в:
| Дата: | 2008 |
|---|---|
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Українська |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2008
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/6978 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Швидкодіючий алгоритм та процессор порівняння чисел у системі залишкових класів базису Крестенсона / Я.М. Николайчук, О.І. Волинський, С.В. Кулина // Штучний інтелект. — 2008. — № 3. — С. 348-352. — Бібліогр.: 3 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1860103064899289088 |
|---|---|
| author | Николайчук, Я.М. Волинський, О.І. Кулина, С.В. |
| author_facet | Николайчук, Я.М. Волинський, О.І. Кулина, С.В. |
| citation_txt | Швидкодіючий алгоритм та процессор порівняння чисел у системі залишкових класів базису Крестенсона / Я.М. Николайчук, О.І. Волинський, С.В. Кулина // Штучний інтелект. — 2008. — № 3. — С. 348-352. — Бібліогр.: 3 назв. — укр. |
| collection | DSpace DC |
| description | У статті досліджено можливості СЗК для побудови алгоритму порівняння чисел, а також створення
схемотехнічної моделі повнофункціонального 16-розрядного процесора.
В статье исследованы возможности системы остаточных классов для создания алгоритма сравнения
чисел, а также создание схемотехнической модели полного функционального 16-разрядного процессора.
|
| first_indexed | 2025-12-07T17:29:44Z |
| format | Article |
| fulltext |
«Искусственный интеллект» 3’2008 348
4Н
УДК 681.31
Я.М. Николайчук, О.І. Волинський, С.В. Кулина
Тернопільський національний економічний університет, м. Тернопіль, Україна
Швидкодіючий алгоритм та процесор
порівняння чисел у системі залишкових класів
базису Крестенсона
У статті досліджено можливості СЗК для побудови алгоритму порівняння чисел, а також створення
схемотехнічної моделі повнофункціонального 16-розрядного процесора.
Вступ
В наш час одним з перспективних шляхів розвитку комп’ютерної теорії є вивчення
непозиційних систем числення, а саме системи залишкових класів (СЗК), яка базується на
використанні базису Крестенсона. Одним з основних завданнь в комп’ютерній техніці є
створення повнофункціональних процесорів. Тому незалежно від того, яка з систем роз-
глядається – позиційна чи непозиційна, основним поштовхом для її розвитку є прагнення
створити повнофункціональний процесор чи спецпроцесор, який зможе виконати постав-
лені перед ним задачі.
У даній статті розглянуто можливість створення алгоритмічної моделі вико-
нання операції порівняння та проектування процесора в НДСЗК.
1. Теоретичні основи СЗК
1.1. Теоретичні основи цілочисельної форми
представлення СЗК
В основу цілочисельного перетворення СЗК покладена Китайська теорема
про залишки [1]. Суть прямого перетворення цілочисельної форми СЗК полягає в
тому, що згідно з теоремами про залишки будь-яке ціле число може однозначно
перетворити набором найменших невід’ємних залишків в системі взаємопростих моду-
лів, що відповідає рішенню діафантового рівняння
)(mod iik pbN = ,
яке відповідає цілочисельному рішенню лінійного рівняння:
iiik bpaN += ,
де ai – ранг, bi – найменший невід’ємний залишок.
При цьому діапазон кодування чисел Nk дорівнює:
1
k
i
i
P p
=
=∏ ; 0≤Nk≤P.
Таким чином ціле число Nk однозначно представляється набором залишків bi.
Швидкодіючий алгоритм та процесор порівняння чисел у системі…
«Штучний інтелект» 3’2008 349
4Н
Зворотне перетворення цілочисельної форми СЗК виконується згідно з аналі-
тичним виразом
∑
=
⋅=
k
i
iik PresN Bb
1
)(mod , (1)
де Bi – базисні числа СЗК, які обчислюються згідно з діафантовим рівнянням:
)(mod1 ii
i
i Pm
p
PB ≡⋅= . (2)
1.2. Теоретичні основи нормалізованої
форми представлення СЗК
Теоретичною основою утворення нормалізованої форми СЗК (НСЗК) [2] є нор-
малізація по модулю Р обох частин рівняння зворотнього перетворення цілочисель-
ної форми СЗК:
∑
=
⋅
=
k
i
iik
P
PBb
res
P
N
1
)(mod , (3)
звідки
∑
=
⋅=
k
i
i
ik P
B
bresN
1
0 )1(mod][ ,
а з врахуванням виразу (2) отримаємо:
)1(mod][
1
0 ∑
=
⋅=
k
i i
i
ik p
mbresN або ∑
=
⋅=
k
i
iik mbresN
1
00 ),1(mod][][ (4)
де
i
i
i p
bb =0][ , а .1][0 0 ≤≤ ib
Для забезпечення однозначного кодування даних в НСЗК необхідно вико-
нувати умову:
Pp
1
≤δ .
Дана формула визначає необхідне число розрядів після коми, у відповідній
системі числення при представлені величини 1/Р в нормалізованій формі, тобто
pi
gggggggg
p
n
i
δ
.01
= ,
де g – цифри у відповідній системі числення, ni – число розрядів, до яких
заокруглюється результат ділення з приведенням до меншого цілого, а δр – дробова
частина, яка визначає величину похибки δр, якою нехтують.
Таким чином аналітичний вираз з НСЗК в СЗК отримує вигляд:
PNN kk ⋅= 0]int[ ,
де int – символ операції виділення цілої частини.
Формула перетворення СЗК (1) може бути представлена в наступному вигляді:
∑
=
⋅⋅=
k
i
i
i
ik Pm
p
PbresN
1
)(mod , (5)
де 10 −≤≤ ii pm .
Очевидно, що наявність коефіцієнтів mi в формулі (4) ускладнює реалізацію
алгоритму виконання цілочисельного перетворення СЗК. Дослідження різних набо-
Николайчук Я.М., Волинський О.І., Кулина С.В.
«Искусственный интеллект» 3’2008 350
4Н
рів pi, яким відповідають набори коефіцієнтів mi в теоретико-числовому аспекті
показали, що існують такі набори модулів р1, p2, ..., pk, які відповідають умовам
взаємної простоти з одиничними коефіцієнтами mi(m1=m2=...=mi=...=mk=...=1).
Прикладом такого набору модулів є p1=2, p2=3, p3=5. Для якого P=30, B1=15,
B2=10, B3=6, а m1=m2=m3=1.
Перевагою НСЗК є виконання операцій над залишками в нормалізованій формі,
що спрощує реалізацію процесорів на основі даного базису, за рахунок виключення
нелінійних операцій отримання залишку по кожному з модулів процесора, а також
заміни операції по «mod P» на операцію по «mod 1», яка виконується шляхом прос-
того відкидання цілої частини результату згідно з операцією int.
1.3. Теоретичні основи нормалізованої досконалої
форми представлення СЗК
Теоретичною основою даної форми є рівняння (3), підставивши в яке m1=m2=mk=1,
оттримаємо базове рівняння перетворення НДСЗК у вигляді:
∑
=
=
k
i
ik bresN
1
00 ).1(mod][][ (6)
З рівняння (6) видно, що з перетворення HДСЗК виключена операція множення
і саме перетворення виконується у вигляді сумування нормалізованих залишків [bi]0
по mod 1, що відповідає операції int відкидання цілої частини результату.
При дослідженні наборів модулів, які відповідають нормалізованій досконалій
формі СЗК було з’ясовано, що ці модулі не є оптимальними для реалізації процесорів
певної розрядності. Оскільки довільному набору взаємопростих модулів відповідає
довільний набір коефіцієнтів mi, це обмежує можливості створення процесорів з
оптимальним набором модулів.
Нами запропонований алгоритм приведення будь-якої цілочисельної форми
СЗК до НДСЗК, який реалізується шляхом корекції графа визначення залишків
згідно з розрахованим набором коефіцієнтів mi [3].
Для реалізації 16-бітного процесора оптимальний набір модулів з максималь-
ним діапазоном кодування задається масивом чисел:
pi = (3, 5, 7, 8, 11, 13).
Для даної СЗК:
Діапазон кодування: 1201201311753 =⋅⋅⋅⋅=P .
Базисні числа:
.46,36960
;75,76440
;74,105105
;53,85800
;42,96096
;21,80080
6
5
4
3
2
1
==
==
==
==
==
==
mB
mB
mB
mB
mB
mB
Скоректований граф обчислення залишків згідно з розрахованим набором кое-
фіцієнтів mi буде мати вигляд:
Швидкодіючий алгоритм та процесор порівняння чисел у системі…
«Штучний інтелект» 3’2008 351
4Н
Рисунок 1 – Скоректований граф обчислення залишків
Зі схеми обчислення числа за графом (рис. 1) зрозуміло, що це значно спрощує
перехід в базис Радемахера і виконання операції порівняння чисел.
2. Реалізація алгоритму та сопроцесора
порівняння чисел на основі НДСЗК
2.1. Алгоритм порівняння чисел в НДСЗК
Для виконання операції порівняння двох чисел в НДСЗК потрібно звернутися
до рис. 1. В пам’яті ЕОМ граф обчислення залишків буде відтворений в другій системі
числення (рис. 2).
Рисунок 2 – Двійкове відображення графа обчислення залишків
Для того, щоб виконати операцію порівняння двох нормалізованих чисел в НДСЗК,
потрібно виконати операцію сумування нормалізованих залишків цих чисел згідно з рис. 2.
Підставивши у формулу (6) двійкові коди залишків, взяті з рис. 2 отримаємо формули:
∑
=
=
n
i
ii bresN
1
)2()2,0()2,0( )1(mod][][ , ∑
=
=
n
i
ij aresN
1
)2()2,0()2,0( )1(mod][][ .
Для реалізації алгоритму ділення необхідно виконати операцію порівняння [Ni]0 i [Nj]0.
Николайчук Я.М., Волинський О.І., Кулина С.В.
«Искусственный интеллект» 3’2008 352
4Н
2.1. Алгоритм порівняння чисел в НДСЗК
Для реалізації операції порівняння запропоновано наступну структуру спец-
процесора:
Рисунок 3 – Структура спецпроцесора для виконання операції
порівняння в базисі Крестенсона
Висновок
В роботі запропоновано використання нормалізованої досконалої системи за-
лишкових класів для реалізації швидкодіючого перетворення з СЗК в нормалізовану
двійкову систему запису Радемахера, що дозволяє виконати операцію порівняння
двох чисел у базисі Крестенсона на базі запропонованої структури спецпроцесора.
Це значно спрощує реалізацію операції ділення в СЗК і створює умови для побудови
повнофункціонального процесора СЗК.
Література
1. Акушский И.Я., Юдицкий Д.И. Машинная арифметика в остаточных класах. – М: Сов. радио, 1968. – 440 с.
2. Николайчук Я.М., Федорович Ю.С. Теоретичні основи базисних перетворень СЗК // Матеріали
наукової конференції «Автоматика 2000». – Львів. – 2000. – С. 120.
3. Николайчук Я.М., Волинський О.І., Кулина С.В. Теорія побудови та компоненти швидкодіючих
процесорів на основі досконалої та розмежованої форм системи залишкових класів // Матеріали
проблемно-наукової міжгалузевої конференції «Інформаційні проблеми комп’ютерних систем,
моделювання, економіки та юриспруденції» (SPIS 2008). – Збірник наукових праць Бучацького
інституту менеджменту і аудиту. – 2008 – Т. 1. – Випуск № 4. – С. 31-35.
Я.М. Николайчук, О.И. Волынский, С.В. Кулина
Быстродействующий алгоритм и процессор сравнения чисел в системе остаточных классов
базиса Крестенсона
В статье исследованы возможности системы остаточных классов для создания алгоритма сравнения
чисел, а также создание схемотехнической модели полного функционального 16-разрядного процессора.
Стаття надійшла до редакції 17.07.2008
|
| id | nasplib_isofts_kiev_ua-123456789-6978 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Ukrainian |
| last_indexed | 2025-12-07T17:29:44Z |
| publishDate | 2008 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Николайчук, Я.М. Волинський, О.І. Кулина, С.В. 2010-03-22T12:54:23Z 2010-03-22T12:54:23Z 2008 Швидкодіючий алгоритм та процессор порівняння чисел у системі залишкових класів базису Крестенсона / Я.М. Николайчук, О.І. Волинський, С.В. Кулина // Штучний інтелект. — 2008. — № 3. — С. 348-352. — Бібліогр.: 3 назв. — укр. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/6978 681.31 У статті досліджено можливості СЗК для побудови алгоритму порівняння чисел, а також створення
 схемотехнічної моделі повнофункціонального 16-розрядного процесора. В статье исследованы возможности системы остаточных классов для создания алгоритма сравнения
 чисел, а также создание схемотехнической модели полного функционального 16-разрядного процессора. uk Інститут проблем штучного інтелекту МОН України та НАН України Распознавание образов. Системы цифровой обработки сигналов и изображений Швидкодіючий алгоритм та процесор порівняння чисел у системі залишкових класів базису Крестенсона Быстродействующий алгоритм и процессор сравнения чисел в системе остаточных классов базиса Крестенсона Article published earlier |
| spellingShingle | Швидкодіючий алгоритм та процесор порівняння чисел у системі залишкових класів базису Крестенсона Николайчук, Я.М. Волинський, О.І. Кулина, С.В. Распознавание образов. Системы цифровой обработки сигналов и изображений |
| title | Швидкодіючий алгоритм та процесор порівняння чисел у системі залишкових класів базису Крестенсона |
| title_alt | Быстродействующий алгоритм и процессор сравнения чисел в системе остаточных классов базиса Крестенсона |
| title_full | Швидкодіючий алгоритм та процесор порівняння чисел у системі залишкових класів базису Крестенсона |
| title_fullStr | Швидкодіючий алгоритм та процесор порівняння чисел у системі залишкових класів базису Крестенсона |
| title_full_unstemmed | Швидкодіючий алгоритм та процесор порівняння чисел у системі залишкових класів базису Крестенсона |
| title_short | Швидкодіючий алгоритм та процесор порівняння чисел у системі залишкових класів базису Крестенсона |
| title_sort | швидкодіючий алгоритм та процесор порівняння чисел у системі залишкових класів базису крестенсона |
| topic | Распознавание образов. Системы цифровой обработки сигналов и изображений |
| topic_facet | Распознавание образов. Системы цифровой обработки сигналов и изображений |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/6978 |
| work_keys_str_mv | AT nikolaičukâm švidkodíûčiialgoritmtaprocesorporívnânnâčiselusistemízališkovihklasívbazisukrestensona AT volinsʹkiioí švidkodíûčiialgoritmtaprocesorporívnânnâčiselusistemízališkovihklasívbazisukrestensona AT kulinasv švidkodíûčiialgoritmtaprocesorporívnânnâčiselusistemízališkovihklasívbazisukrestensona AT nikolaičukâm bystrodeistvuûŝiialgoritmiprocessorsravneniâčiselvsistemeostatočnyhklassovbazisakrestensona AT volinsʹkiioí bystrodeistvuûŝiialgoritmiprocessorsravneniâčiselvsistemeostatočnyhklassovbazisakrestensona AT kulinasv bystrodeistvuûŝiialgoritmiprocessorsravneniâčiselvsistemeostatočnyhklassovbazisakrestensona |