Cited by 274Digital Filter Design and ImplementationMathematical Analysis and Transform MethodsAdvanced Data Compression Techniques

The DOI matches its Crossref record; 127 of the 127 references it cites were found in a registry or an index.

Fast Algorithms for Signal Processing

Blahut, Richard E.·2010·Cambridge University Press eBooks

DOI 10.1017/cbo9780511760921

Open this paper in CoChat — free account

Abstract

Efficient signal processing algorithms are important for embedded and power-limited applications since, by reducing the number of computations, power consumption can be reduced significantly. Similarly, efficient algorithms are also critical to very large scale applications such as video processing and four-dimensional medical imaging. This self-contained guide, the only one of its kind, enables engineers to find the optimum fast algorithm for a specific application. It presents a broad range of computationally-efficient algorithms, describes their structure and implementation, and compares their relative strengths for given problems. All the necessary background mathematics is included and theorems are rigorously proved, so all the information needed to learn and apply the techniques is provided in one convenient guide. With this practical reference, researchers and practitioners in electrical engineering, applied mathematics, and computer science can reduce power dissipation for low-end applications of signal processing, and extend the reach of high-end applications.

Integrity signals

Registry

Crossref · 10.1017/cbo9780511760921

Cites

127 of 127 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Claims the paper makes

This paper’s full text isn’t openly available, so its claims and self-check weren’t run. The registry and citation checks still apply.

An algorithm for the machine calculation of complex Fourier series
Cooley, J. W., & Tukey, J. W. (1965) · Mathematics of Computation · doi:10.1090/s0025-5718-1965-0178586-1 · Cited by 13,154
The Design and Analysis of Computer Algorithms
Aho, A. V., & Hopcroft, J. E. (1974) · CERN Document Server (European Organization for Nuclear Research) · Cited by 9,403
Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
Viterbi, A. J. (1967) · IEEE Transactions on Information Theory · doi:10.1109/tit.1967.1054010 · Cited by 6,954
Information Theory and Reliable Communication.
Lee, P. M., & Gallager, R. G. (1970) · Journal of the Royal Statistical Society Series A (General) · doi:10.2307/2344305 · Cited by 5,429
Discrete Cosine Transform
Ahmed, N., Natarajan, T., & Rao, K. R. (1974) · IEEE Transactions on Computers · doi:10.1109/t-c.1974.223784 · Cited by 5,156
Optimal decoding of linear codes for minimizing symbol error rate
Bahl, L. R. (1974) · IEEE Transactions on Information Theory · Cited by 4,665
Theory and Application of Digital Signal Processing
Rabiner, L. R., Gold, B., & Yuen, C. K. (1978) · IEEE Transactions on Systems Man and Cybernetics · doi:10.1109/tsmc.1978.4309918 · Cited by 2,821
Modular Multiplication Without Trial Division
Montgomery, P. L. (1985) · Mathematics of Computation · doi:10.1090/s0025-5718-1985-0777282-x · Cited by 2,659
The CORDIC Trigonometric Computing Technique
Volder, J. E. (1959) · IRE Transactions on Electronic Computers · doi:10.1109/tec.1959.5222693 · Cited by 2,655
Gaussian elimination is not optimal
Strassen, V. (1969) · Numerische Mathematik · doi:10.1007/bf02165411 · Cited by 2,509

Show all 126 references

Sorted by citations

Items 201–274 of 274

