Дискретные ортогональные преобразования

Учреждение  образования

Белорусский государственный  университет информатики 

и радиоэлектроники

Факультет компьютерных технологий ИИТ

 

 

 

 

 

 

 

 

 

 

 

 

 

Лабораторная  работа №1

тема: «Дискретные  ортогональные преобразования»

 

 

 

 

 

 

 

 

 

 

 

 

 

Проверил:        Выполнил:

Митюхин А.И.         уч-ся гр. 080511 

Голухов А.В.

 

 

 

 

 

Минск

 2011

 

Цель работы: изучение свойств дискретных ортогональных  преобразований: дискретное преобразование Фурье (ДПФ), дискретное преобразование Уолша–Адамара (ДПУА), дискретное преобразование Хартли (ДПХ), дискретное косинусное преобразование (ДКП).

 

Свойство линейности.

Линейность: спектр суммы сигналов равен сумме спектров слагаемых, т.е. если 

v(n)=s(n)+u(n) ,       то  Сv(n)=Сs(n)+Сu(n)

 

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

Свойство ортогональности  ДПФ:

Свойство ортогональности  ДПУА:

, где E – единичная матрица размера N, H_N - ортогональная бинарная матрица Адамара (NхN);

Свойство ортогональности  ДПХ:

Свойство ортогональности ДКП:

, где

E – единичная матрица размера N;

[φ(k, n)]-квадратная матрица ДКП размером (NхN);

 

Определения дискретного  ортогонального преобразования: прямого  преобразования, обратного преобразования.

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

 

где Q – это ортогональные функции, по которым раскладывается произвольная функция;

S_i – коэффициенты разложения или же совокупность таких коэффициентов составляет спектр сигнала по системе функций Q(i,t). Для того чтобы мы могли переходить от спектра к сигналу и от сигнала к спектру мы должны иметь возможность вычислять эти коэффициенты. Поэтому мы должны иметь возможность вычислить эти коэффициенты:

,

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

Векторно-матричное  определение преобразования.

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

 

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

Заданный массив данных: N = 6, x(n) = {2; 1; 2; 3;3;4}

Вычисление  прямого и обратного преобразований. Матричная форма преобразований.

 

1. Дискретное преобразование Фурье.

Прямое преобразование:

, k =0, 1, …,N –1, где

W=e^-i2р/N – поворачивающий множитель

N – количество дискретных отсчетов сигнала

C(k) - N комплексных амплитуд синусоидальных сигналов

x(n) — измеренные значения сигнала которые являются входными данными для прямого преобразования и выходными для обратного

 

;

;

 

Обратное преобразование:

 n =0, 1, …,N –1, где

W=e^i2р/N – поворачивающий множитель

N – количество дискретных отсчетов сигнала

C(k) - N комплексных амплитуд синусоидальных сигналов

x(n) — измеренные значения сигнала которые являются входными данными для прямого преобразования и выходными для обратного

;

 

 

Векторно-матричное  преобразование:

Прямое дискретное преобразование:

Ядро преобразования:

Обратное дискретное преобразование Фурье:

Ядро преобразования:

 

 

2. Дискретное преобразование Уолша–Адамара.

Прямое дискретное преобразование Уолша–Адамара имеет вид

 

 где

H_N - ортогональная бинарная матрица Адамара (NхN);

H_N для N=8 имеет вид:

 

 

Обратное дискретное преобразование Уолша–Адамара в матричном виде:

 

      3.    Дискретное преобразование Хартли.

Прямое ДПХ:

 где

Обратное ДПХ:

Матричная форма  одномерного прямого ДПХ:

 где

- матрица дискретного множества  ортогональных функций ДПХ размером (NxN).

Матричная форма  одномерного обратного ДПХ:

 

ДКХ заданной последовательности:

ядро ДПХ:

Прямое ДПХ  для заданной последовательности:

Обратное ДПХ  для заданной последовательности:

 

 

 

 

1. Дискретное косинусное преобразование.

Прямое ДКП:

     Обратное ДКП:

       где

       

Прямое ДКП  в матричном виде:

где:

[φ(k, n)]-квадратная матрица ДКП размером (NхN):

Обратное ДКП  в матричном виде:

Дискретное косинусное преобразование заданной последовательности.

Ядро ДКП:

 

 

 

Транспонированное ядро для обратного ДКП:

 

Вывод: в рассмотренных дискретных преобразованиях вычислительная сложность  для прямого и обратного преобразований равна: аддитивная = , мультипликативная: = (умножение матрицы ядра NxN на вектор измеренных значения сигнала). Однако, в ДПФ вычислительная сложность увеличивается за счет того, что операции производятся над комплексными числами, так как одно комплексное умножение эквивалентно четырем   операциям   действительного   умножения   и двум операциям сложения, которые необходимы в случае преобразования Фурье.