\documentstyle{article}
\input{amssym.def}
\input{amssym}
\textheight 20cm
\textwidth  14cm
\hoffset -2cm
\voffset -3cm
\mag\magstep1
\tolerance 500
\frenchspacing
\arraycolsep 0.2em
\font\bm=msbm10 scaled 1000
\def\bmc{\mbox{\bm C}}
\def\bmn{\mbox{\bm N}}
\def\bmz{\mbox{\bm Z}}
\def\cn{\bmc_N}
\def\dn{\delta_n}
\def\dN{\delta_N}
\def\Dn{{\Delta_\nu}}
\def\Dnn{{\Delta_{\nu+1}}}
\def\ds{\displaystyle}
\def\fn{f_\nu}
\def\gn{g_\nu}
\def\hc{Ха\-ара--Крес\-тен\-со\-на}
\def\jn{{j_\nu}}
\def\jnn{{j_{\nu-1}}}
\def\la{\langle}
\def\lb{\{}
\def\lf{\lfloor}
\def\nn{{N_\nu}}
\def\nnn{{N_{\nu-1}}}
\def\No{\char "F2}
\def\omn{{\ts{\lower4pt\hbox{$\ominus$}\atop\hbox{${\ss n}$}}}}
\def\omns{{\ss{\lower4pt\hbox{$\ss\ominus$}\atop\hbox{${\sss n}$}}}}
\def\opn{{\ts{\lower4pt\hbox{$\oplus$}\atop\hbox{${\ss n}$}}}}
\def\opns{{\ss{\lower4pt\hbox{$\ss\oplus$}\atop\hbox{${\sss n}$}}}}
\def\proof{Д\,о\,к\,а\,з\,а\,т\,е\,л\,ь\,с\,т\,в\,о. }
\def\qed{$\ \blacksquare$}
\def\qn{{q_\nu}}
\def\qnn{{q_{\nu-1}}}
\def\ra{\rangle}
\def\rb{\}}
\def\rev#1{\mbox{\rm rev}_{#1}}
\def\revs#1{\!\!\!\!\mbox{\rm\footnotesize rev}_{#1}}
\def\rf{\rfloor}
\def\rn{r_\nu}
\def\rpn{r'_\nu}
\def\ss{\scriptstyle}
\def\sss{\scriptscriptstyle}
\def\ts{\textstyle}
\def\vc{Ви\-лен\-ки\-на--Крес\-тен\-со\-на}
\def\wn{\omega_n}
\def\xn{x_\nu}
\def\xpn{x'_\nu}
\def\yn{y_\nu}
\def\ypn{y'_\nu}
\def\zn{z_\nu}
\def\zpn{z'_\nu}

\begin{document}

\leftline{УДК 519.72; 621.391}
\begin{center}
{\large\bf С. М. Машарский} \\[0.5em]
{\large\bf СВЕРТКА И КОРРЕЛЯЦИЯ ДИСКРЕТНЫХ СИГНАЛОВ} \\[0.2em]
{\large\bf В БАЗИСАХ ХААРА--КРЕСТЕНСОНА\footnote{Работа выполнена при
финансовой поддержке Российского фонда фундаментальных исследований
(номер проекта 99-01-00747).}}
\end{center}

{\small\list{}{\leftmargin 3em\rightmargin 3em}
\item[]
В пространстве дискретных $N$-периодических сигналов $\cn$ при $N=n^s$
рассматриваются два вейвлетных базиса, связанныe с дискретным преобразованием
\hc. Для разложений по этим базисам получены аналоги известных теорем о
сдвиге, свертке и корреляции.
\item[]
{\bf Sergey M. Masharsky,\quad
Convolution and Correlation of Discrete Signals in Haar--Chrestenson Bases}
\item[]
Two wavelet bases, related with discrete Haar--Chrestenson transform,
are considered in a space $\cn$ of discrete $N$-periodic signals with
$N=n^s$. Analogues of well-known theorems of shift, convolution and
correlation for these bases are obtained.
\endlist}

\medskip
{\large\bf\leftline{Введение}}
\medskip

В цифровой обработке сигналов важную роль играет их спектральный анализ в
различных ортогональных базисах. Одной из задач такого анализа является
установление связи между спектрами исходных сигналов и спектрами их сдвига,
свертки и корреляции. В общем случае этот вопрос рассмотрен в~[1,\,2].
Полученные в этих работах результаты отражают свойства дискретных
преобразований, являющихся собственными по отношению к оператору сдвига.

В последнее десятилетие бурно развиваются новые методы обработки сигналов,
основанные на разложении по вейвлетным базисам~[3,\,4]. В отличие от
классических ортогональных преобразований, вейвлет-преобразования не
являются собственными по отношению к традиционным операторам сдвига, и
поэтому результаты работ~[1,\,2] к ним неприменимы. Однако вопрос о спектрах
сигналов в вейвлетных базисах остается актуальным. В частном случае (для
базисов Хаара) этот вопрос изучался в~[5--7].

В работах~[8,\,9] рассматриваются базисы \hc, которые являются обобщением
базисов Хаара. Так же, как и в хааровском случае, спектры дискретных сигналов
в базисах \hc\ имеют блочную древовидную структуру. В данной статье,
являющейся обобщением работы~[7], изучается связь этих спектров с
операциями сдвига, свертки и корреляции. При этом, в зависимости от базиса,
в качестве оператора сдвига может выступать циклический или $n$-ичный
сдвиг. Соответственно, свертка и корреляция может быть циклической или
$n$-ичной.

Прокомментируем содержание статьи по разделам.

В разд.~1 содержатся предварительные сведения, необходимые для изложения
дальнейшего материала. Здесь вводятся базисы \hc, дается определение
и приводятся основные свойства операции $n$-ичного сдвига.

В разд.~2 рассматривается базис \hc, связанный с прореживанием по частоте.
В качестве оператора сдвига здесь выступает $n$-ичный сдвиг. Установлено,
что сдвиг сигнала приводит к сдвигам внутри блоков его спектра
с одновременным поворотом спектральных коэффициентов в комплексной
плоскости, а свертка и корреляция двух сигналов --- соответственно к
поблочной свертке и корреляции их спектров.

В разд.~3 рассматривается базис \hc, связанный с прореживанием по времени.
Оператором сдвига здесь является циклический сдвиг. Для спектра сдвига
в этом случае получен результат, аналогичный представленному в разд.~2.
Для спектров свертки и корреляции результаты более тонкие: свертка и
корреляция двух сигналов приводят соответственно к модифицированной
свертке и корреляции соответствующих блоков их спектров (модификация
заключается в том, что при вычислении осуществляется поворот части
слагаемых).

Характер полученных в статье результатов позволяет надеяться на их успешное
применение в прикладных задачах фильтрации, сжатия и передачи сигналов по
каналам связи.

\bigskip
{\large\bf\leftline{1. Предварительные сведения}}
\medskip

Линейное пространство $\cn$ комплекснозначных $N$-периодических
последовательность $x=\lb x(j)\rb$, $j\in\bmz$, будем называть
{\it пространством сигналов}. В $\cn$ обычным образом вводятся скалярное
произведение и норма:
$$
 \la x,y\ra=\sum_{j=0}^{N-1} x(j)\,\overline{y(j)},\qquad
 \|x\|=\la x,x\ra^{1/2}.
$$

Обозначим через $\dN(j)$ единичный $N$-периодический импульс, равный 1 при
$j=0,\,\pm N,\,\pm 2N,\,\dots\,$ и равный нулю при остальных $j\in\bmz$.
Система сигналов $\lb\dN(j-k)\rb, k=0,1,\dots N-1$, образует естественный
ортонормированный базис пространства $\cn$.

Пусть $n,\,s\in\bmn$, $n\ge2$, $s\ge2$. В пространстве $\cn$ при $N=n^s$
рассмотрим два вейвлетных базиса:
$$
 c(j);\quad \fn(\sigma;\,j-p\Dnn),\quad
 p\in0:\nn-1,\ \sigma\in1:n-1,\ \nu\in1:s;                      \eqno(1.1)
$$
$$
 c(j);\quad \gn(\sigma;\,j-p),\quad
 p\in0:\nn-1,\ \sigma\in1:n-1,\ \nu\in1:s.                      \eqno(1.2)
$$
Здесь $\Dn=n^{\nu-1}$, $\nn=N/n^\nu$, $c(j)\equiv1$,
$$
 \fn(\sigma;\,j)=\sum_{\tau=0}^{n-1}\wn^{\sigma\tau}
 \sum_{q=\tau\Dn}^{(\tau+1)\Dn-1}\dN(j-q),                      \eqno(1.3)
$$
$$
 \gn(\sigma;\,j)=\sum_{\tau=0}^{n-1}\wn^{\sigma\tau}
 \delta_\nnn(j-\tau\nn),                                        \eqno(1.4)
$$
$\wn=\exp\lb2\pi i/n\rb$ --- первообразный корень из 1 степени $n$.

Базисы (1.1) и (1.2) называются {\it базисами \hc, связанными}\/
соответственно {\it с прореживанием по частоте}\/ и {\it прореживанием по
времени}~[9]. При $n=2$ получаем базисы Хаара.

Постоянно будут использоваться следующие обозначения: $\lf\alpha\rf$ ---
целая часть вещественного числа $\alpha$; $\la k\ra_n=k-\lf k/n\rf n$ ---
остаток от деления целого числа $k$ на натуральное $n$.

Для целого числа $a\in\lb0,1,\dots,N-1\rb$ запись
$a=(a_{s-1},a_{s-2},\dots,a_0)_n$ означает
$$
 a=a_{s-1}n^{s-1}+a_{s-2}n^{s-2}+\dots+a_0,\quad
 a_k\in0:n-1,\ k\in0:s-1.
$$
Пусть $a,\,b\in\lb0,1,\dots,N-1\rb$, $a=(a_{s-1},\dots,a_0)_n$,
$b=(b_{s-1},\dots,b_0)_n$. {\it Поразрядной суммой по модулю} $n$ чисел $a$
и $b$ называется число $c=(c_{s-1},\dots,c_0)_n$, такое, что
$c_k=\la a_k+b_k\ra_n$, $k\in0:s-1$. Кратко это соотношение записывается так:
$c=a\opn b$. Очевидно, что операция ``$\opn$'' не выводит из множества
$\lb0,1,\dots,N-1\rb$ и обладает следующими свойствами:
$$
 a\opn b = b\opn a,\qquad a\opn 0 = a,\qquad
 a\opn(b\opn c) = (a\opn b)\opn c.
$$
Число $a^*$ называется {\it $n$-ично противоположным}\/ числу $a$, если
$a\opn a^*=0$. Нетрудно видеть, что если $a^*=(a^*_{s-1},\dots,a^*_0)_n$,
то из условия $\la a_k+a^*_k\ra_n=0$, $k\in0:s-1$, следует
$$
 a^*_k=\la-a_k\ra_n=\left\lb
  \begin{array}{ccl}
    n-a_k,&~&a_k\ne0,\\
        0,&~&a_k = 0.
  \end{array}
 \right.
$$
Число $a\omn b:=a\opn b^*$ называется {\it поразрядной разностью по модулю
$n$}.

Зафиксируем $q\in\lb0,1,\dots,N-1\rb$. Отображения $j\to j\opn q$ и
$j\to j\omn q$, $j\in\lb0,1,\dots,N-1\rb$, называются соответственно
{\it $n$-сдвигом вправо}\/ и {\it $n$-сдвигом влево}\/ на величину $q$.
Отметим, что $n$-сдвиг является перестановкой множества $\lb0,1,\dots,N-1\rb$.

\bigskip
{\large\bf\leftline{2. Базис \hc, связанный с прореживанием}}
{\large\bf\leftline{\quad\,по частоте, и оператор $n$-ичного сдвига}}
\medskip

Начнем с нескольких вспомогательных утверждений.

\medskip
{\bf Лемма 2.1.} {\it При $\sigma\in1:n-1$ справедлива формула}
$$
 \fn(\sigma;\,j)=\wn^{\sigma\lf j/\Dn\rf}\,
 \delta_\nn\big(\lf j/\Dnn\rf\big),
 \quad j\in\bmz.                                                \eqno(2.1)
$$

\proof
Правая часть (2.1) равна $\wn^{\sigma\tau}$ при
$j\in\tau\Dn:(\tau+1)\Dn-1$, $\tau\in0:n-1$, и равна 0 при $j\in\Dnn:N-1$
(учесть, что $N=\Dnn\nn$). Те же значения при указанных $j$ принимает
согласно~(1.3) и $\fn(\sigma;\,j)$. Таким образом, при $j\in0:N-1$
равенство~(2.1) верно. Остается проверить $N$-периодичность правой
части~(2.1). Она следует из того, что при любом $k\in\bmz$
$$
 \frac{j+kN}\Dn=\frac j\Dn+nk\nn,\qquad
 \frac{j+kN}\Dnn=\frac j\Dnn+k\nn.
$$

Лемма доказана. \qed

\medskip
{\bf Следствие.} {\it При $p\in0:\nn-1$ справедливо равенство}
$$
 \fn(\sigma;\,j-p\Dnn)=\wn^{\sigma\lf j/\Dn\rf}\,
 \delta_\nn\big(\lf j/\Dnn\rf-p\big).                           \eqno(2.2)
$$

\medskip
Формулы (2.1) и (2.2) несколько упрощаются при $j\in0:N-1$. А именно,
если $j=(j_{s-1},\dots,j_0)_n$, то
$$
 \Big\lf\frac j\Dn\Big\rf=j_{s-1}n^{s-\nu}+\dots+n\,\jn+\jnn,
$$
так что
$$
 \wn^{\lf j/\Dn\rf}=\wn^\jnn.                                   \eqno(2.3)
$$

\medskip
{\bf Лемма 2.2.} {\it При фиксированном $q\in0:N-1$,
$q=(q_{s-1},\dots,q_0)_n$ справедливо равенство}
$$
 \fn(\sigma;\,j\omn q)=\wn^{-\sigma\qnn}\,
 \fn\big(\sigma;\,j-\lf q/\Dnn\rf\Dnn\big),
 \quad j\in0:N-1.                                               \eqno(2.4)
$$

\proof
Имеем $j=\lf j/\Dnn\rf\Dnn+\jnn\Dn+\la j\ra_\Dn$,
\,$q=\lf q/\Dnn\rf\Dnn+\qnn\Dn+\la q\ra_\Dn$. Значит,
$$
 j\omn q=\left(
           \Big\lf\frac j\Dnn\Big\rf \omn
           \Big\lf\frac q\Dnn\Big\rf
         \right) \Dnn
        + \la\jnn-\qnn\ra_n\,\Dn
        + \Big(\la j\ra_\Dn\omn\la q\ra_\Dn\Big).
$$
Согласно (2.1) и (2.3) получаем
$$
 \fn(\sigma;\,j\omn q)=\wn^{\sigma(\jnn-\qnn)}\,
 \delta_\nn\big(\lf j/\Dnn\rf\omn\lf q/\Dnn\rf\big).            \eqno(2.5)
$$
Отметим, что при $a,\,b\in0:N-1$
$$
 \delta_\nn(a\omn b)=
  \left\lb
   \begin{array}{rl}
    1,&\mbox{\rm если}\ a=b\\
    0,&\mbox{\rm если}\ a\ne b
   \end{array}
  \right\rb
 =\delta_\nn(a-b),
$$
поэтому равенство (2.5) принимает вид
$$
 \fn(\sigma;\,j\omn q)=\wn^{-\sigma\qnn}\,\big[\wn^{\sigma\jnn}\,
 \delta_\nn\big(\lf j/\Dnn\rf-\lf q/\Dnn\rf\big)\big].
$$
Учитывая (2.2) и (2.3), приходим к (2.4). Лемма доказана. \qed

\medskip
{\bf Следствие.} {\it При $p\in0:\nn-1$ справедливо равенство}
$$
 \fn(\sigma;\,j\omn p\Dnn)=\fn(\sigma;\,j-p\Dnn),
 \quad j\in0:N-1.                                               \eqno(2.6)
$$

\medskip
{\bf Лемма 2.3.} {\it При $j\in0:N-1$, $\sigma\in1:n-1$ справедливо равенство}
$$
 \fn(\sigma;\,j^*)=\overline{\fn}(\sigma;\,j).                  \eqno(2.7)
$$

\proof
Если $j\in\Dnn:N-1$, то и $j^*\in\Dnn:N-1$, поэтому при таких $j$ (2.7)
превращается в тождество $0=0$. Пусть теперь $j\in\tau\Dn:(\tau+1)\Dn-1$ при
некотором $\tau\in0:n-1$. Это значит, что $j=(\tau,j_{\nu-2},\dots,j_0)_n$,
поэтому $j^*=(\tau^*,j^*_{\nu-2},\dots,j^*_0)_n$. Согласно~(2.1) и~(2.3)
при таком $j$ имеем
$$
 \fn(\sigma;\,j^*)=\wn^{\sigma\tau^*}=\wn^{-\sigma\tau}
                  =\overline{\fn}(\sigma;\,j).
$$

Лемма доказана. \qed

\bigskip
Любой сигнал $x\in\cn$ можно разложить по ортогональному базису~(1.1):
$$
 x(j)=\alpha+\sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{p=0}^{\nn-1}
 \xn(\sigma,p)\,\fn(\sigma;\,j-p\Dnn),\quad j\in\bmz.           \eqno(2.8)
$$
Здесь
$$
 \alpha=\frac1N\sum_{j=0}^{N-1}x(j),\qquad
 \xn(\sigma,p)=\frac1{n^\nu}\sum_{j=0}^{N-1}x(j)\,
 \overline{\fn}(\sigma;\,j-p\Dnn).
$$
Совокупность коэффициентов разложения (2.8)
$$
 H_f(x)=\big\lb\alpha;\ \xn(\sigma,p),\
 p\in0:\nn-1,\ \sigma\in1:n-1,\ \nu\in1:s\big\rb
$$
образует {\it спектр \hc}\/ сигнала $x$, {\it связанный с прореживанием по
частоте}. Преобразование $x\to H_f(x)$ называется {\it дискретным
преобразованием \hc\ с прореживанием по частоте}.

Установим связь между спектрами исходного и $n$-ично сдвинутого сигнала.

\medskip
{\bf Теорема 2.1.} {\it Зафиксируем $q\in0:N-1$, $q=(q_{s-1},\dots,q_0)_n$.
Наряду с сигналом $x\in\cn$ рассмотрим сигнал $\tilde x(j)=x(j\omn q)$,
$j\in0:N-1$. Пусть $H_f(x)=\lb\alpha;\ \xn(\sigma,p)\rb$,
$H_f(\tilde x)=\lb\tilde\alpha;\ \tilde\xn(\sigma,p)\rb$.
Тогда $\tilde\alpha=\alpha$ и}
$$
 \tilde\xn(\sigma,p)=\wn^{-\sigma\qnn}\,
 \xn\big(\sigma,\,p\omn\lf q/\Dnn\rf\big),
$$
$$
 p\in0:\nn-1,\quad \sigma\in1:n-1,\quad \nu\in1:s.
$$

\proof
Согласно (2.8) и (2.6)
$$
 x(j\omn q)=\alpha+\sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{k=0}^{\nn-1}
 \xn(\sigma,k)\,\fn\big(\sigma;\,(j\omn q)\omn k\Dnn\big).
$$
Так как
$$
 (j\omn q)\omn k\Dnn=j\omn(q\opn k\Dnn)=
 j\omn\big((\lf q/\Dnn\rf\opn k)\Dnn+\qnn\Dn+\la q\ra_\Dn\big),
$$
то в силу (2.4) имеем
$$
 x(j\omn q)=\alpha+\sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{k=0}^{\nn-1}
 \xn(\sigma,k)\,\wn^{-\sigma\qnn}\,
 \fn\big(\sigma;\,j-(\lf q/\Dnn\rf\opn k)\Dnn\big).
$$
Произведя замену $p=k\opn\lf q/\Dnn\rf$, получим
$$
 x(j\omn q)=\alpha+\sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{p=0}^{\nn-1}
 \xn(\sigma,\,p\omn\lf q/\Dnn\rf)\,\wn^{-\sigma\qnn}\,
 \fn(\sigma;\,j-p\Dnn).
$$
Остается учесть единственность разложения по ортогональному базису. \qed

\medskip
Перейдем к вопросу о спектре свертки. Пусть $x,\,y\in\cn$; сигнал $z$,
формируемый по правилу
$$
 z(j)=\sum_{k=0}^{N-1}x(k)\,y(j\omn k),\quad j\in0:N-1,         \eqno(2.9)
$$
называется {\it $n$-сверткой}\/ сигналов $x$ и $y$.

\medskip
{\bf Теорема 2.2.} {\it Пусть $z$ --- $n$-свертка сигналов $x$ и $y$,
$H_f(x)=\lb\alpha;\ \xn(\sigma,p)\rb$, $H_f(y)=\lb\beta;\ \yn(\sigma,p)\rb$,
$H_f(z)=\lb\gamma;\ \zn(\sigma,p)\rb$.
Тогда $\gamma=\alpha\beta N$ и}
$$
 \zn(\sigma,p)=n^\nu\sum_{q=0}^{\nn-1}
 \xn(\sigma,q)\,\yn(\sigma,\,p\omn q),
$$
$$
 p\in0:\nn-1,\quad \sigma\in1:n-1,\quad \nu\in1:s.
$$

\proof
По предыдущей теореме
$$
 y(j\omn k)=y(k^*\omn j^*)=
$$
$$
 =\beta+
 \sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{l=0}^{\nn-1}
 \wn^{-\sigma j^*_{\nu-1}}\,\yn(\sigma,\,l\omn\lf j^*/\Dnn\rf)\,
 \fn(\sigma;\,k^*-l\Dnn).                                       \eqno(2.10)
$$
Согласно (2.6) и (2.7)
$$
 \fn(\sigma;\,k^*-l\Dnn)=\fn(\sigma;\,k^*\omn l\Dnn)=
 \overline{\fn}(\sigma;\,k\omn l^*\Dnn)=
 \overline{\fn}(\sigma;\,k-l^*\Dnn).
$$
Произведя в (2.10) замену $q=l^*$, с учетом предыдущего равенства получим
$$
 y(j\omn k)=\beta+\sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{q=0}^{\nn-1}
 \wn^{\sigma\jnn}\,\yn(\sigma,\,q^*\opn\lf j/\Dnn\rf)\,
 \overline{\fn}(\sigma;\,k-q\Dnn).                              \eqno(2.11)
$$
Как уже упоминалось, базис (1.1) является ортогональным; кроме того,
известно~[9], что $\|\fn(\sigma;\cdot-q\Dnn)\|^2=n^\nu$. Учитывая эти факты,
а также формулы~(2.8), (2.11) и определение~(2.9), запишем
$$
 z(j)=\alpha\beta N+\sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{q=0}^{\nn-1}
 \xn(\sigma,q)\,\wn^{\sigma\jnn}\,\yn(\sigma,\,q^*\opn\lf j/\Dnn\rf)\,
 n^\nu.
$$
Но в силу (2.2)
$$
 \wn^{\sigma\jnn}\,\yn(\sigma,\,q^*\opn\lf j/\Dnn\rf)=
 \sum_{p=0}^{\nn-1} \yn(\sigma,\,q^*\opn p)\,\wn^{\sigma\jnn}\,
 \delta_\nn\big(\lf j/\Dnn\rf-p\big)=
$$
$$
 =\sum_{p=0}^{\nn-1} \yn(\sigma,\,p\omn q)\,\fn(\sigma;\,j-p\Dnn).
$$
Значит,
$$
 z(j)=\alpha\beta N+\sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{p=0}^{\nn-1}
 \Bigg\lb
  n^\nu\sum_{q=0}^{\nn-1} \xn(\sigma,q)\,\yn(\sigma,\,p\omn q)
 \Bigg\rb \fn(\sigma;\,j-p\Dnn).
$$

Теорема доказана. \qed

\medskip
Пусть $x,\,y\in\cn$. Сигнал $r$, формируемый по правилу
$$
 r(j)=\sum_{k=0}^{N-1}x(k)\,\overline y(k\omn j),
 \quad j\in0:N-1,                                               \eqno(2.12)
$$
называется {\it $n$-корреляцией}\/ сигналов $x$ и $y$.

\medskip
{\bf Теорема 2.3.} {\it Пусть $r$ --- $n$-корреляция сигналов $x$ и $y$,
$H_f(x)=\lb\alpha;\ \xn(\sigma,p)\rb$, $H_f(y)=\lb\beta;\ \yn(\sigma,p)\rb$,
$H_f(r)=\lb\varrho;\ \rn(\sigma,p)\rb$.
Тогда $\varrho=\alpha\overline\beta N$ и}
$$
 \rn(\sigma,p)=n^\nu\sum_{q=0}^{\nn-1}
 \xn(\sigma,q)\,\overline{\yn}(\sigma,\,q\omn p),
$$
$$
 p\in0:\nn-1,\quad \sigma\in1:n-1,\quad \nu\in1:s.
$$

\proof Сигнал (2.12) представляет собой $n$-свертку сигналов $x$ и $v$, где
$$
 v(j)=\overline y(j^*),\quad j\in0:N-1.
$$
Согласно (2.6) и (2.7)
$$
 v(j)=\overline\beta+
 \sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{p=0}^{\nn-1}
 \overline{\yn}(\sigma,p)\,\overline{\fn}(\sigma;\,j^*-p\Dnn)=
$$
$$
 =\overline\beta+
 \sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{p=0}^{\nn-1}
 \overline{\yn}(\sigma,p)\,\fn(\sigma;\,j-p^*\Dnn).
$$
Отсюда по теореме 2.2 получаем $\varrho=\alpha\overline\beta N$,
$$
 \rn(\sigma,p)=n^\nu\sum_{q=0}^{\nn-1}
 \xn(\sigma,q)\,v_\nu(\sigma,\,p\omn q)=
 n^\nu\sum_{q=0}^{\nn-1} \xn(\sigma,q)\,\overline{\yn}(\sigma,\,q\omn p),
$$
$$
 p\in0:\nn-1,\quad \sigma\in1:n-1,\quad \nu\in1:s.
$$

Теорема доказана. \qed

\bigskip
{\large\bf\leftline{3. Базис \hc, связанный с прореживанием}}
{\large\bf\leftline{\quad\,по времени, и оператор циклического сдвига}}
\medskip

Обратимся к вейвлетному базису (1.2).

\medskip
{\bf Лемма 3.1.} {\it При $\sigma\in1:n-1$ справедлива формула}
$$
 \gn(\sigma;\,j)=\wn^{\sigma\lf j/\nn\rf}\,
 \delta_\nn(j),\quad j\in\bmz.                                  \eqno(3.1)
$$

\proof
Сигнал $\gn(\sigma;\,j)$ в силу (1.4) является $\nnn$-периодическим.
Тем же свойством обладает и сигнал, стоящий в правой части~(3.1). Значит,
равенство~(3.1) достаточно проверить на основном периоде $0:\nnn-1$.

Пусть $j=\tau\nn$ при некотором $\tau\in0:n-1$. Тогда правая часть~(3.1)
принимает значение $\wn^{\sigma\tau}$. Это же значение согласно~(1.4)
принимает и $\gn(\sigma;\,j)$. При остальных $j\in0:\nnn$ равенство~(3.1)
превращается в $0=0$. Лемма доказана. \qed

\medskip
{\bf Следствие.} {\it При $p\in0:\nn-1$ справедливо равенство}
$$
 \gn(\sigma;\,j-p)=\wn^{\sigma\lf j/\nn\rf}\,
 \delta_\nn(j-p),\quad j\in\bmz.                                \eqno(3.2)
$$

\proof
Покажем, что
$$
 \wn^{\sigma\lf(j-p)/\nn\rf}\,\delta_\nn(j-p)=
 \wn^{\sigma\lf j/\nn\rf}\,\delta_\nn(j-p).                     \eqno(3.3)
$$
Поскольку в обеих частях этого равенства стоят $\nnn$-периодические по $j$
сигналы, то достаточно проверить его на периоде $p:p+\nnn-1$.
При $j=p+\tau\nn$, $\tau\in0:n-1$, равенство~(3.3) верно. Но оно также верно
и при остальных $j$ из указанного периода, поскольку в этом случае обе
части~(3.3) равны нулю. Таким образом, равенство~(3.3) при $p\in0:\nn-1$ и
$j\in\bmz$ установлено.

Теперь (3.2) следует из (3.1) и (3.3). \qed

\medskip
Формулы (3.1) и (3.2) принимают более простой вид при $j\in0:N-1$. А именно,
если $j=(j_{s-1},\dots,j_0)_n$, то
$$
 \Big\lf\frac j\nn\Big\rf=j_{s-1}n^{\nu-1}+\dots+j_{s-\nu+1}\,n+j_{s-\nu},
$$
так что
$$
 \wn^{\lf j/\nn\rf}=\wn^{j_{s-\nu}}.                            \eqno(3.4)
$$

\medskip
{\bf Лемма 3.2.} {\it При всех целых $j$ и $p$}
$$
 \gn(\sigma;\,j-p)=\wn^{\sigma\lf p/\nn\rf}\,
 \gn\big(\sigma;\,j-\la p\ra_\nn\big).                          \eqno(3.5)
$$

\proof
Согласно (3.1) при $j,\,k\in\bmz$ имеем
$$
 \gn(\sigma;\,j-k\nn)=\wn^{\sigma k}\,\gn(\sigma;\,j).          \eqno(3.6)
$$
Поскольку $p=\lf p/\nn\rf\nn+\la p\ra_\nn$, то
$$
 j-p=\big(j-\la p\ra_\nn\big)-\lf p/\nn\rf\nn.
$$
Остается воспользоваться формулой (3.6). \qed

\medskip
{\bf Лемма 3.3.} {\it При $\sigma\in1:n-1$ справедливы тождества}
$$
 \gn(\sigma;\,-j)=\overline{\gn}(\sigma;\,j)=\gn(n-\sigma;\,j),
 \quad j\in\bmz.                                                \eqno(3.7)
$$

\proof
Проверим, что
$$
 \wn^{\sigma\lf-j/\nn\rf}\,\delta_\nn(j)=
 \wn^{-\sigma\lf j/\nn\rf}\,\delta_\nn(j),\quad j\in\bmz        \eqno(3.8)
$$
Действительно, если $j=k\nn$ при некотором $k\in\bmz$, то левая и правая
часть~(3.8) равна $\wn^{-\sigma k}$. При остальных $j\in\bmz$ обе части
равенства~(3.8) равны нулю.

Перейдем к доказательству равенства (3.7). Согласно (3.1) и (3.8) имеем
$$
 \gn(\sigma;\,-j)=\wn^{\sigma\lf-j/\nn\rf}\,\delta_\nn(-j)=
 \wn^{-\sigma\lf j/\nn\rf}\,\delta_\nn(j)=\overline{\gn}(\sigma;\,j).
$$
С другой стороны,
$$
 \wn^{-\sigma\lf j/\nn\rf}\,\delta_\nn(j)=
 \wn^{(n-\sigma)\lf j/\nn\rf}\,\delta_\nn(j)=\gn(n-\sigma;\,j).
$$

Лемма доказана. \qed

\bigskip
Любой сигнал $x\in\cn$ можно разложить по ортогональному базису~(1.2):
$$
 x(j)=\alpha'+\sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{p=0}^{\nn-1}
 \xpn(\sigma,p)\,\gn(\sigma;\,j-p),\quad j\in\bmz.              \eqno(3.9)
$$
Здесь
$$
 \alpha'=\frac1N\sum_{j=0}^{N-1}x(j),\qquad
 \xpn(\sigma,p)=\frac1{n^\nu}\sum_{j=0}^{N-1}x(j)\,
 \overline{\gn}(\sigma;\,j-p).
$$
Совокупность коэффициентов этого разложения
$$
 H_g(x)=\big\lb\alpha';\ \xpn(\sigma,p),\
 p\in0:\nn-1,\ \sigma\in1:n-1,\ \nu\in1:s\big\rb
$$
образует {\it спектр \hc}\/ сигнала $x$, {\it связанный с прореживанием по
времени}. Преобразование $x\to H_g(x)$ называется {\it дискретным
преобразованием \hc\ с прореживанием по времени}.

Установим связь между спектрами исходного и сдвинутого сигнала.

\medskip
{\bf Теорема 3.1.} {\it Зафиксируем $q\in0:N-1$.
Наряду с сигналом $x\in\cn$ рассмотрим сигнал $\tilde x(j)=x(j-q)$.
Пусть $H_g(x)=\lb\alpha';\ \xpn(\sigma,p)\rb$,
$H_g(\tilde x)=\lb\tilde\alpha';\ \tilde\xpn(\sigma,p)\rb$.
Тогда $\tilde\alpha'=\alpha'$ и}
$$
 \tilde\xpn(\sigma,p)=\wn^{-\sigma\lf(p-q)/\nn\rf}\,
 \xpn\big(\sigma,\,\la p-q\ra_\nn\big),
$$
$$
 p\in0:\nn-1,\quad \sigma\in1:n-1,\quad \nu\in1:s.
$$

\proof
Согласно (3.9) и (3.5) имеем
$$
 x(j-q)=\alpha'+\sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{k=0}^{\nn-1}
 \xpn(\sigma,k)\,\gn(\sigma;\,j-q-k)=
$$
$$
 =\alpha'+\sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{k=0}^{\nn-1}
 \xpn(\sigma,k)\,\wn^{\sigma\lf(q+k)/\nn\rf}\,
 \gn\big(\sigma;\,j-\la q+k\ra_\nn\big).
$$
Произведем замену $p=\la q+k\ra_\nn$. В этом случае $k=\la p-q\ra_\nn$ и
$$
 \Big\lf\frac{q+k}\nn\Big\rf=\Big\lf\frac{q+\la p-q\ra_\nn}\nn\Big\rf=
 \lf q/\nn\rf+\Big\lf\frac{\la q\ra_\nn+\la p-q\ra_\nn}\nn\Big\rf.
$$
Отметим, что
$$
 \Big\lf\frac{\la q\ra_\nn+\la p-q\ra_\nn}\nn\Big\rf=
  \left\lb
   \begin{array}{rl}
    0,&\mbox{\rm если}\ p\ge\la q\ra_\nn\\
    1,&\mbox{\rm если}\ p < \la q\ra_\nn
   \end{array}
  \right\rb
 =-\Big\lf\frac{p-\la q\ra_\nn}\nn\Big\rf.
$$
Значит,
$$
 \Big\lf\frac{q+k}\nn\Big\rf=
 \lf q/\nn\rf-\Big\lf\frac{p-\la q\ra_\nn}\nn\Big\rf=
 -\left(\Big\lf\frac{p-\la q\ra_\nn}\nn\Big\rf-\lf q/\nn\rf\right)=
 -\Big\lf\frac{p-q}\nn\Big\rf.
$$
Окончательно получаем
$$
 x(j-q)=\alpha'+\sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{p=0}^{\nn-1}
 \xpn\big(\sigma,\la p-q\ra_\nn\big)\,
 \wn^{-\sigma\lf(p-q)/\nn\rf}\,\gn(\sigma;\,j-p).
$$

Теорема доказана. \qed

\medskip
Перейдем к вопросу о спектре свертки. Напомним, что циклической сверткой
сигналов $x$ и $y$ из $\cn$ называется сигнал $z=x*y$ с компонентами
$$
 z(j)=\sum_{k=0}^{N-1}x(k)\,y(j-k),\quad j\in\bmz.              \eqno(3.10)
$$

\medskip
{\bf Теорема 3.2.} {\it Пусть $z$ --- циклическая свертка сигналов $x$ и $y$,
$H_g(x)=\lb\alpha';\ \xpn(\sigma,p)\rb$,
$H_g(y)=\lb\beta';\ \ypn(\sigma,p)\rb$,
$H_g(z)=\lb\gamma';\ \zpn(\sigma,p)\rb$.
Тогда $\gamma'=\alpha'\beta' N$ и}
$$
 \zpn(n-\sigma,\,p)=n^\nu\Bigg\lb
 \sum_{q=0}^{p} \xpn(\sigma,q)\,\ypn(\sigma,\,p-q)+
 \wn^\sigma\sum_{q=p+1}^{\nn-1} \xpn(\sigma,q)\,\ypn(\sigma,\,\nn+p-q)
 \Bigg\rb,
$$
$$
 p\in0:\nn-1,\quad \sigma\in1:n-1,\quad \nu\in1:s.
$$

\proof
По теореме 3.1
$$
 y(j-k)=y\big(-k-(-j)\big)=
$$
$$
 =\beta'+
 \sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{l=0}^{\nn-1}
 \wn^{-\sigma\lf(l+j)/\nn\rf}\,\ypn\big(\sigma,\la l+j\ra_\nn)\,
 \gn(\sigma;\,-k-l).
$$
Сделаем замену $q=\la-l\ra_\nn$. Тогда $l=\la-q\ra_\nn$.

При $q\in1:\nn-1$ получаем $\big\la\la-q\ra_\nn+j\big\ra_\nn=\la j-q\ra_\nn$,
$$
 \Big\lf\frac{\la-q\ra_\nn+j}\nn\Big\rf=
 \Big\lf\frac{\nn-q+j}\nn\Big\rf=\Big\lf\frac{j-q}\nn\Big\rf+1.
$$
Кроме того, в силу (3.6)
$$
 \gn\big(\sigma;\,-k-\la-q\ra_\nn\big)=\gn(\sigma;\,-k-\nn+q)=
 \wn^\sigma\,\gn(\sigma;\,q-k).
$$
Таким образом, слагаемое с индексом $q$ имеет вид
$$
 \wn^{-\sigma\lf(j-q)/\nn\rf}\,\ypn\big(\sigma,\la j-q\ra_\nn)\,
 \gn(\sigma;\,q-k).                                             \eqno(3.11)
$$

При $q=0$ получаем $\la-q\ra_\nn=0$; слагаемое с индексом $q=0$ имеет вид
$\wn^{-\sigma\lf j/\nn\rf}\times$\linebreak   %% убрать \linebreak и \times,
                                              %% если строчка удлинится
$\times\,\ypn\big(\sigma,\la j\ra_\nn)\,\gn(\sigma;\,-k)$,
что формально совпадает с~(3.11).

Учитывая сказанное выше и лемму 3.3, приходим к равенству
$$
 y(j-k)=\beta'+
 \sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{q=0}^{\nn-1}
 \wn^{-\sigma\lf(j-q)/\nn\rf}\,\ypn\big(\sigma,\la j-q\ra_\nn\big)\,
 \overline{\gn}(\sigma;\,k-q).                                  \eqno(3.12)
$$

Как уже упоминалось, базис (1.2) является ортогональным; кроме того~[9],
\linebreak  %% убрать \linebreak,
            %% если строчка удлинится
$\|\gn(\sigma;\cdot-q)\|^2=n^\nu$. Опираясь на эти факты, а также на
формулы~(3.9), (3.12) и определение~(3.10), запишем
$$
 z(j)=\alpha'\beta' N+\sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{q=0}^{\nn-1}
 \xpn(\sigma,q)\,\wn^{-\sigma\lf(j-q)/\nn\rf}\,
 \ypn\big(\sigma,\,\la j-q\ra_\nn\big)\,n^\nu.
$$
Но
$$
 \wn^{-\sigma\lf(j-q)/\nn\rf}\,\ypn\big(\sigma,\,\la j-q\ra_\nn\big)=
 \wn^{-\sigma\lf j/\nn\rf}\,
 \wn^{-\sigma\left\lf(\la j\ra_\nn-q)/\nn\right\rf}\,
 \ypn\big(\sigma,\,\big\la\la j\ra_\nn-q\big\ra_\nn\big)=
$$
$$
 =\wn^{-\sigma\lf j/\nn\rf}\,\sum_{p=0}^{\nn-1}\wn^{-\sigma\lf(p-q)/\nn\rf}\,
 \ypn\big(\sigma,\,\la p-q\ra_\nn\big)\,\delta_\nn\big(\la j\ra_\nn-p\big).
$$
Согласно (3.2) и (3.7)
$$
 \wn^{-\sigma\lf j/\nn\rf}\,\delta_\nn\big(\la j\ra_\nn-p\big)=
 \wn^{-\sigma\lf j/\nn\rf}\,\delta_\nn(j-p)=\gn(n-\sigma;\,j-p),
$$
поэтому
$$
 z(j)=\alpha'\beta' N+\sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{p=0}^{\nn-1}
 \!\Bigg\lb n^\nu\sum_{q=0}^{\nn-1}
 \xpn(\sigma,q)\,\wn^{-\sigma\lf(p-q)/\nn\rf}\,
 \ypn\big(\sigma,\,\la p-q\ra_\nn\big)\Bigg\rb\,
 \gn(n-\sigma;\,j-p).
$$
Осталось заметить, что
$$
 \sum_{q=0}^{\nn-1} \wn^{-\sigma\lf(p-q)/\nn\rf}\,
 \xpn(\sigma,q)\,\ypn\big(\sigma,\,\la p-q\ra_\nn\big)=
$$
$$
 =\sum_{q=0}^{p} \xpn(\sigma,q)\,\ypn(\sigma,p-q)+
 \wn^\sigma\sum_{q=p+1}^{\nn-1}\xpn(\sigma,q)\,\ypn(\sigma,\nn+p-q).
$$

Теорема доказана. \qed

\medskip
Напомним, что циклической корреляцией сигналов $x$ и $y$ из $\cn$
называется сигнал $r$ с компонентами
$$
 r(j)=\sum_{k=0}^{N-1}x(k)\,\overline{y}(k-j),\quad j\in\bmz.   \eqno(3.13)
$$

\medskip
{\bf Теорема 3.3.} {\it Пусть $r$ --- циклическая корреляция сигналов $x$ и
$y$, $H_g(x)=\lb\alpha';\ \xpn(\sigma,p)\rb$,
$H_g(y)=\lb\beta';\ \ypn(\sigma,p)\rb$,
$H_g(r)=\lb\varrho';\ \rpn(\sigma,p)\rb$.
Тогда $\varrho'=\alpha'\overline{\beta'}N$ и}
$$
 \rpn(n-\sigma,\,p)=n^\nu\Bigg\lb
 \sum_{q=p}^{\nn-1} \xpn(\sigma,q)\,\overline{\ypn}(\sigma,\,q-p)+
 \wn^{-\sigma}\sum_{q=0}^{p-1} \xpn(\sigma,q)\,
 \overline{\ypn}(\sigma,\,\nn+q-p) \Bigg\rb,
$$
$$
 p\in0:\nn-1,\quad \sigma\in1:n-1,\quad \nu\in1:s.
$$

\proof
Сигнал (3.13) есть циклическая свертка сигнала $x$ с сигналом
$$
 v(j):=\overline{y}(-j)=\overline{\beta'}+
 \sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{p=0}^{\nn-1}
 \overline{\ypn}(\sigma,p)\,\overline{\gn}(\sigma;\,-j-p)=
$$
$$
 =\overline{\beta'}+\sum_{\nu=1}^{s}\sum_{\sigma=1}^{n-1}\sum_{p=0}^{\nn-1}
 \overline{\ypn}(\sigma,p)\,\gn(\sigma;\,j+p).
$$
Мы воспользовались формулой (3.7).

Найдем спектр \hc\ сигнала $v$. При $p\in1:\nn-1$ согласно~(3.6) имеем
$$
 \gn(\sigma;\,j+p)=\wn^{-\sigma}\,\gn(\sigma;\,j+p-\nn)=
 \wn^{-\sigma}\,\gn\big(\sigma;\,j-(\nn-p)\big),
$$
поэтому
$$
 v'_\nu(\sigma,p)=\wn^{-\sigma}\,\overline{\ypn}(\sigma,\nn-p),
$$
$$
 p\in1:\nn-1,\quad \sigma\in1:n-1,\quad \nu\in1:s.
$$
При этом, очевидно, $v'_\nu(\sigma,0)=\overline{\ypn}(\sigma,0)$,
$\sigma\in1:n-1$, $\nu\in1:s$.

По теореме 3.2 получаем $\varrho'=\alpha'\overline{\beta'}N$,
$$
 \rpn(n-\sigma,\,p)=n^\nu\Bigg\lb
 \sum_{q=0}^{p-1} \xpn(\sigma,q)\,v'_\nu(\sigma,\,p-q)+
 \xpn(\sigma,p)\,v'_\nu(\sigma,\,0)+
$$
$$
 +\wn^\sigma\sum_{q=p+1}^{\nn-1} \xpn(\sigma,q)\,
 v'_\nu(\sigma,\,\nn+p-q)\Bigg\rb=
$$
$$
 =n^\nu\Bigg\lb \wn^{-\sigma} \sum_{q=0}^{p-1}
 \xpn(\sigma,q)\,\overline{\ypn}(\sigma,\,\nn+q-p)+
 \xpn(\sigma,p)\,\overline{\ypn}(\sigma,\,0)%+
%$$
%$$
 +\sum_{q=p+1}^{\nn-1} \xpn(\sigma,q)\,
 \overline{\ypn}(\sigma,\,q-p) \Bigg\rb.
$$

Теорема доказана. \qed

\newpage
%\bigskip
{\large\bf\leftline{Литература}}

\begin{enumerate}
\item {\it Айзенберг Н. Н., Трофимлюк О. Т.}
      Сдвиг, свертка и корреляционная функция дискретных сигналов
      в произвольном базисе
      // ДАН СССР. 1980. Т.~250. \No~1. С.~47--51.
\item {\it Кухарев Г. А.}
      Основные теоремы сдвига, свертки и корреляции для задач
      циф\-ровой обработки сигналов
      // Изв. вузов. Радиоэлектроника. 1985. Т.~28. \No~8. С.~26--31.
\item {\it Daubechies I.}
      The wavelet transform, time-frequency localization and signal analysis
      // IEEE Trans. Inform. Theory. 1990. No.~5. P.~961--1005.
\item {\it Петухов А. П.}
      Периодические дискретные всплески.
      // Алгебра и анализ. 1996. Т.~8. \No~3. С.~151--183.
\item {\it Malozemov V. N., Masharsky S. M.}
      Haar spectra of discrete signals.
      In: Tools for Math. Modelling. The Second International Conf.
      June 14--19, 1999. Abstracts. St.~Petersburg, 1999.P.~86--87.
\item {\it Малоземов В. Н., Машарский С. М.}
      Сравнительное изучение двух вейвлетных базисов
      // Проблемы передачи информации. 2000. Т.~36. Вып.~2.
\item {\it Малоземов В. Н., Машарский С. М.}
      Хааровские спектры дискретных сверток
      // Журн. вычисл. мат. и матем. физ. 2000. Т.~40. \No~6.
\item {\it Дагман Э. Е., Кухарев Г. А.}
      Быстрые дискретные ортогональные преобразования.
      Новосибирск: Наука, 1983. 232~с.
\item {\it Малоземов В. Н., Машарский С. М.}
      Обобщенные вейвлетные базисы, связанные с дискретным
      преобразованием \vc{}
      // Электронный архив препринтов С.-Петербургского мат. общества.
      Препринт \No~1999-21.\\
      {\sf http://www.mathsoc.spb.ru/preprint/1999/index.html\#21}
\end{enumerate}

\end{document}