Преобразование для последовательностей с основанием 4 и другие модификации

С чисто иллюстративной целью рассмотрение было ограничено последовательностями длины N, где другими словами, N — это число 2, возведенное в степень Р:

Однако возникает вопрос: какова специфика ситуации и что следует делать, когда последовательность состоит из 300 элементов? Возможно, следует исключить 44 элемента, чтобы уменьшить их общее число до 256. Можно также дополнить исходную последовательность 212 нулями, тогда число элементов результирующей последовательности окажется равным 512. Ясно, что на практике нецелесообразно оценивать время, затрачиваемое на реализацию процедур над искусственно удлиненными последовательностями; в результате обычно используются средства, реализующие удлинение исходных последовательностей дополнительными элементами и согласующиеся с операцией вида ; вычисления и отображения цифровых изображепий рассчитаны на формат либо на формат вида

Однако выбор некоторых средств не находится в наших руках; например, число строк телевизионного изображения колеблется между 512 и 1024, а в ряде случаев составляет всего 525. Вне нашего контроля находятся также временные ряды, возникающие в геофизических исследованиях, астрономические данные и другая информация естественного происхождения. Последовательность чисел солнечных пятен содержала в 1985 г. 286 членов, поскольку регистрация числа пятен началась в 1700 г., очень немного информации можно извлечь относительно N, и остается только ждать дальнейших результатов.

Если вернуться к обоснованию доводов в пользу выбора закона вида , то вспомним, что этот выбор был обусловлен принципом «разделяй и властвуй», посредством которого поэтапно уменьшалась длина последовательности, пока не осталось два элемента. В результате мы имели тривиальные двухэлементные преобразования, для которых затем выполнялась процедура их объединения, т.е. получения комбинированного преобразования. Ясно, что простейшим является также трехэлементное преобразование

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

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

где последовательно расположенные основания представляют собой ряд простых чисел, был усовершенствован С. Виноградом. Соответствующий материал рассматривается в литературе [С. S. Burrus, Т. W. Parks. DFT/FFT Convolution Algorithms, Wiley Interscience, 1985.-(Алгоритмы свертки для ДПФ/БПФ)]. Этими авторами рассмотрены алгоритмы перестановки для оснований степеней, отличающихся от числа 2.

При использовании этих алгоритмов на практике, когда возникают затруднения в представлении числа N, его часто все-таки можно представить в наиболее удобной и эффективной с точки зрения скорости реализации алгоритмов форме. Если мы потребуем представления N в виде что представляет собой четную величину, принадлежащую к более узкому классу, нежели класс четных значений вида то при этом будут использованы преимущества в скорости реализации алгоритма. Для 4-элементного ДПХ коэффициенты передачи (весовые коэффициенты усиления) равны 1 или

Рис. 8.8. Диаграмма в форме бабочки для 3-элементного ДПХ. Сплошные линии представляют коэффициент передачи, равный 1/3; штриховые линии используются для обозначения коэффициента передачи а остальные линии - для обозначения коэффициентов передачи

— 1, что не влечет за собой операций умножения: аналогичное упрощение характерно и для диаграммы в форме бабочки при При этом уменьшение длины исходной последовательности прекращается при получении 4-элементных подпоследовательностей, в результате чего существенно сокращается общее число операций умножения, для типового случая приблизительно на одну треть. Следовательно, преобразование для основания степени 4 дает заметные преимущества. Программа вычислений представлена в приложении 1.