5.4. Соотношение между прореживанием по времени и прореживанием по частоте

В § 5.3 прореживание по времени и прореживание по частоте трактовались как независимые, хотя и очень по­хожие, алгоритмы. Эта точка зрения полезна для про­граммиста или разработчика машины. Однако можно лучше понять природу алгоритма быстрого преобразова­ния Фурье, применив другую точку зрения, представлен­ную в этом параграфе. Следуя этой точке зрения обычно нельзя получить дополнительную экономию объема вы­числительных операций, но можно установить взаимо­связь двух форм, алгоритма и предложить в некоторых специальных случаях третью форму.

Прежде подразумевалось, что входной и выходной сигналы при ДПФ есть одномерные последовательности. Предположим, что множителями N являются числа p и q. Можно записать входную последовательность в виде двумерной p×q таблицы, например:

		…
	…	…
…	…	…	…
	…	…

где элементом общего вида будет . Индекс l — это номер элемента внутри строки, а индекс i — внутри столбца. Теперь рассмотрим прореживание по частоте. Перепишем равенства (5.56), подставив q вместо N/р.

Тогда получим

(5.57)

Если в первом выражении (5.57) вынести за знак суммы, то примет вид r-й точки ДПФ от l-го столб­ца таблицы 1. Это есть p-точечное ДПФ, переводящее временной индекс i в частотный индекс r:

(5.58)

В выражении (5.58) предусматривается проведение q отдельных ДПФ из p; точек каждое. Расположим резуль­таты в виде другой таблицы:

		…
	…	…	…
…	…	…	…
	…	…

Второе равенство (5.57) предполагает вычисление q-то­чечного ДПФ каждой из p строк таблицы 2:

(5.59)

Теперь можно записать в виде следующей таб­лицы:

		…
	…	…	…
…	…	…	…
	…	…

где второе ДПФ перевело индекс l в индекс k.

Таким образом, в основе выражения (5.59) лежит де­ление входной последовательности на несколько последо­вательностей, которые располагаются как строки табли­цы. После этого вычисляется ДПФ каждого столбца этой таблицы, для того чтобы образовать столбцы второй таб­лицы, причем элемент r-й строки и l-го столбца умножа­ется на W ^rl. Наконец, каждая строка этой таблицы пре­образуется так, чтобы образовать строки последней таб­лицы. Столбцы заключительной таблицы, будучи прочте­ны один за другим, образуют N-точечное ДПФ. Этот про­цесс проиллюстрирован на рис. 5.21 для случая p=5, q=3 и 15-точечного ДПФ.

Теперь рассмотрим прореживание по времени, описы­ваемое как

(5.60)

Если изменить взаимно смысл p и q и поменять местами r и k, i и l, то получим

(5.61)

Уравнение (5.61) преобразует в подобно то­му, как это делалось в (5.57), однако процессы, выра­жаемые этими соотношениями, существенно различаются. Правое уравнение (5.61) соответствует такой структуре табл. 1, при которой столбцами являются . Однако есть ДПФ от . Поэтому первым шагом является формирование некоторой таблицы, столбцы которой являются дискретными преобразованиями Фурье от столбцов табл. 1.

Рис. 5.21. Быстрое преобразование Фурье, изображенное как операция над двумерной таблицей

Левое уравнение (5.52) предусматривает два шага: умножение таблицы на и вычисление ДПФ от каждой из строк. Заметим при этом, что (5.59) описывает прореживание по времени в такой же мере, как и проре­живание по частоте.

Аналогично этому рис. 5.21 иллюстрирует в равной степени оба алгоритма. Единственное различие между этими двумя алгоритмами состоит в том, что множители входят во вторую совокупность ДПФ для прорежива­ния по времени и в первую совокупность ДПФ для проре­живания по частоте. Включение множителей в ту или другую совокупность ДПФ означает, что требуется мень­ше вычислений при прореживании по времени или по ча­стоте по сравнению с прямыми вычислениями ДПФ. Тем не менее рис. 5.21 позволяет лучше оценить соотношение между двумя методами быстрого преобразования Фурье. Множители могут быть названы «поворачи­вающими» множителями (twiddle factors) .

В некоторых специальных случаях «поворачивающие» множители могут быть исключены с помощью хитрых пе­рестановок во входной и выходной последовательностях. Эти перестановки основаны на теореме кругового смещения и на других теоретических положениях. Пред­положим, что в табл. 1 каждый столбец подвергается круговому смещению различным образом, причем l-й столбец смещается по кругу на a×l позиций, где а под­лежит определению.

Выходные значения первой совокуп­ности ДПФ на рис. 5.21 будут теми же, что и ранее, изме­нятся только показатели степени у множителей [см. (5.59)], т. е.

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

(5.62)

Если p и q имеют общие множители, (5.62) не может быть решено для любых целых чисел a, b. Однако если p и q являются взаимно простыми числами, то можно найти целые а, b, которые удовлетворяют (5.62), т, е. определяют такие круговые смещения входной и выходной последовательностей, которые позволяют обходиться без «поворачивающих» множителей. Этот алгоритм иног­да применяется в том случае, когда число точек преобра­зования является степенью 10 и когда могут быть эффек­тивно объединены простые алгоритмы для чисел точек в виде степени 2 и степени 5.

Подводя итоги, отметим, что существуют различные методы уменьшения количества вычислений, требуемых для N-точечного дискретного преобразования Фурье. Двумя основными методами являются: прореживание по времени, когда вычисляются преобразования более ко­ротких последовательностей, составленных из каждого r-го отсчета, и затем эти преобразования объединяются в одно большое преобразование; и прореживание по частоте, при котором короткие куски последовательности комбинируются r способами, чтобы сформировать r ко­ротких последовательностей, у которых отдельные преоб­разования, взятые вместе, образуют полное преобразова­ние. Если N имеет более чем два множителя, вычисление преобразований, которое требуется осуществить после прореживания, может быть еще более упрощено по­средством новых прореживаний по времени или по ча­стоте.

Если последовательность входных точек для осущест­вления преобразования подвергается круговому смеще­нию, то выходные точки умножаются только на опреде­ленные степени W. Если же входные точки для осуществления преобразования умножаются на опреде­ленные степени W, то последовательность выходных то­чек только смещается по кругу. Эти обстоятельства допускают существование и других вариантов основных алгоритмов быстрого преобразования Фурье. Полученные в результате направленные графы могут видоизменяться различным образом для упрощения или, по крайней ме­ре, прояснения задач, связанных с программированием вычислительной машины для вычисления быстрых преоб­разований Фурье.

Поскольку обратное дискретное преобразование Фурье описывается уравнением, совершенно идентичным уравнению (5.2), любой метод вычисления ДПФ может быть легко модифицирован для вычисления обратного ДПФ. Особенность состоит лишь в том, что W заменяет­ся на W* (сопряженное W), а результат вычислений - умножается на 1/N.