Tweets by @dsprelated

A Quadrature Signals Tutorial: Complex, But Not Complicated

Understanding the 'Phasing Method' of Single Sideband Demodulation

Complex Digital Signal Processing in Telecommunications

Introduction to Sound Processing

Introduction of C Programming for DSP Applications

Richard Lyons is a Contracting Systems Engineer and Lecturer at Besser Associates, Mountain View, Calif. He has written over 30 articles and conference papers on DSP top...show full bio

**Would you like to be notified by email when Rick Lyons publishes a new blog?**

Follow @DSPRelated

I have read, in some of the literature of DSP, that when the discrete Fourier transform (DFT) is used as a filter the process of performing a DFT causes an input signal's spectrum to be frequency translated down to zero Hz (DC). I can understand why someone might say that, but I challenge that statement as being incorrect. Here are my thoughts.

**Using the DFT as a Filter**

It may seem strange to think of the DFT as being used as a filter but there are a number of applications where this is done. For example, we can use the DFT to implement a bank of bandpass filters used in some sort of subband coding application, or use the DFT to implement a bank of bandpass filters for a straightforward spectrum analysis application such as a weighted overlap and add (WOLA) spectrum analyzer [1-5].

The general process of using the DFT as a filter is illustrated in Figure 1. An *N*-sample *x*(*n*) input sequence enters a tapped-delay line, is multiplied by a *w*(*k*) window sequence, and the *u*(*n*) product sequence is applied to an *N*-point DFT. Windowing with a *w*(*k*) sequence is optional, based on the our DFT filterbank application. For “rectangular windowing” the *w*(*k*) window sequence would be all ones and the multiplication by the *w*(*k*) sequence in Figure 1 becomes unnecessary.

If the *w*(*k*) window sequence is all ones, as each new *x*(*n*) sample enters the tapped-delay line we compute a new output sample for each of the DFT's *X*_{m}(*n*) output sequences. The subscripted *m* index in *X*_{m}(*n*) represents the *m*th DFT bin where *m* is in the range 0 ≤ *m* ≤ *N*-1. Looking at the *m* = 2 DFT bin, inside the oval of Figure 1 shows a hypothetical, complex-valued, *X*_{2}(*n*) time-domain output sequence.

In viewing the computation of a single DFT bin output as the output of a tapped-delay line finite impulse response (FIR) filter, we can show the Figure 1 *u*(*n*) sequence as the input to an *N*-point DFT, as shown in Figure 2. The dashed rectangle in Figure 2 shows the computations needed to compute a single *m*th bin output sequence *X*_{m}(*n*).

**An Easy Mistake to Make**

Again, the misconception I referred to at the beginning of this blog, regarding the use of the DFT as a filterbank of bandpass filters as shown in Figure 1 or as a single bandpass filter as shown in Figure 2, is that when used as a filter the DFT translates spectral energy down in frequency such that all of the DFT's *m*th bin output signals are centered at zero Hz (DC). I believe this is not true, and here's why:

You see, when implementing the standard *N*-point DFT equation,

we're correlating the e^{-j2πpm/N} twiddle factors with an *x*(*n*) input sequence. In an FIR implementation we're convolving the e^{-j2πpm/N} twiddle factors with an *x*(*n*) input sequence, and that means from an FIR filter viewpoint the order of the e^{-j2πpm/N} twiddle factor coefficients must be flipped relative to their order in a standard DFT. Figure 2 illustrates what I'm saying here. Notice in Figure 2 how the largest DFT twiddle factor coefficient e^{-j2π⋅(N-1)⋅m/N} is on the left side, and the smallest twiddle factor coefficient e^{-j2π⋅0⋅m/N} is on the right side, of Figure 2's tapped-delay line.

I've seen two Internet DSP tutorial websites, as well as a recently-published DSP textbook, that had the twiddle factors incorrectly reversed in order when the authors were discussing using the DFT as a filter. That is, they mistakenly had the e^{-j2π⋅0⋅m/N} twiddle factor coefficient on the left side of the tapped-delay line, ...and that's a VERY easy mistake to make. (I don't know if the Professor on Gilligan's Island or Sheldon Cooper on THE BIG BANG THEORY would make that mistake, but some people do.)

The critical point here is that the DFT twiddle factors in Eq. (1) comprise a negative-frequency complex exponential, while the twiddle factor coefficients in Figure 2 comprise a positive-frequency complex exponential.

Improper ordering of the DFT twiddle factors, when trying to perform a mathematical analysis of the Figure 2 FIR filter, leads to an incorrect equation for the frequency response of the DFT's *m*th bin FIR filter.

