Реализация алгоритма обратного БПФ

Используется точно такой же программный модуль, как и для БПФ, только:

1. Входными значениями являются коэффициенты Фурье;

2. Степень коэффициента W меняет знак на противоположный;

3. Нормализация не выполняется.

Бит-инверсия также выполняется в самом начале.

Порядок выполнения работы

Используя сведения, приведенные в теоретической части и указаниях к выполнению, найти Быстрое преобразование Фурье по алгоритму с прореживанием по времени с замещением. Необходимо учесть, что исходная последовательность действительная, результат – комплексная.

1. Считать с диска отсчеты измеренного сигнала.

2. Построить график полученного сигнала: меню Вставка > График > X-Y зависимость.

3. Разработать программный блок БПФ Алгоритм БПФ, использующий указанные возможности, называют алгоритмом с замещением.

4. Найти модуль спектральных коэффициентов.

5. Используя встроенную функцию FFT, найти ДПФ входной последовательности.

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

Задание на самостоятельную работу

Разработать программу для обратного БПФ.

Оформление отчета

В отчете необходимо представить программу БПФ выполненную в MathCAD и график совмещенных результатов БПФ, выполненных с использованием программы и встроенной функции FFT.

Разновидности БПФ и оптимизация его реализации

Данный раздел не написан по нескольким причинам:

1. Ограничение времени на выполнение работы;

2. Это имеет смысл при изучении ЦОС для специальностей с уклоном на программирование (углубленном изучении программирования);

3. При углубленном изучении ЦОС, для самостоятельной проработки;

4. Элементарная нехватка времени.

Что здесь могло бы быть:

1. Обратное БПФ;

2. Ускорение БПФ для действительной последовательности (обработка двух последовательностей одновременно или обработка последовательности удвоенной длины);

3. Использование итеративного БПФ вместо рекурсивного;

4. БПФ, для которого N ≠ 2 ^m;

5. Да мало ли чего еще – нет предела совершенству.

Возможно, часть из перечисленного или все будет со временем внесено, а может быть и нет.

Коэффициенты W_N^k при реализации алгоритма можно представить в виде действительной (cos) и мнимой (sin) частей и хранить их в разных ячейках (переменных). Аналогично нужно представлять входную последовательность x (с нулевыми мнимыми частями y), выходную и промежуточные результаты.

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

Вопросы к лабораторной работе

1. Для чего используют быстрое преобразование Фурье?

2. За счет чего количество операций при БПФ меньше, чем при обычном ПФ?

3. Какой принцип используется в алгоритме БПФ?

4. Чему равно количество этапов БПФ?

5. Что является центральной операцией БПФ?

6. Что такое бит - инверсия? Какова ее цель?

7. В чем разница алгоритма с прореживаем по времени от алгоритма с прореживанием по частоте?

8. Что называют алгоритмом с замещением?

9. Изобразите «бабочку» для точки с некоторым номером на некотором этапе, заданными преподавателем (например, для 83 точки на 4 этапе). Для выполнения этого надо определить, скольки точечное преобразование M выполняется на данном этапе (сколько точек в домене); какое расстояние между точками бабочки (M /2); какой является точка в бабочке – верхней или нижней (это имеет большое значение); какой номер бабочки; какой номер бабочки в домене (k).

Лабораторная работа №3. Дискретное косинусное преобразование (ДКП)

Цель работы: Изучение дискретного косинусного преобразования.

Необходимые теоретические сведения

Дискретное косинусное преобразование (ДКП) широко применяется в системах сжатия сигналов (рис. 1). Исходный аналоговый сигнал x (t) преобразуется с помощью АЦП в цифровую последовательность x [ n ], которая запоминается в буферной памяти. Накопленная выборка длины N поступает на блок прямого ортогонального преобразования, где вычисляется последовательность X [ k ]. Прямое ортогональное преобразование должно обладать такими свойствами, чтобы последовательность X [ k ] имела малое число значимых членов. Кодированию подвергаются только члены X [ k ], которые переносят существенную информацию (энергию). За счет этого, в основном, и достигается сжатие сигнала.

Рисунок 1 – Сжатие сигналов на основе ортогональных преобразований

Ключевым моментом в реализации метода является выбор ортогонального преобразования, а также выбор способа кодирования коэффициентов X [ k ]. Ортогональное преобразование считается эффективным, если оно обладает быстрым вычислительным алгоритмом, обеспечивает наибольшую концентрацию энергии спектральных составляющих в небольшом числе членов последовательности X [ k ] и малые искажения при их кодировании и декодировании. Очень хорошо сформулированным требованиям отвечает ДКП.

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