High speed implementation of certain adaptive filters: A novel Toeplitz matrix decomposition approach
McWhorter, F. L., & Tague, J. A. (1993) · Circuits Systems and Signal Processing · doi:10.1007/bf01188091 · Cited by 1
The Goertzel-Blahut algorithm is closely related to the fast fourier transform
Fedorenko, S. V. (2012) · International Symposium on Problems of Redundancy in Information and Control Systems (REDUNDANCY) · doi:10.1109/red.2012.6338398 · Cited by 1
Signal to Interference Ratio Based Antenna Selection for Spatial Multiplexing
Batabyal, S., & Das, S. S. (2015) · Wireless Personal Communications · doi:10.1007/s11277-015-2435-x · Cited by 1
Stratification-induced scale splitting in convection
Shcheritsa, O. V., Гетлинг, А. В., & Mazhorova, O. S. (2014) · Advances in Space Research · doi:10.1016/j.asr.2014.08.034 · Cited by 1
Design of Secure Ad Hoc Network Using Three Dimensional Discrete Wavelet Transformation Based on Performance Enhancement
Abdul-Rahaim, L. A. (2015) · American Journal of Networks and Communications · doi:10.11648/j.ajnc.s.2015040301.17 · Cited by 1
Global Positioning System: A New Opportunity in Human Life Logging System
Bakdaulet, D., Yermekbayeva, J. J., Suleimenova, S. T., & Kulniyazova, K. (2018) · Advances in intelligent systems and computing · doi:10.1007/978-981-13-0344-9_42 · Cited by 1
An Image Zero Watermark Algorithm Based on DINOv2 and Multiple Cycle Transformation
Huang, X., & Wu, Y. (2024) · Lecture notes in computer science · doi:10.1007/978-981-99-9788-6_22 · Cited by 1
Low-complexity general FIR filters based on Winograd's inner product algorithm
Gustafsson, O., & Ehliar, A. (2013) · IEEE International Symposium on Circuits and Systems proceedings · doi:10.1109/iscas.2013.6571790 · Cited by 1
Digital-domain chromatic dispersion compensation for different pulse shapes: Practical considerations
Rozental, V. N., Parahyba, V., Reis, J. D., de Oliveira, J. F., & Mello, D. A. A. (2015) · SBMO/IEEE MTT-S International Microwave and Optoelectronics Conference (IMOC) · doi:10.1109/imoc.2015.7369135 · Cited by 1
Time Delay Estimation via Co-Prime Aliased Sparse FFT
Bei, Z. H. A. O., Chen, C., Ma, Z., & Yu, F. N. (2016) · IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences · doi:10.1587/transfun.e99.a.2566 · Cited by 1
Performance evaluation of the program of DCT-II using cyclic convolutions
Prots’ko, I., Rykmas, R., & Mashevska, M. (2017) · IEEE International Conference on Computer Sciences and Information Technologies (CSIT) · doi:10.1109/stc-csit.2017.8098785 · Cited by 1
Constructing Fast Algorithms by Expanding a Set of Matrices into Rank-1 Matrices
da Silva, G. J., & de Souza, R. M. C. (2019) · Circuits Systems and Signal Processing · doi:10.1007/s00034-019-01228-5 · Cited by 1
Алгоритмы прямого и обратного ДКП малых порядков с уменьшенной мультипликативной сложностью
Царёв, А. П., Makowska, M., & Стшелец, П. (2019) · Известия высших учебных заведений Радиоэлектроника · doi:10.20535/s0021347019110025 · Cited by 1
The Cosine Number Transform: A Graph Signal Processing Approach
Ribeiro, G. B., & Lima, J. B. (2019) · IEEE Global Conference on Signal and Information Processing · doi:10.1109/globalsip45357.2019.8969165 · Cited by 1
FAST RATIONAL INTERPOLATION OF TRANSFER FUNCTIONS OF LINEAR DYNAMIC SYSTEMS WITH DISTRIBUTED PARAMETERS
Kodnyanko, V. (2020) · Radio Electronics Computer Science Control · doi:10.15588/1607-3274-2020-4-5 · Cited by 1
A New Simple Algorithm for Deriving the Winograd 9-Point FFT by Using New Identical Equations for 3 × 3 Circulant and Quasi-Circulant Matrices
Takahashi, N., Takago, D., & Takebe, T. (2020) · Journal of Signal Processing · doi:10.2299/jsp.25.43 · Cited by 1
Fast 10-Point DFT Algorithm for Power System Harmonic Analysis
Papliński, J. P., & Cariow, A. (2021) · Applied Sciences · doi:10.3390/app11157007 · Cited by 1
A Novel Approach for Defining a Hilbert Number Transform
Lima, J. B., Gondim, M. A. A., & de Souza, R. M. C. (2021) · Circuits Systems and Signal Processing · doi:10.1007/s00034-021-01834-2 · Cited by 1
Formant Frequencies Estimation Based on Correlogram Method of Spectral Analysis and Binary-Sign Stochastic Quantization
Yakimov, V. N., Lange, P. K., & Yaroslavkina, E. E. (2022) · Studies in systems, decision and control · doi:10.1007/978-3-030-95120-7_13 · Cited by 1
Precoded GFDM System to Combat Inter Carrier Interference : Performance AnalysisPreprint
Tiwari, S., Das, S. S., & Bandyopadhyay, K. K. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1506.03744 · Cited by 1
Hitless rate and bandwidth switching in dynamically recon gurable coherent optical systems
Rozental, V. N. (2016) · doi:10.26512/2016.01.t.21966 · Cited by 1
Digital and Mixed Domain Hardware Reduction Algorithms and Implementations for Massive MIMO
Akram, N. (2020) · doi:10.25148/etd.fidc009239 · Cited by 1
Design and Realization of Fully-digital Microwave and Mm-wave Multi-beam Arrays with FPGA/RF-SOC Signal Processing
Pulipati, S. K. (2021) · doi:10.25148/etd.fidc009769 · Cited by 1
Enhancement of spectrum sensing in cognitive radio : providing reliable spectral opportunities
Moawad, A. (2020) · doi:10.70675/6842ede0zbd41z438azb5cbzfc6b6c9e4907 · Cited by 1
Optimization of calculating time-frequency correlation function on the CPU
Avramchuk, V. S., Евгеньевна, Л. Е., & Cheremnov, A. G. (2014) · International Conference on Mechanical Engineering, Automation and Control Systems · doi:10.1109/meacs.2014.6986858
Computational Study and Performance Evaluation of Different Genomic Signal Processing Methods for Identification of Protein Coding Regions (Exon Regions) of DNA Sequence
N.VamsiThalatam, M., & Rao, A. A. (2014) · International Journal of Computer Applications · doi:10.5120/14884-3318
Processing module of FFT in monolithic single-chip MEMS
Prots’ko, I., Teslyuk, V., & Lozynskyi, A. (2016) · International Conference on Perspective Technologies and Methods in MEMS Design · doi:10.1109/memstech.2016.7507524
DEVELOPMENT OF WFTA BASED ON THE HASHING ARRAY
Prots’ko, I., & Teslyuk, V. (2018) · Radio Electronics Computer Science Control · doi:10.15588/1607-3274-2018-2-15
Quadratic exponential in modified discrete Fourier transform and shifted Gaussian series
Валерьевна, Р. Е., Serbina, L. I., & Ситник, С. М. (2019) · Journal of Physics Conference Series · doi:10.1088/1742-6596/1203/1/012098
Lossless and low-cost integer-based lifting wavelet transform
Hasan, M. M. (2019) · HARVEST (University of Saskatchewan)
Digital Analysis of the Vibration Signals Amplitude Spectrum Based on Fourier Processing of the Binary-Sign Analog-Stochastic Quantization Result
Yakimov, V. N., Batyschev, V. I., & Mashkov, A. V. (2019) · Mekhatronika Avtomatizatsiya Upravlenie · doi:10.17587/mau.20.723-731
Огляд алгоритмів ефективного обчислення дпф на основі циклічних згорток
Prots’ko, I. (2016) · Computer systems and network · doi:10.23939/csn2016.857.082
High Performance Digital Algorithm for Calculating the Harmonic Spectrum Estimates of Complex Signals
Yakimov, V. N., Акулов, В. А., Batishchev, V. I., & Mashkov, A. V. (2019) · International Conference on Complex Systems: Control and Modeling Problems (CSCMP) · doi:10.1109/cscmp45713.2019.8976762
Multidimensional Signal Processing Techniques for Disturbance Mitigation in Synthetic Aperture Systems
Edussooriya, C. U. S. (2012) · UVic’s Research and Learning Repository (University of Victoria)
The Fractional Quaternion Fourier Number Transform
da Silva, L. C., Neto, J. R. D. O., & Lima, J. B. (2020) · IEEE International Conference on Acoustics Speech and Signal Processing · doi:10.1109/icassp40776.2020.9054714
A Multistaged Hyperparallel Optimization of the Fuzzy-Logic Mechanistic Model of Molecular RegulationPreprint
Aiyetan, P. (2020) · bioRxiv (Cold Spring Harbor Laboratory) · doi:10.1101/2020.09.28.315986
Optimising the Performance of Convolutional Neural Networks across Computing Systems using Transfer LearningPreprint
Mulder, R., Radu, V., & Dubach, C. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2010.10621 · Cited by 2
Spectral Analysis Based on a Discrete Binary Model for Signal Stochastic Quantization and Calculating a Weighted Correlation Function Estimate.
Yakimov, V. N., & Batishchev, V. I. (2020) · International Conference on Software Testing, Verification, and Validation
Image Inpainting as a Quadratic Programming Task
Myasnikov, V., & Verichev, A. (2020) · International Conference on Information Technology and Nanotechnology (ITNT) · doi:10.1109/itnt49337.2020.9253173
Accelerating two dimensional FFT and convolutional neural networks on FPGA
Kala, S., & Jose, B. R. (2020) · Dyuthi Digital Repository (Cochin University of Science and Technology)
Fast computation of the SLTF transform
Końca, R. (2015) · PRZEGLĄD ELEKTROTECHNICZNY
ANALYSIS OF THE ERROR OF COMPUTATION FAST TRANSFORMS OF FOURIER CLASS BASED ON CYCLIC CONVOLUTIONS
Prots’ko, I., & Ostrovka, D. (2020) · Ukrainian Journal of Information Technology · doi:10.23939/ujit2020.02.052
Implementação em FPGA de Geradores de Números Pseudo-aleatórios sobre Anéis de Inteiros
de Almeida, D. C. M., Souza, C. E., Chaves, D. P. B., & Pimentel, C. J. L. (2021) · Anais de XXXV Simpósio Brasileiro de Telecomunicações e Processamento de Sinais · doi:10.14209/sbrt.2021.1570733941
Derivation of Diagonalized Identical Equations for 3 by 3 Circulant and Quasi-Circulant Matrices and Their Application to Winograd 7-Point FFT
Takahashi, N., & Takago, D. (2021) · Journal of Signal Processing · doi:10.2299/jsp.26.13
Transformada Rápida de Hartley Otimizada
Jr., G., & Souza, R. (2013) · Anais de XXXV Simpósio Brasileiro de Telecomunicações e Processamento de Sinais · doi:10.14209/sbrt.2013.220
Fourier filter-based physics- information convolutional recurrent network for 2D incompressible flow
Xiao, C., Zhu, X., Yin, F., Cao, X., Peng, K., & Nie, J. (2022) · Frontiers in Physics · doi:10.3389/fphy.2022.971722
Further Quaternion Integral Transforms
Hitzer, E. (2023) · Trends in mathematics · doi:10.1007/978-3-031-28375-8_3
Primary and branched solutions in the problem of approximation of the finite function by modulus of double discrete Fourier transform
Савенко, П. О. (2021) · Математичні методи та фізико-механічні поля · doi:10.15407/mmpmf2021.64.4.32-46
أثر التفاعل بين أسلوبين للعصف الذهني (سحابة الكلمة-الخرائط الذهنية الرقمية) في بيئة تعلم إلكترونية وأسلوب التعلم (البصري/ اللفظي) لتنمية مهارات حل المشكلات التكنولوجية والتفكير البصري وبقاء أثر التعلم لدى الطلاب المعلمين
الرسول, ن. ا. م. ف. ع. (2023) · تکنولوجيا التعليم سلسلة دراسات وبحوث · doi:10.21608/tesr.2023.337885
Arithmetic for Deep Learning
de Dinechin, F. D., & Kumm, M. (2023) · Springer eBooks · doi:10.1007/978-3-031-42808-1_24
Primary and Branched Solutions in the Problem of Approximation of a Finite Function by the Modulus of Double Discrete Fourier Transform
Савенко, П. О. (2024) · Journal of Mathematical Sciences · doi:10.1007/s10958-024-07002-6
High-Order Block Toeplitz Inner-Bordering Method for Solving the Gelfand-Levitan-Marchenko EquationPreprint
Медведев, С. Б., Vaseva, I. A., & Федорук, М. П. (2024) · SSRN Electronic Journal · doi:10.2139/ssrn.4852227
DEVELOPMENT OF A PLUG-IN FOR VIZUALIZATION OG STRUCTURAL SCHEMES OF COMPUTERS BASED ON THE TEXTUAL DESCRIPTION OF ALGORITHMS OF HARMONIC TRANSFORMS
Prots’ko, I., & Teslyuk, V. (2024) · Radio Electronics Computer Science Control · doi:10.15588/1607-3274-2024-2-15
Optimizing RGB Convolution on Cortex-M7 MCU: Approaches for Performance Improvement
Lee, S., Sung, J., & Kwon, J.-W. (2024) · IEEE Access · doi:10.1109/access.2024.3439586
The Design and Implementation of the Very Coarse Channelizer for the ALMA 2030 Wideband Sensitivity Upgrade
Gunaratne, T. (2024) · IEEE Pacific Rim Conference on Communications, Computers and Signal Processing (PACRIM) · doi:10.1109/pacrim61180.2024.10690187
Space-Frequency Processing Methods for Satellite Navigation Signals
Tsarik, V. I. (2024) · Proceedings of Telecommunication Universities · doi:10.31854/1813-324x-2024-10-6-34-44
Analysis of Near-Field Intensity Distribution in Subwavelength Gratings Through Decomposition into Cylindrical Waves
Bereza, A. S., Chernyavsky, A. E., Perminov, S. V., & Shapiro, D. A. (2024) · Bulletin of the Lebedev Physics Institute · doi:10.3103/s106833562460270x
Wideband Digital $N$ -Beam Delay-Sum Apertures at $\mathcal{O}(N)$ Complexity: Towards 64 GS/s 8-Beams on Intel Agilex-9 Direct-RF Chiplets
Perera, S. M., & Madanayake, A. (2024) · IEEE International Conference on RFID Technology and Applications (RFID-TA) · doi:10.1109/rfid-ta64374.2024.10965176
Review of discrete-time signal processing
Mandal, S. (2025) · Elsevier eBooks · doi:10.1016/b978-0-44-334719-1.00008-x
An Efficient 64-Point IFFT Hardware Module Design
Efnusheva, D., Tentov, A., & Tagasovska, N. (2014) · Lecture notes in electrical engineering · doi:10.1007/978-3-319-06764-3_59
Fast DCT-VIII Algorithms for Short-Length Input Sequences
Raciborski, M., Polyakova, M. V., & Cariow, A. (2026) · Electronics · doi:10.3390/electronics15010207
Fast Algorithms for Digital Processing of Measurement Data and Assessment of the Technical Condition of Aviation Facilities Power Equipment
Myrhorod, V., ГВОЗДЕВА, І. М., Будашко, В. В., & Grama, G. (2025) · IEEE International Conference on Methods and Systems of Navigation and Motion Control (MSNMC) · doi:10.1109/msnmc61130.2025.11399740
Accelerated Algorithm for Solving the Direct Scattering Problem for the Wave Equation
Frumin, L. L., & Chernyavsky, A. E. (2025) · Optoelectronics Instrumentation and Data Processing · doi:10.3103/s8756699025700840
Extraordinary optical transmission in holographic and polycrystalline diffractive nanostructures
Ushkov, A. (2020) · doi:10.70675/0ce765f9zb1a1z4903zb19ezcefe58849bd9
A Novel Hybrid Quantum Circuit for Integer Factorization: End-to-End Evaluation in Simulation and Real Quantum Hardware
Thé, J. V. G., Santos, V. O., & Gharabaghi, B. (2026) · Journal of Cybersecurity and Privacy · doi:10.3390/jcp6020071
Further Development of the Polynomial Based Method for the Discrete Fourier Transform Computation Over the Finite Field
Olshevskaia, O., Lotonina, K., & Fedorenko, S. V. (2026) · International Conference on Digital Signal Processing and its Applications (DSPA) · doi:10.1109/dspa69176.2026.11476741
Channel Estimation and 3-D Near-Field Localization for Extremely Large Antenna Arrays
Guellil, R., Abed‐Meraim, K., Belouchrani, A., & Trung, N. L. (2026) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2026.3689640
Digital Computation of the Fractional Fourier Transform Based on Modulo-$$2^b+1$$ Convolutions
Gutierrez-Huampo, E., Neto, J. R. D. O., & Lima, J. B. (2026) · Circuits Systems and Signal Processing · doi:10.1007/s00034-026-03674-4
Visualization of the Structure of DCT Based on the Synthesized Algorithm Using Cyclic Convolutions
Prots’ko, I., Bilas, Y., & Teslyuk, V. (2023) · International Workshop on Computer Information Technologies in Industry 4.0 (CITI) · doi:10.55056/ceur-ws.org/vol-3468/paper10.pdf
Geometry-Aware Transform Pruning for Omnidirectional Image Compression
da Silveira, T. L. T., Segala, E. B., Bayer, F. M., & Cintra, R. J. (2026) · IEEE Access · doi:10.1109/access.2026.3726449
A Recursive Welch–Berlekamp Algorithm with Quasi-Linear Complexity O(nlog 2 n)
Chen, C., Tang, N., Han, Y. S., & Bai, B. (2026) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit62367.2026.11653655
Optimized Shift & Add Multipliers for Efficient Filter and Neural Network Implementations
Khorbotly, S., & Zeudom, F. A. (2026) · IEEE International Conference on Electro Information Technology · doi:10.1109/eit68936.2026.11670429
Approaches to the Design of Fast Parallel Finite-Impulse Response Filter Structures [Lecture Notes]
Parhi, K. K., & Nassif, R. (2026) · IEEE Signal Processing Magazine · doi:10.1109/msp.2026.3693977
Inspection Factorization for Hardware-Efficient 2D Fast Convolution
Silva, T. O. D., & Moraes, F. (2026) · Symposium on Integrated Circuits and Systems Design · doi:10.1109/sbcci69725.2026.11706796

