Устройство для определения количества единиц в двоичном числе Советский патент 1990 года по МПК H03M7/04 G06F11/10 

(61) 1322480

(21)4440259/24-24

(22)13.06.88

(46) 28.02.90. Бюл. IP 8 (72) В.Г.Попов, Б.В.Панца и С.А.Шибаев

(53)621.39Ь(088.8)

(56)Авторское свидетельство СССР № 1322480, кл. Н 03 М 7/04, 1986.

(54)УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ КОЛИЧЕСТВА ЕДИНИЦ В ДВОИЧНОМ ЧИСЛЕ

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

Изобретение относится к вычислительной технике и может быть использовано для контроля цифровой информации. Целью изобретения является повышение быстродействия устройства. Устройство содержит N-разрядный регистр, восемь групп элементов И, группу элементов ИЛИ, первый и второй элементы ИЛИ, элемент ИЛИ-НЕ, четыре элемента И, элемент И-НЕ, элемент задержки, триггер, реверсивный счетчик, третий и четвертый элементы ИЛИ, пятый элемент И, первые и вторые информационные входы, вход запуска кодовые входы, тактовый вход, информационные и управляющий выходы. 1 ил.

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

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

На чертеже приведена структурная схема предлагаемого устройства.

Устройство содержит п-разрядный регистр 1, первую 2, вторую 3, третью 4 и четвертую 5 группы элементов И, группу элементов ИЛИ 6, первый 7 и второй 8 элементы ИЛИ, элемент ИЛИ- НЕ 9, первый 10, второй 11, третий 12 и четвертый 13 элементы И, элемент И-НЕ 14, элемент 15 задержки, триггер 16, реверсивный счетчик 17, пятую 18, седьмую 19, шестую 20 и восьмую 21 группы элементов И, третий 22 и четвертый 23 элементы ИЛИ, пятый элемент И 24, первые 25 и вторые 26

информационные входы устройства, вход 27 запуска устройства, кодовые входы 28 устройства, тактовый вход 29, информационные 30 и управляющий 31 выходы устройства.

Исходное состояние устройства характеризуется тем, что регистр 1 и триггер 1Ь установлены в О (не показано).

Пусть число разрядов анализируемого кода - четное, Разделим разряды исходного кода на две равные части по п/2 разрядов.

Обозначим буквой Е - общее количество единиц в двоичном коде; количество единиц в первой и второй половинах исходного кода соответственно; Н - количество нулей во второй половине исходного кода.

Тогда

,+Е 1+Е1+п/2-п/2 Е1 -(п/2- -E2)J+n/2 E,-Ha+n/2.