Подход с модификацией сигнала работает следующим образом.

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

Прямое и обратное ДКП последовательности x [ n ] имеют вид

	,	(1)
	,	(2)

где N - длина выборки x [ n ]; X [ k ] - коэффициенты ДКП; совокупность весовых функций, причем

.

(3)

Обратим внимание на то, что коэффициенты X [ k ] в (1) не являются комплексными. Они имеют действительные значения. Кроме этого, в соответствии с общим принципом построения ДКП, последовательность x [ n ] является действительной и четной. Поэтому ДКП как бы применяется не к исходной выборке x [ n ] (рис. 1,а), а к преобразованной последовательности, являющейся четным расширением x [ n ]:

.

(4)

Рисунок 1 – Преобразование входной последовательности

Последовательность y [ n ] должна рассматриваться как периодическая с периодом 2 N (рис. 1, б). Данное обстоятельство необходимо учитывать при синтезе сигналов в соответствии с (4).

В интерпретации базисных функций, мы просто используем базисные функции, которые являются только косинусами, но одновременно мы разрешаем использовать половинные частоты. То есть вместо использования частот 0, 1, 2, 3 и 4 мы используем частоты 0, 0.5, 1, 1.5, 2, 2.5, …. Кроме того, для симметричности мы начинаем оцифровку косинусных базисных функций не на нулевых периодах, а со смещением в половину расстояния между пикселями.

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

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

Значения коэффициентов ДПФ X_F (k) 2 N -точечной последовательности y [ n ] определяются по формуле (M =2 N):

,

(5)

где – как и прежде – вспомогательная функция; M =2× N.

Для удобства рассмотрения преобразуем выражение (5):

(6)

Из (1) и (6) следует, что коэффициенты ДКП X_C [ k ] могут быть вычислены через коэффициенты ДПФ X_F [ k ]:

(7)

Наличие связи между коэффициентами Фурье и ДКП позволяет вычислять ДКП с использованием алгоритма БПФ.

Достоинством ДКП является то, что по своей эффективности оно мало отличается от оптимального преобразования Карунена – Лоэва и существенно превосходит преобразование Фурье.

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

(8)

где x [ n ] и x ´[ n ] - отсчеты исходного и восстановленного сигнала соответственно; N – длина сигнала.

Порядок выполнения работы

Данная работа выполняется на ПЭВМ с использованием программы MathCAD 15.

1. Считать с диска отсчеты измеренного сигнала.

2. Построить график полученного сигнала.

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

4. Используя формулы (4), (5) и программу вычисления БПФ[1] из предыдущей работы, найти коэффициенты ДПФ X_F (_k) 2 N -точечной последовательности y [ n ].

5. Используя формулу (7), пересчитать коэффициенты Фурье в коэффициенты ДКП. Вывести полученные значения на экран и построить график.

6. Сравнить результаты пп 3. и 5, выведя их на один график.

7. Используя программу вычисления БПФ[2] из предыдущей работы, выполнить ДПФ исходной последовательности.

8. Восстановить сигнал. Для этого выполнить обратные преобразования ОДКП по формуле (2) для коэффициентов ДКП п.5 и ОДПФ коэффициентов Фурье п.7, используя заданное преподавателем количество значимых коэффициентов ДКП и ДПФ (обычно 2, 4, 8 и 16).

9. Полученные значения восстановленного сигнала по ОДКП и ОДПФ вывести на экран и построить графики вместе с графиком исходной последовательности для визуальной оценки искажений восстановления при неполном числе коэффициентов.

10. Используя формулу (8), вычислить среднеквадратические ошибки при заданных количествах первых коэффициентов и занести их в таблицу. Сравнить эффективность ДКП и ДПФ на предмет сжатия сигнала.

Оформление отчета

В отчете необходимо представить программу ДКП выполненную в MathCAD, таблицы пп. 3, 5, 9 и 10 и графики пп. 9 и 10.

Вопросы к лабораторной работе

1. В какой области практического использования применяют дискретное косинусное преобразование?

2. Как в общем выглядит процесс кодирования с использование ДКП.

3. Какие основные требование предъявляют к преобразованию, используемому в системах сжатия сигнала?

4. Как выглядят формулы прямого и обратного ДКП?

5. За счет чего коэффициенты ДКП имеют действительные, а не комплексные, как в ДПФ, значения?

6. При каком виде функции особенно сказывается преимущество ДКП перед ДПФ?

7. Какой метод используют для ускорения вычисления коэффициентов ДКП?

8. Как выглядит связь между коэффициентами ДКП и коэффициентами ДПФ?

9. Какой метод используется для сравнения эффективности ДКП и ДПФ в данной работе?