Устройство для вычисления булевых производных

(46) (71) Ф 19ехнический интит 72) т В.М. Да Тупико Д.В. Кузьмицкмерко енко В.П В Д ельство СССР 15/31, 1982,ьство СССР 7/04, 1985. ЫЧИСЛЕНИЯ БУЛЕ аратнои поддержкиемах анализа и назначено для а вычислений в си синтеза цифровы между ф-лы,нных, синтез а уп- диаг- устиаг е р уставтома е и пред оддержки за и си жатия д обраб тор 1, й блок упра а сче произ рои- устых.а фиг,1 изображен ойства для вычисл од блок-схе ния булевых - блок-схем а фиг.3 - в ус шения ГОСУДАРСТВЕННЫЙ КОМИТЕТПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМПРИ ГКНТ СССР ОПИСАНИЕ ИЭ АВТОРСКОМУ СВИДЕТЕЛЬСТВ и С.Н. Янушкевич(54) УСТРОЙСТВО ДЛЯ ВВЫХ ПРОИЗВОДНЫХ57) Изобретение относится к автомтике и вычислительной технике и пр автоматов, сжатиятопологии БИС, обраИзобретение относится е и вычислительной техниназначено для аппаратнои п вычислений в системах акали теза цифровых автоматов, с ных, синтеза топологии БИС ки изображений.Цель изобретения - расши функциональных возможностей вычисления смешанных булевы роизводных, на фиг,2перационного блока; н 2ботки изображений, Цель изобретения - расширение функциональных возможностей за счет вычисления смешанных булевых производных. Устроиство содержит коммутатор, операционный блок, группу триггеров, демультиплексор, блок управления. В процессе работы исходные данные в виде отдельных композиций матрицы через информационный вход устройства и коммутатор заносятся на операционный блок, где происходит поразрядное суммирование исходного и сдвинутого векторов композиций матрицы. В зависимости от режима устройство позволяет по заданной системе векторов значений логических функций и переменных вычислять смешанную булевую производную по направлению диагоналиосями столбцов и строк. 1 з.п.5 ил., 2 табл. риант функциональнои схемы блокравления на фиг4 - временнаярамма для первого режима работыройства, на фиг.5 - временная драмма,пля второго режима работыройства,Устройство содержит коммутадемультиплексор 2, операционны3, группу 4 триггеров, блок 5ления, информационный вход 6 усства, три управляюцдх входа 7-9ройства, выход 1 О устройства, в11 коммутатора 1, выход 12 упрания коммутацией, выход 13 разресдвига влево, выход 14 управлени1481793 Та бли ца 2 Сигналы навходе шифратора 561 0 Сигналы на выходешифратора 56 . 000 001 010 000 0,00 010 15 111 111 размеробразовами знач2 -1); буХ) перем е К- матриц2 2вектоЦ 0 иная 2 ний Х евых фун нных,т.ех Х, В - коорди соотве столбц М- матриц 2 х 2ы ма оки тственнз);а раэмеформир ая по пра л М си нулеатлица игналы находе шифрата 55 Сигналы на выходшифратора 55 111 000 0 1 О 1 режимом коммутатора, выход"15 разрешения записи в сдвиговый регистр,выход 16 разрешения записи в регистр,выход 17 разрешения сдвига вправо,выход 18 разрешения записи. Операционный блок 3 содержит коммутатор19, сдвиговый регистр 20, группу21 элементов НЕРАВНОЗНАЧНОСТЬ, демультиплексор 22, регистр 23, выход24 блока, элементы ЗАПРЕТ 25 и 26,элементы И 27-35, элементы ИЛИ 36-41,счетчики 42-46, схемы 4.7"49 срав"нения, регистры 50-52, триггеры 53и 54, дешифраторы 55 и 56, генератор57 импульсов, элементы 58-61 задержки,Счетчик 42 предназначен для рег"ламентирования работы устройства придифференцировании матрицы К ъ по переменной Х ш раэ и предсТавляет собой ш-разрядный двоичный суммирующийсчетчик. Исходное состояние счетчика 42 - нулевое.Счетчик 43 предназначен для регламентирования работы устройствапри дифференцировании результата81 К /ЭХ 1 по переменной В 1 рази представляет собой 1-разрядныйдвоичный суммирующий счетчик. Исходное состояние счетчика 43 - нулевое.Счетчик 44 предназначен для регламентирования работы устройствапри дифференцировании матрицы Епо переменным (Х,В) г раз и представляет собой г-разрядный двоичныйсуммирующий счетчик. Исходное состояние счетчика 44 - нулевое.Счетчик 45 - двухразрядный двоичный суммирующий счетчик, Исходноесостояние счетчика 45 - нулевое,Счетчик 46 - 2 -разрядный двоичный суммирующий счетчик. Исходноесостояние счетчика 46 - нулевое.Регистры 50-52 являются ш,1 иг-разрядными регистрами соответственно. Иифратор 55 кодирует входныегналы в соответствии с табл,1. Шифратор 56 кодирует входные сигналы в соответствии с табл.2. Смешанная булевая производная первого типа системы булевых функций в матричном виде определяется следующим образом М К М (той 2) (1) Поясним соотношение (1) на кретном примере. Пусть й = 2 вые функции двух переменных) рица Кр задана в виде5 1481793 6Эта матрица образована четырьмя , Данное свойство использовано в булевыми функциями Г (Х), где Цустройстве для восстановления исход 0,3), которые задайы своими некто- ной системы К векторов Х булевых рами значений Х . функций Г(Х).Для этого необходимо5систему К в подвергшуюся обработкеВ соответствий с (1) смешанная операторой дифференцированая по одбулева производная первого типа име- ной из координат Х и В а и 1 раз ет вид соответственно продифференцировать2"-ш и 2"-1 раз соответственно.Математическая модель (2) реалиЗхав = 2 гХгзуется устройством в первом резямеработы,Смешанная булева производная вто 11 1111 11 .0000 1 10101 110101000 011 1000111 рого тица системы булевых функцийпо обоим координатам Х и В одновременно определяется в матричном видеследующим образом В общем виде соотношение (1) можно записать следующим образом 20 З=вв 914 еь (4)4 ВВВ гдеЬ- матрица сдвига размерности формируемая по правилу)где операции в квадратных скобкахповторяются ш и 1 раз соответственно.01 Выражение (2) может быть использовано для вычисления смешанной булевой производной первого типа любого порядка по координатам Х и В..При этом следует учитывать важное свойство оператора булевого дифференцирования порядка а и 1. Это свойство периодичности. Суть его заключается в том, что значения производных систем булевых функций повторяются с периодом 2 , т.е. 30 Поясним соотношение (4) на примере вычисления ЗКф /З(Х,В)матрицы 111 0000 01 01 1010 35 В соответствии с (4) получим 40Ввг 9 Ьхг Вгг Ьхи1 11 01 11 11 010000 01,0000 О 145 0101 01 01010 0 О 1010 К л 1 +К 44О К111 001 000 101 Х 1" к) о Е 4 а" к И общем виде соотношениео записать следующим образо) м Из соотношения (3) для матрицы Рсущес изводных по каждой из того, при 1, ш = 2Данный оператор также обладает свойством периодичности, которое может быть записано в виде 1+" кедается по столбцам с информанного входа устройства через к причем при г = 2 К (К = 0,1,2,) матрица Рвосстанавливается, Соответственно, для восстановления исходной системы К векторов Хбулевых функций й (Х) необходимо сис)тему, подвергшуюся обработке оператором дифференцирования по (Х,В) г раз, продифференцировать по (Х,В) (2" - г) раз.Таким образом, оператор вида (5) позволяет вычислить производную системы булевых функций по диагонали с направлением возрастания значений отсчетов координат Х и В.Математическая модель (5) ре лизуется устройством при работе его во втором режиме.Таким образом, математические модели(2) и (5), положенные в основу функционирования устройства, реализуются в двух режимах.Первый режим позволяет по заданной системе Кл векторов значений Х 1 (3 = 0,2 - 1) логических функций(Х) и переменных вычислять смешанную булеву производную первого типаЯ +1 К / Э Х д В 1 по направлению осей координат Х и В (столбцов и строк соответственно), т.е.:по направлению возрастания переменной Х = - (Х, Х" Х ) и переменной "весов" векторов Х,Второй режим позволяет по заданной системе Кь векторов значений Х 1 логических функций й(Х) и перемейных вычислять смешанную булеву производную второго типа по (Х,В) вида оК /д(Х,В) т.е. по направ лению диагонали между осями Х и В.Работу устройства рассмотрим на примере реализации математической модели вида Э К /дХ. Выходные параметры этой модели имеют следующие значения: г = О, ш = 1, 1 = О,Исходная матрицаа 100 010 100 010 по столбцам подается на информационный вход операционного блока 3, Впервом такте на регистр 23 заносятся О значения элементов вектора Х , а восдвиговый регистр 20 - значейия элементов вектора Х , которые затемсдвигаются на одйн разряд вправо всторону разрядов. Группа 21 злементо 5 НЕРАВНОЗНАЧНОСТЬ выполняет операциюсложения по модулю два содержимыхсдвигового регистра 20 и регистра 23а результат Э Х / 3(Х,В) эаписываетося в группу 4 триггеров.Во втором такте происходит сдвигсодержимого с 4 вигового регистра 20в сторону старших разрядов под управлением сигнала с выхода 13 разрешенисдвига влево, далее происходит .записрезультата в регистр 23, а затем всдвиговый регистр 20 записываетсяследующий вектор Х и происходитгсдвиг на один разряд вправо в сторону младших векторов Х. Группа 21 мутатор 1 на вход операционногоблока 3.В первом такте в сдвиговый регистр 20 и регистр 23 заносятся значения элементов первого столбца Хматрицы К , В сдвиговом регистре20 происходит сдвиг содержимого наодин разряд в сторону младших разрядов, под управлением ствола с выхода17 разрешения сдвига вправо, и далеепоразрядное суммирование по модулюдва содержимого сдвигового регистра20 и содержимого регистра 23 (вгруппе 21 элементов НЕРАВНОЗНАЧНОСТЬ),т.е. исходного н сдвинутого векторов. Результат (ЭХ /ЗХ) заносится вогруппу 4 триггеров.Во втором также в сдвиговый регистр 20 и в регистр 23 заносятсязначения элементов второго вектораХ матрицы Ки далее повторяютсят фпроцедуры, аналогичные процедурампервого такта,25 После завершения последнего такта результат д Р/3 Х з писывается вгруппу 4 триггеров.Рассмотрим реализацию математической модели вида Э Р /Э(Х,В). Входные параметры этой модели имеют следующие значения: г = 1, ш = О, 1 = ОИсходная матрицаэлементов НЕРАВНОЗНАЧНОСТЬ осуществляет операцию сложения по модулюдва содержимого сдвигового регистра20 и регистра 23, и результат вычисления записывается в группу 4 триггеров.В четвертом такте в группу 4 триггеров записывается вектор ХТаким образом, в группе 4 тригге 3ров формируется результат дифференцирования д Р/ Э(Х,В).Теперь рассмотрим работу устройства н общем, выделив два режима.В первом режиме реализуется математическая модель (2) вида Э(Р, //ЗХ ЭВ . При этом можно выделитьдва этапа.На первом этапе первого режимаустройство реализует вычислениявида Э ( К /ЭХВ начальиых тактах на второй итретий управляющие входы 8 и 9 устройства подаются значения параметров ш и 1 соответственно, В операционный блок 3 с информационноговхода 6 через коммутатор 1 записывается вектор - столбец Х 1 ( = 1, 2")1матрицы Р= ХХХ 1начиная с вектора Х, , и осуществлялоется обработка вектора Х в соответствии с математической модельюЗХ /ЗХ (Под управ 1 ением сигнала низкогоуровня с выхода 18 разрешения записиполученный в операционном блоке 3результат ( о Х, /ЗХ( ) записынается в группу 4 триггеров,На втором этапе первого режимаустройство реализует вычисления видааф(а( К,/ЗХ")/ав ",На этапе по высокому логическомууровню сигнала с выхода 18 разрешения записи (признак считынания информации по строкам) результат вычисления первого этапа дифференцирования 3( Р /ЗХ(из группы 4триггеров через демультиплексор 2 икоммутатор 1 (под управлением сигнала с выхода 12 управления коммутацией) передается в операционный блок3. Операционный блок 3 выполняетобработки матрицы 3 ( К/д Х ( в соответствии с математической модельюд(д( К /д Х) /дВ( . Результатвиде матрицы 3 ф/Зч(З ВИ)записывается в группу 4 триггеров идалее через демультиплексор 2 поступает на выход 10 устройства.Таким образом, в первом режиме устройство реализует математическуюль нида(1111 /ЗХ(Ф)ЗВ(0Во втором режиме реализуется математическая модель (5) видаЭ(ф К /д (Х,В)(,В начальных тактах на первый управляющий вход 7 устройства подается значение параметра г. В операционный 1510 блок 3 с информационного входа 6 через коммутатор 1 записывается вектор Х; Я=1,2") матрицы К Х Х ХД начиная с вектора Х,Операционным блоком 3 выполняетсяобработка матрицы К(каждого изее векторов Х ) в соответствии сматематической моделью (5) видаЗК,/З(Х,В) (ЗХ; /З(Х,В), Результат20 обработки поступает на группу 4 триггеров. Полученный результат черездемультиплексор 2 и коммутатор 1поступает в операционный блок 3 (повекторам ( Х /З(Х,В) г - 1 раз.Пос 25 ле обработки результат н виде матрицы Э(К/д(Х,В)" поступаетчерез демультиплексор 2 на выход 10устройства,Таким образом, во втором режиме30 устройство реализует математическуюмодель вида 3( К /З(Х,В)1,Для восстановления исходной системы по результату диЬеренцирования 3( К/ЗХ(1 ЗВ первого режима достаточно подать на второй и третий управляющие входы 8 и 9 устройствапараметры (2"-т) и (2 -(,) соответственно.В результате обработки в соответствии с математической моделью (2) и40 свойством (3) исходная матрица Кь- восстановится, Аналогично дпя носстановления исходной системы по результату дифференцирования 3(" К//З(Х,В) " второго режима необходимо45 на первыи управляющий вход 7 устрой-ства подать параметр (2 -г), и нрезультате обработки в соответствиис математической моделью (5) и свойством (6) исходная матрица Квосстановится.Формула изобретения1. Устройство для вычисления булевых производных, содержащее группутриггеров, демультиплексор, причемвход демультиплексора соединен с выходом триггеров группы,о т л и ч а ющ е е с я тем, что, с целью расширения функциональных воэможностей засчет вычисления смешанных булевых93 12 1 1481 1 производных, оно содержит коммутатор, операционный блок и блок управления, причем информационный вход устройства соединен с первым информацион 5 ным входом коммутатора, второй информационный вход которого соединен с первым выходом демультиплексора, а выход соединен с;информационным входом операцйоиного блока, выход которого соединен с информационным входом триггеров группы, первый,второй и третий управляющие входы устройства соединены соответственно с первым, вторым и третьим входами 15 блока управления, выход управления коммутацией которого соединен с управляющими входами коммутатора и демультиплексора, выход разрешения сдвига влево, выход управления режи мом коммутатора, выход разрешения записи в сдвиговый регистр, выход разрешения записи в регистр и выход разрешения сдвига вправо соединены соответственно с первым, вторым, треть им, четвертым и пятым управляющими входами операционного блока, выход разрешения записи соединен с управляющим входом триггеров группы,второй выход демультиплексора является 3 п выходом устройства. 2, Устройство по п.1, о т л ич а ю щ е е с я тем, что операционный блок содержит коммутатор, сдвиговый регистр, регистр, группу элементов НЕРАВНОЗНАЧНОСТЬ,демультиплексор, причем информационный вход операционного блока соединен с первым информационным входом коммутатора, второй информационный вход которого соединен с первым выходом демультиплексора, а выход соединен с инФормационным входом сдвигового регистра, выход которого соединен с первым входом элементов НЕРАВНОЗНАЧНОСТЬ группы и информационным входом регистра, выход которого соединен с входом элементов НЕРАВНОЗНАЧНОСТЬ группы, выход которой соединен с входом демультиплексора, первый, второй, третий четвертый и пятый управляющие входы операционного блока соединены соответственно с первым входом разрешения сдвига сдвигового регистра, с управляющим входом коммутатора и демультиплексора, с управляющим входом сдвигового регистра, с управляющим входом регистра, с вторым входом разрешения сдвига сдвигового регистра, второй выход демультиплексора является выходом операционного блока.(хИ 1 б оФ 17 дихт Составитель В. Сорокинктор В. Данко Техред М.Ходанич КорректорВ. Гирня 69 КНТ ССС оизводственно-издательский комбинат "Патент" г. Ужгород, ул, Гагарина, 101 дьюдйг 3 лока ур раЮлмия Заказ 2692/51 ВНИИПИ Госуда АиюУм Хлеау ураем.нн 1 5 венного комитета 113035, Москва, Ж Подписноеизобретениям и открытиям Раушская наб., д. 4/5