Комбінаторний процесор

Винахід відноситься до обчислювальної техніки і призначений для рішення комбінаторно - логічних задач, які виникають під час проектування дискретних пристроїв, наприклад при розробці контрольних та діагностичних тестів. Відомий пристрій для логічної обробки інформації, що містить вхідні шини коефіцієнтів рівняння, вхідну шин у правої частини рівняння, шина результату, двійковий лічильник, групи з першої по n-нну елементів І, операційний пристрій, блок порівняння, тригер, два елементи НІ, два індикатори, генератор імпульсів, два елементи І, суматори по модулю 2, виходи операційного пристрою, елементи рівнозначність (а.с. СРСР №1262519, кл. G06F15/20, 1985р.) Недоліком відомого пристрою є обмежені функціональні можливості. Відомий пристрій для рішення логічних рівнянь (а. с. СРСР №1411768, кл. G06F15/20, опубл. 23.07.88р.), що містить лічильник, елемент І, перший і другий елементи НІ, тригер, операційний блок, блок порівняння, n груп по m елементів І, кожна, де n - число змінних рівняння, причому j-й вхід (j=1, ...m) і-го (і=1, ...n) коефіцієнта рівняння пристроїв підключений до першого входу j-го елемента І і-й групи, вихід якого підключений до j-y інформаційному входу і-й групи операційного блоку, j-й вихід якого підключений до j-го входу першої групи блоку порівняння, j-й вхід другої гр упи блоку порівняння підключений до j-му входу значення правої частини рівняння пристрою, тактовий вхід пристрою підключений до першого входу елемента І, ви хід якого підключений до рахунковому входу лічильника, перший інформаційний вихід якого підключений до виходу ознаки відсутності рішення пристрою і до входу першого елемента НІ, вихід якого підключений до другого входу елемента І, вихід блоку порівняння підключений до рахункового входу тригера, вихід якого підключений до виходу ознаки наявності рішення пристрою і до входу другого елемента НІ, вихід якого підключений до третього входу елемента І, пристрій містить блок пам'яті, причому з другого по (n+1)-й інформаційні виходи лічильника підключені відповідно до адресних входів з першого по n-й блок пам'яті, вхід читання якого підключений до тактового входу пристрою, і-й вихід блоку пам'яті підключений до і-го виходу результату рішення пристрою і до других входів m елементів і-ї гр упи. Недоліком відомого пристрою є обмежені функціональні можливості. Найбільш близьким по технічній суті і результату, що досягається є пристрій для розв'язання комбінаторнологічних задач (Патент України №38565, G06F17/276 опуб. 2001р., бюл. №4), який має К груп інформаційних входів по n розрядів у кожній, виходи результату, перший лічильник, перший блок пам'яті, елемент НІ, інформаційний вихід, керуючий вхід, два елемента І, К блоків обчислення значення співмножника, причому керуючий вхід з'єднаний з першим входом першого елемента І та з керуючим входом першого блока пам'яті, вихід першого елемента І з'єднаний з рахунковим входом першого лічильника, перші п виходів якого з'єднані з адресними входами першого блока пам'яті, (n+1)-ий вихід з'єднаний з інформаційним виходом, та через елемент НІ з'єднаний з другим входом першого елемента І, виходи першого блока пам'яті з'єднані з першими групами входів блоків обчислення значення співмножника та з виходами результату, і-та гр упа інформаційних входів з'єднана з другою гр упою входів і-го блоку обчислення значення співмножника, виходи блоків обчислення значення співмножника з'єднані з відповідними входами другого елементу І. Недоліком відомого пристрою є обмежені функціональні можливості. В основу вина ходу поставлено задачу вдосконалення комбінаторного процесора шляхом введення нового складу елементів, та нової організації взаємозв'язків між ними, забезпечити ширші функціональні можливості при використанні винаходу, а саме - спроможність знаходити усі рішення логічних рівнянь. Поставлене завдання вирішується тим, що комбінаторний процесор який має К груп інформаційних входів по n розрядів у кожній, виходи результату, перший лічильник, перший блок пам'яті, елемент НІ, інформаційний вихід, керуючий вхід, два елемента І, К блоків обчислення значення співмножника, причому керуючий вхід з'єднаний з першим входом першого елемента І та з керуючим входом першого блока пам'яті, вихід першого елемента І з'єднаний з рахунковим входом першого лічильника, перші п виходів якого з'єднані з адресними входами першого блока пам'яті, (n+1)-ий вихід з'єднаний з інформаційним виходом, та через елемент НІ з'єднаний з другим входом першого елемента І, ви ходи першого блока пам'яті з'єднані з першими групами входів блоків обчислення значення співмножника та з виходами результату, і-та гр упа інформаційних входів з'єднана з другою групою входів і-го блоку обчислення значення співмножника, виходи блоків обчислення значення співмножника з'єднані з відповідними входами другого елементу І, згідно з винаходом містить другий лічильник, другий блок пам'яті, формувач імпульсу, причому вихід другого елемента І з'єднаний з рахунковим входом другого лічильника та входом формувача імпульсу, ви хід формувача імпульсу з'єднаний з входом запису другого блоку пам'яті, виходи другого лічильника з'єднані з адресними входами другого блоку пам'яті, виходи результату з'єднані з інформаційними входами другого блоку пам'яті. На фігурі представлена функціональна схема комбінаторного процесора. Комбінаторний процесор містить К груп інформаційних входів по n розрядів у кожній 1, виходи результату 2, перший лічильник 3, К блоків, обчислення значення співмножника 4, другий елемент І 5, перший блок пам'яті 6, другий блок пам'я ті 7, формувач імпульсу 8, елемент НІ 9, інформаційний вихід 10, другий лічильник 11, керуючий вхід 12, причому керуючий вхід 12 з'єднаний з першим входом першого елемента І 13 та з керуючим входом першого блока пам'яті 6, вихід першого елемента І 13 з'єднаний з рахунковим входом першого лічильника 3, перші n виходів якого з'єднані з адресними входами першого блока пам'яті 6, (n+1)-ий вихід з'єднаний з інформаційним виходом 10 та через елемент НІ 9 з'єднаний з другим входом першого елемента І 13, виходи першого блока пам'яті 6 з'єднані з першими групами входів блоків обчислення значення співмножника 4 та з виходами результату 2, і-та група інформаційних входів 1і з'єднана з другою групою входів і-го блоку обчислення значення співмножника 4і, виходи блоків обчислення значення співмножника 4 з'єднані з відповідними входами другого елементу І 5, ви хід другого елемента І 5 з'єднаний з рахунковим входом другого лічильника 11 та входом формувача імпульсу 8, вихід формувача імпульсу 8 з'єднаний з входом запису другого блоку пам'яті 7, виходи другого лічильника 11 з'єднані з адресними входами другого блоку пам'яті 7, виходи результату 2 з'єднані з інформаційними входами другого блоку пам'яті 7. Працює комбінаторно-логічний процесор таким чином. Пристрій призначено для рішення логічних рівнянь вигляду П1 & П2 & ...& Пk=1, 0 де Пі=Ai1&X1 v Ai2&X2 v...vAin&Xn, AijÎ { ,1} , n - кількість змінних, k - кількість співмножників. На інформаційні входи 11 - 1k подаються значення коефіцієнтів А відповідно для кожного співмножника, причому Aij = 1, якщо у диз'юнктивну форму і-го співмножника входить змінна Xj (інакше - 0). Пошук рішення полягає у послідовному формуванні двійкових кодів та визначення значень співмножників, при цьому знаходиться рішення мінімальної потужності. У початковому стані двійкові лічильники 3 та 11 знаходяться у стані 0...0. У залежності від двійкового коду, що поступає з ви ходу лічильника 3, з виходу блоку 6 пам'яті видаються сигнали "1" в відповідних позиціях, при цьому номери позицій "1", що формуються для кожного стану лічильника 3, є лексикографічно впорядкованими, тобто спочатку записані коди для сполучень по одному елементу, потім по два, по троє і т.д. На (n+1)-му виході двійкового лічильника - сигнал "0", на виході елемента НІ 9 "1", тому після подачі на керуючий вхід 12 тактових імпульсів через елемент І 13 імпульси поступають на рахунковий вхід двійкового лічильника 3, змінюючи його стан і відповідне двійкове слово на виходах блоку пам'яті 6. Значення і-го вихідного розряду блоку 6 пам'яті відповідає значенню х. Блоки обчислення значення співмножника 4 обчислюють значення співмножників. Елемент 5 І обчислює їх кон'юнкцію. Якщо у процесі роботи знайдено рішення, про що свідчить одиничний сигнал на виході елемента І 5, який поступає на рахунковий вхід другого лічильника 11 і збільшує його стан на одиницю. Формувач імпульсів 8 формує імпульс запису, який поступає на вхід запису другого лічильника 11 і рішення записується. Таким чином, у другому блоці пам'яті 11 після закінчення роботи (про це свідчить одиничний сигнал на виході 10) сформовані усі рішення логічного рівняння, а не одно, як було у прототипі.