Устройство для подсчета числа единиц

 

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

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

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

РЕСПУБЛИК (я)5 G 06 F 11/28, 7/50

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

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

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

6 (21) 4754982/24 (22) 30.10,89 (46) 30.07.91. Бюл, № 28 (72) Л,Б.Авгуль, В,П.Супрун, В.И. Костеневич и С.М.Терешко (53) 681,325(088.8) (56) Авторское свидетельство СССР ¹ 1068932, кл. 6 06 F 7/50, 1980, Патент ФРГ N 1537536, кл, Н 03 К 19/00, 1972. (54) УСТРОЙСТВО ДЛЯ ПОДСЧЕТА ЧИСЛА

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

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

Устройство содержит элементы 11,...,1я равнозначности пятой группы, элементы. Ж „„1667083 А1

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

x>,...,xn, на управляющие входы сигналы

01 = Uz = О. Тогда на выходах устройства реализуются фундаментальные (элементарные) симметричные булевы функции, зависящие от переменных x>,...,x>. При подаче на первый управляющий вход сигнала Ui = 1 устройство переводится в режим контроля.

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

1 ил„1 табл.

21,...,2з равнозначности шестой группы, элементы ИЛИ 31,...,34, элемент НЕ 4, элементы

5i....,54 равнозначности первой группы, элементы 61,...,6в равнозначности второй групп ы, элементы 71,...,7a равнозначности

I третьей группы,.элементы Зi,...,83 равнозначности четвертой группы; информационные входы 91„...,94, управляющие входы 10 и

11 и выходы 12,...,125.

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

В рабочем режиме на информационные входы 9>,...,94 подаются компоненты двоичного вектора х1,...,х4 соответственно, на уп1667083 равляющий вход 10 — сигнал U1 = О, нэ управляющий вход11 — сигнал U2=0. При этом элементы 11,...,14 равнозначности переводятся s режим инверторов. элементы 51, 54, 61,6 2, 65, 66, 71, 7в, 81, 82, 8з равнозначности — в режим элементов И, элементы 52, 5з, бз, 64, 72,...,77 равнозначности — в режим элементов ИЛИ-НЕ. На выходах 121,...,125 устройства реализуются фундаментальные (элементарные) симметрические булевы

; функции (ф.с.б.ф) соответственно F1,...,Fg, где

F1(X1 Х2 Х3, Х4) = F4 (Х1, Х2. Х3, Х4), l l 1,...,5.

