УДК:519.95:621.324:681.3(07)

Коноплянко З.Д.

ПАРАЛЕЛЬНІ АЛГОРИТМИ ОБЧИСЛЕННЯ k-ЗНАЧНИХ АРИФМЕТИЧНИХ ОПЕРАЦІЙ

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

 

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

Ключові слова: k-значна структура, кодування, логіка, штучний інтелект, аналіз, синтез.

Аннотация. В работе разработаны и исследованны методы построения параллельных 10-значных алгоритмов суммирования и умножения, которые по своей структуре образуют новую параллельную вычислительную математику, аналогов которой на нынешний день не существует. С другой стороны базовые двухместные алгоритмы добавления и умножения 10-ти значной логики послужат основой для построения параллельных вычислительных алгоритмов систем искусственного интеллекта.

Ключевые слова: k -значна структура, кодировка, логика, искусственный интеллект, анализ, синтез.

Summary. The paper developed and tested methods of parallel 10-digit addition and multiplication algorithms that form the structure a new parallel computational mathematics, analogues to the present day does not exist. On the other hand double basic addition and multiplication algorithms are 10-valued logic to provide a basis for building a parallel computing algorithms of artificial intelligence.

Кеу words: multiple-valued structure, encoding, logic; analysis, synthesis, artificial intelligence.

1. Постановка задачі

У роботі [1] розроблені та досліджені методи побудови багатовходових k-значних універсальних функціональних перетворювачів, які за своєю структурою утворюють нову паралельну обчислювальну математику, аналогів якої на нинішній день не існує. Базові двомісні функції додавання та множення k-значної логіки послужать основою для побудови паралельних обчислювальних алгоритмів систем штучного інтелекту. k-значна логіка є типом формальної логіки, в основі якої лежать натуральні числа, визначені на проміжку  [2].

Оскільки в основі будь-яких алгебр лежать відповідні двомісні функції додавання та множення (в комбінаториці – „+” та „”, в булевій алгебрі – „” та „” тощо), розглянемо двомісні функції k-значної логіки виду , де  – функції, що реалізуються універсальним елементом (мультиплексором) і пробігають усю множину функцій з  однієї змінної, тобто їх можна записати у вигляді одновимірного кортежу. Усі функції визначені на Ek зі значеннями також у . Первісні результати у цій сфері щодо аналізу структури і роботи алгоритмів описані у [2, 3].

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

2.Формалізація моделей

На основі емпіричного синтезу до складу подібного роду обчислювальних алгоритмів входить канал обчислення за модулем modk та канал обчислення прискореного переносу на основі k-значних універсальних функціональних перетворювачів. Відповідно до складу цих каналів увійдуть: елемент розпізнавання k-значної змінної (ПЕ+ДШ); матричний селектор (МС), комутатори (КМ) та ключі (Кл). Роботу цих компонентів описують гранично просторові системи предикатних рівнянь [1, 2]. Відповідні таблиці істинності (табл.1-4), що описують роботу алгоритмів обчислення двомісних функції додавання та множення у десятковій системі числення мають наступний вигляд:

Таблиця 1

Таблиця істинності, що описує роботу каналу множення за модулем 10

mod10

Х2

0

1

2

3

4

5

6

7

8

9

Х1

0

0

0

0

0

0

0

0

0

0

0

1

0

1

2

3

4

5

6

7

8

9

2

0

2

4

6

8

0

2

4

6

8

3

0

3

6

9

2

5

8

1

4

7

4

0

4

8

2

6

0

4

8

2

6

5

0

5

0

5

0

5

0

5

0

5

6

0

6

2

6

4

0

6

2

8

4

7

0

7

4

1

8

5

2

9

6

3

8

0

8

6

4

2

0

8

6

4

2

9

0

9

8

7

6

5

4

3

2

1

 

Таблиця 2

Таблиця істинності, що описує роботу каналу переносу множення за модулем 10


