Устройство для решения булевых дифференциальных уравнений

 

Изобретение относится к цифровой вычислительной технике и может быть использовано в качестве аппаратной поддержки вычислений в системах автоматизированного проектирования цифровых автоматов, при анализе и диагностике комбинационных схем, в системах логического управления роботами-манипуляторами, гибкими автоматизированными производствами. Цель изобретения - расширение функциональных возможностей за счет решения булевых дифференциальных уравнений. Поставленная цель достигается тем, что устройство содержит 2<SP POS="POST">N</SP> блоков 1 управления, где N - число булевых переменных, 2<SP POS="POST">N</SP> блоков 2 дешифрации, 2<SP POS="POST">N</SP> вычислительных блоков 3 и коммутатор 4. Исходное булевое дифференциальное уравнение, представляемое как система булевых уравнений в форме Жегалкина, решается посредством быстрого дискретного преобразования Фурье в конъюнктивном базисе. 4 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (я)з G 06 F 15/332

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Twm

Тагя

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4719275/24 (22) 14.07.89 (46) 07.07.91. Бюл. М 25 (71) Минский радиотехнический институт (72) В;Г. Левашенко, Г,А, Кухарев, B.Ï. Шмерко и С.Н. Янушкевич (53) 681.325(088.8) (56) Авторское свидетельство СССР

N- 1269146, кл. G 06 F 15/31, 1985, Авторское свидетельство СССР

М 1001107, кл. G 06 F 15/332, 1982, (54) УСТРОЙСТВО ДЛЯ РЕШЕНИЯ БУЛЕВЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ (57) Изобретение относится к цифровой вычислительной технике и может быть использовано в качестве аппаратной поддержки вычислений в системах автоматизированно„„212 1 66 1791A1

ro проектирования цифровых автоматов, при анализе и диагностике комбинационных схем. в системах логического управления роботами-манипуляторами, - гибкими автоматизированными производствами.

Цель изобретения — расширение функциональных возможностей за счет решения булевых дифференциальных уравнений.

Поставленная цель достигается тем, что устройство содержит 2" блоков 1 управления, где и — число булевых переменных, 2" блоков 2 дешифрации, 2" вычислительных блоков 3 и коммутатор 4. Исходное булевое дифференциальное уравнение, представляемое как система булевых уравнений в форме Жегалкина, решается посредством быстрого дискретного преобразования

Фурье в конъюнктивном базисе. 4 ил.

1661791

Изобретение относится к цифровой вычислительной технике и может быть использовано в качестве аппаратной поддержки вычислений в системах автоматизированного проектирования цифровых автоматов, при анализе и диагностике комбинационных схем, в системах логического управления роботами-манипуляторами, гибкими автоматизированными производствами.

Цель изобретения — расширение функциональных возможностей за счет решения булевых дифференциальных уравнений, Устройство (фиг. 1) содеожит 2п блоков

1 управления, 2п блоков 2 дешифрации, 2," вычислительных блоков 3 и коммутатор 4.

Каждый блок 1 управления (фиг. 2) содержит первый 5 и второй 6 триггеры и элемент И 7, Каждый блок 2 дешифрации (фиг. 3) содержит дешифратор 8, регистры 9, элементы И

10 первой группы, элементы И 11 второй группы и элемент ИЛИ 12. Каждый вычислительный блок 3 (фиг, 4) содержит сумматор

13 по модулю два, элементы И 14, сдвигающие регистры 15, первый 16 и второй 17 элементы ИЛИ и элемент 18 задержки.

Устройство имеет следующий алгоритм работы.

На первом этапе выполняют усеченное дискретное преобразование Фурье в коньюнктивном базисе согласно матричному соотношению;

Х = Кгг F+ (mod2), () где F г" — матрица дифференцирования размерности 2пх2", формируемая по cootношению