**The Frequency Response of the DFT's mth Bin**

As derived in the Appendix A, the frequency response of the

where frequency variable ω is –π ≤ ω ≤ π measured in radians/sample. The |*H*_{DFT}(ω)| magnitude response of *H*_{DFT}(ω) is a sin(x)/x-like bandpass filter response centered at a frequency of:

That ω_{cntr} center frequency is the value of ω where the angle argument of the ratio's denominator equals zero in Eq. (2). The spectral magnitude |*H*_{DFT}(ω)| for *N* = 16 and *m* = 4 is shown in Figure 3(a). There we see that the main lobe of |*H*_{DFT}(ω)| is located at a frequency of ω_{cntr} = 2π4/16 = 0.5π radians/sample (one fourth of the input signal's sample rate measured in Hz). The linear phase response of this example *H*_{DFT}(ω)'s passband is given in Figure 3(b).

Figure 3(a) illustrates why we can treat consecutive time-domain output samples of a DFT's *m*th bin as the output of a complex bandpass filter.

**A Simple Example**

Figure 4 shows a simple example of how the DFT, used as a filter, does not induce frequency translation as some people claim. Figure 4(a) shows a sinusoidal *u*(*n*) input sequence whose frequency is *f*_{s}/16, where *f*_{s} is the *u*(*n*) sample rate is Hz. (There are 16 samples/cycle in *u*(*n*)). A block of *N* = 128 samples of sequence *u*(*n*) contains exactly eight sinusoidal cycles. The complex *X*_{8}(*n*) output of a 128-point DFT's *m* = 8 bin is shown in Figure 4(b). Each complex

*X*_{8}(*n*) = Real[*X*_{8}(*n*)] + *j*Imag[*X*_{8}(*n*)]

sample in Figure 4(b) represents the output of the *m* = 8th bin of consecutive 128-point DFTs.

Notice how the real and imaginary parts of *X*_{8}(*n*) also contain 16 samples/cycle, as did the *u*(*n*) input sequence. NO frequency translation occurs in the DFT's *X*_{8}(*n*) bin time-domain output sequence!

**Here's Where Frequency Translation Can Occur**

