## Do Multirate Systems Have Transfer Functions?

The following text describes why I ask the strange question in the title of this blog. Some months ago I was asked to review a article manuscript, for possible publication in a signal processing journal, that presented a method for improving the performance of cascaded integrator-comb (CIC) decimation filters [1].

Thinking about such filters, Figure 1(a) shows the block diagram of a traditional 2nd-order CIC decimation filter followed by downsampling by the sample rate factor R. There we...

## 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 –...## Reducing IIR Filter Computational Workload

This blog describes a straightforward method to significantly reduce the number of necessary multiplies per input sample of traditional IIR lowpass and highpass digital filters.

Reducing IIR Filter Computations Using Dual-Path Allpass Filters

We can improve the computational speed of a lowpass or highpass IIR filter by converting that filter into a dual-path filter consisting of allpass filters as shown in Figure 1.

...## Microprocessor Family Tree

Below is a little microprocessor history. Perhaps some of the ol' timers here will recognize a few of these integrated circuits. I have a special place in my heart for the Intel 8080 chip.

Image copied, without permission, from the now defunct Creative Computing magazine, Vol. 11, No. 6, June 1985.

## Controlling a DSP Network's Gain: A Note For DSP Beginners

This blog briefly discusses a topic well-known to experienced DSP practitioners but may not be so well-known to DSP beginners. The topic is the proper way to control a digital network's gain. Digital Network Gain Control Figure 1 shows a collection of networks I've seen, in the literature of DSP, where strict gain control is implemented.

FIGURE 1. Examples of digital networks whose initial operations are input signal...

## Is It True That *j* is Equal to the Square Root of -1 ?

A few days ago, on the YouTube.com web site, I watched an interesting video concerning complex numbers and the j operator. The video's author claimed that the statement "j is equal to the square root of negative one" is incorrect. What he said was:

He justified his claim by going through the following exercise, starting with:

Based on the algebraic identity:

the author rewrites Eq. (1) as:

If we assume

Eq. (3) can be rewritten...

## The Swiss Army Knife of Digital Networks

This blog describes a general discrete-signal network that appears, in various forms, inside so many DSP applications.

Figure 1 shows how the network's structure has the distinct look of a digital filter—a comb filter followed by a 2nd-order recursive network. However, I do not call this useful network a filter because its capabilities extend far beyond simple filtering. Through a series of examples I've illustrated the fundamental strength of this Swiss Army Knife of digital networks...

## The Risk In Using Frequency Domain Curves To Evaluate Digital Integrator Performance

This blog shows the danger in evaluating the performance of a digital integration network based solely on its frequency response curve. If you plan on implementing a digital integrator in your signal processing work I recommend you continue reading this blog.

Background

Typically when DSP practitioners want to predict the accuracy performance of a digital integrator they compare how closely that integrator's frequency response matches the frequency response of an ideal integrator [1,2]....

## The Real Star of Star Trek

Unless you've been living under a rock recently, you're probably aware that this month is the 50-year anniversary of the original Star Trek show on American television. It's an anniversary worth noting, as did Time and Newsweek magazines with their special editions.

Over the years I've come to realize that a major star of the original Star Trek series wasn't an actor. It was a thing. The starship USS Enterprise! Before I explain my thinking, here's a little...

## 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...

## A Wide-Notch Comb Filter

This blog describes a linear-phase comb filter having wider stopband notches than a traditional comb filter.

Background

Let's first review the behavior of a traditional comb filter. Figure 1(a) shows a traditional comb filter comprising two cascaded recursive running sum (RRS) comb filters. Figure 1(b) shows the filter's co-located dual poles and dual zeros on the z-plane, while Figure 1(c) shows the filter's positive-frequency magnitude response when, for example, D = 9. The...## The Little Fruit Market: The Beginning of the Digital Explosion

