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

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

Иллюстрации

Показать все

Реферат

 

ОП ИСАНИЕ

ИЗОБРЕТЕНИЯ

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

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

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

Республик рц 1 005026 (61) Дополнительное к авт. свид-йу— (22) Заявлено 080781 (21) 3316764/18-24

)5 ) М Кл з

G 06 F 5/02 с присоединением заявки ¹

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

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

Опубликовано 150383. Бюллетень ¹ 10

tS3)УДК 681.3 (088.8) Дата опубликования описания 150383 (72) Авт оры изобретения

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

ЕДИНИЦ В ДВОИЧНОМ КОДЕ и-РАЗРЯДНОГО ЧИСЛА

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

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

И и выполняющее функции определения количества единиц двоичного числа с целью отнесения его к множеству четных или нечетных чисел (11.

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

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

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

Второй и третий входы трехвходового элемента И соединены соответственно с выходом элемента И-HE и с. входом тактовых импульсов устройства. Вы- . ход трехвходового элемента И соединен с синхронизирующими входами триггеров и входом счетчика. Вйходы выходного элемента И и счетчика являются .соответственно управляющим и.информационным выходаве устройства (2 ).

Недостаткси этого устройства яв ляется низкое быстродействие.

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

1005026

Поставленная цель достигается тем, что. в устройство для определения количества единиц в двоичном коде и-разрядного числа, содержащее счетчик, элементы И, И-НЕ, а каждый

1-й разряд устройства (i = 1,2,..., ) содержит элементы И, ИЛИ и триггер, выход которого соединен с первым входом первого элемента ИЛИ i-го разряда устройства, выход которого подключен к первым входам первого и !О второго элементов И (i+1)- го разряда устройства; вторые входы первого и второго элементов И i-ro разряда устройства соединены с входами прямого и инверсного сигналов i-ro разряда двоичного кода числа соответственно, выход первого элемента

ИЛИ n-ro разряда устройства соединен с первыми входами элемента И-НЕ и первого элемента И, второй вход элемента И-НЕ соединен с вторым входом первого элемента И, с первым входом второго элемента И, с пер- выми входами первого и второго эле- ментов И первогo разряда QcTpoAGTBB 25 и с управляющим входом разрешения работы устройства, второй и третий входы второго элемента И соединены с выходом элемента И-НЕ и с входом тактовых импульсов устройства соответственно; выход второго элемента

И соединен с синхронизирующими входами триггеров i-x разрядов устройства и с прямым входом счетчика, выходы первого элемента И и счетчика подключены к управляющему выхо- 35 ду окончания работы устройства и к информационному выходу устройства соответственно, введены пороговый элемент, элемент НЕ, а в каждый

i-й разряд устройства введены эле- Щ менты И и ИЛИ, причем выход порогового элемента подключен к входу элемента НЕ, к реверсивному входу счетчика, к первым входам третьего и четвертого элементов И 1-х разрядов устройства, выходы которых соединены с первыми входами второго и третьего элементов ИЛИ а-го разряда устройства соответственно, выходы которых подключены к информационному входу триггера и второму входу первого элемента ИЛИ i-ro разряда устройства соответственно, вы ход элемента НЕ подключен к третьим входам первого и второго элементов

И i-го разряда устройства, выходы которых соединены с вторыми входами второго и третьего элементов ИЛИ

i-ro разряда устройства соответственно, вторые входы третьего и четвертого элементов И i-ro разряда уст- 60 ройства подключены к входам прямого и инверсного сигналов i-го разряда двоичного кода числа соответственно, третьи входы третьего и четвертого элементов И 1-го разряда 65 устройства соединены с выходом первого элемента ИЛИ (i- 1)-го разряда устройства, третьи входы третьего и четвертого элементов И первого разряда устройства соединены с управляющим входом разрешения работы устройства, входы порогового элемента соединены с прямыми и инверсными входами i-x разрядов устройства соответственно.

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

Устройство содержит счетчик 1, элементы И 2, И-НЕ 3, И 4, триггер

5, элементы ИЛИ 6, 7 и 8, И 9-12, пороговый элемент 13, элемент НЕ 14, вход 15 тактовых импульсов устройства, управляющий вход 16 разрешения работы устройства, вход 17 прямого сигнала i-ro разряда, вход 18 инверсного сигнала 1-го разряда, управляющий 19 и информационный 20 выходы устройства.

Элементы устройства соединены слецующим образом.

Прямой выход триггера 5 каждого разряда соединен с входом элемента

ИЛИ 6, выход которого подключен к входам элементов И 9-12 i+1 разряда. Выходы элементов И 9 и 11 соеди-. нены с входами элемента ИЛИ 7, выход которого подключен к информационному входу триггера 5. Выходы элементов И 10 и 12 подключены к входам элемента ИЛИ 8, выход которого соединен с входом элемента

ИЛИ 6. Один из входов элемента И 9 соединен с входом элемента И 12 и является входом 17 прямого сигнала соответствующего разряда. Один из входов элемента И 10 соединен с входом элемента И 11 и является входом

18 инверсного сигнала соответствующего разряда. Выход элемента ИЛИ 6 последнего разряда соединен с входами элемента И-НЕ 3 и элемента

И 4. Вход элемента И-HE 3 соединен с входами элемента И 4, трехвходового элемента И 2 элементов И 9-12 первого разряда и с управляющим входом 16 устройства. Входы трехвходового элемента И 2 соединены с входом 15 тактовых импульсов устройства и с выходом элемента И-НЕ 3 ° Выход трехвходового элемента И 2 соединен с синхронизирующими входами триггеров 5 и с одним из входов счетчика 1. Вход порогового устройства 13 соединен с входами прямого

17 и инверсного 18 сигналов каждого разряда. Выход порогового устройства 13 соединен с входом элемента НЕ 14, входами элементов И

11 и 12 кажцого разряда и с другим входом счетчика 1. Выход элемента

НЕ 14 соединен с входами 9 и 10 элементов И каждого разряда. Выходы! нi 5026 элемента И 4 и счетчика 1 являются соответственно управляющим 19 и информационным 20 выходами устройства.

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

В исходном состоянии все триггеры и счетчик обнулены. На входы 17 и 18 подаются прямой и инверсный сигналы от соответствующих разрядов двоичного кода числа. Если в этом коде количество единиц больше -половины максимального .количества единиц, то пороговый элемент 13 формирует на выходе сигнал, в противном случае сигнала на выходе порогово- IS го элемента 13 нет. В последнем случае на входы элементов И 9 и 10 каждого разряда с выхода элемента

НЕ 14 подается разрешающий сигнал, а на входы элементов И 11 и 12 с 2р выхода порогового элемента 13 подается запрещающий сигнал. При поступлении на вход 16 управляющего сигнала происходит либо подготовка триггера 5 первого разряда к переходу в единичное состояние, либо передача управляющего сигнала через элемент И 10 и элемент HJIH 6 на элементы И 9-12 следующего разряда.

Распространение управляющего сигна- 3О ла прекращается на разряде, имеющем на входе 17 единичный сигнал. Триггер 5 этого разряда подготавливается к тому, чтобы по сигналу на синхронизирующем входе переключиться в единичное состояние ° При поступлении тактового сигнала трехвходо вый элемент И 2 выдает сигнал, и подготовленный триггер переходит в ,единичное состояние, что вызывает дальнейшее распространение управ- 4О ляющего сигнала до того разряда, на входе 17 которого имеется единичный сигнал. Этот процесс продолжается до тех пор, пока на выходе элемента ИЛИ 6 последнего. разряда 45 не появляется сигнал, который через элемент И 4 поступает на управляющий выход устройства, что означает возможность чтения состояния счетчика 1, содержимое которого показывает число импульсов синхронизации выданных на триггеры 5. Это число равно числу тактовых импульсов, потребовавшихся для продвижения управляющего сигнала от первого до последнего разряда, и точно соответствует числу единиц в двоичном ко де числа. и+1

0 пРи п+1

1 при количество единиц в двоичном где коде числа, равно..+ Сп-22+ С"-" и и

В случае наличия сигнала на выходе порогового элемента 13 в счетчик записывается число, соответствующее максимальному количеству единиц в коде числа и устанавливается режим вычитания. На входы элементов И 11 и 12 каждого разряда подается разрешающий сигнал, а на входы элементов И 9 и 10 каждого разряда — запрещающий сигнал. При поступлении на вход 16 управляющего сигнала происходит либо подготовка триггера 5 первого разряда к переходу в единичное состояние, либо передача управляющего сигнала через элемент И 12 и элемент ИЛИ 6 на элементы И 9-12 следующего разряда. Распространение управляющего сигнала прекращается на разряде, имеющем на входе 18 единичный сигнал. Этот процесс продолжается до тех пор, .пока на выходе элемента

ИЛИ 6 последнего разряда не появляется сигнал, который через элемент

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

:числа.

Данное устройство обладает более высоким быстродействием, чем устройство-прототип.

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

Т = — (С 7ь+ с -2 +...+C j7ü+.. + с п 7у (и

2 где n — количество разрядов в коде числа;

Т вЂ” период поступления тактовых импульсов;

С вЂ” время работы устройства и при наличии i единиц в коде числа.

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

1005026

Дли и = 7Т = 3 5 i Т = 2,4 ь, I I сй—

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

Формула изобретения устройство для определения количества единиц в двоичном коде и-разрядного числа, содержащее счетчик, элементы И, И-НЕ, а каждый i-й разряд устройства (i = 1,2,...,n) содержит элементы И, ИЛЙ и триггер, выход которого соединен с первым 35 входом первого элемента ИЛИ i-ro разряда устройства, выход которого подключен к первым входам первого и второго элементов И (i+1)-го раэ ряда устройства, вторые входы пер- 20 вого и второго элементов И i-го . разряда устройства соединены с входами прямого и инверсного сигналов

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

И-НЕ и первого элемента И, второй вход элемента И-НЕ соединен с вторым входом первого элемента И, с пер- yg вым входом второго элемента И, с первыми входами первого и второго элементов И первого разряда устройства и с управляющим входом разрешения работы устройства» второй и третий входы второго элемента И соединены с выходом элемента И-НЕ и с входом тактовых импульсов устройства соответственно, выход второго элемента И соединен с синхронизирующими входами триггеров i-х разрядов устройства и с прямым входом счетчика, выходы первого элемента

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

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

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

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

У 428385, кл. G 06 F 11/10, 1972.

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

9 716041, кл. G 06F 11/10, 1977 (прототип).

1005026

Составитель В. Кайданов

Редактор Л. Алексеенко Техред N.Koøòóðà Корректор Ji. Бокшан

Эаказ 1899/63 Тираж 704 Подписное

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

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

Филиал ППП "Патент", г. Ужгород, ул. Проектная, 4