Спосіб паралельного додавання та відновлення тривалостей групи часових інтервалів

Изобретение относится к автоматике и вычислительной технике и может быть использовано в операционных схемах аналоговых процессоров, а также при решении задач определения экстремумов функций, заданных таблично. Известен способ параллельного сложения длительностей группы временных Интервалов [ Карпов Р.Г,, Карпов М.Р. Преобразование и обработка широтно-импульсных сигналов, М., "Ма шиностроение", 1977, с. 71|, основанных на преобразовании длительностей в напряжение, суммировании напряжений и выделении среднего значения суммы на общем периоде следования группы временных интервалов, Недостатком данного способа является ограниченная область применения. Известен способ параллельного сложения длительностей группы временных интервалов[Авт. св. №388259,1971, БИ № 16], основанный на накоплении кратных длительностей и заключающийся в том, что для каждого временного интервала группы выделяют путем дифференцирования моменты времени его начала и конца, по выделенным моментам времени определяют текущее значение разности между суммой моментов времени начала временных интерралов группы и суммой моментов времени окончания интервалов группы, длительность наибольшего временного интервала группы преобразуют в последовательность кратных длительностей путем умножения ее на это значение разности, а полученные кратные длительности накапливают. Однако известный способ характеризуется пониженной точностью формирования суммы длительностей временных интервалов группы, определяемой ошибками, возникающими при возможном совпадении друг с другом моментов времени начала и конца различных интервалов группы. Наиболее близким к предлагаемому является способ параллельного сложения длительностей группы временных интервалов [Авт. св. № 1119035, 1984, БИ № 38], в котором накапливают кратные длительности, сравнивают между собой длительности временных интервалов группы и выделяют временной интервал наименьшей длительности, формируют длительность, кратную этой наименьшей длительности путем умножения ее на количество временных интервалов в группе, формируют новую гр уппу временных интервалов путем вычитания этой наименьшей длительности из длительности каждого временного интервала предыдущей группы, далее указанные действий повторяют для каждой новой группы временных интервалов до выделения интервала наименьшей длительности равной нулю, а полученные кратные длительности последовательно суммируют. Недостатком известного способа является ограниченная область применения, т.к. в нем не предусмотрено выполнение операции параллельного восстановления исходных данных и и х хранения. В основу изобретения поставлена задача усовершенствования способа параллельного сложения длительностей группы, временных интервалов, в котором формирование матрицы теневых бинарных масок и временного интервала наименьшей длительности в каждой группе обеспечивает восстановление исходной группы временных интервалов и за счет этого расширение области применения способа. Поставленная задача решается тем, что в способе параллельного сложения и восстановления длительностей группы временных интервалов накапливают кратные длительности, сравнивают между собой длительности временных интервалов исходной группы и- выделяют временной интервал наименьшей длительности, кратную этой наименьшей длительности путем умножения ее на количество временных интервалов в гр уппе, формируют новую гр уппу временных интервалов путем вычитания этой наименьшей длительности из длительности каждого временного интервала предыдущей гр уппы, повторяют указанные действия для каждой новой группы временных интервалов до выделения интервала наименьшей длительности, после чего подученные кратные длительности последовательно суммируют согласно изобретению, сравнивают между собой длительности временных интервалов исходной группы А{а 1, а2,.а3... aj,..., a n}, выделяют и запоминают временной интервал q наименьшей длительности, первую группу А1{а11, а12,а13 .... a1j,..., a1n}} временных интервалов формируют путем вычитания выделенного временного интервала q наименьшей длительности каждого временного интервала исходной· группы, представляют A1 и запоминают в виде признаков наличия временного интервала наименьшей длительности в первой группе, которые являются элементами первой теневой бинарной маски F1{f11 , f12. …f1j.....f 1n}, вторую гр уппу А2{а21, а22,.... a2j,..., a 2n} временных интервалов формируют путем вычитания и запоминания выделенной наименьшей длительности q1, из длительности каждого временного интервала первой группы, представляют А2 и запоминают в виде признаков наличия временного интервала наименьшей длительности во второй группе, которые являются элементами второй теневой бинарной маски F2{f21, f22 . …f 2j.....f2n} аналогично запоминают q2, q3, …. qm-1 и формируют новые третью, четвертую, m-ю группы А3, А4 , .... Am временных интервалов, которые представляют в виде признаков наличия временного интервала наименьшей длительности этих группах, которые являются элементами третьей, F3, четвертой F4, m-й Fm теневых бинарных масок, а из первой, второй, третьей, m-й масок формируют матрицу теневых бинарных масок вида: а восстановление длительности группы временных интервалов основано на накоплении кратных длительностей групп, каждая i-я из которых может быть получена путем умножения наименьшей длительности qi-1 предыдущей гр уппы на элементы теневой бинарной маски Fi, формируют новую гр уппу Вi-1 временных интервалов путем умножения наименьшей длительности qi-2 предыдущей группы на элементы теневой бинарной маски Fi-1, далее указанные действия повторяют для каждой новой группы до формирования первой группы Β1 временных интервалов, затем полученные кратные длительности последовательно суммируют и формируют исходную гр уппу А временных интервалов. Предложенный способ заключается в следующем. На первом шаге для исходной группы А{а 1, а2 ,.... aj,..., an} временных интервалов сравнивают между собой длительности этих интервалов a1, а2 а3.....aj,,.., an (n число интервалов в группе). Выделяют и запоминают временной интервал наименьшей длины q, который преобразуют в кратную ей длительность S путем умножения выделенной длительности на количество временных интервалов в исходной группе р, т.е. S = q *p. Формируют новую (первую) гр уппу А1{а11, а12 ,.... a1j,..., a1n} (где первая нижняя цифра обозначает номер группы, вторая - номер позиции временного интервала в этой группе) временных интервалов путем вычитания полученной наименьшей длительности q из длительности каждого временного интервала предыдущей (исходной) группы, т,е. Далее первую группу Α1 временных интервалов представляют и запоминают в виде признаков наличия временного интервала наименьшей длительности в первой группе, которые являются элементами первой теневой бинарной маски F1, т.е. где f1j - элемент маски j-ro временного интервала а1j на первом шаге, принимающий значения для первой группы временных интервалов на втором шаге указанные действия повторяют, а именно сравнивают между собой длительности интервалов первой группы, выделяют и запоминают новый временной интервал наименьшей длительности q1. Затем формируют длительность, кратную новой наименьшей длительности путем умножения этой наименьшей длительности на количество временных интервалов в первой группе p1, т е. S 1 = q1 · p1 Также формируют вторую гр уппу временных интервалов А2{а21, а22,.... a2j,..., a2n} Путем вычитания последней наименьшей длительности из длительности каждого временного интервала предыдущей (первой) группы, т.е. Аналогично, втор ую группу А2 временных интервалов представляют и запоминают в виде признаков наличия временного интервала наименьшей длительности во второй гр уппе, которые являются элементами второй теневой бинарной маски F2, т.е. А2{а 21, а22 ,.... a2j ,..., a2n} ~ F2{f21, f22 . …f 2j.....f2n}· Последовательность действий для третьей, четвертой, m-й групп аналогична, «угорая в конечном итоге сводится к выделению, запоминанию наименьшей длительности qm-1 временного интервала, представлению и запоминанию в виде признака наличия этого интервала в m-й группе, как элемента логической единицы в теневой бинарной маске Fm, с учетом того, что Таким образом, после описанных преобразований формируют матрицу теневых бинарных масок, которая имеет вид: Восстановление длительностей исходной группы временных интервалов основано на накоплении кратных длительностей групп, каждая і-я из которых может быть получена путем умножения наименьшей длительности q предыдущей группы Аi-1 временных интервалов на элементы теневой маски Fi, и формируют новую гр уппу Βi : Затем формируют новую группу Вi-1 временных интервалов путем умножения наименьшей длительности qi-2 предыдущей гр уппы на элементы теневой бинарной ма Указанные действия повторяют для каждой новой группы до формирования первой группы Β1 временных интервалов, полученные кратные длительности последовательно суммируют и формируют (восстанавливают) исходн ую гр уппу А временных интервалов: Описанный выше способ, например для пяти шагов действий, поясняется в табл. 1 и 2. В частности, табл.1 иллюстрирует формирование матрицы теневых бинарных масок, а табл. 2 - восстановление длительностей исходной группы временных интервалов. За счет того, что в способе параллельного сложения и восстановления длительностей группы временных интервалов используются известные действия, которые позволяют сформировать сумму длительностей временных интервалов исходных групп, а также реализуются вновь введенные действия: представление и запоминание групп временных интервалов в виде признаков наличия временного интервала наименьшей длительности в каждой группе с помощью элементов теневой бинарной маски, формирование матрицы теневых бинарных масок, которые позволяют выполнить восстановление исходной группы временных интервалов. Длительности исходной группы временных интервалов формируются в процессе накопления кратных длительностей групп, каждая из которых получена путем умножения наименьшей длительности предыдущей группы временных интервалов на соответствующие элементы матрицы теневых бинарных масок, что расширяет область применения способа. Устройство, реализующее способ, содержит входы 11, 12.....1n . блоки 21, 22, ...,2n сравнения, блок 3 сравнения, блок 4 последовательного суммирования (накопления) кратных длительностей, блок 5 запоминания (хранения), блок 6 запоминания признаков наличия текущей наименьшей длительности в группах временных интервалов, блоки 71, 72.....7 n последовательного суммирования, выходы 81, 82 .....8n формирования (восстановления) длительности временных интервалов исходной группы, причем, первые входы блоков 21, 22.....2n сравнения соединены с входами 11, 12.....1n устройства и первыми выходами блоков 21, 22.....2n сравнения соответственно, вторые входы которых подключены к выходу блока 3 сравнения, кроме того первые выходы блоков 21, 22.....2n соединены с соответствующими входами блока 3 сравнения. Вторые выходы блоков 21, 22.....2n сравнения подключены к группе входов блока 4 последовательного суммирования и группе входов блока 6 запоминания, а выход блока 3 сравнения соединен с входом блока 4 последовательного суммирования и блока 5 запоминания, выход которого подключен к первым входам блоков 71, 72.....7n последовательного суммирования. Вторые входы блоков 71, 72.....7n последовательного суммирования соединены с соответствующими выходами блока 6 запоминания, а выходы являются выходами 81, 82.....8n длительностей исходной группы временных интервалов. Реализация предложенного способа устройством (чертеж) осуществляется следующим образом. На входы 11, 12.....1 n (где n-максимальное количество временных интервалов в группе), подаются длительности временных интервалов исходной (первой} группы с помощью блоков 21, 22.....2n сравнения выделяются разности между длительностями отдельных интервалов группы и интервалами меньшей длительности, блоком 3 сравнения выделяются интервалы наименьшей длительности, блок 4 последовательного суммирования (накопления) кратных длительностей, выполняет умножение наименьших длительностей на количество временных интервалов в текущей группе, блок 5 запоминания (хранения), последовательно по шагам фиксирует интервалы наименьшей длительности соответственно в группах временных интервалов Α1 , А2 , .... An , блоки 71, 72 .....7n осуществляют последовательное суммирование, на выходах 8 1, 82.....8 n которого формируются (восстанавливаются) длительности временных интервалов исходной группы. Рассмотрим параллельное сложение, например, длительностей группы из пяти временных интервалов. Складываются интервалы с длительностями равными 11,3,5, 8 и 15. Пять длительностей подаются соответственно на выходы 11-15, задавая, исходн ую гр уппу для сложения. Поскольку в исходном состоянии на выходе блока 3 присутствует нулевой сигнал, то в первом действии сложения от каждой исходной длительности вычитается нуль с блока 3, и на выходах блоков 21-25 получаются разности, фактически равные исходным длительностям временных интервалов 11,3,5,8 и 15, которые параллельно воздействуют по пяти входам на блок 4 и блок 3, где происходит выделение интервала наименьшей длительности из пяти исходных интервалов, т.е. в блоке 3 и 4 происходит образование пятикратной к минимальной и равной длительности 15, кратность которой определяется количеством длительностей первой группы. При этом в блоке 5 запоминания фиксируется наименьшая длительность временного интервала, равная 3, а в блоке 6 - признаки наличия данной наименьшей длительности в текущей группе временных интервалов в соответствии со следующим выражением: где fij - группа j-й временной длительности, для 1-й группы; aij - разность между интервалами меньшей длительности qi-1 и длительностями интервалов аi1, аi2, аi3, ..., ain для і-ой группы. Таким образом, информация в блоке 6 ' на первом шаге для первой группы Α1 временных интервалов может быть записана в виде первой теневой бинарной маски следующим образом: На втором шаге в блоках 21-25 формируются разности между исходными длительностями 11, 3,5,8 и 15 и минимальной длительностью первой группы равной трем, Образуются разности 8, 3, 5 и 12 второй группы. Наименьшая длительность временного интервала второй группы равная двум формируется в блоке 3 в четырехкратном размере, т.е. 8, кратность которой определяется количеством интервалов второй группы, суммируется в блоке 4 С пятикратной минимальной длительностью первой группы, в данном случае с 15, Аналогично, на втором шаге для второй труппы временных интервалов в блоках 5 и 6 запоминания фиксируется соответственно следующая информация - временной интервал наименьшей длины, в данном случае, равный q1 = 2, а группа временных интервалов А2 представляется и фиксируется в виде второй теневой бинарной маски F2 как На третьем шаге в блоках 21-25 формируются разности между длительностями 8, 2, 5 и 12 второй группы и минимальной длительностью второй группы. Образуются значащие разности 6,3 и 10 третьей группы. Минимальная длительность интервалов третьей группы, равная трем, формируется в блоке 3 и в трехкратном размере 9, кратность которой определяется количеством длительностей третьей группы, суммируется в блоке 4 с полученной на предыдущи х двух действиях сумме пяти и четырех кратных. Следовательно, в блоке 5 (запоминания) при этом фиксируется длительность, равная q2 = 3, а в блоке 6 запоминания, третья группа временных интервалов Аз фиксируется и представляется в виде третьей теневой бинарной маски F3 как На четвертом шаге в блоках 21-25 формируются разности между длительностями временных интервалов 6, 3 и 10 третьей группы и минимальной длительностью третьей группы. Образуются значащие разности 3 и 7, Минимальная длительность четвертой группы равна трем и формируется в. блоке 3, а в Двухкратном размере 6, кратность которой определяется количеством длительностей данного действия, накапливается в блоке 4, к полученной на предыдущи х тре х действия х сумме пяти, четырех, трехкратных. В блоках 5 и 6 запоминания при этом оказывается зафиксированной следующая информация соответственно: длительность, равная q3 = 3, а четвертая группа временных интервалов А4 представляется в виде четвертой теневой бинарной маски F4{f41 , f 42. f 43 f44..f45... } ~ {1,0, 0.0.1}. На пятом (последнем) шаге в блоке 4 накапливается однократная минимальная длительность, равная четырем, к кратным предыдущи х четырех действий а в блоках 5 и 6 запоминания фиксируется соответственно текущая минимальная длительность временного интервала q4 равная 4, а признаки ее наличия в текущей гр уппе A5 временных интервалов представляются в виде пятой теневой бинарной маски F5 следующим образом: Таким образом, схематически параллельное сложение сигналов длительностей , временных интервалов 11t, 3t, 5t, 15t можно отобразить следующим образом: Информацию, зафиксированную в блоке 6 длительностей, можно представить в виде матрицы: в процессе параллельного сложения временных где количество строк соответствует числу шагов параллельного сложения временных длительностей, а количество столбцов числу временных интервалов в исходной гр уппе, Соответственно в блоке 5 запоминания зафиксированы наименьшие длительности q, q1, .... q4 равные 3, 2, 3, 3, 4. Используя содержимое блоков 5 и 6 и блоки 71.... 7n последовательного суммирования, можно параллельно за 5 шагов восстановить временные длительности исходной группы. Рассмотрим параллельное восстановление длительностей группу из 5 временных интервалов. На первом шаге из блоков 5 и 6 запоминания считываетсй соответствующая информация, например, зафиксированная на первом шаге параллельного сложения временных интервалов, т.е. длительность q равная 3 и первая строка матрицы признаков, т.е. первая бинарная маска F={1 1 1 1 1}. Эта информация поступает на входы соответствующи х блоков 71.....7n последовательного суммирования, где происходит поэлементное умножение на элементы теневой бинарной маски F1 причем, если соответствующий элемент теневой бинарной маски аij=1, то к содержимому соответствующего блока 71, ..., 7n последовательного суммирования, прибавляется величина q (исходное состояние этих блоков равно нулю) значит, содержимое блоков 71.....75 будет одинаково и в данном случае равно 3, т.е. B 1{3 3 3 3 3}. На втором шаге, с учетом содержимого блоков 5 и 6 запоминания к содержимому блоков 7 1,73,74,75 Прибавляется временная длительность, равная 2. Следовательно, сформируется новая группа временных интервалов В2{2 0 2 2 2}, а содержимое блоков 71, ...75 будет {5355 5}. На третьем, четвертом, пятом шагах выполняются аналогичные операции. Таким образом, схематически, параллельное восстановление сигналов длительностей временных интервалов 11,3,5,8,15, описанное выше, поясняется табл, 2. Предлагаемый способ позволяет не только выполнить параллельное сложение длительностей группы временны интервала, но и восстановить после завершения указанной операции длительности исходной группы временные интервалов, что расширяет функциднельные возможности предлагаемого способа.