Постановка задачи разработки быстрых алгоритмов

 

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

1. Прямое применение ДПФ (3.6).

2. Использование быстрых алгоритмов вычисления ДПФ (быстрого преобразования Фурье - БПФ).

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

БПФ - есть детальное описание процедуры вычисления ДПФ, которое, однако, не есть очевидный метод преобразования входного массива x(n) в выходной массив X(k), при этом мы жертвуем концептуальной ясностью вычислений в пользу эффективности.

Критерием эффективности в подавляющем большинстве случаев является время вычислений.

Приведем тривиальный пример существования быстрых алгоритмов.

Пусть надо вычислить число A.

.

Его сложность - 3 сложения + 4 умножения.

Путем преобразования правой части этого выражения (расстановки скобок) можно придти к выражению

.

Сложность полученного выражения - 2 сложения + 1 умножение. Естественно, второй способ вычисления числа А более эффективен.

Алгоритм Кули - Тьюки

 

   Для построения БПФ-алгоритма Кули - Тьюки предположим, что длина входного массива преобразования Фурье может быть представлена в виде произведения [9]

 

N = N¢N¢¢.

 

   В выражении для преобразования Фурье (1.6) сделаем следующую замену записи каждого индекса:

n = n¢+N¢n¢¢,

n¢=0,…,N¢-1,n¢¢=0,…,N¢¢-1,

k = N¢¢k¢+k¢¢,

k¢=0,…,N¢-1,k¢¢=0,…N¢¢-1.

Тогда

.

 

   Раскроем скобки в показателе степени поворачивающего множителя и обозначим:

 

 

С учётом того, что

,

 

получим

    , .   (3.7)

 

   Хотя для понимания полученная формула более трудна, чем исходная (3.6), однако число входящих в неё умножений и сложений существенно меньше. А именно, она содержит:

Сложений N (N'+N'' - 2 ).

Умножений N (N'+N'' + 1 ).

   В качестве примера на рис. 3.1 приведена структура алгоритма БПФ с N=6.

При этом количество входных данных представляется в виде произведения

N = N'·N'' = 3·2.

   Во многих приложениях, в которых используется алгоритм Кули-Тьюки, длина преобразования равна степени двух или четырёх. Для построения БПФ-алгоритма длина 2^m преобразования представляется в виде 2·2 ^m-1 или  

2^m-1·2. В этом случае говорят о БПФ-алгоритме по основанию два. Аналогично, длина 4 ^m преобразования разлагается в виде 4·4 ^m-1 или 4 ^m-1·4, и тогда говорят о БПФ-алгоритме Кули-Тьюки по основанию четыре. Если в 2^m-точечном алгоритме Кули-Тьюки по основанию два полагается N'=2 и

 

Рис.3.1-Структура БПФ-алгоритма Кули – Тьюки с N=6

 

N''=2 ^m-1, то он называется БПФ-алгоритмом Кули -Тьюки по основанию два с прореживанием по времени. Учитывая, что , в этом случае уравнения, задающие БПФ, записываются в следующем простом виде:

 

              ;                    (3.8)

 

              .                (3.9)

 

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

- с чётными индексами;

- с нечётными индексами.

   Множество компонент выходного вектора разбивается при этом тоже на два подмножества:

- первых N/2 компонент;

- последующих N/2 компонент.

   2^m-точечный БПФ-алгоритм Кули -Тьюки по основанию два, в котором N'=2 ^m-1 и N''=2, называется БПФ-алгоритмом Кули - Тьюки по основанию два с прореживанием по частоте. Уравнения БПФ в этом случае преобразуются к виду

              .                          (3.10)

 

   Прореживание по частоте разбивает компоненты входного вектора на два подмножества, содержащие соответственно первые N/2 компонент и последующие N/2 компонент. Компоненты выходного вектора разбиваются на подмножества:

- компоненты с чётными индексами;

- компоненты с нечётными индексами.

   Достаточно широко на практике применимы БПФ-алгоритмы Кули -Тьюки по основанию 4. Они могут быть использованы в случаях, когда длина преобразования N равна степени 4, и получаются её разложением в виде

4·4 ^m-1 или 4 ^m-1·4. Уравнения этой формы БПФ можно получить простой подстановкой в обобщённое уравнение БПФ-алгоритма Кули - Тьюки (3.7):

- для прореживания по времени - N'=4 и N''= N/4;

- для прореживания по частоте - N''=4 и N'= N/4.

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

 

 

ЛЕКЦИЯ 5

 

ПРЕОБРАЗОВАНИЕ СИГНАЛОВ

 

---

Дата добавления: 2018-02-15; просмотров: 1278; Мы поможем в написании вашей работы!

Поделиться с друзьями:

---

---

Мы поможем в написании ваших работ!