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

 

Союз Советскик

Социалистических

Республик

П ИС.АНЙ Е

ИЗОБРЕТЕНИЯ

<>798830

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (61) Дополнительное к авт. свид-ву (22) Заявлено 26.12.78 (21) 2709175/18-24 (51)M

G 06 Г 7/50 с присоединением заявок 9 2709176/18-24

2709177/18-24 (23) Приоритет

Государственный комитет

СССР по делам изобретений н открытий

Опубликовано 23.81.81, Бюллетень ¹ 3 (5З) УДЫ 681.325 (088.8) Дата опубликования описания 26.0181 (72) Авторы изобретения

С.В.Сорокин и Г.М.Морозов (71) Заявитель (54) УСТРОИСТВО ДЛЯ ПОДСЧЕТА КОЛИЧЕСТВА ЕДИНИЦ.В ДВОИЧНОМ ЧИСЛЕ

Известен асинхронный импульсный счетчик на асинхронных симметричных

Т-триггерах, реализующий Функцию подсчета количества единиц в двоичном числе, представленном последовательным импульсным кодом. двоичное 1з число поступает на вход Т-триггера первого разряда. Код; являющийся результатом подсчета количества единиц входного двоичного числа, образуется на выходах A,В,С,Т-триггеров, С13 .

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

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

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

