2
$\begingroup$

Let $x[n]$ be a periodic sequence with period $N$ and Fourier series representation $$x[n] = \sum _{k=<N>}a_ke^{jk\frac{2\pi}{N}n}$$ Determine the Fourier series coefficients for $$y[n] = \begin{cases} x[n], & \text{if $n$ is even} \\[2ex] 0, & \text{if $n$ is odd} \end{cases}$$

My try

$N$ even

We have $x[0], 0 , x[2] , 0 , \dots x[N-2] , 0 , x[N]$.

Since $x[0] = x[N]$ the sequence $y[n]$ is periodic with $N$. Also we have

$$e^{jM\frac{2\pi}{N}n}x[n] \leftrightarrow a_{k-M}$$Let $M = \frac{N}{2}$, then $(-1)^nx[n] \leftrightarrow a_{k-\frac{N}{2}}$. In this case $$b_k = \frac{1}{2}(a_k + a_{k-\frac{N}{2}})$$

$N$ odd

By writing the first terms of $y[n]$, we see that $y[n]$ is periodic with period $2N$

$$x[0], 0 , x[2] , 0 , \dots x[N-1] , 0 , x[N+1] , 0 , x[N+3] , \dots , 0 , x[2N]$$Which is $$x[0], 0 , x[2] , 0 , \dots x[N-1] , 0 , x[1] , 0 , x[3] , \dots , 0 , x[0]$$

So we write

\begin{align} b_k &= \frac{1}{2N}\sum _{n=<2N>}y[n]e^{\frac{-jk\pi n}{N}}\\ &= \frac{1}{2N} \sum _{n=0}^{\frac{N-1}{2}}x[2n] e^{\frac{-jk2\pi n}{N}} + \frac{(-1)^k}{2N}\sum _{n=1}^{\frac{N-1}{2}}x[2n-1] e^{\frac{-jk\pi (2n-1)}{N}}. \end{align}

I don't know how to proceed further and how to relates $b_k$ and $a_k$.

$\endgroup$
1
$\begingroup$

For odd $N$ you can write the DFS coefficients $b_k$ of $y[n]$ as

$$\begin{align}b_k&=\frac{1}{2N}\sum_{n=0}^{2N-1}x[n]\frac{1+e^{-jn\pi}}{2}e^{-j\frac{2\pi nk}{2N}}\\&=\frac{1}{4N}\sum_{n=0}^{2N-1}x[n]e^{-j\frac{2\pi nk}{2N}}+\frac{1}{4N}\sum_{n=0}^{2N-1}x[n]e^{-j\frac{2\pi n(k+N)}{2N}}\tag{1}\end{align}$$

By splitting each sum in Eq. $(1)$ into two sums with indices ranging from $n=0$ to $n=N-1$ it can be shown that the first sum is zero for odd $k$, and the second sum is zero for $k+N$ odd, i.e., for even $k$. Consequently, for even $k$ only the first sum remains, and it equals $\frac12 a_{k/2}$, and for odd $k$ only the second sum remains, which equals $\frac12a_{(k+N)/2}$.

In sum, the result is

$$b_k=\begin{cases}\frac12 a_{k/2},&k\textrm{ even}\\\frac12 a_{(k+N)/2},&k\textrm{ odd}\end{cases}\tag{2}$$


Just a simple example in order to illustrate the relation between $a_k$ and $b_k$ as expressed in Eq. $(2)$:

We choose

N = 5;

and

x = [1,2,3,4,5];

As correctly explained in the OP, the sequence $y[n]$ has a length of $2N=10$:

y = [1,0,3,0,5,0,2,0,4,0];

The DFS coefficients are just the DFT coefficients scaled by the inverse of the period. So we have

A = fft(x) / N;
B = fft(y) / (2*N);

According to $(2)$, apart from a scaling, the coefficients $b_k$ are obtained by filling the even indices starting from $a_0$, and filling the odd indices starting from $a_{(N+1)/2}=a_3$. So we should get

B2 = .5 * [A(1),A(4),A(2),A(5),A(3),A(1),A(4),A(2),A(5),A(3)];

which gives

B-B2
ans =

  0  0  0  0  0  0  0  0  0  0

Obviously, the coefficients $b_k$ are $N$-periodic, even though $y[n]$ has period $2N$. This is a well-known property of sequences for which all odd elements vanish.

