Інтернет-конференції НУБіП України, ГЛОБАЛЬНІ ТА РЕГІОНАЛЬНІ ПРОБЛЕМИ ІНФОРМАТИЗАЦІЇ В СУСПІЛЬСТВІ І ПРИРОДОКОРИСТУВАННІ ’2024

Розмір шрифту: 
АЛГОРИТМ ВИКОНАННЯ ОПЕРАЦІЇ ДІЛЕННЯ ЦІЛИХ ЧИСЕЛ У ВИГЛЯДІ ВІДОБРАЖЕНЬ
Борис Семенович Гусєв, Олександр Вікторович Самощенко, Олег Миколайович Кулініч

Остання редакція: 19-11-2024

Тези доповіді


Борис Гусєв

кандидат технічних наук, доцент, доцент

Національний університет біоресурсів і природокористування України,

кафедра комп’ютерних систем, мереж та кібербезпеки, Київ, Україна

https://orcid.org/0000-0003-1658-7822

gusevbs@nubip.edu.ua

Олександр Самощенко

кандидат технічних наук, доцент, доцент

Київський національний університет імені Тараса Шевченка,

кафедра комп'ютерної інженерії, м. Київ, Україна

https://orcid.org/0000-0001-9999-476X

aleksandr.samoshchenko@gmail.com

Олег Кулініч

кандидат технічних наук, доцент, доцент

Національний університет біоресурсів і природокористування України,

кафедра комп’ютерних систем, мереж та кібербезпеки, Київ, Україна

https://orcid.org/0000-0002-0643-6898

o.kulinich@nubip.edu.ua

АЛГОРИТМ ВИКОНАННЯ ОПЕРАЦІЇ ДІЛЕННЯ ЦІЛИХ ЧИСЕЛ

У ВИГЛЯДІ ВІДОБРАЖЕНЬ

Анотація. Арифметична операція ділення цілих чисел представлена за допомогою перетворення поліномів доповняльних кодів (ДК). Перевага математичної моделі характеризується формуванням поліномів додатних та від'ємних цілих чисел одним виразом. Визначена залежність області визначення відображення операндів в ДК та розрядності полінома, а також сформований алгоритм визначення спеціального полінома частки при всіх можливих комбінацій значення знакових розрядів. При цьому показано, що поліном частки визначається за допомогою значень знакових розрядів часткових залишків діленого, які, в свою чергу, визначаються за допомогою додавання перетвореного або неперетвореного ДК дільника до зсунутого на один розряд вліво коду попереднього ДК часткового залишку. Доведено, що збільшення значення ДК часткового залишку діленого зводиться до модифікованого зсуву вліво ДК залишку діленого з втратою знакового розряду. Сформовані логічні вирази для фіксації ознаки переповнення частки. Приведений алгоритм перетворення полінома частки в підсумковий ДК частки. Для математичного опису ДК цілих чисел використовується зміщений по модулю код. Задача ділення цілих чисел зведена до операції ділення поліномів ДК. Запропонований алгоритм для визначення поліному частки, що не залежить від знаків операндів. Сформований алгоритм обчислення коректного ДК залишку діленого для всіх комбінацій знакових розрядів операндів.

Ключові слова: комп’ютерне подання даних; комп’ютерне ділення; зміщений код; доповняльний код; залишок від ділення; ознака переповнення.

1. ВСТУП

В сучасних комп’ютерних системах при виконанні операції цілочислового ділення використовуються операнди, представлених у вигляді зображень, як правило, з використанням ДК. Операція ділення виконується над операндами сумісно з їх знаками, а результат відразу представляється у вигляді зображень початкових даних.

Постановка проблеми. Проєктування апаратних засобів комп’ютерних систем, зокрема арифметичних пристроїв, передбачає застосування нових підходів до організації обчислювальних процесів, які забезпечують виконання заданих операцій.

Арифметична операція ділення цілих чисел, представлених у вигляді відображень, відрізняється достатньою алгоритмічною складністю, тому для забезпечення реалізації більш оптимальних структур арифметичних пристроїв необхідно розглянути теоретичні засади побудови, математичні моделі, що дозволять виконувати розробку і оптимізацію методів виконання арифметичних операцій, а також практичну реалізацію арифметичних пристроїв, призначених для виконання операцій ділення операндів з фіксованою комою, представлених у вигляді сучасних комп’ютерних відображень.

Аналіз останніх досліджень і публікацій. Операція ділення цілих чисел, представлених в ДК, є беззаперечною складовою перетворень в сучасних комп'ютерних системах [1], [2]. У зв’язку з достатньою алгоритмічною складністю цієї операції велика увага приділяється необхідності оптимізації ресурсів операційних пристроїв ділення [2]. В значній мірі зміст досліджень стосується використання додатних операндів, в результаті чого отримані ефективні методики створення пристроїв ділення беззнакових чисел. Крім цього, запропоновані методики створення пристроїв ділення знакових чисел, які передбачають алгоритмічну та апаратну модифікацію блока ділення додатних чисел [3], [4]. Достовірність таких рішень в значній мірі обґрунтована результатами чисельних експериментів [5], [6]. Альтернативним варіантом створення пристроїв ділення цілих чисел в ДК є зведення і розв’язок вказаної задачі до операції ділення поліномів ДК знакових чисел з узагальненим алгоритмом визначення спеціального полінома частки при усіх комбінаціях знаків операндів.

