Способ параллельного сложения длительностей группы временных интервалов Советский патент 1984 года по МПК G06G7/14 

СО

о со

О1 Изобретение относится к автоматике и вычислительной технике и может быть использовано в операционных схемах аналоговых процессоров, а так же при решении задач определения экс тремумов функгщй, заданных таблично. Известен способ параллельного сложения длительностей группы времен ных интервалов, основанный на преобразовании длительностей в напряжения, суммировании напряжений и вьаделении среднего значения суммы на общем периоде следования группы вре{менных интервалов Недостатком данного способа является ограниченная область применения Известен способ параллельного сло жения длительностей группы временных интервалов, основанный на накоплении кратных длительностей и заключанзщийся в том, что для каждого временнога интервала группы вьщеляют путем дифференцирования моменты времени его начала и конца, по вьщеленным моментам времени определяют текущее значение разности между суммой моментов времени начала временных интервалов группы и суммой моментов времени окончания интервалов группы, длительность наибольшего временного интервала группы преобразуют в последовательность кратных длительностей путем умножения ее на зто значение разности, а полученные кратные длительности накапливают. Однако известный способ характеризуется пониженной точностью фор. мирования суммы длительностей временных интервалов группы, определяемой ошибками, возникающими при возможном совпадении друг с другом моментов времени начала или конца различных интервалов группы. Цель изобретения - повышение точности. Поставленная цель достигается тем что согласно способу параллельного сложения длительностей группы временных интервалов, основанному на накоплении кратных длительностей, сравнивают между собой длительности йременных интервалов группы и вЬщеля ют временной интервал наименьшей дли тельности, формируют длительность, краткую этой наименьшей длительности путем умножения ее-на количество вре менных интервалов в группе, формируют новую группу временных интерва,лов путем вычитания этой наименьшей 1 5 длительности из длительности каждого временного интервала предьщуи ей группы, далее указанные действия повторяют для каждой новой группы временных интервалов до вьщеления интервала наименьшей длительности равной нулю, а полученные кратные длительности последовательно суммируют. На чертеже изображена блок-схема устройства, реализующего способ параллельного сложения длительностей. Параллельное сложение длительностей группы временных интервалов осуществляется следующим образом. На первом шаге для исходной (первой) группы временнЬк интервалов сравнивают между собой длительности этих интервалов и вьщеляют временной интервал наименьшей длины. Эту наименьшую длительность преобразуют ,в кратную ей длительность путем умножения полученной наименьшей длительности на количество временньк интервалов в исходной группе, а также формируют новую (вторую) группу временных интервалой путем вычитания полученной наименьшей длительности из длительности каждого временного интервала предыдущей группы. Для второй группы временных интервалов указанные действия повторяют, а именно сравнивают между собой длительности интервалов второй группы и вьщеляют новый временной интервал наименьшей длины. Затем формируют длительность, кратную новой наименьшей длительности путем умножения этой наименьшей длительности на количество временных интервалов во второй группе,а также формируют третью группу временных интервалов путем вычитания последней наименьшей длительности из длительности каждого временного интервала второй грза1пы. Далее последовательность действий повторяют для каждой новой группы временных интервалов до вьоделения интервала наименьшей длительности равной нулю. Полученные для каждой группы временных интервалов кратные длительности накапливают путем последовательного их суммирования. Устройство реализуннцее способ содержит входы 1, 1j, 1 ,,...,„ (где п - максимальное количество временных интервалов в группе), на которые подаются длительности временных интервалов исходной (первой)

31

группы, блоки 2, 2,...2f сравнения, с помощью которых вьщеляются разности между длительностями отдельных интервалов группы и-интервалами наименьшей дпительности блок 3 сравнения, на котором вьщеляются интервалы наименьшей длительности, блок 4 последовательного суммирования (накопления) кратных длительностей, в котором также вьтолняется умножение наименьших длительностей на количество временных интервалов в текущей группе.

Рассмотрим параллельное сложение, например, длительностей группы из пяти временных интервалов. Складываются интервалы с длительностями равными 11, 3, 5, 8 и 15. Пять длительностей подаются соответственно на выходы , задавая исходную группу для сложения.

Поскольку в исходном сост;оянии на вькоде блока 3 присутствует нулевой сигнал, то в первом действии сложе|Ния от каждой исходной длительности вычитается нуль с блока 3, и на выходах блоков получаются разности, фактически равные исходным длительностям временных интервалов 11, 3, 5, 8 и 15, которые параллельно воздейству ют по пяти входам на блок 4 и блок 3, где происходит выделение интервала наименьшей длитель ности из пяти Исходных интервалов, т.е. в блоке 3 и 4 происходит образование пятикратной к минимальной и равной длительности 15, кратность которой определяется количеством длительностей первой труппы.

Во втором действии на блоках 7.2 фop вIpyютcя разности между исходными длительностями It, 3, 5, 8 и 15 и минимальной длительностью первой группы равной трем. Образуются разности 8,2,5 и 12 второй группы. Наименьшая длительность временного 1186

0354

интервала второй группы равная двум формируется в блоке 3 в четырехкратном размере, т.е. 8, кратность которой определяется количеством интервалов второй группы, суммируется в блоке 4 с пятикратной минимальной длительностью первой группы, в данном случае с 15.

В третье.м действии на блоках 2,Q 2f формируются разности между длительностями 8, 2, 5 и 12 второй группы и минимальной длительностью второй группы. Образуются значащие разности 6, 3 и 10 третьей группы. №ij нимальная длительность интервалов

Третьей группы равная трем формируется в блоке 3 и в трехкратном размере 9, кратность которой определяется количеством длительностей третьей

Q группы, суммируется в блоке 4 с полученной на предьщущих двух действиях сумме пяти и четырех кратных.

В четвертом действии на блоках 2 J формируются разности между дли5 тельностями временных интервалов

6, 3 и 10 третьей группы и минимальной длительностью третьей группы. Образуются значащие разности 3 и 7. Минимальная длительность четвертой группы равная трем формируется в блоке 3 и в двухкратном размере 4, кратность которой определяется количеством длительностей данного действия, накапливается в блоке 4, к полученной на предыдущих трех действиях сум ме пяти, четырех, трехкратных.

В пятом (последнем) действии в блоке 4 накапливается однократная roiнимальная длительность равная четырем к кратным предыдущих четырех действий.

Таким образом, схематически параллельное сложение сигналов длительностей временных интервалов tit, 3f, 5r, 8lD, ЛЬУ можно отобразить сле У1ощим образом.

З S О

СПОСОБ ПАРАЛЛЕЛЬНОГО СЛОЖЕ-. НИЯ ДЛИТЕЛЬНОСТЕЙ ГРУППЫ ВРЕМЕННЖ ИНТЕРВАЛОВ, основанный на накоплении кратных длительностей, отличающийся тем, что, с целью повышения точности, сравнивают между собой длительности временных интервалов группы и выделяют временной интервал наименьшей длительности, фор мируют длительность, кратную этой наименьшей длительности путем умножения ее на количество временных интервалов в группе, формируют новую группу временных интервалов путем вычитания этой наименьшей длительности из длительности каждого временного интервала предьщущей группы, далее указанные действия повторяют для каждой новой группы временных интервалов до вьщеления интервала наименьшей длительности равной нулю, а полученные кратные длительности последовательно суммируют. с е

1 действие©2 действие©3 действие©4 действие©5 действие.

В кружках обозначены соответствующие промежуточные результаты сложения.

(i)

41 $11190 Работоспособность данного способа подтверждается в численном представлений доказательством следующего тождестваппс Z.,.ZH -lO-- K-o,.,);., 1 .- где el.0(,n) -исходные величины (действи-jQ тельные числа). Докажем справедливость данного тождества в предложении, что числа а. различны и упорядочены по чине, т.е.15 a.aj.. .а,а... .а. (2) Тогда в силу (2) minTa -a j .а.-а, и правая часть тождества (1) примет вид: Ztn-u-)- -t«K- --i}L St - , , . л , ,/ . / ,1/ I M«r«i-i)4°r%)(- H«7- iM -2Kv«2K ...4и-{иП(«,-«. ,- пОКг«И 30 JV 1 11 1/ -(-1)(..)---ЗК-Г«п-з). + .( )о,. t(n-2)q...(i-i)«.4()«.n-(iM)« х«.....3а .2«.а)Нп-().(i-i)o( .-(n-i)ct.(it1)a. -V --3o( 4...п-{М)с,,,,(П«и2 --- з%-2 2«„.,.«,-(п:Яс.,,|.р , Гг / т 1 -...,i-2)J-lJoi.(M)j-1jo(,,„-.-(Н).,.,-(з-1)а„2-( «„., nc,t(n-l)o,,,4n-2l«,..+ n-{i-l)J«.f )4,(-)«U2 -- 3«nV2VH а -Сп-Яо(,о, -...-Mi-ZHcx. , + c«..(f-i).-(n-ila;,o,.-...,„.2 + «.22о,„./«. «т + ... + а., + о(. + ... + «.+о(2+5S f, -5 20 2J 5« Так как остальные слагаемые взаимно уничтожаются. Тождество (1) доказано. Обозначим через А, множест о ненулевых чисел, участвующих в первом цикле. Элементы множества А обозначин ./0. А Гак f ) . где ,ац - данные числа (,п). Символом minA обозначим наименьшее из чисел, входящих в множество А. Шнимум выбирают из п чисел, поэтому в первом цикле образуется nminA , Для анализа последующих циклов введем в расмотрение множества чисел A, .. .А-,А.,,.. .А|, образующихся по правилу: элементами множества А являются числа, которые рассматриваются в (1+1)-ом цикле. Это разности каждого из чисел множества с наименьшим числом из AJ. Наименьшее число из множества А обозначим символом mitiA. (1«2,п) . Образуем по этому правилу множества А,, состоящее цикла. Элементы А, обозначим а , а 0. А г« up ,,АЛ г, .. ,п . I J I К, ,) V к о) «i «о)к., { K-VV«olK . («K-«i)K 2 -V« f-0 Здесь в силу(2) minA, заменен на (а,а,). Минимум выбирается из (п-1)-го числа. Поэтому во втором цикле образуется число 1Л А о Г l (n-1)minA, (n-1) -а Л .. JIoкaжeм, используя метод математиче -j Qjj индукции, что в произвольном ° Г Д X . г 1 In-d-l) min}a.,-a;..L., где (,.,) - элементы множества А., т.е. число i-ro цикла: A. (a...,),,. (а. 0). . Утверждение верно для i 1,2. Предположим, что утверждение i-ro цикла. Покажем, что оно верно для (i+1)-ro 1щкла. 7 По сформулированному выше прави образуем множество элементами к. . а. « О, а. - числа (i-H)-ro цикла: i.,J-hкг )Ч(«к-.1)-(.,о,-«,.-«.«);, {° K-«ijK i+i. Т.К. Здесь в силу (2) rainA заменен (.). Минимум выбирается из эл ментов множества A,vi, т.е. из (n-i чисел. Поэтому в (1+1)-ом действии образуется число: (n-1)minA., (n-i)minja -a .). Утверждение доказано. По доказанному в произвольном i цикле (i 1,п) образуется ЧИСЛ.О n-(i-1),-a,.,;. 358 За п действий способа накапливается сумма результатов всех циклов от первого до п-го, т.е. сумма вида 2.cn-(i-.ijrnin o,-o,.j;;.o,.. и силу доказанного тождеств(1). Тождество доказывает универсальность предложенного способа параллельного сложения п чисел, заданных в цифровой или в ансшоговой форме. Предлагаемьй способ -позволяет повысить точность сложения за счет замены дифференцирования длительностей группы на сравнени. длительностей друг с другом. Кроме того, понижаются требования быстродействия по элементной базе за счет раепараллеливания процесса формирования суммы и расширяется область применения за счет дополнительного определения разностей временных интервалов.