12.4: Convolución rápida directa y transformadas rectangulares

Última actualización
Guardar como PDF

Page ID: 87086

\( \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}}\)

Un enfoque relativamente nuevo utiliza el mapeo de índices directamente para convertir una convolución unidimensional en una convolución multidimensional. Esto se puede hacer mediante un mapa tipo-1 o tipo-2. Las circunvoluciones cortas a lo largo de cada dimensión son realizadas por los algoritmos óptimos de Winograd. A diferencia del caso de la DFT, no hay ahorros de aritmética solo a partir del mapeo de índices. Todo el ahorro proviene de algoritmos cortos eficientes. En el caso del mapeo de índices con convolución, las multiplicaciones deben anidarse juntas en el centro del algoritmo de la misma manera que para el WFTA. No hay equivalente a la estructura de PFA para convolución. La convolución multidimensional no se puede calcular por circunvoluciones de fila y columna, ya que la DFT fue por DFT de fila y columna.

Primero parecería que aplicar el mapeo de índices y algoritmos cortos óptimos directamente a la convolución sería más eficiente que usar DFT y convertirlos en convolución para ser calculados por los mismos algoritmos óptimos. En algoritmos prácticos, sin embargo, el método DFT parece ser más eficiente.

Un método que es atractivo para hardware de propósito especial utiliza aritmética distribuida. Este enfoque utiliza una búsqueda de tabla de productos parciales precalculados para producir un sistema que hace convolución sin requerir multiplicaciones.

Otro método que requiere hardware especial utiliza transformadas teóricas numéricas para calcular la convolución. Estas transformadas se definen sobre campos finitos o anillos con aritmética realizada módulo números especiales. Estas transformadas tienen una flexibilidad bastante limitada, pero cuando se pueden usar, son muy eficientes.

Colaborador

ContribeeBurrus