(10] Winograd, S., On Computing the Discrete Fourier Transform, Math. Сотр. 32 (1978): 175-199.

fill Winograd S., On Computing The Discrete Fourier Transform, Math Сотр. 32 (1978): 175-199. /Шеется перевод: см. сб. статей с. 117 русск. взд. 1

[12] Johnson, Н. W., and С. S. Burrus, Large DFT Modules: 11, 13, 17, 19 and 25, Tech. Rep. 8105, Dep. Elec. Eng., Rice University, Houston, Texas, 1981.

[13] Ooertzel, Q., An Algorithm for the Evaluation of Finite Trigonometric

Series, Amer. Math. Monthly 65 (1968): 34-35. (14] Sarwate, D. V., Semi-Fast Fourier Transforms Over GF (2 ), IEEE Trans.

Сотр. C-27 (1978): 283-284.

Глава 5

1) Ore, 0., Number Theory and its History, McGraw-Hill, New York, 1948. 21 Hardy, Q. H., and E. M. Wright, The Theory of Numbers, Oxford University Press, Oxford, England, 1960.

[3] Birkhoff, G., and S. MacLane, A Survey of Modern Algebra, Macmillan, New York, 1941; rev. ed., 1953.

[41 Van der Waerden, B. L., Modern Algebra, 2 vols, transl. by F. Blum and T.J. Benac, Frederic Ungar Publishing Сл., New York, 1949, J953. (Имеется перевод: см. гл. II 12].]