(Л

ел

Ј q

-4

№

Ч

Из указанного выражения видно, что выдача подсчета количества единиц в коде сводится к нахождению разности количеств единиц в первой и нулей во второй половинах кода и коррекции результата на величину п/2.

Разность может быть найдена еле- .„ дующим образом.

Попарно анализируются одноименные разряды в первой и второй половинах регистра. Если в анализируемом коде комбинация 11, то разность равна +1 и в счетчик нужно добавить единицу. Если в анализируемой паре комбинация 00, то разносить равна -1 и из счетчика следует вычесть единицу. Если KOM-I бинация равна 01 либо 10, то содержимое счетчика остается изменения. В случае, когда первая пара разрядов содержит комбинацию 11, а вторая - 00, нет необходимости в счетчик вначале прибавлять единицу, а затем вычитать,еледует оставить содержимое счетчика без изменения с переходом к анализу очередной пары комбинаций 11 и 00.

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

Если в процессе поиска таких пар встречаются только комбинации 11, то в счетчик прибавляется 1, если только комбинация 00, то из счетчика вычитается 1.

Коррекция может быть осуществлена предварительной записью кода п/2 в счетчик.

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

Устройство начинает работать по сигналу запуска, поступающему по входу 27 запуска на единичный вход триггера 16 и устанавливающему его в состояние 1. При этом единичным сигналом с единичного выхода триггера 16 открывается элемент И 13, через который начинают поступать тактовые импульсы с входа 29.

Пусть в 8-разрядный регистр 1 в первую половину принят код 1001, во вторую - 1010, а в счетчик 17 двоичный код 1000. 1

При этом элемент И 21 открыт.

Единичный сигнал с его выхода по одноименным инверсным входам закрывает

0

5

0

5

0

5

0

5

последующие элементы И 2, поступает на второй вход элемента И 3 и через элемент НИИ 7 открывает по первому входу элемент И-НЕ 14, По этому сиг- налу элемент ИЛИ-НЕ 9 формирует на своем выходе нулевой сигнал, закрывающий по первому входу элемент И 10.

Так как на инверсных выходах вторых разрядов обеих половин регистра 1 имеются единичные сигналы, то открытый элемент И 42 по инверсному входу нулевым сигналом с выхода элемента И 41 формирует на своем выходе единичный сигнал. Этим сигналом закрыты по одноименным инверсным входам последующие элементы И 4 и открыты по ий- версному входу элементы Д 52 и через элемент ИЛИ 8 по второму входу элемент И-НЕ 9. При этом на его выходе формируется нулевой сигнал, закрывающий по первым входам оба элемента И 11 и 12.

Тактовый сигнал, поступающий по входу 29 через открытый элемент И 13, не воздействует на состояние счетчика 17, а устанавливает после прохождения элемента 15 задержки в О через открытый элемент И 31 первый разряд первой половины регистра 1 и в 1 через открытый элемент И 52 и элемент ИЛИ 6 j, второй разряд второй половины регистра 1.

Таким образом, после тактового импульса в регистре 1 фиксируется код 0001.1110.

После этого на выходах элементов И 2 и 4 устанавливаются нулевые сигналы, которые поступают через элементы ИЛИ 7 и 8 на соответствующие входы элемента ИЛИ-НЕ 9. На выходе последнего формируется единичный сигнал, открывающий элемент И 10.

Очередной тактовый импульс, проходящий через открытый элемент И 13, не воздействует на состояние счетчика 17 и регистра 1, так как элементы, ИЗ, 5, 11 и 12 закрыты. Так как элемент И 10 открыт, то этим тактовым сигналом устанавливаются в О триггер 16 и все разряды регистра 1. Единичный сигнал, возникающий на нулевом выходе триггера 16, по выходу 31 используется в качестве сигнала окончания процесса подсчета числа единиц и возможности считывания результата с выходов 30.

г .

В данном случае в счетчике 10 сохраняется двоичный код 1000, означающий наличие четырех единиц в ана- лизируемом коде 1001.1010.

Если после очередного тактового импульса на входах элемента И-НЕ 14 устанавливается комбинация 10, то элемент И 11 открывается по третьему и первому входам, а элемент И 12 закрывается по третьему входу. Поэтому очередным тактовым сигналом произво- дятся прибавление 1 к содержимому счетчика 17 и через элемент 15 задержки установка в О соответствую- цего разряда первой половины регистра 1. Время задержки элементом 15 за держки определяется переходными процессами в элементе И 11 (И 12) и , счетчике 17.

Еслиже после очередного импульса на входах элемента И-НЕ 14 устанав- ливается комбинация 01, то открывается элемент И 12 и закрывается элемент И 1, При этом очередным тактовым импульсом из счетчика 17 вычитается 1 и через открытый соответст- вующий элемент И 5 устанавливается в 1 соответствующий разряд второй половины регистра 1.

Пусть в-первую половину регистра принят код 1001, а во вторую - такой же код 1001.

При этих условиях состояние элементов .,,4,52, 1ШИ7,8, И-НЕ14, 9, И10,11,12 до поступления тактового сигнала аналогично рассмотренному выше.

Кроме того, нулевым сигналом с выхода элемента 112 h/ открыт по инверсному входу элемент Ш,,.,. Так как на его прямых входах присутствуют единичные сигналы с единичных выходо старших разрядов обеих половин регистра 1, то элемент И 1 ,открыт, и единичный сигнал с его выхода закрывает по инверсным входам все ос- тальные элементы И 18 группы. Одновременно по второму входу открываетс одноименный элемент И 20 и через элемент ИЛИ 22 открывается по первому входу элемент И 24.

Аналогично единичным сигналом с нулевых выходов предпоследних разрядов обеих половин регистра 1 по прямым входам открыт элемент И 19..,, на обоих инверсных входах которого имеются нулевые сигналы с выходов и

элементов и 19п(гм.

Единичным сигналом с выхода открытого элемента И 19Ы1 аоткрыты по

5

0 5

0

5

5

0

вторым входам элемент И 21ь/2.г и элемент И 24 через элемент ИЛИ 23 и заг крыты по инверсным входам остальные элементы И 19.

Так как элемент И 24 открыт, то открыты и элементы И 20п/2., и 21„,г„ При этом через монтажное ИЛИ открыт дополнительно элемент И 3 ц/г .

Таким образом, элементы И18,19, ИЛИ 22,23,24, И 20 и 21 за счет встречного анализа кодов в регистре 1 обеспечивают формирование условий для переключения дополнительных разрядов обеих половин регистра, содержащих пары комбинаций 11 и 00.

По тактовому сигналу с выхода элемента 15 задержки производится одновременная установка в О первого и четвертого разрядов первой половины регистра 1 через открытые элементы ИЗ, и И , а в 1 - второго и третьего разрядов второй половины регистра 1 через открытые элементы И 5г и 21 .jH элементы ИЛИ б-j и n/2-1 Ри этом после первого тактового импульса в регистре 1 фиксируется код 0000.1111.

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

По завершении цикла подсчета единиц в анализируемом коде регистр 1 и триггер 16 установлены в О, а в счетчике 17 фиксируется результат работы устройства. Для нового цикла в устройство принимается по входам 25 и 26 очередной код в регистр 1, а в счетчик 17 по входам 28 - двоичньй код п/2. После этого по входу 27 подается импульс запуска.

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

Устройство для определения коли- чества единиц в двоичном числе по авт. св. № 1322480, отличаю- |щ е е с я тем, что, с целью повышения быстродействия устройства за счет уменьшения числа тактов его работы, в него введены пятый элемент И, тре тий и четвертый элементы ИЛИ и пятая - восьмая группы элементов И, первый и второй прямые входы 1-го (,2... п/2-1) элемента И пятой группы подключены соответственно к прямым выходам (i+1)-ro и (i+n/2+1)-ro разрядов n-разрядного регистра, первый инверсный вход i-го (,2...n/2-1) элемента И пятой группы подключен к выходу . (i-M)-ro элемента первой группы, выход каждого элемента И пятой группы, кроме первого, соединен с соответствующими инверсными входами всех предыдущих элементов И пятой группы, первыми входами соответствующих элементов И шестой группы и соответствующими вхо- дами третьего элемента ИЛИ, выход ко- |торого соединен с первым входом пятого элемента И, первый и второй прямые входы i-го (,2...п/2-1) элемента И седьмой группы соединены с инверсны- ми выходами соответственно (i+1)-ro и (i+n/2-1)-го разрядов п-раэрядного регистра, первый инверсный вход 1-го (,2...п/2-1) элемента И седьмой группы подключен к выходу (i+1)-ro элемента И третьей группы, выходы кажт

дого элемента И седьмой группы, кроме первого, соединены с соответствующими инверсными входами предыдущих элементов И седьмой группы, первыми входами соответствующих элементов И восьмой группы и соответствующими входами четвертого элемента ИЛИ, выход которого соединен с вторым входом пятого элемента И, выход которого соединен с вторыми входами элементов И шестой и восьмой групп, третьи входы элементов И восьмой группы объединены и подключены к выходу элемента задержки, выход 1-го (, 2...п/2-1) элемента И шестой группы объединен с выходом (1+1)-го элемента И второй группы, выход 1-го (,2..,п/2-1) элемента И восьмой группы соединен с третьим входом (1+1)-го элемента ИЛИ группы.