Использование БПФ

Даже при наличии мощного процессора непосредственный подсчет всех нужных значений является трудоемкой задачей. Для уменьшения числа умножений используется следующий подход. Образец заменяется последовательностью длины . Из входной последовательности образуют последовательности длины , . После этого подсчитывается циклическая свертка

Для отыскания значений свертки используется БПФ. Для этого число должно обладать соответствующими арифметическими свойствами. Покажем теперь, как по найденным значениям подсчитываются значения . Это проще всего продемонстрировать на примере . Имеем

,

. Точно также,

. Теперь мы можем найти значения