Структура матрицы найдена мной, как автором, эмпирическим путем, который заключался в том, что анализировались свойства перестановочных матриц и и выявлении свойства
Такая структура матрицы легко объясняется. Попозже распишу.
Алгоритмы Винограда малоточечных ДПФ
Re: Алгоритмы Винограда малоточечных ДПФ
Собственно, так выглядит дпф в случае преобразования индексов по райдеру.
Входная перестановка может быть представлена как результат левого умножения вектора x (без отсчета с индексом 0) на матрицу , которая получается из единичной матрицы размера (M-1)x(M-1) путем перестановки ее строк согласно
где
Выходная перестановка может быть представлена как результат правого умножения вектора X (без отсчета с индексом 0) на матрицу , которая получается из единичной матрицы размера (M-1)x(M-1) путем перестановки ее столбцов согласно
где
Здесь g - примитивный элемент. - мультипиликативный обратный к
Мультипликативные обратные вычисляются на основании той же мт ферма:
или где
Не трудно заметить, что если последовательность есть , то последовательность будет
Короче говоря, матрица получается путем транспонирования матрицы и перестановки ее столбцов исключая первый в обратном порядке. Ну и произведением будет матрица с 1 на позиции 1,1 и на побочной диагонали минора c 0 в остальных позициях.
Как-то так.
Входная перестановка может быть представлена как результат левого умножения вектора x (без отсчета с индексом 0) на матрицу , которая получается из единичной матрицы размера (M-1)x(M-1) путем перестановки ее строк согласно
где
Выходная перестановка может быть представлена как результат правого умножения вектора X (без отсчета с индексом 0) на матрицу , которая получается из единичной матрицы размера (M-1)x(M-1) путем перестановки ее столбцов согласно
где
Здесь g - примитивный элемент. - мультипиликативный обратный к
Мультипликативные обратные вычисляются на основании той же мт ферма:
или где
Не трудно заметить, что если последовательность есть , то последовательность будет
Короче говоря, матрица получается путем транспонирования матрицы и перестановки ее столбцов исключая первый в обратном порядке. Ну и произведением будет матрица с 1 на позиции 1,1 и на побочной диагонали минора c 0 в остальных позициях.
Как-то так.