$\endgroup$
14
  • $\begingroup$ $a_k$ that you used in your answer, and the $a_k$ that OP used in his answer (to the even part) might be confusing. The former is the DFS of the $2N$ length sequence, while the latter is the DFS of the length $N$ sequence, that he is interested in to express N-point Fourier series coefficients $b_k$ in terms of. $\endgroup$
    – Fat32
    Nov 15 '20 at 19:31
  • $\begingroup$ as he says don't know how to proceed further and how to relates bk and ak. in the last line. $\endgroup$
    – Fat32
    Nov 15 '20 at 19:32
  • $\begingroup$ @Fat32: $a_k$ are just the DFS coefficients of $x[n]$, and $b_k$ are the DFS coefficients of $y[n]$, just like in the question. $\endgroup$
    – Matt L.
    Nov 15 '20 at 19:33
  • 1
    $\begingroup$ @Fat32 I see. Anyway, your answers are really fascinating. Thank you so much. $\endgroup$
    – S.H.W
    Nov 16 '20 at 0:54
  • 1
    $\begingroup$ @S.H.W: That's right, and similarly for the other sum. $\endgroup$
    – Matt L.
    Nov 16 '20 at 14:47
1
$\begingroup$

You are asking for DFS (discrete Fourier series) coefficients $b_k$ of the periodic sequence $y[n]$, in terms $a_k$ of the periodic sequence $x[n]$. Since DFS and DFT (discrete Fourier transform) are the same things, I will instead write down an answer for the DFTs $Y[k]$ and $X[k]$ of the associated sequences, in the context of which $X[k] = a_k$ , and $Y[k] = b_k$ will be understood.

I would like to relate DFTs to DTFTs (discrete-time Fourier transform) through the sampling relation, which indicates that :

N-point DFT X[k] of the N-point sequence x[n], is the uniform samples of the DTFT X(w) of x[n].

The DTFT of $x[n]$ is :

$$ X(\omega) = \sum_{n=0}^{N-1} x[n] e^{-j \omega n } \tag{a}$$

and the DFT of $x[n]$ is :

$$ X[k] = X(\frac{2\pi}{N}k) = \sum_{n=0}^{N-1} x[n] e^{-j \frac{2\pi}{N}nk } \tag{b}$$ Let $x[n]$ and $y[n]$ be two sequences related by: $$y[n]=\begin{cases}{ x[n] ~~~,~~~n:even \\ ~~~0 ~~~~~,~~~ n:odd }\end{cases}$$

You can also express $y[n]$ as :

$$ x[n] \longrightarrow \boxed{ \downarrow 2 } \overset{w[n]}{\longrightarrow} \boxed{ \uparrow 2 } \longrightarrow y[n] $$

Applying DTFT relations to the sequences :

$$ W(\omega) = 0.5 \left( X\left( \frac{\omega}{2} \right) + X\left( \frac{\omega-2\pi}{2} \right) \right) \tag{1} $$

and

$$ Y(\omega) = W(2\omega) \tag{2} $$

hence

$$ Y(\omega) = 0.5 \left( X\left( \omega \right) + X\left( \omega-\pi\right) \right) \tag{3} $$

Eq.3 describes the relation (for any $N$) between the DTFTs $Y(\omega)$ and $X(\omega)$ of the sequences $x[n]$, and $y[n]$. To turn this into the equivalent relation between the N-point DFTs $X[k]$ and $Y[k]$, (and for your case a relation between DFS $a_k$ and $b_k$) we shall sample the associated DTFTs. Then we have :

$$ \begin{align} Y[k] &= Y( \frac{2\pi}{N} k ) ~~~,~~~k = 0,1,...,N-1 \tag{4} \\ \\ &= 0.5 \left( X\left( \frac{2\pi}{N} k \right) + X\left( \frac{2\pi}{N} k-\pi\right) \right) \tag{5} \\ \\ &\boxed{ Y[k] = 0.5 \left( X\left[ k \right] + X\left[k- \frac{N}{2} \right] \right) }\tag{6} \\ \end{align}$$

Eq.6 describes the requested relation between N-point DFTs $X[k]$ and $Y[k]$.

When $N$ is EVEN (say $N = 2 M$ ) the relation becomes :

$$ \boxed{ Y[k] = 0.5 ( X[k] + X[k-M] ) }\tag{7} $$

which is what you have arrived at $b_k = 0.5(a_k + a_{k -\frac{N}{2}})$.

