9.5. Алгоритмы БПХ для взаимно-простых множителей

В разд. 3.6 была получена общая форма факторизации через кронекеровское произведение матриц ДПХ небольших размерностей . в случае, когда взаимно-простые сомножители А, т.е.

В разд. 4.4 бьшо показано, что базовые модули . могут быть факторизованы двумя способами:

1. Каноническим

или

где и определяются из соответствующих канонических разложений модулей например:

2. Через циркулянтные матрицы

Применяя к (9.32) теорему факторизации из разд. 1.1 и подставляя вместо или (9.34), получаем два варианта алгоритма простых множителей:

Для ДПХ возможна также организация вычислений типа гнездового алгоритма (типа Винограда-Фурье), что позволяет значительно уменьшить число умножений

где

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