1.4.5. Методы быстрого вычисления круговой свертки
Существуют три основных метода быстрого вычисления круговой свертки. Методы различаются требуемым объемом вычислительных операций и памяти, а также степенью точности, связанной с ошибками округления.
Первый метод, основанный на использовании БПФ и получивший название метода быстрой свертки, приводит к существенному сокращению требуемого количества арифметических операций для последовательностей, длина которых больше 32. Недостатки метода — значительные ошибки округления, большой объем памяти, требуемый для хранения комплексных экспоненциальных коэффициентов, и все еще значительный объем вычислений.
Второй метод, использующий теоретико-числовые преобразования
является точным, так как служит для преобразования последовательностей в кольце целых чисел. Существенный недостаток, ограничивающий его применение в
реальных системах, — зависимость между длиной последовательности
и требуемой длиной кодового слова, что приводит к длинным кодовым словам для больших
Третий метод — метод модульной арифметики в кольце полиномов, обеспечивающий высокие эффективность и точность вычислений. Недостаток этого метода заключается в сложности программирования вычислений, которая зависит
длины обрабатываемой последовательности.
Рис. 1.15 (см. скан)