Free Books
   Free Books    Mathematics of the DFT  

Shift Theorem


Theorem: For any $ x\in{\bf C}^N$ and any integer $ \Delta$,

$\displaystyle \zbox {\hbox{\sc DFT}_k[\hbox{\sc Shift}_\Delta(x)] = e^{-j\omega_k\Delta} X(k).} $


Proof:

\begin{eqnarray*} \hbox{\sc DFT}_k[\hbox{\sc Shift}_\Delta(x)] &\isdef & \sum_{n... ...}x(m) e^{-j 2\pi mk/N} \\ &\isdef & e^{-j \omega_k \Delta} X(k) \end{eqnarray*}

The shift theorem is often expressed in shorthand as

$\displaystyle \zbox {x(n-\Delta) \longleftrightarrow e^{-j\omega_k\Delta}X(\omega_k).} $

The shift theorem says that a delay in the time domain corresponds to a linear phase term in the frequency domain. More specifically, a delay of $ \Delta$ samples in the time waveform corresponds to the linear phase term $ e^{-j \omega_k \Delta}$ multiplying the spectrum, where $ \omega_k\isdeftext 2\pi k/N$.7.13Note that spectral magnitude is unaffected by a linear phase term. That is, $ \left\vert e^{-j \omega_k \Delta}X(k)\right\vert = \left\vert X(k)\right\vert$.

Linear Phase Terms

The reason $ e^{-j \omega_k \Delta}$ is called a linear phase term is that its phase is a linear function of frequency:

$\displaystyle \angle e^{-j \omega_k \Delta} = - \Delta \cdot \omega_k $

Thus, the slope of the phase, viewed as a linear function of radian-frequency $ \omega_k$, is $ -\Delta$. In general, the time delay in samples equals minus the slope of the linear phase term. If we express the original spectrum in polar form as

$\displaystyle X(k) = G(k) e^{j\Theta(k)}, $

where $ G$ and $ \Theta$ are the magnitude and phase of $ X$, respectively (both real), we can see that a linear phase term only modifies the spectral phase $ \Theta(k)$:

$\displaystyle e^{-j \omega_k \Delta} X(k) \isdef e^{-j \omega_k \Delta} G(k) e^{j\Theta(k)} = G(k) e^{j[\Theta(k)-\omega_k\Delta]} $

where $ \omega_k\isdeftext 2\pi k/N$. A positive time delay (waveform shift to the right) adds a negatively sloped linear phase to the original spectral phase. A negative time delay (waveform shift to the left) adds a positively sloped linear phase to the original spectral phase. If we seem to be belaboring this relationship, it is because it is one of the most useful in practice.

Linear Phase Signals

In practice, a signal may be said to be linear phase when its phase is of the form

$\displaystyle \Theta(\omega_k)= - \Delta \cdot \omega_k\pm \pi I(\omega_k), $

where $ \Delta$ is any real constant (usually an integer), and $ I(\omega_k)$ is an indicator function which takes on the values 0 or $ 1$ over the points $ \omega_k$, $ k=0,1,2,\ldots,N-1$. An important class of examples is when the signal is regarded as a filter impulse response.7.14 What all such signals have in common is that they are symmetric about the time $ n=\Delta$ in the time domain (as we will show on the next page). Thus, the term ``linear phase signal'' often really means ``a signal whose phase is linear between $ \pm\pi$ discontinuities.''

Zero Phase Signals

A zero-phase signal is thus a linear-phase signal for which the phase-slope $ \Delta$ is zero. As mentioned above (in §7.4.3), it would be more precise to say ``0-or-$ \pi $-phase signal'' instead of ``zero-phase signal''. Another better term is ``zero-centered signal'', since every real (even) spectrum corresponds to an even (real) signal. Of course, a zero-centered symmetric signal is simply an even signal, by definition. Thus, a ``zero-phase signal'' is more precisely termed an ``even signal''.

Application of the Shift Theorem to FFT Windows

In practical spectrum analysis, we most often use the Fast Fourier Transform7.15 (FFT) together with a window function $ w(n), n=0,1,2,\ldots,N-1$. As discussed further in Chapter 8, windows are normally positive ($ w(n)>0$), symmetric about their midpoint, and look pretty much like a ``bell curve.'' A window multiplies the signal $ x$ being analyzed to form a windowed signal $ x_w(n) = w(n)x(n)$, or $ x_w = w\cdot x$, which is then analyzed using an FFT. The window serves to taper the data segment gracefully to zero, thus eliminating spectral distortions due to suddenly cutting off the signal in time. Windowing is thus appropriate when $ x$ is a short section of a longer signal (not a period or whole number of periods from a periodic signal).


Theorem: Real symmetric FFT windows are linear phase.


Proof: Let $ w(n)$ denote the window samples for $ n=0,1,2,\ldots,M-1$. Since the window is symmetric, we have $ w(n)=w(M-1-n)$ for all $ n$. When $ M$ is odd, there is a sample at the midpoint at time $ n=(M-1)/2$. The midpoint can be translated to the time origin to create an even signal. As established on page [*], the DFT of a real and even signal is real and even. By the shift theorem, the DFT of the original symmetric window is a real, even spectrum multiplied by a linear phase term, yielding a spectrum having a phase that is linear in frequency with possible discontinuities of $ \pm\pi$ radians. Thus, all odd-length real symmetric signals are ``linear phase'', including FFT windows.

When $ M$ is even, the window midpoint at time $ n=(M-1)/2$ lands half-way between samples, so we cannot simply translate the window to zero-centered form. However, we can still factor the window spectrum $ W(\omega_k)$ into the product of a linear phase term $ \exp[-\omega_k(M-1)/2]$ and a real spectrum (verify this as an exercise), which satisfies the definition of a linear phase signal.

Next Section:
Convolution Theorem
Previous Section:
Symmetry