SU1005026A1

SU1005026A1 - Device for determining number of ones in n-bit number binary code

Info

Publication number: SU1005026A1
Application number: SU813316764A
Authority: SU
Inventors: Виктор Николаевич Горшков; Евгений Павлович Иванюк
Priority date: 1981-07-08
Filing date: 1981-07-08
Publication date: 1983-03-15

Description

Изобретение относитс к вычисЯй .тельной технике и может быть иепользовано в устройствах контрол дискретной информации.The invention relates to computing technology and can be used in discrete information control devices.

Известно устройство дл контрол . двоичных чисел на четность, содержащее распределитель импульсов, фиксирующий триггер, элементы ИЛИ и И и выполн ющее функции определени количества единиц двоичного числа с целью отнесени его к множеству четных или нечетных чисел fl. A device for control is known. binary parity numbers, which contains a pulse distributor, fixing a trigger, OR and AND elements, and performing the functions of determining the number of binary number units in order to assign it to the set of even or odd numbers fl.

Недостатком такого устройства вл етс то, что оно имеет ограни- . ченныё функциональные возможности, так как не позвол ет указывать точное количество значащих разр дов числа.The disadvantage of such a device is that it has a limitation. This functionality does not allow you to specify the exact number of significant bits of a number.

Наиболее близким к предлагаемс лу по технической сущности вл етс устройство дл определени количества единиц в двоичном коде, содержащее счетчик, элементы И, И-НЕ, а в каждс разр де элементы И, ИЛИ, триггер , при этом пр мой выход триггера соединен с первым входом элемента ИЛИ, выход которого подключен к первым входр1М первого и второго элементов И разр да. Шходы первого и второгй элементов И каждого раэр да подключены соответственно -в информационному входу триггера и втог рому входу элемента ИЛИ. Вторые входы первого и второго элементов И вл ютс входами соответственно пр мого и инверсного сигналов соответствующего разр да кода.числа. Выход элемента ИЛИ п-го |разр да соединен с вторыми входами элемента И-НЕ и The closest to the proposed technical entity is a device for determining the number of units in binary code, containing a counter, AND, AND-NOT elements, and, for each bit, AND, OR, trigger elements, with the direct trigger output connected to the first the input of the OR element, the output of which is connected to the first input of the first and second elements of the AND bit. The moves of the first and second elements AND each ray are connected, respectively, at the information input of the trigger and into the input of the element OR. The second inputs of the first and second elements And are the inputs of the direct and inverse signals of the corresponding bit of the code number, respectively. The output of the element OR n-th | bit is connected to the second inputs of the element NAND and

10 выходного элемента Л Первый вход элемента И-НЕ соединен с первыми входами выходного элемента И, трехвходового элемента И, первого и второго элементов И первого разр да 10 output element L The first input of the element AND-NOT is connected to the first inputs of the output element AND, the three-input element AND, the first and second elements AND the first digit

15 и с управл ющим входом устройства. Второй и третий входы трехвходового элемента И соединены соответственно с выходсм элемента Ji-HE и с. входом тактовых импульсов устройства. Вы20 ход трехвходового элемюнта И соединен с синхронизирующими входами триггеров и входом счетчика. Выхода выходного элемента И и счетчика вл ютс соответственно управл ющим 15 and with the control input of the device. The second and third inputs of the three-input element I are connected respectively to the output of the element Ji-HE and c. the input clock of the device. The 20 stroke of the three-input switch and is connected to the trigger inputs of the triggers and the counter input. The outputs of the output element And and the counter are respectively controlling

25 и. информационным выходами устройства С2 3Недостатком этого устройства вч л етс низкое быстродействие.25 and. the information outputs of the C2 device. 3 The disadvantage of this device is low performance.

