The Discrete Fourier Transform of Symmetric Sequences

• Matlab
• DFT_FFT
• Tutorials

Symmetric sequences arise often in digital signal processing.  Examples include symmetric pulses, window functions, and the coefficients of most finite-impulse response (FIR) filters, not to mention the cosine function.  Examining symmetric sequences can give us some insights into the Discrete Fourier Transform (DFT).  An even-symmetric sequence is centered at n = 0 and x_even(n) = x_even(-n).  The DFT of x_even(n) is real.  Most often, signals we encounter start at n = 0, so they are not strictly speaking even-symmetric.  We’ll look at the relationship between the DFT’s of such sequences and those of true even-symmetric sequences.  Note: for basics of using the DFT, see my last post [1].

Let x(n) be a causal sequence as shown in Figure 1 (top).  Let x_even(n) be an even-symmetric version of x(n), defined over n = -8:7, as shown in Figure 1 (bottom).  This sequence is centered at n = 0, and the first non-zero value occurs at n = -3.  The sequence is also referred to as a non-causal sequence, because it begins before n = 0.  Mathematically, the most straightforward way to find the Discrete Fourier Transform (DFT) of this sequence would be to evaluate the DFT formula (see Appendix) over n = -8: 7.  We would then find that the spectrum X_even(k) is real.  However, in this article, we’ll compute the DFT using the standard time index range of n= 0: N-1, which allows us to use the Matlab Fast Fourier Transform (FFT) function.  We’ll find X_even(k) using two different methods.

Method 1:  Time Shift

Given the causal sequence x(n), we can use the time-shifting property of the DFT to find the DFT of  x_even(n) .  For x(n) with DFT X(k), the time-shifting property is given by (see Appendix):

$$ x(n-N_0) \iff e^{-j2\pi N_0k/N}X(k) \qquad(1a) $$

Where X(k) is the DFT of x(n) and N₀ is delay in samples.  We define normalized radian frequency ω = 2πf/f_s, where f_s is sample frequency in Hz and f = kf_s/N.  We can then also write:

$$ x(n-N_0) \iff e^{-j\omega N_0}X(\omega) \qquad(1b) $$

Consider x(n) and x_even(n) shown in Figure 1.  x_even(n) is equal to x(n) advanced in time by N₀ = 3 samples, so:

$$x_{even}(n)= x(n+N_0) \qquad (2)$$

Since we are advancing x(n) by N₀ samples, Equation 1b becomes:

$$ x_{even}(n)=x(n+N_0) \iff e^{j\omega N_0}X(\omega) \qquad(3) $$

Thus, the DFT of x_even(n) is:

$$X_{even}(\omega) = e^{j\omega N_0}X(\omega) \qquad(4) $$

We can also write the converse of Equation 4:

$$X(\omega) = e^{-j\omega N_0}X_{even}(\omega) \qquad(5) $$

This equation shows that the DFT of a sequence x(n) having even symmetry with respect to its center sample is a real spectrum X_even(ω) multiplied by a linear phase shift.  An example of this is the frequency response of a symmetric FIR filter with an odd number of taps.  Given an even-symmetric filter h_even(n) with real frequency response H_even(ω), the causal filter’s frequency response is linear-phase:

$$H(\omega) = e^{-j\omega N_0}H_{even}(\omega) \qquad(6) $$

where N₀ = (number of taps – 1)/2.  A symmetric FIR with an even number of taps also has linear phase [2].

Figure 1.  Top:  Causal sequence x(n).   Bottom:  Even-symmetric sequence x_even(n). 

Method 1 Example

In this example, we use Equation 4 to find the DFT of x_even(n) shown in Figure 1 (bottom), given the causal sequence x(n) of Figure 1 (top):

x(n) = [2 8 12 13 12 8 2 0 0 0 0 0 0 0 0 0]/57.

The Matlab code is listed below.  Note that the .* operator performs element-by-element multiplication of two vectors.

    fs= 1;             % Hz sample frequency
    N= 16;             % samples length of x
    x= [2 8 12 13 12 8 2 0 0 0 0 0 0 0 0 0]/57;    % causal sequence
    % compute DFT of causal x
    X= fft(x,N);       % DFT
    k= 0:N-1;          % frequency index
    f= k*fs/N;         % Hz frequency
    % compute DFT of x_even using time shift property of DFT
    w= 2*pi*f/fs;        % rad normalized radian frequency
    No = 3;              % samples time advance
    Xeven= exp(j*w*No).*X;    % Equation 4

