Устройство для вычисления суммы квадратов К числоимпульсных величин Советский патент 1984 года по МПК G06F7/552 

Изобретение относится к цифровой вычислительной технике и может быть использовано при-создании систем и приборов обработки информации. Известно устройство для вычисления Суммы квадратов к чисел, содержащее счетчик, счетный вход которого соединен с выходом элемента заде ки, а разрядные выходы - с первыми входами первой группы элементов И, и накопитель Cl 3. Недостатком этого устройства является низкое быстродействие, обусловленное тем, что необходимо возво дить в квадрат каждое слагаемое в отдельности, подавая их на единственный вход устройства последовател но во времени и суммируя результаты Наиболее близким к предлагаемому по технической сущности является устройство для вычисления суммы квадратов К чисел, содержащее элемент ИЛИ, входы которого соединены с входами устройства, счетчик, подключенный разрядными выходами к первым входам первой группы элементов И, элементы задержки и накопитель, выход которого является выходом устройства С 211. Недостатками известного устройства являются невысокое быстродейст вие, а также сложность, схемы, обусловленная наличием в его составе k формирователей строб-импульсов а также избыточного разряда счетчика (его первый разряд всегда находится в единичном состоянии) и соответственно элементов И группы. Цель изобретения - повышение быстродействия устройства. Поставленная цепь достигается тем, что в устройство, содержащее элемент ИЛИ, счетчик, первую группу элементов И, элемент задержки, накапливающий сумматор, выход которого является выходом устройства, раз рядные выходы счетчика соединены соответственно с первыми входами элементов И первой группы, введены М-1 групп элементов И (М - разрядность кода числа входных шин), М-1 элементов задержки, группа элементов ИЛИ, шифратор, даходы которого соединены с входными шинами устройства соответственно и входами элемента ИЛИ, выход которого через элемент задержки подключен к счетному входу счетчика, разрядные выходы которого соединены с первыми входами элементов И всех групп соответственно, первый выход шифратора соединен с вторыми входами элементов И первой группы и младшим разрядом накапливающего сумматора, i -и выход шифратора соединен через соответствую1ций элемент задержки (i 2, 3,..., М) с вторыми входами элементов И i-й группы и первым входом соответствующего элемента ИЛИ группы, выход j-ro элемента И i-й группы (j 1,2,. ..,N, i 1,2,...,M, гдеН разрядность счетчика (соединен с соответствующим входом (i+j-1)-го элемента ИЖ группы,выход (i+j-1)-ro элемента ИЖ группы соединен соответствующим входом накапливающего сумматора. Иа чертеже представлена блоксхема предлагаемого устройства. Устройство содержит шифратор 1, элемент ИЛИ 2, элементы 3, 4 и 5 задержки,счетчик 6, группы элементов И 7, 8 и 9, группу элементов ИЛИ 10, накапливающий сумматор 11. В основу принципа действия изоб ретения положено следующее представение квадрата числа: т L (2i-i-1) . Пусть входные величинь т. удовлетворяют условию Тогда из условия (1) следует .22 2 , (2t-f1)i-() л t.+ m,4,,.ttTt 1 . п X(2H()f...-fX -г гл. Необходимыми условиями работы устройства являются одновременность начала формирования всех величин гп, , а также синхронность импульсов на всех входах (эти импульсы могут, например, формироваться одним и тем же генератором). При этом число входных величин, формирование значений которых не закончено (число входов, на которые в очередном такте поступают импульсы, будем говорить число ненулевых входных сигналов), является невозрастающей во времени величиной. Обозначим число ненулевых входных сигналов в момент начала их формирования (т.е. число входов устройства, на которые поступят первые импульсы входных пакетов) К. В некоторый момент заканчивается формирование одной или нескольких одновременно входных величин, число оставшихся ненулевых входных сигналов обозначим К(очевидно, , К,К). Если , то в некоторый момент число ненулевых входных сигналов снова уменьшается - до К и т.д., пока не завершится формирование максимальной из входных величин Таким образом, получаем убьтающую в времени последовательность KoK-jK.j. Ж О, где . Пусть переход от К-, к К ц, ненулевых входных величи совершается после п входных импульсов (тактов), переход от К к К после п, входных импульсов и т.д. Очевидно,min mi. n,.nj... п max m; . Тогда формула (3) может быть записана в виде n,mf4...4mjzk T:(2,4-r)fV 1:(2, о п ч d-1-i )с (2,4-0 . (4) J Пусть далее, для записи числа К в двоичном позиционном коде требует ся М разрядов. Тогда любое из чисел последовательности К . может быть представлено в виде (i..,.o(.«v) (SP и соответственно, ;/ -е слагаемое пр вой части формулы (4) - в виде :мч (2i4) (6) 1.0 Jl Именно в этом виде формирует сла гаемые суммы (4) предлагаемое устро ство. Шифратор 1, за счет соответствую щего объединения выходов на элементах ШШ, формирует на выходах этих элементов двоичный параллельный импульсный код числа ненулевых входных сигналов (шифратор 1 и элементы ИЛИ - импульсные). Например, для шифратор 1 должен иметь семь выходных шин (нулевая входная комбинация не нуждается в шифрадии) Выходы 1-3 шифратора соединены с входом первого элемента ИЛИ, выход 4 - с входом первого и второго элементов ИЛИ, остальные выходы - с входами второго элемента ИЛИ. Аналогично может быть получена структура шифратора 1 для любого числа входных сигналов. Элемент 3 задержки задерживает импульсы на время Т,/М-1) 4t , причем должно выполняться условие Т + Т, где 2 время срабатывания счетчика; Т - минимальный интервал времени между входными импульсами устройства, а время ut должно быть достаточным для срабатывания накапливающего сумматора 11, т.е. может быть весьма малым. Элементы 4 и 5 задержки (их количество равно М-1) задерживают импульсы соответственно на время At, 2/it,..., (М-1) At. Число групп элементов И 7, 8 и 9 равно М - числу выходов шифратора 1, число элементов И в каждой группе равно N. Число элементов ИЛИ в группе 10 равно N-bM-2 (поскольку последний элемент ИЛИ является вьфожден ным - имеет только один вход, т.е. представляет собой прямое соединение выхода N-ro элемента И М-й группы с входом M+N-ro разряда накапливающего сумматора 11). I Устройство работает следуюш 1м образом. В исходном состоянии импульсы на входах устройства отсутствуют, счетчик 6 и иакапливаюш;ий сумматор 11 установлены в нуль. В некоторый момент на К входов поступают первые импульсы. Ввиду синхронности входных импульсов на выходе элемента ИЛИ 2 формируется при этом один импульс независимо от величины К:,. Пусть для определенности К-, К 7, T.e.N 3. Тогда в течение всего времени, пока число ненулевых входных сигналов будет оставаться равным семи, одновременно с входными импульсами устройства будут формироваться импульсы на первом, втором и третьем выходах шифратора 1 (поскольку 7-111 в двоичной системе счисления). Импульс с первого выхода шифратора 1, поступая на вход первого (младшего) разряда накапливающего сумматора 11 и на вторые входы элементов И первой группы 7, вызывает прибавление к содержимому накапливающего сумматора 11 числа 2П + 1 (здесь-г,- содержащееся в счетчике 6 число), так как выходы элементов И этой группы подключены к разрядным входам накапливающего сумматора 11 (через элементы ИЛИ группы 10) со сдвигом на один разряд в сторону старших разрядов. Импульс с второго выхода дифратора 1, задержанный элементом 4 на время, достаточное для завершения переходных процессов в накопителе, вызывает увеличение его содержимого на величину 2(2п+1), так как выход элемента 4 подключен (через элемент ИЛИ группы 10) к входу второго разряда накапливающего сумматора 11, а выходы элементов И второй группы соединены с разрядными входами накапливающего сумматора 11 (через группу элементов ИЛИ 10) со сдвигом в сторону старших разрядов на два разряда.

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

3задержки увеличивает содержимое

П счетчика 6 на единицу. Так будет продолзцаться до тех пор, пока не закончится формирование одной или нескольких одновременно входных величин (закончатся соответствующие пакеты входных импульсов), причем в накапливающий сумматор 11 все это время будут добавляться числа вида (2п+1)К, п 0, 1,2, . .., .

Обработка каждого входного импульса требует при этом М тактов вместо К+1 тактов в устройствепрототипе (3 вместо 8 в расматриваемом примере, а уже при имеем

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

Пусть в некоторый момент одновременно заканчиваются два пакета входных импульсов (т.е. 101 в двоичной форме счисления).Теперь каждый входной импульс будет увеличивать содержимое накапливающего сумматора 11 на величину К (2т-1), И Т1, , . .. ,П2-1 (так как импульсы будут возникать только на первом и третьем выходах шифратора 1), в полном соответствии с формулой (6) .

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

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

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

импульса в течение М тактов (3 вместо К+1 тактов в устройстве-прототипе) вследствие чего оно обладает существенно более высоким быстродействием, вьшгрыш в быстродействии

0 очень быстро растет с ростом К, так уже при имеем М 5, т.е. 5 тактов вместе 52 (выигрыш более чем в 6 раз).

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

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

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

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