Оптимизация вычислений 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 имеет следующий вид:
- считать новую точку x(n+1).
- добавить новое значение MTIE для интервала [x(1), x(n+1)].
- пересчитать (обновить) предыдущие значения 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 использованы одноноправленные списки "со сжатием". Это означает, что каждый узел такого списка содержит
- хранимое значение
- количество таких значений, идущих подряд
- ссылку на следующий узел
Так как все три последовательности монотонны, любые совпадающие значения могут идти только подряд. Поэтому в описанной реализации списка будут храниться только различные элементы.
Такой подход позволяет сэкономить значительное количество памяти, поскольку хранятся только необходимые значения, и значительный объем вычислений, поскольку операции обновления не повторяются для одинаковых значений, а производятся над "блоками" таких значений целиком.
Заключение
Итак, в этой статье был описан оптимизированный по сложности и памяти алгоритм вычисления MTIE. Конкретная реализация такого алгоритма позволит вычислять MTIE на измеряющих приборах, имеющих скромные аппаратные ресурсы, с абсолютной точностью и в реальном времени.
Алексей Алехин
Метротек, СПб
Сентябрь 2009
