Машина баз знань

Реферат: Машина баз знань належить до області обчислювальної техніки та може бути використана при побудові систем, заснованих на знаннях (knowledge-based systems). Машина баз знань містить головний комп'ютер, універсальний процесор, оперативну пам'ять баз знань, пам'ять програм та даних, два блоки вводу-виводу, блок керування, регістр кореня бази знань, перший та другий регістри команд, регістр даних, регістр імені структури, регістр номера слова фрейму, регістр адреси бази знань, регістр координати сліду, регістр вершини сліду, регістр ітерації, регістр істинності, регістр ознак сліду, регістр ознак породження, регістр першої інверсії, регістр другої інверсії, регістр типу фрейму, регістр ознак останнього елемента, додатковий регістр ознак сліду, додатковий регістр ознак породження, одинадцять мультиплексорів, стек адрес даних, стек регістрів, стек ознак, пам'ять сліду, суматор, перший та другий суматори по модулю два. За допомогою запропонованого винаходу досягаються такі переваги: 1) знання зберігаються у вигляді множини визначень термінів та відокремлено від алгоритму їхньої обробки; 2) алгоритм роботи пристрою апаратно "зашитий" у блок керування; 3) знання, що містяться у базі знань, зберігаються у вигляді ієрархічної структури, яка значно підвищує ефективність пошуку рішення за рахунок логічного виводу тільки у необхідній частині бази знань; 4) зберігається структура логічного виводу, яка в подальшому може бути використана для пояснення ходу логічного виводу або породження нової структури даних; 5) надається можливість ефективно зберігати та інтерпретувати ітераційні та рекурсивні структури даних, які містять визначення з використанням відношень альтернативи, послідовності та ітерації. UA 109711 C2 (12) UA 109711 C2 UA 109711 C2 5 10 15 20 25 30 35 40 45 50 55 60 Даний пристрій належить до області обчислювальної техніки та може бути використаний при побудові систем, заснованих на знаннях (knowledge-based systems). Відомий пристрій [SU1455345, 30.01.1989, Устройство для реализации нормальных алгорифмов Маркова // Довгань В.М, Кореневский Н.А., Бойко Ю.Л., Плотников В.В.], який призначено для обробки інформаційних потоків та масивів даних текстового та числового характерів згідно із заданими нормальними алгорифмами та складається із: блока організації підставлення, комутатора, блока пам'яті слова, блока регістрів слова, дешифратора межі слова, блока пошуку входження, блока керування. Більш швидкодіючим є пристрій [SU1635192, 15.03.91, Устройство для реализации подстановок слов // Довгаль В.М., Корольков О.Ф., Керекеша В.В., Старков Ф.А., Шевелев С.С], який дозволяє оброблювати дані символьного та числового типів за допомогою нормальних алгорифмів, які складаються виключно із формул підставлення з двобуквеними лівими та правими частинами, при цьому всі ліві частини (антецеденти) формул паралельно порівнюються із двобуквеним початковим словом (ситуацією) за допомогою асоціативного вузла порівняння. Відомий пристрій складається із: блока пам'яті слів, блока пам'яті входжень, блока пам'яті підстановок, вузла зсуву, комутатора, першого вузла контролю оброблюваного слова, вузла порівняння, блока організації підстановки елементів логіки, лічильника та блока керування. Більш досконалим щодо функціональних можливостей є пристрій [RU2039375, 22.06.1992, Устройство для реализации продукций // ДовгальВ.М, Старков Ф.А., Керекеша В.В., Шевелев С.С, Леонов Е.И.], який складається із: блока пам'яті слів, вузла порівняння, блока керування, регістра символу ситуації, регістра маркера ситуації, блока тегів, блока ідентифікації активної продукції та регістра зсуву показника зчитування. Блоки сполучені між собою за допомогою окремих шин та працюють під керуванням блока керування. Серед головних особливостей відомого пристрою (RU2039375, 22.06.1992) слід відмітити те, що він допускає обробку продукцій нефіксованої довжини. Головним недоліком даного пристрою є те, що продукції у блоці пам'яті слів зберігаються у вигляді символьного масиву нефіксованої довжини. Це призводить до неефективного використання пам'яті слів та до необхідності по-символьної перевірки в процесі співставлення антецедентів. Найближчим до запропонованого є пристрій [US Patent, number 5218669 June 8, 1993, VLSI hardware implemented rule-based expert system apparatus and method (апаратно реалізована система обробки продукційних правил) // Hideaki Kobayashi, Masahiro Shindo], обраний за прототип. Пристрій являє собою співпроцесор та містить: блок керування, блок вводу-виводу, робочу пам'ять, арифметико-логічний блок та оперативну пам'ять. Блок вводу-виводу забезпечує обмін даними та командами між системою обробки продукційних правил та головним комп'ютером. Процесор продукційних правил у складі блока керування, арифметико-логічного блока та робочої пам'яті виконує обробку продукційних правил та реалізований у формі інтегральної мікросхеми. Арифметико-логічний блок виконує команди: порівняння над даними (=, , , =, NOT, AND, OR); переміщення даних; логічного зсуву та переходу. Блок керування керує роботою всіх модулів процесора продукційних правил, а також процесом обміну даними між пам'яттю правил та блоком вводувиводу. Оперативна пам'ять містить набір команд фіксованої довжини. Кожна команда містить такі поля: "тип команди", "прапор" (умова (соndition)/дія (action)) та два операнди. Якщо поточна команда у полі "прапор" містить умову, то відбувається порівняння операндів у залежності від коду поля "тип команди". Якщо команда характеризується як дія, то над поточними операндами виконується дія, зазначена у полі "тип команди". Серед недоліків прототипу можна вказати наступні. 1) Необхідність виконання великої кількості обчислень у процесі пошуку активної продукції при співставленні антецедентів. Це пов'язано із тим, що між продукційними правилами, які містяться в оперативній пам'яті у вигляді команд спеціального формату, відсутній ієрархічний зв'язок. 2) Відсутність механізму пояснення логічного виводу. 3) Відсутність ефективного представлення у пам'яті ітераційних та рекурсивних структур. Спільними ознаками прототипу та запропонованої моделі є оперативна пам'ять баз знань, блок керування, перший блок вводу-виводу та головний комп'ютер, через перший блок вводувиводу підключений до системної шини. В основу моделі поставлена задача побудови спеціалізованої машини баз знань. Всяка задача, поставлена у вигляді імені функції та значення її аргументу, вирішується дедуктивним виводом рішення у процесі інтерпретації бази знань. База знань складається із структури взаємозв'язаних визначень термінів, кожне з яких представляється у формі одного з п'яти фреймів: альтернативи, послідовності, ітерації, текстової константи або терміналу. Усякий 1 UA 109711 C2 5 10 15 20 25 30 35 40 45 50 55 60 фрейм - послідовність слів фіксованої довжини (наприклад, трибайтових), серед яких розрізняється перше слово, а в кожному зі слів - перший байт і наступні. Фрейми текстової константи й терміналу - однослівні, ітерації - двослівні, альтернативи й послідовності багатослівні. Фрейми визначень всіх термінів всякої бази знань розміщено у пам'яті бази знань у вигляді ієрархічної структури, що усуває проблему множини конфліктних правил. Такий принцип організації бази знань дозволяє ефективно зберігати та інтерпретувати ітераційні й рекурсивні структури визначень. Ще однією важливою відмінністю системи обробки знань є те, що структура процесу інтерпретації, процесу виводу рішення зберігається спеціальними засобами ведення сліду. З метою розширення функціональних можливостей інтерпретації рекурсивних, ітераційних та вкладених структур і формування структури виводу рішення задачі у прототип, що містить оперативну пам'ять баз знань, блок керування, перший блок вводу-виводу та головний комп'ютер, через перший блок вводу-виводу підключений до системної шини, введено універсальний процесор, пам'ять програм та даних, другий блок вводу-виводу, регістр кореня бази знань, перший та другий регістри команд, регістр даних, регістр імені структури, регістр номера слова фрейму, регістр адреси бази знань, регістр координати сліду, регістр вершини сліду, регістр ітерації, регістр істинності, регістр ознак сліду, регістр ознак породження, регістр першої інверсії, регістр другої інверсії, регістр типу фрейму, регістр ознак останнього елемента, додатковий регістр ознак сліду, додатковий регістр ознак породження, одинадцять мультиплексорів, стек адрес даних, стек регістрів, стек ознак, пам'ять сліду, суматор, перший та другий суматори по модулю два, при цьому системною шиною машини поєднані пам'ять програм та даних, універсальний процесор та перші входи-виходи другого блока вводу-виводу, чий другий вхід-вихід підключено до першого входу-виходу регістра даних, другий вхід-вихід якого підключено до входу-виходу стека адрес даних, перший вихід другого блока вводу-виводу підключено до входу регістра кореня бази знань, чий вихід підключено до другого входу першого мультиплексора, вихід якого підключено до входу регістра імені структури, чий вихід з'єднано із першими входами десятого мультиплексора і першого регістра команд та з другим входом четвертого мультиплексора, вихід якого підключено до входу регістра номера слова фрейму, чий вихід підключено до першого входу стека регістрів та до першого входу суматора, вихід якого підключено до першого входу четвертого мультиплексора та до другого входу десятого мультиплексора, чий вихід підключено до входу регістра адреси бази знань, з'єднаного виходом із адресним входом оперативної пам'яті бази знань, перший інформаційний вихід якої підключений до перших входів першого мультиплексора та сьомого мультиплексора, чий вихід підключено до входу регістра координати сліду, вихід якого з'єднаний із адресним входом пам'яті сліду, інформаційним входом оперативної пам'яті бази знань та із входом регістра вершини сліду, чий вихід підключено до другого входу стека регістрів та до третього входу сьомого мультиплексора, другий вхід якого підключений до другого виходу стека регістрів, чий перший вихід підключено до третього входу четвертого мультиплексора, вихід першого регістра команд підключено до входу другого блока вводу-виводу, чий другий вихід підключено до входу другого регістра команд, перший вихід якого підключено до першого входу блока керування, а другий вихід підключено до перших входів другого, третього, шостого та дев'ятого мультиплексорів, вихід ознак оперативної пам'яті бази знань підключено до входів додаткових регістрів ознак сліду, ознак породження та до других входів п'ятого, шостого, восьмого та дев'ятого мультиплексорів, вихід додаткового регістра ознак сліду підключено до другого входу другого мультиплексора, вихід додаткового регістра ознак породження підключено до другого входу третього мультиплексора, треті входи другого, третього, шостого, дев'ятого і другі входи п'ятого та восьмого мультиплексорів підключені до виходу стека ознак, а виходи другого, третього, п'ятого, шостого, восьмого і дев'ятого мультиплексорів з'єднані із входами регістрів ознак сліду, ознак породження, першої інверсії, другої інверсії, типу фрейму та ознак останнього елемента відповідно, перші виходи регістрів ознак сліду, ознак породження, типу фрейму та ознак останнього елемента підключено до третього входу першого регістра команд та другого входу блоку керування, чий вихід підключено до другого входу першого регістра команд, другі виходи регістрів ознак сліду, ознак породження, першої інверсії, другої інверсії, типу фрейму та ознак останнього елемента підключено до входу стека ознак, перший вихід регістра першої інверсії та третій вихід регістра типу фрейму разом із виходом логічної одиниці підключено до входу ознак оперативної пам'яті баз знань, а третій вихід регістра першої інверсії підключено до першого входу першого суматора по модулю два та до першого входу одинадцятого мультиплексора, перший вихід регістра другої інверсії підключено до першого входу другого суматора по модулю два, чий другий вхід разом із другим входом першого суматора по модулю два та третім входом блока керування підключений до виходу регістра 2 UA 109711 C2 5 10 15 20 25 30 35 40 45 50 55 60 істинності, вхід якого з'єднаний із виходом одинадцятого мультиплексора, чиї другий і третій входи підключені до виходів першого та другого суматора по модулю два відповідно, входивиходи стека ознак з'єднані із входами-виходами пам'яті сліду та регістра ітерації, чий вихід підключений до другого входу суматора та до четвертого входу блока керування. Відмітними ознаками запропонованої машини баз знань від відомого прототипу є: 1) знання зберігаються у вигляді структури взаємозв'язаних визначень термінів та відокремлено від алгоритму їх обробки; 2) алгоритм роботи машини баз апаратно "зашитий" у автомат керування по типу Мура; 3) знання, що містяться у базі знань, зберігаються у вигляді ієрархічної структури, яка значно підвищує ефективність пошуку рішення за рахунок логічного виводу тільки у необхідній частині бази знань; 4) зберігається структура логічного виводу, яка може бути використана для пояснення ходу логічного виводу або породження нової структури даних; 5) надається можливість ефективно зберігати та інтерпретувати ітераційні та рекурсивні структури визначень з використанням відношень кон'юнкції, диз'юнкції та інверсії. На фіг. 1 наведено структуру машини баз знань, на фіг. 2 наведено структуру блока керування, на фіг. 3 наведено структуру багатовхідного регістра, на фіг. 4 наведено структуру реверсивного регістра, на фіг. 5 наведено структуру запису стека 23 регістрів та пам'яті 40 сліду, на фіг. 6 наведено структуру слова оперативної пам'яті 46 бази знань, на фіг. 7 наведено структуру байта ознак слова бази знань та записів стека 45 ознак, на фіг. 8 наведено структуру шаблонів фреймів альтернативи, послідовності, ітерації, текстової константи та терміналу, на фіг. 9 наведено граф алгоритму роботи машини баз знань. У табл. 1 наведено ім'я, формат та призначення регістрів. Машина баз знань (фіг. 1) складається із: головного комп'ютера 1, модуля розширення функціональності 2, спеціалізованого пристрою знань 3, першого блока вводу-виводу 4, універсального процесора 5, пам'яті 6 програм та даних, другого блока вводу-виводу 7, регістра RКБЗ 8 кореня бази знань, першого регістра RКОМ1 9 команд, другого регістра RКОМ2 10 команд, регістра RД 11 даних, стека 12 адрес даних, першого мультиплексора MX1 13, регістра R01 14 імені структури, блока 15 керування, додаткового регістра R07* 16 ознак сліду, другого мультиплексора МХ2 17, регістра R07 18 ознак сліду, додаткового регістра R08*19 ознак породження, третього мультиплексора МХ3 20, регістра R08 21 ознак породження, четвертого мультиплексора МХ4 22, стека 23 регістрів, п'ятого мультиплексора МХ 5 24, регістра R09 25 першої інверсії, регістра R02 26 номера слова фрейму, шостого мультиплексора МХ 6 27, регістра R10 28 другої інверсії, восьмого мультиплексора МХ 8 29, регістра R11 30 типу фрейму, суматора Σ 31, сьомого мультиплексора МХ7 32, регістра RC06 33 ітерації, дев'ятого мультиплексора МХ 9 34, регістра R12 35 ознак останнього елемента, десятого мультиплексора МХ 10 36, регістра RC04 37 координати сліду, регістра R05 38 вершини сліду, регістра R03 39 адреси бази знань, пам'яті сліду 40, регістра R13 41 істинності, одинадцятого мультиплексора МХ 11 42, першого суматора 43 по модулю два, другого суматора 44 по модулю два, стека ознак 45 та оперативної пам'яті бази знань 46. Головний комп'ютер 1 призначений для постановки завдання та зчитування результатів роботи модуля розширення функціональності 2. Універсальний процесор 5 керує роботою компонентів із складу модуля 2 та виконує термінальні програми на замовлення спеціалізованого пристрою знань 3, який розширює набір команд універсального процесора 5 та призначений для швидкої апаратної обробки вхідного завдання. Блок вводу-виводу 7 призначений для організації взаємодії між універсальним процесором 5 та спеціалізованим пристроєм знань 3. Пам'ять 6 зберігає системні програми універсального процесора 5, термінальні програм баз знань, словник термінів, вхідний та вихідний масиви даних. Вхід-вихід головного комп'ютера 1 через перший блок 4 вводу-виводу підключений до системної шини разом із універсальним процесором 5, пам'яттю 6 програм та даних та першими входами-виходами другого блока 7 вводу-виводу. Другий вхід-вихід другого блока 7 вводувиводу підключено до першого входу-виходу регістра RД 11 даних, другий вхід-вихід якого підключено до входів-виходів стека 12 адрес даних. Перший вихід другого блока 7 вводу-виводу підключено до входу регістра RKБЗ 8 кореня бази знань, чий вихід підключено до другого входу першого мультиплексора MX1 13, вихід якого підключено до входу регістра R01 14 імені структури, чий вихід з'єднано із першими входами десятого мультиплексора МХ 10 36 і першого регістра RКОМ1 9 команд та з другим входом четвертого мультиплексора МХ4 22, вихід якого підключено до входу регістра R02 26 номера слова фрейму, чий вихід підключено до першого входу суматора Σ 31 та до першого входу стека 23 регістрів. Вихід суматора Σ 31 підключено до першого входу четвертого мультиплексора МХ4 22 та до другого входу десятого мультиплексора МХ10 36, чий вихід підключено до входу регістра R03 39 адреси бази знань, з'єднаного виходом із адресним входом оперативної пам'яті 46 бази знань. Перший 3 UA 109711 C2 5 10 15 20 25 30 35 40 45 50 55 інформаційний вихід оперативної пам'яті 46 бази знань підключений до перших входів першого мультиплексора МХ1 13 та сьомого мультиплексора МХ7 32, чий вихід підключено до входу регістра RC04 37 координати сліду, вихід якого з'єднаний із адресним входом пам'яті сліду 40, інформаційним входом оперативної пам'яті 46 бази знань та із входом регістра R05 38 вершини сліду. Вихід регістра R05 38 вершини сліду підключено до другого входу стека 23 регістрів та до третього входу сьомого мультиплексора МХ7 32, другий вхід якого підключений до другого виходу стека 23 регістрів, чий перший вихід підключено до третього входу четвертого мультиплексора МХ4 22. Вихід першого регістра команд RКОМ1 9 підключено до входу другого блока 7 вводу-виводу, чий другий вихід підключено до входу другого регістра RКОМ2 10 команд, перший вихід якого підключено до першого входу блока 15 керування, а другий вихід підключено до перших входів другого МХ2 17, третього МХ3 20, шостого МХ6 27 та дев'ятого МХ9 34 мультиплексорів. Вихід ознак оперативної пам'яті 46 бази знань підключено до входів додаткових регістрів ознак сліду R07* 16, ознак породження R08* 19 та до других входів п'ятого МХ5 24, шостого МХ6 27, восьмого МХ8 29 та дев'ятого МХ9 34 мультиплексорів. Вихід додаткового регістра R07* 16 ознак сліду підключено до другого входу другого мультиплексора МХ2 17, вихід додаткового регістра R08* 19 ознак породження підключено до другого входу третього мультиплексора МХ3 20. Треті входи другого МХ2 17, третього МХ3 20, шостого МХ6 27, дев'ятого МХ9 34 і другі входи п'ятого МХ5 24 та восьмого МХ8 29 мультиплексорів підключені до виходу стека 45 ознак. Виходи другого МХ2 17, третього МХ3 20, п'ятого МХ5 24, шостого МХ6 27, восьмого МХ8 29 і дев'ятого МХ9 34 мультиплексорів з'єднані із входами регістрів ознак сліду R07 18, ознак породження R08 21, першої інверсії R09 25, другої інверсії R10 28, типу фрейму R11 30 та ознак останнього елементу R12 35 відповідно. Перші виходи регістрів ознак сліду R07 18, ознак породження R08 21, типу фрейму R11 30 та ознак останнього елемента R12 35 підключено до третього входу першого регістра RКОМ1 9 команд та до другого входу блока 15 керування, чий вихід підключено до другого входу першого регістра RКОМ1 9 команд. Другі виходи регістрів ознак сліду R07 18, ознак породження R08 21, першої інверсії R09 25, другої інверсії R10 28, типу фрейму R11 30 та ознак останнього елемента R12 35 підключено до входу стека 45 ознак. Перший вихід регістра R09 25 першої інверсії та третій вихід регістра R11 30 типу фрейму разом із виходом логічної одиниці підключено до входу ознак оперативної пам'яті 46 баз знань. Третій вихід регістра R09 25 першої інверсії підключено до першого входу першого суматора 43 по модулю два та до першого входу одинадцятого мультиплексора МХ 11 42. Перший вихід регістра R10 28 другої інверсії підключено до першого входу другого суматора 44 по модулю два, чий другий вхід разом із другим входом першого суматора 43 по модулю два та третім входом блока 15 керування підключений до виходу регістра R13 41 істинності. Вхід регістра R13 41 істинності з'єднаний із виходом одинадцятого мультиплексора МХ 11 42, чиї другий і третій входи підключені до виходів першого 43 та другого 44 суматора по модулю два відповідно. Входивиходи стека 45 ознак з'єднані із входами-виходами пам'яті 40 сліду та регістра RC06 33 ітерації, чий вихід підключений до другого входу суматора Σ 31 та до четвертого входу блока 15 керування. Зовнішні вхідні дані, що надходять через блок вводу-виводу 4, призначені для ініціалізації або модифікації вмісту пам'ятей та регістрів. Блок 7 вводу-виводу виконує обмін даними та командами між універсальним процесором 5 та спеціалізованим пристроєм знань 3. За допомогою блока вводу-виводу 7 відбувається початкова ініціалізація вмісту регістрів, ініціалізація та модифікація даних в пам'ятях 12, 23, 40, 45 та 46. Блок 17 керування (фіг. 2) складається із трьох модулів: логіка переходів 47, пам'ять станів 48 та вихідна логіка 49. Блок 15 керування за результатами аналізу кодів на його входах формує на виходах команди керування блоком 7 вводу-виводу та операційною частиною пристрою 3. Логіка переходів 47 визначає наступний стан блока 15 керування, що є функцією від поточного стану пам'яті станів 48 та кодів на входах блока 15 керування. Команди на виходах блока 15 керування визначаються вихідною логікою 49 та є функцією від поточного стану пам'яті станів 48. Структуру багатовхідного регістра (RКОМ1, RКОМ2, RД) зображено на фіг. 3, що складається із мультиплексора MXi та регістра Ri. На вхід регістра Ri надходять дані з виходу MXi та по шині команд. Згідно із командою виконується комутація відповідного входу даних мультиплексора із його виходом. Дані з виходу мультиплексора MXi записуються у регістр Ri. Структуру реверсивного регістра (RC04, RC08) зображено на фіг. 4. Реверсивний регістр складається із мультиплексора МХi, арифметико-логічного пристрою та регістра Ri. На вхід регістра Ri надходять дані з виходу MXi та по шині команд. При надходженні команди 4 UA 109711 C2 5 10 15 20 25 30 35 40 45 50 55 60 виконується комутація вхідних даних та даних на виході арифметико-логічного пристрою із виходом мультиплексора MXi. Дані з виходу мультиплексора MXi записуються у регістр Ri. База знань (БЗ) представляється у формі інформаційної структури множини визначень, вузлами якої є поняття (термінальні - константи чи іменовані процедури, або не термінальні), а дугами - відношення альтернативи, послідовності чи ітерації, що зв'язують поняття (вузли) визначальної частини всякого визначення. Пам'ять 46 бази знань зберігає знання у машинній формі, що складається із множини фреймів, кожний із яких має структуру масиву слів фіксованої довжини (наприклад, 3 байти). Довжина фрейму залежить від типу відношення, яке він описує, та від числа понять у визначальній частині, і може складатись з деякого скінченного числа слів. Пам'ять 40 сліду зберігає структуру виводу рішення задачі. Вона може бути використана для пояснення процесу рішення задачі та при породженні наслідку. Пам'яті стеків адрес даних 12, регістрів 23 та ознак інтерпретації 45 тимчасово зберігають проміжні дані процесу виводу рішення. Якщо на деякому етапі процесу інтерпретації вибраний шлях виявився хибним, то вміст регістрів відновлюється зчитуванням даних із відповідних пам'ятей. На фіг. 6 наведено структуру слів бази знань, із яких складаються фрейми. Кожне слово бази знань містить 24-біти: байт ознак інтерпретації та інформаційне поле. Інформаційне поле залежно від типу поточного фрейму містить: фізичну адресу, що посилається на інший фрейм; фізичну адресу текстової константи або номер (ім'я) термінальної програми. На фіг. 7 наведено структуру байта ознак. Дане поле містить інформацію про тип фрейму та ознаки його інтерпретації. Кожен фрейм (фіг. 8) містить голову та елементи, зв'язані одним відношенням: альтернативи, послідовності чи ітерації. Голова та будь-який з елементів займають декілька послідовно розташованих комірок пам'яті, елементи одного фрейму також розташовуються послідовно, причому голова фрейму розташована першою в даній послідовності. Розмір фреймів (число елементів в одному фреймі) альтернативи чи послідовності може бути довільним, але скінченним. Фрейм ітерації складається із двох компонент: голови та посилання на ітерований елемент, яким є фрейм деякого довільного поняття, за виключенням визначеного у формі ітерації. Цим забезпечується зв'язність різних фреймів у єдину багаторазово вкладену структуру, що може містити рекурсивні конструкції. Складність опису (потужність множини понять, структура їхнього взаємозв'язку) може бути довільною та обмежується ресурсами конкретної реалізації (об'ємом оперативної пам'яті, об'ємом зовнішньої пам'яті, розрядністю вузлів та шин). Ті поняття бази знань, які не визначені через поняття бази знань, є термінальними та містять посилання на константи або термінальні програми, що у подальшому виконуються універсальним процесором 5. Описана таким чином інформаційна структура прикладної області є базою знань прикладної області. На фіг. 9 у формі орієнтованого циклічного графу наведено алгоритм роботи машини баз знань. Пристрій працює наступним чином, безперервно виконуючи алгоритм фіг. 9 від початкової команди "старт" аж до зупинки тактового сигналу. В опису алгоритму використано наступні позначення: СПЗ - спеціалізований пристрій знань, УП - універсальний процесор, БЗ - база знань, ПС - пам'ять сліду, САД - стек адрес даних, СР - стек регістрів, CO - стек ознак, INP пам'ять вхідного масиву даних, OUT - пам'ять вихідного масиву даних, ПП - пам'ять програм. 1. Початкова установка: - Завантаження БЗ; - Завантаження бібліотек термінальних програм в ПП; - Завантаження даних (аргументу обчислювальної функції) в масиви INP і OUT пам'яті ПП; - Установка регістрів у початковий стан, зокрема регістр R11:=00. - Перехід в стан 2. 2. Прийом завдання процесором СПЗ: - Якщо отримано в RKБ3 8 завдання (ім'я функції), то: - прийом від УП в RД 11 адрес даних та через RКОМ2 10 - ознак інтерпретації (режиму інтерпретації в R07, R08, значення інверсії 2 в R10 та в R12:=X); - R01:= адреса кореня БЗ (тобто код регістра RKБ3 8 через мультиплексор МХ1 присвоїти регістру R01); - запис значення регістра RД 11 в стек 12; - запис ознак інтерпретації (R11 - тип фрейму=00, режим інтерпретації - R07=0/1, R08=0/1, R09 інверсії 1=X, R10 - інверсії 2=0/1, R12=X) в стек 45; - перехід в стан 3. 5 UA 109711 C2 5 10 15 20 25 30 35 40 45 50 55 - Якщо через RКОМ2 10 отримано значення істинності, то зберегти його в R13 41 та перейти в стан 21. - Інакше, очікування завдання поверненням до пункту 2. 3. Аналіз завдання і режиму його інтерпретації (R11+R07+R08): - R02:= [R01] (вміст R01 записати в R02); - R03:= [R01] (вміст R01 записати в R03); - Читання із БЗ 46 першого слова фрейму: R07*:= [поле ОС - ознака сліду], R11:= [поле "тип фрейму"], R09:= [поле 1]. - Блок 15 керування аналізує R11, R07 та R08: Якщо R11=(00)&(R07=0/1)&(R08=0/1), то перехід до п. 4 (термінали), Якщо (R11=01/10)&R07=0&R08=0, то перехід до п. 5 (розпізнавання альтернативи), Якщо R11=01&R07=0&R08=1, то перехід до п. 6 (породження альтернативи), Якщо R11=01&R07=1&R08=0, то перехід до п. 8 (розпізнавання альтернативи із слідом), Якщо R11=01&R07=1&R08=1, то перехід до п. 9 (породження альтернативи по сліду), Якщо R11=10&R07=0&R08=1, то перехід до п. 10 (породження послідовності), Якщо R11=10&R07=1&R08=1, то перехід до п. 12 (породження послідовності по сліду), Якщо R11=10&R07=1&R08=0, то перехід до п. 13 (розпізнавання послідовності із слідом), Якщо R11=11&R07=0&R08=0, то перехід до п. 15 (розпізнавання ітерації), Якщо R11=11&R07=0&R08=1, то перехід до п. 17 (породження ітерації), Якщо R11=11&R07=1&R08=0, то перехід до п. 18 (розпізнавання ітерації із слідом), Якщо R11=11&R07=1&R08=1, то перехід до п. 20 (породження ітерації по сліду). 4. Передача термінального завдання процесору УП: - R01:= [перший та другий байти першого слова фрейму, зчитані із БЗ 46]; - Запис RД 11 в стек 12 та ознак інтерпретації (тип фрейму - термінал з регістра R11 поточний режим інтерпретації - R07, R08; інверсія завдання із R09-1) в стек 45; - Передача процесору УП значень RД 11 та значень R01 і ознак інтерпретації через RКОМ1 9; - Перехід в стан 2. 5. Розпізнавання альтернативи: - R02:= [R02] + 1; - R03:= [R02]; - Читання із БЗ 46 другого слова фрейму. R10:= [поле 2], R12:= [поле ОЕ], R07*:= [значення (0/1) ознаки ОС] або R08*:= [значення (0/1) ознаки породження ОП], R01:= [перший та другий байти другого слова фрейму]. - Запис значень регістра RД 11 в стек 12, [R02] - в стек 23. Запис ознак інтерпретації (R11 - тип фрейму альтернативи та R09-1 з першого слова фрейму; R10-2, R12 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R07=0, R08=0) в стек 45; - R07:= R07*; R08:= R08*; - Перехід в стан 3. 6. Породження альтернативи: -R07:= R07*; - Аналіз R07: якщо 0, то перехід в стан 21, інакше - в 7. 7. Встати на слід: - RC04:= [перший та другий байти першого слова фрейму, зчитаного з БЗ 46]; - RC06:= [слово ПС 40, зчитане за адресою RC04]; - R03:= [R02] + [RC06]; - Читання з БЗ 46 за адресою [R03] вибраного слова фрейму. R10:= [поле 2], R12:= [поле ОЕ], R01:= [перший та другий байти вибраного слова фрейму]. - Запис RД 11 в стек 12. Запис ознак інтерпретації (R11 - тип фрейму альтернативи та R09-1 з першого слова фрейму; R10-2, R12 - ОЕ з вибраного слова фрейму та поточний режим інтерпретації - R07=0/1, Ro8=1) в стек 45; - Перехід в стан 3. 8. Розпізнавання альтернативи із слідом: - RC06:= 1; -RC04:=[R05] + 1; - Запис [RC06] в ПС 40 за адресою [RC04]; -R03:=[R02] + [RC06]; - Читання з БЗ 46 за адресою [R03] другого слова фрейму. R10:= [поле 2], R12:= [поле ОЕ], R01:= [перший та другий байти вибраного слова фрейму]. 6 UA 109711 C2 5 10 15 20 25 30 35 40 45 50 55 60 - Запис RД 11 в стек 12, [R05], [R02] - в стек 23. Запис ознак інтерпретації (R11 - тип фрейму альтернативи та R09-1 з першого слова фрейму; R10-2, R12 - ОЕ з вибраного слова фрейму та поточний режим інтерпретації - R07=1, R08=0) в стек 45; - R05:= [RC04]. - Перехід в стан 3. 9. Породження альтернативи по сліду: - RC04:= [RC04] + 1; - RC06:= [ПС 40] за адресою [RC04]; -R03:=[R02] + [RC06]. - Читання з БЗ 46 за адресою [R03] вибраного слова фрейму. R10:= [поле 2], R12:= [поле ОЕ], R01:= [перший та другий байти вибраного слова фрейму]. - Запис RД 11 в стек 12. Запис ознак інтерпретації (R11 - тип фрейму альтернативи та R09-1 з першого слова фрейму; R10-2, R12 - ОЕ з вибраного слова фрейму та поточний режим інтерпретації - R07=1, R08=1) в стек 45. - Перехід в стан 3. 10. Породження послідовності: - R07:= R07*; - Аналіз R07 (біта "ознака сліду", взятого з першого слова фрейму): якщо 1, то перехід в стан 11, інакше - в стан 12. 11. Встати на слід: - RC04:= [перший та другий байти першого слова фрейму, зчитаного з БЗ 46]; - Перехід в стан 12. 12. Породження послідовності по сліду або без сліду: - R02:= [R02] + 1; - R03:= [R02]; - Читання з БЗ 46 другого слова фрейму. R10:= [поле 2], R12:= [поле ОЕ], R01:= [перший та другий байти другого слова фрейму]. - Запис значення RД 11 в стек 12, [R02] в стек 23. Запис ознак інтерпретації (R11 - тип фрейму послідовності та R09-l з першого слова фрейму; R10-2, R12 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R07=0/1, R08=1) в стек 45. - Перехід в стан 3. 13. Розпізнавання послідовності із слідом: - RC06:= 1; - RC04:= [R05]; - R03:=[R02] + [RC06]. = - Читання з БЗ 46 другого слова фрейму. R10: [поле 2], R12:= [поле ОЕ], R01:= [перший та другий байти другого слова фрейму]. - Запис RД 11 в стек 12, [R05], [R02] - в стек 21, [RC06] - в стек 45. Запис ознак інтерпретації (R11 - тип фрейму послідовності та R09 - її з першого слова фрейму; R10-2, R12 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R07=0/1, R08=1) в стек 45. - Перехід в стан 3. 14. Завершити породження ітерації по сліду: - RC06:=[RС06] - 1; -R03:=[R02] + 1; - Читання з БЗ 46 другого слова фрейму. R10:= [поле 2], R01:= [перший та другий байти другого слова фрейму]. - Запис [RС06] в стек 45, [R02] в стек 23. Запис ознак інтерпретації (R11 - тип фрейму ітерації та R09-1 з першого слова фрейму; R10-2 з другого слова фрейму та поточний режим інтерпретації - R07=0/1, R08=1) в стек 45. - Перехід в стан 3. 15. Розпізнавання ітерації: - R03:=[R02] + 1; - Читання з БЗ 46 другого слова фрейму. R10:= [поле 2], R12:= [поле ОЕ], R07*:= [значення (0/1) ознаки розпізнавання із слідом] або R08*:= [значення (0/1) ознаки породження], R01:= [перший та другий байти другого слова фрейму]. - Запис значення регістру [R02] в стек 23. Запис ознак інтерпретації (R11 - тип фрейму ітерації та R09-1 з першого слова фрейму; R10-2, R12 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R07=0, R08=0) в стек 45; - R07:= R07*; R08:= R08*. - Перехід в стан 3. 7 UA 109711 C2 5 10 15 20 25 30 35 40 45 50 55 60 16. Встати на слід: - RС04:= [перший та другий байти першого слова фрейму, зчитаного з БЗ 46]; - RC06:= [ПС 40] за адресою [RC04]. - Якщо лічильник [RС06]  0, то перехід в стан 14, інакше - в стан 19. 17. Породження ітерації: -R07:= R07*; - Аналіз R07 (біта "ознака сліду", взятого з першого слова фрейму): якщо 1, то переходимо в стан 16, інакше - в 19. 18. Розпізнавання ітерації із слідом: - RC04:= [R05] + 1; - RC06:=0; - Запис [RС06] в ПС 40 по адресу RC04; - R03:=[R02] + 1. - Читання з ОЗУ БЗ 46 другого слова фрейму. R10:= [поле 2], R01:= [перший та другий байти другого слова фрейму]. - Запис [R05], [R02] в стек 23. Запис ознак інтерпретації (R11 - тип фрейму ітерації та R09-1 з першого слова фрейму; R10-2 з другого слова фрейму та поточний режим інтерпретації - R07=1, R08=0) в стек 45. - R05:= [RC04]. - Перехід в стан 3. 19. Завершити породження ітерації без сліду: - R13:= R09. - Перехід в стан 21. 20. Породження ітерації по сліду: - RC04 = [RC04] + 1; - RC06:= [ПС 40] за адресою [RC04]. - Якщо [RС06]  0, то перехід в стан 14, інакше - в стан 19. 21. Прийом і аналіз прапорів: - R07, R08, R09, R10, R11, R12:= [Верхній запис ознак інтерпретації стека 45]; -R13:=[R13]  [R10]. - Аналіз R11, R13, R07 та R08: Якщо R11=(00)&R13=1&(R07=0/1)&(R08=0/1), то перехід до п. 22 (прапор лож на термінал), Якщо R11=(00)&R13=0&(R07=0/1)&(R08=0/1), то переходимо до п. 23 (прапор істина на термінал), Якщо R11=01&R13=0&R07=0&R08=0, то перехід до п. 24 (розпізнавання альтернативи після прапору істина), Якщо R11=01&R13=0&R07=1&R08=0, то перехід до п. 25 (розпізнавання альтернативи із слідом після прапору істина), Якщо R11=01&R13=0&R07=0/1&R08=1, то перехід до п. 27 (породження альтернативи після прапору істина), Якщо R11=01&R13=1&R07=0&R08=0, то перехід до п. 28 (розпізнавання альтернативи після прапору лож), Якщо R11=01&R13=1&R07=1&R08=0, то перехід до п. 30 (розпізнавання альтернативи із слідом після прапору лож), Якщо R11=01&R13=1&R07=0/1&R08=1, то перехід до п. 32 (породження альтернативи після прапору лож), Якщо R11=10&R13=0&R07=0&R08=0, то перехід до п. 34 (розпізнавання послідовності після прапору істина), Якщо R11=10&R13=0&R07=1&R08=0, то перехід до п. 35 (розпізнавання послідовності із слідом після прапору істина), Якщо R11=10&R13=0&R07=0/1&R08=1, то перехід до п. 37 (породження послідовності після прапору істина), Якщо R11=10&R13=1&R07=0&R08=0, то перехід до п. 38 (розпізнавання послідовності після прапору лож), Якщо R11=10&R13=1&R07=1&R08=0, то перехід до п. 40 (розпізнавання послідовності із слідом після прапору лож), Якщо R11=10&R13=1&R07=0/1&R08=1, то перехід до п. 41 (породження послідовності після прапору лож), Якщо R11=11&R13=0&R07=0&R08=0, то перехід до п. 42 (розпізнавання ітерації після прапору істина), 8 UA 109711 C2 5 10 15 20 25 30 35 40 45 50 55 60 Якщо R11=11&R13=0&R07=1&R08=0, то перехід до п. 43 (розпізнавання ітерації із слідом після прапору істина), Якщо R11=11&R13=0&R07=0/1&R08=1, то перехід до п. 44 (породження ітерації після прапору істина), Якщо R11=11&R13=1&R07=0&R08=0, то перехід до п. 46 (розпізнавання ітерації після прапору лож), Якщо R11=11&R13=1&R07=1&R08=0, то перехід до п. 47 (розпізнавання ітерації із слідом після прапору лож), Якщо R11=11&R13=1&R07=0/1&R08=1, то перехід до п. 48 (породження ітерації після прапору лож). 22. Відновлення покажчиків INP, OUT: - RД:= [RД із стека 12]; - Перехід в стан 2. 23. Набуття нових значень покажчиків INP, OUT: - Виштовхнути [RД] із стека 12. - Перехід в стан 2. 24. Розпізнавання альтернативи після прапору істина: - Виштовхнути [R02] із стека 23; - Виштовхнути [RД] із стека 12. - R13:=[R13]  [R09]. - Перехід в стан 21. 25. Розпізнавання альтернативи із слідом після прапору істина: - R02:= [R02] із стека 23; - R03:= [R02]; - RC04:= [R05] із стека 23; - ОС першого слова фрейму:= 1; поля 1 та тип фрейму - відновити у байті ознак та [перший та другий байти першого слова фрейму за адресою [R03] БЗ 46]:= [RC04]. - Виштовхнути [RД] із стека 12. - R13:=[R13]  [R09]. - Перехід в стан 21. 26. Вихід з розпізнавання альтернативи: - Виштовхнути [R02] із стека 23; -R13:=[R13]  [R09]. - Перехід в стан 21. 27. Породження альтернативи по сліду після прапору істина: - Виштовхнути [RД] із стека 12. -R13:=[R13]  [R09]. - Перехід в стан 21. 28. Розпізнавання альтернативи після прапору лож: - Відновлення покажчиків INP, OUT: RД:= [RД] із стека 12. - Аналіз значення R12: якщо 1, перехід в стан 26, інакше - в стан 29. 29. Розпізнавання нового варіанта альтернативи: - R02:= [R02 із стека 23] + 1; - R03:= [R02]; - Читання з ОЗУ БЗ 46 чергового слова фрейму альтернативи. R10:= [поле 2], R12:= [поле ОЕ], R07*:= [значення (0/1) ознаки розпізнавання із слідом] або R08*:= [значення (0/1) ознаки породження], R01:= [перший та другий байти вибраного слова фрейму]. - Запис значення регістра [RД] в стек 12, а [R02] в стек 23. Запис ознак інтерпретації (R11 - тип фрейму альтернативи та R09-1 з першого слова фрейму; R10-2, R12 - ОЕ з чергового слова фрейму та вхідний режим інтерпретації - R07=0, R08=0) в стек 45; - R07:= R07*; R08:= R08*. - Перехід в стан 3. 30. Розпізнавання альтернативи із слідом після прапору лож: - Відновлення покажчиків INP, OUT: RД:= [RД із стека 12]. - Аналіз значення R12: якщо 1, перехід в стан 31, інакше - в стан 33. 31. Вихід із розпізнавання альтернативи із слідом: - Виштовхнути [R02] із стека 23; - RС04:= [R05] із стека 23; - R13:=[R13]  [R09]. - Перехід в стан 21. 9 UA 109711 C2 5 10 15 20 25 30 35 40 45 50 55 32. Породження альтернативи по сліду після прапору лож: - Відновлення RД:= [RД із стека 12]; - R13:=[R13]  [R09]. - Перехід в стан 21. 33. Розпізнавання із слідом нового варіанта альтернативи: - RC04:= [R05 із стека 23] + 1; RC06:= [RC06 із ПС 40] + 1; - Запис [RC06] в ПС 40 по адресу RC04; - R02:= [R02 із стека 23]; R03:=[R02;H [RC06]. - Читання з ОЗУ БЗ 46 чергового слова фрейму. R10:= [поле 2], R15:= [поле ОЕ], R01:= [перший та другий байти обраного слова фрейму]. - Запис [RД] в стек 12, запис [R05], [R02] в стек 23. - Запис ознак інтерпретації (R11 - тип фрейму альтернативи та R09-1 з першого слова фрейму, відновлених з магазину; R10-2, R12 - ОЕ з вибраного слова фрейму та поточний режим інтерпретації - R07=1, R08=0) в стек 45; - R05:= [RC04]. - Перехід в стан 3. 34. Розпізнавання послідовності після прапору істина: - Аналіз значення R12: якщо 1, то перехід в стан 24, інакше - в стан 29. 35. Розпізнавання послідовності із слідом після прапору істина: - Аналіз значення R12: якщо 1, то перехід в стан 25, інакше - в стан 36. 36. Продовжити розпізнавання послідовності із слідом: - RC06:= [RC06 із стека 45] + 1; -R03:=[R02] + [RC06]. - Читання із ОЗУ БЗ 46 чергового слова фрейму. R10:= [поле 2], R12:= [поле ОЕ], R01:= [перший та другий байти вибраного слова фрейму]. - Запис [RД] в стек 12, [R05], [R02] - в стек 23, [RC06] - в ПС 40. Запис ознак інтерпретації (R11 тип фрейму послідовності та R09-1 з першого слова фрейму; R10-2, R12 - ОЕ з чергового слова фрейму та поточний режим інтерпретації з R07=0/1, R08=1) в стек 45. - Перехід в стан 3. 37. Породження послідовності після прапору істина: - Аналіз значення R12: якщо 1, перехід в стан 24, інакше - в стан 39. 38. Розпізнавання послідовності після прапору лож: - Відновлення RД:= [RД із стеку 12]. - Перехід в стан 26. 39. Продовжити породження послідовності: - R02:= [R02 із стеку 23]+ 1; - R03:= [R02]. - Читання з ОЗУ БЗ 46 чергового слова фрейму послідовності. R10:= [поле 2], R12:= [поле ОЕ], R01:= [перший та другий байти другого слова фрейму]. - Запис [RД] в стек 12, [R02] - в стек 23. Запис ознак інтерпретації (R11 - тип фрейму послідовності та R09-1 з першого слова фрейму; R10-2, R12 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R07=0/1, R08=1) в стек 45. - Перехід в стан 3. 40. Розпізнавання послідовності із слідом після прапору лож: - Відновлення покажчиків: RC04:= [R05 із стека 23], RД:= [RД із стека 12]; - R07:= R07*; R08:= R08*. - Перехід в стан 26. 41. Породження послідовності після прапору лож: - Відновлення RД:= [RД із стека 12]; - R07:= R07*; R08:= R08*; - Виштовхнути [R02 із стеку 23]. - R13:=[R13]  [R09]. - Перехід в стан 21. 42. Розпізнавання ітерації після прапору істина: - R03:= [R02 із стека 23] + 1. - Читання із БЗ 46 другого слова фрейму. R10:= [поле 2], R12:= [поле ОЕ], R07*:= [значення (0/1) ознаки розпізнавання із слідом] або R08*:= [значення (0/1) ознаки породження], R01:= [перший та другий байти другого слова фрейму]. 10 UA 109711 C2 5 10 15 20 25 30 35 40 - Запис значення регістру [R02] в стек 23. Запис ознак інтерпретації (R11 - тип фрейму ітерації та R09-1 з першого слова фрейму; R10-2, R12 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R07=0, R08=0) в стек 45. - R07:= R07*; R08:= R08*. - Перехід в стан 3. 43. Розпізнавання ітерації із слідом після прапору істина: - RC04:= [R05 із стека 23] + 1; RC06:= [RC06 із ПС 40 по адресу RC04] + 1; - Запис [RC06] в ПС 40 по адресу RC04; - R03:= [R02 із стека 23] + 1. - Читання з БЗ 46 другого слова фрейму. R10:= [поле 2], R01:= [перший та другий байти другого слова фрейму]. - Запис [R05], [R02] в стек 23. Запис ознак інтерпретації (R11 - тип фрейму ітерації та R09-1 з першого слова фрейму; R10-2 з другого слова фрейму та поточний режим інтерпретації - R07=1, R08=0) в стек 45. - Перехід в стан 3. 44. Породження ітерації після прапору істина: - RC06:=[RC06 із стека 45]; - Аналіз [RС06]: якщо [RС06]  0, то перехід в стан 45, інакше - в стан 46. 45. Продовжити породження ітерації після прапору істина: - RC06:= [RC06] - 1; R03:= [R02 із стека 23] + 1. - Читання з БЗ 46 другого слова фрейму. R10:= [поле 2], R01:= [перший та другий байти другого слова фрейму]. - Запис [RС06] в стек 45, запис [R02] в стек 23. Запис ознак інтерпретації (R11 - тип фрейму ітерації та R09-1 з першого слова фрейму; R10-2 з другого слова фрейму та поточний режим інтерпретації - R07=0/1, R08=1) в стек 45. - Перехід в стан 3. 46. Завершити породження ітерації та розпізнавання ітерації після прапору лож: - Виштовхнути [R02 із стека 23]; R13:= [R09]. - Перехід в стан 21. 47. Розпізнавання ітерації із слідом після прапору лож: - R03:= [R02 із стека 23]; - RC04:= [R05 із стека 23]; - ОС першого слова фрейму:= 1; поля 1 та тип фрейму - відновити; - [перший та другий байти першого слова фрейму в БЗ 46]:= [RC04]; - R13:= [R09]. - Перехід в стан 21. 48. Породження ітерації після прапору лож: - Виштовхнути [R02 із стека 23]; Виштовхнути [RC06 із стека 45]; : - R13 = [R09]. - Перехід в стан 21. Оскільки система обробки знань підтримує системний шинний інтерфейс (наприклад, АРВ), то вона може бути легко інтегрована в сучасні мікропроцесорні системи на кристалі з метою розширення їхнього набору команд. Таблиця 1 Ім'я регістра RKБ3 RКОМ1 RКОМ2 RД R01 R02 R03 RC04 R05 RC06 Розрядність, біт 16 24 24 24 16 16 16 16 16 16 Опис регістра Регістр кореня бази знань Перший регістр команд Другий регістр команд Регістр даних Регістр імені структури Регістр номера слова фрейму Регістр адреси бази знань Регістр-лічильник координати сліду Регістр вершини сліду Регістр-лічильник ітерації 45 11 UA 109711 C2 Продовження таблиці 1 R07 R08 R09 R10 R11 R12 R13 R07* R08* 1 1 1 1 3 1 1 1 1 Регістр ознаки сліду Регістр ознаки породження Регістр інверсії 1 Регістр інверсії 2 Регістр типу фрейму Регістр ознаки останнього елемента Регістр істинності Додатковий регістр ознаки сліду Додатковий регістр ознаки породження ФОРМУЛА ВИНАХОДУ 5 10 15 20 25 30 35 40 45 Машина баз знань, що містить оперативну пам'ять баз знань, блок керування, перший блок вводу-виводу та головний комп'ютер, через перший блок вводу-виводу підключений до системної шини, яка відрізняється тим, що в неї введено універсальний процесор, пам'ять програм та даних, другий блок вводу-виводу, регістр кореня бази знань, перший та другий регістри команд, регістр даних, регістр імені структури, регістр номера слова фрейму, регістр адреси бази знань, регістр координати сліду, регістр вершини сліду, регістр ітерації, регістр істинності, регістр ознак сліду, регістр ознак породження, регістр першої інверсії, регістр другої інверсії, регістр типу фрейму, регістр ознак останнього елемента, додатковий регістр ознак сліду, додатковий регістр ознак породження, одинадцять мультиплексорів, стек адрес даних, стек регістрів, стек ознак, пам'ять сліду, суматор, перший та другий суматори по модулю два, при цьому системною шиною машини поєднані пам'ять програм та даних, універсальний процесор та перші входи-виходи другого блока вводу-виводу, чий другий вхід-вихід підключено до першого входу-виходу регістра даних, другий вхід-вихід якого підключено до входу-виходу стека адрес даних, перший вихід другого блока вводу-виводу підключено до входу регістра кореня бази знань, чий вихід підключено до другого входу першого мультиплексора, вихід якого підключено до входу регістра імені структури, чий вихід з'єднано із першими входами десятого мультиплексора і першого регістра команд та з другим входом четвертого мультиплексора, вихід якого підключено до входу регістра номера слова фрейму, чий вихід підключено до першого входу стека регістрів та до першого входу суматора, вихід якого підключено до першого входу четвертого мультиплексора та до другого входу десятого мультиплексора, чий вихід підключено до входу регістра адреси бази знань, з'єднаного виходом із адресним входом оперативної пам'яті бази знань, перший інформаційний вихід якої підключений до перших входів першого мультиплексора та сьомого мультиплексора, чий вихід підключено до входу регістра координати сліду, вихід якого з'єднаний із адресним входом пам'яті сліду, інформаційним входом оперативної пам'яті бази знань та із входом регістра вершини сліду, чий вихід підключено до другого входу стека регістрів та до третього входу сьомого мультиплексора, другий вхід якого підключений до другого виходу стека регістрів, чий перший вихід підключено до третього входу четвертого мультиплексора, вихід першого регістра команд підключено до входу другого блока вводу-виводу, чий другий вихід підключено до входу другого регістра команд, перший вихід якого підключено до першого входу блока керування, а другий вихід підключено до перших входів другого, третього, шостого та дев'ятого мультиплексорів, вихід оперативної пам'яті бази знань підключено до входів додаткових регістрів ознак сліду, ознак породження та до других входів п'ятого, шостого, восьмого та дев'ятого мультиплексорів, вихід додаткового регістра ознак сліду підключено до другого входу другого мультиплексора, вихід додаткового регістра ознак породження підключено до другого входу третього мультиплексора, треті входи другого, третього, шостого, дев'ятого і другі входи п'ятого та восьмого мультиплексорів підключені до виходу стека ознак, а виходи другого, третього, п'ятого, шостого, восьмого і дев'ятого мультиплексорів з'єднані із входами регістрів ознак сліду, ознак породження, першої інверсії, другої інверсії, типу фрейму та ознак останнього елемента відповідно, перші виходи регістрів ознак сліду, ознак породження, типу фрейму та ознак останнього елемента підключено до третього входу першого регістра команд та другого входу блока керування, чий вихід підключено до другого входу першого регістра команд, другі виходи регістрів ознак сліду, ознак породження, першої інверсії, другої інверсії, типу фрейму та ознак останнього елемента підключено до входу стека ознак, перший вихід регістра першої інверсії та 12 UA 109711 C2 5 10 третій вихід регістра типу фрейма разом із виходом логічної одиниці підключено до входу оперативної пам'яті баз знань, а третій вихід регістра першої інверсії підключено до першого входу першого суматора по модулю два та до першого входу одинадцятого мультиплексора, перший вихід регістра другої інверсії підключено до першого входу другого суматора по модулю два, чий другий вхід разом із другим входом першого суматора по модулю два та третім входом блока керування підключений до виходу регістра істинності, вхід якого з'єднаний із виходом одинадцятого мультиплексора, чиї другий і третій входи підключені до виходів першого та другого суматора по модулю два відповідно, входи-виходи стека ознак з'єднані із входамивиходами пам'яті сліду та регістра ітерації, чий вихід підключений до другого входу суматора та до четвертого входу блока керування. 13 UA 109711 C2 14 UA 109711 C2 15 UA 109711 C2 Комп’ютерна верстка І. Мироненко Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП "Український інститут інтелектуальної власності", вул. Глазунова, 1, м. Київ – 42, 01601 16