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

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

Иллюстрации

Показать все

Реферат

 

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

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

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

РЕСПУБЛИК (19) (И) (51)4 (06 F 7

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

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

Н A ВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) 1170446 (21) 3967680/24-24 (22) 02.09.85 (46) 07.03.87. Бюл. ¹ 9 (72) О.И.Сидоренко (53) 681.3 (088.8) (56) Авторское свидетельство СССР № 1170446, кл. С 06 Р 7/00, 1984. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ

СВОЙСТВ ПОЛНОТЫ ЛОГИЧЕСКИХ ФУНКЦИЙ (57) Изобретение относится к вычислительной технике, может быть использовано для распознавания функциональной полноты систем логических функций при проектировании цифровых устройств, а также для контроля и поис5383

129. ка неисправностей в устройствах путем анализа логических свойств булевых функций, описывающих временные диаграммы их функционирования, и является усовершенствованием изобретения по авт.св. N- 1!70446. Целью изобретения является повышение достоверности контроля входной информации путем дополнительного определения коэффициентов немонотонности, нелинейности и несамодвойственности (коэффициентов логической сигнатуры).

Устройство содержит RS-триггер l, оперативные запоминающие блоки 2 и

3, триггеры 4 со счетным входом, коммутатор 5 триггерных сигналов, формирователи 6 и 7 импульсов, О-триггер 8, регистр 9 сдвига, элементы

И 10 и ll, элемент РАВНОЗНАЧНОСТЬ 12, элемент И 13, элемент РАВНОЗНАЧНОСТЬ

14, элемент И 15, регистр 16 памяти, двоичный счетчик 17, ждущий генератор 18 тактов, элемент 19 задержки, RS"òðèããåðû 20 и 21, шину 22 логической "1", вход 23 ввода, вход 24 сброса, выходы 25 — 29 информации о наборе свойств полноты, выход 30 сигнала окончания работы, вход 31 запуска „элемент 2 зад< ря к н, 3 l JEMf í ò

ИЛИ 33, элементы И 34 — 39, элемент

ИЛИ 40, элементы И 41 и 42, коммутаторы 43 — 45 каналов, элемент 46 задержки, двоичные счетчики 47 и 48, информационный вход 49, вход 50 синхронизации, выход 51 информации о ранге, элемент ИЛИ 5?, двоичные счетчики 53 и 54, накапливающий сумматор

55, выход 56 информации о коэффициенте несамодвойственности, выход 57 информации о коэффициенте немонотонности и выход 58 информации о коэффициенте нелинейности. Предлагаемое устройство различает двоичные последовательности с одинаковым рангом, но отличающиеся друг от друга числом пар соседних наборов соответствующих булевых функций, на которых не выполняется свойство монотонности (коэффициентом немонотонности) и свойство линейности (коэффициентом нелинейности), а также числом пар противоположных наборов, на которых не выполняется свойство самодвойственности (коэффициентом несамодвойственности). l ил.

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

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

На чертеже представлена схема устройства.

Устройство содержит RS-триггер 1, оперативные запоминающие блоки 2 и 3, триггеры 4 со счетным входом, коммутатор 5 триггерных сигналов, формирователи 6 и 7 импульсов, D-триггер

8, регистр 9 сдвига, элементы И 10 и ll, элемент РАВНОЗНАЧНОСТЬ 12, элемент И 13, элемент РАВНОЗНАЧНОСТЬ 14, элемент И 15, регистр 16 памяти, двоичный счетчик 17, ждущий генератор 18 тактов, элемент 19 задержки, RS-триг10 геры 20 и 21, шину 22 логической 1, вход 23 ввода, вход 24 сброса, выходы 25-29 информации о наборе свойств полноты, выход 30 сигнала окончания работы,:вход 31 запуска, элемент 32 задержки, элемент ИЛИ 33, элементы И 34 — 39, элемент ИЛИ 40,. элементы И 41 и 42, коммутаторы 43—

45 каналов, элемент 46 задержки, 2О двоичные счетчики 47 и 48, информационный вход 49, вход 50 синхронизации, выход 51 информации о ранге, элемент ИЛИ 52,, двоичные счетчики

53 и 54, накапливающий сумматор 55, 3 12953 выход 56 информации о коэффициенте несамодвойственности, выход 57 информации о. коэффициенте немонотонности и выход 58 информации о коэффициенте нелинейности. 5

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

Перед началом работы по входу 24 сброса подается импульс сброса, который устанавливает в нулевое состоя- 10 ние триггеры 1,4 и 8, регистры 9 и

16, двоичные счетчики 17, 47, 48, 53 и 54 и накапливающий сумматор 55.

