Алгоритм Винограда вычисления БПФ расписан везде (например, на http://www.sibsutis.ru/~mavr/LIB/books.htm несколько книг: Нуссбаумер, Блейхут и др.), однако таким языком изложения, что требуется дополнительная консультация.
1. Везде пишут о тривиальных умножениях на +-1 и +-j. Как это понимать?
Например, Нуссбаумер (стр. 135 электронной книги) приводит формулы расчёта:
m0=1*(t7+t8)
m6=j*(x6-x2)
Это умножение приводится для указания на то, что результат в m0 - чисто действительный, а в m6 - чисто мнимый? Или как?
2. Во всех книгах (по крайней мере, в перечисленных) приводится список формул исходя з того, что входная последовательность х - массив чисто действительных чисел. Если же х - массив комплексных чисел? На сколько я понял, нужно провести расчёт двух БПФ отдельно: для массивов Re[x] и Im[x], а затем их объединить по соответствующим формулам. Вопрос: при расчёте m0 и m6 для массива Im[x] с точки зрения результирующего БПФ для комплексного массива х результат в m0 - станет чисто мнимым, а в m6 - чисто действительным?

ПФ - комплексное преобразование. Все числа на входе и выходе, как и промежуточные результаты - комплексные. Нужно посмотреть, нет ли в конкретной реализации алгоритма оптимизации, рассчитанной на то, что мнимая часть входа равна нулю. Если нет - нужно использовать алгоритм непосредственно для комплексного входа. Если есть - нужно эту оптимизацию выкинуть.

Умножение на 1 - это просто копирование.
Умножение на j - это перестановка действительной и мномой части и инверсия мнимой части.
Такие операции не требуют умножений или сложений, и поэтому считаются тривиальными.

За вторую часть ответа - спасибо.

По первой части ответа:
Но, судя по тексту (стр. 79 Нуссбаумера), это несколько не так (см. приложенный файл)...

Не увидел в тексте никаких противоречий написанному мною. Действительные числа являются подмножеством комплексных. Поэтому можно рассматривать сужение комплексного преобразования на последовательности действительных чисел. Это сужение будет обладать определенной симметрией, которую можно использовать для оптимизации реализации алгоритма.

Спасибо.

А как быть, когда N=12, например?

1. Я понял, что N=N1*N2=3*4. Но что такое (N2,N1)=1 - для меня остаётся загадкой...

2. Будет ли справедлив такой метод расчёта результирующего 12-точечного БПФ y от входного массива x:
2.1. Вычисляем черыре 3-точечных БПФ (для разных x[i])
%******* 4 x ModFFT3 ****************
y[1 5 9 ] =БПФ3(x[ 1 5 9]);
y[4 8 12]=БПФ3(x[ 4 8 12]);
y[7 11 3]=БПФ3(x[ 7 11 3]);
y[10 2 6]=БПФ3(x[10 2 6]);
2.2. Вычисляем три 4-точечных БПФ (для разных y[i])
y([1 4 7 10])=fft4(y[1 4 7 10]);
y([5 8 11 2])=fft4(y[5 8 11 2]);
y([9 12 3 6])=fft4(y[9 12 3 6]);?
Или нужны дополнительно ещё какие-то операции?