However, when $N$ is ODD, there is a problem due to $N/2$ not being an integer. The sequence $X[k-N/2]$ is interpreted as an interpolation of $X[k]$ at the fractional indices $k-N/2$.

For $N=2M+1$ , we have $X[k-N/2] = X[k-M-0.5]$ , $k=0,1,...,N-1$ , which evaluates $X[k]$ at the points $m = 0.5,1.5,...,N-0.5$. To get those intermediate samples, we need an interpolation of $X[k]$ by 2.

Interpolation of $X[k]$ by 2, is achieved by zero padding $x[n]$ by $N$ samples, and computing its $2N$-point DFT :

$$ x_e[n] = \begin{cases}{ x[n] ~~~,~~~ 0 \leq n < N \\ ~~~0 ~~~~ , ~~~~ N \leq n < 2N }\end{cases} $$

Then we can see, by the DFT - DTFT sampling relation that :

$$ \mathcal{DFT}\{x_e[n]\} =X_2[k] = X(\frac{2\pi}{2N}k )= X(\frac{2\pi}{N} k/2 ) = X[k/2] \tag{8} $$

for $ k = 0,1,.,2N-1$. Note that DTFTs of $x[n]$ and $x_e[n]$ are the same.

Based on Eqs. 8, you can restate Eq.6 when $N$ is odd :

$$ \boxed{ Y[k]= 0.5 \big( X\left[ k \right] + X_2\left[2k- N\right] \big) } \tag{9} $$

with your notation it becomes: $$ b_k = 0.5 ( a_k + a^e_{2k-N} ) $$ where $a^e$ is the DFS of the sequence $x_e[n]$.

As you can see, you cannot express $b_k$ (with a simple formula) in terms of sole $a_k$ when $N$ is odd.

$\endgroup$
1
$\begingroup$

A more simpler interpretation of the required $b_k$ is based on the DTFT relation between $x[n]$ and $y[n]$, as stated in my first answer :

$$Y(\omega) = 0.5 \left( X(\omega) + X(\omega - \pi) \right) \tag{1} $$

It's simple to show that $X(\omega-\pi)$ is the DTFT of the sequence $(-1)^n x[n]$. We can denote that new sequence as $x_s[n]$, and its DTFT as $X_s(\omega) = X(\omega-\pi)$. Then Eq.1 becomes :

$$Y(\omega) = 0.5 \left( X(\omega) + X_s(\omega ) \right) \tag{2} $$

And we can simply apply $N$-point DFT samlping on Eq.2 to get DFT $Y[k]$ :

$$Y[k] = Y(\frac{2\pi}{N}k) = 0.5 \left( X(\frac{2\pi}{N}k) + X_s(\frac{2\pi}{N}k) \right) = 0.5 \left( X[k]+X_s[k]\right) \tag{3} $$

Hence for all $N$ even or odd, $$Y[k] = X[k] + X_s[k] ~~~,~~~k=0,1,...,N-1 \tag{4}$$

where $X_s[k]$ is the $N$-point DFT of the sequence $x_s[n] = (-1)^n x[n]$ , $n=0,1,..,N-1$.

In terms of DFS sequences Eq.4 becomes:

$$b_k = a_k + {a^s}_k ~~~,~~~ k=0,1,...,N-1 \tag{5}$$

where ${a^s}_k$ is the $N$-point DFT of the sequence $x_s[n] = (-1)^n x[n]$ , $n=0,1,..,N-1$.

$\endgroup$
1
$\begingroup$

As if three mis-interpretations were not sufficient, I'm putting yet another interpretation of the problem, this time from the perspective of OP (which is also taken by MattL in his answer) who considers $y[n]$ to be a $2N$-point periodic sequence, where my previous three answers assumed $y[n]$ as of length $N$, anyway.

The definition

$$ y[n] = \begin{cases} { x[n] ~~~,~~~ n:even \\ ~~~ 0 ~~~ ~~, ~~~ n:odd }\end{cases} $$

for $n=0,1,...,2N-1$ can be represented by the following block diagram :

$$ x[n] \longrightarrow \boxed{1:2} \overset{w[n]} \longrightarrow \boxed{\downarrow 2} \overset{v[n]} \longrightarrow \boxed{\uparrow 2} \longrightarrow y[n]$$

