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

 

Изобретение относится к автоматике и вычислительной технике. Цель изобретения - сокращение аппаратурных затрат. Устройство содержит N-разрядный входной регистр 1, выходной регистр 2, преобразователь 3 двоичного кода в уплотненный код, преобразователь 4 уплотненного кода в код количества единиц. Преобразователь 3 содержит узел 7 управляемой инверсии, узел 8 формирования уплотненного кода, элемент НЕ 9 и матрицу 10 модулей. Узлы 7 и 8 связаны с входом 11 и получают от него управляющие сигналы 0 или 1. Матрица 10 состоит из [(N + 1)/2] строк модулей, причем каждая I-я строка содержит (N - I) модулей. 4 ил.

СОЮЗ СО8ЕТСНИХ

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

РЕСПУБЛИН (51) 5 G 06 F 7/50

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

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

ПРИ ГННТ СССР (21) 4398425/?4 — 24 (27) ?5. 03. 88 (46) 07.06.90. Бюл. ¹ 71 (71) Вычислительный центр СО АН СССР (72) П.А.Ким, К.С.Алсынбаев, В.А.Забелин и Н.А.Осипов (53) 681. 325(088.8) (56) Авторское свидетельство СССР № 450160, кл. G 06 F 7/50, 1972.

Авторское свидетельство СССР

798830, кл. G 06 F 7!50, 1978.

:,54) УСТРОЙСТВО ДЛЯ ПОДСЧЕТА КОЛИЧЕСТВА ЕДИНИЦ В ДВОИЧНОМ ЧИСЛЕ (57) Изобретение относится к автома— тике и вычислительной технике. Цель изобретения — сокращение аппаратурных затрат. Устройство содержит и-разрядный входной регистр 1, выходной ðåгистр 2, преобразователь 3 двоичного кода в уплотненный код, преобразователь 4 уплотненного кода в Koji количества единиц. Преобразователь 3 содержит узел 7 управляемой инверсии, узел 8 Формирования уп IoTHeHHol" кода, элемент HE 9 и матрицу 10 модулей.

Узлы 7 и 8 "âÿçàíû с входом 11 и получают от него управляющие сигналы 0 или 1. Матрица 10 состоит из 1(п+1) /2) строк модулей, причем каждая i-я строка содержит (n-i) модулей. 4 ил.

1569822

Изобре гение относич ся к автоматике и вычислительной технике.

Цель изобретения — сокращение апгаратурных затрат. э

На фиг. 1 изображена схема устройства для подсчета количества единиц в двоичном числе; на фиг. 2 — схема выполнения узла управляемой инверсии; на фиг. 3 — схема выполнения узла фор-,0 мирования уплотненного кода (для п=8); на фиг. 4 — схема выполнения матрицы модулей.

Устройство для подсчета количества единиц в двоичном числе содержит п-разрядный входной регистр 1 (фиг,l), выходной регистр 2, преобразователь 3 двоичного кода в уплотненный код,, преобразователь 4 уплотненного кода в код количества единиц, входы 5, выхо- 0 ды 6 . Преобразователь 3 содержит узел

7 управляемой инверсии, узел 8 формирования уплотненного кода, элемент НЕ

9 и матрицу 10 модулей. Устройство содержит также вход llпризнака непревьш ения половины количества единиц в двоичном числе. Узел 7 содержит разрядные модули 12, каждый из которых содержит элемент И 13 и элемент И 14 (с инверсными входами) . Узел 8 содержит группу элементов ИЛИ 15 и группу элементов ЗАПРЕТ 16. Матрица 10 содержит модули 17, каждый из которых содержит элемент ИЛИ 18 и элемент И

19 (фиг. 2 — 4) .

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

Ha o Ho e Ic 1 через входы устройства 5 заносится код числа.

С выходов входного регистра 1 код числа передается на узел 7, управляемый по входу 11. Пусть сигнал "1"на входе 11 информирует устройсТво о том, что число единиц в обрабатываемом коде не больше числа нулей, тогда узел 7 пропускает через себя информацию без изменения. Если на входе 11 сигнал "0", то узел 7 инвертирует каждый разряд кода, обеспечивая тем самым подсчет числа нулей с помощью той