The DFT of x(n) is plotted in Figure 2; we see that it is complex.  The DFT of x_even(n) is plotted in Figure 3; as expected, it is real.

Figure 2.  DFT of causal sequence x(n).  Top:  real part.   Bottom:  imaginary part.

Figure 3.  DFT of x_even(n).  Top:  real part.   Bottom:  imaginary part.

Method 2:  Periodic Extension in Time

Figure 1 (bottom) plots x_even(n), which has finite length N = 16 samples.  Its spectrum, which we computed using the DFT, is of course discrete, as shown in Figure 3.  You may recall that the Fourier Transform of a periodic signal is discrete.  The converse is also true:  the inverse Fourier Transform of a discrete spectrum is periodic.  So, mathematically, our finite-length x_even(n) can be viewed as periodic, with each period replicating its N samples [3].  This is shown in Figure 4, where the top plot shows x_even(n), and the center plot shows x_even(n) extended to be periodic.

Figure 4.  Top:  sequence x_even(n).  Middle:  periodic extension x_p(n).  Bottom:  u(n) = x_p(0:N-1) .

For our periodic sequence x_p(n) we can state:

$$x_p(n+N)= x_p(n) \qquad(7) $$

Thus,

$$x_p(N-1)= x_p(-1)     \qquad \qquad \quad $$

$$x_p(N-2)= x_p(-2), etc. \qquad(8) $$

If we define u(n)= x_p(0:N-1), then u(n) is as shown in Figure 4 (bottom).  Conveniently, the time index n of u(n) matches that used in the DFT formula (see Appendix).  Note that u(n) has even symmetry with respect to N/2 = 8 (not including the sample at N = 0).  The DFT of u(n) is real, as we’ll show in the following example.

Method 2 Example

Here is the Matlab code to find u(n) given x_even(n), and compute its DFT.

    fs= 1;         % Hz sample frequency
    N= 16;         % samples length of x_even
    x_even= [0 0 0 0 0 2 8 12 13 12 8 2 0 0 0 0]/57;
    xp= [x_even x_even];        % periodic extension of x_even (2 periods)
    u= xp(9:24);                % u = xp over n= 0:N-1
    U= fft(u,N);                % DFT
    k= 0:N-1;                   % frequency index
    f= k*fs/N;                  % Hz frequency

x_even, xp, and u are plotted in Figure 4.  The DFT of u(n) is real and identical to the DFT we computed in Example 1; see Figure 3.

From Equation 8, x_p(N/2: N-1) = xp(-N/2: -1).  That is, the samples of x_p from N/2: N-1 match the negative-time portion of xp.  So, we can view the range n = N/2: N-1 as negative time, and any sequence with non-zero samples in this range is non-causal.  Common examples of non-causal sequences are any periodic sequence, such as a cosine.

If we form the bottom plot of u(n) in Figure 4 into a circle, we get the three-dimensional plot of Figure 5.  The symmetry with respect to n= 0 or n = N/2 is apparent.  The plot shows the equivalence of x_even(n) and u(n).  The plot can be viewed as periodic, with each period represented by one trip around the circle.

Finally, a word about odd-symmetric sequences.  An odd-symmetric sequence is centered at n = 0 and x_odd(n) = -x_odd(-n).  The DFT of such a sequence is pure imaginary.  Examples of odd sequences are the coefficients of FIR differentiators [4] and Hilbert transformers.

Figure 5.  Circular plot of u(n), N = 16.

For Appendix, see the PDF version.

References

1.Robertson, Neil, “Learn to Use the Discrete Fourier Transform”, DSPRelated.com, Sept, 2024, https://www.dsprelated.com/showarticle/1696.php

2.Mitra, Sanjit K., Digital Signal Processing, 2^nd Ed., McGraw Hill, 2001, Section 4.4.3.

3.Lyons, Richard G., Understanding Digital Signal Processing, 3^rd Ed., Pearson, 2011, Section 3.14.

4.Robertson, Neil, “Evaluate Noise Performance of Discrete-Time Differentiators”, DSPRelated.com, March, 2022, https://www.dsprelated.com/showarticle/1447.php

December, 2024     Neil Robertson

Sign in