Устройство для подсчета количестваЕдиНиц B дВОичНОМ чиСлЕ Советский патент 1981 года по МПК G06F7/50 

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

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

Преобразователь двоичного кода в уплотненный код при этом может быть выполнен так, что он содержит 1 од, п строк модулей, причем входы модулей первой строки соединены со входами преобразователя двоичного кода в уплотненный код, выходы модулей последней строки соединены с выходами преобразователя двоичного кода в уплотненный код, каждый модуль к-ой строки ( ,.,. , ) содержит элементы И и ИЛИ и две группы входов по 2 входов в каждой, входы первой и второй групп каждого Е элемента k-ой строки (1 1 , . . . , 0/2 ) соединены с выходами (21-1)-го и 21 -го модулей (К-1)-ой строки, элементы И каждого модуля образуют матрицу, причем входы элементов И каждой строки матрицы подключены к соответствующему входу первой группы входов модуля, входы элементов И каждого столбца матрицы подключены к соответствующему входу второй группы входов модуля, входы каждого т элемента- ИЛИ (т 1 , . . . 2 -1) соединены с выходами элементов И соответствукицей диагонали матрицы, входы каждого р элемента ИДИ (р 2 + 1 . . , 2) соединены с ( )-ми, входами первой и второй групп входов модуля, выходы элементов ИЛИ подключены к выходам модуля. . .

Преобразойатель двоичного кода в уплотненный код выполнен так, что он содержит (п-1) строк модулей, каждый из модулей содержит элементы И и ИЛИ, причем первый вход Кс1ждого модуля соединен с первыми входами элементов-И и ИЛИ, второй вход модул соединен со вторыми входами элементов И и ИЛИ, выход элемента И соединен с первым выходом модуля, выход элемента ИЛИ соединен со вторым выходом модуля, входы модулей первой строки соединены со входами преобразователя двоичного кода в уплотненный код, выходы модулей последней строки, а также первый выход первого модуля и второй выход последнего модуля предпоследней строки присоединены к выходс№1 преобразователя двоичного кода в уплотненный код, первый выход последнего модуля первой строки соединен с первым входом первого модуля второй строки второй выход последнего модуля первой стро|ки соединен со вторым входом последнего модуля второй строки, первый выход первого модулякаждой четной строки подключен к первому входу первого модуля следующей четной строки второй выход последнего модуля четной строки присоединен ко втоЕому входу последнего модуля следующей четной строки, остальные выходы модулей каждой строки присоединены ко входам модулей следующей строки, причем первый выход любого i-rgi модуля каждой нечетной строки присоединен ко второму входу i-ro модуля следующей строки, второй выход любого i-ro модуля каждой нечетной строки присоединен к первому входу i+1-го модуля следующей строки, первый выход любого i-го модуля каждой четной строки присоединен ко второму входу i-1-го модуля следующей строки, а второй выход любого i-ro модуля каждой четной строки .присоединен к первому входу 1-го модуля следующей строки.

