Finding Fourier series coefficients for discrete time signal

Let $$x[n]$$ be a periodic sequence with period $$N$$ and Fourier series representation $$x[n] = \sum _{k=}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 , x , 0 , \dots x[N-2] , 0 , x[N]$$.

Since $$x = 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 , x , 0 , \dots x[N-1] , 0 , x[N+1] , 0 , x[N+3] , \dots , 0 , x[2N]$$Which is $$x, 0 , x , 0 , \dots x[N-1] , 0 , x , 0 , x , \dots , 0 , x$$

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

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.

• $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. Nov 15 '20 at 19:31
• as he says don't know how to proceed further and how to relates bk and ak. in the last line. Nov 15 '20 at 19:32
• @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. Nov 15 '20 at 19:33
• @Fat32 I see. Anyway, your answers are really fascinating. Thank you so much. Nov 16 '20 at 0:54
• @S.H.W: That's right, and similarly for the other sum. Nov 16 '20 at 14:47

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.

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

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]$$.

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