Х2

0

1

2

3

4

5

6

7

8

9

Х1

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

0

2

0

0

0

0

0

1

1

1

1

1

3

0

0

0

0

1

1

1

2

2

2

4

0

0

0

1

1

1

2

2

3

3

5

0

0

1

1

2

2

3

3

4

4

6

0

0

1

1

2

3

3

4

4

5

7

0

0

1

2

2

3

4

4

5

6

8

0

0

1

2

3

4

4

5

6

7

9

0

0

1

2

3

4

5

6

7

8

Таблиця 3

Таблиця істинності, що описує роботу каналу додавання за модулем 10

0

1

2

3

4

5

6

7

8

9

0

0

1

2

3

4

5

6

7

8

9

1

1

2

3

4

5

6

7

8

9

0

2

2

3

4

5

6

7

8

9

0

1

3

3

4

5

6

7

8

9

0

1

2

4

4

5

6

7

8

9

0

1

2

3

5

5

6

7

8

9

0

1

2

3

4

6

6

7

8

9

0

1

2

3

4

5

7

7

8

9

0

1

2

3

4

5

6

8

8

9

0

1

2

3

4

5

6

7

9

9

0

1

2

3

4

5

6

7

8

Таблиця 4


Таблиця істинності, що описує роботу каналу переносу додавання за модулем 10

0

1

2

3

4

5

6

7

8

9

0

0

0

0

0

0

0

0

0

0

0

1

0

0

0

0

0

0

0

0

0

1

2

0

0

0

0

0

0

0

0

1

1

3

0

0

0

0

0

0

0

1

1

1

4

0

0

0

0

0

0

1

1

1

1

5

0

0

0

0

0

1

1

1

1

1

6

0

0

0

0

1

1

1

1

1

1

7

0

0

0

1

1

1

1

1

1

1

8

0

0

1

1

1

1

1

1

1

1

9

0

1

1

1

1

1

1

1

1

1

 

 

 

 

 

 

 

 

 

Структура алгоритмів додавання та множення зображена на рис.1.

Рис. 1. Узагальнена структурна схема алгоритмів і послідовностей дій та їх зв’язки

Оскільки в структурі алгоритму канал переносу безпосередньо пов’язаний із значеннями вхідних змінних, то у ньому немає необхідності у елементі розпізнавання k-значної змінної і матричному селекторі, а комутатор працює від вихідних сигналів спільного матричного селектора. Крім того, канал формування переносу множення вимагає, згідно таблиці істинності (див. табл.2), формування усіх k значень алфавіту і , навпаки – канал формування переносу (див.табл.4) додавання вимагає тільки двох значень – 0 та 1.

Висновки

В роботі отримано формальний метод побудови паралельних структур алгоритмів додавання та множення в 10-значній системі числення.

Це надало можливість формалізувати такі алгоритми та показати можливість уніфікованого підходу до окремих функціональних каналів і повну однорідність самих структур алгоритмів за рахунок гнучкості під час зміни виконуваних операцій.

 

Література

1.    Коноплянко З.Д. Концепції створення паралельної обчислювальної математики на основі k-значних багатовходових універсальних функціональних перетворювачів для систем штучного інтелекту. //Тези доповідей Міжнародної науково-технічної Мультиконференції «Системи та засоби штучного інтелекту».-Донецьк.-ІПШІ «Наука і освіта».-2009.-236 с.

2.    Коноплянко З.Д,, Чаплига В.М., Чаплига М.В. Багатозначні структури та кодування систем економічної кібернетики. -Львів: ЛБІ НБУ, 2004. -314 с.

3.    Пат. 20462 Україна, МКВ H03K 19/08. Двовходовий багатозначний логічний елемент / Бондаренко М.Ф., Коноплянко З.Д., Четвериков Г.Г. – №97031289/24; Заявлено 20.03.97; Опубл. 15.07.97; Бюл. № 3. – 5 с.