Алгоритмы Винограда малоточечных ДПФ

thermit
Сообщения: 2
Зарегистрирован: 19 авг 2022, 17:40

Алгоритмы Винограда малоточечных ДПФ

Сообщение thermit »

Структура матрицы найдена мной, как автором, эмпирическим путем, который заключался в том, что анализировались свойства перестановочных матриц и и выявлении свойства

Такая структура матрицы легко объясняется. Попозже распишу.

Гость

Re: Алгоритмы Винограда малоточечных ДПФ

Сообщение Гость »

Собственно, так выглядит дпф в случае преобразования индексов по райдеру.



Входная перестановка может быть представлена как результат левого умножения вектора x (без отсчета с индексом 0) на матрицу , которая получается из единичной матрицы размера (M-1)x(M-1) путем перестановки ее строк согласно
где

Выходная перестановка может быть представлена как результат правого умножения вектора X (без отсчета с индексом 0) на матрицу , которая получается из единичной матрицы размера (M-1)x(M-1) путем перестановки ее столбцов согласно
где
Здесь g - примитивный элемент. - мультипиликативный обратный к
Мультипликативные обратные вычисляются на основании той же мт ферма:

или где

Не трудно заметить, что если последовательность есть , то последовательность будет
Короче говоря, матрица получается путем транспонирования матрицы и перестановки ее столбцов исключая первый в обратном порядке. Ну и произведением будет матрица с 1 на позиции 1,1 и на побочной диагонали минора c 0 в остальных позициях.

Как-то так.

Ответить