1.4.5. Методы быстрого вычисления круговой свертки

Существуют три основных метода быстрого вычисления круговой свертки. Методы различаются требуемым объемом вычислительных операций и памяти, а также степенью точности, связанной с ошибками округления.

Первый метод, основанный на использовании БПФ и получивший название метода быстрой свертки, приводит к существенному сокращению требуемого количества арифметических операций для последовательностей, длина которых больше 32. Недостатки метода — значительные ошибки округления, большой объем памяти, требуемый для хранения комплексных экспоненциальных коэффициентов, и все еще значительный объем вычислений.

Второй метод, использующий теоретико-числовые преобразования является точным, так как служит для преобразования последовательностей в кольце целых чисел. Существенный недостаток, ограничивающий его применение в

реальных системах, — зависимость между длиной последовательности и требуемой длиной кодового слова, что приводит к длинным кодовым словам для больших

Третий метод — метод модульной арифметики в кольце полиномов, обеспечивающий высокие эффективность и точность вычислений. Недостаток этого метода заключается в сложности программирования вычислений, которая зависит длины обрабатываемой последовательности.

Рис. 1.15 (см. скан)