2.4. Дискретные преобразования Фурье для общего случая периодической дискретизации сигнала
В разд. 1.5 было показано, что
можно вывести различные алгоритмы обработки применительно к сигналам,
полученным с использованием различных растров периодической дискретизации.
В этом разделе мы используем тот
же подход, который привел нас к алгоритмам ДПФ и БПФ, к общему случаю
периодической дискретизации сигналов. Будет показано, что такие сигналы можно
представить дискретными рядами Фурье и дискретными представлениями
преобразования Фурье. Мы свяжем эти ДПФ с дискретизацией непрерывного
преобразования Фурье и выведем также общее семейство алгоритмов быстрого преобразования
Фурье, которое включает алгоритмы разбиения на строки и столбцы и разбиения по
векторному основанию как частные случаи.
2.4.1. ДПФ для общего случая периодической дискретизации сигналов
Рассмотрим периодическую
последовательность
с
матрицей периодичности
. Для такой последовательности
(2.89)
для
любого целочисленного вектора
. Обозначим через
область плоскости
, содержащую в
точности один период этой последовательности. Будем называть эту область
основным периодом последовательности. Она содержит
отсчетов
(
является обобщением
, упоминавшимся ранее).
По аналогии с прямоугольным
случаем выскажем гипотезу, что
можно единственным образом представить в
виде конечной суммы комплексных синусоид с кратными периодами
, (2.90)
где
-
целочисленный вектор, a
- область конечной протяженности в
-области. Поскольку
последовательность
периодична,
то
(2.91)
Так
как правые части (2.90) и (2.91) должны равняться при всех значениях
и
, необходимо, чтобы
(2.92)
для
всех целочисленных векторов
и
. Из этого следует, что для нетривиальных
значений
и
или
.
Если
сделать подстановку для
и положить
, можно прийти к следующему
выражению:
. (2.94)
Поскольку
комплексные экспоненты в этой сумме периодичны как по
(матрица периодичности
), так и по
(матрица
периодичности
),
видно, что самое большее
из отсчетов
могут быть независимыми. Таким
образом, область
,
так же как и
,
будет содержать только
отсчетов. Если
определяется как
, (2.95)
то
можно констатировать существование разложения в ряд Фурье для любой
периодической последовательности. Легко проверить, что выражения (2.94) и
(2.95) идентичны. Нетрудно также установить единственность (2.95) благодаря
ортогональности комплексных экспонент
в области
. Заметим также, что
периодична с матрицей
периодичности
. (2.96)
Если
является последовательностью
ограниченной протяженности с опорной областью, ограниченной
, можно применить следующие
соотношения для рядов Фурье для определения дискретного преобразования Фурье:
, (2.97)
. (2.98)
Эти
соотношения подобны выражениям (2.20) и (2.21). Единственная разница состоит в
том, что матрица
не
обязательно должна быть диагональной.
Напомним, что
- матрица периодичности в
пространственной области. Она связывает последовательность конечной
протяженности с ее периодическим продолжением. Периодическое продолжение
- не единственное;
любая последовательность конечной протяженности может иметь несколько
периодических продолжений, из которых ее можно восстановить. Рассмотрим,
например, сигнал с
-точечной
опорной областью на прямоугольном растре, показанной на рис. 2.10, а. Его можно
периодически продолжить в прямоугольной системе координат (рис. 2.10, б) с
помощью матрицы периодичности
(2.99)
или
в гексагональной системе координат (рис. 2.10, в) с помощью матрицы
, (2.100)
предполагая,
что
делится
на 2 [6]. Читатель может найти и другие способы периодического продолжения.
Рис. 2.10. Последовательность
конечной протяженности с прямоугольной дискретизацией и два периодических
дополнения этой последовательности.
Каждая матрица
приводит к различным
периодическим продолжениям и тем самым к различным ДПФ. Насколько они подобны?
Все они - преобразования одной и той же последовательности, и, следовательно,
все соответствуют отсчетам интегрального преобразования Фурье этой
последовательности. Чем они отличаются? Они отличаются способом, которым
берутся отсчеты преобразования Фурье. Сравнивая (2.97) с (1.133а), которое
определяет преобразование Фурье
, можно увидеть, что
. (2.101)
Матрица
- матрица
дискретизации в пространстве преобразования Фурье.
При выводе теоремы отсчетов в гл.
1 мы определили две матрицы
и
, связанные соотношением
. Матрица
являлась матрицей
дискретизации, показывающей, где должны быть взяты отсчеты аналогового сигнала
с ограниченным частотным спектром, а матрица
показывала, каким образом Фурье-преобразование
исходного сигнала периодически дополняется для получения преобразования Фурье
сигнала после дискретизации. Одна из интерпретаций ДПФ состоит в том, что оно
представляет собой результат дискретизации Фурье-преобразования. Матрица,
определяющая отсчет спектра
, является, таким образом, аналогом
матрицы
, за
исключением того, что частотные и пространственные области обращены. Точно так
же матрица
,
удовлетворяющая условию
, аналогична матрице
. Она показывает, как следует
периодически продолжить (или наложить) последовательность в другой области, в
данном случае в пространственной области.
Если
- непрерывный сигнал с
ограниченным спектром, имеющий непрерывное Фурье-преобразование
, то дискретный сигнал
может быть
образован дискретизацией
с использованием матрицы
. Как было показано в
гл. 1, если
,
то (2.102)
. (2.103)
[Допущение,
что сигнал
имеет
ограниченный спектр, снимает проблему наложения.] Используя равенство (2.101),
получим
. (2.104)
ДПФ
соответствует,
таким образом, сведенным к определенному масштабу отсчетам Фурье-преобразования
исходного непрерывного сигнала по частотам
. Матрицу
можно интерпретировать как матрицу
дискретизации, определяющую, каким образом осуществляется дискретизация
непрерывного Фурье-преобразования
.
В общем случае
и
являются матрицами размера
, где
- размерность
рассматриваемых сигналов. Матрица
должна быть обратимой, а элементы
матрицы
(но
не
) должны
быть целыми числами. С учетом этого обстоятельства все формулы этого раздела
равно справедливы для сигналов любой размерности.