Multiplying Two Binary Numbers
I just encountered what I think is an interesting technique for multiplying two integer numbers. Perhaps some of the readers here will also find it interesting.
Here's the technique: assume we want to multiply 18 times 17. We start by writing 18 and 17, side-by-side in column A and column B, as shown at the top of Figure 1. Next we divide the 18 at the top of column A by two, retaining only the integer part of the division, and double the 17 at the top of column B. The results of those two...
"Neat" Rectangular to Polar Conversion Algorithm
The subject of finding algorithms that estimate the magnitude of a complex number, without having to perform one of those pesky square root operations, has been discussed many times in the past on the comp.dsp newsgroup. That is, given the complex number R + jI in rectangular notation, we want to estimate the magnitude of that number represented by M as:
On August 25th, 2009, Jerry (Mr. Wizard) Avins posted an interesting message on this subject to the comp.dsp newsgroup (Subject: "Re:
Improved Narrowband Lowpass IIR Filters
Here's a neat IIR filter trick. It's excerpted from the "DSP Tricks" chapter of the new 3rd edition of my book "Understanding Digital Signal Processing". Perhaps this trick will be of some value to the subscribers of dsprelated.com.
Due to their resistance to quantized-coefficient errors, traditional 2nd-order infinite impulse response (IIR) filters are the fundamental building blocks in computationally-efficient high-order IIR digital filter implementations. However, when used in...
Computing FFT Twiddle Factors
Some days ago I read a post on the comp.dsp newsgroup and, if I understood the poster's words, it seemed that the poster would benefit from knowing how to compute the twiddle factors of a radix-2 fast Fourier transform (FFT).
Then, later it occurred to me that it might be useful for this blog's readers to be aware of algorithms for computing FFT twiddle factors. So,... what follows are two algorithms showing how to compute the individual twiddle factors of an N-point decimation-in-frequency...
Computing an FFT of Complex-Valued Data Using a Real-Only FFT Algorithm
Someone recently asked me if I knew of a way to compute a fast Fourier transform (FFT) of complex-valued input samples using an FFT algorithm that accepts only real-valued input data. Knowing of no way to do this, I rifled through my library of hardcopy FFT articles looking for help. I found nothing useful that could be applied to this problem.
After some thinking, I believe I have a solution to this problem. Here is my idea:
Let's say our original input data is the complex-valued sequence...
Some Thoughts on a German Mathematician
Carl Friedrich Gauss
Here are a few interesting facts about the great Carl Friedrich Gauss (1777-1855), considered by some historians to have been the world's greatest mathematician. The overused phrase of "genius" could, with full justification, be used to describe this man. (How many people do you know that could have discovered the law of quadratic reciprocity in number theory at the age seventeen years?) Gauss was so prolific that by some estimates he personally doubled the amount of...
Using Mason's Rule to Analyze DSP Networks
There have been times when I wanted to determine the z-domain transfer function of some discrete network, but my algebra skills failed me. Some time ago I learned Mason's Rule, which helped me solve my problems. If you're willing to learn the steps in using Mason's Rule, it has the power of George Foreman's right hand in solving network analysis problems.
This blog discusses a valuable analysis method (well known to our analog control system engineering brethren) to obtain the z-domain...
Simultaneously Computing a Forward FFT and an Inverse FFT Using a Single FFT
Most of us are familiar with the processes of using a single N-point complex FFT to: (1) perform a 2N-point FFT on real data, and (2) perform two independent N-point FFTs on real data [1–5]. In case it's of interest to someone out there, this blog gives the algorithm for simultaneously computing a forward FFT and an inverse FFT using a single radix-2 FFT.
Our algorithm is depicted by the seven steps, S1 through S7, shown in Figure 1. In that figure, we compute the x(n) inverse FFT of...
Multiplierless Exponential Averaging
This blog discusses an interesting approach to exponential averaging. To begin my story, a traditional exponential averager (also called a "leaky integrator"), shown in Figure 1(a), is commonly used to reduce noise fluctuations that contaminate relatively constant-amplitude signal measurements.
Figure 1 Exponential averaging: (a) standard network; (b) single-multiply network.That exponential averager's difference equation is
y(n) = αx(n) + (1 –...Free DSP Books on the Internet - Part Deux
Since Stephane Boucher posted my "Free DSP Books on the Internet" blog here in February 2008, I have learned of additional books on the Internet that are related to signal processing. I list those books below. Again, the listed books are copyrighted. The books' copyright holders have graciously provided their books free of charge for downloading for individual use, but multiple copies must not be made or printed. As such, be aware that using any of these books as promotional material is...
Computing an FFT of Complex-Valued Data Using a Real-Only FFT Algorithm
Someone recently asked me if I knew of a way to compute a fast Fourier transform (FFT) of complex-valued input samples using an FFT algorithm that accepts only real-valued input data. Knowing of no way to do this, I rifled through my library of hardcopy FFT articles looking for help. I found nothing useful that could be applied to this problem.
After some thinking, I believe I have a solution to this problem. Here is my idea:
Let's say our original input data is the complex-valued sequence...
Improved Narrowband Lowpass IIR Filters
Here's a neat IIR filter trick. It's excerpted from the "DSP Tricks" chapter of the new 3rd edition of my book "Understanding Digital Signal Processing". Perhaps this trick will be of some value to the subscribers of dsprelated.com.
Due to their resistance to quantized-coefficient errors, traditional 2nd-order infinite impulse response (IIR) filters are the fundamental building blocks in computationally-efficient high-order IIR digital filter implementations. However, when used in...
Multiplying Two Binary Numbers
I just encountered what I think is an interesting technique for multiplying two integer numbers. Perhaps some of the readers here will also find it interesting.
Here's the technique: assume we want to multiply 18 times 17. We start by writing 18 and 17, side-by-side in column A and column B, as shown at the top of Figure 1. Next we divide the 18 at the top of column A by two, retaining only the integer part of the division, and double the 17 at the top of column B. The results of those two...
Coupled-Form 2nd-Order IIR Resonators: A Contradiction Resolved
This blog clarifies how to obtain and interpret the z-domain transfer function of the coupled-form 2nd-order IIR resonator. The coupled-form 2nd-order IIR resonator was developed to overcome a shortcoming in the standard 2nd-order IIR resonator. With that thought in mind, let's take a brief look at a standard 2nd-order IIR resonator.
Standard 2nd-Order IIR Resonator A block diagram of the standard 2nd-order IIR resonator is shown in Figure 1(a). You've probably seen that block diagram many...
"Neat" Rectangular to Polar Conversion Algorithm
The subject of finding algorithms that estimate the magnitude of a complex number, without having to perform one of those pesky square root operations, has been discussed many times in the past on the comp.dsp newsgroup. That is, given the complex number R + jI in rectangular notation, we want to estimate the magnitude of that number represented by M as:
On August 25th, 2009, Jerry (Mr. Wizard) Avins posted an interesting message on this subject to the comp.dsp newsgroup (Subject: "Re:
Looking For a Second Toolbox? This One's For Sale
In case you're looking for a second toolbox, this used toolbox is for sale.The blue-enameled steel toolbox measures 13 x 7 x 5 inches and, when opened, has a three-section tray attached to the lid. Showing signs of heavy use, the interior, tray, and exterior have collected a fair amount of dirt and grease and bear many scratches. The bottom of the box is worn from having been slid on rough surfaces.
The toolbox currently resides in Italy. But don't worry, it can be shipped to you....
Above-Average Smoothing of Impulsive Noise
In this blog I show a neat noise reduction scheme that has the high-frequency noise reduction behavior of a traditional moving average process but with much better impulsive-noise suppression.
In practice we may be required to make precise measurements in the presence of highly-impulsive noise. Without some sort of analog signal conditioning, or digital signal processing, it can be difficult to obtain stable and repeatable, measurements. This impulsive-noise smoothing trick,...
Specifying the Maximum Amplifier Noise When Driving an ADC
I recently learned an interesting rule of thumb regarding the use of an amplifier to drive the input of an analog to digital converter (ADC). The rule of thumb describes how to specify the maximum allowable noise power of the amplifier [1].
The Problem Here's the situation for an ADC whose maximum analog input voltage range is –VRef to +VRef. If we drive an ADC's analog input with an sine wave whose peak amplitude is VP = VRef, the ADC's output signal to noise ratio is maximized. We'll...
A Useful Source of Signal Processing Information
I just discovered a useful web-based source of signal processing information that was new to me. I thought I'd share what I learned with the subscribers here on DSPRelated.com.
The Home page of the web site that I found doesn't look at all like it would be useful to us DSP fanatics. But if you enter some signal processing topic of interest, say, "FM demodulation" (without the quotation marks) into the 'Search' box at the top of the web page
and click the red 'SEARCH...
Implementing Impractical Digital Filters
This blog discusses a problematic situation that can arise when we try to implement certain digital filters. Occasionally in the literature of DSP we encounter impractical digital IIR filter block diagrams, and by impractical I mean block diagrams that cannot be implemented. This blog gives examples of impractical digital IIR filters and what can be done to make them practical.
Implementing an Impractical Filter: Example 1
Reference [1] presented the digital IIR bandpass filter...
A New Contender in the Digital Differentiator Race
This blog proposes a novel differentiator worth your consideration. Although simple, the differentiator provides a fairly wide 'frequency range of linear operation' and can be implemented, if need be, without performing numerical multiplications.
BackgroundIn reference [1] I presented a computationally-efficient tapped-delay line digital differentiator whose $h_{ref}(k)$ impulse response is:
$$ h_{ref}(k) = {-1/16}, \ 0, \ 1, \ 0, \ {-1}, \ 0, \ 1/16 \tag{1} $$and...
Above-Average Smoothing of Impulsive Noise
In this blog I show a neat noise reduction scheme that has the high-frequency noise reduction behavior of a traditional moving average process but with much better impulsive-noise suppression.
In practice we may be required to make precise measurements in the presence of highly-impulsive noise. Without some sort of analog signal conditioning, or digital signal processing, it can be difficult to obtain stable and repeatable, measurements. This impulsive-noise smoothing trick,...
Implementing Simultaneous Digital Differentiation, Hilbert Transformation, and Half-Band Filtering
Recently I've been thinking about digital differentiator and Hilbert transformer implementations and I've developed a processing scheme that may be of interest to the readers here on dsprelated.com.
This blog presents a novel method for simultaneously implementing a digital differentiator (DD), a Hilbert transformer (HT), and a half-band lowpass filter (HBF) using a single tapped-delay line and a single set of coefficients. The method is based on the similarities of the three N =...
A Complex Variable Detective Story – A Disconnect Between Theory and Implementation
Recently I was in the middle of a pencil-and-paper analysis of a digital 5-tap FIR filter having complex-valued coefficients and I encountered a surprising and thought-provoking problem. So that you can avoid the algebra difficulty I encountered, please read on.
A Surprising Algebra Puzzle
I wanted to derive the H(ω) equation for the frequency response of my FIR digital filter whose complex coefficients were h0, h1, h2, h3, and h4. I could then test the validity of my H(ω)...
Online DSP Classes: Why Such a High Dropout Rate?
Last year the IEEE Signal Processing Magazine published a lengthy article describing three university-sponsored online digital signal processing (DSP) courses [1]. The article detailed all the effort the professors expended in creating those courses and the courses' perceived values to students.
However, one fact that struck me as important, but not thoroughly addressed in the article, was the shocking dropout rate of those online courses. For two of the courses the article's...
Handy Online Simulation Tool Models Aliasing With Lowpass and Bandpass Sampling
Analog Devices Inc. has posted a neat software simulation tool on their corporate web site that graphically shows the aliasing effects of both lowpass and bandpass periodic sampling. This is a nice tutorial tool for beginners in DSP.
The tool shows four important characteristics of periodic sampling:
Characteristic# 1: All input analog spectral components, regardless of their center frequencies, show up (appear) below half the sample rate in the digitized...An Efficient Linear Interpolation Scheme
This blog presents a computationally-efficient linear interpolation trick that requires at most one multiply per output sample.
Background: Linear Interpolation
Looking at Figure 1(a) let's assume we have two points, [x(0),y(0)] and [x(1),y(1)], and we want to compute the value y, on the line joining those two points, associated with the value x.
Figure 1: Linear interpolation: given x, x(0), x(1), y(0), and y(1), compute the value of y. ...
Computing an FFT of Complex-Valued Data Using a Real-Only FFT Algorithm
Someone recently asked me if I knew of a way to compute a fast Fourier transform (FFT) of complex-valued input samples using an FFT algorithm that accepts only real-valued input data. Knowing of no way to do this, I rifled through my library of hardcopy FFT articles looking for help. I found nothing useful that could be applied to this problem.
After some thinking, I believe I have a solution to this problem. Here is my idea:
Let's say our original input data is the complex-valued sequence...
Complex Down-Conversion Amplitude Loss
This blog illustrates the signal amplitude loss inherent in a traditional complex down-conversion system. (In the literature of signal processing, complex down-conversion is also called "quadrature demodulation.")
The general idea behind complex down-conversion is shown in Figure 1(a). And the traditional hardware block diagram of a complex down-converter is shown in Figure 1(b).
Let's assume the input to our down-conversion system is an analog radio frequency (RF) signal,...
Simultaneously Computing a Forward FFT and an Inverse FFT Using a Single FFT
Most of us are familiar with the processes of using a single N-point complex FFT to: (1) perform a 2N-point FFT on real data, and (2) perform two independent N-point FFTs on real data [1–5]. In case it's of interest to someone out there, this blog gives the algorithm for simultaneously computing a forward FFT and an inverse FFT using a single radix-2 FFT.
Our algorithm is depicted by the seven steps, S1 through S7, shown in Figure 1. In that figure, we compute the x(n) inverse FFT of...
