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

 

Устройство относится к цифровой вычислительной технике и может быть использовано для аппаратной поддержки вычислений в системах автоматизированного анализа и синтеза цифровых автоматов при их диагностике и контроле, в системах генерирования и синтеза изображений, управления роботами-манипуляторами. В устройство, содержащее блок синхронизации и блок вычислений, с целью повышения быстродействия за счет распараллеливания вычислений значений логической производной булевой функции по каждой из переменных, дополнительно введены M-1 блок вычислений и M блоков вывода данных. 2 з.п. ф-лы, 3 ил.

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

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

РЕСПУБЛИК

А1

ÄÄSUÄÄ 1541591 (51)5 G 06 F 7/00, 15/31

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

К А ВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТНРЫТИЯМ пРН ГКНТ СССP

1 (21) 4378636/24-24 (22) 12. 02. 88 (46) 07.02.90. Бюл. У 5 (71) Минский радиотехнический инсти тут (72) С. Н. Янушкевич, Е.Н. Зайцева, Г.А. Кухарев и В.П. Шмерко (53) 681. 327. 6 (088 ° 8) (56) Авторское свидетельство СССР

9 1168925, кл. Г 06 F 7/04, 1985.

Авторское свидетельство СССР

Р 1277089, кл. Г 06 F 7/04,,1987 ° (54) УСТРОЙСТВО ДЛЯ ЛОГИЧЕСКОГО

ДИФФЕРЕНЦИРОВАНИЯ БУЛЕВЫХ ФУНКЦИЙ (57) Устройство относится к цифроИзобретение относится к области цифровой вычислительной техники и может быть использовано для аппаратной поддержки вычислений в системах автоматизированного анализа и синтеза цифровых автоматов, при их диагностике и контроле, в системах генерирования и синтеза изображений, управления роботами-манипуляторами..

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

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

2 вой вычислительной, технике и может быть использовано для аппаратной поддержки вычислений в системах автоматизированного анализа и синтеза цифровых автоматов при их диагностике и контроле, в системах генерирования и синтеза изображений, управления роботами-манипуляторами. В устройство, содержащее блок синхронизации и блок вычислений, с целью повышения быстродействия за счет распараллеливания вычислений значений логической производной булевой функции по каждой из переменных, дополнительно введены И-1 блок вычислений и М блоков вывода данных. 2 з.п.ф-лы, 3 ил.

В основу предлагаемого изобрете= ния положены следующие математические модели функционирования компонентов и устройства в целом.

