12.5: Transformaciones teóricas numéricas para convolución

Última actualización
Guardar como PDF

Page ID: 87087

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

Aquí observamos las condiciones colocadas en una transformada lineal general para que pueda soportar la convolución cíclica. La forma de una transformación lineal de una secuencia longitud-N de número viene dada por

\[X(k)=\sum_{n=0}^{N-1}t(n,k)x(n) \nonumber \]

para$k=0,1,...,(N-1)$. La definición de convolución cíclica de dos secuencias viene dada por

\[y(n)=\sum_{m=0}^{N-1}x(m)h(n-m) \nonumber \]

para$n=0,1,...,(N-1)$ y todos los índices evaluados módulo$N$. Nos gustaría encontrar las propiedades de la transformación tales que soportará la convolución cíclica. Esto significa que si$X(k),\; H(k),\; Y(k)$ son las transformaciones de$x(n),\; h(n),\; y(n)$ respectivamente,

\[Y(k)=X(k)H(k) \nonumber \]

Las condiciones se derivan tomando la transformada definida en las ecuaciones anteriores de ambos lados de la ecuación que da

\[Y(k)=\sum_{n=0}^{N-1}t(n,k)\sum_{m=0}^{N-1}x(m)h(n-m) \nonumber \]

\[Y(k)=\sum_{m=0}^{N-1}\sum_{n=0}^{N-1}x(m)h(n-m)t(n,k) \nonumber \]

Haciendo el cambio de las variables de índice,$l=n-m$ da

\[Y(k)=\sum_{m=0}^{N-1}\sum_{l=0}^{N-1}x(m)h(l)t(l+m,k) \nonumber \]

Pero a partir de la ecuación, esto debe ser

\[Y(k)=\sum_{n=0}^{N-1}x(n)t(n,k)\sum_{m=0}^{N-1}x(m)t(m,k) \nonumber \]

\[Y(k)=\sum_{m=0}^{N-1}\sum_{l=0}^{N-1}x(m)h(l)t(n,k)t(l,k) \nonumber \]

Esto debe ser cierto para todos$\(x(n),\; h(n)$ y$k$, por lo tanto de las ecuaciones anteriores tenemos

\[t(m+l,k)=t(m,k)t(l,k) \nonumber \]

Para$l=0$ nosotros tenemos

\[t(m,k)=t(m,k)t(0,k) \nonumber \]

Por lo tanto,$t(0,k)=1$. Para$l=m$ nosotros tenemos

\[t(2m,k)=t(m,k)t(m,k)=t^2(m,k) \nonumber \]

Porque de igual manera$l=pm$ tenemos

\[t(pm,k)=t^p(m,k) \nonumber \]

Por lo tanto,

\[t^N(m,k)=t(Nm,k)=t(0,k)=1 \nonumber \]

Pero

\[t(m,k)=t^m(1,k)=t^k(m,1) \nonumber \]

Por lo tanto,

\[t(m,k)=t^{mk}(1,1) \nonumber \]

Definir$t(1,1)=\alpha$ da la forma para nuestra ecuación de transformación lineal general como

\[X(k)=\sum_{n=0}^{N-1}\alpha ^{nk}x(n) \nonumber \]

donde$\alpha$ es una raíz de orden$N$ $N “role="presentation” style="position:relative;” tabindex="0">$

La siguiente tabla da posibles parámetros para varios módulos de números Fermat.

t	b	$M=F_t$	$N_2$	$N_{\sqrt{2}}$	$N_{max}$	$\alpha \: \text{for}\: N_{max}$

3	8	$2^8+1$	16	32	256	3
4	16	$2^{16}+1$	32	64	65536	3
5	32	$2^{32}+1$	64	128	128	$\sqrt{2}$
6	64	$2^{64}+1$	128	256	256	$\sqrt{2}$

Tabla 12.5.1 Módulos de números Fermat

t	b	\(M=F_t\)	\(N_2\)	\(N_{\sqrt{2}}\)	\(N_{max}\)	\(\alpha \: \text{for}\: N_{max}\)

3	8	\(2^8+1\)	16	32	256	3
4	16	\(2^{16}+1\)	32	64	65536	3
5	32	\(2^{32}+1\)	64	128	128	\(\sqrt{2}\)
6	64	\(2^{64}+1\)	128	256	256	\(\sqrt{2}\)