8. Алгоритмы для вычисления преобразования хаара

8.1. Ортогональные функции Хаара

Множество функций Хаара har(n,m,t) (рис. 8.1), образующих периодическую, ортонормированную и полную систему функций, было предложено в 1910 году. Рекуррентное соотношение, позволяющее получить har(n,m,t), имеет вид

;

где , 1  m  2 ^r

Рис. 8.1. Функции Хаара для N=8

Коэффициенты преобразования Хаара Y(k), , соответствующие входной последовательности {X(m)}, получаются в результате преобразования

, где H^*(n) – матрица Хаара размерностью NN.

Для N=8

.

Рассматривая H^*(n), можно отметить, что N/2 коэффициентов преобразования Хаара соответствуют корреляции двух соседних точек в пространстве входных последовательностей, N/4 коэффициентов соответствуют связям четырех соседних точек и так далее до N/N коэффициентов, соответствующих всем N координатам пространства входных последовательностей. Это означает, что область преобразования в случае преобразования Хаара обладает свойством как локальной, так и глобальной чувствительности. При дискретном преобразовании Фурье и преобразовании Уолша-Адамара каждый коэффициент преобразования является функцией всех координат пространства входных последовательностей (свойство глобальной чувствительности), а в преобразовании Хаара это относится к первым двум коэффициентам.

Для осуществления преобразования Хаара требуется 2(N-1) операций сложения / вычитания и N операций умножения.

8.2. Быстрое преобразование Хаара

Для N=8 алгоритм преобразования Хаара типа Кули-Тьюки может быть представлен следующим образом. В исходной матрице преобразования Хаара необходимо переупорядочить столбцы H(3), пользуясь последовательно двоичной инверсией при N=8,4,2.

Шаг 1. Переставим столбцы H^*(3) в соответствии с двоичной инверсией их номеров при N=8, т.е. {0,1,2,3,4,5,6,7}  {0,4,2,6,1,5,3,7}, что приведет к

.

0 1 2 3 0 1 2 3

Шаг 2. Переставим столбцы (44) матриц, заключенных в квадраты в соответствии с двоичной инверсией номеров столбцов при N=4, т.е. {0,1,2,3}  {0,2,1,3}, что приведет к матрице

.

Шаг 3. Переставим столбцы (22) матриц, заключенных в квадраты в соответствии с двоичной инверсией номеров столбцов при N=2, т.е. {0,1}  {0,1}, что приводит к матрице, совпадающей с .

Граф-схемы прямого и обратного быстрого преобразования Хаара представлены соответственно на рис 8.2 и 8.3.

Рис. 8.2. Граф-схема прямого быстрого преобразования Хаара

Тогда спектр можно определить как

P_h(0)=F²(0);

P_h(1)=F²(1);

;

.

В общем виде можно записать

P_h(0)=F²(0);

; .

Рис. 8.3. Граф-схема быстрого обратного преобразования Хаара

9. Стационарные случайные процессы

Случайный процесс ( ), иначе временной ряд или стохастический процесс, обозначается символом {·}- это совокупность действительнозначных (или комплекснозначных) функций, которую можно охарактеризовать её вероятностной структурой. Каждая отдельная функция , где - переменная, а фиксировано, называется выборочной функцией. С практической точки зрения, выборочную функцию (или некоторый отрезок выборочной функции конечной длины) можно считать наблюдаемым результатом отдельного эксперимента. Возможное число экспериментов определяется выборочным пространством индексов , причём последнее может быть счётным или несчётным (рис. 9.1).

Рис. 9.1. Ансамбль реализаций, задающий случайный процесс

Рассмотрим два произвольных случайных процесса и . В первую очередь, представляют интерес средние значения по ансамблю в произвольный фиксированный момент времени , где и - случайные величины от аргумента . Такие средние значения определяются:

, (9.1)

где Е – символ математического ожидания.

Следующие важные статистические характеристики – это корреляционные функции, определённые для произвольных фиксированных моментов времени и .

(9.2)

В общем случае эти величины различны для различных комбинаций и .

При :

(9.3)

Следовательно, корреляционные функции и совпадают с обычными дисперсиями процессов и в фиксированный момент времени, в то время как представляет собой корреляцию случайных величин и .

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

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

Для стационарных случайных процессов и средние значения постоянны и не зависят от . То есть:

(9.4)

Где , - плотности вероятности случайных величин и соответственно.

В свою очередь, для произвольных фиксированных величин и :

(9.5)

Величины и называются автокорреляционными или ковариационными функциями процессов и соответственно, а называется взаимной ковариационной функцией процессов и .

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

В терминах плотностей вероятности:

(9.6)

При произвольных и ковариационные функции связаны с корреляционными с помощью соотношений:

(9.7)

Следовательно, корреляционные функции совпадают с ковариационными, если средние значения равны нулю.

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

Из предположения стационарности следует, что ковариационные функции и - чётные функции от , т.е.

(9.8)

В то же время взаимная ковариационная функция удовлетворяет соотношению:

(9.9)

Доказательство:

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

Поскольку результат не зависит от сдвига начала отсчёта, то можно заменить на до взятия математического ожидания. Поэтому:

Что и требовалось доказать.

При справедливо:

(9.10)

Т.е. эти соотношения – частный случай формулы (9.9).

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

В случае ансамбля выборочных функций среднее значение (математическое ожидание) и ковариационная функция определяются как:

(9.11)

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

Аналогично ковариационная функция вычисляется путём усреднения по ансамблю произведений мгновенных значений в моменты времени и .

Рис. 9.2. Классификация случайных процессов.

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

В этом случае среднее значение и ковариационная функция , вычисленные по -ой реализации будут равны:

(9.12)

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

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

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

(9.13)

где - дельта-функция Дирака, равная нулю всюду, кроме точки , и интеграл от неё равен единице по любому интервалу, содержащему начало координат; коэффициент - скалярная величина, называемая уровнем мощности или интенсивностью белого шума.