Устройство для подсчета числа единиц Советский патент 1991 года по МПК G06F11/28 G06F7/50 

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

Цель изобретения - повышение достоверности контроля устройства для подсчета числа единиц.

На чертеже представлена схема устройства для подсчета числа единиц при п 4 (п - разрядность входного булева вектора X (xiхп), в котором осуществляется подсчет числа логических единиц).

Устройство содержит элементы 1i1п

равнозначности пятой группы, элементы

2i2з равнозначности шестой группы, элементы ИЛИ 3i34, элемент НЕ 4, элементы

5т54 равнозначности первой группы, элементы б1,...,6б равнозначности второй группы, элементы 7i7в равнозначности

третьей группы, элементы 81,...,8з равнозначности четвертой группы, информационные входы 9i9i. управляющие входы 10 и

11 и выходы 12i....,12s.

Устройство для подсчета числа единиц работает в рабочем режиме и режиме контроля.

В рабочем режиме на информационные входы 9i94 подаются компоненты двоичного вектора xiХ4 соответственно, на упсь о

vj

О 00

со

равляющий вход 10 - сигнал Ui 0, на управляющий вход 11 -сигнал 1)2 0. При этом элементы 1114 равнозначности переводятся в режим инверторов, элементы 5i, 5/j, 61.6 а, 65, бе, 7i, 7в, 8i, 82, 83 равнозначности - в режим элементов И, элементы 52, 5з,

6з. 64, 727 равнозначности - в режим

элементов ИЛИ-НЕ. На выходэх 12i12s

устройства реализуются фундаментальные (элементарные) симметрические булевы

функции (ф.с.б.ф) соответственно FIFs,

где

Fl(xi, Х2, ХЗ, Х4) F/f 1(Х1, Х2, ХЗ, Х4),

1 15.

Заметим, что ф.с.б.ф.

Г1, еслих 4-хг+....+х„ а

Рч (x1, х2хп

О, если х., х д+....+х„ f a где 0 а п

Сигнал логической единицы формируется на выходе 12| лишь в том случае, если вектор входных двоичных переменных X (xi, X2. хз, х/)) содержит ровно (i-1) единичных компонент.

В режим контроля устройство для подсчета числа единиц переводится подачей на управляющий вход 10 сигнала Ui 1.В этом режиме устройство независимо от значения входного вектора проверяется четырьмя фиксированными тест-наборами, которые позволяют обнаружить любую константную неисправность произвольной кратности на входах-выходах элементов 5, 6, 7, 8, 1 равнозначности групп с первой по пятую.

Проверяющие тест-наборы формируются следующим образом.

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

С (Ui, U2. XI. Х2. ХЗ, Х4. Х5. Х6,...,ХП),

где Ui- U2 - сигналы на первом и втором управляющих входах 10 и 11 устройства;

хк - сигнал на К-м информационном входе 9 устройства (К 1. 2п).

Тогда проверяющими тест-наборами являются вектора:

Ci - (1, 0, 0, 0, 1. О, 1. Оn mod 2);

Са-(1,1, О, О, 0,1.0.1(1-n mod 2));

Сэ-(1,0, 1.1, 1,0, 1,0n mod 2);

С4-(1,1, 1,1, 0.1.0,1(1-n mod 2)).

n mod 2 1. если п - нечетное, в противном случае n mod 2 0.

Таким образом, четыре проверяющих тест-набора представляют собой комбинацию двух кортежей сигналов Ki (0. О,) и К2 - (1,1) на вторых и третьих входах элементов 5 равнозначности первой группы и двух

п-компонентных векторов vi (О,1,0,1п

mod 2) и vz - (1. О, 1, 0(1-n mod 2)),

первая компонента которых подается в ре0

5

0

5

0

жиме контроля на первые входы элементов 5 равнозначности первой группы, а w-я (w 2, 3п-1) - на первые и вторые входы элементов равнозначности w-й линейки; п-я компонента - на первые входы элементов равнозначности n-й линейки.

Вектор-реакция Re (г , rfГп 4-1)

устройства на тест-набор Се (е 1, 2, 3, 4) при отсутствии неисправностей имеет вид

Re (ae, be, beЬе.Эе)

гдеаеЈ {0.1}; be €{0,1}

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

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

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

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

Кроме того устройство обладает однородной и регулярной структурой, построено на логических элементах с ограниченным числом входов.

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

Устройство для подсчета числа единиц, содержащее п (п - разрядность входного двоичного слова) элементов ИЛИ и элемент НЕ, о т л и ч а ю щ е е с я тем, что., с целью повышения достоверности контроля, содержит (n-t-2) групп элементов равнозначности.

i-я из которых (I 1п-1) содержит 2 (i+1)