Мета публікації. Метою дослідження є розв’язок задачі виконання ділення в системі ДК, що ґрунтується на використанні теорії зміщених кодів, понятті модульності при кодуванні, контролі ознаки переповнення за результатами аналізу знаків операндів та часткового залишку діленого, що дозволяють підвищити ефективність виконання операцій ділення цілих чисел у вигляді відображень.

2. ТЕОРЕТИЧНІ ОСНОВИ

Обчислення частки від ділення цілих чисел визначено співвідношенням AB ∙ D C, де A = ±ǀAǀ, B = ±ǀBǀ, C = ±ǀCǀ, D = ±ǀDǀ – коди діленого, дільника, частки та залишку відповідно, причому ǀCǀ < ǀBǀ. Відображення дільника, частки і залишку в ДК вказано n-розрядним поліномом OpK(n,1) = [NOp] OpK(n-1,1) = (VOp)mVV∙ NOpOp, де n розрядність операндів, (n,1) – поле розрядів операнду від n до 1, V2n – параметр відображення n- розрядного ДК, (X)mV – позначення процедури обчислення залишку коду X за модулем V, OpK(n-1,1) – n-розрядні ДК операндів, NOp – значення знакового розряду операнду. Область визначення n-розрядної функції OpK(n,1) для дільника, частки та залишку визначається за виразом Op [0;V/2 1], якщо Op 0 і Op [-V/2; -1], якщо Op < 0. Область визначення 2n-розрядної функції діленого AK(2n,1) визначається як A [0;V2/2 1], якщо A 0 і A [-V2/2; -1], якщо A < 0. Далі в роботі аналітично визначаються результати обчислення частки та залишку при різних комбінаціях знаків діленого і дільника, в результаті чого отримані аналітичні вирази для визначення залишку ілюструють однакові результати незалежно від знаків операндів.

3. РЕЗУЛЬТАТИ ТА ОБГОВОРЕННЯ

В роботі запропонована математична модель для виконання операції ділення цілих чисел у вигляді відображень з використанням перетворення поліномів ДК:

1. Математична модель характеризується формуванням поліномів додатних та від'ємних цілих чисел за допомогою одного виразу.

2. Визначена залежність області визначення відображення операндів в ДК та розрядності полінома.

3. Сформований алгоритм визначення спеціального полінома частки при всіх можливих комбінацій значення знакових розрядів. Показано, що поліном частки визначається за допомогою значень знакових розрядів часткових залишків діленого, які визначаються за допомогою додавання перетвореного або неперетвореного ДК дільника до зсунутого на один розряд вліво коду попереднього часткового залишку. Приведений алгоритм перетворення полінома частки в підсумковий код частки не залежить від знаків операндів.

Для математичного опису ділення ДК цілих чисел використовується зміщений за модулем код. Задача ділення цілих чисел зведена до операції ділення поліномів ДК. Сформований алгоритм обчислення коректного залишку діленого для всіх комбінацій знакових розрядів операндів.

ВИСНОВКИ ТА ПЕРСПЕКТИВИ ПОДАЛЬШИХ ДОСЛІДЖЕНЬ

Запропонований підхід для формалізованого опису операції ділення цілих операндів, що базується на використанні зміщеного кодування і виконанні дій за допомогою пріоритетного використання модулярності даних, показав методологічну повноту, чітку математичну послідовність висновків та коректність отриманих результатів.

Наукова новизна результатів полягає у формулюванні теоретичних положень з метою синтезу базових арифметичних пристроїв та розв'язання задачі визначення характерних ознак в операціях ділення цілих операндів. Практична реалізація наведеного підходу дозволяє отримати схеми для ефективного виконання однієї з основних комп'ютерних арифметичних операцій. Запропонований метод передбачає кодування додатних та від’ємних цілих чисел відповідно до однакової математичної залежності.

Перспективність результатів дослідження, ґрунтується на доведених математичних відношеннях, нескладності запропонованого алгоритму операції ділення та можливості створення відповідних конкурентоспроможних пристроїв ділення цілих чисел в ДК.

ПОСИЛАННЯ

[1] William Stallings, Computer organization and architecture: designing for performance, 10th ed. Pearson Education, Inc, 2016, 864 p.

[2] Udayan Patankar, Ants Koel, Review of Basic Classes of Dividers Based on Division Algorithm. Thomas Johann Seebeck Department of Electronics, Tallinn University of Technology, 19086 Tallinn, Estonia. January, 2021. dоi 10.1109/ACCESS.2021.3055735.

[3] Anila Ann Varghese et al, FPGA Implementation of Area-Efficient IEEE 754 Complex Divider. Procedia Technology, 24 (2016), pp. 1120 – 1126.

[4] S. Subha. A Modified Synthetic Division Algorithm, International Journal of Computational and Applied Mathematics, ISSN 1819-4966 Volume 12, Number 3 (2017), pp. 691-697.

[5] Muhammad Firmansyah Kasim et al, FPGA Implementation of Fixed-Point Divider Using Pre-Computed Values, Procedia Technology, 11 (2013), pp. 206 – 211.

[6] Samoshchenko, O. V., Gusev, B. S., Lapko, V. V., Mathematical description the divide of integer numbers. [Matematichniy opis operatsiy dilennya tsilykh chisel], Naukovi pratsi Donets'koho natsional'noho tekhnichnoho universytetu. Seriya “Informatyka, Kybernetyka ta obchysliuvalna tekhnika”, 2023, No. 2(35)-1(36), pp.85-96.(In Ukrainian), doi:10.31474/1996-1588-2023-1-36-85-96.


Ключові слова


комп’ютерне подання даних; комп’ютерне ділення; зміщений код; доповняльний код; залишок від ділення; ознака переповнення.