In some applications of the DFT used as a filterbank, a frequency down-conversion does occur. Because Figure 2's *X*_{m}(*n*) output sequence is narrow in bandwidth relative to the bandwidth of the input *u*(*n*) sequence, some DFT filterbank practitioners decimate the *X*_{m}(*n*) sequence by *N* as shown in Figure 5. That decimation process frequency translates a DFT bin's *X*_{m}(*n*) spectral energy, originally centered at 2π*m*/*N* radians/sample, to be centered at zero Hz (DC).

The decimated-by-*N* *X*_{m,dec}(*r*) sequence in Figure 5 is:

and the output index *r* is *r* = 0,1,2,3,…. For example, the *u*(*n*) input sequence in Figure 4(a) is a sinusoid whose frequency is centered exactly at the *m* = 8 bin. If that *u*(*n*) sequence had been thousands of samples in length, decimating the real and imaginary parts of *X*_{8}(*n*) by *N* = 128 produces an all-ones sequence and an all-zeros sequence, respectively. If a lengthy *u*(*n*) sequence's frequency had been ±Δ radians/sample above or below the *m* = 8 bin's center frequency, the decimated complex X8,dec(r) sequence would have a frequency of ±Δ radians/sample.

The interesting thing about the ʹfrequency translation through decimation by *N*ʹ process, shown in Figure 6, is that the spectral energy in any *X*_{m}(*n*) sequence is frequency translated to be centered at zero Hz regardless of the value of *m*. The top panel of Figure 6 shows the frequency translation if *m* is a positive integer. The bottom panel of Figure 6 shows the frequency translation if *m* is a negative integer.

**Conclusion**

To recap the main points of this blog we can say:

- Computing consecutive
*m*th bin output samples of an*N*-point DFT can be viewed as a tapped-delay line complex-valued FIR filter as shown in Figure 2. - The linear phase frequency response of the DFT's
*m*th bin filter is sin(x)/x-like passband centered at 2π*m*/*N*radians/sample (*m**f*_{s}/*N*Hz). - When a new
*m*th bin output sample is computed, upon the arrival of each new delay line input sample, the DFT's*m*th bin output sequence exhibits no frequency translation.

I end this blog by pointing out that what I haven't yet figured out is “How can the Figure 2 FIR bandpass filter have linear phase when its coefficients are not symmetrical?”

**References**

[1] Lyons, R. Understanding Digital Signal Processing, 2nd Ed. & 3rd Ed., Prentice Hall Publishing, Hoboken, NJ, 2010, Chap. 13, Section 13.20.

[2] Crochiere, R., and Rabiner, L. Multirate Digital Signal Processing, Prentice Hall, Englewood Cliffs, NJ, 1983 pp. 315-319.

[3] http://www.rfel.com/download/W05012_Architectures_for_SDR_Channelisation.pdf

[4] http://www.onsemi.com/pub_link/Collateral/AND8382-D.PDF

[5] http://www.onsemi.cn/site/pdf/ICECS2003_ASR.pdf

**Appendix A [Derivation of Eq. (2)]**

We can determine the frequency response of the *m*th bin of an *N*-point DFT by treating the Figure 2 block diagram as a simple tapped-delay line finite impulse response (FIR) filter. Doing so we see that the coefficients of the Figure 2 FIR filter are:

where time index *p* is 0 ≤ *p* ≤ *N*-1. Because e^{-j2πmN/N} = 1, we can simplify Eq. (A-1) as:

Next we use the discrete-time Fourier transform (DTFT) definition to find the *H*_{DFT}(ω) frequency response of the *h*_{DFT}(*p*) coefficients as:

where frequency variable ω is –π ≤ ω ≤ π measured in radians/sample. The summation in Eq. (A-3) is a geometric series, so we can set Eq. (A-3) equal to:

Because e^{j2πm} =1, we have:

Factoring out the half-angled exponentials e^{-jNω/2} and e^{j(πm/N-ω/2)}, we have:

Using Euler's identity, e^{jα} - e^{-jα} = 2*j*sin(α), we arrive at

Canceling common factors and rearranging terms, the frequency response of our *N*-point DFT's *m*th bin bandpass filter is:

Richard Lyons is a Contracting Systems Engineer and Lecturer at Besser Associates, Mountain View, Calif. He has written over 30 articles and conference papers on DSP topics, and authored Amazon.com's top selling DSP book "Understanding Digital Signal Processing, 3rd Ed.". He served as an Associate Editor at IEEE Signal Processing Magazine, for nine years, where he created and edited the "DSP Tips & Tricks" column. Lyons is the editor of, and contributor to, the book "Streamlining Digital Signal Processing-A Tricks of the Trade Guidebook, 2nd Ed." (Wiley & Sons, 2012).

Previous post by Rick Lyons:

Next post by Rick Lyons:

Comments / Replies

dszabo

Said:

The DFT is symetrical about N/2.

2 years ago

+1

Sorry, you need javascript enabled to post any comments.

dszabo

Said:

I apologize if it came off pithy, I am a huge fan of your articles and enjoy your book on DSP very much!

I just picture it in my head. The real part of an FIR filter based on the DFT would look like a rectangular window with an integer number of cosine waves. The imaginary part would have an integer number of sine waves. The midway point would have even real symetry odd imaginary symetry. This would mean the filter has a linear phase response.

It can be shown mathematically by expressing the coefficients in rectagular form using cosine and sine and noting that cosine has even symetry about integer multiples of pi and sine has odd symetry about integer multiples of pi.

Thanks for all your great articles! They have really helped me gain insight into the world of DSP.

-Dan

I just picture it in my head. The real part of an FIR filter based on the DFT would look like a rectangular window with an integer number of cosine waves. The imaginary part would have an integer number of sine waves. The midway point would have even real symetry odd imaginary symetry. This would mean the filter has a linear phase response.

It can be shown mathematically by expressing the coefficients in rectagular form using cosine and sine and noting that cosine has even symetry about integer multiples of pi and sine has odd symetry about integer multiples of pi.

Thanks for all your great articles! They have really helped me gain insight into the world of DSP.

-Dan

Sorry, you need javascript enabled to post any comments.

cfelton

Said:

Rick,

Thanks for another great post. For a couple years I had

the fortune to work with the group that generated

references [4] and [5]. I was working for a hearing-aid

company that was internally developing their own WOLA

until our R&D design site was sold to the group that

generated the aforementioned references.

As it is with many semiconductor and high-tech, there was

numerous selling of divisions, consolidations, etc. The

design group I was part of is no longer around, vanished

into the design center oblivion. But they were some good

years while it lasted.

Thanks for another great post. For a couple years I had

the fortune to work with the group that generated

references [4] and [5]. I was working for a hearing-aid

company that was internally developing their own WOLA

until our R&D design site was sold to the group that

generated the aforementioned references.

As it is with many semiconductor and high-tech, there was

numerous selling of divisions, consolidations, etc. The

design group I was part of is no longer around, vanished

into the design center oblivion. But they were some good

years while it lasted.

Sorry, you need javascript enabled to post any comments.

HLK1970

Said:

Hi Rick

“How can the Figure 2 FIR bandpass filter have linear phase when its coefficients are not symmetrical?”

Here are my thoughts, for what they are worth ...

In Figure 2 you have plotted the real and imag parts of the impulse response for a single DFT bin. In the "real world" we would implement a pair of frequency bins, centered on zero. The complex sinusoids corresponding to each bin would have the same frequency, but they would be complex conjugates of each other. When the coefficients of the two DFT filter bins are summed, the imaginary parts cancel, leaving the real part, which would be symmetric around the middle of the analysis window (if there are an odd number of taps).

“How can the Figure 2 FIR bandpass filter have linear phase when its coefficients are not symmetrical?”

Here are my thoughts, for what they are worth ...

In Figure 2 you have plotted the real and imag parts of the impulse response for a single DFT bin. In the "real world" we would implement a pair of frequency bins, centered on zero. The complex sinusoids corresponding to each bin would have the same frequency, but they would be complex conjugates of each other. When the coefficients of the two DFT filter bins are summed, the imaginary parts cancel, leaving the real part, which would be symmetric around the middle of the analysis window (if there are an odd number of taps).

Sorry, you need javascript enabled to post any comments.

Rick Lyons

Said:

Hi HLK1970. You wrote:

“How can the Figure 2 FIR bandpass filter have linear phase

when its coefficients are not symmetrical?”

THAT(!) …is the question. And I’ve asked myself that question many times.

HLK1970, do you have access to Oppenheim’s & Schafer’s DSP book? In their first edition, Figure 3.32(c), they show real-valued asymmetrical coefficients of a nonrecursive FIR filter that they claim is linear phase. (That figure is Figure 3.35(c) in their 2nd edition). Weird huh, real-valued asymmetrical coefficients having linear phase. The problem is, I’m unable to model that FIR filter and obtain linear phase as they claim. I’d be interested in what happens if you, HLK1970, try to model that filter.

HLK1970, you wrote,

“In Figure 2 you have plotted the real and imag parts

of the impulse response for a single DFT bin.”

Nope, my Figure 2 is a block diagram. I didn’t provide any impulse response plots in my blog.

You wrote:

“In the "real world" we would implement a pair of frequency

bins, centered on zero.”

I’m not sure what is a “pair of frequency bins centered at zero.” Are you talking about the DFT’s zero-Hz bin (DC bin)? How can you have two bins centered at zero?

[-Rick-]

“How can the Figure 2 FIR bandpass filter have linear phase

when its coefficients are not symmetrical?”

THAT(!) …is the question. And I’ve asked myself that question many times.

HLK1970, do you have access to Oppenheim’s & Schafer’s DSP book? In their first edition, Figure 3.32(c), they show real-valued asymmetrical coefficients of a nonrecursive FIR filter that they claim is linear phase. (That figure is Figure 3.35(c) in their 2nd edition). Weird huh, real-valued asymmetrical coefficients having linear phase. The problem is, I’m unable to model that FIR filter and obtain linear phase as they claim. I’d be interested in what happens if you, HLK1970, try to model that filter.

HLK1970, you wrote,

“In Figure 2 you have plotted the real and imag parts

of the impulse response for a single DFT bin.”

Nope, my Figure 2 is a block diagram. I didn’t provide any impulse response plots in my blog.

You wrote:

“In the "real world" we would implement a pair of frequency

bins, centered on zero.”

I’m not sure what is a “pair of frequency bins centered at zero.” Are you talking about the DFT’s zero-Hz bin (DC bin)? How can you have two bins centered at zero?

[-Rick-]

Sorry, you need javascript enabled to post any comments.

HLK1970

Replied:

Hi Rick

By "a pair of frequency bins centred on zero" I meant that if you are interested in the mth frequency bin, with a relative frequency of m/N cycles per sample (using your symbols from your fig 2) then, as you are using complex math, you would need to actually apply two filters in parallel for this frequency - one at +m/N, and its complex conjugate partner at -m/N. When their outputs are summed the imaginary part cancels. In your fig 2 you only have the +m/M bin.

I probably should have written "symmetric around zero".

Regards,

HLK

By "a pair of frequency bins centred on zero" I meant that if you are interested in the mth frequency bin, with a relative frequency of m/N cycles per sample (using your symbols from your fig 2) then, as you are using complex math, you would need to actually apply two filters in parallel for this frequency - one at +m/N, and its complex conjugate partner at -m/N. When their outputs are summed the imaginary part cancels. In your fig 2 you only have the +m/M bin.

I probably should have written "symmetric around zero".

Regards,

HLK

HLK1970

Replied:

Hi Rick

Did you mean O&S's 1975 "Digital Signal Processing" book? I couldn't find a figure 3.32 in there.

Regards,

HLK

Did you mean O&S's 1975 "Digital Signal Processing" book? I couldn't find a figure 3.32 in there.

Regards,

HLK

Rick Lyons

Said:

Hi HLK,

Reading your last two posts, it seems to me that the “real world” process you’re referring to is equivalent to some sort of real-valued bandpass filter. But that’s not the process in my Figure 2. My Figure 2 refers to performing consecutive DFTs. That is, perform one DFT each time a new u(n) input sample arrives at the input of the tapped delay line in my Figure 2, and then examine the consecutive output samples of a single Xm(n) DFT bin.

Regarding my reference to O&S’s DSP book, forgive me for not being more specific. I meant the 1st and 2nd editions of their “Discrete-Time Signal Processing” book. (Not their 1975 “Digital Signal Processing” book.) Again HLK, I’d be tickled if you could take a look at their “Discrete-Time Signal Processing” 1st edition’s Figure 3.32(c) [or their 2nd edition’s equivalent Figure 3.35(c)] and see if you’re able to duplicate what they claim are real-valued, asymmetrical, tapped-delay line FIR filter coefficients that exhibit linear phase. For the life of me I wasn’t able to duplicate what they claimed were their linear-phase results.

I welcome further discussion.

See Ya’,

[-Rick-]

Reading your last two posts, it seems to me that the “real world” process you’re referring to is equivalent to some sort of real-valued bandpass filter. But that’s not the process in my Figure 2. My Figure 2 refers to performing consecutive DFTs. That is, perform one DFT each time a new u(n) input sample arrives at the input of the tapped delay line in my Figure 2, and then examine the consecutive output samples of a single Xm(n) DFT bin.

Regarding my reference to O&S’s DSP book, forgive me for not being more specific. I meant the 1st and 2nd editions of their “Discrete-Time Signal Processing” book. (Not their 1975 “Digital Signal Processing” book.) Again HLK, I’d be tickled if you could take a look at their “Discrete-Time Signal Processing” 1st edition’s Figure 3.32(c) [or their 2nd edition’s equivalent Figure 3.35(c)] and see if you’re able to duplicate what they claim are real-valued, asymmetrical, tapped-delay line FIR filter coefficients that exhibit linear phase. For the life of me I wasn’t able to duplicate what they claimed were their linear-phase results.

I welcome further discussion.

See Ya’,

[-Rick-]

Sorry, you need javascript enabled to post any comments.

Alen Docef

Said:

Rick,

I know this is old, but it seems nobody commented on your question about the O&S linear phase example. I am looking at the second edition (this one: http://www.amazon.com/Discrete-Time-Signal-Processing-2nd-Prentice-Hall/dp/0137549202/). You may be referring to Figure 5.35, on page 294.

Although only 19 samples are plotted in that figure, h[n] is infinite in duration. When you say you were not able to replicate the "linear phase" claim, did you maybe truncate h[n]? If you did truncate, that probably made the filter non-linear-phase. This is why symmetric filters are useful; they preserve linear phase when a window (rectangular or otherwise, but symmetric) is applied. This is not the case with non-symmetric filters. O&S briefly refer to this in section 5.7.3. when they say that the symmetry conditions are sufficient, but not necessary, for linear phase.

Cheers,

Alen

I know this is old, but it seems nobody commented on your question about the O&S linear phase example. I am looking at the second edition (this one: http://www.amazon.com/Discrete-Time-Signal-Processing-2nd-Prentice-Hall/dp/0137549202/). You may be referring to Figure 5.35, on page 294.

Although only 19 samples are plotted in that figure, h[n] is infinite in duration. When you say you were not able to replicate the "linear phase" claim, did you maybe truncate h[n]? If you did truncate, that probably made the filter non-linear-phase. This is why symmetric filters are useful; they preserve linear phase when a window (rectangular or otherwise, but symmetric) is applied. This is not the case with non-symmetric filters. O&S briefly refer to this in section 5.7.3. when they say that the symmetry conditions are sufficient, but not necessary, for linear phase.

Cheers,

Alen

Sorry, you need javascript enabled to post any comments.

Sorry, you need javascript enabled to post any comments.