Authors: Blahut, R. E.
Affiliations: University of Illinois Urbana-Champaign (US)
Corresponding author: Blahut, Richard E.
Venue: Cambridge University Press eBooks
Publisher: Cambridge University Press
Published: 2010-06-24
DOI: 10.1017/cbo9780511760921
OpenAlex: W565312106
Cited by: 274
References: 126
Citations by year: 2026: 13 · 2025: 17 · 2024: 24 · 2023: 20 · 2022: 15 · 2021: 22 · 2020: 27 · 2019: 21 · 2018: 22 · 2017: 14 · 2016: 15 · 2015: 28 · 2014: 12 · 2013: 8 · 2012: 4
FWCI: 1.43
Type: book
Language: en
Open access: closed
Licence: www.cambridge.org/core/terms (unspecified, 313 d)
Locations: Cambridge University Press eBooks (publishedVersion)
CERN Document Server (European Organization for Nuclear Research) (submittedVersion)
Topics: Physical Sciences › Computer Science › Signal Processing › Digital Filter Design and Implementation
Physical Sciences › Mathematics › Applied Mathematics › Mathematical Analysis and Transform Methods
Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Data Compression Techniques
Keywords: fast algorithms, computational efficiency, energy consumption reduction, embedded systems, video processing, algorithm comparison

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

Fast Algorithms for Signal Processing

Abstract

Overview

Integrity signals

Verification

Claims the paper makes

Citations

Cites

Cited by

Related

Metadata

Record

About these checks