Процесор баз знань

Реферат: Процесор баз знань належить до обчислювальної техніки та може бути використаний при побудові систем, заснованих на знаннях (knowledge-based systems). Процесор баз знань містить головний комп'ютер, універсальний процесор, оперативну пам'ять, два блоки вводувиводу, блок управління, регістр кореня бази знань, два регістри команд, регістр даних, регістр імені структури, регістр номера слова фрейму, регістр адреси бази знань, регістр координати сліду, регістр вершини сліду, регістр ітерації, регістр ознак сліду, регістр ознак породження, додатковий регістр ознак сліду, додатковий регістр ознак породження, регістр першої інверсії, регістр другої інверсії, регістр типу фрейму, регістр ознак останнього елемента, регістр істинності, дванадцять мультиплексорів, стек адрес даних, стек регістрів, стек ознак, суматор та два суматори по модулю два. Технічним результатом є: 1) знання зберігаються у вигляді множини визначень термінів та відокремлено від алгоритму їхньої обробки; 2) алгоритм роботи пристрою апаратно "зашитий" у блок керування; 3) знання, що містяться у базі знань зберігаються у вигляді ієрархічної структури, яка значно підвищує ефективність пошуку рішення за рахунок логічного виводу тільки у необхідній частині бази знань; 4) зберігається структура логічного виводу, яка в подальшому може бути використана для пояснення ходу логічного виводу або породження нової структури даних; 5) надається можливість ефективно зберігати та інтерпретувати ітераційні та рекурсивні структури даних, які містять визначення з використанням відношень альтернативи, послідовності та ітерації. UA 109324 C2 (12) UA 109324 C2 UA 109324 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); переміщення даних; логічного зсуву та переходу. Блок управління керує роботою всіх модулів процесора продукційних правил, а також процесом обміну даними між пам'яттю правил та блоком вводувиводу. Оперативна пам'ять містить набір команд фіксованої довжини. Кожна команда містить такі поля: "тип команди", "прапор" (умова (condition)/дія (action)) та два операнди. Якщо поточна команда у полі "прапор" містить умову, то відбувається порівняння операндів у залежності від коду поля "тип команди". Якщо команда характеризується як дія, то над поточними операндами виконується дія, зазначена у полі "тип команди". Серед недоліків прототипу можна вказати наступні. 1. Необхідність виконання великої кількості обчислень у процесі пошуку активної продукції при співставленні антецедентів. Це пов'язано із тим, що між продукційними правилами, які містяться в оперативній пам'яті у вигляді команд спеціального формату, відсутній ієрархічний зв'язок. 2. Відсутність механізму пояснення логічного виводу. 3. Відсутність ефективного представлення у пам'яті ітераційних та рекурсивних структур. Спільними ознаками прототипу та пропонованої моделі є головний комп'ютер, перший блок вводу-виводу, оперативна пам'ять та блок управління. В основу винаходу поставлена задача побудови спеціалізованого процесора баз знань. Всяка задача, поставлена у вигляді імені функції та значення її аргументу, вирішується виводом рішення у процесі інтерпретації бази знань. База знань складається із структури взаємозв'язаних визначень термінів, кожне з яких представляється у формі одного з п'яти фреймів: альтернативи, послідовності, ітерації, текстової константи або терміналу. Усякий фрейм - послідовність слів фіксованої довжини 1 UA 109324 C2 5 10 15 20 25 30 35 40 45 50 55 60 (наприклад, трьохбайтових), серед яких розрізняється перше слово, а в кожному зі слів перший байт і наступні. Фрейми текстової константи й термінала - однослівні, ітерації двослівні, альтернативи й послідовності - багатослівні. Фрейми визначень всіх термінів всякої бази знань розміщено у пам'яті бази знань у вигляді ієрархічної структури, що усуває проблему множини конфліктних правил. Така організація бази знань дозволяє ефективно зберігати та інтерпретувати ітераційні й рекурсивні структури визначень. Ще однією відмінністю моделі є те, що структура процесу виводу рішення зберігається спеціальними засобами ведення сліду. З метою розширення функціональних можливостей інтерпретації рекурсивних, ітераційних та вкладених структур і формування структури виводу рішення задачі у прототип, що містить перший блок вводу-виводу, оперативну пам'ять, блок управління та головний комп'ютер, вхідвихід якого підключений до перших входів-виходів першого блока вводу-виводу, чий другий вхід-вихід підключено системною шиною до входів-виходів оперативної пам'яті, введено універсальний процесор, другий блок вводу-виводу, регістр кореня бази знань, два регістри команд, чотирнадцять регістрів даних, імені структури, номера слова фрейму, адреси бази знань, координати сліду, вершини сліду, ітерації, ознак сліду, ознак породження, першої інверсії, другої інверсії, типу фрейму, ознак останнього елемента та істинності, додатковий регістр ознак сліду, додатковий регістр ознак породження, дванадцять мультиплексорів, три стеки адрес даних, регістрів та ознак, суматор та два суматори по модулю два, при цьому входи-виходи універсального процесора разом із першими входами-виходами другого блока вводу-виводу з'єднані із системною шиною, другий вхід-вихід другого блока вводу-виводу підключено до першого входу-виходу регістра даних, другий вхід-вихід якого підключено до входу-виходу стеку адрес даних, перший вихід другого блока вводу-виводу підключено до входу регістра кореня бази знань, чий вихід з'єднано з першими входами третього та четвертого мультиплексорів та із входом регістра імені структури, вихід якого підключено до перших входів другого та п'ятого мультиплексорів та до другого входу першого мультиплексора, чий перший вхід разом із другим входом другого мультиплексора з'єднаний із виходом суматора, третій вхід з'єднаний із першим виходом стеку регістрів, а вихід підключено до входу регістра номера слова фрейму, вихід якого підключено до першого входу стеку регістрів та до першого входу суматора, чий другий вхід разом із першими входами блока управління, стеку ознак та четвертим входом п'ятого мультиплексора підключений до виходу регістра ітерації, вихід другого мультиплексора підключено до входу регістра адреси бази знань, вихід якого з'єднаний із другим входом п'ятого мультиплексора, чий третій вхід разом із входом регістра вершини сліду з'єднаний із виходом регістра координати сліду, вхід якого підключений до виходу третього мультиплексора, чий другий вхід з'єднаний із другим виходом стеку регістрів, а третій вхід разом із другим входом стеку регістрів підключений до виходу регістра вершини сліду, вихід першого регістра команд підключено до входу другого блока вводу-виводу, чий другий вихід підключено до входу другого регістра команд, вихід якого підключено до третього входу блока управління та до перших входів шостого, сьомого, восьмого, дев'ятого, десятого, одинадцятого мультиплексорів та до входів додаткових регістрів ознак сліду та породження, чиї виходи підключені до других входів шостого та сьомого мультиплексорів відповідно, треті входи яких разом із другими входами восьмого, дев'ятого, десятого та одинадцятого мультиплексорів підключені до другого виходу стеку ознак, чий перший вихід підключений до другого входу четвертого мультиплексора, вихід якого з'єднаний із входом регістра ітерації, виходи шостого, сьомого, восьмого, дев'ятого, десятого та одинадцятого мультиплексорів з'єднані із входами регістрів ознак сліду, ознак породження, першої інверсії, другої інверсії, типу фрейму та ознак останнього елемента відповідно, перші виходи регістрів ознак сліду, ознак породження, типу фрейму та ознак останнього елемента підключено до другого входу першого регістра команд та до четвертого входу блока управління, чий вихід підключено до першого входу першого регістра команд, третій вхід якого підключений до виходу п'ятого мультиплексора, другі виходи регістрів ознак сліду, ознак породження, першої інверсії, другої інверсії, типу фрейму та ознак останнього елемента підключено до другого входу стеку ознак, другий вихід регістра першої інверсії підключено до першого входу першого суматора по модулю два та до першого входу дванадцятого мультиплексора, перший вихід регістра другої інверсії підключено до першого входу другого суматора по модулю два, чий другий вхід разом із другим входом першого суматора по модулю два та другим входом блока управління підключений до виходу регістра істинності, вхід якого з'єднаний із виходом дванадцятого мультиплексора, чиї другий і третій входи підключені до виходів першого та другого суматора по модулю два відповідно. Відмітними ознаками запропонованого процесора баз знань від відомого прототипу є: 1) знання зберігаються у вигляді множини визначень термінів та відокремлено від алгоритму їх обробки; 2) знання зберігаються у вигляді ієрархічної структури, яка значно підвищує 2 UA 109324 C2 5 10 15 20 25 30 35 40 45 50 55 60 ефективність пошуку рішення за рахунок логічного виводу тільки у необхідній частині бази знань; 3) зберігається структура логічного виводу, яка в подальшому може бути використана для пояснення ходу логічного виводу або породження нової структури даних; 4) надається можливість ефективно зберігати та інтерпретувати ітераційні та рекурсивні структури даних, які містять визначення з використанням відношень кон'юнкції, диз'юнкції та інверсії. На фіг. 1 наведено структуру процесора баз знань, на фіг. 2 наведено структуру блока управління, на фіг. 3 наведено структуру багатовхідного регістра, на фіг. 4 наведено структуру реверсивного регістра, на фіг. 5 наведено структуру запису стеку 17 регістрів та пам'яті сліду, на фіг. 6 наведено структуру слова бази знань, на фіг. 7 наведено структуру байта ознак слова бази знань та записів у стеку 45 ознак, на фіг. 8 наведено структуру шаблонів фреймів альтернативи, послідовності, ітерації, текстової константи та терміналу, на фіг. 9 наведено граф алгоритму роботи процесора баз знань. У табл. наведено ім'я, формат та призначення регістрів. Процесор баз знань (фіг. 1) складається із: головного комп'ютера 1, модуля розширення функціональності 2, спеціалізованого процесора 3, першого блока вводу-виводу 4, універсального процесора 5, оперативної пам'яті 6, другого блока вводу-виводу 7, регістра RКБЗ 8 кореня бази знань, першого RКОМ1 9 та другого RКОМ2 10 регістрів команд, регістра RД 11 даних, стеку 12 адрес даних, регістра R01 13 імені структури, блока 14 управління, першого мультиплексора MX1 15, регістра R02 16 номера слова фрейму, стеку 17 регістрів, додаткового * * регістра R07 18 ознак сліду, додаткового регістра R08 19 ознак породження, шостого мультиплексора МХ6 20, сьомого мультиплексора МХ7 21, регістра R07 22 ознак сліду, регістра R08 23 ознак породження, регістра RC06 24 ітерації, восьмого мультиплексора МХ 8 25, регістра R09 26 першої інверсії, суматора  27, третього мультиплексора МХ3 28, дев'ятого мультиплексора МХ9 29, регістра R10 30 другої інверсії, другого мультиплексора МХ 2 31, регістра RC04 32 координати сліду, регістра R05 33 вершини сліду, четвертого мультиплексора МХ 4 34, десятого мультиплексора МХ10 35, регістра типу фрейму R11 36, одинадцятого мультиплексора МХ11 37, регістра R12 38 ознаки останнього елемента, регістра R03 39 адреси бази знань, п'ятого мультиплексора МХ5 40, регістра R13 41 істинності, дванадцятого мультиплексора МХ 12 42, першого 43 та другого 44 суматорів по модулю два та стеку 45 ознак. Головний комп'ютер 1 призначений для постановки завдання, зчитування результатів роботи модуля розширення функціональності 2 та конфігурації роботи модуля 2. Універсальний процесор 5 керує роботою усіх блоків із складу модуля 2 та виконує термінальні програми на замовлення спеціалізованого процесора 3. Спеціалізований процесор 3 розширює набір команд універсального процесора 5 та разом із ним виконує апаратну обробку завдання, що надійшло від головного комп'ютера 1. Блок вводу-виводу 7 реалізує інтерфейс між універсальним 5 та спеціалізованим 3 процесорами. Вхід-вихід головного комп'ютера 1 підключений до перших входів-виходів першого блока 4 вводу-виводу, чий другий вхід-вихід підключений системною шиною до входів-виходів універсального процесора 5, оперативної пам'яті 6 та до перших входів-виходів другого блока 7 вводу-виводу. Другий вхід-вихід другого блока 7 вводу-виводу підключено до першого входувиходу регістра 11 даних, чий другий вхід-вихід підключено до входу-виходу стеку 12 адрес даних. Перший вихід другого блока 7 вводу-виводу підключено до входу регістра 8 кореня бази знань, чий вихід з'єднано з першими входами третього 28 та четвертого 34 мультиплексорів та із входом регістра 13 імені структури. Вихід регістра 13 імені структури підключено до перших входів другого 31 та п'ятого 40 мультиплексорів та до другого входу першого 15 мультиплексора, чиї перший вхід разом із другим входом другого 31 мультиплексора з'єднаний із виходом суматора 27, третій вхід з'єднаний із першим виходом стеку 17 регістрів, а вихід підключено до входу регістра 16 номера слова фрейму. Вихід регістра 16 номера слова фрейму підключено до першого входу стеку 17 регістрів та до першого входу суматора 27, чий другий вхід разом із першими входами блока 14 управління, стеку 45 ознак та четвертим входом п'ятого мультиплексора 40 підключений до виходу регістра 24 ітерації. Вихід другого мультиплексора 31 підключено до входу регістра 39 адреси бази знань, вихід якого з'єднаний із другим входом п'ятого мультиплексора 40, чий третій вхід разом із входом регістра 33 вершини сліду з'єднаний із виходом регістра 32 координати сліду. Вхід регістра 32 координати сліду підключений до виходу третього мультиплексора 28, чий другий вхід з'єднаний із другим виходом стеку 17 регістрів, а третій вхід разом із другим входом стеку 17 регістрів підключений до виходу регістра 33 вершини сліду. Вихід першого регістра 9 команд підключено до входу другого блока 7 вводу-виводу, чий другий вихід підключено до входу другого регістра 10 команд, вихід якого підключено до третього входу блока 14 управління та до перших входів шостого 20, сьомого 21, восьмого 25, дев'ятого 29, десятого 35, одинадцятого 37 мультиплексорів та до входів додаткових регістрів ознак сліду 18 та породження 19. Виходи додаткових регістрів ознак 3 UA 109324 C2 5 10 15 20 25 30 35 40 45 50 55 сліду 18 та породження 19 підключені до других входів шостого 20 та сьомого 21 мультиплексорів відповідно, треті входи яких разом із другими входами восьмого 25, дев'ятого 29, десятого 35 та одинадцятого 37 мультиплексорів підключені до другого виходу стеку 45 ознак. Перший вихід стеку 45 ознак підключений до другого входу четвертого 34 мультиплексора, вихід якого з'єднаний із входом регістра 24 ітерації. Виходи шостого 20, сьомого 21, восьмого 25, дев'ятого 29, десятого 35 та одинадцятого 37 мультиплексорів з'єднані із входами регістрів ознак сліду 22, ознак породження 23, першої інверсії 26, другої інверсії 30, типу фрейму 36 та ознак останнього елемента 38 відповідно. Перші виходи регістрів ознак сліду 22, ознак породження 23, типу фрейму 36 та ознак останнього елемента 38 підключено до другого входу першого регістра 9 команд та до четвертого входу блока 14 управління, чий вихід підключено до першого входу першого регістра 9 команд, третій вхід якого підключений до виходу п'ятого мультиплексора 40. Другі виходи регістрів ознак сліду 22, ознак породження 23, першої інверсії 26, другої інверсії 30, типу фрейму 36 та ознак останнього елемента 38 підключено до другого входу стеку 45 ознак. Другий вихід регістра 26 першої інверсії підключено до першого входу першого суматора 43 по модулю два та до першого входу дванадцятого мультиплексора 42, перший вихід регістра 30 другої інверсії підключено до першого входу другого суматора 44 по модулю два, чий другий вхід разом із другим входом першого суматора 43 по модулю два та другим входом блока 14 управління підключений до виходу регістра 41 істинності. Вхід регістра 41 істинності з'єднаний із виходом дванадцятого мультиплексора 42, чиї другий і третій входи підключені до виходів першого 43 та другого 44 суматора по модулю два відповідно. Блок 7 вводу-виводу виконує обмін командами та даними між універсальним 5 і спеціалізованим 3 процесорами як при початковій ініціалізації вмісту регістрів та структурованих пам'ятей 12, 17 та 45, так і в процесі рішення задач. Пам'яті 12, 17 та 45 розміщені на кристалі програмованої логічної інтегральної схеми. Головною їхньою функцією є тимчасове (при наявності живлення кристалу) збереження даних, необхідних в процесі роботи пристрою. Блок 14 управління (фіг. 2) складається із трьох модулів: логіка переходів 46, пам'ять станів 47 та вихідна логіка 48. Блок 14 управління за результатами аналізу кодів на першому, другому, третьому та четвертому входах формує на його виходах команди управління блоком 7 вводувиводу та операційною частиною спеціалізованого процесора 3. Логіка переходів 46 визначає наступний стан блока 14 управління, що є функцією від поточного стану пам'яті станів 47 та кодів на входах блока 14 управління. Команди на виходах блока 14 управління визначаються вихідною логікою 48 та є функцією від поточного стану пам'яті станів 47. Структуру багатовхідного регістра (RКОМ1, RД) зображено на фіг. 3. Багатовхідний регістр складається із мультиплексора MXі та регістра Rі. На вхід регістра Rі надходять дані з виходу MXі та відповідна команда запису. При надходженні команди відбувається комутація відповідного входу мультиплексора MXі із його виходом та дані з виходу мультиплексора MX і записуються у регістр Rі. Структуру реверсивного регістра (RC04, RC06) зображено на фіг. 4. Реверсивний регістр складається із мультиплексора МХі, арифметико-логічного пристрою та регістра Rі. При надходженні команди відбувається комутація відповідного входу даних мультиплексора MX і із його виходом та запис у регістр Rі. База знань (БЗ) представляється у формі інформаційної структури множини визначень, вузлами якої є поняття (термінальні - константи чи іменовані процедури, або не термінальні), а дугами - відношення альтернативи, послідовності чи ітерації, що зв'язують поняття (вузли) визначальної частини всякого визначення. Пам'ять бази знань зберігає знання у машинній формі, що складається із множини фреймів, кожний із яких має структуру масиву слів фіксованої довжини (наприклад, 3 байти). Розмір фрейму залежить від типу відношення, яке він описує, та від числа понять у визначальній частині і може складати від одного до деякого скінченного числа слів. Пам'ять сліду зберігає структуру виводу рішення задачі. Вона може бути використана для пояснення процесу рішення задачі або при породженні наслідку. На фіг. 5 наведено структуру запису пам'яті сліду, стеку 12 адрес даних та стеку 17 регістрів. Кожен запис стеку 45 ознак складається із 8-ми біт. На фіг. 6 наведено структуру слів бази знань, із яких складаються фрейми. Кожне слово бази знань містить 24-біти: байт ознак інтерпретації та інформаційне поле. Інформаційне поле залежно від типу поточного фрейму містить: фізичну адресу, що посилається на інший фрейм, фізичну адресу, що посилається на текстову константу, або номер (ім'я) термінальної програми. 4 UA 109324 C2 5 10 15 20 25 30 35 40 45 50 55 60 На фіг. 7 наведено структуру байта ознак, що містить інформацію про тип фрейму та ознаки його інтерпретації. Кожен фрейм (фіг. 8) містить голову та елементи, пов'язані одним відношенням: альтернативи, послідовності чи ітерації. Голова та будь-який з елементів займають декілька послідовно розташованих комірок пам'яті, елементи одного фрейму також розташовуються послідовно, причому голова фрейму розташована першою в даній послідовності. Розмір фреймів (число елементів в одному фреймі) альтернативи чи послідовності може бути довільним, але скінченним. Фрейм ітерації складається із двох компонент: голови та посилання на ітерований елемент, яким є фрейм деякого довільного поняття, за виключенням визначеного у формі ітерації. Цим забезпечується зв'язність різних фреймів у єдину багаторазово вкладену структуру, що може містити рекурсивні конструкції. Складність опису (потужність множини понять, структура їхнього взаємозв'язку) може бути довільною та обмежується ресурсами конкретної реалізації (об'ємом оперативної пам'яті, об'ємом зовнішньої пам'яті, розрядністю вузлів та шин). Ті поняття бази знань, які не визначені через поняття бази знань, є термінальними та містять посилання на константи або термінальні програми, що у подальшому виконуються універсальним процесором 5. Описана таким чином інформаційна структура прикладної області є базою знань прикладної області. На фіг. 9 у формі орієнтованого циклічного графу наведено алгоритм роботи процесора баз знань. Пристрій працює наступним чином, безперервно виконуючи алгоритм фіг. 9 від початкової команди "старт" аж до зупинки тактового сигналу. В опису алгоритму використано наступні позначення: СП - спеціалізований процесор 3, УП - універсальний процесор 5, БЗ - база знань, ПС - пам'ять сліду, САД - стек 12 адрес даних, CP - стек 17 регістрів, CO - стек 45 ознак, INP пам'ять вхідного масиву, OUT - пам'ять вихідного масиву, ПП - пам'ять програм. 1. Початкова установка: - завантаження БЗ; - завантаження бібліотек термінальних програм в ПП УП; - завантаження даних (аргументу обчислювальної функції) в масиви ІNP і OUT пам'яті даних УП; - установка регістрів у початковий стан, зокрема регістр R11:=00; - перехід в стан 2. 2. Прийом завдання процесором СП 3: - якщо отримано в RKБЗ 8 завдання (ім'я функції), то: - прийом від УП 5 адрес даних в RД 11 та ознак інтерпретації (режиму інтерпретації в R 07 22, R08 23, значення інверсії 2 в R10 30 та в R11 36:=Х); - R01:= адреса кореня БЗ (тобто код регістра RКБЗ 8 присвоїти регістру R01); - запис значення регістра RД 11 в стек 12; - запис ознак інтерпретації (R11 - тип фрейму=00, режим інтерпретації - R07=0/1, R08=0/1, R09 інверсії 1=Х, R10 - інверсії 2=0/1, R12=Х) в стек 45; - перехід в стан 3; - якщо через RКОМ2 10 отримано значення істинності, то зберегти його в R 13 та перейти в стан 21; - інакше, очікування завдання поверненням до пункту 2. 3. Аналіз завдання і режиму його інтерпретації (R11+R07+R08): - R02:=[R01] (вміст R01 записати в R02); - R03:=[R01] (вміст R01 записати в R03); - читання із БЗ першого слова фрейму: R07*:=[поле ОС - ознака сліду], R11:=[поле "тип фрейму"], R09:=[поле 1]; - блок 14 управління аналізує 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 (породження ітерації), 5 UA 109324 C2 5 10 15 20 25 30 35 40 45 50 55 60 якщо R11=11& R07=1& R08=0, то перехід до п. 18 (розпізнавання ітерації із слідом), Якщо R11=11& R07=1& R08=1, то перехід до п. 20 (породження ітерації по сліду). 4. Передача термінального завдання процесору УП 5: - R01:=[перший та другий байти першого слова фрейму]; - запис RД 11 в стек 12 та ознак інтерпретації (тип фрейму - термінал з регістра R11; поточний режим інтерпретації - R07, R08; інверсія завдання із R09 - 1) в стек 45; - передача процесору УП 5 значень RД 11 та значень R01 і ознак інтерпретації через RКОМ1 9; - перехід в стан 2. 5. Розпізнавання альтернативи: - R02:=[R02]+1; - R03:=[R02]; - читання другого слова фрейму. R10:=[поле 2], R12:=[поле ОЕ], R07*:=[значення (0/1) ознаки ОС] або R08*:=[значення (0/1) ознаки породження ОП], R01:=[перший та другий байти другого слова фрейму]; - запис значень регістра RД 11 в стек 12, [R02] - в стек 17. Запис ознак інтерпретації (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:=[перший та другий байти першого слова фрейму, зчитаного з БЗ]; - RC06:=[слово ПС, зчитане за адресою RС04]; - R03:=[R02]+[RC06]; - читання з Б3 за адресою [R03] вибраного слова фрейму. R10:=[поле 2], R12:=[поле ОЕ], R01:=[перший та другий байти вибраного слова фрейму]; - запис RД 11 в стек 12. Запис ознак інтерпретації (R 11 - тип фрейму альтернативи та R 09 - 1 з першого слова фрейму; R10 - 2, R12 - ОЕ з вибраного слова фрейму та поточний режим інтерпретації - R07=0/1, R08=1) в стек 45; - перехід в стан 3. 8. Розпізнавання альтернативи із слідом: - RC06:=1; -RC04:=[R05]+1; - запис [RС06] в ПС за адресою [RC04]; - R03:=[R02]+[RC06]; - читання з БЗ за адресою [R03] другого слова фрейму. R10:=[поле 2], R12:=[поле ОЕ], R01:=[перший та другий байти вибраного слова фрейму]; - запис RД 11 в стек 12, [R05], [R02] - в стек 17. Запис ознак інтерпретації (R11 - тип фрейму альтернативи та R09 - 1 з першого слова фрейму; R10 - 2, R12-OЕ, з вибраного слова фрейму та поточний режим інтерпретації - R07=1, R08=0) в стек 45; - R05=[RC04]; - перехід в стан 3. 9. Породження альтернативи по сліду: - RC04:=[RC04]+1; - RC06:=[ПС] за адресою [RC04]; - R03:=[R02]+[RС06]; - читання з БЗ за адресою [R03] вибраного слова фрейму. R10=[поле 2], R12:=[поле OE], R01:=[перший та другий байти вибраного слова фрейму]; - запис RД 11 в стек 12. Запис ознак інтерпретації (R 11 - тип фрейму альтернативи та R 09 - 1 з першого слова фрейму; R10 - 2, R12 - ОЕ з вибраного слова фрейму та поточний режим інтерпретації - R07=1, R08=1) в стек 45; - перехід в стан 3. 10. Породження послідовності: - R07:=R07*; - аналіз R07 (біту "ознака сліду", взятого з першого слова фрейму): якщо 1, то перехід в стан 11, інакше - в стан 12. 11. Встати на слід: - RC04:=[перший та другий байти першого слова фрейму, зчитаного з БЗ]; 6 UA 109324 C2 5 10 15 20 25 30 35 40 45 50 55 60 - перехід в стан 12. 12. Породження послідовності по сліду або без сліду: - R02:=[R02]+1; - R03:=[R02]; - читання з БЗ другого слова фрейму. R10:=[поле 2], R12:=[поле ОЕ], R01:=[перший та другий байти другого слова фрейму]; - запис значення RД 11 в стек 12, [R02] в стек 17. Запис ознак інтерпретації (R 11 - тип фрейму послідовності та R09 - 1 з першого слова фрейму; R10 - 2, R12 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R07=0/1, R08=1) в стек 45; - перехід в стан 3. 13. Розпізнавання послідовності із слідом: - RС06:=1; - RC04:=[R05]; - R03:=[R02]+[RC06]; - читання з БЗ другого слова фрейму. R10:=[поле 2], R12:=[поле ОЕ], R01:=[перший та другий байти другого слова фрейму]; - запис RД 11 в стек 12, [R05], [R02] - в стек 17, [RC06] - в стек 45. Запис ознак інтерпретації (R11 - тип фрейму послідовності та R09 - 1 з першого слова фрейму; R10 - 2, R12 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R07=0/1, R08=1) в стек 45; - перехід в стан 3. 14. Завершити породження ітерації по сліду: - RC06:=[RC06]-1; - R03:=[R02]+1; - читання з БЗ другого слова фрейму. R10:=[поле 2], R01:=[перший та другий байти другого слова фрейму]; - запис [RC06] в стек 45, [R02] в стек 17. Запис ознак інтерпретації (R11 - тип фрейму ітерації та R09 - 1 з першого слова фрейму; R10 - 2 з другого слова фрейму та поточний режим інтерпретації - R07=0/1, R08=1) в стек 45; - перехід в стан 3. 15. Розпізнавання ітерації: - R03:=[R02]+1; - читання з Б3 другого слова фрейму. R10:=[поле 2], R12:=[поле ОЕ], R07*:=[значення (0/1) ознаки розпізнавання із слідом] або R08*:=[значення (0/1) ознаки породження], R01:=[перший та другий байти другого слова фрейму]; - запис значення регістра [R02] в стек 17. Запис ознак інтерпретації (R11 - тип фрейму ітерації та R09 - 1 з першого слова фрейму; R10 - 2, R12 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R07=0, R08=0) в стек 45; - R07:=R07*; R08=R08*; - перехід в стан 3. 16. Встати на слід: - RC04:=[перший та другий байти першого слова фрейму, зчитаного з БЗ]; - RC06:=[ПС] за адресою [RC04]; - якщо лічильник [RC06]≠0, то перехід в стан 14, інакше - в стан 19. 17. Породження ітерації: - R07:=R07*; - аналіз R07 (біту "ознака сліду", взятого з першого слова фрейму): якщо 1, то перехід в стан 16, інакше - в 19. 18. Розпізнавання ітерації із слідом: - RC04:=[R05]+1; - RC06:=0; - запис [RС06] в ПС за адресою RC04; - R03:=[R02]+1; - читання з БЗ другого слова фрейму. R10:=[поле 2], R01:=[перший та другий байти другого слова фрейму]; - запис [R05], [R02] в стек 17. Запис ознак інтерпретації (R11 - тип фрейму ітерації та R09 - 1 з першого слова фрейму; R10 - 2 з другого слова фрейму та поточний режим інтерпретації R07=1, R08=0) в стек 45; - R05:=[RC04];· - перехід в стан 3. 19. Завершити породження ітерації без сліду: 7 UA 109324 C2 5 10 15 20 25 30 35 40 45 50 55 60 - R13:=R09; - перехід в стан 21. 20. Породження ітерації по сліду: - RC04:=[RC04]+1; - RC06:=[ПС] за адресою [RC04]; - якщо [RC06]≠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 (розпізнавання ітерації після прапору істина), якщо 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] із стеку 17; - виштовхнути [RД] із стеку 12. - R13:=[R13]  [R09]; - перехід в стан 21. 8 UA 109324 C2 5 10 15 20 25 30 35 40 45 50 55 25. Розпізнавання альтернативи із слідом після прапору істина: - R02:=[R02] із стеку 17; - R03:=[R02]; - RC04:=[R05] із стеку 17; - ОС першого слова фрейму:=1; поля 1 та тип фрейму - відновити у байті ознак та [перший та другий байти першого слова фрейму за адресою [R03] БЗ]:=[RC04]; - виштовхнути [RД] із стеку 12; - R13:=[R13]  [R09]; - перехід в стан 21. 26. Вихід з розпізнавання альтернативи: - виштовхнути [R02] із стеку 17; - R13:=[R13]  [R09]; - перехід в стан 21. 27. Породження альтернативи по сліду після прапору істина: - Виштовхнути [RД] із стеку 12. - R13:=[R13]  [R09]; - перехід в стан 21. 28. Розпізнавання альтернативи після прапору хибність: - відновлення покажчиків INP, OUT: RД:=[RД] із стеку 12; - аналіз значення R12: якщо 1, перехід в стан 26, інакше - в стан 29. 29. Розпізнавання нового варіанту альтернативи: - R02:=[R02 із стеку 17]+1; - R03:=[R02]; - читання з БЗ чергового слова фрейму альтернативи. R10:=[поле 2], R12:=[поле ОE], R07*:=[значення (0/1) ознаки розпізнавання із слідом] або R08*:=[значення (0/1) ознаки породження], R01:=[перший та другий байти обраного слова фрейму]; - запис значення регістра [RД] в стек 12, a [R02] в стек 17. Запис ознак інтерпретації (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] із стеку 17; - RC04:=[R05] із стеку 17; - R13:=[R13]  [R09]; - перехід в стан 21. 32. Породження альтернативи по сліду після прапору хибність: - відновлення RД:=[RД із стеку 12]; - R13:=[R13]  [R09]; - перехід в стан 21. 33. Розпізнавання із слідом нового варіанту альтернативи: - RC04:=[R05 із стеку 17]+1; RC06:=[RC06 із ПС]+1; - запис [RC06] в ПС за адресою RC04; - R02:=[R02 із стеку 17]; R03:=[R02]+[RC06]; - читання з БЗ чергового слова фрейму. R10:=[поле 2], R15:=[поле ОЕ], R01:=[перший та другий байти вибраного слова фрейму]; - запис [RД] в стек 12, запис [R05], [R02] в стек 17. - запис ознак інтерпретації (R11 - тип фрейму альтернативи та R09 - 1 з першого слова фрейму, відновлених з магазину; R10 - 2, R12 - ОЕ з вибраного слова фрейму та поточний режим інтерпретації - R07=1, R08=0) в стек 45; - R05:=[RC04]; - перехід в стан 3. 34. Розпізнавання послідовності після прапору істина: - аналіз значення R12: якщо 1, то перехід в стан 24, інакше - в стан 29. 35. Розпізнавання послідовності із слідом після прапору істина: - аналіз значення R12: якщо 1, то перехід в стан 25, інакше - в стан 36. 9 UA 109324 C2 5 10 15 20 25 30 35 40 45 50 55 60 36. Продовжити розпізнавання послідовності із слідом: - RC06:=[RC06 із стеку 45]+1; - R03:=[R02]+[RC06]; - читання із БЗ чергового слова фрейму. R10:=[поле 2], R12:=[поле ОЕ], R01:=[перший та другий байти вибраного слова фрейму]; - запис [RД] в стек 12, [R05], [R02] - в стек 17, [RC06] - в ПС. Запис ознак інтерпретації (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 із стеку 17]+1; - R03:=[R02]; - читання з БЗ чергового слова фрейму послідовності. R10:=[поле 2], R12:=[поле ОЕ], R01:=[перший та другий байти другого слова фрейму]; - запис [RД] в стек 12, [R02] - в стек 17. Запис ознак інтерпретації (R11 - тип фрейму послідовності та R09 - 1 з першого слова фрейму; R10 - 2, R12 - ОЕ з другого слова фрейму та поточний режим інтерпретації - R07=0/1, R08=0 в стек 45; - перехід в стан 3. 40. Розпізнавання послідовності із слідом після прапору хибність: - відновлення покажчиків: RC04:=[R05 із стеку 17], RД:=[RД із стеку 12]; - R07:=R07*; R08:=R08*; - перехід в стан 26. 41. Породження послідовності після прапору хибність: - відновлення RД:=[RД із стеку 12]; - R07:=R07*; R08:=R08*; - виштовхнути [R02 із стеку 17]; - R13:=[R13]  [R09]; - перехід в стан 21. 42. Розпізнавання ітерації після прапору істина: - R03:=[R02 із стеку 17]+1; - читання із БЗ другого слова фрейму. R 10:=[поле 2], R12:=[поле OE], R07*:=[значення (0/1) ознаки розпізнавання із слідом] або R08*:=[значення (0/1) ознаки породження], R01:=[перший та другий байти другого слова фрейму]; - запис значення регістра [R02] в стек 17. Запис ознак інтерпретації (R11 - тип фрейму ітерації та R09 - 1 з першого слова фрейму; R10 - 2, R12 - ОE з другого слова фрейму та поточний режим інтерпретації - R07=0, R08=0) в стек 45; - R07:=R07*; R08:=R08*; - перехід в стан 3. 43. Розпізнавання ітерації із слідом після прапору істина: - RC04:=[R05 із стеку 17]+1; RC06:=[RC06 із ПС за адресою RC04]+1; - запис [RC06] в ПС за адресою RC04; - R03:=[R02 із стеку 17]+1; - читання з БЗ другого слова фрейму. R10:=[поле 2], R01:=[перший та другий байти другого слова фрейму]; - запис [R05], [R02] в стек 17. Запис ознак інтерпретації (R11 - тип фрейму ітерації та R09 - 1 з першого слова фрейму; R10 - 2 з другого слова фрейму та поточний режим інтерпретації R07=1, R08=0) в стек 45; - перехід в стан 3. 44. Породження ітерації після прапору істина: - RC06:=[RC06 із стеку 45]; - аналіз [RC06]: якщо [RC06] ≠ 0, то перехід в стан 45, інакше - в стан 46. 45. Продовжити породження ітерації після прапору істина: - RC06:=[RC06]-1; R03:=[R02 із стеку 17]+1; - читання з БЗ другого слова фрейму. R10:=[поле 2], R01:=[перший та другий байти другого слова фрейму]; 10 UA 109324 C2 5 10 15 20 - запис [RC06] в стек 45, запис [R02] в стек 17. Запис ознак інтерпретації (R11 - тип фрейму ітерації та R09 - 1 з першого слова фрейму; R10 - 2 з другого слова фрейму та поточний режим інтерпретації - R07=0/1, R08=1) в стек 45; - перехід в стан 3. 46. Завершити породження ітерації та розпізнавання ітерації після прапору хибність: - виштовхнути [R02 із стеку 17]; R13:=[R09]; - перехід в стан 21. 47. Розпізнавання ітерації із слідом після прапору хибність: - R03:=[R02 із стеку 17]; - RC04:=[R05 із стеку 17]; - ОС першого слова фрейму:=1; поля 1 та тип фрейму - відновити; - [перший та другий байти першого слова фрейму в БЗ]:=[RC 04]; - R13:=[R09]; - перехід в стан 21. 48. Породження ітерації після прапору хибність: - виштовхнути [R02 із стеку 17]; виштовхнути [RC06 із стеку 45]; - R13:=[R09]; - перехід в стан 21. Оскільки система обробки знань підтримує системний шинний інтерфейс (наприклад, АРВ), то вона може бути легко інтегрована в сучасні мікропроцесорні системи на кристалі з метою розширення їхнього набору команд. Таблиця Ім'я регістра RКБЗ RКОМ1 RКОМ2 RД R01 R02 R03 RC04 R05 RС06 R07 R08 * R07 * R08 R09 R10 R11 R12 R13 25 30 35 Розрядність, біт 16 24 24 24 16 16 16 16 16 16 1 1 1 1 1 1 3 1 1 Процесор баз знань Опис регістра Регістр кореня бази знань Перший регістр команд Другий регістр команд Регістр даних Регістр імені структури Регістр номера слова фрейму Регістр адреси бази знань Регістр-лічильник координати сліду Регістр вершини сліду Регістр-лічильник ітерації Регістр ознаки сліду Регістр ознаки породження Додатковий регістр ознаки сліду Додатковий регістр ознаки породження Регістр інверсії 1 Регістр інверсії 2 Регістр типу фрейму Регістр ознаки останнього елемента Регістр істинності ФОРМУЛА ВИНАХОДУ Процесор баз знань, що містить перший блок вводу-виводу, оперативну пам'ять, блок керування та головний комп'ютер, вхід-вихід якого підключений до перших входів-виходів першого блока вводу-виводу, чий другий вхід-вихід підключено системною шиною до входіввиходів оперативної пам'яті, який відрізняється тим, що в нього введено універсальний процесор, другий блок вводу-виводу, регістр кореня бази знань, два регістри команд, чотирнадцять регістрів даних, імені структури, номера слова фрейму, адреси бази знань, координати сліду, вершини сліду, ітерації, ознак сліду, ознак породження, першої інверсії, другої інверсії, типу фрейму, ознак останнього елемента та істинності, додатковий регістр ознак сліду, додатковий регістр ознак породження, дванадцять мультиплексорів, три стеки адрес даних, регістрів та ознак, суматор та два суматори по модулю два, при цьому входи-виходи 11 UA 109324 C2 5 10 15 20 25 30 35 універсального процесора разом із першими входами-виходами другого блока вводу-виводу з'єднані із системною шиною, другий вхід-вихід другого блока вводу-виводу підключено до першого входу-виходу регістра даних, другий вхід-вихід якого підключено до входу-виходу стеку адрес даних, перший вихід другого блока вводу-виводу підключено до входу регістра кореня бази знань, чий вихід з'єднано з першими входами третього та четвертого мультиплексорів та із входом регістра імені структури, вихід якого підключено до перших входів другого та п'ятого мультиплексорів та до другого входу першого мультиплексора, чий перший вхід разом із другим входом другого мультиплексора з'єднаний із виходом суматора, третій вхід з'єднаний із першим виходом стеку регістрів, а вихід підключено до входу регістра номера слова фрейму, вихід якого підключено до першого входу стеку регістрів та до першого входу суматора, чий другий вхід разом із першими входами блока керування, стеку ознак та четвертим входом п'ятого мультиплексора підключений до виходу регістра ітерації, вихід другого мультиплексора підключено до входу регістра адреси бази знань, вихід якого з'єднаний із другим входом п'ятого мультиплексора, чий третій вхід разом із входом регістра вершини сліду з'єднаний із виходом регістра координати сліду, вхід якого підключений до виходу третього мультиплексора, чий другий вхід з'єднаний із другим виходом стеку регістрів, а третій вхід разом із другим входом стеку регістрів підключений до виходу регістра вершини сліду, вихід першого регістра команд підключено до входу другого блока вводу-виводу, чий другий вихід підключено до входу другого регістра команд, вихід якого підключено до третього входу блока керування та до перших входів шостого, сьомого, восьмого, дев'ятого, десятого, одинадцятого мультиплексорів та до входів додаткових регістрів ознак сліду та породження, чиї виходи підключені до других входів шостого та сьомого мультиплексорів відповідно, треті входи яких разом із другими входами восьмого, дев'ятого, десятого та одинадцятого мультиплексорів підключені до другого виходу стеку ознак, чий перший вихід підключений до другого входу четвертого мультиплексора, вихід якого з'єднаний із входом регістра ітерації, виходи шостого, сьомого, восьмого, дев'ятого, десятого та одинадцятого мультиплексорів з'єднані із входами регістрів ознак сліду, ознак породження, першої інверсії, другої інверсії, типу фрейму та ознак останнього елемента відповідно, перші виходи регістрів ознак сліду, ознак породження, типу фрейму та ознак останнього елемента підключено до другого входу першого регістра команд та до четвертого входу блока керування, чий вихід підключено до першого входу першого регістра команд, третій вхід якого підключений до виходу п'ятого мультиплексора, другі виходи регістрів ознак сліду, ознак породження, першої інверсії, другої інверсії, типу фрейму та ознак останнього елемента підключено до другого входу стеку ознак, другий вихід регістра першої інверсії підключено до першого входу першого суматора по модулю два та до першого входу дванадцятого мультиплексора, перший вихід регістра другої інверсії підключено до першого входу другого суматора по модулю два, чий другий вхід разом із другим входом першого суматора по модулю два та другим входом блока керування підключений до виходу регістра істинності, вхід якого з'єднаний із виходом дванадцятого мультиплексора, чиї другий і третій входи підключені до виходів першого та другого суматора по модулю два відповідно. 40 12 UA 109324 C2 13 UA 109324 C2 14 UA 109324 C2 15 UA 109324 C2 Комп’ютерна верстка А. Крижанівський Державна служба інтелектуальної власності України, вул. Василя Липківського, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут інтелектуальної власності”, вул. Глазунова, 1, м. Київ – 42, 01601 16