Оптимизация вычислений MTIE

Материал из b4wiki
Перейти к: навигация, поиск

Содержание

Введение

Эта статья описывает алгоритм быстрого и точного расчёта максимально допустимой ошибки временного интервала (MTIE), как характеристики долговременной стабильности синхронной передачи сигнала.

О том, откуда возникает задача измерений и расчётов этой характеристики, можно прочитать в статье "В погоне за Вандером".

Обозначения и постановка задачи

Входные данные - последовательность целых значений временной ошибки - Time Error (TE) samples. Обозначим их

x(0), x(1), ... x(n)

Для этой последовательности необходимо расчитать максимальную ошибку временного интервала - Maximum Time Interval Error (MTIE). Она зависит от длины рассматриваемого интервала.

Рассмотрим интервалы длины k, и используем для них следующее обозначение:

[ x(i), x(i+k) ] = { x(i), x(i+1), ... x(i+k) }, 
   где i = 0 .. (n-k)

А для экстремумов таких интервалов

max(i,j) = max [ x(i), x(j) ]
min(i,j) = min [ x(i), x(j) ],
   где i,j = 0 .. n

Тогда MTIE для интервала длины k расчитывается по следующей формуле:

MTIE(k) = max { max(i,i+k) - min(i,i+k) | i = 0 .. (n-k) }

то есть как максимум разностей экстремумов всех интервалов данной длины.

В реальности вычисления должны производиться во время измерений. Поэтому в каждый момент времени есть только начало последовательности x(t), а в каждый следующий момент времени добавляется новая точка.

Глобальным экстремумом в данный момент времени будем считать экстремум интервала наибольшей длины: [x(1), x(n)]. А локальным экстремумом будем называть экстремум рассматриваемого интервала.

Расчёт MTIE должен производиться для текущего набора точек, а при появлении новой - пересчитываться, с учётом нового значения. То есть расчёт должен производиться в реальном времени.

Алгоритм вычисления MTIE

Общая структура

Итерация алгоритма для вычисления MTIE имеет следующий вид:

  1. считать новую точку x(n+1).
  2. добавить новое значение MTIE для интервала [x(1), x(n+1)].
  3. пересчитать (обновить) предыдущие значения MTIE.

Шаг 2 сводится к проверке того, что новая точка является новым глобальным экстремумом и добавлению нового значения MTIE, равного разности глобальных экстремумов:

max(1,n+1) - min(1,n+1)

Шаг 3 необходим, поскольку с появлением новой точки, образуются новые интервалы всех длин, содержащие эту точку:

[x(i), x(n+1)], где i = 1 .. n

А каждый новый интервал может изменить соответствующее значение MTIE.

В этом-то процессе обновления и заключается основная часть алгоритма. Если просто пересчитывать заново все точки - вычисления будут очень трудоёмкими. Необходимо исключить все лишние операции, выполнение которых не является необходимым для пересчёта значений MTIE.

Так как MTIE - это максимальная разность экстремумов, необходимо понять, является ли новая точка новым локальным экстремумом для рассматриваемого интервала, и если это так, сравнить разность новых экстремумов этого интервала с соответствующим значением MTIE.

Поскольку новая точка влияет только на появление крайних правых интервалов, мы будем рассматривать экстремумы только этих интервалов, и обозначим их следующим образом:

m(k) = min(n-k, n)
M(k) = max(n-k, n),
    где k = 0 .. n

При k = 0 получается вырожденный интервал - то есть просто точка x(n). Зачем это нужно, будет видно дальше.

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

m'(k+1) = min{ m(k), x(n+1) }
M'(k+1) = max{ M(k), x(n+1) }
  (штрихом будем обозначать обновлённые экстремумы)

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

Таким образом из последовательностей

m(0), m(1), ... m(n)
M(0), M(1), ... M(n)

получатся последовательности

m'(1), m'(2), ... m'(n+1)
M'(1), M'(2), ... M'(n+1)

Здесь нам пригодились значения m(0) = M(0) = x(n), чтобы получить из них значения m'(1) и M'(1). И для того, чтобы можно было также совершить следующую итерацию, определим нулевые члены для полученных последовательностей:

m'(0) = M'(0) = x(n+1)

Итак, с новыми экстремумами обновление MTIE выглядит просто:

MTIE'(k) = max{ MTIE(k), M'(k) - m'(k) }

Оптимизация алгоритма

Заметим, что последовательности m(i) и M(i) монотонны:

m(i) > m(i+1)
M(i) < M(i+1)

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

Это можно использовать, чтобы обновлять не всю последовательность, а только её начало:

Выберем минимальный индекс i, такой что x(n+1) > m(i), 
  тогда для любого j > i, обновлять значения не имеет смысла, 
  т.к. x(n+1) > m(i) > m(i+1) > ... > m(n).
То есть 
   m'(j) = m(j-1), при j-1 > i.
   m'(j) = x(n+1), иначе.

Запишем члены последовательности m'(i) и соответствующие им значения в виде таблицы:

m'(1) | ... | m'(i)  | m'(i+1) | ... | m'(n+1)
x(n+1)| ... | x(n+1) | m (i)   | ... | m (n)

Аналогичное рассуждение можно провести для последовательности максимумов, поменяв местами знаки (<) и (>).

Так же можно заметить, что на каждой итерации необходимо обновлять только одну из последовательностей экстремумов:

Если x(n+1) > x(n), то x(n+1) > m(0) > m(1) > ... > m(n),
                   (то есть обновлять минимумы нет смысла).
Если x(n+1) < x(n), то x(n+1) < M(0) > M(1) > ... > M(n),
                   (то есть обновлять максимумы нет смысла).  
Если x(n+1) = x(n), то не нужно обновлять ни то ни другое.

При этом, в любом случае после обновления необходимо добавить x(n+1) в качестве m'(0) и M'(0).


Эффективная реализация

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

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

В действующей реализации алгоритма для хранения последовательностей минимумов, максимумов и MTIE использованы одноноправленные списки "со сжатием". Это означает, что каждый узел такого списка содержит

  1. хранимое значение
  2. количество таких значений, идущих подряд
  3. ссылку на следующий узел

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

Такой подход позволяет сэкономить значительное количество памяти, поскольку хранятся только необходимые значения, и значительный объем вычислений, поскольку операции обновления не повторяются для одинаковых значений, а производятся над "блоками" таких значений целиком.

Заключение

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



Алексей Алехин
Метротек, СПб
Сентябрь 2009

Личные инструменты
Пространства имён

Варианты
Действия
разработки
технологии
разное
Инструменты