11.2.6. ПРЕОБРАЗОВАНИЕ ВИНОГРАДА

Способы дискретного преобразования Фурье постоянно обновляются. Большинство модификаций БПФ подстроено под решение специальных задач или аппаратурную реализацию. Особого упоминания заслуживает разработанный Виноградом (см. работу [11.7]) новый метод, основанный на совершенно ином подходе. По сути дела, он заключается в преобразовании одномерной последовательности в многомерный массив, каждая компонента которого совпадает с одним из значений исходной последовательности. Затем этот массив подвергается преобразованию Фурье и вновь преобразуется в одномерную последовательность как функция частоты. Преобразование последовательности в массив осуществляется на основе представлений, заимствованных из теории чисел с использованием так

Рис. 11.3. (см. скан) Пример поведения коэффициентов Фурье, вычисленных методом БПФ при а — вычисленные значения коэффициентов; б - транспонированные значения, задающие двусторонний спектр.

называемой китайской теоремы об остатках. Теория и реализация преобразования Фурье методом Винограда существенно сложнее, чем в случае использования БПФ, описанного в разд. 11.2.2. Кроме того, процесс преобразования последовательности в массив требует расширения объема памяти, в которой хранятся данные, и получить преобразованный ряд на месте исходного

в рамках этого алгоритма невозможно. Несмотря на эти недостатки, алгоритм Винограда приобретает все большую популярность, поскольку он, во-первых, позволяет существенно сократить расход машинного времени и, во-вторых, легко обобщается на алгоритмы с основанием более 2 и на алгоритмы со смешанным основанием. Более подробно о методе Винограда см. в работе [11.7].