Логическая производная булевой функции f(х) = f(х „ х, ..., х 3. переменных по перемнной х (i = 1,mg определяется соотношением

-af(x) ах= f(x,, ... х,, х,„)6Г(х

Э В 1

° ° ° у х1 у ° ° ° Х1 1) ° (1)

В матричном виде данная процедура представляется следующей математической моделью: ай (х) < 1 (mod 2) (2) ах,. где Х вЂ” вектор значений (вектор ucf тинности) булевой функции

f (x), Х = х " х "... х< - >), 1541591

Э вЂ” матрица дифференцирования () размерности 2"х 2, формируемая по рекуррентному соотношению (1 11

1, 2 (1 1 2 — символ кронекеровского про- 10 изведения матриц; — единичная матрица размерности 2 х 2 . где,g

7 выходных данных соответственно, информационный вход регистра 7 выОперации сложения при перемножении матрицы и вектора Х в (2) также выполняются по модулю два.

На фиг. 1 представлена структурная схема устройства; на фиг. 2 — структурная схема блока вычислений; на фиг. 3 — структурная схема блока вывода данньгх.

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

3 вывода группы являются выходами устройства. 35

Блок 1 вычислений (фиг. 2) содержит регистр входных данных 4, сумматор 5

rro модулю два, коммутатор 6, причем информационный вход и вход синхронизации коммутатора 6 являются информационным входом и входом синхронизации блока соответственно, первый и второй выходы коммутатора 6 подключены к первому информационному входу

45 сумматора 5 по модулю два и к информационному входу регистра 4 входных данных соответственно, выход регист- ра 4 входных данных подключен к второму информационному вхог(у сумматора по модулю два 5, выход которого явля- 5О ется выходом блока.

Блок 3 вывода данных (фиг. 3) содержит регистр 7 вьгходных данньгх и коммутатор 8, первый и второй информационные вход которого подключены к ггервому и второму выходам регистра ходных данных и управляющий вход коммутатора 8 являются информационным и управляющим входами соответственно, выход коммутатора 8 является выходом блока.

Устройство функционирует следующим образом.

Пусть необходимо вычислить логическую производную Х /дх,, aX /дх и дХ /дхэ булевой фуйкции Е(х)

= Е(х„, х, х ) трех переменных. Исходный вектор значений Х(= (х х (е) (1) х(")7 функции f (х) подается поэлементно, начиная с младшего элемента х() на информационный вход устройства.

Устройство содержит три блока вычислений и три блока вывода данных и блок синхронизации.

Рассмотрим работу первых, вторых и третьих блоков вычислений и блоков вывода данных.

На тактах с первого по четвертый происходит загрузка первого блока вычислений элементами х(), х(">, х( и х(вектора значений Х . Это осу(8) ществляется следующим образом: на первом такте первый элемент х в ектора Х поступает на информационный вход коммутатора 6 и передается на

его второй выход по низкому логическому уровню сигнала на его входе синхронизации и записывается в регистр 4. На втором такте элемент x (} () (и ) т сывается в регистр 4 аналогично.

Одновременно элемент х перезапи(о! сывается из первого во второй pasряд регистра 4. На третьем и четвертом тактах .значения элементов х ( и х вектора Х последовательно

Х записываются в регистр 4 ° Таким образом„ к концу четвертого такта значения элементов х х х х оказываются записанными соответственно B четвертом, третьем, втором и первом разрядах регистра 4. На пятом такте происходит суммирование по (о) модулю два элемента x(), поступившего с выхода регистра 4, и элемента (Ф) х, поступившего с первого выхода коммутатора 6 по высокому логическому уровню напряжения на его входе синхронизации. Результат суммирования у () = х(@x поступает на информационный вход регистра 7 и по высокому логическому уровню сигнала на входе синхронизации коммутатора 8 передается íà его выход, т.е. на пер1591 6 шестом тактах соответственно на выход устройства передаются значения элементов у (2) = у (,") и у (, = у, ), 5 а в регистр 4 последовательно записываются значения элементов х () и х() вектора Х,. На седьмом и восьмом тактах на йьжод устройства по(с) ступают элементы у ) = х ()9 х и у (2 ) = x (их (7) вектора результата Y /х„, а на девятом и десятом— ре зультаты v у 1 и у 2) jj () °

Таким образом, на первых вух тактах происходит загрузка второго блока вычислений, на следующих Boch ми — выдача результата Y /õ 2 (у (а) у (1) у (7) ) 1

2 2 2

Рассмотрим функционирование третьего блока 1 вычислений и третьего

20 блока 3 вывода данных.

При вычислении Y /õ на первом такте происходит загрузка третьего блока вычислений первым элементом х(вектора значений Х . На втором

25 такте выполняется суммйрование по модулю два элементов х и х (. Pe(а) (а) (ц зультат суммирования у (= х )® х(" поступает на выход устройства и, кроме того, записывается в регистр 7. третье с выхода регистра 7 поступает на выход устройства, при этом пройсходит загрузка блока вычислений значением элемента х . Далее на четных тактах (четвертом, шестом и восьмом) происходит формирование результатов суммирования соответственно у ( (2) DI (4) (4)> (5) у (6)

= х ® х"), а на нечетных (пятом, 40 седьмом и девятом) на выход устройпоступают pe3 ëh Tû у = у () и у () = у (с) соответственз з з но.

Таким образом, на нервом такте происходит загрузка вычислительной ячейки, а на втором и последующих— выдача результата Y /х = (у(а) у 1 ... у() 1 (по девятый такт включительйо), 50

5 154 вый вьжод устройства. На шестом такте на выход устройства передается результат у() = х()()))х (s) этот же

:результат записывается в регистр 7.

На седьмом и восьмом тактах на выход устройства передаются соответственно результаты у(, ) = х(ех и у

= х в х и, кроме того, по оконча(з) (т) нии восьмого такта в регистре 7 ока(а) зываются записанными элементы у а)

Э у(,", у(;, у (, )- элементы второго из пары равных векторов д Х / а)х; и ) Х / х, составляющих вектор результата йХ /3x.. На девятом такf те вычислений с выхода ре,гистра 7 через коммутатор на вьжод устройства поступает значение элемента у(4) = у(а)

2 вектора результата Y /õ,, а на десятом — двенадцатом тактах соответст(2)

Т

1 1 у, ) . На девятом такте в устройстве можно вводить для обработки элементы следующего вектора Х,.

Таким образом, на первых четырех тактах в предлагаемом устройстве выполняется загрузка блока вычислений значениями элементов вектора Х, на следующих восьми — выдача результата дифференцирования, причем, начиная с девятого такта, может осуществляться загрузка блока вычислений элементами следующего вектора Х(.

Функционирование второго блока 1 вычислений и второго блока 3 вывода данных, обеспечивающих вычисление вектора У /х2, происходит следующим образом.

На первых двух тактах выполняется загрузка второго блока вычислений элементами х а) и х вектора зна(1) и Х )х (а» (>) х (т) (î I первом такте элемент х записывается в регистр 4 (его первый разряд), на втором также в регистр 4 (его первый разряд) записывается элемент х() а элемент х ) перезаписывается во второй разряд регистра 4. На третьем такте происходит суммирование по модулю два элементов х <а» и (2) х и результат у = х )Фх поступает на выход устройства и, кроме того, записывается в регистр 7 выходных данных. К концу четвертого такта на выход устройства поступает результат у(, ) = х") эх (), а в регистре 7 оказываются записанными значения элементов у )и у",(. На первом и

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

i» Устройство для логичеСкого дифференцирования булевых функций, содержащее блок синхронизации и блок вычислений, причем информационные входы блока вычислений являются входами устройства, а входы синхронизации блока вычислений подключены к выходам блока синхронизации, о т л и1541591 ч ающ е е с я тем, что, с целью позыв ения быстродействия за счет распараллеливания вычислений значений логической производной булевой функции по каждой иэ переменных, в

5 устройство введены М-1 блоков вычислений и М блоков вывода данных, где

М вЂ” количество переменных„ причем информационные входы блоков вывода данных подключены к выходам блоков вычислений, входы синхронизации блоков вывода данных подключены к выходам блока синхронизации, а выходы блоков вывода данных являются выходами устройства.

2, Устроиство по пе 1 о т л и ч а ю щ е е с я тем, что блок вычислений содержит сумматор по модулю два, регистр входных данных и коммутатор, щ причем первый выход коммутатора соeJTHHeH с первым информационным входом сумматора по модулю два, второй выход коммутатора подключен к информационному входу регистра входных данных, выход которого подключен к второму информационному входу сумматора по модулю два, причем информационным входом и входом синхронизации блока являются со отв е т с тв ен но инфо рмацио нный вход и вход синхронизации коммутатора, а выход сумматора по модулю два — выходом блокa..

3. Устройство по п. 1, о т л ич а ю щ е е с я тем, что блок вывода данных содержит регистр выходных данных и коммутатор, первый и второй информационные входы которого подключены соответственно к первому и второму выходам регистра выходных данных, вход которого является информационным входом блока, а вход синхронизации коммутатора — входом синхронизации блока, выход коммутатора является выходом блока.

1541591 0 8uwcrt84Ub

Ретсяр(поклепа йорма данньи) -й роюря8 ретсара

4 -йразря

Составитель А. Доброхотов

Редактор Е. Папп Техред М.Ходанич Корректор О. Кравцова

Заказ 280

Тираж 5б9

Подписное

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

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

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

Фроо

7-йра юд

g-g %7.ф7УУ кокнуть

f-й ро рЯ РбастРо