Radix-4 FFT против Radix-2

Является ли реализация radix-4 быстрее, чем эквивалентно хорошо закодированное FFT radix-2? И если да, то почему это будет быстрее?

Это зависит. Теоретически вы можете сохранить несколько умножений с помощью radix-4, так как radix-4 имеет 1/4 числа бабочек и 3 mpy + 8 добавок на бабочку (если правильно структурировано), а radix 2 имеет 1 mpy + 2 добавления на бабочку ,

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

Таким образом, это только преимущество, если количество mpy является ограничивающим фактором, который для большинства аппаратных средств в наши дни не так.

сюда ! Вы можете найти объяснение основных различий между двумя алгоритмами для БПФ. В конце документа есть несколько таблиц, в которых можно отметить, что, если размер данных увеличивается, производительность radix-4 fft лучше, чем radix-2.

$\frac{\pi}{2}$$\sin(\cdot)$$\cos(\cdot)$

чистое число умножений и сложений, я думаю, одинаково, но бабочка radix-4 может быть все сделана в банке регистров процессора (я думаю, что есть около 16 различных регистров с плавающей запятой, и вам нужно 8 для реальной и воображаемой частей из 4 значений - 2 регистра для синусных и косинусных тиддлов и, возможно, какой-то другой регистр или два для нуля). это быстрее, чем делать это в памяти.

В основании 2 число выборок выражается в единицах мощности 2, но в основании 4 количество выборок принадлежит степени 4.