9.5: Evaluación del PFA y WFTA

Última actualización
Guardar como PDF

Page ID: 86806

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

En cuanto a las FFT's de Cooley-Tukey, la primera evaluación de estos algoritmos será sobre el número de multiplicaciones y adiciones requeridas. El número de multiplicaciones para calcular el PFA en la ecuación viene dado por Mapeo de Índice Multidimensional. Usando la notación que$T(N)$ es el número de multiplicaciones o adiciones necesarias para calcular una DFT Longitud-N, el número total para un PFA de cuatro factores de Longitud-N, donde $N=N1N2N3N4N=N1N2N3N4“role="presentation” style="position:relative;” tabindex="0"> $N=N_1N_2N_3N_4$$

\[T(N)=N_1N_2N_3T(N_4)+N_2N_3N_4T(N_1)+N_3N_4N_1T(N_2)+N_4N_1N_2T(N_3) \nonumber \]

El recuento de multiplicaciones y adiciones en el Cuadro 9.5.1 siguiente se calculan a partir de (105) con los recuentos de los factores tomados del Algoritmo de Transformada de Fourier de Winograd (WFTA) Cuadro 6.2.1. La lista de longitudes son las posibles con módulos en el programa de longitud 2, 3, 4, 5, 7, 8, 9 y 16 como es cierto para el PFA y el WFTA. Se puede usar un máximo de cuatro longitudes relativamente primos de este grupo dando 59 longitudes diferentes en el rango de 2 a 5040. La FFT radix-2 o split-radix permite 12 longitudes diferentes en el mismo rango. Si se agregan módulos de longitud 11 y 13 de, la longitud máxima se convierte en 720720 y el número de longitudes diferentes se convierte en 239. Agregar módulos para 17, 19 y 25 da una longitud máxima de 1163962800 y un número muy grande y denso de longitudes posibles. La longitud del código para los módulos más largos se vuelve excesiva y no debe incluirse a menos que sea necesario.

El número de multiplicaciones necesarias para el WFTA es simplemente producto de las necesarias para los módulos requeridos, incluidas las multiplicaciones por unidad. El número total puede contener algunos multiplicadores de unidad pero es difícil eliminarlos en un programa práctico. El Cuadro 9.5.1 contiene tanto el número total (MULTS) como el número con los multiplicados de unidad eliminados (RMULTS).

Calcular el número de adiciones para el WFTA es más complicado que para el PFA debido a la expansión de los datos que se mueven a través del algoritmo. Por ejemplo, el número de adiciones, TA, para el ejemplo longitud-15 en la Fig. 9.3.1 viene dado por

\[TA(N)=N_2TA(N_1)+TM_1TA(N_2) \nonumber \]

donde$N_1=3,\; N_2=5,\; TM_1=$ el número de multiplica para el módulo longitud-3 y por lo tanto el factor de expansión. Como se mencionó anteriormente existe un orden óptimo para minimizar las adiciones. El orden utilizado para calcular en la Tabla 9.5.1 es óptimo en la mayoría de los casos y cercano al óptimo en los demás.

Cuadro 9.5.1: Número de multiplicaciones reales y adiciones para FFT complejos de PFA y WFTA
Largo	PFA	PFA	WFTA	WFTA	WFTA
N	Mults	Agrega	Mults	RMults	Agrega
10	20	88	24	20	88
12	16	96	24	16	96
14	32	172	36	32	172
15	50	162	36	34	162
18	40	204	44	40	208
20	40	216	48	40	216
21	76	300	54	52	300
24	44	252	48	36	252
28	64	400	72	64	400
30	100	384	72	68	384
35	150	598	108	106	666
36	80	480	88	80	488
40	100	532	96	84	532
42	152	684	108	104	684
45	190	726	132	130	804
48	124	636	108	92	660
56	156	940	144	132	940
60	200	888	144	136	888
63	284	1236	198	196	1394
70	300	1336	216	212	1472
72	196	1140	176	164	1156
80	260	1284	216	200	1352
84	304	1536	216	208	1536
90	380	1632	264	260	1788
105	590	2214	324	322	2418
112	396	2188	324	308	2332
120	460	2076	288	276	2076
126	568	2724	396	392	3040
140	600	2952	432	424	3224
144	500	2676	396	380	2880
168	692	3492	432	420	3492
180	760	3624	528	520	3936
210	1180	4848	648	644	5256
240	1100	4812	648	632	5136
252	1136	5952	792	784	6584
280	1340	6604	864	852	7148
315	2050	8322	1188	1186	10336
336	1636	7908	972	956	8508
360	1700	8148	1056	1044	8772
420	2360	10536	1296	1288	11352
504	2524	13164	1584	1572	14428
560	3100	14748	1944	1928	17168
630	4100	17904	2376	2372	21932
720	3940	18276	2376	2360	21132
840	5140	23172	2592	2580	24804
1008	5804	29100	3564	3548	34416
1260	8200	38328	4752	4744	46384
1680	11540	50964	5832	5816	59064
2520	17660	82956	9504	9492	99068
5040	39100	179772	21384	21368	232668

Del Cuadro 9.5.1 vemos que en comparación con el PFA o cualquiera de los FFT's de Cooley-Tukey, el WFTA tiene significativamente menos multiplicaciones. Para las longitudes más cortas, el WFTA y el PFA tienen aproximadamente el mismo número de adiciones; sin embargo, para longitudes más largas, el PFA tiene menos y los FFT de Cooley-Tukey siempre tienen los menores. Si se compara la aritmética total, el número de multiplicaciones más el número de adiciones, las FFT, PFA y WFTA de base dividida tienen aproximadamente el mismo recuento. Se han desarrollado versiones especiales del PFA y WFTA para datos reales.

El tamaño del programa Cooley-Tukey es el más pequeño, el PFA siguiente y el WFTA más grande. El PFA requiere el menor número de constantes almacenadas, la FFT Cooley-Tukey o split-radix siguiente, y el WFTA requiere el mayor número. Para una DFT de aproximadamente 1000, el PFA almacena 28 constantes, la FFT 2048 y la WFTA 3564. Tanto el FFT como el PFA se pueden calcular in place y el WFTA no. El PFA se puede calcular en orden sin ununscrambler. La FFT de radix-2 también puede hacerlo, pero requiere sobrecarga de indexación adicional. La sobrecarga de indexación y transferencia de datos es mayor para el WFTA porque las secciones separadas de pretejido y posttejido requieren su indexación y pasan a través de los datos completos. Los módulos más cortos en el PFA y WFTA y las mariposas en las FFT de base 2 y 4 son más eficientes que los más largos porque los cálculos intermedios se pueden mantener en registros de cpu en lugar de memoria general. Sin embargo, los módulos y radices más cortos requieren más pases a través de los datos para una longitud aproximada dada. Una comparación adecuada requerirá que los programas reales sean compilados y ejecutados en una máquina en particular. Hay muchas preguntas abiertas sobre la relación de algoritmos y arquitectura de hardware.

Colaborador

ContribeeBurrus