9-точечное преобразование Фур] жений, 44 вещественных сложения

lo ~ h

/, /.

tJ + (,

и + h

1 0 I

-1 1 0

0 0 0 -I 0 -1

-1 0 0 -1 0 -I

-I 0 0 -1 0 -1

1 -I I -I

0 0

; 0 0 0

0 ; -J

0 j J

-j 0 0 0

0 j j Q

0 -J -J -J.

= Vt + Ui

7 -

Я = (3 + (4 +

Л, = / - ti

e* = (i - (j

at = tt - г

e, = (4 - a

: -at - a -at + с

9 = 2ж/9 To = -b) - bt

0 = ] = b, -

= \ Ti= -b,~ b,

= - i Гз = ft, - t

= 1 (2 COS 9 - COS 29 - COS Дв) Ti = + + bi = i(cos 9 + COS 29 - 2 COS 49) Ti = T, - 6, = ,4cos9 - 2cos2fl + 13 ) Tt - T4 + b, = sin 39 = sin 39 = - sin 9 = -sin 49 ,0 = - sin 2S

Т.Т,- 7Ь Г, =. Г, + Ti

Т,~ То - т, + т, Тю - йт - П

г - г>7 - 7-,

Т,1 = + г, + Г) Ко =

у, = Т, + jTiol Кг = Ti - JTu V, = Tt + jbb к. = n -f n = г, - jT2 VtTt- jbt И, = Г. + /Т у, = T, - уГю

* тривиальные сложения.

*) Тривиальные сложения.

8-точечное преобразование Фурье; 2 (8) вещественных умножении, 26 вещественных сложений

ье; 10 (И) вещественных умно-

434 Приложение Б. Набор малых БПФ-алгоритмов Винограда

16-точечная циклическая свертка; 10 (18) вещественных умножений, 74 вещественных сложений

Шнложение Б. Набор малых тФ->;гог шсМгр

и = V0 + us

t, = и. + щг

li ~ u2 ию

tj = vi - v,n

Гд = U4 + fl, tj = - 1

/б = fl + vo It = v, - vi = v} + uii li = vi - Ill do = fs + VII li, = vt - v