Преобразователь двоичного кода в уплотненный код может быть выполнен так, что он содержит -п-1 строк модулей, причем каждая i-ая строка ( I 1 , . . , , п -1) преобразователя двоичного кода в уплотненный код -содержит n-i модулей, а каждый из модулей содержит элемент И и элемент ИЛИ, причем первый вход модуля соединен с первыми входами.элементов Ни ИЛИ, второй вход модуля соединен со вторыми входами элементов. .И и ИЛИ, выход элемента И соединен с первым выходом модуля, выход элемента ИЛИ соединен со втор«ым выходом модуля, первые входы модулей первой строки и второй вход последнего модуля первой строки соединены со входами преобразователя двоичного кода в уплотненный код, второй выход первого модуля каждой строки и первый выход мо дуля последней строки соединены с выходами преобразователя двоичного кода в уплотненный-код, первый выход последнего модуля каждой строки, кроме последней, соединен со вторым входом последнего модуля следующей СТ130КИ, в каждой строке второй выход J-го модуля (j 2,..., п-1) присоединен ко второму входу (j-l)-ro модуля, первый выход а модуля (CJ,-1 ...,п-1-1) каждой строки присоедине. ны к первому входу cj, модуля следующей строки. На фиг. 1 изображена схема устройства для подсчета количества еди ниц в двоичном числе на 8 разрядов; на фиг. 2,3 и 4 - варианты выполнен преобразователя двоичного кода в уплотненный кодtна фиг, 5 - схема выполнения модуля преобразователя двоичного кода в уплотненный код, выполненного в соответствии с фиг.2 Устройство для подсчета количест ва единиц в двои-и.ом числе содержит входной регистр 1, выходной регистр 2, входы устройства 3, выходы устройства 4, преобразователь 5. двоичного кода в уплотненный код и преобразователь 6 уплотненного кода в код количества единиц причем входы преобразователя 5 соединены с выходами входного регистра 1, выходы преобразователя 5 соединены со входами преобразователя 6, выходы которого соединены со входами выходного регистра 2. Устройство для подсчета единиц работает следующим образом. На входной регистр 1 через входы устройства 3 заносится двоичный код числа. С выходов входного регистра 1 код числа передается в преобразователь 5 двоичного кода в уплотнен ный код, количество единиц на выходе которого равно количеству единиц во входном числе. . Работа преобразователя б уплотне ного кода в код количества единиц описывается формулами V-boi аг-ЧЬ,; °a--boV4 i °i--44V4b,y4V4b7/ где «ар, а ,32 , а, - сигналы на выход преобразователя кода, bg ; b,;...;b-j - сигналы на входа - преобразователя В результате такого двойного.пре образования на выходах устройства образуется код количества единиц во входном числе. Преобразователь 5 состоит из logj строк модулей 7 (фиг.5), причем вход модулей 7 первой строки соединены со входами преобразователя 5, выходы модуля последней строки соединены с выходами преобразователя 5, каждой из двух г.рупп входов любого модуля 7,кроме модулей первой строк подключены к соответствующим выхода одного модуля 7 предыдущей строки, каждый модуль 7 содержит элементы 8И, образующие матрицу, элементы 9ИЛИ, и две группы входов, причем входы каждой группы входов модуля 7 i-ой строки (i 1 ,.,.., 1 ) пронумерованы от О до - 1 и соеди нены со входами элементов 8И таким образом, что образуется совпадение каждого входа первой группы входов модуля 7 с каждым входом второй группы входов модуля 7, выход каждого элемента 8и подключен кг входу того элемента 9ИЛИ, номер которого равен сумме номеров вХодов модуля 7, подключенных к данному элементу 8И, кроме тогсэ, каждый J -ый вход любой группы входов модуля 7 i-ой строки соединен со входом элемента 9ИЛИ с номером 2 + j / выхода элементов 9ИЛИ соединены с соответствующими выходами модуля 7. Работа преобразователя 5 двоичного кода в уплотненный код заключается в следующем. Каждый модуль i-ой строки устройства преобразует коды, поступающие на входы первой и- второй групп его входов таким образом, что в коде на выходе модуля 7 все единицы сдвинуты вправо, а количество единиц в выходном коде равно суммарному количеству единиц во входных кодах. Модули 7 соединены между собой так, что йа входы каждой группы входов любого модуля 7 поступает код, в котором все единицы сдвинуты вправо. В результате преобразования двоичного входного числа модулями 7 преобразователя 5 на выходе модуля 7 последней строки образуется код, в котором все единицы сдвинуты вправо, а их количество равно количеству единиц во входном регистре 1. Другой вариант построения преобразователя 5 двоичного кода в уплотненный код показан на фиг. 3. Преобразователь 5 содержит n-i строк модулей 10, каждый из которых содержит элементы НИ и 12ИЛИ. Входы модулей 10 первой строки соединены со входами преобразователя 5. Выходы модулей 10 последней строки, а также первый выход первого модуля 10 (модули встроках нумеруются слева направо) и второй выход последнего модуля 10 предпоследней строки присоединены к выходам преобразователя 5. Первый выход последнего модуля 10 первой строки соединен с первым входом первого модуля 10 второй строки, второй выход последнего модуля 10 первой строки соединен со вторым входом последнего модуля 10 второй строки. Первый выход первого модуля каждой четной строки подключен к первому входу первого модуля 10 следующей четной строки. Второй выход последнего модуля 10 каждой четной строки присоединен ко второму входу последнего модуля 10 следующей четной строки. Оставшиеся выходы модулей 10 каждой строки присоединены ко входам-модулей 10 следующей строки, причем первый выход любого i-го модуля 10 каждой нечетной строки присоединен ко второму входу i-ro модуля 10 следующей строки, второй выход любого i-ro модуля 10 каждой нечетной строки присоединен к первому входу i+1-го модуля 10 следующей строки, первый выход любого

