Saltar al contenido principal
LibreTexts Español

1.1: Introducción

  1. Última actualización
  2. Guardar como PDF
  • Page ID
    87016

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

    El desarrollo de algoritmos rápidos suele consistir en utilizar propiedades especiales del algoritmo de interés para eliminar operaciones redundantes o innecesarias de una implementación directa. Debido a la periodicidad, simetrías y ortogonalidad de las funciones básicas y la relación especial con la convolución, la transformada discreta de Fourier (DFT) tiene una enorme capacidad de mejora de su eficiencia aritmética.

    Existen cuatro enfoques principales para formular algoritmos eficientes de DFT. Los dos primeros rompen un DFT en múltiples más cortos. Esto se hace en Mapeo de Índice Multidimensional mediante el uso de un mapa de índices y en la Descripción Polinómica de Señales por reducción polinómica. El tercero es Factorizar los Operadores de Procesamiento de Señal que factoriza el operador DFT (matriz) en factores dispersos. La DFT como convolución o filtrado desarrolla un método que convierte una DFT de longitud de inicialización en convolución cíclica. Todavía otro enfoque es interesante donde, para ciertos casos, la evaluación de la DFT puede plantearse recursivamente como evaluar una DFT en términos de dos DFT de media longitud que son evaluadas cada una a su vez por una DFT de un cuarto de longitud y así sucesivamente.

    Los teoremas de complejidad computacional muy importantes de Winograd se exponen y discuten brevemente en los algoritmos de DFT cortos de Winograd. Los detalles y evaluaciones específicos de la FFT Cooley-Tukey y la FFT Split-Radix se dan en el algoritmo de transformada rápida de Fourier Cooley-Tukey, y PFA y WFTA se cubren en Los algoritmos de transformada de Fourier de Factor Prime y Winograd. Una breve discusión sobre la convolución de alta velocidad se da en Algoritmos de Convolución, tanto por su propia importancia como por su conexión teórica con la DFT. También presentamos el chirp, Goertzel, QFT, NTT, SR-FFT, Approx FFT, Autogen y programas para implementar algunos de estos.

    Ivan Selesnick da una breve introducción en los algoritmos cortos de DFT de Winograd al uso de las técnicas de Winograd para dar un desarrollo altamente estructurado de FFT de corta duración y describe un programa que escribirá estos programas de manera automática. Markus Pueschel presenta su“role="presentación” style="position:relative;” tabindex="0">

    This page titled 1.1: Introducción is shared under a CC BY license and was authored, remixed, and/or curated by C. Sidney Burrus.