Устройство для определения количества единиц в двоичном коде N-разрядного числа Советский патент 1983 года по МПК G06F5/02 

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

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

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

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

10 выходного элемента Л Первый вход элемента И-НЕ соединен с первыми входами выходного элемента И, трехвходового элемента И, первого и второго элементов И первого разряда

15 и с управляющим входом устройства. Второй и третий входы трехвходового элемента И соединены соответственно с выходсм элемента Ji-HE и с. входом тактовых импульсов устройства. Вы20ход трехвходового элемюнта И соединен с синхронизирующими входами триггеров и входом счетчика. Выхода выходного элемента И и счетчика являются соответственно управляющим

25 и. информационным выходами устройства С2 3Недостатком этого устройства явч ляется низкое быстродействие.

Цель -изобретения - повыиение быст30родействия. Поставленная цель достигается тем, что. в устройство для определе ния количества единиц в двоичном к де п-разрядного числа, содержащее счетчик, элементы И, И-НЕ, а кажды i-й разряд устройства (i 1,2.,.,. содержит элементы И, ИЛИ и триггер выход которого соединен с первым входом первого элемента ИЛИ i-ro разряда устройства, выход которого подключен к первым входам первого второго элементов И (1 + 1)- го разря да устройства; вторые входы первого и второго элементов И i-ro разр да устройства соединены с входами прямого и инверсного сигналов i--ro разряда двоичного кода числа соответственно, выход первого элемента ИЛИ п-го разряда устройства соединен с первыми входами элемента И-НЕ и первого элемента И второй вход элемента И-НЕ соединен с вторым входом первого элемента И, с первым входом второго элемента И, с первыми входами первого и второго элементов И первого разряда устройства и с управляющим входом разрешения работы устройства, второй и третий входы второго элемента И соединены с выходом элемента И-НЕ и с входом тактовых импульсов устройства соответственно, выход второго элемента И соединен с синхронизирующими входами триггеров i-x разрядов устройства и с прямым входом счетчика, выходы первого элемента И и счетчика подключены к управляющему выходу окончания работы устройства и к информационному выходу устройства соответственно, введены пороговый элемент, элемент НЕ, а в каждый i-й разряд устройства введены элемелты И и ИЛИ, причем выход порогового элемента подключен к входу элемента НЕ, к реверсивному входу счетчика, к первым входам третьего и четвертого элементов И i-x разрядов устройства, выходы которых соединены с первыми входами второго и третьего элементов ИЛИ i-ro разряда устройства соответственно, выходы которых подключены к информационному входу триггера и второму входу первого элемента ИЛИ i-rd раз ряда устройства соответственно, выход элемента НЕ подключен к третьим входам первого и второго элементов И i-ro разряда устройства, выходы которых соединены с вторыми входами второго и третьего элементов ИЛИ i-ro разряда устройства соответстве но, вторые входы третьего и четвертого элементов И i-ro разряда устройства подключены к входам прямого и инверсного сигналов i- го разряда двоичного кода числа соответст венно/ третьи входы третьего и четвертого элементов И i-ro разряда устройства соединены с выходом первого элемента ИЛИ (i- 1)-го разряда устройства, третьи входы третьего и четвертого элементов И первого разряда устройства соединены с управляющим входом разрешения работы устройства, входы порогового элемента соединены с прямыми и инверсными входами i-x разрядов устройства соответственно. На чертеже представлена структурная схема устройства. Устройство содержит счетчик 1, элементы И 2, И-НЕ 3, И 4, триггер 5, элементы ИЛИ б, 7 и 8, И 9-12, пороговый элемент 13, элемент НЕ 14, вход 15 тактовых импульсов устройства, управляющий вход 16 разрешения работы устройства, вход 17 прямого сигнала i-ro разряда, вход 18 инверсного сигнала i-ro разряда, управляющий 19 и информационный 20 выходы устройства. Элементы устройства соединены следующим образом. Прямой выход триггера 5 каждого разряда соединен с входом элемента ИЛИ 6, выход которого подключен к входам элементов И 9-12 i+l разряда. Выходы элементов И 9 и 11 соединены с входами элемента ИЛИ 7, выход которого подключен к информационному входу триггера 5. Выходы элементов И 10 и 12 подключены к входам элемента ИЛИ 8, выход которого соединен с входом элемента ИЛИ 6. Один из входов элемента И 9 соединен с входом элемента И 12 и является входом 17 прямого сигнгша соответствующего разряда. Один из входов элемента И 10 соединен с входом элемента И 11 и является входом 18 инверсного сигнала соответствующего разряда. Выход элемента ИЛИ 6 последнего разряда соединен с входами элемента И-НЕ 3 и элемента И 4. Вход элемента И-НЕ 3 соединен с входами элемента И 4, трехвходового элемента И 2 элементов И 9-12 первого разряда и с управляющим входом 16 устройства. Входы трехвходового элемента И 2 соединены с входом 15 тактовых импульсов устройства и с выходом элемента И-НЕ 3. Выход трехвходового элемента И 2 соединен с синхронизирующими входами триггеров 5 и с одним из входов счетчика 1. Вход порогового устройства 13 соединен с входами прямого 17 и инверсного 18 сигналов каждого разряда. Выход порогового устройства 13 соединен с входом элемента НЕ 14, входами элементов И 11 и 12 каждого разряда и с другим входом счетчика 1. Выход элемента НЕ 14 соединен с входами 9 и 10 элементов И каждого разряда. Выходы элемента И 4 и счетчика 1 являются соответственно управляющим 19 и информационным 20 выходами устройст ва. ,: Устройство работает следующим об разом. . В исходном состоянии все триггеры и счетчик обнулены. На входы 17 и 18 подаются прямой и инверсный сигналы от соответствующих разрядов двоичного кода числа. Если в этом коде количество единиц больше половины максимального количества единиц, то пороговый элемент 13 формирует на выходе сигнал, в противном случае сигнала,на выходе порогового элемента 13 нет. В последнем слу чае на входы элементов и 9 и 10 каж дого разряда с выхода элемента НЕ 14 подается разрешающий сигнал, а на входы элементов И 11 и 12 с выхода порогового элемента 13 подае ся запрещающий сигнал. При поступлении на вход 16 управляющего сигнала происходит либо подготовка триггера 5 первого разряда к переходу в единичное состояние, либо пе редача управляющего сигнала через элемент И 10 и элемент ИЛИ 6 на. элементы И 9-12 следующего разряда Распространение управляющего сигнала прекращается на разряде, имеющем на входе 17 единичный сигнал. Триггер 5 этого разряда подготавливается к тому, чтобы по сигналу на синх ронизирующем входе переключиться в единичное состояние. При поступлении тактового сигнала трехвходовый элемент И 2 выдает сигнал, и подготовленный триггер переходит в .единичное состояние, что вызывает дальнейшее распространение управляющего сигнала до того разряда, на входе 17 которого имеется единич ный сигнал. Этот процесс продолжается до тех пор, пока на выходе элемента ИЛИ 6 последнего разряда не появляется сигнал, который через элемент И 4 поступает на управ ляющий выход устройства, что означает возможность л тения состояния счетчика 1, содержимое которого по казывает число импульсов синхрониз ции f выданных на триггеры 5. Это число равно числу тактовых импульс потребовавшихся для продвижения уп равл5иощего сигнала от первого до последнего разряда, и точно соответствует числу единиц в двоичном де числа. В случае наличия сигнала на выходе порогового элемента 13 в счет чик записывается число, соответствующее максимальному количеству единиц в кбде числа и устанавливается режим вычитания. На входы эле ментов И 11 и 12 каждого разряда подается разрешающий сигнал, а на входы элементов И 9 и 10 каждого разряда - запрещающий сигнал. При поступлении на вход 16 управляющего сигнала происходит либо подготовка триггера 5 первого разряда к переходу в единичное состояние, либо передача управляющего сигнала черрз элемент И 12 и элемент ИЛИ 6 на элементы И 9-12 следующего разряда. Распространение управляющего сигнала прекращается на разряде, имеющем на входе 18 единичный сигнал. Этот процесс продолжается до тех пор, -пока на выходе элемента ИЛИ 6 последнего разряда не появляется сигнал, который черезэлемент И 4 поступает на управляющий выход устройства. Содержимое счетчика 1 соответствует разности между максимально возможным количествбм единиц в двоичном коде числа и количеством тактовых импульсов, поступивших на счетчик, равном количеству нулей в контролируемом коде, т.е. соответствует количеству единиц в этом коде числа. Данное устройство обладает более высоким быстродействием, чем устройство-прототип. Действительно, если все кодовые комбинации равновероятны, то среднее время определения количества единиц в двоичном коде числа, содержащем нечетно.е число разрядов, для устройства-прототипа равно -2..,.+ с i-c +- ч- cj п -с (с -количество разрядов де числа; -период поступления тактовых импульсов; -время работы устройства при наличии i единиц в коде числа. Среднее время определений количества единиц для данного устройства при условии, что пороговый элемент работает в соответствии с выражением0при 1при где - количество единиц в двоичном коде числа, равноJ ±L ЛИ ) 2.СГ).