There used to be a fruit market located at 391 San Antonio Road in Mountain View, California. In the 1990's I worked part time in Mountain View and drove past this market's building, shown in Figure 1, many times, unaware of its history. What happened at that fruit market has changed the lives of almost everyone on our planet. Here's the story.

William Shockley In 1948 the brilliant physicist William Shockley, along with John Bardeen and Walter Brattain, co-invented the transistor at Bell...

## Somewhat Off Topic: Deciphering Transistor Terminology

I recently learned something mildly interesting about transistors, so I thought I'd share my new knowledge with you folks. Figure 1 shows a p-n-p transistor comprising a small block of n-type semiconductor sandwiched between two blocks of p-type semiconductor.

The terminology of "emitter" and "collector" seems appropriate, but did you ever wonder why the semiconductor block in the center is called the "base"? The word base seems inappropriate because the definition of the word base is:...

## An Efficient Full-Band Sliding DFT Spectrum Analyzer

In this blog I present two computationally efficient full-band discrete Fourier transform (DFT) networks that compute the 0th bin and all the positive-frequency bin outputs for an N-point DFT in real-time on a sample-by-sample basis.

An Even-N Spectrum Analyzer

The full-band sliding DFT (SDFT) spectrum analyzer network, where the DFT size N is an even integer, is shown in Figure 1(a). The x[n] input sequence is restricted to be real-only valued samples. Notice that the only real parts of...

## A Fast Guaranteed-Stable Sliding DFT Algorithm

This blog presents a most computationally-efficient guaranteed-stable real-time sliding discrete Fourier transform (SDFT) algorithm. The phrase “real-time” means the network computes one spectral output sample, equal to a single-bin output of an N‑point discrete Fourier transform (DFT), for each input signal sample.

Proposed Guaranteed Stable SDFT

My proposed guaranteed stable SDFT, whose development is given in [1], is shown in Figure 1(a). The output sequence Xk(n) is an N-point...

## Controlling a DSP Network's Gain: A Note For DSP Beginners

This blog briefly discusses a topic well-known to experienced DSP practitioners but may not be so well-known to DSP beginners. The topic is the proper way to control a digital network's gain. Digital Network Gain Control Figure 1 shows a collection of networks I've seen, in the literature of DSP, where strict gain control is implemented.

FIGURE 1. Examples of digital networks whose initial operations are input signal...

## A Table of Digital Frequency Notation

When we read the literature of digital signal processing (DSP) we encounter a number of different, and equally valid, ways to algebraically represent the notion of frequency for discrete-time signals. (By frequency I mean a measure of angular repetitions per unit of time.)

The various mathematical expressions for sinusoidal signals use a number of different forms of a frequency variable and the units of measure (dimensions) of those variables are different. It's sometimes a nuisance to keep...

## The Risk In Using Frequency Domain Curves To Evaluate Digital Integrator Performance

This blog shows the danger in evaluating the performance of a digital integration network based solely on its frequency response curve. If you plan on implementing a digital integrator in your signal processing work I recommend you continue reading this blog.

Background

Typically when DSP practitioners want to predict the accuracy performance of a digital integrator they compare how closely that integrator's frequency response matches the frequency response of an ideal integrator [1,2]....

## A New Contender in the Quadrature Oscillator Race

This blog advocates a relatively new and interesting quadrature oscillator developed by A. David Levine in 2009 and independently by Martin Vicanek in 2015 [1]. That oscillator is shown in Figure 1.

The time domain equations describing the Figure 1 oscillator are

w(n) =...

## A Wide-Notch Comb Filter

This blog describes a linear-phase comb filter having wider stopband notches than a traditional comb filter.

Background

Let's first review the behavior of a traditional comb filter. Figure 1(a) shows a traditional comb filter comprising two cascaded recursive running sum (RRS) comb filters. Figure 1(b) shows the filter's co-located dual poles and dual zeros on the z-plane, while Figure 1(c) shows the filter's positive-frequency magnitude response when, for example, D = 9. The...## 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...

## 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(ω)...