where $x[n]$ is of length $N$, $w[n]$ of length $2N$, $v[n]$ of $N$, and $y[n]$ is of length $2N$. Note that the first block is a repeater (concatenator) (by 2 in this case).

Now, the freq-domain equivalent of the above time-domain block for all $N$ is: $$ 2X[k] \longrightarrow \boxed{\uparrow 2} \overset{W[k]} \longrightarrow \boxed{\%N} \underset{0.5} {\overset{V[k]} \longrightarrow} \boxed{1:2} \longrightarrow Y[k]$$

Where the middle block is an aliaser, which aliases $W[k]$ of length $2N$ into $V[k]$ of length $N$ sequence (and also divides by 2). All DFT sequences have their lengths equal to their time domain counterparts.

Hence, the dual block diagram expresses the $2N$-point DFT $Y[k]$ of the $2N$-point sequence $y[n]$, in terms of $N$-point DFT $X[k]$ of $N$-point sequence $x[n]$.

Now we have the following relations :

$ Y[k] = V[(k)_N] ~~~,~~ k=0,1,...,2N-1 \\\\$

$V[k] = 0.5( W[k] + W[k+N] ) ~~~,~~~ k=0,1,...,N-1 \\\\$

$ W[k] = \begin{cases} {2 X[k/2] ~~~, ~~~ k = 0,2,4,...2N-1 \\ ~~~~~~ 0 ~~~~~~~~ , ~~~~ k=1,3,...,2N-1 \\} \end{cases} $

From which you can deduce that :

For $N$ EVEN:

$Y[k] =\begin{cases} { X[\frac{(k)_N}{2}] + X[ \frac{(k)_N+N}{2}] ~~~ , ~~~ k=0,2,4,...,2N-1 \\ ~~~0 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ , k= 1,3,5,...,2N-1 \\ }\end{cases}$

And for $N$ ODD:

$Y[k] =\begin{cases} { X[\frac{(k)_N}{2}] ~~~~ , ~~~~~~ k=0,2,4,...,2N-1 \\ X[ \frac{(k)_N+N}{2}] ~~~~, k= 1,3,5,...,2N-1 }\end{cases}$

which is identical to Eq.2 of MattL for odd N, (except the scale factor). NOTE the modulus operator on the indices of the sequence $X[k]$.

$\endgroup$
1
$\begingroup$

Yet another interpretation of the requested DFS coefficients can be obtained by one of the DFS (or DFT) properties known as modulation theorem which states that

If the N-point sequences $x[n]$ and $w[n]$ has $N$-point DFS sequences $a_k$ and $w_k$, then we have :

$$ x[n] \cdot w[n] \overset{DFS} \longleftrightarrow \frac{1}{N} ~ a_k ~ \overset{N} {\star} ~w_k \tag{1}$$

Where the right side of Eq.1 is the N-point circular convolution of the sequences $a_k$ and $b_k$ (for DFS sequences it's interpreted as N-point periodic convolution).

Then one can see that $y[n]$ is related to $x[n]$ by :

$$y[n] = x[n]\cdot w[n] \tag{2} $$

where $w[n] = 0.5(1 + (-1)^n) $. Then applying the modulation theorem in Eq.1, and nothing that

$$ w_k = 0.5 \cdot \left( N \delta[k] + \frac{1 -(-1)^N}{1 + e^{-j\frac{2\pi}{N}k}} \right) \\\\$$

$$ w_k = \begin{cases}{ \frac{N}{2} ( \delta[k] + \delta[k-N/2] ~~~,~~~ N:even \tag{3}\\ \frac{N}{2} \delta[k] + \frac{1}{1 + e^{-j\frac{2\pi}{N}k}} ~~~~~~~~~~~,~~~ N:odd }\end{cases} \\\\$$

Then we can see that the N-point DFS coefficients $b_k$ of $y[n]$ is given by:

$$b_k = \frac{1}{N} ( a_k \star w_k) \\ \tag{4}$$

$$ b_k = \begin{cases}{ 0.5 a_k + 0.5 a_{k-N/2} ~~~~~~~~~~~~~~~~~~~~~~~~~~~~,~~ N:even \tag{5} \\ \\ 0.5 a_k + \frac{1}{N} \sum_{m=0}^{N-1} a_{k-m} \frac{1}{1 + e^{-j\frac{2\pi}{N}m}} ~~~~~~~~~~~,~~~ N:odd }\end{cases} \\\\$$

$k = 0,1,...,N-1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.