0
$\begingroup$

This q will make use of these 3 DTFT pairs... $$ \require{extpfeil}\Newextarrow{\xleftrightarrow}{15,15}{0x2194} \begin{array}{rcl} \alpha x_1[n] + \beta x_2[n] & \xleftrightarrow{\mathscr{F}} & \alpha X_1[e^{j\omega}] + \beta X_2[e^{j\omega}]\\ x[n - n_o] & \xleftrightarrow{\mathscr{F}} & e^{-j\omega n_o}X[e^{j\omega}]\\ \left(\begin{array}{c}n+r-1\\n\end{array}\right)a^nu[n] & \xleftrightarrow{\mathscr{F}} & \frac{1}{\left(1 - a\text{e}^{-j\omega}\right)^r} \end{array} $$


My q actually stems from this one...

How do you find the number of solutions like this?

$$x_1 + x_2 + x_3 + x_4 = 32$$

where $0 \le x_i \le 10$.

What's the generalized approach for it?

To which I provided a generalized approach...

$$ card\left(C\right) = \left[x^{n - vl}\right]\left(x^0 + x^2 + \cdots + x^{u - l}\right)^v = \left[x^{n - vl}\right]\left(\frac{1 - xx^{u - l}}{1 - x}\right)^v $$

As well as the answer to the given problem...

$$ \Longrightarrow \left[x^{32 - 4\cdot 0}\right]\left(\frac{1 - xx^{10 - 0}}{1 - x}\right)^4 = 165 $$

Wrt these definitions...

  • # variables (NOT only 4) $=v$.
  • Rhs (NOT only 32) $=n$.
  • Lower bound (NOT only 0) $=l$.
  • Upper bound (NOT only 10) $=u$.

I've since learned of the IDTFT$\left[X[e^{j\omega}]\right]$'s machine-like efficiency when used as a coefficient extractor, e.g., after assigning values for the 4 variables, the quoted sequence is represented by...

$$ \left(x^0 + x^2 + \cdots + x^{10}\right)^4 = \left(\frac{1 - x^{11}}{1 - x}\right)^4 $$

Which, after expanding...

$$ = \frac{1}{(1-x)^4} -\frac{4x^{11}}{(1-x)^4} +\frac{6x^{22}}{(1-x)^4} -\frac{4x^{33}}{(1-x)^4} +\frac{x^{44}}{(1-x)^4} $$

& substituting $e^{-j\omega}\;\forall\;x$ (which of course, would seldom be done in practice, BUT aids explanation)...

$$ = \frac{1}{(1-e^{-j\omega})^4} -\frac{4e^{-j11\omega}}{(1-e^{-j\omega})^4} +\frac{6e^{-j22\omega}}{(1-e^{-j\omega})^4} -\frac{4e^{-j33\omega}}{(1-e^{-j\omega})^4} +\frac{e^{-j44\omega}}{(1-e^{-j\omega})^4} $$

We treat it as the TF $X[e^{j\omega}]$ & VERY quickly deduce the final answer (using the 3 aforementioned DTFT pairs)...

$$ \begin{array}{rcl} X[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & x[n]\\ \shortparallel & & \shortparallel\\ \frac{1}{(1-e^{-j\omega})^4} = X_1[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & x_1[n] = \left(\begin{array}{c}n+3\\n\end{array}\right)u[n]\\ + & & +\\ ? = X_2[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & x_2[n] =\;?\\ + & & +\\ \vdots & \vdots & \vdots\\ + & & +\\ ? = X_5[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & x_5[n] =\;?\\ & & \\ & \Downarrow & \\ & & \\ X[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & x[n]\\ \shortparallel & & \shortparallel\\ \frac{1}{(1-e^{-j\omega})^4} = X_1[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & x_1[n] = \left(\begin{array}{c}n+3\\n\end{array}\right)u[n]\\ - & & -\\ \frac{4e^{-j\omega11}}{(1-e^{-j\omega})^4} = 4e^{-j\omega11}X_1[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & 4x_1[n - 11] = 4\left(\begin{array}{c}n-8\\n\end{array}\right)u[n - 11]\\ + & & +\\ \frac{6e^{-j\omega22}}{(1-e^{-j\omega})^4} = 6e^{-j\omega22}X_1[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & 6x_1[n - 22] = 6\left(\begin{array}{c}n-19\\n\end{array}\right)u[n - 22]\\ - & & -\\ \frac{4e^{-j\omega33}}{(1-e^{-j\omega})^4} = 4e^{-j\omega33}X_1[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & 4x_1[n - 33] = 4\left(\begin{array}{c}n-30\\n\end{array}\right)u[n - 33]\\ + & & +\\ \frac{e^{-j\omega44}}{(1-e^{-j\omega})^4} = e^{-j\omega44}X_1[e^{j\omega}] & \xleftrightarrow{\mathscr{F}} & x_1[n - 44] = \left(\begin{array}{c}n-41\\n\end{array}\right)u[n - 44]\\ & & \\ & \Downarrow & \\ & & \\ \end{array}\\ x[n] = \frac{(n+1)(n+2)(n+3)u[n]}{6} $$


I've already verified to myself that $x[n]$ is a closed form version of the GF, i.e., $(0,1,2,3,4,\ldots) \mapsto (1,4,10,20,30,\ldots)$, but there are certain GFs - the generalized 1 that I opened up w/ for instance - which I struggle to find IDTFTs for!

Could someone please help me find (or explain the impossibility of finding) IDTFT$\left[X[e^{j\omega}]\right]$ for...

$$ X\left[e^{j\omega}\right] = \left(\frac{1 - xx^{u - l}}{1 - x}\right)^v $$

If you conclude $\nexists$ IDTFT$\left[X[e^{j\omega}]\right]$, & you have good reason, would you also describe the family of GFs for which this method will not work?


UPDATE 1

After realizing that the coefficients resulting from the expansion step are given by pascal's triangle, I was able to derive...

$$ card\left(C\right) = \left[x^{n - vl}\right]\left(\frac{1 - xx^{u - l}}{1 - x}\right)^v\\ = \sum_{k = 0}^{v}\left[(-1)^k\left(\begin{array}{c}v\\k\end{array}\right) \left(\begin{array}{c}n + v - k(u - l + 1) - l\\n\end{array}\right)u[n - k(u - l + 1)] \right] $$

But can it be further simplified?

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.