In = vi + Ul! fl, - ,11 - vn l . / + II 1,1 - <1 + Г16 = (14 + 111 l = (. + II.

r = /6 - /10 /19 = f, + (11 = f, - III (11 = Г I, + In ait = (i + In fl, = /, - (1, 0 = r,i + (. fl, - Гц -flo Itt + Iv fli = Ы - 11 01 Iw - iJ , = .- 1 e, И1 - UI

a, - fl, - Гз ..<!- <i fl, e, + fl,

flio i - 1 flu - i4 -flu = nil - I, flu = fl, + I fll, = (, + /,

4,1, = fll* + fll

e = 2x/16

Bi - COS 29 Bb COS 29 S, = cos 39 Bi = cos 9 + cos 39 Bi = -cos 9 + cos 39 Bi. = 1 Bii . 1 Bi, = 1 Bii - - sin 29 a,4 = -sin 29 Bi, = -sin 39 Bit = - sin 9 + sin 39 B = - sin 9 - sin 39

) Тривиальные сложения.

Г, = + bi Г = 6, - b,

Ti = bu + bij

Ti - 111, - fell Ti b,* b,

T, = bi - b,

n- bi - bi Ti = b, - b,

T, = r, + Г,

r, - Г4 - r. Ti. = r, + r, Г11 . Г, - r, r . (1,1 + 614 Г11 . bi, - bi. Tii b + *i. Г, - bii - bii Та - Ti, f Ti. 7-1, = 2-1. - Ti. Ti, - Tii + Г11 T - T - Га

ki Г, + ;Г.

V,-T,+ JT,

Vi . r - ;Г,

4 = 61+ yfti.

Vi . Ti. + ;Г, И, 7i + JT, Vi-Ti- JT V, = b,

И, . r, + yTi,

v . T, - JT, Vi. = Tii - JT.,

V,j = bi- jbn Vii . Tii + JTi. Vii = r. - JT, v . n - JT

ЛИТЕРАТУРА

Монографии

[1] Nussbaumer, Н. J., Fast Fourier Transform and Convolution Algorithms

2nd ed., Springer-Verlag, Berlin, 1982. (Имеется перевод: Нуесбаумер Г.

Быстрое преобразование Фурье и алгоритмы вычисления свертки. - М.;

Радио и связь, 1985.1 [2] Kronsjo L. I., Algorithms: Their Complexity and Efficiency, John Wiley

New York, 1979.

[3] Aho, A. v., J. E. Hopcroff, and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass 1974. [Имеется перевод: Ахо A., Хопкрофт Дж., Ульман Дж. Построение и анализ вычис-лительных алгорипиов. - М.: Мнр, 1979,1

14] Elliott, D, Р., and R. Rao, Fast Transforms: Algorithms, Analyses, and Applications, Academic Press, New York, 1983.

Сборники статей

[11 McClellan, J, H,. and C, M, Rader, Number Theory in Digital Signal Processing, Prentice-Hall. Englewood Cliffs, N. J., 1979. [Имеется перевод: Макклеллан Дж. X., Редер Ч. М. Применение теории чисел в цифровой обработке сигналов. - М.: Радио и связь, 1983.]

Глава 1

[1] Cooley, J, W P. A. W, Lewis, and P, D, Welch, Historical Notes on the Fourier Transform, IEEE Trans. Audio Electroacoust. AU-15 (1967) : 76-

[2] Oppenheim, A. V. and R. W. Shafer, Digital Signal Processing, Prentice-Hall, Englewood Cliffs, N, J 1975.

[3] Rabiner, L, R and B. Gold, Theory and Application of Digital Signal Processing, Prentrce-Hall, Englewood Cliffs, 1975. [Имеется перевод; Pa-бннер Л. P., Гоулд Б. Теория и применение цифровой обработки сигналов. - М. Мир., 1978.]

[4] Winograd S., А New Algorithm for fnner Product, IEEE Trans. Corap. C-17 (1968): 693-694.

[6] Cooley, J. W., and J. W. Tukey, An Algorithm for the Machine Compulation of Complex Fourier Series, Math, Сотр. 19 (1965): 297-301.

[6] Stockham, T, G., High Speed Convolution and Correlation, Spring Joint Comput. Conf., AFIPS Conf. Proc. 28 (1966): 229-233.

[7] Good, I, J The Interaction Algorithm and Practical Fourier Analysis, J. Royal Statist, Soc, Ser, В 20 (1958); 361-375; addendum, 22 (1960): 372-375, к J

[8] Thomas, L, H Using a Computer to Solve Problems in Physics, in Applications of Digital Computers, Qinn and Co Boston, Mass 1963.

[9] Winograd, S On Computing the Discrete Fourier Transform, Proc, Nal, Acad. Sci. USA, 73 (1976): 1005-1006. [101 Winograd, S., On Computing the Discrete Fourier Transform, Math. Сотр., 32 (1978): 175-199. [Имеется перевод: см. сб. статей [1], с. 117 русск. изд.]

[11 ] Butler, J., and R. Lowe, Beam-forming Matrix Simplifies Design of Electronically Scanned Antennas, Electronic Design 9 (1961): 170-173.

[12] Agarwal, R. C, and J. W, Cooley, New Algorithms for Digital Convolution, IEEE Trans, Acoust., Speech, Signal Proc. ASSP-25 (1977): 392-410. [Имеется перевод: см. сб. статей [1], с. 91 русск. изд.]

Литература

[13] Levinson, N.. The Wiener RMS Error Criteria in Filter Design and Prediction, J. Math. Phys. 25 (1947): 261-278.

Глава 2

[1 ] Birkhoff, G and S, MacLane, A Survey of Modern Algebra, Macmillan, New

York, 1941; rev, ed 1953, [2] Van der Waerden, B, L., Modern Algebra, 2 vols, trans, by F. Blum and

T. J. Benac, Frederic Ungar Publishing Co., New York, 1949, 1953. [Имеется

перевод нем. изд. 1967 г.: Ван дер Варден Б. Л. Алгебра. - М.: Наука,

1976; 2-е изд. 1979.1 [3] Thrall, R. М. and L. Tornheim, Vector Spaces and Matrices, John Wiley,

New York, 1957.

[4] Fraleigh, J. В., A First Course in Abstract Algebra, 2nd. ed. Addison-Wesley, Reading, Mass. 1976.

[5] Strang, G., Linear Algebra and Its Applications, 2nd ed., Academic Press, New York, 1980, [Имеется перевод изд, 1976 г.: Стренг Г. Линейная алгебра и ее применения.-М.: Мир, 1980.]

[6] Baumslag, В. and В. Chandler, Theory and Problems of Group Theory, Schaums Outline Series, McGraw-Hill, New York, 1968.

[71 Pollard, J. M., The Fast Fourier Transform in a Finite Field, Math, Сотр. 25 (1971): 365-374. [Имеется перевод; см. сб. статей [1], с. 147 русск. изд.]

Глава 3

[1] Agarwal, R. С, and J, W. Cooley, New Algorithms for Digital Convolution, IEEE Trans. Acoust., Speech, Signal Proc, ASSP-25 (1977): 392410. [Имеется перевод: см. сб, статей [1], с. 91 русск. изд.]

(2] Winograd S., On Computing the Discrete Fourier Transform, Math. Сотр. 32 (1978): 175-199. [Имеется перевод: см. сб.статей П], с. 117 русск. изд,1

(3) Winograd, S., Some Bilinear Forms Whose Multiplicative Complexity Depends on the Feild of Constants, Math. Syst. Theor. 10 (1977): 169-80. (Имеется перевод: см, сб, статей [1], с. 225 русск. изд.]

[4] Winograd S., Arithmentic Complexity of Computations, CB.HS-NSF Regional Conf, Series Appl. Math Siam Publications 33, 1980.

[1] Cooley, J, W, and J. W, Tukey, An Algorithm for the Machine Computation of Complex Fourier Series, Math, Сотр. 19 (1965): 297-301.

[2] Singleton, Ж. C, An Algorithm for Computing the Mixel Radix Fast Fourier Transform, IEEE Trans. Audio Electroacoust. AU-17 (1969): 93-103.

[3] Good, I. J., The Interaction,Algorithm and Practical Fourier Analysis, J. Royal Statist, Soc, Ser. В 20 (1958): 36-375; addendum, 22 (1960): 372-375,

[4] Thomas, L, H Using a Computer to Solve Problems in Physics, Applications of Digital Computers, Ginn and Co., Boston, Mass. 1963.

[5] Good, I. J., The Relationship between Two Fast Fourier Transform, IEEE Trans. Comp, C-20 (1971): 310-317. [Имеется перевод: см. сб. статей [1], с. 136 русск. изд.]

[6] Rader, С, М and N. М. Brenner, А New Principle for Fast Fourier Transformation, IEEE Trans. Acoust., Speech, Signal Proc ASSP-24 (1976): 264-265.

[7] Preuss, R. D., Very Fast Computation of the Radix-2 Discrete Fourier Transform, IEEE Trans. Aucoust Speech, Signal Proc. ASSP-30 (1982): 595-607.

[8] Rader, C. M., Discrete Fourier Transforms When the Number of Data Samples Is Prime, Proc. IEEE 56 (1968): 1107-1108. [Имеется перевод: см. сб. статей [1], с. 89 русск. изд. 1

[9] Bluestein, L. I., А, Linear Filtering Approach to the Computation of the Discrete Fourier Transform, IEEE Trans. Audio Electroacoust. AU-18 (1970): 451-455.