Комбінаторно-логічний процесор

Комбінаторно-логічний процесор, який має К груп інформаційних входів по п розрядів у кожній, виходи результату, лічильник, блок пам'яті, тригер, перший і другий елементи НІ, вихід ознаки відсутності рішення, вихід ознаки наявності рішення, керуючий вхід, перший елемент І, причому вихід тригера з'єднаний з виходом ознаки наявності рішення та через перший елемент НІ - з першим входом першого елемента І, керуючий вхід з'єднаний з другим входом першого елемента І та з керуючим входом блока пам'яті, вихід першого елемента І з'єднаний з рахунковим входом лічильника, виходи якого з'єднані з адресними входами блока пам'яті, К блоків обчислення значення співмножника, другий елемент І, виходи блока пам'яті з'єднані з першими групами входів блоків обчислення значення співмножника та з виходами результату, і-та група інформаційних входів з'єднана з другою групою входів і-го блока обчислення значення співмножника, виходи блоків обчислення значення співмножника з'єднані з ВІДПОВІДНИМИ входами другого елемента І, вихід якого з'єднаний з одиничним входом тригера, який відрізняється тим, що додатково містить шину значення початкової адреси, вхід запису, схему порівняння, шину значення кінцевої адреси, причому входи шини значення початкової адреси з'єднані з входами початкового стану лічильника, вхід запису з'єднаний з входом запису стану лічильника, входи шини значення кінцевої адреси з'єднані з першою групою входів схеми порівняння, виходи лічильника з'єднані з другою групою входів схеми порівняння, вихід схеми порівняння з'єднаний з виходом ознаки відсутності рішення та через другий елемент НІ з'єднаний з третім входом першого елемента ю Винахід відноситься до обчислювальної техніки і призначений для рішення комбінаторнологічних задач, які виникають під час проектування дискретних пристроїв, наприклад, при розробці контрольних та діагностичних тестів Відомий пристрій для логічної обробки інформації, що містить ВХІДНІ шини коефіцієнтів рівняння, вхідну шину правої частини рівняння, шину результату, двійковий лічильник, групи з першої по n-ну елементів І, операційний пристрій, блок порівняння, тригер, два елементи НІ, два індикатори, генератор імпульсів, два елементи І, суматори по модулю 2, виходи операційного пристрою, елементи РІВНОЗНАЧНІСТЬ (ас СРСР N 1262519, кл G06F 15/20, 1985р) Недоліком відомого пристрою є низька швидкодія Відомий пристрій для рішення логічних рівнянь (ас СРСР N 1411768, кл G06F 15/20, опубл 23 07 88р), що містить лічильник, елемент І, пер ший і другий елементи НІ, тригер, операційний блок, блок порівняння, п груп по m елементів І кожна, де п - число змінних рівняння, причому j-й вхід 0 = 1, ,т) і-го (і = 1, ,п) коефіцієнта рівняння пристроїв підключений до першого входу j-ro елемента І і-й групи, вихід якого підключений до j-ro інформаційного входу і-й групи операційного блоку, j-й вихід якого підключений до j-ro входу першої групи блоку порівняння, j-й вхід другої групи блоку порівняння підключений до j-ro входу значення правої частини рівняння пристрою, тактовий вхід пристрою підключений до першого входу елемента І, вихід якого підключений до рахункового входу лічильника, перший інформаційний вихід якого підключений до виходу ознаки відсутності рішення пристрою і до входу першого елемента НІ, вихід якого підключений до другого входу елемента І, вихід блоку порівняння підключений до рахункового входу тригера, вихід якого підключений до виходу ознаки наявності рішення пристрою і до вхо (О о ю ду другого елемента НІ, вихід якого підключений до третього входу елемента І, пристрій містить блок пам'яті, причому з другого по (п + 1)-й інформаційні виходи лічильника підключені ВІДПОВІДНО до адресних входів з першого по n-й блоку пам'яті, вхід читання якого підключений до тактового входу пристрою, і-й вихід блоку пам'яті підключений до іго виходу результату рішення пристрою і до других входів m елементів і-й групи Недоліком відомого пристрою є низька швидкодія Найбільш близьким по технічній суті і результату, що досягається, є пристрій для розв'язання комбінаторно-логічних задач (Патент України № 38565, м кл G06F 15/20, опубл Бюл № 4, 2001 р), що містить К груп інформаційних входів по п розрядів у кожній, виходи результату, лічильник, блок пам'яті, тригер, перший і другий елементи НІ, вихід ознаки відсутності рішення, вихід ознаки наявності рішення, керуючий вхід, перший елемент І, причому вихід тригера з'єднаний з виходом ознаки наявності рішення, та через перший елемент НІ з першим входом першого елемента І, керуючий вхід з'єднаний з другим входом першого елемента І та з керуючим входом блока пам'яті, вихід першого елемента І з'єднаний з рахунковим входом лічильника, виходи якого з'єднані з адресними входами блока пам'яті, К блоків обчислення значення співмножника, другий елемент І, виходи блока пам'яті з'єднані з першими групами входів блоків обчислення значення співмножника, і-та група інформаційних входів з'єднана з другою групою входів і-го блоку обчислення значення співмножника, виходи блоків обчислення значення співмножника з'єднані з ВІДПОВІДНИМИ входами другого елементу І, вихід якого з'єднаний з одиничним входом тригера Недоліком відомого пристрою є низька швидкодія В основу винаходу поставлено задачу вдосконалити комбінаторно-логічний процесор шляхом введення нового складу елементів, та нової організації взаємозв'язків між ними забезпечити більшу швидкодію при розв'язанні комбінаторно-логічних задач Поставлене завдання вирішується тим, що комбінаторно-логічний процесор містить К груп інформаційних входів по п розрядів у кожній, виходи результату, лічильник, блок пам'яті, тригер, перший і другий елементи НІ, вихід ознаки відсутності рішення, вихід ознаки наявності рішення, керуючий вхід, перший елемент І, причому вихід тригера з'єднаний з виходом ознаки наявності рішення, та через перший елемент НІ з першим входом першого елемента І, керуючий вхід з'єднаний з другим входом першого елемента І та з керуючим входом блока пам'яті, вихід першого елемента І з'єднаний з рахунковим входом лічильника, виходи якого з'єднані з адресними входами блока пам'яті, К блоків обчислення значення співмножника, другий елемент І, виходи блока пам'яті з'єднані з першими групами входів блоків обчислення значення співмножника та з виходами результату, і-та група інформаційних входів з'єднана з другою групою входів і-го блоку обчислення значення співмножника, виходи блоків 54065 обчислення значення співмножника з'єднані з ВІДПОВІДНИМИ входами другого елементу І, вихід якого з'єднаний з одиничним входом тригера, згідно з винаходом має шину значення початкової адреси, вхід запису, схему порівняння, шину значення кінцевої адреси, причому входи шини значення початкової адреси з'єднані з входами початкового стану лічильника, вхід запису з'єднаний з входом запису стану лічильника, входи шини значення кінцевої адреси з'єднані з першою групою входів схеми порівняння, виходи лічильника з'єднані з другою групою входів схеми порівняння, виход схеми порівняння з'єднаний з виходом ознаки відсутності рішення, та через другий елемент НІ з'єднаний з третім входом першого елемента І Заявлений пристрій має новий склад елементів, та нову організацію взаємозв'язків між ними, тобто містить нову сукупність ознак, які забезпечують нові технічні властивості винаходу Технічний результат, як наслідок цих властивостей - підвищення швидкодії На фіг 1 представлена функціональна схема комбінаторно-логічного процесора, на фіг 2 представлена функціональна схема блоку обчислення значення співмножника Комбінаторно-логічний процесор містить К груп інформаційних входів по п розрядів у кожній 1, виходи результату 2, лічильник З, К блоків, обчислення значення співмножника 4, другий елемент І 5, блок пам'яті 6, тригер 7, перший і другий елементи НІ 8, 9, вихід ознаки відсутності рішення 10, вихід ознаки наявності рішення 11, керуючий вхід 12, перший елемент І 13, шину значення початкової адреси 14, вхід запису 15, схему порівняння 16, шину значення кінцевої адреси 17, блок обчислення значення співмножника 4 містить елемент АБО 19 та п елементів І 18 Вихід тригера 7 з'єднаний з виходом ознаки наявності рішення 11, та через перший елемент НІ 8 з першим входом першого елемента І 13, керуючий вхід 12 з'єднаний з другим входом першого елемента І 13 та з керуючим входом блока пам'яті 6, вихід першого елемента І 13 з'єднаний з рахунковим входом лічильника 3, виходи якого з'єднані з адресними входами блока пам'яті 6, виходи блока пам'яті 6 з'єднані з першими групами входів блоків обчислення значення співмножника 4 та з виходами результату 2, і-та група інформаційних входів 11 з'єднана з другою групою входів і-го блоку обчислення значення співмножника 4і, виходи блоків обчислення значення співмножника 4 з'єднані з ВІДПОВІДНИМИ входами другого елементу І 5, вихід якого з'єднаний з одиничним входом тригера 7, входи шини значення початкової адреси 14 з'єднані з входами початкового стану лічильника З, вхід запису 15 з'єднаний з входом запису стану лічильника 3, входи шини значення кінцевої адреси 17 з'єднані з першою групою входів схеми порівняння 16, виходи лічильника 3 з'єднані з другою групою входів схеми порівняння 16, виход схеми порівняння 16 з'єднаний з виходом ознаки відсутності рішення 10, та через другий елемент НІ 9 з'єднаний з третім входом першого елемента І З Всі елементи, що входять до складу пристрою є відомими елементами автоматики і обчислювальної техніки і можуть бути виконані по будь-якій 54065 ВІДОМІЙ схемі Працює комбінаторно-логічний процесор таким чином Процесор призначено для рішення логічних рівнянь вигляду Пі&П 2 & & П к = 1 , де П, = Ац&Хі v A l 2 & X 2 v vAm&Xn, A,j e {0,1}, n - КІЛЬКІСТЬ змінних, k - КІЛЬКІСТЬ СПІВМНОЖНИКІВ На інформаційні входи 1-і - 1к подаються значення коефіцієнтів А ВІДПОВІДНО для кожного співмножника, причому А,, = 1 , якщо у диз'юнктивну форму і-го співмножника входить змінна X, (інакше -0) Пошук рішення полягає у послідовному формуванні двійкових кодів та визначення значень СПІВМНОЖНИКІВ, при цьому знаходиться рішення мінімальної потужності У початковому стані триггер 7 знаходиться в стані " 1 " На шину значення початкової адреси 14 подається двійковий код адреси, починаючи з якої відбувається пошук рішення На вхід запису 15 подається імпульс і значення початкової адреси записується у двійковий лічильник 3 На входи шини значення кінцевої адреси 17 подається двійковий код адреси, до якого проводиться пошук У залежності від двійкового коду, що поступає з виходу лічильника 3, з виходу блоку 6 пам'яті видаються сигнали " 1 " в ВІДПОВІДНИХ ПОЗИЦІЯХ, при цьому номери позицій " 1 " , що формуються для кожного стану лічильника 3, є лексикографічне впорядкованими, тобто спочатку записані коди для сполучень по одному елементу, потім по два, по троє і т д Наприклад, для п = 3 ці коди мають вигляд 0 0 1 , 0 1 0 , 1 0 0 , 0 1 1 , 1 0 1 , 1 1 0 , 1 1 1 На виході схеми порівняння 16 сигнал "0", на виході елемента НІ 9 " 1 " , тому після подачі на керуючий вхід 12 тактових імпульсів через елемент І 13 імпульси поступають на рахунковий вхід двійкового лічильника 3, змінюючи його стан і відпові дне двійкове слово на виходах блоку пам'яті 6 Значення і-го вихідного розряду блоку 6 пам'яті відповідає значенню х Блоки обчислення значення співмножника 4 обчислюють значення СПІВМНОЖНИКІВ, а елемент 5 І обчислює їх кон'юнкцію У процесі рішення можуть бути два випадки Рішення рівняння існує При цьому на виході 11 з'являється ознака наявності рішення, і значення розрядів на виходах 2 результату відповідає значенням X Рішення немає У цьому випадку після перебору всіх варіантів двійковий лічильник 3 на (п + 1)-м виході формує сигнал " 1 " , при цьому на виході 10 з'являється ознака відсутності рішення, через елемент НІ 9 на вхід елемента І 13 поступає сигнал "0", що закриває надходження імпульсів на рахунковий вхід лічильника З Таким чином процесор розв'язує ЛОГІЧНІ рівняння На відміну від прототипу, пошук починається з заданої адреси, значення якої визначається в залежності від особливостей рівняння Наприклад, для діагностичних тестів відомо, що довжина тесту не менша ніж L = Іод 2 К, де К - КІЛЬКІСТЬ станів об'єкту Значення L відповідає КІЛЬКОСТІ ОДИНИЦЬ у двійковому коді на виходах блока пам'яті 6 Тому при пошуку мінімального діагностичного тесту не має сенсу розглядати варіанти, для яких довжина тесту менша ніж L, а відповідне значення двійкового коду подається на шину початкової адреси 14 Якщо при розв'язку комбінаторно-логічних задач цікавить наявність та вид рішення заданої потужності, то на входи шини значення кінцевої адреси подається двійковий код адреси, до якого потрібно виконувати пошук Таким чином, заявлений пристрій вирішує задачу у менший термін, тобто має більшу швидкодію s — п 18, _ « г li • ! ) I 11 1 9 Фіг.2 ФІГ.1 ТОВ "Міжнародний науковий комітет" вул Артема, 77, м Київ, 04050, Україна (044)236-47-24 4 • 18n t