Для n SjS-r , 7 2,4С.

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

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

Устройство для определения количества единиц в двоичном коде п-разрядного числа, содержащее счетчик, элементы И, Н-НЕ, а каждый i-й разряд устройства (i 1,2,,..,п) содержит элементы И, ИЛИ и триггер, выход которого соединен с первым входом первого элемента ИЛИ i-ro разряда устройства, выход которЪго подключен к первым входам первого и второго элементов И (i-t-l)-ro раз ряда устройства, вторые входы первого и второго элементов И i-ro разряда устройства соединены с входами прямого и инверсного сигналов i-ro разряда,двоичного кода числа соответственно; выход первого элемента ИЛИ. п-го разряда устройства (Соединен с первыми входами элемента И-НЕ и первого элемента И, второй вход элемента И-НЕ соединен с вторы входом первого элемента И, с первым входом второго элемента И, с первыми входами первого и второго элементов И первого разряда устройства и с управляющим входом разрешения работы устройствам второй и тре тий входы второго элемента И соединены с выходом элемента И-НЕ и с входом тактовых импульсов устройства соответственно, выход второго элемента И соединен с синхронизирующими входами триггеров i-x разря цов устройства и с прямым входом счетчика/ выходы первого элемента М и счетчика подключены к управляющему выходу окончания работы устройства и к информационному выходу устройства соответственно-, отличающееся- теМу что, с целью повышения быстродействия, в устройство введены пороговый элемент, элемент НЕ, а вкаждый i-й разряд устройства введены 1элеме.нты И и ИЛИ причем выход порогового элемента подключен к входу элемента НЕ, к реверсивному входу -счетчика, к первым входам третьего и четвертого элементов И i-x разрядов устройства, выходы которых.соединены с первыми входами второго и третьего элементов ИЛИ i-ro разряда устройства соответственно, выходы которых подключены к информадионному входу триггера и второму входу первого элемента ИЛИ i-ro разряда устройства соответственно, выход элемента НЕ подключен к третьим входам первого и второго элементов И i-ro раэряда устройства, выходы которых соединены с вторыми входами, второго и третьего элементов ИЛИ i-ro разряда устройства соответственно, вторые входы третьего и четвертого элементов И i-ro разряда устройства подключены к входам прямого и инверсного сигналов i-ro разряда двоичного кода числа соответственно, третьи входы третьего и четвертого элементов И i-ro разряда устройства соединены с выходом первого элемента ИЛИ (i-l)-ro разряда устройства, третьи входы третьего и четвертого элементов И первого разряда устройства соединены с управляющим входом ра13решения работы устройства, входы порогового элемента соединены с прямыми и инверсными входами i-x разрядов устройства co ответственно.

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

1.Авторское свидетельство СССР 428385, кл. G 06 F 11/10, 1972.

2.Авторское свидетельство СССР 716041, кл. G 06F 11/10, 1977 (прототип)