0
$\begingroup$

I'm trying to find a tight (as tight as possible) upper bound for $\lvert x_u(t) \rvert$, where $x_u(t)$ is the $T$-periodic signal defined by the Fourier sum $$ x_u(t) = \frac{1}{N}\sum_{k=-N_0}^{N_0}X_u[k] e^{i2\pi kt/T}. $$ Here, $N$ is any odd prime, $N_0 = (N-1)/2$, and $X_u[k]$ are the DFT coefficients of the Zadoff–Chu sequence $x_u[n]$, namely \begin{align} X_u[k] &= \sum_{n=0}^{N-1}x_u[n] e^{-i 2 \pi nk/N} & x_u[n] &= e^{-i \pi u n (n+1)/N} \end{align} for any $u=1,2,\dots,N-1$. The upper bound does not need to depend on $u$ - in other words, an upper bound for $\max_{u,t} \lvert x_u(t) \rvert$ is sufficient.

I've obviously tried the triangle inequality and the Cauchy–Schwarz inequality, both of which result in $\lvert x_u(t) \rvert \le \sqrt{N}$ (it can be proven that $\lvert X_u[k]\rvert = \sqrt{N}$ independently of $k$ and $u$), but the bound is too loose.

The next thing I tried was to expand the $X_u[k]$ coefficients and write $$ x_u(t)=\sum_{n=0}^{N-1}x_u[n]D_N\Bigl(\frac{t}{T} - \frac{n}{N}\Bigr) $$ where we introduce the Dirichlet kernel $$ D_N(y) = \frac{1}{N}\sum_{k=-N_0}^{N_0}e^{i2\pi k y} =\frac{\sin(N\pi y)}{N\sin(\pi y)} =\frac{1}{N}+\frac{2}{N}\sum_{k=1}^{N_0-1}\cos(2\pi k y). $$ Then, by the triangle inequality and some symmetry arguments that allow fixing $t=T/(2N)$, one obtains $$ \lvert x_u(t) \rvert \le \sum_{n=0}^{N-1}\Bigl\lvert D_N\Bigl(\frac{t}{T} - \frac{n}{N}\Bigr)\Bigr\rvert \le \sum_{n=0}^{N-1}\Bigl\lvert D_N\Bigl(\frac{2n-1}{2N}\Bigr)\Bigr\rvert \le \frac{4}{\pi}\sum_{n=1}^{2N-1}\frac{1}{n} - \frac{2}{\pi}\sum_{n=1}^{N-1}\frac{1}{n} $$ after using $y(1-y/\pi) \le \sin y \le (4/\pi)y(1-y/\pi)$ to bound the kernel. By well-known results about harmonic numbers, one can find the large-$N$ bound $$ \lvert x_u(t) \rvert \lesssim \frac{2}{\pi} \ln N + \frac{4}{\pi} \ln 2 + \frac{2}{\pi} \gamma\tag{1}\label{eq:d_bound} $$ where $\gamma$ is the Euler—Mascheroni constant. This is a much better bound than the previous one, but graphing the function shows that it is still too pessimistic (case $N=7$ and case $N=53$ - in both cases, parameter $u$ is set to provide the highest possible peak).

At this point, I've started to suspect that one cannot rely only on the fact that $\lvert x_u[n]\rvert = 1$ and $\lvert X_u[k]\rvert = \sqrt{N}$ to find a meaningful bound, and the actual value of those coefficients must be taken into account. With this in mind, I tried to apply the approach of Upper bound for sum of the nth roots of unity to $$ \lvert x_u(t)\rvert^2 = \frac{1}{N}\biggl\lvert \sum_{k=-N_0}^{N_0} e^{i \pi u u^{-1} k(u^{-1}k + 1)/N}e^{i2\pi k t/T}\biggr\rvert^2 =\frac{1}{N} \sum_{k=-N_0}^{N_0} e^{i \pi u u^{-1} k(u^{-1}k + 1)/N}e^{i2\pi k t/T} \sum_{l=-N_0}^{N_0} e^{-i \pi u u^{-1} l(u^{-1}l + 1)/N}e^{-i2\pi k t/T}. $$ The first identity follows from the fact that $X_u[k] = X_u[0] x_u^*[u^{-1}k]$, where $u^{-1}$ is the inverse of $u$ modulo $N$ (recall that $N$ is prime, so $u^{-1}$ is well defined) and where $(\cdot)^*$ denotes complex conjugate. Unfortunately, because of the quadratic term in the exponent (i.e., $u^{-1} k(u^{-1}k + 1)$), I don't see the way to express the double sum in terms of $k-l$ only and, in turn, to move forward.