i-ro модуля 10 каждой четМой строки присоединен ко второму входу I-1-го модуля 10 следующей строки, а второй выход любого i -го модуля .10 каждой четной строки присоединен к первому входу i-ro модуля 10 следующей строки. Входы элементов 11И и 12ИЛИ каждого модуля 10 соединены со входами модуля 10, а выходы подключены соответственно к первому и второму выходам модуля 10. Каждый из модулей 10 осуществляет сдвиг единиц, поступивших на его входы,вправо, то есть,если на первый и второй входы модуля 10 поступают коды 00,01,10,11 то на первом и втором выходе модуля появляются соответственно коды 00, 01, 01,11. Модули 10 соединены между собой таким образом, что на выходе преобразователя 5 образуется код, в котором все единицы сдвинуты вправо, а их количество равно количеству единиц входного двоичного числа.

Третий вариант построения преобразователя 5 двоичного кода в уплотненный код представлен на фиг.4.

Преобразователь 5 содержит модули 13, каждый из модулей 13 содержит элемент 14 И и элемент 15 ИЛИ, причем первый вход модуля 13 соединен с первыми входами элементов 14 И и 15 ИЛИ, второй вход модуля 13 соединен- со вторыми входами элементов 14 И и 15 ИЛИ, выход элемента 14 И соединен с первым выходом модуля 13, выход элемента 15 ИЛИ соединен со вторым выходом модуля 13. Первые . входы модулей 13 первой строки и второй вход последнего модуля 13 первой строки соединены со входами прео.бразователя 5. Второй выход первого модуля 13 каждой строки (модули в строках пронумерованы слева направо) и первый выход первого модуля 13 последней строки присоединен к соответствующим выходам преобразователя 5. Первый выход последнего модуля 13 каждой строки, кроме последней , соединен со вторым входом последнего .модуля 13 следующей строки. В каждой, строке второй выход любого i-ro модуля 13,, кроме первого, присоединен ко второму входу 1-1-гс модуля 13. В каждой строке первый выход любого i-ro модуля 13, кроме последнего, присоединен к первому входу i--ro же модуля 13 следующей строки.

Структура связи между элементами предлагаемого устройства проще, чем в известном устройстве, за счет исключения таких конструктивно слоя:

ных элементов, как сумматоры. Большая степень регулярности связей между элементами и простота самих элементов устройства повышает технологичность его изготовления методами с микроэлектроники, что приводит, в конечном счете, к увеличению процента выхода годных изделий в производстве и повышение надежности устройства в процессе эксплуатации. Q В известном устройстве время задержки сигналов при прохождении их через сумматоры определяется по формуле

(n/2-i), (1)

--гс/

f где Т - время пробега сигнала суммы через сумматор; t - время пробега сигнала переноса через сумматор; п - разрядность входного ре20гистра.

В данном устройстве время задержки Tfji сигналов с выходов п-разрядного входного регистра 1 при прохождении их через модули преобразователя 5 и через преобразователь 6 складывается из суммарного времени задержки, сигнала модулем каждой строки первого преобразователя кода и вторым преобразователем кода и определяется по формуле

Ji)

..г (2)

2- ,-1

jyi

5 где t

задержка сигнала модулем i-ой строки преобразователя 5;

г

задержка сигнала преобразователем б;

разрядность входного реп гистра 1.

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

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

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

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

