This question comes right out of the problems section of Oppenheim's Signals & Systems 2ed textbook. I don't understand the solution to the problem.

(problem #1.35) If a discrete-time complex sinusoid is expressed by \$x[n] = \exp(jmn2\pi/N)\$ (m is any integer), prove that the fundamental frequency is N0 = N/gcd(N,m).

Solution: for a discrete-time signal to be periodic \$x[n]= x[n+N_0]\$. Substituting n+N0 into n and expanding that expression means that \$m(2\pi/N)N_0 = 2\pi{}k\$, where k is some (not any) integer. Rearranging we get the expression N0=N/(m/k). somehow (m/k) = gcd(N,m).

I don't see it.

  • \$\begingroup\$ I added some math formatting to make it easier to read your question. But I also rearranged the first formula, putting n inside the exponential function, because I think this is the correct form for a complex exponential. Please revert if I changed the meaning of your question. \$\endgroup\$
    – The Photon
    Apr 5 '13 at 2:21

Let's write the book's solution out in more detail.

First, by definition, a discrete-time signal is periodic with period N0 if for all n, \$x[n+N_0] = x[n]\$.

So we're interested in cases where

\$\exp(j2\pi{}mn/N) = \exp(j2\pi{}m(n+N_0)/N)\$.

We know that the complex exponential, considered as a continuous function, repeats whenever it's argument advances by \$2\pi\$. So our equality holds whenever the phase difference between the arguments increases by some multiple of \$2\pi\$, that is whenever there is a k such that

\$2\pi{}mn/N + 2\pi{}k = 2\pi{}m(n+N_0)/N\$.

We can eliminate terms here to get

\$ mn/N + k = mn/N + mN_0/N\$

and further

\$ k = mN_0/N \$

So the period of our discrete time function is

\$N_0 = Nk/m\$

But N0 must be an integer, and we also want the smallest possible value of N0 to get the fundamental frequency. That means we want the smallest k that makes Nk/m an integer.

Lets write this out in terms of the prime factors of N and m:

\$N_0 = \dfrac{k \Pi_p n_p}{\Pi_q m_q} \$

For this to be an integer we need k to be made up of all the factors of m, except the ones that are held in common with N.

\$ k = \dfrac{\Pi_q m_q}{\Pi_{\mathrm{common\ factors}} m_q}\$

But the numerator here is just m, and the denominator here is just the gcd of N and m, so we have

\$ m / k = \gcd(N, m)\$

which is what we were trying to show.

TL;DR: It's to make it work out so that N0 is an integer.


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.