Одновременно с этим ждущий генератор 18 тактов устанавливается в первое состояние, при котором тактовые импульсы с его выхода отсутствуют.

RS-триггеры 20 и 21 также переводятся в первые (единичные) состояния, торых подготавливается выдача тактовых импульсов с выхода элемента

И 37 для определения свойств несохранения констант, а с выхода элементов

И 38 — для определения свойства несамодвойственности. Кроме того, с

25 единичного выхода RS-триггера 21 выдается потенциальный сигнал управления на коммутатор 5 триггерных сигналов.

Коммутатор 5 триггерных сигналов представЛяет собой комбинационную схему. его i-й разряд реализует на своих выходах следующие логические функции:

К;„= Q, (CV9; )V Ц (С V9 ); (1<)Cu где f ° — логическая функция первого

1 IH выхода, соединенного с i-м информационным входом вто- 40 рой группы коммутатора 45 каналов;

f< „, — логическая функция второго выхода соединенного со счетным входом L,i+1)-го счетного триггера 4; прямой (неинвертирующий) выход i-ro счетного триггера 4; инверсный выход 1-Fo счетного триггера 4;

С вЂ” управляющий сигнал с выхода RS-триггера 21;

Ф; — управляющий сигнал с i-ro выхода регистра 9 сдвига.

Так как регистр сдвига после сброса обнуляется, то сигналы коммутации счетных триггеров 4 с его выходов отсутствуют, поэтому ио входам установки нуля счетные триггеры 4 разблокируются, а счетный вход i-го счетного триггера через коммутатор. 5 триггерных сигналов оказывается подключенным к выходу предыдущего (i-1)-го триггера, образуя п-разрядный двоичный счетчик, ири этом к информационным входам второй группы коммутатора 45 каналов подключаются инверсные выходы счетных триггеров 4, на информационных входах второй группы коммутатора 44 каналов появляется двоичный код набора-."Все О", а на информационных входах второй группы коммутатора 45 каналов — код набора "Все 1".

С подачей по входу 31 импульса запуска устройства срабатывает

RS-триггер l и на его выходе появляется потенциал логической "1, иереключающий оперативные запоминающие блоки 2 и 3 в режим записи информации, поступающей на вход 49 у тройства через открывшийся элемент И 4! на информационные входы оперативных запоминающих блоков 2 и 3, при этом коммутатор 43 каналов переключается в состояние, когда синхроимпульсы, поступающие по входу 50 устройства, проходят на его выход и далее на входы разрешения работы оперативных saпоминающих блоков 2 и 3 и через элемент 46 задержки на вход и-разрядного двоичного счетчика 47, который служит счетчиком адреса. Адресная информация с выходов двоичного счетчика 47 поступает на информационные входы первой группы коммутаторов 44 и 45 каналов, которые после сигнала запуска устройства оказываются подключенными к адресным входам обоих оперативных запоминающих блоков 2 и

3. В них, таким образом, записывается по одним и тем же адресам одна и та ..ке информация, причем первый бит входной двоичной последовательности записывается по адресу "Все О . Одновременно происходит подсчет количества единиц в анализируемой двоичной последовательности, поступающей по входу 49 устройства, с помощью (n+1)-разрядногс двоичного счетчика

48, на счетный вход которого пасгупает информация, образующаяся на выходе элемента И 42 в результате стробирования входной информации с выхода элемент И 41 синхроимпульсами с выхода коммутатора 43 каналов.

129

С подачей по входу 23 ввода импульса ввода RS-триггер 1 переключается в нулевое состояние, при котором закрываются элементы И 41 и

42, а бба оперативных запоминающих блока переводятся в режим считывания записанной информации. При этом запускается ждущий генератор 18 тактов и первый же импульс с его выхода через подготовленные элементы И 37 и

38 поступает на входы элементов И 10, 11 и 35 соответственно. Кроме того, коммутаторы 44 и 45 каналов переклю- чаются так, что к их выходам подключаются информационные входы второй группы, т.е. адресные входы блока 2 переключаются к счетным триггерам 4, адресные входы блока 3 — к соответствующим выходам коммутатора 5 триггерных сигналов, а через коммутатор

43 каналов на входы разрешения работы блоков 2 и 3 начинают поступать импульсы с выхода ждущего генератора

18 тактов.

Элемент И 10 является определителем свойства несохранения константы нуль. К моменту поступления первого тактового импульса на один из его входов с выхода элемента И 37 на другом его входе с выхода блока 2 оказывается подключенным значение булевой функции на нулевом наборе, поэтому, если анализируемая логическая функция не сохраняет константу нуль, то тактовый импульс проходит на вы- ход элемента И 10 и переводит первый триггер регистра !б памяти в единичное состояние, фиксируемое на выходе 25 устройства.

