Уравновешенное троичное быстрое преобразование Фурье - введение
На некоторое время приостановлю рассказ про к.п.д солнечных батарей, потому как мне срочно надо написать статью про УТБПФ (см заголовок). Её-то и буду выкладывать сюда по кусочкам. Конструктивная критика приветствуется. Начнем.
УДК 519.6
Уравновешенное троичное быстрое преобразование Фурье
В статье показаны преимущества дискретного преобразования Фурье с симметричным относительно нуля расположением отсчетов и предложен быстрый метод его вычисления для числа отсчетов N=3q, показана его тесная связь с уравновешенной троичной системой счисления. Приведен алгоритм троичной инверсии, выполняющийся за O(N) операций и варианты преобразования Фурье для случая действительных входных данных. Рассмотрен вариант алгоритма в базисе Эйзенштейна и проведена оценка эффективности. Приводятся области применения уравновешенного троичного БПФ.
Balanced Ternary Fast Fourier Transform
Features of discrete Fourier transform with symmetrical location of data points on coordinate plane are shown. Fast method of evaluating such a transform is implemented and its connection with balanced ternary radix is explained. Balanced ternary inversion algorithm is introduced requiring O(N) operations and practical realization of Balanced Ternary FFT are given, including real-data forward and inverse FFT. Eisenstein basis was examined as a tool for improving efficiency and operations counts are given. Applications of Balanced Ternary FFT are shown.
Введение
Все существующие алгоритмы быстрого преобразования Фурье, по сути, вычисляют выражения
в одномерном случае или
в двумерном, где n,u,v ∈ [0..N-1].
Это удобно в вычислительном плане и привычно в том смысле, что все индексы неотрицательны, однако во множестве практических приложений такая форма записи приводит к трудностям. Наиболее информативной частью спектра является, как правило, окрестность нуля. К примеру, в задаче вычисления дифракции нулю в пространственной области соответствует оптическая ось системы, а нулю в частотной области - направление вдоль оптической оси. Однако, в формулах (1) окрестность нуля распределяется по углам массива.
Известен метод, позволяющий отцентрировать изображение и в пространственной, и в частотной области. Это умножение на (-1)u+v. В задачах дифракции такое умножение нужно проводить дважды, что замедляет работу и усложняет программу. Кроме того, количество отрицательных частот не равно количеству положительных, что требует большой внимательности при проектировании фильтров. Еще большую аккуратность необходимо соблюдать при работе с действительными данными - в этом случае теоретически возможно вдвое сократить как число арифметических операций, так и объем памяти (по сравнению с произвольными комплексными данными), но структура преобразованного сигнала достаточно сложна, как будет подробно показано в разделе 1.
В настоящей статье предложен быстрый метод вычисления преобразования
которое является симметричным относительно нуля: число положительных коэффициентов равно числу отрицательных. Назовем такие преобразования уравновешенными.
В разделе 1 ( часть 1, часть 2) показано, что такое преобразование представляет практический интерес, позволяя существенно упростить работу, особенно при работе с действительными данными и в двумерном случае.
В разделе 2 выводится алгоритм уравновешенного троичного БПФ с прореживанием по времени с базисом 3, показывается взаимосвязь с уравновешенной троичной системой счисления, что обосновывает название алгоритма.
Раздел 3 ( часть 1, часть 2, часть 3) посвящен практической реализации одномерного УТ БПФ: рассмотрен быстрый алгоритм троичной инверсии и пути уменьшения числа арифметических операций, в том числе переход к базису Эйзенштейна и использование быстрого комплексного умножения.
В разделе 4 рассмотрена реализация прямого и обратного преобразования для действительных входных данных. Показано, что число арифметических операций уменьшается ровно вдвое, а объем занимаемой памяти - в зависимости от представления - либо ровно вдвое меньше, либо составляет N+1 столбцов из 2N+1 исходных.
Раздел 5 содержит описание двумерного БПФ, как для комплексных чисел, так и для действительных.
В разделе 6 проведена оценка вычислительных затрат. Алгоритм УТ БПФ требует меньше действительных умножений, чем алгоритмы Кули-Тьюки и со смешанным базисом, но существенно больше, чем алгоритм Винограда. Полное же число арифметических операций выше, чем у двоичного алгоритма примерно на 10%. Учитывая дополнительные расходы на циклическую перестановку в двоичных алгоритмах, в реальных приложениях предложенный алгоритм может оказаться наиболее производительным.
Наконец, в разделе 7 рассказано об опыте практического применения алгоритма в задачах расчета дифракции и очерчен круг прикладных задач, где описанный алгоритм рекомендуется к использованию.
Продолжение - завтра, в это же время.
УДК 519.6
Уравновешенное троичное быстрое преобразование Фурье
В статье показаны преимущества дискретного преобразования Фурье с симметричным относительно нуля расположением отсчетов и предложен быстрый метод его вычисления для числа отсчетов N=3q, показана его тесная связь с уравновешенной троичной системой счисления. Приведен алгоритм троичной инверсии, выполняющийся за O(N) операций и варианты преобразования Фурье для случая действительных входных данных. Рассмотрен вариант алгоритма в базисе Эйзенштейна и проведена оценка эффективности. Приводятся области применения уравновешенного троичного БПФ.
Balanced Ternary Fast Fourier Transform
Features of discrete Fourier transform with symmetrical location of data points on coordinate plane are shown. Fast method of evaluating such a transform is implemented and its connection with balanced ternary radix is explained. Balanced ternary inversion algorithm is introduced requiring O(N) operations and practical realization of Balanced Ternary FFT are given, including real-data forward and inverse FFT. Eisenstein basis was examined as a tool for improving efficiency and operations counts are given. Applications of Balanced Ternary FFT are shown.
Введение
Все существующие алгоритмы быстрого преобразования Фурье, по сути, вычисляют выражения
в одномерном случае или
в двумерном, где n,u,v ∈ [0..N-1].
Это удобно в вычислительном плане и привычно в том смысле, что все индексы неотрицательны, однако во множестве практических приложений такая форма записи приводит к трудностям. Наиболее информативной частью спектра является, как правило, окрестность нуля. К примеру, в задаче вычисления дифракции нулю в пространственной области соответствует оптическая ось системы, а нулю в частотной области - направление вдоль оптической оси. Однако, в формулах (1) окрестность нуля распределяется по углам массива.
Известен метод, позволяющий отцентрировать изображение и в пространственной, и в частотной области. Это умножение на (-1)u+v. В задачах дифракции такое умножение нужно проводить дважды, что замедляет работу и усложняет программу. Кроме того, количество отрицательных частот не равно количеству положительных, что требует большой внимательности при проектировании фильтров. Еще большую аккуратность необходимо соблюдать при работе с действительными данными - в этом случае теоретически возможно вдвое сократить как число арифметических операций, так и объем памяти (по сравнению с произвольными комплексными данными), но структура преобразованного сигнала достаточно сложна, как будет подробно показано в разделе 1.
В настоящей статье предложен быстрый метод вычисления преобразования
которое является симметричным относительно нуля: число положительных коэффициентов равно числу отрицательных. Назовем такие преобразования уравновешенными.
В разделе 1 ( часть 1, часть 2) показано, что такое преобразование представляет практический интерес, позволяя существенно упростить работу, особенно при работе с действительными данными и в двумерном случае.
В разделе 2 выводится алгоритм уравновешенного троичного БПФ с прореживанием по времени с базисом 3, показывается взаимосвязь с уравновешенной троичной системой счисления, что обосновывает название алгоритма.
Раздел 3 ( часть 1, часть 2, часть 3) посвящен практической реализации одномерного УТ БПФ: рассмотрен быстрый алгоритм троичной инверсии и пути уменьшения числа арифметических операций, в том числе переход к базису Эйзенштейна и использование быстрого комплексного умножения.
В разделе 4 рассмотрена реализация прямого и обратного преобразования для действительных входных данных. Показано, что число арифметических операций уменьшается ровно вдвое, а объем занимаемой памяти - в зависимости от представления - либо ровно вдвое меньше, либо составляет N+1 столбцов из 2N+1 исходных.
Раздел 5 содержит описание двумерного БПФ, как для комплексных чисел, так и для действительных.
В разделе 6 проведена оценка вычислительных затрат. Алгоритм УТ БПФ требует меньше действительных умножений, чем алгоритмы Кули-Тьюки и со смешанным базисом, но существенно больше, чем алгоритм Винограда. Полное же число арифметических операций выше, чем у двоичного алгоритма примерно на 10%. Учитывая дополнительные расходы на циклическую перестановку в двоичных алгоритмах, в реальных приложениях предложенный алгоритм может оказаться наиболее производительным.
Наконец, в разделе 7 рассказано об опыте практического применения алгоритма в задачах расчета дифракции и очерчен круг прикладных задач, где описанный алгоритм рекомендуется к использованию.
Продолжение - завтра, в это же время.