5G же аппаратуры, подсчитывающей число единиц в коде. С выходов узла 7 обработанный код числа передается на матрицу 10 модулей 17, количество единиц, на выходе которой равно количеству единиц во входном числе при общем ко- 55 личестве единиц, не превышающем число нулей, либо число нулей во входном числе при сигнале "О" на входе 11.

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

Если с входа 11 поступает сигнал "1", то работа второй половины узла 8 (элементы ЗАПРЕТ 16) блокируется,, уплотненный код, равный количеству единиц во входном числе, поступает на входы преобразователя 4, Если на вход 11 поступает сигнал "О", то на первую половину входов преобразователя 4 засылаются "1", а на вторую половину входов преобразователя 4 посылаются инверсные значения выходов матрицы 10.

Работа преобразователя 4 уплотненного кода в код количества единиц описывается следующими формулами (для случая п=8); а, =b,; а,=b, Ь, az=bo Ь,ч Ь,Ь,;

З=Ьо Ь, у Ь Ь„ Ь, Ь у ЬаЬ7, где Ь,b,,bz,...,Ьт — сигналы на входах преобразователя 4; а,а <,а„,а з — сигналы на выходах преобра— зователя 4.

Сигналы через выходной регистр 2 поступают на выходы 6. E результате на выходах 6 устройства образуется код количества единиц во входном числе. Информация о соотношении нулей и единиц на входе 11 может быть обеспечена аналоговыми пороговыми элементами.

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

Устройство для подсчета количества единиц в двоичном числе, содержащее входной регистр, выходной регистр, преобразователь двоичного кода в уплотненный код и преобразователь уплотненного кода в код количества единиц, причем входы устройства соединены с входами входного регистра, выходы которого соединены с входами преобразователя двоичного кода в уплотненный код, выходы которого соединены с входами преобразователя уплотненного кода в код количества единиц, выходы которого соединены с входами выходного регистра, выходы которого соединены с выходами усчройства, при этом преобразователь двоичного кола в уплотненный код содержит матрицу мод 5 15698 лей, каждый из которых содержит элемент И и элемент ИЛИ, первые входы которых соединены с первым входом модуля, вторые входы соединены с вторым входом модуля, а выходы соединены соответственно с первым и вторым выходами модуля, первый вход j-ro модуля 1с-й строки матрицы (j=1,...,n-k;

k=2,...,I(n+1)/2); и — разрядность входного регистра; (х) — целая часть х) соединен с первым выходом j-ro мо— дуля (k-1)-й строки матрицы, второй вход р-ro модуля q-й строки матрицы (р=1 ° .. n-с1-1; q=1 ... р ((и+1) /? 1) 15 соединен с вторым выходом (р+1)-ro модуля q-й строки матрицы, второй вход (n-k)-го модуля k-й строки матрицы соединен с первым выходом (n-k+

+1)-го модуля (k-1)-й строки матрицы, 20 отличающееся тем, что, с целью сокращения аппаратурных затрат, преобразователь двоичного кода в уплотненный код содержит узел управляемой инверсии, элемент НЕ и узел форми- 25

22 6 рования уплотненного кода, содержащий группу элементов ИЛИ и группу элементов ЗАПРЕТ, выходы которых являются выходами преобразователя двоичного кода в уплотненный код, причем первые входы элементов ИЛИ группы и информационные входы элементов ЗАПРЕТ группы соединены с выходом элемента НЕ, вход которого соединен с входом признака непревыщения половины количества единиц в двоичном числе устройства и с управляющим входом узла управляемой инверсии, информационные входы которого являются входами преобразователя двоичного кода в уплотненный код, а выходы соединены с первыми входами модулей с первого по (п-1)-й и с вторым входом (n-1)-rî модуля первой строки матрицы, второй выход первого модуля q-й строки матрицы соединен с вторым входом q † элемента ИЛИ группы и с управляющим входом (P(n+1)/2J-q+ 1)-ro элемента ЗАПРЕТ группы.

1569322

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

Редактор Л.Зайцева Техред М.Дидык Корректор О.Кравцова

Заказ 1450 Тираж 566 Подписное

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

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

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