Аналогично элемент И 11 является определителем свойства несохранения константы единица. Один из его входов подключается к инверсному выходу блока 3, поэтому к моменту поступления первого тактового импульса с выхода элемента И 37 на этом входе оказывается инверсное значение анализируемой функции на наборе "Все 1", Если анализируемая логическая функция не сохраняет константу единица, то тактовый импульс проходит на выход элемента И 11 и устанавливает второй триггер регистра 16 в единичное состояние, фиксируемое на выходе

26 устройства.

Первый после ввода тактовый импульс, пройдя элемент !9 задержки, переводит RS-триггер 20 во второе

5383 6 (нулевое) состояние, при котором запрещается прохождение тактовых им- . пульсов на выход элемента И 37,и поступает на счетный вход первого триггера двоичного счетчика, образованного из отдельных счетных триггеров 4 с помощью коммутатора 5 триггерных сигналов. Укаэанный счетчик начинает считать поступающие с эле10 мента 19 задержки тактовые импульсы, при этом к адресным входам блока

2 подключаются через коммутатор 44 каналов прямые выходы счетных триггеров 4, а к адресным входам блока 3инверсные выходы этих триггеров че рез коммутатор 45 каналов, Таким образом, на выходах элемента РАВНОЗНАЧНОСТЬ 12, являющегося определителем свойства несамодвойственности, соединенных с прямыми выходами обоих оперативных запоминающих блоков, в одни и те же моменты времени значения анализируемой лЬгической функции оказываются на противоположных наборах. В случае, если анализируемая функция является несамодвойственной, то хотя бы на одной паре противоположных наборов значе30 ния функции оказываются одинаковыми.

При этом тактовые импульсы с выхода элемента И 38, опережающие моменты изменения состояний триггеров 4 на величину, определяемую элементом 19 задержки, проходят на выход элемента

35 H 35 и устанавливают третий триггер регистра 16 памяти в единичное состояние, фиксируемое на выходе 27 устройства. Кроме того, импульсы с выхода элемента И 35 попадают на счет40 ный вход двоичного счетчика 53 в количестве, соотве.тствующем коэффициенту несамодвойственности, результат определения которого выдается на выход 56 устройства.

После перебора 2 состояний на выходе и-го счетного триггера появляется отрицательный перепад напряжения„ из которого формирователь 7 фор5 мирует управляющий импульс. Последний переводит RS-триггер 21 во второе (нулевое}. состояние, при котором тактовые импульсы проходят на выход элемента И 39, соединенного с элементами И 13 и 36. Кроме того, импульс с выхода формирователя 7 записывает

"1" в D-триггер 8 и в первый разряд регистра 9 сдвига, при этом на выходе первого разряда регистра 9 сдвига

7 12953 появляется сигнал Р< коммутации первого счетного триггера 4, па которому указанный триггер удерживается в нулевом состоянии. Задержанные тактовые импульсы через первый разряд каммута- 5 тора 5 триггерных сигналов проходят в обход первого счетного триггера на счетный вход второго триггера, а к первому адресному входу блока 3 через коммутатор 45 каналов оказывается подключенным инверсный выход счетного триггера.

Укороченный таким образом на один первый разряд двоичный счетчик, образованный иэ счетных триггеров 4 и разрядов коммутатора 5 триггерных сигналов, продолжает считать тактовые импульсы с выхода элемента 19 задержки, при этом блохи 2 и 3 поочередно подключают к первым входам элемента

И 13 и элемента РАВНОЗНАЧНОСТЬ 14 значения анализируемой логической функции на всех парах склеивающихся по первой переменной наборов.

Элемент И 13 является определителем свойства немонотонности. Его второй вход соединяется с инверсным выходом блока 3, поэтому в один и тот же момент времени на первых двух входах элемента И 13 оказываются значения анализируемой функции на двух склеивающихся наборах, причем значе- . ние функции на большем из них оказывается проинвертированным. Таким обт 35 разом, если логическая функция является немонотонной, та хотя .бы на одной паре склеивающихся яаборов значение функции на меньшем иэ иих больше, чем на боль- <О шем, при этом на первых двух входах элемента И 13 оказывается потенциал логической "1", I тактовые импульсы, поступающие на его третий вход с выхода элемента

И 39, проходят на выход элемента

И 13 и устанавливают четвертый триггер регистра 16 памяти в единичное состояние, фиксируемое на выходе 28 устройства. Кроме того, импульсы с выхода элемента И 13 проходят на счетный вход двоичного счетчика 54 в количестве, соответствующем коэффициенту немонатонности, результат определения которого выдается на выход 57 устройства..

