способ параллельного сложения длительностей группы временных интервалов

Формула изобретения

СПОСОБ ПАРАЛЛЕЛЬНОГО СЛОЖЕНИЯ ДЛИТЕЛЬНОСТЕЙ ГРУППЫ ВРЕМЕННЫХ ИНТЕРВАЛОВ, основанный на накоплении кратных длительностей, сравнении между собой длительностей временных интервалов исходной и последующих групп, выделении временного интервала наименьшей длительности и формировании длительности в каждой группе кратной наименьшей длительности в группе путем умножения ее на количество временных интервалов в этой группе, формировании первой и последующих групп временных интервалов путем вычитания наименьшей длительности предыдущей группы из длительности каждого временного интервала этой группы с повторением указанных действий для каждой новой группы временных интервалов до выделения интервала наименьшей длительности, после чего полученные кратные длительности последовательно суммируют, отличающийся тем, что запоминают временной интервал q наименьшей длительности исходной группы A { a; a₂; a₃; . . . ; a_j; . . . ; a_n } , представляют первую группу временных интервалов A₁ { a₁₁; a₁₂ ; a₁₃; . . . ; a_1j; . . . ; a_1n } и запоминают в виде признаков наличия временного интервала наименьшей длительности в первой группе, которые являются элементами первой теневой бинарной маски F₁ { f₁₁; f₁₂; f₁₃; . . . ; f_1j; . . . ; f_1n } , запоминают выделенный временной интервал q₁ наименьшей длительности первой группы, представляют вторую группу временных интервалов A₂ { a₂₁; a₂₂; a₂₃; . . . ; a₂j; . . . ; a_2n } и запоминают в виде признаков наличия временного интервала наименьшей длительности во второй группе, которые являются элементами второй теневой бинарной маски F₂ { f₂₁; f₂₂; f₂₃; . . . ; f_2j, аналогично запоминают q₂; q₃; . . . ; q_m-1, представляют новые третью, четвертую, m-ю группы A₃, A₄ , . . . , A_m временных интервалов и запоминают в виде признаков наличия временного интервала наименьшей длительности в этих группах, которые являются элементами третьей F₃, четвертый F₄, m-й F_m теневых бинарных масок, а из первой и второй, третьей, m-й формируют матрицу теневых бинарных масок вида



а восстановление длительности группы временных интервалов основано на накоплении кратных длительностей групп, каждая i-я из которых может быть получена путем умножения наименьшей длительности q_1i-1 предыдущей группы на элемент теневой бинарной маски F_1i, формируют новую группу B_1i-1 временных интервалов путем умножения наименьшей длительности q_i-2предыдущей группы на элементы теневой бинарной маски F_i-1, далее указанные действия повторяют для каждой новой группы до формирования первой группы B₁ временных интервалов, затем полученные кратные длительности последовательно суммируют и формируют исходную группу A временных интервалов.

Описание изобретения к патенту

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

Известен способ параллельного сложения длительностей группы временных интервалов [1] , основанный на преобразовании длительностей в напряжение, суммировании напряжений и выделении среднего значения суммы на общем периоде следования группы временных интервалов.

Недостатком данного способа является ограниченная область применения.

Известен способ параллельного сложения длительностей группы временных интервалов [2] , основанный на накоплении кратных длительностей и заключающийся в том, что для каждого временного интервала группы выделяют путем дифференцирования моменты времени его начала и конца, по выделенным моментам времени определяют текущее значение разности между суммой моментов времени начала временных интервалов группы и суммой моментов времени окончания интервалов группы, длительность наибольшего временного интервала группы преобразуют в последовательность кратных длительностей путем умножения ее на это значение разности, а полученные кратные длительности накапливают.

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

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

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

Целью изобретения является расширение области применения.

Предложенный способ заключается в следующем. На первом шаге для исходной группы A{ a₁; a₂; a₃; . . . ; a_j; . . . a_n} временных интервалов сравнивают между собой длительности этих интервалов a₁; a₂; a₃; . . . ; a_j; . . . ; a_n (n - число интервалов в группе). Выделяют и запоминают временной интервал наименьшей длины q, который преобразуют в кратную ей длительность S путем умножения выделенной наименьшей длительности на количество временных интервалов в исходной группе р, т. е. S = q p.

Формируют новую (первую) группу А₁{ a₁₁; a₁₂; a₁₃; . . . ; a_1j; . . . ; a_1n} (где первая нижняя цифра обозначает номер группы, вторая - номер позиции временного интервала в этой группе) временных интервалов путем вычитания полученной наименьшей длительности q из длительности каждого временного интервала предыдущей (исходной) группы, т. е.

а₁₁ = а₁ - q;

a₁₂ = a₂ - q;

= a₃ - ;

= a_j - ;

a_1n = a_n - q. Далее первую группу А₁ временных интервалов представляют и запоминают в виде признаков наличия временного интервала наименьшей длительности в первой группе, которые являются элементами первой теневой бинарной маски F₁, т. е.

А₁{ a₁₁; a₁₂; a₁₃; . . . ; a_1j; . . . ; a_1n}

F₁{ f₁₁; f₁₂; f₁₃; . . . ; f_1j; . . . ; f_1n} , F_1j - элемент маски j-го временного интервала a_1j на первом шаге, принимающий значения

0;

Для первой группы временных интервалов на втором шаге указанные действия повторяют, а именно сравнивают между собой длительности интервалов первой группы, выделяют и запоминают новый временной интервал наименьшей длительности q₁. Затем формируют длительность, кратную новой наименьшей длительности, путем умножения этой наименьшей длительности на количество временных интервалов в первой группе р₁, т. е. S₁ = q₁ p₁. Также формируют вторую группу временных интервалов А₂{ a₂₁; a₂₂; a₂₃; . . . ; a_2j ; . . . ; a_2n} путем вычитания последней наименьшей длительности q₁из длительности каждого временного интервала предыдущей (первой) группы, т. е.

а₂₁ = а₁₁ - q₁;

= a₁₂ - ;

= a_1j - ;

a_2n = a_1n - q₁.

Аналогично, вторую группу А₂ временных интервалов представляют и запоминают в виде признаков наличия временного интервала наименьшей длительности во второй группе, которые являются элементами второй теневой бинарной маски F₂, т. е.

А₂{ a₂₁; a₂₂; a₂₃; . . . ; a_2j; . . . ; a_2n}

F₂{ f₂₁; f₂₂; f₂₃; . . . ; f_2j; . . . ; f_2n}

Последовательность действий для третьей, четвертой, m-й групп аналогична, которая в конечном итоге сводится к выделению, запоминанию наименьшей длительности q_m-1 временного интервала, представлению и запоминанию в виде признака наличия этого интервала в m-й группе, как элемента логической единицы в теневой бинарной маске F_m, с учетом того, что a_mj0:

A_m{ a_m1; a_m2; a_m3; . . . ; a_mj; . . . ; a_mn}

F_m{ f_m1; f_m2; f_m3; . . . ; f_mj; . . . ; f_mn} .

Таким образом, после описанных преобразований формируют матрицу теневых бинарных масок, которая имеет вид:

где ((i { } ; i { } )).

Восстановление длительностей исходной группы временных интервалов основано на накоплении кратных длительностей групп, каждая i-я из которых может быть получена путем умножения наименьшей длительности q предыдущей группы А_i-1 временных интервалов на элементы теневой маски F_i, и формируют новую группу В_i:

F_i{ f_i1; f_i2; f_i3; . . . ; f_ij; . . . ; f_in} q_i-1 =

= B_i { b_i1; b_i2; b_i3; . . . ; b_ij; b_in} .

Затем формируют новую группу B_i-1 временных интервалов путем умножения наименьшей длительности q_i-2 предыдущей группы на элементы теневой бинарной маски F_i-1, т. е.

F_i-1 { f_(i-1)1; f_(i-1)2; f_(i-1)3; . . . ;

f_(i-1)j; . . . ; f_(i-1)n} q_i-2 = B_i-1{ b_(i-1)1;

b_(i-1)2; b_(i-1)3; . . . ; b_(i-1)j; . . . ; b_(i-1)n} .

Указанные действия повторяют для каждой новой группы до формирования первой группы В₁ временных интервалов, полученные кратные длительности последовательно суммируют и формируют (восстанавливают) исходную группу А временных интервалов

A_i= B_ij.

Описанный выше способ, например, для пяти шагов действий поясняется табл. 1 и 2. В частности, табл. 1 иллюстрирует формирование матрицы теневых бинарных масок, а табл. 2 - восстановление длительностей исходной группы временных интервалов.

Анализ научно-технической и патентной литературы показал, что известно применение теневых бинарных масок, а также параллельное сложение группы временных интервалов в отдельности, однако последовательности действий, обладающих совокупностью признаков, авторами не обнаружено.

Заявленная последовательность действий: представление и запоминание групп временных интервалов в виде признаков наличия временного интервала наименьшей последовательности в каждой группе с помощью элементов теневой бинарной маски, формирование матрицы теневых бинарных масок, а также восстановление исходной группы временных интервалов приводит к получению положительного эффекта (расширению области применения).

Таким образом, заявляемое решение соответствует критерию "существенные отличия".

Устройство, реализующее способ, содержит входы 1₁, 1₂, 1_n, блоки 2₁, 2₂, . . . , 2_n сравнения, блок 3 сравнения, блок 4 последовательного суммирования (накопления) кратных длительностей, блок 5 запоминания (хранения), блок 6 запоминания признаков наличия текущей наименьшей длительности в группах временных интервалов, блоки 7₁, 7₂, . . . , 7_nпоследовательного суммирования, выходы 8₁, 8₂, . . . , 8_n формирования (восстановления) длительности временных интервалов исходной группы, причем первые входы блоков 2₁, . . . , 2_n сравнения соединены с входами 1₁, . . . . , 1_n устройства и первыми выходами блоков 2₁, . . . , 2_n сравнения соответственно, вторые входы которых подключены к выходу блока 3 сравнения, кроме того, первые выходы блоков 2₁, . . . , 2_n соединены с соответствующими входами блока 3 сравнения. Вторые выходы блоков 2₁, . . . , 2_n сравнения подключены к группе входов блока 4 последовательного суммирования и группе входов блока 6 запоминания, а выход блока 3 сравнения соединен с входом блока 4 последовательного суммирования и блока 5 запоминания, выход которого подключен к первым входам блоков 7₁, . . . , 7_n последовательного суммирования. Вторые входы блоков 7₁, . . . , 7_nпоследовательного суммирования соединены с соответствующими выходами блока 6 запоминания, а выходы являются выходами 8₁, . . . . , 8_n длительностей исходной группы временных интервалов.

Реализация предложенного способа устройством осуществляется следующим образом.

На входы 1₁, 1₂, . . . 1_n (где n - максимальное количество временных интервалов в группе) подаются длительности временных интервалов исходной (первой) группы, с помощью блоков 2₁, 2₂, . . . . , 2_n сравнения выделяются разности между длительностями отдельных интервалов группы и интервалами меньшей длительности, блоком 3 сравнения выделяются интервалы наименьшей длительности, блок 4 последовательного суммирования (накопления) кратных длительностей выполняет умножение наименьших длительностей на количество временных интервалов в текущей группе, блоке 5 запоминания (хранения) последовательно по шагам фиксирует интервалы наименьшей длительности (q; q₁; q₂; . . . ; q_n-1), блок 6 запоминания последовательно по шагам фиксирует признаки наличия текущей наименьшей длительности соответственно в группах временных интервалов А₁, А₂, . . . , А_m, блоки 7₁, 7₂, . . . 7_n осуществляют последовательное суммирование, на выходах 8₁, 8₂. . . 8_n которого формируются (восстанавливаются) длительности временных интервалов исходной группы.

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

Поскольку в исходном состоянии на выходе блока 3 присутствует нулевой сигнал, то в первом действии сложения от каждой исходной длительности вычитается нуль с блока 3, и на выходах блоков 2₁ - 2₅получаются разности, фактически, равные исходным длительностям временных интервалов 11, 3, 5, 8 и 15, которые параллельно воздействуют по пяти входам на блок 4 и блок 3, где происходит выделение интервала наименьшей длительности из пяти исходных интервалов, т. е. в блоке 3 и 4 происходит образование пятикратной к минимальной и равной длительности 15, кратность которой определяется количеством длительностей первой группы. При этом в блоке 5 запоминания фиксируется наименьшей длительность временного интервала, равная 3, а в блоке 6 - признаки наличия данной наименьшей длительности в текущей группе временных интервалов в соответствии со следующим выражением:

0; где f_ij - группа j-й временной длительности a_ij для i-й группы;

a_ij - разность между интервалами меньшей длительности q_i-1 и длительностями интервалов a_i1; a_i2; . . . ; a_in для i-й группы.

Таким образом, информация в блоке 6 на первом шаге для первой группы А₁ временных интервалов может быть записана в виде первой теневой бинарной маски следующим образом:

{ f₁₁; f₁₂; f₁₃; f₁₄; f₁₅} { 1 1 1 1 1}

На втором шаге в блоках 2₁ - 2₅ формируются разности между исходными длительностями 11, 3, 5, 8 и 15 и минимальной длительностью первой группы, равной трем. Образуются разности 8, 2, 5 и 12 второй группы. Наименьшая длительность временного интервала второй группы, равная двум, формируется в блоке 3 в четырехкратном размере, т. е. 8, кратность которой определяется количеством интервалов второй группы, суммируется в блоке 4 с пятикратной минимальной длительностью первой группы, в данном случае с 15.

Аналогично, на втором шаге для второй группы временных интервалов в блоках 5 и 6 запоминания фиксируется соответственно следующая информация; временной интервал наименьшей длины, в данном случае равный q₁ = 2, а группа временных интервалов А₂ представляется и фиксируется в виде второй теневой бинарной маски F₂ как:

{ f₂₁; f₂₂; f₂₃; f₂₄; f₂₅} { 1 0 1 1 1}

На третьем шаге в блоках 2₁ - 2₅ формируются разности между длительностями 8, 2, 5 и 12 второй группы и минимальной длительностью второй группы. Образуются значащие разности 6, 3 и 10 третьей группы. Минимальная длительность интервалов третьей группы, равная трем, формируется в блоке 3 и в трехкратном размере 9, кратность которой определяется количеством длительностей третьей группы, суммируется в блоке 4 с полученной на предыдущих двух действиях суммой пяти- и четырехкратных. Следовательно, в блоке 5 (запоминания) при этом фиксируется длительность, равная q₂ = 3, а в блоке 6 запоминания третья группы временных интервалов А₃ фиксируется ипредставляется в виде третьей теневой бинарной маски F₄ как

{ f₃₁; f₃₂; f₃₃; f₃₄; f₃₅} { 1 0 0 1 1}

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

В блоках 5 и 6 запоминания при этом оказывается зафиксированной следующая информация соответственно: длительность, равная q₃ = 3, а четвертая группа временных интервалов А₄ представляется в виде четвертой теневой бинарной маски F₄{ f₄₁; f₄₂; f₄₃; f₄₄; f₄₅} { 1, 0, 0, 0, 1} .

На пятом (последнем) шаге в блоке 4 накапливается однократная минимальная длительность, равная четырем, к кратным предыдущих четырех действий, а в блоках 5 и 6 запоминания фиксируется соответственно текущая минимальная длительность временного интервала q₄, равная 4, а признаки ее наличия в текущей группе А₅ временных интервалов представляются в виде пятой теневой бинарной маски F₅ следующим образом:

{ f₁₅; f₂₅; f₃₅; f₄₅; f₅₅} { 0 0 0 0 1}

Таким образом, схематически параллельное сложение сигналов длительностей временных интервалов 11, 3, 5, 8, 15 можно отобразить следующим образом:

11 3 5 8 15

3 1-й шаг

15 (3x5)

8 0 2 5 12

2 2-й шаг

8 (2x4)

6 0 3 10

3 3-й шаг

9 (3x3)

3 0 7

3 4-й шаг

6 (3x2)

0 4

4 5-й шаг

4 (4x1)

Информацию, зафиксированную в блоке 6 в процессе параллельного сложения временных длительностей, можно представить в виде матрицы

где количество строк соответствует числу шагов параллельного сложения временных длительностей, а количество столбцов - числу временных интервалов в исходной группе. Соответственно в блоке 5 запоминания зафиксированы наименьшие длительности q, q₁, . . . , q₄, равные { 3, 2, 3, 3 4} . Используя содержимое блоков 5 и 6 и блоки 7₁. . . , 7_nпоследовательного суммирования, можно параллельно за 5 шагов восстановить временные длительности исходной группы. Рассмотрим параллельное восстановление длительностей группы из пяти временных интервалов. На первом шаге из блоков 5 и 6 запоминания считывается соответствующая информация, например, зафиксированная на первом шаге параллельного сложения временных интервалов, т. е. длительность q, равная 3, и первая строка матрицы признаков, т. е. первая бинарная маска F₁ = { 1 1 1 1 1} . Эта информация поступает на входы соответствующих блоков 7₁, . . . 7_n последовательного суммирования, где происходит поэлементное умножение на элементы теневой бинарной маски F₁, причем, если соответствующий элемент теневой бинарной маски F_ij = 1, то к содержимому соответствующего блока 7₁, . . . , 7_n последовательного суммирования прибавляется величина q (исходное состояние этих блоков равно нулю), значит содержимое блоков 7₁, . . . , 7₅ будет одинаково и в данном случае равно 3, т. е. В₁{ 3 3 3 3 3} .

На втором шаге с учетом содержимого блоков 5 и 6 запоминания к содержимому блоков 7₁, 7₃, 7₄, 7₅ прибавляется временная длительность, равная 2. Следовательно, сформируется новая группа временных интервалов В₂{ 2 0 2 2 2} , а содержимое блоков 7₁, . . . , 7₅ будет { 5 3 5 5 5} .

На третьем, четвертом, пятом шагах выполняются аналогичные операции.

Таким образом, схематически параллельное восстановление сигналов длительностей временных интервалов 11, 3, 5, 8, 15, описанное выше, поясняется таблицей 2.

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