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

 

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

союз советских социАлистичесних

РЕСПУБЛИК

А2,ЯО„„И47072

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

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ пО изОБРетениям и ОтнРытиям

ПРИ ГКНТ СССР (61) 1322480

1 (21) 4440259/24-24 (22) 13.06.88 (46) 28.02.90. Вюл. Ф 8 (72) В.Г.Попов, Б.В.Панца и С.А.Шибаев (53) 621.396(088.8) (56) Авторское свидетельство СССР

Ф 1322480, кл. Н 03 M 7/04, 1986. (54) УСТРОЙСТВО ДЛЯ ОПРЕДЕЛЕНИЯ .КОЛИЧЕСТВА ЕДИНИЦ В ДВОИЧНОМ ЧИСЛЕ (57) Изобретение относится к вычислительной технике и может быть исИзобретение относится к вычислительной технике и может быть использовано для контроля цифровой информации.

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

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

Устройство содержит п-разрядный регистр 1, первую 2, вторую 3, третью 4 и четвертую 5 группы элементов

И, группу элементов ИЛИ 6, первый 7 и второй 8 элементы ИЛИ, элемент ИЛИНЕ 9, первый 10, второй 11, третий 12 и четвертый 13 элементы И, элемент

-HE 14, элемент 15 задержки, триггер 16, реверсивный счетчик 17, пятую 18, седьмую 19, шестую 20 и восьмую 21 группы элементов И, третий 22 и четвертый 23 элементы ИЛИ, пятый элемент И 24, первые 25 и вторые 26

{51)5 и 03 И 7/04. С 06 Г 11/10

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

29, информационные 30 и управляющий

31 выходы устройства.

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

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

Обозначим буквой Š— общее количество единиц в двоичном коде; E,Å г количество единиц в первой и второй половинах исходного кода соответственно; Нг — количество нулей во второй половине исходного кода.

Тогда

Е=Е 1+В г=Е „+Е г+и/2-n/2 =(Е „— {n/2Ег)1+"/2=Е,-Н,+и/г, 1547072!

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

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

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

Если в анализируемой паре комбинация

00, то раэность равна -1 и из счетчика следует вычесть единицу. Если комбинация равна 01 либо 10, то содержимое счетчика остается без изменения.

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

11 и 00 °

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

30 в анализируемом коде нескольких пар разрядов, первая из которых содержит код 11, а вторая - 00.

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

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

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

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

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

При этом элемент И 2, открыт, Единичный сигнал с его выхода по одноименным инверсным входам закрывает последующие элементы И 2, поступает на второй вход элемента И 3 и через

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

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

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

Так товый сиги ал, по ступающий по входу 29 через открытый элемент И 13, не воздействует на состояние счетчика 17, а устанавливает после прохождения элемента 15 задержки в "0" через открытый элемент И 3, первый разряд первой половины регистра 1 и в

"1" через открытый элемент И 5 и элемент ИЛИ 6 второй разряд второй половины регистра 1, Таким образом, после тактового импульса в регистре 1 фиксируется код 0001.1110.

После этого на выходах элементов

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

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

В данном случае в счетчике 10 сохраняется двоичный код 1000, ознаУстройство для определения коли чества единиц в двоичном числе по авт. св. Р 1322480, о т л и ч а юjm е е с я тем, что, с целью повышения быстродействия устройства за счет уменьшения числа тактов его работы, в него введены пятый элемент И, тре тий и четвертый элементы ИЛИ и пятая— восьмая группы элементов И, первый и второй прямые входы i-. ãî (i=1,2.. °

n/2-1) элемента И пятой группы подключены соответственно к прямым выходам (i+1)-го и (i+n/2+1)-го разрядов и-разрядного регистра, первый инверс50

5 154707 чающий наличие четырех единиц в анализируемом коде 1001. 1010.

Если после очередного тактового импульса на входах элемента И-HE 14

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

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

"1" соответствующий разряд второй половины регистра 1.

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

При этих условиях состояние элементов И2,,3„,4,5, ИЛИ7,8, И-НЕ14, 9, И10,11,12 до поступления тактового сигнала аналогично рассмотренному выше, Кроме того, нулевым сигналом с выхода элемента И2 открыт по инверсному входу элемент И18„,. Так как на его прямых входах присутствуют 40 единичные сигналы с единичных выходов старших разрядов обеих половин регистра 1» элемент И 18ь/,,откр т и единичный сигнал с его выхода за-. крывает по инверсным входам все ос- 45 тальные элементы И 18 группы. Одновременно по второму входу открывается одноименный элемент И 20 и через элемент ИЛИ 22 открывается по первому входу элемент И 24.

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

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

2 6 вторым входам элемент И 21 ыа-1 и эле мент И 24 через элемент ИЛЙ 23 и за=. крыты по инверсным входам остальные

\ элементы И 19.

Так как элемент И 24 открыт, то открыты и элементы И 20 „, и 21„/

При этом через монтажное ИЛИ открыт дополнительно элемент И 3 „1 .

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

По тактовому сигналу с выхода элемента 15 задержки производится одновременная установка в "0" первого и четвертого разрядов первой половины регистра 1 через открытые элементы И 3, и,И 3„1,, а в "1 — второго и тре тье го разрядов второй половины регистра 1 через открытые элементы

И 5 и 21 „ и элементы ИЛИ 6 и

6 д, . При этом после первого тактового импульса в регистре 1 фиксируется код 0000.1111.

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

По завершении цикла подсчета единиц в анализируемом коде регистр 1 и триггер 1 6 установлены в "0", а в счетчике 17 фиксируется результат работы устройства. Для нового цикла в устройство принимается по входам 25 и 26 очередной код в регистр

1, а в счетчик 17 по входам 28— двоичный код n/2. После этого по входу 27 подается импульс запуска.

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

1547072 ный вход i- ro (i=1, 2... n/2-1 ) элемента И пятой группы подключен к выходу ,(i+1)-го элемента первой группы, выход каждого эцемента И пятой груп™. 5 кроме первого, соединен с соответствующими инверсными входами всех предыдущих элементов И пятой группы, первы ми входами соответствующих элементов И шестой группы и соответствующими вхо- 10 дами третьего элемента ИЛИ, выход ко торого соединен с первым входом пятого элемента И, первый и второй прямые уходы i-го (ь =1,2...n/2-1) элемента И ,седьмой группы соединены с инверсны ми выходами соответственно (х+1)-го .и (д+и/2-1)-го разрядов и-разрядного регистра, первый инверсный вход i-го ,(i 1,2...n/2-1) элемента И седьмой группы подключен к выходу (л.+1)-го 2О элемента И третьей группы, выходы каж-, I дого элемента И седьмой группы, кроме первого, соединены с соответствующими инверсными входами предыдущих элементов И седьмой группы, первыми входами соответствующих элементов И восьмой группы и соответствующими входами четвертого элемента ИЛИ, выход которого соединен с вторым входом пятого элемента И, выход которого соединен с вторыми входами элементов И шестой и восьмой групп, третьи входы элементов И восьмой группы объединены и подключены к выходу элемента задержки, выход i-го (i=1, 2...n/2-1) элемента И шестой группы объединен с выходом (i+1)-ro эле.— мента И второй группы, выход i-го (i=1,2...n/2-1) элемента И восьмой группы соединен с третьим входом (i+1)-го элемента ИЛИ группы.!

547072

Составитель О.Неплохов

Редактор А.Лежнина Техред Л.Сердокова Корректор Б.Гирняк

Заказ 85 Тираж б61 Подписное

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

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

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