Пред.
След.
Макеты страниц
Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO
4. МЕТОДЫ ФАКТОРИЗАЦИИ БАЗОВЫХ МОДУЛЕЙ ДПФВ предыдущей главе было отмечено, что гдна из причин, определяющая большое многообразие алгоритмов БПФ, вызвана конкретными способами вычисления базовых модулей
4.1. Вычисление ДПФ через циклическую сверхуДля случая, когда
Рейдер показал, что матрица
где
Приведем пример построения матрицы 3 и 5. Пусть в
Таким образом, для Итак, если Вопросам вычисления циклических сверток уделено большое число публикации, например
где Выражение (4.3) може быть переписано в несколько другой эквивалентной форме.
где Для построения 1. Процедура синтеза на основе интерполяционной формулы Лагранжа (алгоритм Тоома Кука) [2]. Представим циклическую свертку в полиномиальной форме
где Полином интерполяционной формулы Лагранжа
Тоща мы приходим к форме
отсюда 2. Сокращения по модулям неприводимых полиномов. Полином
где степень каждого полинома
определяет матрицы
определяют матрицу
где Очевидно, что к (4.9) может быть ггоименен алгоритм Тоома Кука (4,6) с нижней границей числа умножений
Обычно матрицы
Из
Такое представление может быть полезно, когда последовательность
Для вычисления базовых модулей
где В общем случае коэффициенты матриц
Аналогично
Так как
т.е. при таком сокращении имеем в матрице В [9, 10] предложена модификация представления (4.15), позволяющая уменьшить число сложений. Предложенный вариант канонического представления авторы назвали вертикально-гнездовым алгоритмом Затем вьшолняется следующее сокращение по двум полиномам
где Тогда
Аналогичный подход может быть применен к факторизации матрицы
где Например, при
Для вычисления базовых ДПФ
Для решения (4.19) применен вычислительный подход поиска элементов
Такой подход позволил найти оптимальные алгоритмы Таблица 4.1 (см. скан)
|
1 |
Оглавление
|