Система баз знань

Реферат: Винахід належить до області обчислювальної техніки та може бути використаний при побудові систем, заснованих на знаннях (knowledge-based systems). Система баз знань складається із: головного комп'ютера, другого блока вводу-виводу, оперативної пам'яті, термінального процесора, що включає перший блок вводу-виводу, регістр даних, робочу пам'ять, мультиплексор, регістр-лічильник координат вхідного масиву, регістр-лічильник координат вихідного масиву, арифметико-логічний блок, перший блок управління, та співпроцесора знань, що включає третій блок вводу-виводу, другий блок управління, буферний регістр, блоки імені структури, номера слова фрейму, координати сліду, адреси у вхідному масиві, адреси у вихідному масиві, лічильника ітерації, істинності, ознак інтерпретації, адреси бази знань, даних пам'яті бази знань, лічильника магазину, даних пам'яті магазину, вершини сліду, даних пам'яті сліду, пам'ять бази знань, пам'ять магазину та пам'ять сліду. Технічним результатом, що досягається даним винаходом, є розширення функціональних можливостей інтерпретації рекурсивних, ітераційних та вкладених структур, підвищення ефективності зберігання даних. UA 109713 C2 (12) UA 109713 C2 UA 109713 C2 5 10 15 20 25 30 35 40 45 50 55 Даний винахід належить до області обчислювальної техніки та може бути використаний при побудові систем, заснованих на знаннях (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); переміщення даних; логічного зсуву та переходу. Блок управління керує роботою всіх модулів процесора продукційних правил, а також процесом обміну даними між пам'яттю правил та блоком вводу-виводу. Оперативна пам'ять містить набір команд фіксованої довжини. Кожна команда містить такі поля: "тип команди", "прапор" (умова (сondition)/дія (action)) та два операнди. Якщо поточна команда у полі "прапор" містить умову, то відбувається порівняння операндів залежно від коду поля "тип команди". Якщо команда характеризується як дія, то над поточними операндами виконується дія, зазначена у полі "тип команди". Серед недоліків прототипу можна вказати наступні. 1) Необхідність виконання великої кількості обчислень у процесі пошуку активної продукції при співставленні антецедентів. Це пов'язано із тим, що між продукційними правилами, які містяться в оперативній пам'яті у вигляді команд спеціального формату, відсутній ієрархічний зв'язок. 2) Відсутність механізму пояснення логічного виводу. 3) Відсутність ефективного представлення у пам'яті ітераційних та рекурсивних структур. Спільними ознаками прототипу та пропонованої моделі є головний комп'ютер, оперативна пам'ять, перший блок управління, арифметико-логічний блок, робоча пам'ять, перший регістр даних, регістр-лічильник координат вхідного масиву та перший блок вводу-виводу. В основу моделі поставлена задача побудови спеціалізованої системи баз знань. Всяка задача, поставлена у вигляді імені функції та значення її аргументу, вирішується виводом рішення у процесі інтерпретації бази знань. 1 UA 109713 C2 5 10 15 20 25 30 35 40 45 50 55 60 База знань складається із структури взаємозв'язаних визначень термінів, кожне з яких представляється у формі одного з п'яти фреймів: альтернативи, послідовності, ітерації, текстової константи або терміналу. Усякий фрейм - послідовність слів фіксованої довжини (наприклад, трибайтових), серед яких розрізняється перше слово, а в кожному зі слів - перший байт і наступні. Фрейми текстової константи й термінала - однослівні, ітерації - двослівні, альтернативи й послідовності - багатослівні. Фрейми визначень всіх термінів всякої бази знань розміщено у пам'яті бази знань у вигляді ієрархічної структури, що усуває проблему множини конфліктних правил. Такий принцип організації бази знань дозволяє ефективно зберігати та інтерпретувати ітераційні й рекурсивні структури визначень. Ще однією важливою відмінністю системи баз знань є те, що структура процесу інтерпретації, процесу виводу рішення зберігається спеціальними засобами ведення сліду. З метою розширення функціональних можливостей інтерпретації рекурсивних, ітераційних та вкладених структур і формування структури виводу рішення задачі у пристрій, що містить головний комп'ютер, оперативну пам'ять, перший блок вводу-виводу, перший блок управління, арифметико-логічний блок, робочу пам'ять, регістр даних та регістр-лічильник координат вхідного масиву, у якому перший вхід-вихід першого блока вводу-виводу разом із входамивиходами оперативної пам'яті підключений до системної шини пристрою, другий вхід-вихід першого блока вводу-виводу підключений до входів-виходів регістра-лічильника координат вхідного масиву, третій вхід-вихід першого блока вводу-виводу разом із входами-виходами арифметико-логічного блока, входом-виходом першого блока управління та першими входамивиходами першого регістра даних, з'єднаного другими входами-виходами з входами-виходами робочої пам'яті, підключений до шини даних, введено регістр-лічильник координат вихідного масиву, мультиплексор, другий та третій блоки вводу-виводу, буферний регістр, блоки імені структури, номера слова фрейму, адреси бази знань, координати сліду, вершини сліду, адреси у вхідному масиві, адреси у вихідному масиві, лічильника ітерації, істинності, лічильника магазину та ознак інтерпретації, пам'ять бази знань, пам'ять магазину, пам'ять сліду, блок даних пам'яті бази знань, блок даних пам'яті магазину, блок даних пам'яті сліду, при цьому четвертий вхід-вихід першого блока вводу-виводу підключений до входів-виходів регістра-лічильника координат вихідного масиву, чий вихід разом із виходом регістра-лічильника координат вхідного масиву підключений через мультиплексор до адресних входів робочої пам'яті, головний комп'ютер через другий блок вводу-виводу разом із входами-виходами третього блока вводувиводу підключені до системної шини пристрою, перший вихід третього блока вводу-виводу підключено до першого входу другого блока управління, перший вихід якого підключено до першого входу третього блока вводу-виводу, другий вихід другого блока управління підключено до перших входів блоків імені структури, номера слова фрейму, координати сліду, адреси у вхідному масиві, адреси у вихідному масиві, лічильника ітерації, істинності та ознак інтерпретації, третій вихід другого блока управління підключено до перших входів блоків адреси бази знань, даних пам'яті бази знань, лічильника магазину, даних пам'яті магазину, вершини сліду та даних пам'яті сліду, другий вихід другого блока вводу-виводу підключено до других входів блоків імені структури, номера слова фрейму, адреси бази знань, координати сліду, вершини сліду, адреси у вхідному масиві, адреси у вихідному масиві, лічильника ітерації, істинності, лічильника магазину, ознак інтерпретації, даних пам'яті бази знань, даних пам'яті магазину та даних пам'яті сліду, вихід пам'яті бази знань підключено до третіх входів другого блока управління, третього блока вводу-виводу, блоків імені структури, номера слова фрейму та ознак інтерпретації, вихід пам'яті магазину підключено до четвертого входу блока імені структури, до четвертого входу блока номера слова фрейму, до третіх входів блоків координат сліду, адреси у вхідному масиві та адреси у вихідному масиві, вихід пам'яті сліду підключено до п'ятого входу блока номера слова фрейму та до третього входу блока лічильника ітерації, вихід блока імені структури підключено до шостого входу буферного регістра, до третього входу блока адреси бази знань, до шостого входу блока номера слова фрейму, до третього входу блока даних пам'яті бази знань, до шостого входу блока даних пам'яті магазину та до третього входу блока даних пам'яті сліду, вихід блока номера слова фрейму підключено до четвертого входу блока адреси бази знань, вихід блока координати сліду підключено до другого входу блока даних пам'яті магазину та до четвертого входу блока вершини сліду, вихід блока адреси у вхідному масиві підключено до четвертого входу блока даних пам'яті магазину та до п'ятого входу буферного регістра, вихід блока адреси у вихідному масиві підключено до п'ятого входу блока даних пам'яті магазину та до четвертого входу буферного регістра, вихід блока лічильника ітерації підключено до другого входу буферного регістра, до сьомого входу блока даних пам'яті магазину та до четвертого входу блока даних пам'яті сліду, вихід блока істинності підключено до першого входу буферного регістра, вихід блока ознак інтерпретації підключено 2 UA 109713 C2 5 10 15 20 25 30 35 40 45 50 55 60 до третього входу блока істинності, до третього входу буферного регістра та до восьмого входу блока даних пам'яті магазину, четвертий вихід другого блока управління підключено до входів управління пам'яті бази знань, магазину та сліду, адресні входи яких з'єднані із виходами блока адреси бази знань, лічильника магазину та блока вершини сліду відповідно, вихід блока даних пам'яті бази знань підключено до входу даних пам'яті бази знань, вихід блока лічильник магазину підключено до четвертого входу блока даних пам'яті бази знань, вихід блока даних пам'яті магазину підключено до входу даних пам'яті магазину, вихід блока вершини сліду підключено до четвертого входу блока координати сліду, вихід блока даних пам'яті сліду підключено до входу даних пам'яті сліду, вихід буферного регістра підключено до других входів третього блока вводу-виводу та другого блока управління. Відмітними ознаками запропонованої системи баз знань від відомого прототипу є: 1) модуль розширення функціональності системи реалізовано на базі програмованої логічної інтегральної схеми; 2) знання зберігаються у вигляді множини визначень термінів та відокремлено від алгоритму їх обробки; 3) алгоритм роботи системи апаратно "зашитий" у автомат управління по типу Мура; 4) знання, що містяться у базі знань, зберігаються у вигляді ієрархічної структури, яка значно підвищує ефективність пошуку рішення за рахунок логічного виводу тільки у необхідній частині бази знань; 5) зберігається структура логічного виводу, яка в подальшому може бути використана для пояснення ходу логічного виводу або породження нової структури даних; 6) надається можливість ефективно зберігати та інтерпретувати ітераційні та рекурсивні структури даних, які містять визначення з використанням відношень кон'юнкції, диз'юнкції та інверсії. На фіг. 1 наведено структуру системи баз знань; на фіг. 2 наведено структуру блока управління; на фіг. 3 наведено структуру буферного регістра RБ 17, блоків імені структури Б01 18, адреси бази знань Б03 26, даних пам'яті бази знань БDT_БЗ 27, адреси у вхідному масиві Б06 21, адреси у вихідному масиві Б07 22, лічильника магазину БЛМ 28, даних пам'яті магазину БDT_ПМ 29, даних пам'яті сліду БDT_ПС 31; на фіг. 4 наведено структуру блоків номера слова фрейму Б 02 19, координати сліду Б04 20, вершини сліду Б05 30, лічильника ітерації Б08 23 та істинності Б09 24; на фіг. 5 наведено структуру блока ознак інтерпретації Б ОІ 25; на фіг. 6 наведено структуру запису пам'яті магазину та сліду; на фіг. 7 наведено структуру слова бази знань; на фіг. 8 наведено структуру байта ознак слова фрейму; на фіг. 9 наведено структуру шаблонів фреймів; на фіг. 10 наведено граф алгоритму роботи системи. У табл. 1 наведено регістровий склад блоків, у табл. 2 наведено опис команд блока управління, у табл. 3 наведено реалізацію базових процедур алгоритму роботи системи. Система баз знань (фіг. 1) складається із: головного комп'ютера 1, модуля розширення функціональності 2, співпроцесора знань 3, другого блока вводу-виводу 4, термінального процесора 5, оперативної пам'яті 6, першого блока вводу-виводу 7, регістра даних RDT 8, робочої пам'яті 9, мультиплексора MX 10, регістра-лічильника RCm 11 координат вхідного масиву, регістра-лічильника RCn 12 координат вихідного масиву, арифметико-логічного блока АЛБ 13, першого блока управління 14, третього блока вводу-виводу 15, другого блока управління 16, буферного регістра RБ 17, блока імені структури Б01 18, блока номера слова фрейму Б02 19, блока координати сліду Б04 20, блока адреси у вхідному масиві Б06 21, блока адреси у вихідному масиві Б07 22, блока лічильника ітерації Б08 23, блока істинності Б09 24, блока ознак інтерпретації БОІ 25, блока адреси бази знань Б03 26, блока даних пам'яті бази знань БDT_БЗ 27, блока лічильника магазину БЛМ 28, блока даних пам'яті магазину БDT_ПМ 29, блока вершини сліду Б05 30, блока даних пам'яті сліду БDT_ПС 31, пам'ять бази знань RAMБЗ 32, пам'ять магазину RAMПМ 33, пам'ять сліду RAMПС 34. Головний комп'ютер 1 призначений для постановки завдання, зчитування результатів роботи модуля розширення функціональності 2 та конфігурації роботи модуля 2. Термінальний процесор 5 призначений для виконання термінальних програм на замовлення співпроцесора 3. співпроцесор знань 3 розширює набір команд термінального процесора 5 та призначений для швидкої апаратної обробки поставленого завдання, що надійшло від головного комп'ютера 1. Головний комп'ютер 1 через другий блок вводу-виводу 4 підключений разом із входамивиходами оперативної пам'яті 6 та першими входами-виходами першого 7 та третього 15 блоків вводу-виводу до системної шини. Другий та четвертий входи-виходи першого блока вводувиводу 7 підключені до входів-виходів відповідно регістра-лічильника RCm 11 координат вхідного масиву та регістра-лічильника RCn 12 координат вихідного масиву, чиї виходи через мультиплексор MX 10 підключені до адресних входів робочої пам'яті 9. Третій вхід-вихід першого блока вводу-виводу 7 разом із входами-виходами арифметико-логічного блока АЛБ 13, першого блока управління 14 та першими входами-виходами регістра даних RDT 8, з'єднаного другими входами-виходами з входами-виходами робочої пам'яті 9, підключений до шини даних. 3 UA 109713 C2 5 10 15 20 25 30 35 40 45 50 55 Перший вихід третього блока вводу виводу 15 підключено до першого входу другого блока управління 16, перший вихід якого підключено до першого входу третього блока вводу-виводу 15. Другий вихід другого блока управління 16 підключено до перших входів блоків імені структури Б01 18, номера слова фрейму Б02 19, координати сліду Б04 20, адреси у вхідному масиві Б06 21, адреси у вихідному масиві Б07 22, лічильника ітерації Б08 23, істинності Б09 24, ознак інтерпретації БОІ 25. Третій вихід другого блока управління 16 підключено до перших входів блоків адреси бази знань Б03 26, даних пам'яті бази знань БDT_БЗ 27, лічильника магазину БЛМ 28, даних пам'яті магазину БDT_ПМ 29, вершини сліду Б05 30, даних пам'яті сліду БDT_ПС 31. Другий вихід другого блока вводу-виводу 15 підключено до других входів блоків імені структури Б01 18, номера слова фрейму Б02 19, адреси бази знань Б03 26, координати сліду Б04 20, вершини сліду Б05 30, адреси у вхідному масиві Б06 21, адреси у вихідному масиві Б07 22, лічильника ітерації Б08 23, істинності Б09 24, лічильника магазину БЛМ 28, ознак інтерпретації БОІ 25, даних пам'яті бази знань БDT_БЗ 27, даних пам'яті магазину БDT_ПМ 29, даних пам'яті сліду БDT_ПС 31. Вихід пам'яті бази знань RAMБЗ 32 підключено до третіх входів другого блока управління 16, третього блока вводу-виводу 15, блоків імені структури Б01 18, номера слова фрейму Б02 19 та ознак інтерпретації БОІ 25. Вихід пам'яті магазину RAMПМ 33 підключено до четвертого входу блока імені структури Б01 18, до четвертого входу блока номера слова фрейму Б02 19, до третіх входів блоків координат сліду Б04 20, адреси у вхідному масиві Б06 21 та адреси у вихідному масиві Б07 22. Вихід пам'яті сліду RAMПС 34 підключено до п'ятого входу блока номера слова фрейму Б02 19 та до третього входу блока лічильника ітерації Б08 23. Вихід блока імені структури Б01 18 підключено до шостого входу буферного регістра RБ 17, до третього входу блока адреси бази знань Б03 26, до шостого входу блока номера слова фрейму Б 02 19, до третього входу блока даних пам'яті бази знань БDT_БЗ 27, до шостого входу блока даних пам'яті магазину БDT_ПМ 29, до третього входу блока даних пам'яті сліду БDT_ПС 31. Вихід блока номера слова фрейму Б02 19 підключено до четвертого входу блока адреси бази знань Б03 26. Вихід блока координати сліду Б04 20 підключено до другого входу блока даних пам'яті магазину БDT_ПМ 29 та до четвертого входу блока вершини сліду Б 05 30. Вихід блока адреси у вхідному масиві Б 06 21 підключено до четвертого входу блока даних пам'яті магазину Б DT_ПМ 29 та до п'ятого входу буферного регістра RБ 17. Вихід блока адреси у вихідному масиві Б07 22 підключено до п'ятого входу блока даних пам'яті магазину БDT_ПМ 29 та до четвертого входу буферного регістра RБ 17. Вихід блока лічильника ітерації Б08 23 підключено до другого входу буферного регістра RБ 17, до сьомого входу блока даних пам'яті магазину БDT_ПМ 29 та до четвертого входу блока даних пам'яті сліду БDT_ПС 31. Вихід блока істинності Б09 24 підключено до першого входу буферного регістра RБ 17. Вихід блока ознак інтерпретації БОІ 25 підключено до третього входу блока істинності Б09 24, до третього входу буферного регістра RБ 17 та до восьмого входу блока даних пам'яті магазину БDT_ПМ 29. Четвертий вихід другого блока управління 16 підключено до входів управління пам'яті бази знань RAMБЗ 32, магазину RAMПМ 33 та сліду RAMПС 34, адресні входи яких з'єднані із виходами блока адреси бази знань Б03 26, лічильника магазину БЛМ 28 та блока вершини сліду Б05 30 відповідно. Вихід блока даних пам'яті бази знань БDT_БЗ 27 підключено до входу даних пам'яті бази знань RAMБЗ 32. Вихід блока лічильник магазину БЛМ 28 підключено до четвертого входу блока даних пам'яті бази знань Б DT_БЗ 27. Вихід блока даних пам'яті магазину БDT_ПМ 29 підключено до входу даних пам'яті магазину RAMПМ 33. Вихід блока вершини сліду Б05 30 підключено до четвертого входу блока координати сліду Б04 20, вихід блока даних пам'яті сліду БDT_ПС 31 підключено до входу даних пам'яті сліду RAMПС 34. Вихід буферного регістра RБ 17 підключено до других входів третього блока вводу-виводу 15 та другого блока управління 16. Опис регістрів блоків із складу співпроцесора 3 наведено у табл. 1. Операційна частина співпроцесора 3 виконує команди, множину яких (табл. 2) можна розділити на 8 груп: а) завантаження даних із Ri до Rj; б) завантаження константи до Ri; в) інкремент даних у Ri та запис їх у Rj; г) декремент даних у Ri та запис їх у Rj; д) завантаження зовнішніх даних у Ri; e) завантаження даних із пам'яті до Ri; ж) команди для роботи із пам'яттю; з) команди запиту на обробку термінальних програм. Розглянемо принцип роботи пристрою: 1. Ініціалізація системи баз знань. Відбувається ззовні за допомогою блока вводу-виводу 4. залежно від зовнішніх команд, що надійшли від термінального процесора 5, виконується завантаження початкових даних у регістри співпроцесора 3. Після цього виконується ініціалізація пам'ятей 32, 33 та 34. 4 UA 109713 C2 5 10 15 20 25 30 35 40 45 50 55 60 2. Передача управління роботи. Після завершення етапу ініціалізації виконується передача управління співпроцесору 3, який неперервно працює згідно закладеному у нього алгоритму (фіг. 10). 3. Обробка поставленого завдання. Виконується в процесі зміни станів дру-го блока управління 16. Залежно від поточного стану на його виходи надходять команди, які керують операційною частиною співпроцесора 3, до якої належать блоки 17-31. 3.1. Залежно від типу поточної команди відбувається модифікація даних, що містяться у регістрах блоків 17-25, або передача даних із цих блоків до блоків (26-31) роботи із пам'ятями (32-34). Як видно із фіг. 1, вхід кожного блока (18-25) з'єднаний із декількома вхідними шинами. Залежно від команди може відбуватися або ні запис даних із однієї із цих шин до регістра відповідного блока. 3.2. Залежно від типу поточної команди на третьому виході блока управління 16 виконується або ні модифікація даних, що містяться у регістрах блоків 26-31. 3.3. Залежно від типу поточної команди на четвертому виході блока 16 управління виконується або ні завантаження, зчитування чи модифікація даних пам'ятей 32-34. 3.4. Для виконання чергової термінальної програми блок управління 16 співпроцесора 3 через блок вводу-виводу 15 передає термінальному процесору 5 ім'я і дані відповідного завдання, які той приймає через блок вводу-виводу 7. Після завершення виконання термінальної програми термінальний процесор 5 через блоки вводу-виводу 7 та 15 надсилає відповідну команду та результати. 4. Передача результатів виконання завдання. Після завершення виконання поставленого завдання блок управління 16 співпроцесора 3 через блок вводу-виводу 15 передає термінальному процесору 5 відповідні результати й очікує нового завдання. Блок 16 управління (фіг. 2) складається із трьох модулів: логіка переходів 35, пам'ять станів 36 та вихідна логіка 37. Логіка переходів 35 визначає наступний стан блока управління 16, що є функцією від поточного стану пам'яті станів 36 та кодів на входах блока управління 16. Пам'ять станів 36 складається із набору елементів пам'яті та призначена для збереження поточного стану блока 16 управління. Команди на виходах блока управління 16 визначаються вихідною логікою 37 та є функцією від поточного стану пам'яті станів 36. Структуру багато вхідних блоків RБ, Б01, Б03, Б06, Б07, БЛМ, БDT_БЗ, БDT_ПМ, БDT_ПС зображено на фіг. 3 у складі відповідних мультиплексора MXi та регістра Ri. Вхід мультиплексора MXi з'єднаний із n шинами вхідних даних та шиною команд. На входи регістра Ri надходять дані з виходу MXi та відповідна команда. Під управлінням відповідної команди відбувається комутація входів мультиплексора і запис даних у регістр Ri. Структуру блоків Б02, Б04, Б05, Б08 та Б09 зображено на фіг. 4 у складі мультиплексора MXi, арифметико-логічного пристрою, інвертора та регістра Ri. Інформаційні входи мультиплексора MXi з'єднано із шинами вхідних даних, інверсії вхідних даних та виходами арифметико-логічного пристрою, а виходи підключено до входів регістра Ri. Команди управляють комутацією інформаційних входів мультиплексора MXi та записом даних з його виходів у регістр Ri. Структуру блока ознак інтерпретації БОІ зображено на фіг. 5, який складається із мультиплексора MXi регістра ознак сліду (R10), регістра ознак породження (R11), регістра Інв_1 (R12), регістра Інв_2 (R13), регістра типу фрейму (R14), регістра ознаки останнього елемента (R15). Входи мультиплексора MXi з'єднані із двома шинами вхідних даних та шиною команд. Входи регістрів Ri (R10-R15) з'єднані із виходами MXi та шиною команд. При надходженні відповідної команди виконується комутація вхідних даних мультиплексора MXi та їх запис у відповідний регістр Ri. База знань (БЗ) представляється у формі інформаційної структури множини визначень, вузлами якої є поняття (термінальні - константи чи іменовані процедури, або не термінальні), а дугами - відношення альтернативи, послідовності чи ітерації, що зв'язують поняття (вузли) визначальної частини всякого визначення. Пам'ять бази знань зберігає знання у машинній формі, що складається із множини фреймів, кожний із яких має структуру масиву слів фіксованої довжини (наприклад, 3 байти). Довжина фрейму залежить від типу відношення, яке він описує, та від числа понять у визначальній частині і може складати від одного до деякого скінченного числа слів. Пам'яті сліду та магазину зберігають (у формі фіг. 6) оперативну інформацію процесу інтерпретації бази знань. Пам'ять сліду зберігає структуру виводу рішення задачі. Вона може бути використана для пояснення процесу рішення задачі або при породженні наслідку. Пам'ять магазину тимчасово зберігає проміжні дані процесу виводу рішення. Якщо на деякому рівні процесу інтерпретації вибраний шлях виявився хибним, то відбувається відновлення необхідного вмісту регістрів зчитуванням даних із пам'яті магазину. 5 UA 109713 C2 5 10 15 20 25 30 35 40 45 50 55 60 На фіг. 7 наведено структуру слів бази знань, із яких складаються фрейми. Кожне слово бази знань містить 24-біти: байт ознак інтерпретації та інформаційне поле. Інформаційне поле залежно від типу поточного фрейму містить: фізичну адресу, що посилається на інший фрейм; фізичну адресу, що посилається на текстову константу; номер (ім'я) термінальної програми. На фіг. 8 наведено структуру байта ознак. Дане поле містить інформацію про тип фрейму та ознаки його інтерпретації. Кожен фрейм (фіг. 10) містить голову та елементи, пов'язані одним відношенням: альтернативи, послідовності чи ітерації. Голова та будь-який з елементів займають декілька послідовно розташованих комірок пам'яті, елементи одного фрейму також розташовуються послідовно, причому голова фрейму розташована першою в даній послідовності. Розмір фреймів (число елементів в одному фреймі) альтернативи чи послідовності може бути довільним, але скінченним. Фрейм ітерації складається із двох компонент: голови та посилання на ітерований елемент, яким є фрейм деякого довільного поняття, за виключенням визначеного у формі ітерації. Цим забезпечується зв'язність різних фреймів у єдину багаторазово вкладену структуру, що може містити рекурсивні конструкції. Складність опису (потужність множини понять, структура їхнього взаємозв'язку) може бути довільною та обмежується ресурсами конкретної реалізації (об'ємом оперативної пам'яті, об'ємом зовнішньої пам'яті, розрядністю вузлів та шин). Ті поняття бази знань, які не визначені через поняття бази знань, є термінальними та містять посилання на константи або термінальні програми, що у подальшому виконуються термінальним процесором 5. Описана таким чином інформаційна структура прикладної області є базою знань прикладної області. На фіг. 10 у формі орієнтованого циклічного графа наведено алгоритм роботи системи баз знань. При виконанні цього алгоритму співпроцесор 3 виконує набір процедур, зміст яких визначено у табл. З, де у якості змінних Rx та Ry можуть бути застосовані регістри R01-R09, ROI RЛМ. співпроцесор знань 3 безперервно виконує алгоритм фіг. 10 від початкової команди "старт" аж до зупинки тактового сигналу. В опису алгоритму використано наступні позначення: СПЗ співпроцесор знань 3, ТП - термінальний процесор 5, БЗ - база знань 32, ПМ - пам'ять магазину 33, ПС - пам'ять сліду 34, INP - пам'ять вхідного масиву, OUT - пам'ять вихідного масиву, ПП пам'ять програм 6. 1. Початкова установка: - Завантаження БЗ; - Завантаження бібліотек термінальних програм в ПП або формування (конфігурування) структури ТП; - Завантаження даних (аргументу обчислювальної функції) в масиви INP і OUT робочої пам'яті 9; - Установка регістрів у початковий стан, зокрема регістр R14:=00. - Перехід в стан 2. 2. Прийом завдання процесором СПЗ: - Якщо отримано завдання, то: - прийом від ТП адрес даних в R06, R07 та ознак інтерпретації (режиму інтерпретації в R10, R11, значення інверсії  2 в R13 та в R15:=X); - R01:= адреса БЗ; - запис значень регістрів [R06], [R07] в ПМ; - запис ознак інтерпретації (R14 - тип фрейму=00, режим інтерпретації – R10=0/1, R11=0/1, R12 - Інв_1=Х, R13 - Інв_2=0/1, R15=Х) в ПМ; - перехід в стан 3. - Якщо отримано значення істинності, то зберегти його в R09 та перейти в стан 21; - Інакше, очікування завдання поверненням до пункту 2. 3. Аналіз завдання і режиму його інтерпретації (R14+R10+R11) процесором СПЗ: - R02:= [R01] (вміст R01 записати в R02); - R03:- [R01] (вміст R01 записати в R03); - Читання першого слова фрейму, R10:= [поле ОС], R14:= [поле "тип фрейму"], R12:= [поле  1]. - Аналіз R14, R10 та R11: Якщо R14=(00)&(R10=0/1)&(R11=0/1), то переходимо до п. 4 (термінали), Якщо (R14=01/10)&R10=0&R11:=0, то перехід до п. 5 (розпізнавання альтернативи), Якщо R14=01& R10=0&R11=1, то перехід до п. 6 (породження альтернативи), Якщо R14=01&R10=1&R11=0, то перехід до п. 8 (розпізнавання альтернативи із слідом), 6 UA 109713 C2 5 10 15 20 25 30 35 40 45 50 55 60 Якщо R14=01&R10-1&R11=1, то перехід до п. 9 (породження альтернативи по сліду), Якщо R14=10&R10=0&R11=1, то перехід до п. 10 (породження послідовності), Якщо R14=10&R10=1&R11=1, то перехід до п. 12 (породження послідовності по сліду), Якщо R14=10&R10=1&R11=0, то перехід до п. 13 (розпізнавання послідовності із слідом), Якщо R14=11&R10=0&R11=0, то перехід до п. 15 (розпізнавання ітерації), Якщо R14=11&R10=0&R11=1, то перехід до п. 17 (породження ітерації), Якщо R14=11&R10=1&R11=0, то перехід до п. 18 (розпізнавання ітерації із слідом), Якщо R14=11&R10=1&R11=1, то перехід до п. 20 (породження ітерації по сліду). 4. Передача термінального завдання процесору ТП: - R01:= [перший та другий байти першого слова фрейму]; - Запис R06, R07 та ознак інтерпретації (тип фрейму - термінал; поточний режим інтерпретації - R10, R11; інверсія із завдання -  1) в ПМ; - Передача R01, R06, R07 та ознак інтерпретації процесору ТП; - Перехід в стан 2. 5. Розпізнавання альтернативи: - R02:= [R02] + 1; - R03:- [R02]; - Читання другого слова фрейму. R13:= [поле  2], R15:= [поле ОЕ], R10':= [значення (0/1) ознаки розпізнавання із слідом] або R11':= [значення (0/1) ознаки породження], R01:= [перший та другий байти другого слова фрейму]. - Запис значень регістрів [R06], [R07], [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму альтернативи та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2, R15 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R10=O, R11=0) в ПМ; - R10:=R10' R11=R11'; - Перехід в стан 3. 6. Породження альтернативи: - R10:= R10'; - Аналіз R10 (біта "ознака сліду", взятого з першого слова фрейму): якщо 0, то перехід в стан 21, інакше - в 7. 7. Встати на слід: - RC04:= [перший та другий байти першого слова фрейму]; - RC08:- [ПС за адресою RC04]; - R03:= [R02] + [RC08]; - Читання вибраного слова фрейму. R13:= [поле  2], R15:= [поле ОЕ], R01:- [перший та другий байти вибраного слова фрейму]. - Запис [R06], [R07] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму альтернативи та R12Інв_1 з першого слова фрейму; R13 - Інв_2, R15 - ОЕ з вибраного слова фрейму та поточний режим інтерпретації – R10=0/1, R11=1) в ПМ; - Перехід в стан 3. 8. Розпізнавання альтернативи із слідом: - RC08:= 1; - RC04:=[R05] + 1; - Запис [RC08] в ПС за адресою [RC04]; - R03:=[R02] + [RC08]; - Читання другого слова фрейму. R13:= [поле  2], R15:= [поле ОЕ], - R01= [перший та другий байти вибраного слова фрейму]. - Запис [R06], [R07], [R05], [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму альтернативи та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2, R15 - ОЕ з вибраного слова фрейму та поточний режим інтерпретації - R10=1, R11=0) в ПМ; -R05:= [RC04]; - Перехід в стан 3. 9. Породження альтернативи по сліду: - RC04:= [RC04] + 1; - RC08:= [ПС] за адресою [RC04]; - R03:= [R02] + [RC08]; - Читання вибраного слова фрейму. R13:= [поле  2], R15:= [поле ОЕ], - R01:= [перший та другий байти вибраного слова фрейму]. - Запис [R06], [R07] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму альтернативи та R12 Інв_1 з першого слова фрейму; R13 - Інв_2, R15 - ОЕ з вибраного слова фрейму та поточний режим інтерпретації - R10=1, R11=1) в ПМ; 7 UA 109713 C2 5 10 15 20 25 30 35 40 45 50 55 - Перехід в стан 3. 10. Породження послідовності: - R10:= R10'; - Аналіз R10 (біта "ознака сліду", взятого з першого слова фрейму): якщо 1, то переходимо в стан 11, інакше - в 12. 11. Встати на слід: - RC04:= [перший та другий байти першого слова фрейму]; - Перехід в стан 12. 12. Породження послідовності по сліду або без сліду: - R02:= [R02] + 1; - R03:= [R02]; - Читання другого слова фрейму. R13:= [поле  2], R15:= [поле ОЕ], R01:= [перший та другий байти другого слова фрейму]. - Запис значень регістрів [R06], [R07], [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму послідовності та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2, R15 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R10=0/1, R11=1) вПМ; - Перехід в стан 3. 13. Розпізнавання послідовності із слідом: - RC08:= 1; - RC04:= [R05]; - R03:- [R02] + [RC08]; - Читання другого слова фрейму. R13:= [поле 2], R15:= [поле ОЕ], R01:= [перший та другий байти другого слова фрейму]. - Запис [R06], [R07], [R05], [R02], [RC08] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму послідовності та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2, R15 - ОЕ з другого слова фрейму та поточний режим інтерпретації – R10=0/1, R11=1) в ПМ; - Перехід в стан 3. 14. Завершити породження ітерації по сліду: - RC08:= [RC08]-1; - R03:=[R02] + 1; - Читання другого слова фрейму. R13:= [поле  2], R01:= [перший та другий байти другого слова фрейму]. - Запис [RC08], [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму ітерації та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2 з другого слова фрейму та поточний режим інтерпретації – R10=0/1, R11=1) в ПМ; - Перехід в стан 3. 15. Розпізнавання ітерації: - R03:- [R02] + 1; - Читання другого слова фрейму. R13:= [поле  2], R15:= [поле ОЕ], R10':= [значення (0/1) ознаки розпізнавання із слідом] або R11':= [значення (0/1) ознаки породження], R01:= [перший та другий байти другого слова фрейму]. - Запис значень регістра [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму ітерації та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2, R15 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R10=0, R11=0) в ПМ; - R10:= R10'; R11:= R11'; - Перехід в стан 3. 16. Встати на слід: - RC04:= [другий та третій байти першого слова фрейму]; - RC08:= [ПС] по адресі RC04; - Якщо лічильник [RC08]≠0, то перехід в стан 14, інакше - в стан 19. 17. Породження ітерації: - R10:= R10'; - Аналіз R10 (біта "ознака сліду", взятого з першого слова фрейму): якщо 1, то переходимо в стан 16, інакше - в 19. 18. Розпізнавання ітерації із слідом: - RC04:=[R05] + 1; - RC08:=0; - Запис [RC08] в ПС по адресі RC04; - R03:=[R02]+ 1; 8 UA 109713 C2 5 10 15 20 25 30 35 40 45 50 55 60 - Читання другого слова фрейму. R13:= [поле  2], R01:= [перший та другий байти другого слова фрейму]. - Запис [R05], [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму ітерації та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2 з другого слова фрейму та поточний режим інтерпретації R10=1, R11=0) в ПМ; - R05:= [RC04]; - Перехід в стан 3. 19. Завершити породження ітерації без сліду: - R09:= R12; - Перехід в стан 21. 20. Породження ітерації по сліду: - RC04:= [RC04] + 1; - RC08:= [ПС] по адресі RC04; - Якщо [RC08] ≠ 0, то перехід в стан 14, інакше - в стан 19. 21. Прийом і аналіз прапорів: - Ознаки інтерпретації з магазину R10, R11, R12, R13, R14, R15:= [Верхній запис ПМ]; - R09:=[R09]  [R13]; - Аналіз R14, R09, R10 та R11: Якщо R14=(00)&R09=1&(R10=0/1)&(R11=0/1), то переходимо до п. 22 (прапор хибність на термінал), Якщо R14=(00)&R09=0&(R10=0/1)&(R11=0/1), то переходимо до п. 23 (прапор істина на термінал), Якщо R14=01&R09=0&R10=0&R11=0, то перехід до п. 24 (розпізнавання альтернативи після прапора істина), Якщо R14=01&R09=0&R10=1&R11=0, то перехід до п. 25 (розпізнавання альтернативи із слідом після прапора істина), Якщо R14=01&R09=0&R10=0/1&R11=1, то перехід до п. 27 (породження альтернативи після прапора істина), Якщо R14=01&R09=1&R10=0&R11=0, то перехід до п. 28 (розпізнавання альтернативи після прапора хибність), Якщо R14=01&R09=1&R10=1&R11=0, то перехід до п. 30 (розпізнавання альтернативи із слідом після прапора хибність), Якщо R14=01&R09=1&R10=0/1&R11=1, то перехід до п. 32 (породження альтернативи після прапора хибність), Якщо R14=10&R09=0&R10=0&R11=0, то перехід до п. 34 (розпізнавання послідовності після прапора істина), Якщо R14=10&R09=0&R10=1&R11=0, то перехід до п. 35 (розпізнавання послідовності із слідом після прапора істина), Якщо R14=10&R09=0&R10=0/1&R11=1, то перехід до п. 37 (породження послідовності після прапора істина), Якщо R14=10&R09=1&R10=0&R11=0, то перехід до п. 38 (розпізнавання послідовності після прапора хибність), Якщо R14=10&R09=1&R10=1&R11=0, то перехід до п. 40 (розпізнавання послідовності із слідом після прапора хибність), Якщо R14=10&R09=1&R10=0/1&R11=1, то перехід до п. 41 (породження послідовності після прапора хибність), Якщо R14=11&R09=0&R10=0&R11=0, то перехід до п. 42 (розпізнавання ітерації після прапора істина), Якщо R14=11&R09=0&R10=1&R11=0, то перехід до п. 43 (розпізнавання ітерації із слідом після прапора істина), Якщо R14=11&R09=0&R10=0/1&R11=1, то перехід до п. 44 (породження ітерації після прапора істина), Якщо R14=11&R09=1&R10=0&R11=0, то перехід до п. 46 (розпізнавання ітерації після прапора хибність), Якщо R14=11&R09=1&R10=1&R11=0, то перехід до п. 47 (розпізнавання ітерації із слідом після прапора хибність), Якщо R14=11&R09=1&R10=0/1&R11=1, то перехід до п. 48 (породження ітерації після прапора хибність). 22. Відновлення покажчиків INP, OUT: - R06:=[R06 iз ПМ]; 9 UA 109713 C2 5 10 15 20 25 30 35 40 45 50 55 60 - R07:=[R07 iз ПМ]; - Перехід в стан 2. 23. Набуття нових значень покажчиків INP, OUT: - Виштовхнути [R06], [R07] із ПМ; - Перехід в стан 2. 24. Розпізнавання альтернативи після прапора істина: - Виштовхнути [R02 з ПМ]; - Виштовхнути [R06 та R07] із ПМ. - R09:=[R09]  [R12]; - Перехід в стан 21. 25. Розпізнавання альтернативи із слідом після прапора істина: - R02:=[R02 iз ПМ]; - R03:= [R02]; - RC04:=[R05 iз ПМ]; - ОС першого слова фрейму:= 1; поля  1 та тип фрейму - відновити; - [перший та другий байти першого слова фрейму]:= [RC04]; - Виштовхнути [R06 та R07] із ПМ. - R09:=[R09]  [R12]; - Перехід в стан 21. 26. Вихід з розпізнавання альтернативи: - Виштовхнути [R02 із ПМ]; - R09:=[R09]  [R12]; - Перехід в стан 21. 27. Породження альтернативи по сліду після прапора істина: - Виштовхнути [R06 та R07] із ПМ. - R09:=[R09]  [R12]; - Перехід в стан 21. 28. Розпізнавання альтернативи після прапора хибність: - Відновлення покажчиків INP, OUT: R06:= [R06 з ПМ], R07:= [R07 з ПМ]; - Аналіз значення R15: якщо 1, перехід в стан 26, інакше - в стан 29. 29. Розпізнавання нового варіанта альтернативи: - R02:=[R02 iз ПМ] + 1; - R03:= [R02]; - Читання чергового слова фрейму альтернативи. R13:= [поле  2], R15:- [поле ОЕ], R10':= [значення (0/1) ознаки розпізнавання із слідом] або R11':= [значення (0/1) ознаки породження], R01:= [перший та другий байти вибраного слова фрейму]. - Запис значень регістрів [R06], [R07], [R02] в ПМ Запис ознак інтерпретації (R14 - тип фрейму альтернативи та R12 – Інв_1 з першого слова фрейму - тобто відновлення їхніх значень у магазині; R13 - Інв_2, R15 - ОЕ з чергового слова фрейму та відновити записаний у магазині вхідний режим інтерпретації – R10=0, R11=0) в ПМ; - R10:= R10'; R11:= R11'; - Перехід в стан 3. 30. Розпізнавання альтернативи із слідом після прапора хибність: - Відновлення покажчиків INP, OUT: R06:= [R06 з ПМ], R07:= [R07 з ПМ]; - Аналіз значення R15: якщо 1, перехід в стан 31, інакше - в стан 33. 31. Вихід із розпізнавання альтернативи із слідом: - Виштовхнути [R02 із ПМ]; - R05:= [R05 із ПМ]; - R09:= [R09]  [R12]; - Перехід в стан 21. 32. Породження альтернативи по сліду після прапора хибність: - Відновлення покажчиків R06:= [R06 із ПМ], R07:= [R07 із ПМ]; - R09:=[R09]  [R12]; - Перехід в стан 21. 33. Розпізнавання із слідом нового варіанта альтернативи: - RC04:= [R05 із ПМ] + 1; - RC08:= [RC08 із ПС]+ 1; - Запис [RC08] в ПС по адресі RC04; - R02:= [R02 із ПМ]; R03:= [R02] + [RC08]; - Читання чергового слова фрейму. R13:= [поле  2], R15:= [поле ОЕ], 10 UA 109713 C2 5 10 15 20 25 30 35 40 45 50 55 60 - R01:= [перший та другий байти вибраного слова фрейму]. - Запис [R06], [R07], [R05], [R02] в ПМ - ця запис відновлюється; - Запис ознак інтерпретації (R14 - тип фрейму альтернативи та R12 - Інв_1 з першого слова фрейму, відновлених з магазину; R13 - Інв_2, R15 - ОЕ з вибраного слова фрейму та поточний режим інтерпретації - R10=1, R11=0) в ПМ; - R05:= [RC04]; - Перехід в стан 3. 34. Розпізнавання послідовності після прапора істина: - Аналіз значення R15: якщо 1, перехід в стан 24, інакше - в стан 29. 35. Розпізнавання послідовності із слідом після прапора істина: - Аналіз значення R15: якщо 1, перехід в стан 25, інакше - в стан 36. 36. Продовжити розпізнавання послідовності із слідом: -RC08:= [RC08 із ПМ] + 1; R03:= [R02] + [RC08]; - Читання чергового слова фрейму. R13:= [поле  2], R15:= [поле ОЕ], R01:= [перший та другий байти вибраного слова фрейму]. - Запис [R06], [R07], [R05], [R02], [RC08] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму послідовності та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2, R15 - ОЕ з другого слова фрейму та поточний режим інтерпретації – R10=0/1, R11=1) в ПМ; - Перехід в стан 3. 37. Породженняпослідовності після прапора істина: - Аналіз значення R15: якщо 1, перехід в стан 24, інакше - в стан 39. 38. Розпізнавання послідовності після прапора хибність: - Відновлення покажчиків INP, OUT: R06:= [R06 з ПМ], R07:= [R07 з ПМ]; - Перехід в стан 26. 39. Продовжити породження послідовності: - R02:= [R02 із ПМ]+ 1; - R03:= [R02]; - Читання чергового слова фрейму послідовності. R13:= [поле  2], R15:= [поле ОЕ], R01:= [перший та другий байти другого слова фрейму]. - Запис [R06], [R07], [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму послідовності та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2, R15 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R10=0/1, R11=1) в ПМ; - Перехід в стан 3. 40. Розпізнавання послідовності із слідом після прапора хибність: - Відновлення покажчиків: R05:= [R05 із ПМ], R06:= [R06 із ПМ], R07:= [R07 із ПМ]; R10:= R10'; R11:= R11'; - Перехід в стан 26. 41. Породження послідовності після прапора хибність: - Відновлення покажчиків INP, OUT: R06:= [R06 із ПМ], R07:= [R07 із ПМ]; - R10:= R10'; R11=R11'; Виштовхнути [R02 із ПМ]; R09:= [R09]  [R12]; - Перехід в стан 21. 42. Розпізнавання ітерації після прапора істина: -R03:=[R02 iз ПМ] + 1; - Читання другого слова фрейму. R13:= [поле  2], R15:= [поле ОЕ], R10':= [значення (0/1) ознаки розпізнавання із слідом] або R11':= [значення (0/1) ознаки породження], R01:= [перший та другий байти другого слова фрейму]. - Запис значення регістра [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму ітерації та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2, R15 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R10=O, R11=0) в ПМ; - тобто тут просто збільшення лічильника магазину без фактичного запису (запис зберігається) - R10:= R10' R11:= R11'; - Перехід в стан 3. 43. Розпізнавання ітерації із слідом після прапора істина: - RC04:= [R05 із ПМ] + 1; RC08:= [RC08 із ПС по адресі RC04] + 1; - Запис [RC08] в ПС по адресі RC04; R03:= [R02 із ПМ] + 1; - Читання другого слова фрейму. R13:= [поле  2], R01:= [другий та третій байти другого слова фрейму]. - Запис [R05], [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму ітерації та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2 з другого слова фрейму та поточний режим інтерпретації – R10=l, R11=0) в ПМ; - тобто тут просто збільшення лічильника магазину без фактичного запису (запис зберігається) 11 UA 109713 C2 5 10 15 20 25 - Перехід в стан 3. 44. Породження ітерації після прапора істина: - RC08:=[RC08 iз ПМ]; - Аналіз [RC08]: якщо [RC08] ≠ 0, то перехід в стан 45, інакше - в стан 46. 45. Продовжити породження ітерації після прапора істина: - RC08:= [RC08] - 1; R03:= [R02 із ПМ] + 1; - Читання другого слова фрейму. R13:= [поле  2], R01:= [перший та другий байти другого слова фрейму]. - Запис [RC08], [R02] в ПМ. Запис ознак інтерпретації (R14 - тип фрейму ітерації та R12 - Інв_1 з першого слова фрейму; R13 - Інв_2 з другого слова фрейму та поточний режим інтерпретації – R10=0/1, R11=1) в ПМ; - Перехід в стан 3. 46. Завершити породження ітерації та розпізнавання ітерації після прапора хибність: - Виштовхнути [R02 із ПМ]; -R09:- [R12]; - Перехід в стан 21. 47. Розпізнавання ітерації із слідом після прапора хибність: - R03:= [R02 із ПМ]; RC04:= [R05 із ПМ]; - ОС першого слова фрейму:= 1; поля 11 та тип фрейма - відновити; - [перший та другий байти першого слова фрейму]:= [RC04]; -R09:= [R12]; - Перехід в стан 21. 48. Породження ітерації після прапора хибність: - Виштовхнути [R02 із ПМ]; Виштовхнути [RC08 із ПМ]; - R09:= [R12]; - Перехід в стан 21. Оскільки система обробки знань підтримує системний шинний інтерфейс (наприклад, АРВ), то вона може бути легко інтегрована в сучасні мікропроцесорні системи на кристалі з метою розширення їхнього набору команд. Таблиця 1 Блок Б01 Б02 Б03 Б04 Б05 Б06 Б07 Б08 Б09 БOI БЛМ БDT БЗ БDT ПМ БDT ПС Регістр, який містить Розрядність, біт блок R01 16 R02 16 R03 16 RC04 16 R05 16 R06 16 R07 16 RC08 16 R09 16 R10 1 R11 1 R12 1 ROI R13 1 R14 3 R15 1 16 RDT БЗ 16 RDT ПМ 16 RDT ПС 16 Опис регістра Регістр імені структури Регістр номера слова фрейму Регістр адреси бази знань Регістр координати сліду Регістр вершини сліду Регістр адреси у вхідному масиві Регістр адреси у вихідному масиві Регістр лічильника ітерації Регістр істинності Регістр ознаки сліду Регістр ознаки породження Регістр Інв_1 Регістр Інв_2 Регістр типу фрейму Регістр ознаки останнього елемента Регістр лічильника магазину Регістр даних пам'яті бази знань Регістр даних пам'яті магазину Регістр даних пам'яті сліду 30 Таблиця 2 № 1 2 3 Ім'я команди LD ¬R12, R09 LD 0, RC08 LD DTПВВ, R01 Опис команди Завантаження інверсії регістра R12 у R09 Завантаження "0" у регістр RC08 Завантаження зовнішніх даних у R01 12 UA 109713 C2 Продовження таблиці 2 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 LD DTПВВ, R02 LD DTПВВ, R03 LD DTПВВ, RC04 LD DTПВВ, R05 LD DTПВВ, R06 LD DTПВВ, R07 LD DTПВВ, RC08 LD DTПВВ, R09 LD DTПВВ, RDT БЗ LD DTПВВ, RDT ПМ LD DTПВВ, RDT ПС LD DTПВВ. RЛМ LD DTПВВ, ROI LD R01, R02 LD R01, R03 LDR01, RDT БЗ LD R01, RБ LDR02+1, R02 LD R02, R03 LD R02, RDT ПМ LD R02, RDT ПС LD R03, RDT БЗ LDRC04+1, RC04 LD RC04, R05 LD R05+1, RC04 LD R05, RDT ПМ LD R06, RDT ПМ LD R06, RБ LD R07, RDT ПМ LD R07, RБ LD RC08-1, RC08 LD RC08+1, RC08 LD RC08, RDT ПМ LD RC08, RDT ПС LD RC08, RБ LD R09  R13, R09 LD R09, RБ LD R10, RБ LDRAMБ3,R01 LD RAMБ3, R02 LD RAMБ3, RC04 LD RAMБ3, R10 LD RAMБ3, R10 LD RAMПМ, R01 LD RAMПМ, R02 LD RAMПМ, R05 LD RAMПМ, R06 LD RAMПМ, R07 LD RAMПС, R02 LD RAMПС, RC08 LD ROI, RDT ПМ RDRAMБ3 RDRAMПМ RDRAMПС REQ_TERM_PRG Завантаження зовнішніх даних у R02 Завантаження зовнішніх даних у R03 Завантаження зовнішніх даних у RC04 Завантаження зовнішніх даних у R05 Завантаження зовнішніх даних у R06 Завантаження зовнішніх даних у R07 Завантаження зовнішніх даних у RC08 Завантаження зовнішніх даних у R09 Завантаження зовнішніх даних у RDT Б3 Завантаження зовнішніх даних у RDT ПМ Завантаження зовнішніх даних у RDT ПС Завантаження зовнішніх даних у RЛМ Завантаження зовнішніх даних у R01 Завантаження даних із R01 у R02 Завантаження даних із R01 у R03 Завантаження даних із R01 у RDT БЗ Завантаження даних із R01 у RБ Інкремент R02 Завантаження даних із R02 у R03 Завантаження даних із R02 у RDT ПМ Завантаження даних із R02 у RDT ПС Завантаження даних із R03 у RDT БЗ Інкремент RC04 Завантаження даних із RC04 у R05 Інкремент R05 та запис у RC04 Завантаження даних із R05 у RDT ПМ Завантаження даних із R06 у RDT ПМ Завантаження даних із R06 у RB Завантаження даних із R07 у RDT ПМ Завантаження даних із R07 у RB Декремент RC08 Інкремент RC08 Завантаження даних із RC08 у RDT ПМ Завантаження даних із RC08 у RDT ПС Завантаження даних із RC08 у RБ Завантаження даних із R09  R13 у R09 Завантаження даних із R09 у RБ Завантаження даних із R10 у RБ Завантаження даних із RAMБ3 у R01 Завантаження даних із RAMБ3 у R02 Завантаження даних із RAMБ3 у RC04 Завантаження даних із RAMБ3 у R10 Завантаження даних із RAMБ3 у Rn Завантаження даних із RAMПМ у R01 Завантаження даних із RAMПМ у R02 Завантаження даних із RAMПМ у R05 Завантаження даних із RAMПМ у R06 Завантаження даних із RAMПМ у R07 Завантаження даних із RAMПС у R02 Завантаження даних із RAMПС у RC08 Завантаження даних із ROI у RDT ПМ Зчитування даних із пам'яті бази знань Зчитування даних із пам'яті магазину Зчитування даних із пам'яті сліду Запит на обробку термінальної програми 13 UA 109713 C2 Продовження таблиці 2 59 60 61 WRRAMБ3 WRRAMПМ WR RAMПС Запис даних у пам'ять бази знань Запис даних у пам'ять магазину Запис даних у пам'ять сліду Таблиця 3 4 5 6 7 Реалізація процедур Вміст Rx записати в Rv LD Rx, Rv LD Ry, RRA Зчитування слова із оперативної пам'яті по адресі, що RDRAM міститься в Ry, та запис в Rx LD DATARAM, Rx LD BLy, BLWA Запис даних з регістра Rx в оперативну пам'ять, по адресі, LD BLx, BLDT що знаходиться в Ry WRRAM Інкремент даних у Rx та їх запис у Rv LDRx+1,Ry Декремент даних у Rx та їх запис у Rv LDRx-1,Ry Запис "0»у Rx LD 0, Rx Запис "1" у Rx LD1,Rx 8 Інвертування Rx та запис результату в Ry 9 Завантаження зовнішніх даних у Rx 10 Зчитування першого слова фрейму 11 Аналіз Rx 12 Передача Rx до термінального процесора № Базова процедура 1 2 3 базових LD R x , Ry LD DTПВВ, Rx LD R02, RRA RDRAM LDRx, RБ LD Rx, RБ REQ_TER_PROGR ФОРМУЛА ВИНАХОДУ 5 10 15 20 25 30 Система баз знань, що містить головний комп'ютер, оперативну пам'ять, перший блок вводувиводу, перший блок управління, арифметико-логічний блок, робочу пам'ять, регістр даних та регістр-лічильник координат вхідного масиву, у якому перший вхід-вихід першого блока вводувиводу разом із входами-виходами оперативної пам'яті підключений до системної шини пристрою, другий вхід-вихід першого блока вводу-виводу підключений до входів-виходів регістра-лічильника координат вхідного масиву, третій вхід-вихід першого блока вводу-виводу разом із входами-виходами арифметико-логічного блока, входом-виходом першого блока управління та першими входами-виходами першого регістра даних, з'єднаного другими входами-виходами з входами-виходами робочої пам'яті, підключений до шини даних, яка відрізняється тим, що в неї введено регістр-лічильник координат вихідного масиву, мультиплексор, другий та третій блоки вводу-виводу, буферний регістр, блоки імені структури, номера слова фрейму, адреси бази знань, координати сліду, вершини сліду, адреси у вхідному масиві, адреси у вихідному масиві, лічильника ітерації, істинності, лічильника магазину та ознак інтерпретації, пам'ять бази знань, пам'ять магазину, пам'ять сліду, блок даних пам'яті бази знань, блок даних пам'яті магазину, блок даних пам'яті сліду, при цьому четвертий вхід-вихід першого блока вводу-виводу підключений до входів-виходів регістра-лічильника координат вихідного масиву, чий вихід разом із виходом регістра-лічильника координат вхідного масиву підключений через мультиплексор до адресних входів робочої пам'яті, головний комп'ютер через другий блок вводу-виводу разом із входами-виходами третього блока вводу-виводу підключені до системної шини пристрою, перший вихід третього блока вводу-виводу підключено до першого входу другого блока управління, перший вихід якого підключено до першого входу третього блока вводу-виводу, другий вихід другого блока управління підключено до перших входів блоків імені структури, номера слова фрейму, координати сліду, адреси у вхідному масиві, адреси у вихідному масиві, лічильника ітерації, істинності та ознак інтерпретації, третій вихід другого блока управління підключено до перших входів блоків адреси бази знань, даних пам'яті бази знань, лічильника магазину, даних пам'яті магазину, вершини сліду та даних пам'яті сліду, другий вихід другого блока вводу-виводу підключено до других входів блоків імені 14 UA 109713 C2 5 10 15 20 25 30 структури, номера слова фрейму, адреси бази знань, координати сліду, вершини сліду, адреси у вхідному масиві, адреси у вихідному масиві, лічильника ітерації, істинності, лічильника магазину, ознак інтерпретації, даних пам'яті бази знань, даних пам'яті магазину та даних пам'яті сліду, вихід пам'яті бази знань підключено до третіх входів другого блока управління, третього блока вводу-виводу, блоків імені структури, номера слова фрейму та ознак інтерпретації, вихід пам'яті магазину підключено до четвертого входу блока імені структури, до четвертого входу блока номера слова фрейму, до третіх входів блоків координат сліду, адреси у вхідному масиві та адреси у вихідному масиві, вихід пам'яті сліду підключено до п'ятого входу блока номера слова фрейму та до третього входу блока лічильника ітерації, вихід блока імені структури підключено до шостого входу буферного регістра, до третього входу блока адреси бази знань, до шостого входу блока номера слова фрейму, до третього входу блока даних пам'яті бази знань, до шостого входу блока даних пам'яті магазину та до третього входу блока даних пам'яті сліду, вихід блока номера слова фрейму підключено до четвертого входу блока адреси бази знань, вихід блока координати сліду підключено до другого входу блока даних пам'яті магазину та до четвертого входу блока вершини сліду, вихід блока адреси у вхідному масиві підключено до четвертого входу блока даних пам'яті магазину та до п'ятого входу буферного регістра, вихід блока адреси у вихідному масиві підключено до п'ятого входу блока даних пам'яті магазину та до четвертого входу буферного регістра, вихід блока лічильника ітерації підключено до другого входу буферного регістра, до сьомого входу блока даних пам'яті магазину та до четвертого входу блока даних пам'яті сліду, вихід блока істинності підключено до першого входу буферного регістра, вихід блока ознак інтерпретації підключено до третього входу блока істинності, до третього входу буферного регістра та до восьмого входу блока даних пам'яті магазину, четвертий вихід другого блока управління підключено до входів управління пам'яті бази знань, магазину та сліду, адресні входи яких з'єднані із виходами блока адреси бази знань, лічильника магазину та блока вершини сліду відповідно, вихід блока даних пам'яті бази знань підключено до входу даних пам'яті бази знань, вихід блока лічильник магазину підключено до четвертого входу блока даних пам'яті бази знань, вихід блока даних пам'яті магазину підключено до входу даних пам'яті магазину, вихід блока вершини сліду підключено до четвертого входу блока координати сліду, вихід блока даних пам'яті сліду підключено до входу даних пам'яті сліду, вихід буферного регістра підключено до других входів третього блока вводу-виводу та другого блока управління. 15 UA 109713 C2 16 UA 109713 C2 17 UA 109713 C2 18 UA 109713 C2 19 UA 109713 C2 Комп’ютерна верстка Г. Паяльніков Державна служба інтелектуальної власності України, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601 20