Пристрій для обчислення булевих диференціалів

Изобретение относится к автоматике и вычислительной технике и предназначено для автоматизации процесса вычисления булевых дифференциалов при проектировании средств тестового и аппаратурного контроля комбинационных схем, систем автоматизированного проектирования дискретных устройств. Наиболее близким к заявляемому устройству является устройство для вычисления булевых дифференциалов [Авт.св.СССР № 940166, кл, G 06 F 15/31, 1982], содержащее счетчик и один канал с арифметическим блоком, включающий первый и второй мультиплексоры, первый элемент НЕРАВНОЗН АЧНОСТЬ, а также блок элементов И-НЕ, демультиплексор, регистр результата, причем информационные входы первого и второго мультиплексоров соединены с шиной исходных данных, выходы счетчика соединены с управляющими входами первого мультиплексора, демультиплексора и с первой группой входов блока элементов И-НЕ, вторая группа входов блока элементов И-НЕ соединена с шиной переменных, выходы блока элементов И-НЕ соединены с управляющими входами второго мультиплексора, выход первого и второго мультиплексоров соединены с входами элемента НЕРАВНОЗНАЧНОСТЬ, вы ходы демультиплексора соединены с входами регистра результата. Однако известное устройство обладает ограниченными функциональными возможностями поскольку функционирует в одном из двух режимов, вычисления ориентированных или неориентированных булевых дифференциалов (булевых разностей) и не способно осуществлять ориентированное дифференцирование по одним переменным булевой функции и неориентированное - по другим ее переменным, кроме того, обладает низким быстродействием вследствие последовательного алгоритма работы и последовательной архитектуры аппаратурного решения. Задачей настоящего изобретения является создание такого устройства, в котором новое (параллельнопоследовательное) выполнение его структуры позволяет обеспечить возможность одновременного как ориентированного, так и неориентированного дифференцирования булевой функции по различным переменным и за счет этого расширить класс решаемых задач, а также повысить быстродействие. Эта задача решается тем, что в устройстве для вычисления булевых дифференциалов, содержащем счетчик и один канал с арифметическим блоком, включающем первый и второй мультиплексоры, а также первый элемент НЕРАВНОЗНАЧНОСТЬ, со-' гласно изобретению, дополнительно введено (n-1) канал с арифметическим блоком в каждом, причем в каждый канал устройства введены два элемента задержки, а в каждый арифметический блок - инвертор, второй элемент НЕРАВНОЗНАЧНОСТЬ, первый и второй элемент совпадения, третий и четвертый мультиплексоры, при этом выход первого блока задержки соединен через второй элемент задержки с первым информационным входом арифметического блока и непосредственно с вторым информационным входом арифметического блока, вход первого блока задержки соединен с третьим информационным входом арифметического блока, выход которого соединен с входом следующего канала, n разрядных выходов счетчика подключены к первым управляющим входам n арифметических блоков, выход последнего канала является выходом устройства, входом которого служит вход первого канала, кроме того первый информационный вход арифметического блока через первый вход первого элемента НЕРАВНОЗН АЧНОСТЬ соединен с первым информационным входом первого мультиплексора и первым входом первого элемента совпадения, выход которого соединен с первым информационным входом второго мультиплексора, выходы первого и второго мультиплексоров соединены соответственно с первым и вторым информационными входами третьего мультиплексора, второй информационный вход арифметического блока соединен с вторым входом первого элемента НЕРАВНОЗНАЧНОСТЬ, с первым входом второго элемента НЕРАВНОЗН АЧНОСТЬ и с первым информационным входом четвертого мультиплексора, выход третьего мультиплексора соединен с вторым информационным входом четвертого мультиплексора, выход которого является выходом арифметического блока, третий информационный вход арифметического блока через второй вход второго элемента НЕРАВНОЗНАЧНОСТЬ и первый вход второго элемента совпадения соединен с вторым информационным входом второго мультиплексора, выход второго элемента НЕРАВНОЗНАЧНОСТЬ соединен с вторым управляющим входом первого мультиплексора, первый управляющий вход арифметического блока соединен с вторым входом первого элемента совпадения и через инвертор - с управляющим входом первого мультиплексора и с вторым входом второго элемента совпадения, второй, третий и четвертый управляющие входы каждого арифметического блока соединены с управляющими входами соответственно второго, третьего и четвертого м ультиплексоров. Введение в устройства (n-1)-каналов с арифметическим блоком и двух элементов .задержки в каждом, а в каждый арифметический блок второго элемента НЕРАВНОЗНАЧНОСТЬ, инвертора и двух мультиплексоров с соответствующими связями позволяет расширить класс решаемых задач за счет возможности одновременного как ориентированного, так и неориентированного дифференцирования булевой функции по различным переменным, а также сформировать с минимально возможной задержкой, по отношению к исходному вектору истинности булевой функции длины 2n, за 2n-1 тактов результирующее значение булева дифференциала за счет использования параллельно-последовательной структуры устройства вместо последовательной. На фиг.1 показана структурная схема устройства для вычисления булевы х ди фференциалов; на фиг.2 принципиальная схема арифметического блока. Устройство для вычисления булевых дифференциалов содержит счетчик 1, элементы 21…2.n, 31...3n задержки, блоки 41...4n арифметические, шины 51...5n, 61...6 n, 71..7n управления. Арифметический блок 4i (і=1, n ) состоит из элементов 8, 9 НЕРАВНОЗНАЧНОСТЬ, инвертора 10, элементов 11,12 совпадения, мультиплексоров 13-16, а также содержит информационные и управляющие входы 17-19, 20-23 .соответственно, выход 24, причем разрядные выходы счетчика 1 подключены к управляющим входам 20 арифметических блоков 4i управляющие входы 21, 22, 23 арифметических блоков 4, связаны соответственно с выводами 5i, 6i, 7i, шин управления 5-7. В каждом из n каналов устройства вы ход элементов 2i задержки соединен через соответствующий элемент 3i задержки с информационным входом 17 арифметического блока 4, и непосредственно с информационным входом 18 арифметического блока 4i. Вход элемента 2, задержки подключен к информационному входу 19 арифметического блока 4i, выход 24 которого связан с входом следующего канала. Вход первого канала служит входом устройства, выходом которого является выход 24 последнего канала. Информационный вход 17 арифметического блока 4i через первый вход элемента 8 НЕРАВНОЗН АЧНОСТЬ соединен с первым информационным входом мультиплексора 13 и первым входом элемента совпадения 11, выход которого связан с первым информационным входом мультиплексора 14, Выходы мультиплексоров 13, 14, подключены соответственно к первому и второму информационным входам мультиплексора 15. Информационный вход 18 арифметического блока 4i соединен с вторым входом элемента 8 НЕРАВНОЗНАЧНОСТЬ, с первым входом элемента 9 НЕРАВНОЗНАЧНОСТЬ и с первым информационным входом мультиплексора 16. Выход мультиплексора 15 связан с вторым информационным входом мультиплексора 16, выход которого является выходом арифметического блока 4i. Информационный вход 19 арифметического блока 4i через второй вход элемента 9 НЕРАВНОЗНАЧНОСТЬ и первый вход элемента 12 совпадения подключен к второму информационному входу мультиплексора 14. Выход элемента 9 НЕРАВНОЗНАЧНОСТЬ соединен с вторым управляющим входом мультиплексора 13. Управляющий вход 20 арифметического блока 4i соединен с вторым входом элемента 11 совпадения и через инвертор 10 - с управляющим входом мультиплексора 13 и с вторым входом элемента 12 совпадения. Управляющие входы 21-23 арифметического блока 4i соединены с управляющими входами мультиплексоров 14-16 соответственно. Разрядность (число каналов) n счетчика 1 совпадает с числом переменных дифференцируемой булевой функции. Блоки 21 и 31 задержки первого канала задерживают на такт вектор истинности булевой функции, поступающий на вход. Блоки задержки в каждом последующем канале осуществляют задержку в два раза большую чем в предыдущем канале. Шины управления 5-7 используются для задания различных режимов работы. Если на выводе 5| шины 5 присутствует логический нуль, что дифференцирование булевой функции f(xn,...,xi) по переменной xi не производится. При этом величины потенциалов на выводах 6i и 7i не оказывают влияния на функционирование устройства. В случае подачи "1" на вывод 5i характер дифференцирования указывается с помощью сигнала на выводе 6i: "0" соответствует неориентированному, а "1" - ориентированному дифференцированию. Наличие логического нуля на выводе 6i исключает влияние потенциала с вывода 7 i на работу устройства. При поступлении "1" на вывод 6i дифференцирование, ориентированное на увеличение (уменьшение), обеспечивается благодаря "1" ("0") на выводе 7 i. В соответствии с определением булевым дифференциалом (разностью) логической функции f(xn.....x1) по переменной Хi называется булевая функция df(xn .....х1) вида: df(xn.....х1) = f(xn.....xi....x1) +f(xn...xi..х1), то есть, для вычисления функции df(xn .....х1) необходимо определить значение функции f на наборе и сложить по mod 2 со значением исходной функции на рассматриваемом наборе. При n=1 булево дифференцирование описывается матричным соотношением: Булевым дифференциалом по переменной xi, ориентированным на увеличение df (xn.....х1) (уменьшение df (xn.....х1), называется логическая функция, равная 1 тогда и только тогда, когда f(xn .....х1) изменяется при изменении xi из 0 в 1 (из 1 в 0), При n=1 булево дифференцирование, ориентированное на увеличение, задается равенством: Согласно определению [Ланкастер П. Теория матриц. М., Наука, 1978, с.272 (с,235)] прямое произведение матриц А= |aej| І иВ= = II b ej II в записи А В есть блочная матрица вида: В случае произвольного n с помощью n-кратного прямого произведения матриц из равенств (1)-(3), а также единичной диагональной матрицы задается булево дифференцирование, выполняемое по различным переменным неориентированно, сориентировано на увеличение или на уменьшение. Так, дифференцирование логической функции f(x2,x1), неориентированное по переменной х2 и ориентированное на увеличение по x1, задается матрицей: Дифференцирование соответствует матрица: булевой функции, ориентированное на уменьшение по переменной х2, Таким образом, если в n-кратном прямом произведении на 1-й позиции (нумерация справа налево) имеет место матрица (1), (2) или{3), то булева функция дифференцируется по переменной xi неориентированно, ориентированно на увеличение или ориентированно на уменьшение соответственно. В случае наличия в указанной позиции матрицы (4) дифференцирование по переменной xi не производится. Прямое n-кратное произведение может быть представлено обычным произведением n матриц той же размерности [Трахтман A.M., Тра хтман В.А. Основы теории, дискретных сигналов на конечных интервалах. М., Сов. радио, 1975, с.208 (с. 17)1, Так, матрица Каждому из n сомножителей соответствует преобразование логической функции по определенной переменной. Так, дифференцирование булевой функции по переменной xi осуществляется (или не осуществляется) і-й матрицей (нумерация справа налево), вид которой задает ориентацию дифференциала (либо ее отсутствие). Предлагаемое устройство реализует алгоритм последовательного умножения вектора логической функции на n матриц-сомножителей, причем і-й канал обеспечивает умножение на і-го из n матриц (нумерация слева направо). Устройство позволяет также дифференцировать логические функции и тогда, когда их векторы истинности длины 2n подаются на вход непосредственно друг за другом. Последовательность из нулей и единиц значений булева дифференциала вырабатывается с задержкой на 2n1 тактов по отношению к вектору истинности, т.е. первое значение формируется в том же такте, в котором на вход поступает последняя компонента исходного вектора. Устройство для вычисления булевых дифференциалов функционирует следующим образом. Пример 1. Пусть n=2, а дифференцирование не ориентировано по переменной х и ориентировано на увеличение по х, т.е. устройство реализует умножение вектора булевой функции f(x2, x1) на матрицу (5). В исходном состоянии на выводы 5 1, 52, 61 и 71 подается "1", на выводе 62 присутствует "0", а величина потенциала на выводе 72 не влияет на функционирование устройства. Тогда в арифметическом блоке 41 выход элемента 12 совпадения через вторые информационные входы мультиплексоров 14, 15, 16 подключаются к выходу 24. В арифметическом блоке 4 2 выходы элементов 8 и 9 НЕРАВНОЗНАЧНОСТЬ соединяются с выходом 24 через первый и второй информационные входы мультиплексора 1-3, первый информационный вход мультиплексора 15 и второй информационный вход мультиплексора 16. В первом такте счетчик 1 находится в нулевом состоянии , на входе устройства присутствует последнее значение f3 булевой функции двух переменных, блоки задержки 21 и 31 хранят соответственно f2 и f1, а блок задержки 22 содержит "0" в переменном своем разряде и - по втором. В первом и втором разрядах блока задержки 32 содержатся результаты обработки вектора истинности предыдущей булевой функции - 0 и f'2 f’3 соответственно. Значения булевой функции f3 с входа устройства f2 с вы хода блока 21 задержки суммируются по mod 2 элементом 9 НЕРАВНОЗНАЧНОСТЬ. Благодаря наличию “1” на втором информационном входе элемента 12 совпадения величина f2 f3 поступает через вторые информационные входы мультиплексоров 14-16 на выход 24 арифметического блока 41. Результаты f2 f3 с входа арифметического блока 42 и f0 f1 с выхода блока задержки 22 суммируются по mod 2 элементом 9 НЕРАВНОЗНАЧНОСТЬ. Поскольку на управляющем входе 20 арифметического блока 42 имеет место "0". то с выхода инвертора 10 на управляющий вход мультиплексора 13 поступает "1", что обеспечивает подключение выхода элемента 9 НЕРАВНОЗНАЧНОСТЬ к выходу мультиплексора 13. В результате величина через мультиплексоры 13-16 арифметического блока 4 поступает на выход устройства в целом. По окончанию такта блоки задержки 21 и 31 хранят f3 и f2 соответственно. В первом и втором разрядах блока задержки 22 имеем f2 f3 и 0, а в первом и втором разрядах блока задержки . ~ f Во втором такте первое значение 0 новой булевой функции поступает на вход устройства для вычисления булевы х ди фференциалов. Логическая единица с выхода младшего разряда счетчика 1 подается на управляющий вход 20 арифметического блока 41 и инвертируется инвертором 10. "0" через второй вход элемента 12 совпадения и вторые информационные входы мультиплексоров 14-16 поступает на выход 24 арифметического блока 41. В арифметическом блоке 42 логический ноль с информационного входа 19 суммируется по mod 2 элементом 9 НЕРАВНОЗНАЧНОСТЬ с "0", имеющим место на информационном входе 18. Благодаря наличию логического нуля на управляющем входе 20 полученный результат - "0" поступает через второй информационный вход мультиплексора 13, первый информационный вход мультиплексора 15 и второй информационный вход мультиплексора 16 на выход устройства. Таким образом, на выходе устройства для вычисления булевых дифференциалов имеем вектор - результата умножения вектора истинности на матрицу (5). Пример 2. Пусть n=2, а дифференцирование будевой функции производится по переменной х2, причем ориентировано на уменьшение, т.е. устройство реализует умножение вектора истинности на матрицу (6). На выводы 52. 62 подается "1", на выходах 51 и 72 присутствует "0", а величины потенциалов на выводах 61 и 71 не влияют на функционирование устройства. Тогда в арифметическом блоке 41 информационный вход 18 через первый информационный вход мультиплексора 16 подключается к выходу 24, благодаря чему дифференцирование по переменной х1 не производится. В арифметическом блоке 42 выход элемента 11 совпадения соединяется с выходом 24 через первый информационный вход мультиплексора 14, вторые информационные входы мультиплексоров 15 и 16. В первом такте счетчик 1 находится в нулевом состоянии , на входе устройства присутствует последнее значение f3, булевой функции, блоки задержки 21 и 31 хранят соответственно f2 и f1, а блок задержки 22 содержит f1 у в первом своем разряде и f0 - во втором. В первом и втором разрядах блока задержки 3 имеем компоненты вектора истинности и предыдущей булевой функции – f’3 и f’2 соответственно. Величина f2 с выхода блока задержки 21 через информационный вход 18 и мультиплексор 16 арифметического блока 41 подается на выход 24. Логический ноль с разрядного выхода счетчика 1 через управляющий вход 20 арифметического блока 42, второй вход элемента 11 совпадения, первый информационный вход мультиплексора 14, вторые информационные входы мультиплексоров 15, 16 поступают на выход устройства. По окончании такта блоки задержки 21 и 31 хранят f3 и f2 соответственно. В первом и втором разрядах блока задержки 22 имеет f2 и f1, а в первом и втором разрядах блока задержки 32 – f0 и f'3. ~ f Во втором такте первого значения 0 новой булевой функции поступает на вход устройства. Значение f3 с выхода блока 2 задержки через информационный вход 18 и мультиплексор 16 арифметического блока 4 подается на выход 24. Логический ноль с соответствующего разрядного выхода счетчика 1 через управляющий вход 20 арифметического блока 42, второй вход элемента 11 совпадения, первый информационный вход мультиплексора 14, вторые информационные входы мультиплексоров 15 и 16 поступает на выход устройства. ~ f По завершению второго такта величины 0 и f 3 засылаются в блоки задержки 21 и 31 соответственно. Блок задержки 22 содержит f3 в первом своем разряде и f2 во втором. В первом и втором разрядах блока задержки 32 имеем f1, и f 0 ~ f В третьем такте счетчик 1 находится в состоянии 10, а на входе устройства присутствует значение 1 новой булевой функции. Величина f0 с выхода блока задержки 21 через информационный вход 18 и первый информационный вход м ультиплексора 16 арифметического блока 41 подается на выход 24. В арифметическом блоке 42 величины f0 и f2 с ин формационных входов 17 и 18 суммируются по mod 2 с помощью элемента 8 НЕРАВНОЗНАЧНОСТЬ. Благодаря наличию "1" на втором информационном входе элемента 11 совпадения величина f0 f2 поступает через мультиплексор 14-16 на выход 24 устройства. ~ f При переходе к четвертому такту в блоки задержки 21 и 31 засылаются величины f1 и 0 соответственно. В ~ f первом разряде блока задержки 22 имеем 0 , а во втором разряде f3. В первом и втором разрядах блока задержки 32 содержатся величины f2 и f 1 соответственно. В четвертом такте на входе устройства для вычисления булевых дифференциалов присутствует ~ ~ f f значение 2 новой логической функции, а счетчик 1 содержит (11). Величина 1 с выхода блока задержки 21 через информационный вход 18 и первый информационный вход мультиплексора 16 арифметического блока 41 подается на выход 24. В арифметическом блоке 4 2 величина f1 с информационного входа 17 суммируется по mod 2 элементом НЕРАВНОЗНАЧНОСТЬ со значением f3, имеющим место на информационном входе 18. Благодаря наличию логической единицы на управляющем входе 20 полученный результат поступает через мультиплексор 14-16 на выход 24 устройства. Таким образом, на выходе устройства для вычисления булевых дифференциалов имеем вектор - результат умножения вектора истинности на матрицу (6).