1 og < n групп сумматоров по п /2 сум- к маторов в каждой группе(1 k((,og n).

В устройстве двоичное число заносится на и-разрядный входной регистр, а результат подсчета количества единиц (нулей) входного двоичного числа. — на выходной регистр. Соединение сумматоров внутри каждой группы, а также соединение групп сумматоров друг с другом и с выходным п- разрядным регистром и выходным регистром выполнены таким образом, что осуществляется подсчет количества единиц (нулей) входного двоичного числа 2(.

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

798830

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

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

Преобразователь двоичного кода s .. уплотненный код при этом может быть выполнен так, что он содержит log< и строк модулей, причем входы модулей первой строки соединены со входами преобразователя двоичного кода в уплотненный код, выходы модулей последней строки соединены с выходами преобразователя двоичного кода в уплотненный код, каждый модуль k-ой строки (k=1,...,1од п) содержит элементы И и ИЛИ и две группы входов по 2" входов в каждой, входы первой и второй групп каждого К элемента k-ой строки (1=1,..., n/2" ) соединены с выходами (21-1)-ro u

21 -го модулей (k-1)-ой строки, элементы И каждого модуля образуют матрицу, причем входы элементов И каждой строки матрицы подключены к соответствующему входу первой группы входов модуля, входы элементов И каждого столбца матрицы подключены к соответствующему входу второй группы входов модуля, входы каждого m элемента. ИЛИ (m=1,...2 -1) соединены с выходами элементов И соответствующей диагонали матрицы, входы каждого р элемента ИЛИ (р=2"-< + 1

2" ) соединены с (p-2" )-ми, входами первой и второй групп входов модуля, выходы элементов ИЛИ подключены к выходам модуля.

Преобразователь двоичного кода в уплотненный код выполнен так, что он содержит (и-1) строк модулей, каждый из модулей содержит элементы

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

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

i-го модуля каждой четной строки .присоединен к первому входу 1-го модуля следующей строки.

Преобразователь двоичного кода в щ уплотненный код может быть выполнен так, что он содержит -n-1 строк мо дулей, причем каждая i-ая строка (1 1,...,n-1) преобразователя двоичного кода в уплотненный код содержит и-1 модулей, а каждый из модулей содержит элемент И и элемент

ИЛИ, причем первый вход модуля соединен с первыми входами. элементов И и

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

40 j-ro модуля (j =2,..., n-1) присоединен ко второму входу (j-1)-ro модуля, первый выход модуля (ф=1, ...,n-i-1) каждой стрЬки присоедине.ны к первому входу с(, модуля слеИ дующей строки.

798830

25 о о>

О,= ЬоЬ4

О, ЬоЬ Vb,b(,t

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

Устройство для подсчета количества единиц в дво :.ом числе содержит входной регистр 1, выходной регистр

2, входы устройства 3, выходы устройства 4, преобразователь 5.двоичного кода в уплотненный код и преобразователь б уплотненного кода в код количества единиц причем входы преобразователя 5 соединены с выходами входного регистра 1, выходы преобразователя 5 соединены со входами преобразователя б, выходы которого соединены со входами выходного регистра 2.

Устройство для подсчета единиц работает следующим образом.

На входной регистр 1 через входы устройства 3 заносится двоичный код числа. С выходов входного регистра

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

Работа преобразователя 6 уплотненного кода в код количества единиц описывается формулами где,ао, a,;a ;a> — сигналы на выходах преобразователя 6 кода.

Ьо; Ь,;,.:,Ь вЂ” сигналы на входах .преобразователя б. ф5

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

Преобразователь 5 состоит из 1од и $0 строк модулей 7 (фиг.5), причем входы модулей 7 первой строки соединены со входами преобразователя 5, выходы модуля последней строки соединены с выходами, преобразователя 5, выходы каждой из двух групп входов любого модуля 7,кроме модулей первой строки, подключены к соответствующим выходам одного модуля 7 предыдущей строки, каждый модуль 7 содержит элементы

8И, образующие матрицу, элементы ;40

9ИЛИ, и две группы входов, причем входы каждой группы входов модуля 7

i îé строки (i=1,...,1og

9ИЛИ соединены с соответствующими выходами модуля 7.

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

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

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

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

Преобразователь 5 содержит n- строк модулей 10, каждый из которых содержит элементы 11И и 12ИЛИ. Входы модулей 10 первой строки соединены со входами преобразователя 5. Выходы модулей 10 последней строки, а также первый выход первого модуля

10 (модули в строках нумеруются слева направо) и второй выход последнего модуля 10 предпоследней строки присоединены к выходам преобразователя 5. Первый выход последнего модуля 10 первой строки соединен с первым входом первого модуля

10 второй строки, второй выход последнего модуля 10 первой строки сое-. динен со вторым входом последнего модуля 10 второй строки. Первый выход первого модуля каждой четной строки подключен к первому входу первого модуля 10 следующей четной строки. Второй выход последнего модуля 10 каждой четной строки присоединен ко второму входу последнего модуля 10 следующей четной строки.

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

10 каждой нечетной строки присоеди798830

10 (i)

Я% g п (2) о и

Хь=1 "б "" ) где

6 нен ко второму входу i-го модуля

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

i-го модуля 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-го модуля 13, кроме первого, присоединен ко второму входу 1-1-гс модуля 13. В каждой строке первый выход любого i-ro модуля 13, кроме последнего, присоединен к первому входу i--го же модуля 13 следующей строки..

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

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

Т„= 1 (п 2-1) + ь Cog q (1) где Т, — время пробега сигнала суммы через сумматор; п время пробега сигнала переноса через сумматор; и — разрядность входного регистра.

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

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

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

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

798830

45

2.устройство по п.1, о т л и— ч а ю щ e e с я тем, что преобразователь двоичного кода в уплотненный код содержит loga n строк модулей, причем входы модулей первой строки соединены со входами преобразователя двоичного кода в уппотненный код, выходы модулей последней строки соединены с вы одами преобразователя двоичного кода в уплотненный код, каждый модуль k-ой строки (k=1, ...,1о9 и) содержит элементы И и

ИЛИ и две группы входов по 2 входов в каждой, входы первой и второй группы каждого 1 элемента k-ой строки (1=1,..., A)2 ) соединены к с выходами (21 -1)-го и 21 -го модулей (k-1)-ой строки, элементы И каждого модуля образуют матрицу, причем входы элементов И каждой стро- . ки матрицы подключены к соответствующему входу первой группы входов моду- Щ .ля,входы элементов И каждого столбца матрицы подключены к соответствующему входу второй группы входов модуля, .входы каждого. m (m=1, k ...,2 -1) соединены с выходами эле- д ментов И соответствующей диагонали матрицы, входы каждого р элемента

ИЛИ (р=2 + 1,;..24 ) соединены с (р-.2 )-ми входами первой и второй

k-1 групп входов модуля, выходы элементов ИЛИ подключены к выходам модуля.

3. Устройство по п.1, о т л ич а ю щ е е с я тем, что преобразователь двоичного кода в уплотненный код содержит (и-1) строк модулей, каждый из модулей содержит элементы

И и ИЛИ, причем первый вход каждого модуля соединен с первыми входами элементов И и ИЛИ, второй вход модуля соединен со вторыми входами элементов И и ИЛИ, выход элемента 40

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

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

4.устройство по п.1 о т л и ч а ю щ е е с я тем, что преобразователь двоичного кода в уплотненный код содержит и-1 строк модулей, причем каждая i àÿ строка (i =1,..., и-1) преобразователя двоичного Йода в уплотненный код содержит n-i модулей, а каждый из модулей содержит элемент И и элемент ИЛИ, причем первый вход модуля соединен с первыми входами элементов И и ИЛИ, второй вход модуля соединен со вторыми входами элементов И и ИЛИ, выход элемента И соединен с первым выходом модуля, выход элемента ИЛИ соединен со вторым выходом модуля, первые входы модулей первой строки и второй вход последнего модуля первой строки соединены со входами преобразователя двоичного кода в уплотненный код, второй выход первого модуля каждой строки и первый выход первого модуля последней строки соединены с выходами преобразователя двоичного кода в уплотненный код, первый выход последнего модуля каждой строки, кроме последней, соединен со вторым входом последнего модуля следующей строки, в каждой строке второй выход j-го модуля j=2,..., n-1 присоединен ко второму входу j-1 -го модуля, первый выход с(, -ro модуля ($ =1,..., и-i-l) каждой строки присоединен к первому входу с1 -ro модуля следующей строки.

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

1.Будинский Я. Логические цепи в цифровой тЕхнике. М., "Связь", 1977, с. 266, рис. 6.111а. .2.Авторское свидетельство СССР

9 450160, кл. G 06 F 5/02, 1972 (прототип).