элементов равнозначности, n-я группа содержит (п-1) элементов равнозначности, (п+1)-я группа содержит (п-1) элементов равнозначности, (п+2)-я группа содержит (п-1) элементов равнозначности, первый управляющий вход устройства соединен с первым входом j-ro 0 1... ,п) элемента равнозначности (п+1)-й группы и входом элемента НЕ, выход которого соединен с первым входом 1-го элемента равнозначности (п+2)-й группы и первым входом j-ro элемента ИЛИ, выход 1-го элемента ИЛИ соединен с первым входом t-ro элемента равнозначности 1-й группы и первым входом (2i - р + t + 2)-го элемента равнозначности i-й группы (t

1р; р 2 -1 mod 2, если п-четное, р 1

+ I mod 2, если п - нечетное), выход п-го элемента ИЛИ соединен с первым входом 1-го элемента равнозначности л-й группы, второй управляющий вход устройства соединен с вторым входом первого элемента ИЛИ, вторым входом первого элемента рав5

0

0

ноэначности (п+2)-й группы и первыми входами второго и третьего элементов равнозначности первой группы, выход К-го (К

1п-2) элемента равнозначности (п+2)-й

группы соединен с вторым входом (КН)-го элемента равнозначности (п+2)-й группы, вторым ьходом (К+1)-го элемента ИЛИ и первым входом m-ro элемента равнозначности (К+1)-й группы (т --- v + 1, v + 2,. mod .,2K 4 4 - v; v 2 - (К + 1) 2), если п - четное, v 1 + (К+1) mod 2, если п - нечетное); j-й информационный вход устройства соединен с вторым входом j-ro элемента равнозначности {п+1)-й группы, выход первого элемента равнозначности (п+1)-й группы соединен с вторым входом q-ro (q 1, 2) эле- мента равнозначности первой группы,а его второй вход соединен с вторым входом (q+2)-ro элемента равнозначности первой группы, выход второго элемента равнозначности (п-Н)-й группы соединен с третьим входом (2n mod 2+q)-ro элемента равнозначности первой группы,а его второй вход соединен с третьим входом (q + 2 (1 - n mod 2))-го элемента равнозначности первой группы, выход ()-го элемента равнознач- ности (п+1)-й группы соединен с вторым входом первого элемента равнозначности (К+1)-й группы, а его второй вход соединен с вторым входом (2К-ь4)-го элемента равнозначности (К+1)-й группы, второй вход (а- 2)- го (а (2К + 1)/n mod 2 - К mod 2/) элемента равнозначности (К+1)-й группы соединен с выходом (К+2}-го элемента равнозначности (п+1)-й группы, второй вход которого соединен с вторым входом (2К + 5 -а)-го элемента равнозначности (К+1)-й группы, (К+2)-й информационный вход устройства соединен с вторым входом (2Ь+1)-го элемента равнозначности(Ь 1,.. ,К)(К+1)-й группы, второй вход (2Ь + 2)-го элемента равнозначности которой соединен с выходом (К+2)-го элемента равнозначности (п+1)-й группы, выход первого элемента равнозначности К- й группы соединен с третьими входами первого и второго элементов равнозначности (Ю 1)-й группы, выход первого элемента равнозначности (п-1)-й группы соединен с первым выходом устройства, выход (2К+2)-го элемента равнозначности К-й группы соединен с третьими входами ()-го и (2К+4)-го элементов равнозначности (К+1)-й группы, выход 2п-го элемента равнозначности (п-1)- и группы соединен с (п-Н)-м выходом устройства, выход 2d-ro элемента

равнозначности К-й группы (d 1, 2К)

гординен с третьим входом (2d+1)-ro элемента равнозначности (К+1)-й группы и третьим входом (2d+2)-ro элемента равнозначности (К+1)-й группы, четвертый вход которого соединен с четвертым входом (2di1)-ro элемента равнозначности (К+1)-й группы и выходом (2d+1)-ro элемента равнозначности К-й группы, выход i-ro элемента равнозначности n-й группы соединен с (1+1)- г/ выходом устройства, а его (q+1)-u вход соединен с выходом (2i - 1+q)-ro элемента равнозначности (п-1)-й группы.

Изобретение относится к вычислительной технике и предназначено для построения быстродействующих матричных процессоров, обладающих высокой контролепригодностью. Цель изобретения - повышение достоверности контроля устройства для подсчета числа единиц. Устройство для подсчета числа единиц содержит N элементов ИЛИ (N - разрядность входного двоичного слова), элемент НЕ, N + 2 групп элементов равнозначности, N информационных входов, два управляющих входа и N + 1 выходов. Устройство для подсчета числа единиц работает в рабочем режиме и режиме контроля. В рабочем режиме на информационные входы подаются двоичные переменные X₁...X_N, на управляющие входы-сигналы U₁ = U₂ = 0. Тогда на выходах устройства реализуются фундаментальные (элементарные) симметрические булевы функции, зависящие от переменных X₁...X_N. При подаче на первый управляющий вход сигнала U₁ = 1 устройство переводится в режим контроля. В этом режиме независимо от входных переменных X₁...X_N устройство проверяется четырьмя фиксированными тест-наборами, которые позволяют обнаружить любую константную неисправность произвольной кратности на входах/выходах элементов. 1 ил., 1 табл.

Таблица режимов работы устройства для подсчета числа единиц