Одновременно с определением свойства неманотоннасти осуществляется определение свойства нелинейности..

Определителем свойства нелинейности является элемент РАВНОЗНАЧНОСТЬ 14, входы которого подключаются к прямым выходам блоков 2 и 3, а выход соединяется с одним из входов элемента

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

17. В том случае, если ни на одной паре или на всех 2 " парах склеивающихся па первой переменной набо-, ров функция принимает одинаковые значения, с выхода элемента И Зб на счетный вход (n-1) †разрядно двоичного счетчика 17 не поступит соответственно ни одного или поступит ровно 2 импульсов, в результате указанный счетчик будет обнулен. и на вход элемента ИЛИ 33, падключе:."нога своими входами к выходам всех разрядов счетчика 17, будет сформирован потенциал логического "О". После перебора 2 состояний на выходе

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

7 перебрасывает триггер первого разряда регистра 9 сдвига в нулевое состояние, обусловленное единичным состоянием D-триггера 8, а во второй разряд регистра записывается "1", обусловленная единичным состоянием триггера первого разряда регистра 9 сдвига. Таким образом, с выхода второго разряда регистра 9 сдвига появляется сигнал 6 коммутации второго счетноготриггера 4, который действует ачалагично сигналу Ч „ т.е. удерживает в нулевом состоянии второй счетный триггер 4, сигнал на счетный вход третьего триггера 4 поступает в обход второго триггера с выхода перваI га счетного триггера, а на второй адресный вход блока 3 через коммутатор 45 каналов подключается инверсный выход второго счетного триггера

4. Импульсы с выхода формирователя 7, пройдя элемент ИЛИ 40, не проходят далее на выход элемента И 34 и не устанавливают пятый триггер регистра

16 памяти в единичное состояние.

9 12

В любом другом случае, когда число пар склеивающихся наборов,,на которых функция принимает одинаковые

h- значения, отличается от чисел 0 и 2, на выходе элемента ИЛИ 33 формируется потенциал логической "1", .разрешающий прохождение импульса с выхода элемента ИЛИ 40 на вход установки единицы пятого триггера регистра 16 памяти, который устанавливается в единичное состояние, фиксируемое на выходе 29 устройства и свидетельствующее о нелинейности анализируемой логической функции. Пройдя элемент

32 задержки, импульсы с выхода элемента ИЛИ 40 производят перепись содержимого счетчика 17 в накапливающий сумматор 55 и по заднему фронту уста— навливают в начальное нулевое состоя— ние счетчик 17, подготавливая его к работе по следующей переменной. С выходов сумматора 55 информация о коэффициенте нелинейности передается на выход 58 устройства.

Аналогично происходит работа устройства вплоть до коммутации и-го счетного триггера 4, при этом в регистре 9 сдвига через каждые (2" " ) тактов происходит сдвиг логической

"1" в сторону старших разрядов и заполнение младших разрядов логическими "0".

После того, как образованный из счетных триггеров 4 двоичный счетчик

I просчитает 2" состояний с момента коммутации и-го триггера, на выходе (n-1)-ro счетного триггера образуется отрицательный перепад напряжения, который после формирования с помощью формирователя 6 импульсов проходит через подготовленный элемент И 15 и элемент ИЛИ 40 на вход элемента И 34, а "через элемент 32 задержки — на вход переписи накапливающего сумматора 55, на вход установки нуля счетчика 17, а также на стоп-вход генератора 18 тактов и останавливает его, при этом на выходе 30 появляется импульс окончания работы устройства, сигнализируя о том, что полученные значения логической сигнатуры анализируемой логической функции и ее коэффициентов могут быть считаны из регистра )6 памяти, счетчиков 48, 25

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

Устройство для определения свойств полноты логических функций по авт.св. N- 1170446, о т л и ч а ю— щ е е с я тем, что, с целью повьппения достоверности контроля входной информации, устройство содержит четвертый и пятый двоичные счетчики и накапливающий сумматор, причем счетный вход четвертого счетчика соединен с выходом девятого элемента И, счетный вход пятого счетчика соединен с выходом шестого элемен40 та И, информационные входы накапливающего сумматора. подключены к соотведствующим выходам первого двоично—

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

95383 10

53 и 54 и накапливающего сумматора 55.

Предлагаемое устройство характеризуется более высокой достоверностью

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

20 противоположных наборов, на которых не выполняется свойство самодвойственности (коэффициентом несамодвойстненности), ВНИИПИ Заказ 618/55 Тираж 673 Подписное

Произв.-полигр. пр-тие, r. Ужгород, ул. Проектная, 4