"Х) ®;Iгп, i=1,п, где!г " и !гп единичные матрицы размерностей 2 х2 и 2" х2" соответственно; (Ж вЂ” символ кронекеровского произведения матриц, причем при умножении (() матрицы F г" и вектора Х используются операции коньюнкции и суммирования по модулю два. п гп и

Матрица К гг размерности 2 х 2 формируется из матрицы конъюнктивного преп г" г" образования Кгг размерности 2 х 2 путем выделения столбцов с номерами

2 - (t=0,2"-1) и удаления остальных:

Кг = К г - t +Kg; !

12 Кг= 1 1

На втором этапе над векторами Ф) системы Х выполняется операция поэт,ементной дизъюнкции, В итоге получают вектор решения К(как результат объединения ре-, 5 шений отдельных уравнений системы).

На третьем этапе алгоритма определяют нулевые элементы вектора решений Ги соответствующие им наборы переменных

П

Х(),Х ),...,Х, являющиеся коэффициентами векторов значений

Х=(х(0) X(t) Х г 1) Т искомых булевых функций t(X).

Функционирование i-ro блока 1 управления (l=1,2") рассмотрим на примере блока

1 ) управления, В момент времени to на счетный вход триггера 5 поступает тактовый импульс и на выходе триггера 5 формируется уровень логического "0". Он передается с выхода триггера 5 на первый вход элемента И 7 и на третий выход блока ". < В момент времени t0 на вход установки в "1" триггера 6 поступает высокий логический уровень сигнала и на выходе триггера 6 формируется уровень логической "1", который передается на второй выход блока 1t. Сигнал высокого уровня подается на второй вход элемента

И 7, с выхода которого низкий логический уровень сигнала передается на четвертый выход блока 1>.

В момент времени t> на счетный вход триггера 5 поступает тактовый импульс, который устанавливает триггер 5 в состояние логической "1". С выхода триггера 5 высокий логический уровень сигнала поступает на первый вход элемента И 7 и на третий выход блока 1>. В момент времени tt на второй вход элемента И 7 поступает высокий логический уровень сигнала, с выхода элемента

И 7 этот сигнал передается на вход установки в "0" триггера 6 и на четвертый выход блока 1 <. На выходе триггера 6 устанавливается низкий логический уровень сигнала, который передается на второй выход блока 1i и (он сохраняется на нем по 2г -й такт включительно), На третьем такте (момент времени тз) в

50 схеме происходят те же переключения, что и на первом такте, эа исключением того, что на вход установки в "1" триггера 6 сигнал не поступает. На четвертом, пятом и т.д. по г

2 -й такт включительно блок 11 функционирует так же, как на втором и третьем, однако при этом на второй вход элемента И 7 поступает низкий логический уровень сигнала.

Функционирование блока 1г отличается лишь тем, что на его тактовый вход поступа1661791

6 ют сигналы, которые формируются на первом выходе блока 11.

Процесс функционирования блока 2 осуществляется следующим образом; на тактах с первого по 2"-й выполняется загрузка элесР 11 б(1 11 б(4 ) 1-го столбца матрицы преобразования Р2П так что на К-м (К=1,2") такте загружается элемент

d " . Этот элемент передается на выход на соответствующих тактах работы устройства (элемент d на тактах с (2 +1)-го по2 -й), Процесс завершается на 2 -мтакК- z" те.

На первом такте на входы с первого по

2"-й дешифратора 8 поступает код 0,0,...,0.

В результате на первом выходе дешифратора 8 формируется высокий логический уровень сигнала, который передается на первый вход элемента И 101, на второй вход которого поступает тактовый импульс. В результате импульс записи с выхода элемента

И 10> передается на вход записи считывания регистра 191, на информационный вход (О, -1) которого поступает элемент di i-го столбца матрицы преобразования F2,", На этом такте на выход блока через элемент ИЛИ 12 с выхода элемента И 11к (на его втором входе — низкий логический уровень сигнала) передается низкий логический уровень сигнала.

На втором такте (момент времени t>) на входы с первого по 2"-й дешифратора 8 поступает код 1,0,...,0. В результате на втором выходе дешифратора 8 формируется высокий логический уровень сигнала, который передается на первый вход элемента И 102.

При этом на его второй вход поступает тактовый импульс, он передается на вход записи регистра 92, на информационный вход котооого поступает следующий элемент

d " i-r0 столбца матрицы и реобразования

FP. На этом такте на выход блока через элемент И 111 (на его втором входе — высокий логический уровень сигнала) и элемент

ИЛИ 12 передается содержимое регистра

91-d() (на остальных входах элемента

ИЛИ 12 — сигналы логического "0").

Наконец, на 2"-м такте работы устройства 2"-й элемент б() i-го столбца матрицы преобразования F 2" записывается в 2"-й регистр 9. При этом элементы с выходов регистров 9к(К=1,2 ) передаются на выход блока со следующей последовательности: на третьем и четвертом тактах