Заметим, что ф.с.б.ф, (1, если х. + х +....+х,,„=- а

,Fï (х1,. х2„... xn =

О, если х + х +...,+Х„ф- и где 0<а<п (Сигнал логической единицы форми руется на выходе 12 лишь в том случае, если, вектор входных двоичных пере; мнных )(= (х1, х2,.хз, х4) содержит ровно (i-1) единичных, компонент.

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

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

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

С (01, 02. х1, х2, х3, х4, х5, хв,...,хп), . где U1- 02 — сигналы на первом и втором, управляющих входах 10 и 11 устройства; х - сигнал на К-м информационном входе 9 устройства (К = 1, 2,...,n).

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

С1 = (1, О, О, О, 1, О, 1, О„...,n mod 2);

С2 = (1, 1, О, О, О, 1, О, 1,.„,(1-п mod 2));

С = (1, О, 1, 1, 1, О, 1, О,...,п mad 2);

С4=(1, 1,1, 1,0, 1,0, 1,...,(1-п mod 2)).

n mod 2 = 1, если п — нечетное, в . противном случае и щоб 2 = О.

Таким образом, четыре проверяющих тест-набора представляют собой комбинацию двух кортежей сигналов K1 == (О, 0,) и

K2 = (1, 1) на вторых и третьих входах элементов 5 равнозначности первой группы и двух и-компонентных векторов v1=. (О, 1, О, 1„....,п

mod 2) и v2 (1, О, 1, 0,...,(1-n mod 2)), первая компонента которых подается в ре-5

55 жиме контроля на первые входы элементов

5 равнозначности первой группы, a w- (w =

2, З„...,п-1) — на первые и вторые входы элементов равнозначности w-й линейки; и-я компонента — на первые входы элементов равнозначности и-й линейки.

Вектор-реакция Re = {rf, r3,.„.„r +-1) устройства на тест-набор Се {е = 1, 2, 3, 4) при отсутствии неисправностей имеет вид

Re = (ае, be, be,...,be.8e) где ае б (0,1) be б(0,1)

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

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

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

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

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

Устройство для подсчета числа единиц, содержащее и {п — разрядность входного двоичного слова) элементов ИЛИ и элемент

НЕ, о т л и ч а ю щ е е с я тем, что„с целью повышения достоверности контроля, содержит {n+2) групп элементов равнозначности, i-я из которых {i = 1„...n-1) содержит 2 (i+1) элементов равнозначности, п-я группа содержит (п-1) элементов равнозначности, (п+1)-я группа содержит (n-1) элементов равнозначности, (n+2)-я группа содержит (n-1) элементов равнозначности, первый управляющий вход устройства соединен с первым входом j-.ãî {j = 1„...n) элемента равнозначности (n+1)-й группы и входом элемента НЕ, выход которого соединен с первым входом

i-ro элемента равнозначности (и+2}-й группы и первым входом j-ro элемента ИЛИ, выход 1-го элемента ИЛИ соединен с первым входом t-ro элемента равнозначности

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

1,...,р; р=2- i mod 2. если и-четное. р= 1

+ I mod 2, если и — нечетное), выход и-го элемента ИЛИ соединен с первым входом

l-го элемента равнозначности и-й группы, второй управляющий вход устройства соединен с вторым входом первого элемента

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

1...„n-2) элемента равнозначности (и+2)-й значности (и+1)-й группы, второй вход которого соединен с вторым входом (2К+ 5- а)-го элемента равнозначности (К+1)-й группы, (К+2)-й информационный вход устройства соединен с вторым входом (2Ь+1)-го элемента равнозначности (Ь =1...„К)(К+1)-й группы, второй вход (2Ь + 2)-го элемента равнозначности которой соединен с выходом (К+2)-ro элемента равнозначности (n+1)-й группы, выход первого элемента равнозначности Кй группы соединен с третьими входами первого и второго элементов равнозначности (К+1)-й группы, выход первого элемента равнозначности (n-1)-й группы соединен с пер.вым выходом устройства, выход (2К+2)-го элемента равнозначности К-й группы соединен с третьими входами (2К+3)-го и (2К+4)-го элементов равнозначности (К+1)-й группы, выход 2п-ro элемента равнозначности (и-1)й группы соединен с (п+1)-м выходом устройства, выход .2d-го элемента равнозначности К-й. группы (4 = 1, 2,...,К) соединен с третьим входом (2d+1)-ro элемента равнозначности (К+1)-й группьг и третьим входом (2d+2)-го элемента равнозначности (К+1)-й группы, четвертый вход которого соединен с четвертым входом (26+1}-го элемента равнозначности (К+1)-й группы и выходом (2б+1)-го элемента равнозначности К-й группы, выход i-го элемента равнозначности и-й группы соединен с (i+1)м выходом устройства, а его (ц+1)-й вход соединен с выходом (2i - 1+q)-ro элемента равнозначности (и-1)-й группы. группы соединен с вторым входом (К+1)-го, 5 элемента равнозначности (и+2)-й группы, вторым входом (К+1)-го элемента ИЛИ и первым входом m-го элемента равнозначности(К+1)-й группы(m =- v+ 1, v+2...mod .,2К

+4-v; ч=2-(К+1) 2), если n — четное, ч=

1 + (К+1) mod 2, если и — нечетное); j-й информационный вход устройства соединен с вторым входом j-го элемента равнозначности (n+1)-й группы, выход первого элемента равнозначности (и+1)-й группы со10 единен с вторым входом q-ro (q = 1, 2) элемента равнозначности первой группы, а его второй вход соединен с вторым входом (q+2)-го элемента равнозначности первой группы, выход второго элемента равнозначности (и+1)-й группы соединен с третьим входом (2п mod 2+q)-го элемента равнозначности первой группы, а его второй вход

20, соединен с третьим входом (q+ 2 (1- n mod

2))-го элемента равнозначности первой группы, выход (К+2)-го элемента равнознач- 25 ности(п+1)-й группы соединен с вторым входом первого элемента равнозначности (К+1)-й группы, а его второй вход соединен с вторым входом (2К+4)-го элемента равнозначности (К+1)-й группы, второй вход(а+2)30 го (а = (2К+ 1)/и mod 2 — К mod 2/) элемента равнозначности (К+1)-й группы соединен с выходом (К+2)-ro элемента равноТаблица режимов работы устройства для подсчета числа единиц

8ыходы

Управляюие Входы

Информационные

Режим вход

124 125

122 123

9г 9з 9

10 11

О

О

1

0

О

1

О

1

О

О

О

Рабочий

0

1

Контроль

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

0

О

1

1.

0

О

О

О

О

О

1

1

1

1

О

1

О

О

О

О

О

1

1

О

О

0

О

О

О

О

0

О

О

О

О

О

О

О

1

О

О

О

О

О

О

О

О

О

О

О

О

О

1, 1

О

О

О

1 г О

1

О

О

1

О

0

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

О

1667083

Составитель В. Березин

Техред M.Ìoðãåíòàë Корректор Т. Малец

Редактор А. Лежина

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

Заказ 2525 Тираж 418 Подписное

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

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