Цель -изобретени - повыиение быст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.СГ).The goal of the invention is to increase the speed of roaming. The goal is achieved by the fact that. in the device for determining the number of units in binary to de n-bit number containing the counter, the elements AND, AND-NOT, and each i-th bit of the device (i 1,2.,.,. contains the elements AND, OR and the trigger output of which is connected to the first input of the first element OR i-ro bit of the device, the output of which is connected to the first inputs of the first second element AND (1 + 1) of the first bit of the device; the second inputs of the first and second elements AND i-ro bit Yes, the devices are connected to the inputs of the direct and inverse signals i - ro bits of the binary code of the number, respectively, the output The first element OR the n-th bit of the device is connected to the first inputs of the NAND element and the first element. And the second input of the NAND element is connected to the second input of the first element AND, to the first input of the second element AND, to the first inputs of the first and second elements AND the first bit of the device and with the control input of the device operation resolution, the second and third inputs of the second element AND are connected to the output of the NAND element and to the input of the clock pulses of the device, respectively, the output of the second element AND is connected to the synchronization inputs of the trigger ix bits of the device and with the forward input of the counter, the outputs of the first And element and the counter are connected to the control output of the device’s operation and to the information output of the device, respectively, a threshold element is entered, the element is NOT, and in each i-th digit of the device elements and AND, and the output of the threshold element is connected to the input of the element NOT, to the reverse input of the counter, to the first inputs of the third and fourth elements AND ix of the device bits, the outputs of which are connected to the first inputs of the second and third element The devices OR i-ro are the device, respectively, whose outputs are connected to the information input of the trigger and the second input of the first element OR i-rd times the device, respectively, the output of the element is NOT connected to the third inputs of the first and second elements AND the i-ro device bits The outputs of which are connected to the second inputs of the second and third elements OR the i-ro device bit, respectively, the second inputs of the third and fourth elements and the i-ro device bit are connected to the inputs of the direct and inverse signals of the i-th binary signal About the code of the number of respectively / third inputs of the third and fourth elements AND the i-ro bit of the device is connected to the output of the first element OR of the (i- 1) -th bit of the device, the third inputs of the third and fourth elements are And the first bit of the device is connected to The input of the device operation enable, the inputs of the threshold element are connected to the direct and inverse inputs ix of the device bits, respectively. The drawing shows a block diagram of the device. The device contains a counter 1, elements AND 2, AND-NOT 3, AND 4, trigger 5, elements OR b, 7 and 8, AND 9-12, threshold element 13, element NOT 14, input 15 clock pulses of the device, control input 16 enable the device, the input 17 of the direct signal i-ro bit, the input 18 of the inverse signal i-ro bit, control 19 and informational 20 outputs of the device. The elements of the device are connected as follows. The direct output of the trigger 5 of each bit is connected to the input of the element OR 6, the output of which is connected to the inputs of the elements AND 9-12 i + l of the discharge. The outputs of the elements And 9 and 11 are connected to the inputs of the element OR 7, the output of which is connected to the information input of the trigger 5. The outputs of the elements AND 10 and 12 are connected to the inputs of the element OR 8, the output of which is connected to the input of the element OR 6. One of the inputs of the element AND 9 is connected to the input of the element 12 and is the input 17 of the direct signature of the corresponding bit. One of the inputs of the element And 10 is connected to the input of the element And 11 and is the input 18 of the inverse signal of the corresponding bit. The output of the element OR 6 of the last discharge is connected to the inputs of the element AND-NOT 3 and element AND 4. The input of the element AND-NOT 3 is connected to the inputs of the element AND 4, the three-input element AND 2 elements AND 9-12 of the first discharge and with the control input 16 devices. The inputs of the three-input element And 2 connected to the input of 15 clock pulses of the device and the output of the element AND-NOT 3. The output of the three-input element And 2 is connected to the clock inputs of the trigger 5 and one of the inputs of the counter 1. The input of the threshold device 13 is connected to the inputs of the direct 17 and inverse 18 signals of each bit. The output of the threshold device 13 is connected to the input of the element NOT 14, the inputs of the elements 11 and 12 of each bit and to the other input of the counter 1. The output of the element NOT 14 is connected to the inputs 9 and 10 of the elements AND of each bit. The outputs of the element 4 and the counter 1 are respectively the control 19 and the information 20 outputs of the device. ,: The device works as follows. . In the initial state, all the triggers and the counter are reset. The inputs 17 and 18 are supplied with direct and inverse signals from the corresponding bits of the binary code of a number. If in this code the number of units is more than half the maximum number of units, then the threshold element 13 generates a signal at the output, otherwise there is no signal at the output, the threshold element 13 does not. In the latter case, an enable signal is supplied to the inputs of the elements and 9 and 10 of each bit from the output of the HE 14 element, and a prohibitive signal is fed to the inputs of the AND 11 and 12 elements from the output of the threshold element 13. When a control signal arrives at input 16, either preparation of the first bit trigger 5 for switching to the unit state occurs, or the control signal is transmitted through AND 10 and OR 6 on. elements 9-12 of the next bit. The propagation of the control signal ceases at the bit having a single signal at the input 17. A trigger 5 of this bit is prepared to switch to a single state on a signal at the syncating input. When a clock signal arrives, the three-input element 2 produces a signal, and the prepared trigger goes into a single state, which causes further propagation of the control signal until the bit, at the input 17 of which there is a single signal. This process continues until the output of the OR 6 element of the last bit does not receive a signal which, through the element 4, enters the control output of the device, which means that the state of the counter 1 can be shadowed, the contents of which indicate the number synchronization pulses f issued to the triggers 5. This number is equal to the number of clock pulses required to advance the control signal from the first to the last bit, and exactly corresponds to the number of ones in the binary decimal. In the case of the presence of a signal at the output of the threshold element 13, the number corresponding to the maximum number of units in the number of units is written to the counter and the subtraction mode is set. The inputs of the elements 11 and 12 of each bit are supplied with a permitting signal, and the inputs of the elements 9 and 10 of each bits are given a inhibitory signal. When a control signal arrives at input 16, either preparation of the first bit trigger 5 for switching to the single state occurs, or the control signal is transmitted through an AND 12 element and an OR 6 element to AND 9-12 elements of the next bit. The propagation of the control signal is stopped at the bit having a single signal at the input 18. This process continues until, until the output of the element OR 6 of the last bit, the signal through the element 4 does not appear at the control output of the device. The contents of counter 1 correspond to the difference between the maximum possible number of units in the binary code of the number and the number of clock pulses received at the counter equal to the number of zeros in the monitored code, i.e. corresponds to the number of units in this code number. This device has a higher speed than the device prototype. Indeed, if all code combinations are equal, then the average time for determining the number of units in a binary code of a number containing an odd number. The number of bits for a prototype device is -2 ..,. + With ic + - h cj n - s (c is the number of digits for the number; -the arrival time of the clock pulses; -the device operation time if there are i units in the number code. The average time for determining the number of units for this device, provided that the threshold element works in accordance with the expression 0 when number of units in binary code Sla, equals J ± L LI) 2.SG).

Дл n SjS-r , 7 2,4С.For n SjS-r, 7 2.4C.

Таким образом, выигрьпи в быстродействии при условии контрол семиразр дных равноверо тных кодовых комбинаций составл ет 1,5 раз.Thus, gains in speed, subject to the control of seven-bit uniform code combinations, are 1.5 times.

Claims

1. Author's certificate of the USSR 428385, cl. G 06 F 11/10, 1972.

2. Author's certificate of the USSR 716041, cl. G 06F 11/10, 1977 (prototype)