2.Устройство по П.1, о т л и чающееся тем, что преобразователь двоичного кода в уплотненный код содержит строк модулей, причем входы модулей первой строки соединены со входами преобразователя двоичного кода в уплотненный код, выходы модулей последней строки соединены с выходами преобразователя двоичного кодав уплотненный код, каждый модуль k-ой строки , . . . , ) содержит элементы И и ИЛИ и две группы входов по входов в каждой, входы первой и второй группы каждого 1 элемента k-ой строки { 1 , . . . , П/2 ) соединены с выходами (21 -1)-го и 21 -го модулей (k-l)-oй строки, элементы И каждого модуля образуют матрицу, причем входы элементов И каждой строки матрицы подключены к соответствующему входу первой группы входов моду.ля,входы -элементов И каждого столбца матрицы подключены к соответствующему входу второй группы входов модуля .входы каждого, m элемента ИЛИ , . . . , 2 -1 ) соединены с выходами элементов И соответствующей диагонали матрицы,.входы каждого р элемента ИЛИ (р 2 4 1 , -. . . 2 ) соединены с (р-2 )-ми входами первой и второй групп входов модуля, выходы элементов ИЛИ подключены к выходам модуля.

3. Устройство по П.1, о т л ичающееся тем, что преобразователь двоичного кода в уплотненный код содержит (п-1) строк модулей, каждый из модулей содержит элементы И и ИЛИ, причем первый вход каждого модуля соединен с первыми входами элементов И и ИЛИ, второй вход модуля соединен со вторыми входами элементов И и ИЛИ, выход элемента И свединен с первым выходом модуля, выход элемента ИЛИ соединен со вторым ВЕЛХодом модуля, входы модулей первой строки соединены со входами. преобразователя двоичного кода в уплотненный код, выходы модулей последней строки, а также первый выход первого модуля и второй выход последнего модуля предпоследней строки присоединены к выходам преобразователя двоичного кода в уплотненный код, первый выход последнего модуля первой строки соединен с первым входом первого модуля второй строки, второй вь)1ход последнего модуля первой строки соединен.ей вторым входом последнего модуля второй строки, первый выход первого модуля каждой четной строки подключен к первому входу первого модуля следующей -четной строки, второй выход последнего модуля каждой четной строки присоединен ко второму входу последнего модуля следующей четной строки, остальные выходы модулей каждой строки присоединены ко вх:одам модулей следующей строки, причем первый выход любого i-го модуля каждой нечетной строки присЬединен ко второму входу i-ro модуля следующей строкиj второй выход любого i-го модуля каждой

0 нечетной строки присоединен к первому входу i+1-го модуля следующей строки, первый выход любого i-rc модуля каждой четной строки присоединен ко второму входу i-1-го модуля

5 следующей строки, а второй выход любого i-го модуля каждой четной строки присоединен к первому входу i-ro модуля следующей Фтроки.

4.Устройство по п.If о т л и чающееся тем, что преобразо0ватель двоичного кода в уплотненный код содержит п-1 строк модулей, причем каждая i -ая строка (i 1,. . . п-1) преобразователя двоичного Лода в уплотненный код содержит n-i моду5лей, а каждый из модулей содержит элемент И и элемент ИЛИ, причем первый вход модуля соединен с первыми входами элементов И и ИЛИ, второй вход модуля соединен со вторыми вхо0дами элементов И и ИЛИ, выход элемента И соединен с первым выходом модуля, выход элемента ИЛИ соединен со вторым выходом модуля, первые входы модулей первой строки и второй вход

5 последнего модуля первой строки соединены со входами преобразователя двоичного кода в уплотненный код, второй выход первого модуля каждой строки и первый выход первого модуля последней строки соединены с выхо0дами преобразователя двоичного кода в уплотненный код, первый выход последнего модуля каждой строки, кроме последней, соединен со вторым входом последнего модуля следующей строки,

5 в каждой строке второй выход j-ro модуля ,..., п-1 присоединен ко второму входу J-1 -го модуля, первый выход с -го модуля (С 1,, .., n-i-1) каждой строки присоединен к

0 первому входу о -го модуля следующей строки.

Источники информации, принятые во внимание при экспертизе

1.БУДИНСКИЙ Я. Логические цепи в

5 цифровой технике. М., Связь, 1977, с. 266, рис. 6.Ilia.

.2.Авторское свидетельство СССР № 450160, кл. G 06 F 5/02, 1972 (прототип).

444

f

у f , fч r Г f

k

b,

Oo

a,

f

1

11

r//Стропа J

ipuf. 1

Строка 2

Cmfje/(O $

Ф NK. 4 W-ф y4 Y

5

irjii

i f5fLi

(

f

f v 7,

s,

A

f f f

i

TTTt

ЛУФФТ i М

ЛГ

ii,

ФФ

Й/г J