Another similar approach consists in manipulating the above expression into $$ \lvert x_u(t)\rvert^2 = 1 + \frac{2}{N}\sum_{m=1}^{N-1} \operatorname{Re}\Bigl(a_m e^{-i 2\pi m t/T}\Bigr)\tag{2}\label{eq:last} $$ where $$ a_m = \sum_{k=-N_0}^{N_0-m}x_u^*[u^{-1}k]x_u[u^{-1}(k+m)] =x_u[u^{-1}m]\sum_{k=-N_0}^{N_0-m}e^{-i 2\pi u^{-1} km/N} =x_u[u^{-1}m]e^{i \pi u^{-1} m^2/N}\frac{\sin(\pi u^{-1}m(N-m)/N)}{\sin(\pi u^{-1}m/N)}. $$ This time, again with a similar strategy as the one in Upper bound for sum of the nth roots of unity, I may be able to estimate $\lvert a_m \rvert$ (although it'll probably require approximating the $\cos$ with a polynomial of degree 8, instead of 4) but I'm not sure it's worth the effort since I wouldn't know how to use them - some numerical experiments show that, if I just apply $\operatorname{Re}(a_m e^{-i 2\pi m t/T}) \le \lvert a_m \rvert$ inside of $\eqref{eq:last}$, I end up with a bound that is slightly worse than $\eqref{eq:d_bound}$.

Attacking the problem from a somehow different angle, one can also think about a more "analysis-oriented" solution. For instance, looking to \eqref{eq:last}, we have $ \lvert x_u(t) \rvert^2 = f(e^{i2\pi t/T}) $ where $$ f(z) = \operatorname{Re}\Bigl(1 + \frac{2}{N}\sum_{m=1}^{N-1}a_m^* z^m\Bigr) $$ is a function that is harmonic on the whole complex plane, since it's the real part of an entire function. Then I was thinking about Harnack's inequality, but I couldn't really see how to apply it, since I would have to estimate a lower bound on $f(z)$ for $\lvert z \rvert \le R$, $R > 1$, in order to shift the function and ensure its nonnegativity on the ball of radius $R$, but this sounds as hard as the original problem.

To conclude, let me add a few thoughts and minor results that may be useful, although I couldn't find an application.

  • Since $x_u(nT/N) = x_u[n]$, we readily see that $\lvert x_u(nT/N)\rvert = 1$, for all $n \in \mathbb Z$.
  • Symmetry arguments, together with the previous point, suggest that the maximum is located at a point of the form $t=(2m+1)/(2N)$ for some $m =0,1,\dots, N-1$. Actually, the plots suggest that $t=(2N-1)/(2N)$ is the maximum point (I couldn't prove either conjecture).
  • Besides being $N$-periodic, the Zadoff–Chu sequence and its DFT exhibit the symmetries \begin{align} x_u[N-n-1]&=x_u[n] & X_u[-k] &= X_u[k]e^{-i2\pi k/N}. \end{align}
  • Using the second identity above, it is straightforward to show that shifting $x_u(t)$ towards the right by $T/(2N)$ results in an even function, that is $x_u(t-T/(2N))=x_u(-t-T/(2N))$.

Thanks in advance for all your help!

$\endgroup$

0

You must log in to answer this question.