Устройство для решения булевых дифференциальных уравнений Советский патент 1991 года по МПК G06F17/14 

сх

Os

3

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

Лнф. 8/00Ы

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

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

Устройство (фиг. 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 задержки.

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

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

X K22nF2n(mod2),

() где F2ri матрица дифференцирования

размерности 2пх2п, формируемая по соотношению

$-|,)Г

F

1 1

® 2

1,п,

где I 21 1 и 12П единичные матрицы размерностей 2мх2 1 и 2гНх2 | соответственно

- символ кронекеровского произведения матриц, причем при умножении

. (О-

матрицы F 2 и вектора X используются операции конъюнкции и суммирования по модулю два.

Матрица К 22 размерности 22 х2 формируется из матрицы конъюнктивного пре„По ЭП

образования К22 размерности 2 х 2 путем выделения столбцов с номерами 2 (,2n-1) и удаления остальных:

К2 К2 -1 ЈК2;

1 О 1 1

М,2П, К2

0

5 0 5

0

5

0

5

0

5

На втором этапе над векторами X™ системы X выполняется операция поэлементной дизъюнкции, В итоге получают вектор решения Г(как результат объединения ре; шений отдельных уравнений системы).

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

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

(1...х2П-1 т

искомых булевых функций f(X).

Функционирование 1-го блока 1 управления (,2П) рассмотрим на примере блока 11 управления.

В момент времени to на счетный вход триггера 5 поступает тактовый импульс и на выходе триггера 5 формируется уровень логического О. Он передается с выхода триггера 5 на первый вход элемента И 7 и на третий выход блока 11. В момент времени to на вход установки в 1 триггера 6 поступает высокий логический уровень сигнала и на выходе триггера 6 формируется уровень логической 1, который передается на второй выход блока IL Сигнал высокого уровня подается на второй вход элемента И 7, с выхода которого низкий логический уровень сигнала передается на четвертый выход блока 1i.

В момент времени ц на счетный вход триггера 5 поступает тактовый импульс, который устанавливает триггер 5 в состояние логической 1. С выхода триггера 5 высокий логический уровень сигнала поступает на первый вход элемента И 7 и на третий выход блока 1i. В момент времени ti на второй вход элемента И 7 поступает высокий логический уровень сигнала, с выхода элемента И 7 этот сигнал передается на вход установки в О триггера 6 и на четвертый выход блока 11. На выходе триггера 6 устанавливается низкий логический уровень сигнала, который передается на второй выход блока 1i

7П

(он сохраняется на нем по Чг -и такт включительно),

На третьем такте (момент времени to) в схеме происходят те же переключения, что и на первом такте, за исключением того, что на вход установки в 1 триггера 6 сигнал не поступает. На четвертом, пятом и т.д. по

2П

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

Процесс функционирования блока 2| осуществляется следующим образом: на тактах с первого по 2п-й выполняется загрузка элементовd ° -V1-M)d( О i-гостолбца матрицы преобразования F2n, так что на К-м (,2П) такте загружается элемент (К-1,1-1) зтот элемент передается на выход на соответствующих тактах работы устройства (элемент dK на тактах с ()-го

I/«п

по 2 -и), Процесс завершается на 2 -м такте.

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

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

В результате на первом выходе дешифратора 8 формируется высокий логический уровень сигнала, который передается на первый вход элемента И 10i, на второй вход которого поступает тактовый импульс. В результате импульс записи с выхода элемента И 10i передается на вход записи считывания регистра 19i, на информационный вход которого поступает элемент d |M i-ro столбца матрицы преобразования F2n. На этом такте на выход блока через элемент ИЛИ 12 с выхода элемента И 11к (на его втором входе - низкий логический уровень сигнала) передается низкий логический уровень сигнала.

На втором такте (момент времени ti) на входы с первого по 2п-й дешифратора 8 поступает код 1,0,...,0. В результате на втором выходе дешифратора 8 формируется высокий логический уровень сигнала, который передается на первый вход элемента И 102. При этом на его второй вход поступает тактовый импульс, он передается на вход записи регистра 92, на информационный вход которого поступает следующий элемент d 1 1-го столбца матрицы преобразования р2п. На этом такте на выход блока через элемент И 111 (на его втором входе - высокий логический уровень сигнала) и элемент ИЛИ 12 передается содержимое регистра 9i-(r°|M (на остальных входах элемента ИЛИ 12 - сигналы логического О).

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

Функционирование вычислительного

блока 3j рассмотрим на примере вычислительного блока Зп

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

5

5

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

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

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

0 На втором такте (момент времени ti) на вторые входы элементов И 14к поступает

код 1,00. В результате на выход элемента

И 14т, а затем на первый вход элемента ИЛИ 17 передается содержимое регистра 15i, С

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

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

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

выход блока 3i.

2 1

На третьем и последующих (по 2 -и) тактах блок 3i функционирует, как и на втором При этом элементе г .2n) первого столбца матрицы преобразования Р%п

поступают на второй информационный вход блока 3i в такой последовательности: на третьем и четвертом тактах - элемент г , на пятом - восьмом - элемент сг2 0 и т.д., так что К-й элемент первого столбца матрицы преобразования F2n поступаете ()-го такта по 2к-й такты включительно.

Функционирование блока За отличается от функционирования блока 3i тем, что на его первый информационный вход сигналы поступают с выхода блока З-i, а на второй информационный вход блока Зг поступают элементы второго столбца матрицы преобразования F 2П- На выход блока 3| передаются результаты, формируемые на выходе его элемента ИЛИ 16.

Формула изобретения Устройство для решения булевых дифференциальных уравнений, содержащее с первого по п-й вычислительные блоки, где п -число булевых переменных, с первого по n-й блоки управления и с первого по п-й блоки дешифрации, при этом тактовый вход устройства подключен к тактовому входу первого блока управления, первый выход 1-го блока управления (где 1 1п-1) подключен к тактовому входу (1+1)-го блока управления, вход нулевого потенциала устройства подключен к первому информационному входу первого вычислительного блока, выход 1-го вычислительного блока подключен к первому информационному входу (i+1)-ro вычислительного блока, первый информационный вход устройства подключен к информационному входу первого блока дешифрации, выход j-ro блока дешифрации (где J-1п) подключен к второму информационному входу j-ro вычислительного блока, отличающееся тем, что, с целью расширения функциональных возможностей за счет решения булевых дифференциальных уравнений, устройство содержит с (п+1)-го по 2п-й блок управления, с (п+ 1)-го по 2п-й блок дешифрации, с (п+1)-го по 2п-й вычислительный блок и коммутатор, причем первый выход К-ro блока управления (где

К п2п-1) подключен к тактовому входу

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

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

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

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

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

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

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

подключен к выходу вычислительного блока, второй информационный вход которого подключен к первому входу сумматора по модулю два, выход которого подключен к второму входу первого элемента ИЛИ и к информационному входу первого сдвигающего регистра, выход р-го сдвигающего регистра (где р 12п-1) подключен к информационному входу (р+1)-го сдвигающего регистра и к второму входу р-го элемента И, выход сдвигающего регистра подключен к второму входу элемента И, выходы элементов И подключены к входам второго элемента ИЛИ, выход которого подключен к второму входу сумматора по модулю два, при этом каждый блок дешифрации содержит дешифратор, две группы элементов И, элемент ИЛИ и с первого по 2п-й регистры, причем в каждом блоке дешифрации информационные входы первой

г

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

информационным входам всех регистров.

у

Вход уст. В 1

1

Г

1

фиг 4