[51 Berlecamp, Е. R., Algebraic Coding Theory, McGraw-Hill, New York, 1968. [Имеется перевод: Берлекэмп Э. Алгебраическая теория кодирования. - М.: Мир, 1971.1

[61 McClellan, 3. Н., and С. М. Rader, Number Theory in Digital Signal Processing, Prentice-Hall, Englewood Clif.s, N. J., 1979. [Имеется перевод: см. сб. статей [П.]

Глава в

(И Rader, С. М., Discrete Convolution via Mersenne Transforms, IEEE Trans. Сотр. C-21 (1972): 1269-1273.

[2] Agarwal, R. C, and C. S. Burrus, Fast Digital Convolution Using Fermat Transforms, Soutwest IEEE Conf. Rec. Houston (1973); 638-543.

[3] Agarwai, R. C, and C. S. Burrus, Fast Convolution Using Fermat Number Transforms with Applications to Digital Filtering, IEEE Trans. Acoust., Speech, Signal Proc. ASSP 22 (1974): 87-97. [Имеется перевод: см. сб. статей [П, с. 156 русск. изд.]

[4] Agarwal. R. С, and С. S. Burrus, Number Theoretic Transforms to Implement Fast Digital (involution, Proc. IEEE 63 (1975): 550-560.

[5] McClellan, J. H Hardware Realization of a Fermat Number Transform, IEEE Trans. Acoust., Speech, Signal Proc. ASSP-24 (1976): 216-225.

[6] Leibowitz, L. Л(., A. Simplified Binary Arithmetic for the Fermat Number Transform, ЧЕЕЕ Trans. Acoust., Speech, Signal Proc. ASSSP-24 (1976): 356-359. [Имеется перевод: см. сб. статей [1]. с. 202 русск. изд.]

[7] Reed, 1. S., and Т. К. Truong, The Use of Finite Fields to Compute Convolutions, IEEE Trans. Inf. Theor. IT-21 (1975): 208 -213. [Имеется перевод; см. сб. статей [1], с. 207 рус. изд.].

[8] Nussbaumer, Н. J., Digital Filtering Using Complex Mersenne Transforms, IBM Journal Res. Devel. 20 (1976): 498-504. [Имеется перевод: см. сб. статей [И. с. 216 русск. изд.]

[9] Rice, В., Winograd Convolution Algorithms over Finite Fields, Ongressus Numberatium 29 (1980): 827-857. [101 Preparata, F. P. and D. W. Sarwate, (Computational Complexity of Fourier Transforms over Finite Fields, Math. Сотр. 31 (1977): 740-751.

[11] Chevillat, P. R., Transform-Domain Filtering with Number Theoretic

Transforms, and Limited Word Length, IEEE Trans. Acoust., Speech,

Signal Proc. ASSP-26 (1978): 284-290 112) Szabo, N. S., and R. I. Tanaka, Residue Arithmetic and Its Application

to Computer Technology, McGraw-Hill, New York, 1967. [13] Jenkins, W. K. and B. J. Leon, The Use of Residue Number Systems in the

Design of Finite Impulse Response Digital Filters, IEEE Trans. Circuits

Syst. CAS-24 (1977); 191-201.

Глава 7

[1] Nussbaumer, H. J., Digital Filtering Using Polynomial Transforms, Electron. Lett. 13 (1977): 386-387.

[2] Blahut, R. E., Fast Convolution of Rational Sequences, Abstr. 1983 IEEE Internet. Sympos. Inf. Theor.. St. Jovitei Quebec, Canada, 1983.

13] Beth, Т., W. Fumy, and R. Muhlfeld, On Algebraic Discrete Fourier Transforms, Abstr. 1982 IEEE Internal. Sympos. Inf. Theor., Les Arcs, France, 1982.

[4] Arambepola, В., and P. J. W. Rayner, Efficient Transforms for Multidimensional Convolutions, Electron. Lett. 15 (1979): 189-190.

[5] Agarwal, R. C, and J. W. Cooley, New Algorithms for Digital Convolution, IEEE Trans. ASSP-26 (1977): 392-410. (Имеется перевод: см. сб. статей (I], с. 91 pyqcK. изд.]

(6] Nussbaumer, Н. J.. New Algorithms for Convolution and DFT Based on Polynomial Transforms, Proc. 1978 IEEE Internal. Conf. Acoust., Speech, Signal Proc. (1978): 638-641.

[7] Pitas, I., and M. G. Strlntzis, On the Multiplicative Complexity of TWo-Dimensional Fast Convolution Methods, Abstr. 1982 IEEE Internal. Sympos. Inf. Theor., Les Arcs, France, 1982.

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

Глава в

(II Rivard, а. е.. Direct Fast Fourier Transform of Blvarlate Functions, IEEE

Trans. Acoust., Speech, Signal Proc. ASSP-25 (1977); 250-252. [21 Harris, D. В., J. H. McClellan, D. S. K. Chan, and H. W. Schuessler, Vector Radix Fast Fourier Transform, Rec. 1977 IEEE. Internal. Conf. Acoust.. Speech, Signal Proc. (1977): 548-551. (3i Mersereau, R., and T. C. Speake, A Unified Treatment of Cooley-Tukey Algorithms for the Evaluation of the Multidimensional DFT, IEEE Trans. Acoust., Speech. Signal Proc. ASSP-29 (1981); 1011-1018. [4] Winograd, S., On Computing the Discrete Fourier Transform, Proc. Nat,

Acad. Sci. USA 73 (1976); 1005-1006. [5] Kolba. D. P., and T. W. Parks, A Prime Factor FFT Algorithm Using High Speed Convolution, IEEE Trans. Acoust., Speech, Signal Proc, ASSP-25 (1977); 281-294. 1Имеется перевод: см, сб. статей [1 J, с. 72 русск. изд.] [6] Silverman, Н. F., An Introduction to Programming the Winograd Fourier Transform Algorithm (WFTA), IEEE Trans. Acoust., Speech, Signal Proc. ASSP-25 (1977): 162-165. (71 Johnson, H. W., and C. S. Burrus, The Design of Optimal DFT Algorithms Using Dynamic Programming, IEEE Trans. Acoust., Speech, Signal Proc. ASSP-31 (1983); 378-387. [8] Nussbaumer, H. J.. and P. Quandalle, Fast Computation of Discrete Fourier Transforms Using Polynomial Transforms, IEEE Trans. Acoust., Speech, Signal Proc. ASSP-27 (1979); 169-181.

[9] Nussbaumer, Н. J., and P. Quandalle, New Polynomial Transform Algorithms for Fast DFT Computations, Proc. IEEE 1979 Internal. Acoust., Speech, Signal Proc. Conf. (1979): 510-513. JlOl Auslander, L., E. Feig, and S. Winograd, New Algorithms for the Multidimensional Discrete Fourier Transform, IEEE Trans. Acoust., Speech, Signal Proc. ASSP-31 (1983): 388-403.

Глава 9

[1] Stockham, T. G., High Speed Convolution and Correlation, 1966 Spring Joint Comput. Conf., AFIPS Proc. 28 (1966): 229-233. ., [2] Agarwal, R. C., and C, S. Burrus, Fast One-Dimensional Digital Convolution by Multidimensional Techniques, IEEE Trans. Acoust., Speech, Signal Proc. ASSP-22 (1974): 1-10. [Имеется перевод: см. сб. статей [1], с. 172 русск. изд.]

(31 DuBois, Е. and А. N. Venetsanopoulos, Convolution Using а Conjugate Symmetry Property for the Generalized Discrete Fourier Transform, IEEE Trans. Acoust., Speech, Signal Proc. ASSP-26 (1978): 165-170.

[4] Winograd, S., On the Complexity of Symmetric Filters, Proc. Internat. Sympos. Circuits Syst. Tokyo (1979): 262-265.

IS] Winograd S.. Arithmetic Complexity of Computations, CBMS-NSF Regional Conf. Ser. Appl. Math. Siam Publications 33, 1980.

[6] Hopcroft, J. E., and J. Musinski, Duality Applied to the Complexity of Matrix Multiplication and Other Bilinear Forms, SIAM J. Comput. 2 (1973): 169-173.

[7] Rader, C. M., An Improved Algorithm for High Speed Autocorrelation with Applications to Spectra! Estimation, IEEE Trans. Audio Electroacoust., AU-18 (1970): 439-441.

[8] Burrus, C. S., and P. W. Eschenbacher, An In-Place Prime Factor FFT Algorithm, IEEE Trans. Acoust..Speech, Signal Proc. ASSP-29 (1979):806-817.

[9] Liu, В., and F. Mintzer, Calculation of Narrow-Band Spectra by Direct Decimation, IEEE Trans. Acoust., Speech, Signal Proc. ASSP-26 (1978): 629-534.

[101 Crochiere, R. E., and L. R. Rabiner, Interpolation and Decimation of Digital Signals - A Tutorial Review, Proc, IEEE 69 (1981): 330-331.

[11] Kolba, D, P and T, W. Parks, A Prime Factor FFT Algorithm Using High Speed Convolution. IEEE Trans. Acoust.. Speech, Signal Proc. ASSP-26 (1977): 281-294. [Имеется перевод: см. сб, статей [1], с, 72 русск. изд,]

[12] Silverman, Н. F., An Introduction to Programming the Winograd Fourier Transform Algorithm (WFTA), IEEE Trans. Acoust., Speech, Signal Proc, ASSP-25 (1977): 152-166.

[13] Morris, P. L., A Comparative Study of Time Efficient FFT and WFTA Programs for General Purpose Computers, IEEE Trar\s. Acoust., Speech, Signal Proc. ASSP-26 (1978): 141-150,

[14] Nawab, H and J. H. McClellan, Bounds on the Minimum Number of Data Transfers in WFTA and Programs, IEEE Trans. Acoust. Speech, Signal Proc. ASSP-27 (1979): 393-398.

[15] Patterson, R. W., and J. H. McClellan, Fixed-Point Error Analysis of Winograd Fourier Transform Algorithms, IEEE Trans. Acoust., Speech, Signal Proc. ASSP-26 (1978): 447-456.

[16] Panda, G., R. N. Pal, and B. Chatterjee, Error Analysis of Good-Winograd Algorithm Assuming Correlated Truncation Errors, IEEE Trans. Acoust., Speech. Signal Proc. ASSP-31 (1983): 508-512.

Глава 10

[I] Knuth. D. E., The Art of Computer Programming, Vol, 1: Fundamental Algorithms, Addison-Wesley, Reading, Mass., 1968. [Имеется перевод; Кнут Д. Искусство программирования, том 1.-М.; Мнр, 1976.]

[2] Aho, А. V., J. Е. Horcroll. and J. D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, Mass., 1974. [Имеется перевод; см. Монографии [3] .]

[3] Williams, J. М. J., Algorithm 232; Heapsort, Comm ACM 7 (1964): 347-348.

14) Hoare, C. A. R., Quicksort, Comp, J. 6, 1962.

[5] Steiglitz, K., An Introduction to Discrete Systems, John Wiley, New York, 1974.

[6] Fiduccia, C. M., Polynomial Evaluation via the Division Algorithm - The

Fast Fourier Tranform Revisited, Proc. 4th Annual ACM Symp. Theory

Comput. (1972): 88-93. [7] Eklundh, J. O., A Fast Computer Method for Matrix Transposing, IEEE

Trans. Comp, C-21 (1972): 801-803, [8] Winograd, S., Signal Processing and Complexity of Computation, Proc. Int.

Conf. Acoust., Speech, Singnal Proc. (1980): 94-101. [9] Voider, J. E., IRE Trans. Electr. Comp. EC-8 (1959): 330-334. [10] Walther, J. S., Proc. 1971 Spring Joint Comp. Conf. (1971): 379-385. [11] Blahut, R. E., and D, E. Waldecker, Half.Angle Sine-Cosine Generator,

IBM Tech, Disclosure Bull. 13, no. 1 (1970): 222-223.

Глава 11

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

[2] Durbin, J., The Fitting of Time-Series Models, Rev. Internat. Statist. Inst. 23 (1960): 233-244.

[3] Trench, W. F., An Algorithm for the Inversion of Finite Toeplitz Matrices, J. SIAM 12, no. 3 (1964): 512-522.

[4] Berlecamp, E. R., Algebraic Coding Theory, McGraw-Hill, New York, 1968, [Имеется перевод: см. гл. V [5]. ]

[5] Zohar, S The Solution of a Toeplitz Set of Linear Equations, J. Assoc. Comput. Math. 21 (1974): 272-276.

[6] Massey, J. L., Shoft-Register Synthesis and BCH Decoding, IEEE Trans. Inf, Theor. IT-15 (1969): 122-127.

[7] Welch, L. R., and R. A. Scholtz, Continue Fractions and Berlecamps Algorithm, IEEE Trans. Inf. Theor. IT-25 (1979): 19-27.

[8] Blahut, R. E., Theory and Practice of Error Control Codes, Addison-Wesley, Reading, Mass 1983. [Имеется перевод; Блейхут P. Теория и практика кодов, контролирующих ошибки.-М.: Мир, 1986.]

[91 Sugiyama, У., М. Kasahara, S, Hirasawa, and Т. Namekawa, А Method for Solving Key Equation for Decoding Qoppa Codes, Inf. Control 27 (1975): 87-99.

[10] Brent, R. P., F. G. Gustavson, and D, Y. Y. Yun, Fast Solution of Toeplitz Systems of Equations and Computation of Pade Approximants, J. Algorithms 1 (1980): 259-295.

[11] Vieira, A, and T, Kailath, On Another Approach to the Schur-Cohn Criterion, IEEE Trans. Circuits Syst. CAS-24, no, 4 (1977); 218-220.

112] Wiggins, R, A., and E. A. Robinson, Recursive Solution to the Multichannel Filtering Problem, J, Geophys. Res. 70 (1965): 1885-1891.

[13] Dickinson, B. W., Efficient Solution of Linear Equations with Banded Toeplitz Matrices, IEEE Trans. Acoust., Speech, Signal Proc. ASSP-27 (1979): 421-423.

[141 Dickinson, B, W,. M. Morf, and T. Kailath, A Minimal Realization Algorithm for Matrix Sequences, IEEE Trans, Automatic Control AC-19 (1974): 31-38.

[15] Friediander,. В., M. Morf, T. Kailath, and L. Ljung, New Inversion Formulas for Matrices Classified in Terms of Their Distance from Toeplitz Matrices, Linear Algebra and lis 3VPPication 27 (1979): 31-60.

442 Литература

[16] Morf, М,. В. W. Dickinson, Т. Kailath, and А. С. Q. Vieira, Efficient Solution of Covariance Equations for Linear Prediction, IEEE Trans. Acoust., Speech, Signal Proc. ASSP-25 (1977): 429-433.

[171 Monden, Y., and S. Arimofo, Generalized Rouches Theorem and Its Application to Multivariate Autoregressions, IEEE Trans. Acoust., Speech. Signal Proc. ASSP-28 (1980): 733-738.

Глава 12

[1] Viterbi, A. J., Error Bounds for Convolutional Codes and an Asymptotically Optimum Decoding Algorithm, IEEE Trans. Inf. Theor. IT-13 (1%7): 260-269.

[2] Wozencrafi, J. M., Sequential Decoding for Reliable Communication, 1957 Nat. IRE Conv. Rec. 5, part 2 (1957): 11-25.

[3] Wozencrafi, J. M., and B. Reiffen, Sequential Decoding, MIT Press, Cambridge, Mass., 1961.

[41 Fano, R, M., A. Heuristic Discussion of Probabilistic Decoding, IEEE Trans. Inf. Theor. IT-9 (1963): 64-74.

[5] Зигангиров К. Ш. Некоторые процедуры последовательного декодирования. - Проблемы передачи информации, 1966, вып. 2, с. 13-25.

[6] Jelinek, F. А. Fast Sequential Decoding Algorithm Using a Stack. IBM J. Res. Devel. 13 (1969): 675-686.

[7] Jelinek, F., Probabilistic Information Theory, Mc(3raw-Hill. New York 1968.

[8] Forney. G. D., Convolutional Codes III: Sequential Decoding, Inform. Contr.

25 (1974): 267-297. [9] Chevillat, P. R., and D. J. Costello, Jr., An Analysis of Sequential Decoding for Specific Time-Invariant Convolutional Codes, IEEE Trans. Inf Theor. It-24 (1978): 443-451.

[10] Haccoun, D., and M. J. Ferguson, Generalized Stack .Mgoritms for Decoding Convolutional Codes, IEEE Trans. Inf. Theor. IT-21 (1975): 638-651.

[llj Gallager, R. G., Information Theory and Reliable Communications, John Wiley, New York, 1968. [Имеется перевод: Галлагер P. Теория информации и надежная связь. - М.: Сов. радио, 1974.]

[12] Rader, С. М., Memory Management in а Viterbi Decoder, IEEE Trans. Com-municat. COM-29 (1981): 1399-1401.

[13] Jacobs, I. M., and E, R. Berlecamp, A Lower Bound to the Distribution of Computations for Sequential Decoding, IEEE Trans. Inl. Theor. IT-13 (1967): 167-174.

[14J Savage, J. E., Sequental Decoding-The Computation Problem, Bell Syst. Tech. J. 45 (1966): 149-175.

[15] Jelinek, F., An Upper Bound on Moments of Sequential Decoding Effort. IEEE Trans. Inf. Theor. IT-15 (1969). 140-149.

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ

абелева группа 34 автокорреляция 327 адресное тасование 130 алгебра матричная 50 алгебраическое дополнение 52 алгоритм [15

- БПФ Винограда 157

---для больших длин преобразования 270

---улучшенный 286

--выколотый 294

-- гнездовой 265

--Гуда-Томаса 141

--Кули-Тьюки 128

---по основанию два 133

----- четыре 139

--перестановочный Нуссбаумера-Квенделла 287

--Рейдера-Бреннера 136

- быстрой сортировки 350 -- транспозиции 356

- Витерби 406

- Герцеля 144

- деления 59, 64

- Дурбина 377

- Евклида 60, 68 -- рекурсивный 360

- поиска по решетке 402

- решения теплицевой системы Берле-

кэмпа-Месси 385

------, рекурсивный 394

---- Дурбина 377

---- Левинсона 373

---- Тренча 380

----, основанный на рекурсивном алгоритме Евклида 397

- свертки Агарвала-Кули 226 --Винограда 90

- гнездовой 220

--итеративный 237

--Карацубы 85

--Кука-Тома 84

--, метод разложения 233

--Препараты-Сервейта 216

- секционной фильтрации 306, 310 -, сложность из

- сортировки 349 -- слиянием 350

- Тренча 380

- Фано 414

- Штрассена умножения матриц 357 ассоциативность 33, 39, 48

бабочка 352 базис 50 буфер 418

быстрая сортировка 350

- транспозиция 356

быстрое преобразование Фурье (БПФ) 129

вектор 47

векторное пространство 49 векторы ортогональные 49 взаимная корреляция 327 взаимно-простые многочлены 63 --- числа 58

внешнее произведение (векторов) 54 вычет 177, 180

- квадратичный 209

группа 33

- абелева 34

- ко.ммутатнвная 34

- конечная 34

-, образующая 35

-, порядок 35

-, пронзаедение 36

-, разложение на смежные классы 37

- циклическая 35

деление с остатком 39 делимость 39 дерево 348

диаграмма переходов 403 дискретное преобразование Фурье

(ДПФ) 28 дистрибутивность 39, 48 длина кодового ограничения 403

единица группы 35

- кольца 39 единичная матрица 51 единичный элемент 34

замкнутость 33, 39

изоморфизм 34

интерполяция Лагранжа 71, 84 итеративный алгоритм 237 итерация 237

кольцо 39

- вычетов 177

- коммутативное 39