Устройство для вычисления суммы квадратов к числоимпульсных величин

 

УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ СУММЫ КВАДРАТОВ К ЧИСЛОИМПУЛЬСНЫХ ВЕЛИЧИН, содержащее элемент ИЛИ, счетчик, первую группу элементов И, элемент задержки, накапливающий сумматор , выход которого является выходом устройства, разрядные выходы счетчика соединены соответственно с первыми входами элементов И первой группы, отличающеес я тем, что, с целью повышения быстродействия, в него введены М-1 групп элементов И (М - разрядность кода числа входных шин), Н-1 элементов задержки, группа элементов ИЛИ, шифратор, входы которого соединены с входными шинами устройства соответственно и входами элемента ИЛИ, выход которого через элемент задержки подключен к счетному входу счетчика , разрядные выходы которого соединены с первыми входами элементов И всех групп соответственно, первый выход шифратора соединен с вторыми входами элементов И первой группы и мпадшим разрядом накапливающего сумматора, i-й выход шифратора соединен через соответствующий § элемент задержки (,3,...,М) с вторыми входами элементов И i-й груп (Л пы и первым входом соответствующего элемента ИЛИ группы, выход элемента И i-й группы (,2,...,N) , ...,М, где N - разрядность счетчика соединен с соответствующим входом ()-ro элемента ИЛИ группы , выход (i+j-1)-ro элемента ИЛИ группы соединен с соответствующим входом накапливающего сумматора.

СОЮЗ СОВЕТСКИХ

СОЦИАЛ ИСТИЧЕСНИХ

РЕСПУБЛИК (19) (1Ь

3(51) С 06 F 7/552

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

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3512609/18-24 (22) 09. 11.82 (46) 15.05.84. Бюп; Ф 18 (72) В.А.Добрыдень (71) Харьковский инженерно-строительный институт (53) 681.325 (088.8) (56) 1. Авторское свидетельство СССР

В 475619, кл. G 06 F 7/38, 1975.

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

Ф 717759, кл. С 06 F 7/552, 1980 (прототип). (54)(57) УСТРОЙСТВО ДЛЯ ВЫЧИСЛЕНИЯ

СУММЫ КВАДРАТОВ К ЧИСЛОИМПУЛЬСНЫХ

ВЕЛИЧИН, содержащее элемент ИЛИ, счетчик, первую группу элементов И, элемент задержки, накапливающий сумматор, выход которого является выходом устройства, разрядные выходы счетчика соединены соответственно с первыми входами элементов И первой группы, о т л и ч а ю щ е е— с я тем, что, с целью повышения быстродействия, в него введены M-1 групп элементов И (M — разрядность кода числа входных шин), M-1 элементов задержки, группа элементов ИЛИ, шифратор, входы которого соединены с входными шинами jjcTpoHcTBB соответственно и входами элемента ИЛИ, выходд которого чер е 3 элемент задержки подключен к счетному входу счетчика, разрядные выходы которого соединены с первыми входами элементов И всех групп соответственно, первый выход шифратора соединен с вторыми входами элементов И первой группы и младшим разрядом накапливающего сумматора, -й выход шифратора соединен через соответствующий элемент задержки (i=2,3,...,М) с

Ф

Я вторыми входами элементов И j-й группы и первым входом соответствующего . элемента ИЛИ группы, выход 1-ro элемента И i-й группы (j=1 2,. ° .,N)

i=1, ...,И, где N — разрядность счет- р чика соединен с соответствующим входом (i+j-1)-ro элемента ИЛИ группы, выход (i+j-1)-го элемента ИЛИ группы соединен с соответствующим входом накапливающего сумматора.

1092500

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

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

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

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

Недостатками известного устройства являются невысокое быстродействие, а также сложность схемы, обусловленная наличием в его составе К формирователей строб-импульсов, а также избыточного разряда счетчика (его первый разряд всегда находится в единичном состоянии) и соответственно элементов И группы.

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

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

М-1 групп элементов И (M — разрядность кода числа входных шин), М-1 элементов задержки, группа элементов ИЛИ, шифратор, входы которого соединены с входными шинами устройства соответственно и входами элемента ИЛИ, выход которого через элемент задержки подключен к счет(2) 35 ному входу счетчика, разрядные выходы которого соединены с первыми входами элементов И всех групп соответственно, первый выход шифратора соединен с вторыми входами элементов И первой группы и младшим разрядом накапливающего сумматора, 5 -й выход шифратора соединен через соответствующий элемент задержки (i

t0

2, 3,..., M) с вторыми входами элементов И i-й группы и первым входом соответствующего элемента ИЛИ группы, выход j-го элемента И i-й группы ()= 1,2,...,N, х =1,2,...,Г1, где N— разрядность счетчика 1соединен с соответствующим входом (i+j — 1)-го элемента ИЛИ группы, выход (i+j — 1)-го элемента ИЛИ группы соединен соответствующим входом накапливающего сумматора.

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

Устройство содержит шифратор 1, элемент ИЛИ 2, элементы 3, 4 и 5 задержки, счетчик 6, группы элементов И 7, Я и 9, группу элементов

ИЛИ 10, накапливающий сумматор 11.

В основу принципа действия изобретения положено следующее представление квадрата числа:

m2 = a (2i+1) (1)

c,—

i::0

Пусть входные величины m m з

m „удовлетворяют условию

mÄ(m < ... < ш„.

Тогда из условия (1) следует л -1 ч

2 2 2 " 2 - -1 -(2+ ) 1ж-4) °

2 о

"2 1 п1 -ч

40 . (. +X (.+,i,5

m1 пчъ-1

Необходимыми условиями работы устройства являются одновременность начала формирования всех величин rq

45 а также синхронность импульсов на всех входах (зти импульсы могут, например, формироваться одним и тем же генератором). При этом число входных величин, формирование значе50 ний которых не .закончено (число входов, на которые в очередном такте поступают импульсы, будем говорить число ненулевых входных сигналов), является невозрастающей во времени величиной. Обозначим число ненулевых входных сигналов в момент начала их формирования (т.е. число входов устройства, на которые поступят перз 109 2500 вые импульсы входных пакетов) К„.

В некоторый момент заканчивается формирование одной или нескольких одновременно входных величин, число оставшихся ненулевых входных сигна- 5 лов обозначим К (очевидно, К„«<К

К сК) . Если К>40, то в некоторый момент число ненулевых входных сигналов снова уменьшается — до К и т.д., пока не завершится формирование максимальной из входных величин.

Таким образом, получаем убывающую во времени последовательность К1)К К ...)

)Kg = О, где В(K>. Пусть переход от К, к К, ненулевых входных величин совершается после и входных импульсов (тактов), переход от К> к К> после и, входных импульсов и т.д.

Очевидно,min m;=n,(n>... п =max m, .

Тогда формула (3) может быть записана в виде

h1

X.ы.„z" 3 (z;+<) .

1=O Р

П1- 1

" 1+л +--+> =1 . (г + )11< (г + }+

2 2

2 к 1о гп

nd 1-1

--+t X. (г . ) (}

d= t d-г

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

) представлено в виде о М-11

" = o2 +d z+ +4. 2 j (} ,.-(, и соответственно, i --е слагаемое правой части формулы (4) — в виде (6)

Именно в этом виде формирует слагаемые суммы (4) предлагаемое устройство.

Шифратор 1, за счет соответствующего объединения выходов на элементах ИЛИ, формирует на выходах этих элементов двоичный параллельный импульсный код числа ненулевых входных сигналов (шифратор 1и элементы ИПИ вЂ” импульсные). Например, для К=З шифратор 1 должен иметь семь выходных шин (нулевая входная комбинация не нуждается в шифрации).

Выходы 1-3 шифратора соединены с входом первого элемента ИЛИ, выход I5

4 — с входом первого и второго элементов ИЛИ, остальные выходы — с входами второго элемента ИЛИ. Аналогично может быть получена структура шифратора 1 для любого числа входных сигналов °

Элемент 3 задержки задерживает импульсы на время Т,)(М-1) Д1, причем

L1+ 2 (Т, где Г, - время срабатывания счетчи2 ка; Т вЂ” минимальный интервал времени между входными импульсами устройства, а время é должно быть достаточным для срабатывания накапливающего сумматора 11, т.е. может быть весьма малым. Элементы 4 и 5 задержки (их количество равно M-1) задерживают импульсы соответственно на время Л, 2д,..., (М-1) a,t.

Число групп элементов И 7, 8 и 9 равно M — числу выходов шифратора 1, число элементов И в каждой группе равно N. Число элементов ИЛИ в группе 10 равно N+M-2 (поскольку последний элемент ИЛИ является вырожден-ным" — имеет только один вход, т.е. представляет собой прямое соединение выхода N-ro элемента И М вЂ” и группы с входом M+N-го разряда накапливающего сумматора 11). !

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

В исходном состоянии импульсы на входах устройства отсутствуют, счетчик 6 и накапливающий сумматор 11 установлены в нуль.

В некоторый момент на К1 входов поступают первые импульсы. Ввиду синхронности входных импульсов на выходе элемента IUIH 2 формируется при этом один импульс независимо от величины К1. Пусть для определенности К „= К = 7, т.е. 4 = 3. Тогда в течение всего времени, пока число ненулевых входных сигналов будет оставаться равным семи, одновременно с входными импульсами устройства будут формироваться импульсы на первом, втором и третьем выходах шифратора 1 (поскольку 7-111 в двоичной системе счисления). Импульс с первого выхода шифратора 1, поступая на вход первого (младшего) разряда накапливающего сумматора 11 и на вторые входы элементов И первой группы 7, вызывает прибавление к содержимому накапливающего сумматора 11 числа 2 л + 1 (здесь a - co1092500 держащееся в счетчике 6 число), так как выходы элементов И этой группы подключены к разрядным входам накапливающего сумматора 11 (через элементы ИЛИ группы 10) со сдвигом на один разряд в сторону старших разрядов. Импульс с второго выхода шифратора 1, задержанный элементом 4 на время, достаточное для завершения переходных процессов в накопителе, вызывает увеличение его содержимого на величину 2(2n+ 1), так как выход элемента 4 подключен (через элемент ИЛИ группы 10) к входу второго разряда накапливающего сумматора 11, а выходы элементов И второй группы соединены с разрядными входами накапливающего сумматора 11 (через группу элементов ИЛИ 10) со сдвигом в сторону старших разрядов на два разряда.

Аналогично, после окончания переходных процессов в накапливающем сумматоре 11 импульс с третьего выхода шифратора 1, задержанный элементом 5, вызывает прибавление к содержимому накапливающего сумматора 11 числа 2(2н+ 1) . Поскольку в дан ном случае tl=0, содержимое накапливающего сумматора 11 увеличивается в итоге на 1+2+4=7, т.е. на К . После этого импульс с выхода элемента

3 задержки увеличивает содержимое счетчика 6 на единицу. Так будет продолжаться до тех пор, пока не закончится формирование одной или нескольких одновременно входных величин (закончатся соответствующие пакеты входных импульсов), причем в накапливающий сумматор 11 все это время будут добавляться числа вида (2 и +1) К, и =О, 1, 2,..., n -1, Обработка каждого входного импульса требует при этом М тактов вместо К+ 1 тактов в устройствепрототипе (3 вместо 8 в расматриваемом примере, а уже при К=15 имеем

4 такта вместо 16 и т.д.).

Пусть в некоторый момент одновременно заканчиваются два пакета входных импульсов (т.е. К =5 = !01

2 в двоичной форме счисления) .Теперь каждый входной импульс будет увеличивать содержимое накапливающего сумматора 1! на величину К (2п+1), п. +1,...,и — 1 (так как имф У 2 пульсы будут возникать только на

10 первом и третьем выходах шифратора

1), в полном соответствии с формулой (6) .

Совершенно аналогично будет про— должатьея работа устройства после того, как число пакетов импульсов, поступающих на его входы, уменьшится до К>, К+ и т.д., пока входные импульсы не прекратятся (при К=О) .

Накапливающий сумматор 11 зафикси2О рует при этом сумму квадратов входных чисел в соответствии с формулами (4) -(6) .

Предложенное устройство обеспечивает обработку каждого входного

25 импульса в течение М тактов (3 вместо К+1 тактов в устройстве — прототипе) вследствие чего оно обладает существенно более высоким быстродействием, выигрыш в быстродействии о очень быстро растет с ростом К, так уже при К=31 имеем М =S, т.е.

5 тактов вместо 52 (выигрыш более чем в 6 раз) .

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

4б различных типов блоков.

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

4S 2, в сравнении с которым предложенное устройство обладает значительно более высоким быстродействием и меньшим обьемом аппаратуры.

1092500

Составитель А.Казанский

Редактор Л.Алексеенко Техред М. Надь

КорректоР С.Шекмар

Подписное

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

Заказ 3255/32 Тирах 699

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

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