-d, на пятом- восьмом ит,д., так что К-й элемент d() i-го столбца матрицы преобразования F < передается на выход блока 2i с (2 +1)-го такта по 2 -й такт включительно.

Функционирование вычислительного блока 3i рассмотрим на примере вычислительного блока 31.

На первом такте (момент времени to) на вторые входы элементов И 14к поступает код 0,0,...,0. В результате с выходов элементов И 14к низкий логический уровень сигнала передается на входы элемента ИЛИ 17. С выхода элемента ИЛИ 17 низкий логический уровень сигнала передается на второй вход сумматора 13 по модулю два, на первый

15 вход которого поступает си(-нал логического

"0". В этот момент времени to no сигналу сдвига в регистрах 15к выполняется сдвиг содержимого на один разряд влево (в сторону старших разрядов), По сигналу, поступающему на вход записи/считывания регистров 15к через 0,5 такта осуществляется запись этого содержимого в регистры 15к (в первый регистр записывается результат суммирования по модулю два — логический

"0", который поступаеттакже на второй вход элемента ИЛИ 16). В результате на выходе элемента ИЛИ 16 формируется результат (логический "0"), который передается на выход блока 31.

На втором такте (момент времени t<) на вторые входы элементов И 14к поступает код 1,0,...,0. В Результате на выход элемента

И 14t, а затем на первый вход элемента ИЛИ

17 передается содержимое регистра 151, С выхода элемента ИЛИ 17 содержимое регистра 15t (логический "0") передается на второй вход сумматора 13 по модулю два. На его первый вход поступает элемент б первого столбца матрицы преобразования

F 2>. В этот момент времени t> по сигналу сдвига в регистрах 15к выполняется сдвиг содержимого на один разряд влево (в сторону старших разрядов), По сигналу, по45 ступающему на вход записи/считывания

1 регистра 15к через 0,5 такта с выхода элемента 18 задержки, осуществляется запись этого содержимого в регистры 15к, При этом в первый регистр записывается

Рез льтат суммирования по модул О два (б ? О), Кроме того, он поступает также на второй вход элемента ИЛИ 16. В результате на выходе элемента ИЛИ 16 формируется результат б, который передается на выход блока 31, 2"

На третьем и последующих (по 2 -й) тактах блок 3> функционирует, как и на втором, При этом элементе d (К=0.2") первого столбца матрицы преобразования F g"

1661791 поступают на второй информационный вход блока 3> в такой последовательности; на (1,0) третьем и четвертом тактах — элемент 4 на пятом — восьмом — элемент d и т.д., так р,о) что К-й элемент d(первого столбца (к->,o) матрицы преобразования F " поступает с (2 +1)-ro такта по 2 -й такты включительк но.

Функционирование блока 3z отличается от функционирования блока 3> тем, что на его первый информационный вход сигналы поступают с выхода блока 3>, а на второй информационный вход блока 3 поступают элементы d второго столбца матрицы преобразования FP. На выход блока 3i передаются результаты, формируемые на выходе его элемента ИЛИ 16.

Формула изобретения

Устройство для решения булевых дифференциальных уравнений, содержащее с первого по и-й вычислительные блоки, где

n — число булевых переменных, с первого по и-й блоки управления и с первого no n-й блоки дешифрации, при этом тактовый вход устройства подключен к тактовому входу первого блока управления, первый выход

l-ro блока управления (где i=1,...,n — 1) подключен к тактовому входу (1+1)-го блока управления, вход нулевого потенциала устройства подключен к первому информационному входу первого вычислительного блока, выход i-ro вычислительного блока подключен к первому информационному входу (!+1)-го вычислительного блока, первый информационный вход устройства подключен к информационному входу первого блока дешифрации, выход j-ro блока дешифрации (где j=1, .„n) подключен к второму информационному входу j-ro вычислительного блока, о т л и ч а ю щ е е; что, с целью расширения функциональных возможностей за счет решения булевых дифференциальных уравнений, устройство содержит с (и+1)-ro по.2"-й блок управления, с (n+ 1}-ro по 2"-й блок дешифрации, с (и+1)-го по 2"-й вычислительный блок и коммутатор, причем первый выход К-ro блока управления (где

K=n,...,2"-1) подключен к тактовому входу (К+1)-го блока управления, первый выход 2"го блока управления подключен к первым входам режима всех блоков управления, вход единичного потенциала устройства подключен к второму входу режима 2"-го блока управления, второй вход режима b-ro блока управления (где b= 1,...,2"-1) подключен к второму выходу (b+ 1)-го блока управления, второй выход первого блока управления подключен к выходу признака такта устройства, выход К-ro вычислительного блока подключен к первому информационному входу (К+ 1)-го вычислительного блока, выход с-го блока дешифрации (где

5 с=п+1,...,2") подключен к второму информационному входу с-го вычислительного блока, выход 2"-го вычислительного блока подключен к управляющему входу коммутатора, выходы которого подключены соответ10 ственно к информационным выходам устройства, информационные входы которого с второго по 2"-й подключены соответственно к информационным входам блоков дешифрации с второго по 2"-й, 1-й тактовый

15 вход группы устройства (где 1=1,...,2") подключен к тактовым входам 1-ro блока дешифрации и 1-ro вычислительного блока, третьи выходы блоков управления с первого по

2"-й подключены соответственно к инфор20 мационным входам с первого по 2"-й первой группы всех блоков дешифрации и к информационным входам с первого по 2"-й коммутатора, четвертые выходы блоков управления с первого по 2"-й подключены

25 соответственно к информационным входам с первого по 2"-й второй группы всех блоков дешифрации и к информационным входам с первого по 2"-й группы всех вычислительных блоков, при этом каждый блок управле30 ния содержит два триггера и элемент И, причем в каждом блоке управления тактовый вход блока управления, первый и второй входы режима блока управления подключены соответственно к счетному вхо35 ду первого триггера, к входу установки в "1" второго триггера и к первому входу элемента И, выход первого триггера подключен к первому выходу блока управления, к второму входу элемента И и к третьему выходу

40 блока управления, выход элемента И подключен к четвертому выходу блока управления и к входу установки в "0" второго триггера, выход которого подключен к второму выходу блока управления, при этом

45 каждый вычислительный блок соержит два элемента ИЛИ, 2" элементов И, элемент задержки, сумматор по модулю два и 2" сдвигающих регистров, причем в каждом вычислительном блоке тактовый вход вы50 числительного блока подключен к входам сдвига всех сдвигающих регистров и к входу элемента задержки, выход которого подключен к входам записи-считывания всех сдвигающих регистров, информационные

55 входы с первого по 2"-й группы вычислительного блока подключены соответственно к первым входам элементов И с первого по

2 -й, первый информационный вход вычислительного блока подключен к первому входу первого элемента ИЛИ, выход которого

1661791

10 подключен к выходу вычислительного блока, второй информационный вход которого подключен к первому входу сумматора по модулю два, выход которого подключен к второму входу первого элемента ИЛИ и к 5 информационному входу первого сдвигающего регистра, выход р-го сдвигающего регистра (где р= 1,...,2" — 1) подключен к информационному входу (р+1 -го сдвигающего регистра и к второму входу р-го элемента И, 10 выход 2"-го сдвигающего регистра подключен к второму входу 2"-го элемента И, выходы элементов И подключены к входам второго элемента ИЛИ, выход которого подключен к второму входу сумматора по моду- 15 лю два, при этом каждый блок дешифрации содержит дешифратор, две группы элементов И, элемент ИЛИ и с первого по 2"-й регистры, причем в каждом блоке дешиф- рации информационные входы первой 20 группы блока дешифрации подключены к входам дешифратора, выходы которого подключены соответственно к первым входам элементов И с первого по 2"-й первой группы, выходы которых подключены соответственно к входам записи-считывания регистров с первого по 2"-й, выходы которых подключены соответственно к первым входам элементов И с первого по 2"-й второй группы, выходы которых подключены к входам элемента ИЛИ, выход которого подключен к выходу блока дешифрации, информационные входы с первого по 2"-й второй группы которого подключены соответственно к вторым входам элементов И с первого по 2"-й второй группы, тактовый вход блока дешифрации подключен к вторым входам элементов И первой группы, информационный вход блока дешифрации подключен к информационным входам всех регистров.

1661791

AH г

1661791

Составитель В. Смирнов

Редактор А. Козориз Техред M.Ìîðãåíòàë Корректор И. Муска

Заказ 2126 Тираж 413 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., 4/5

Производственно-издательский комбинат " Патент", г, Ужгород, ул.Гагарина, 101