Esta es una de las transformadas de Fourier muy utilizadas en algoritmos de procesamiento de señales digitales (sus modificaciones se utilizan en compresión de audio en MP3, compresión de imágenes en JPEG, etc.), así como en otras áreas relacionadas con el análisis de frecuencias en formato discreto (por ejemplo, (por ejemplo, señal analógica digitalizada). Conversión discreta Fourier requiere como entrada función discreta. Estas funciones a menudo se crean mediante muestreo (muestreo de valores de funciones continuas). Las transformadas discretas de Fourier ayudan a resolver parciales ecuaciones diferenciales y realizar operaciones como convoluciones. Las transformadas discretas de Fourier también se utilizan activamente en estadística, en el análisis de series de tiempo. Las transformaciones pueden ser unidimensionales, bidimensionales e incluso tridimensionales.
Conversión directa:
Conversión inversa:
Designaciones:
§ norte- el número de valores de señal medidos durante un período, así como el número de componentes de descomposición;
§ - valores de señal medidos (en puntos de tiempo discretos con números, que son datos de entrada para conversión directa y datos de salida para conversión inversa;
§ - norte amplitudes complejas de señales sinusoidales que componen la señal original; son datos de salida para conversión directa y datos de entrada para conversión inversa; dado que las amplitudes son complejas, es posible calcular tanto la amplitud como la fase a partir de ellas;
§ es la amplitud habitual (real) de la k-ésima señal sinusoidal;
argumento( xk) - fase de la k-ésima señal sinusoidal (argumento de un número complejo);
§ k- frecuencia de la k-ésima señal, igual a , donde t- el período de tiempo durante el cual se tomaron los datos de entrada.
De esto último se desprende claramente que la transformación descompone la señal en componentes sinusoidales (que se denominan armónicos) con frecuencias desde N oscilaciones por período hasta una oscilación por período. Dado que la frecuencia de muestreo en sí es igual a N muestras por período, los componentes de alta frecuencia no se pueden mostrar correctamente: se produce un efecto muaré. Esto lleva al hecho de que la segunda mitad de las N amplitudes complejas es, de hecho, una imagen especular de la primera y no contiene información adicional.
Considere alguna señal periódica X(t) con un período igual a T. Expandámoslo en una serie de Fourier:
Muestreemos la señal de modo que haya N muestras por período. Representemos la señal discreta en forma de muestras: xn = X(Tennesse), donde , entonces estas lecturas a través de la serie de Fourier se escribirán de la siguiente manera:
Usando la relación: , obtenemos:
Dónde 
Así que tenemos transformada de Fourier discreta inversa.
Multipliquemos ahora escalarmente la expresión para xn encendido y obtenemos:
Aquí usamos: a) expresión para la suma Número finito miembros (expositor) progresión geométrica, y b) la expresión del símbolo de Kronecker como límite de la relación de las funciones de Euler para números complejos. Resulta que:
Esta fórmula describe transformada de Fourier discreta directa.
En la literatura, se acostumbra escribir el multiplicador en la transformación inversa y, por lo tanto, las fórmulas de transformación se suelen escribir de la siguiente forma:
La transformada discreta de Fourier es una transformación lineal que transforma un vector de muestras de tiempo en un vector de muestras espectrales de la misma longitud. Entonces la transformación se puede implementar como una multiplicación. matriz cuadrada para vectorizar:
Se proporciona el código del programa para la transformada de Fourier directa e inversa. Se considera la transformada rápida de Fourier.
La transformada discreta de Fourier (DFT) es herramienta poderosa análisis, que se utiliza ampliamente en el campo del procesamiento de señales digitales (DSP). Existen transformadas de Fourier directas e inversas. La transformada de Fourier discreta directa convierte una señal del dominio del tiempo al dominio de la frecuencia y se utiliza para analizar el espectro de frecuencia de la señal. La transformación inversa hace exactamente lo contrario: por espectro de frecuencia señal reconstruye la señal en el dominio del tiempo.
Para calcular la transformada de Fourier se suele utilizar un procedimiento de cálculo acelerado, el llamado. transformada rápida de Fourier (FFT). Esto le permite reducir significativamente el tiempo del procesador para cálculos matemáticos bastante complejos y que requieren muchos recursos.
1 Complejo números
Primero, necesitamos una clase auxiliar que describa números complejos. Los números complejos son clase especial Los números en matemáticas. Todo número complejo consta de dos partes: real e imaginaria. Ahora nos basta con saber acerca de los números complejos en relación con DFT que la parte real de un número complejo almacena información sobre la amplitud de la señal y la parte imaginaria almacena información sobre la fase.
Código de clase para describir números complejos.(giro alrededor) """2 Directo discreto rápido Transformada de Fourier
Se pasa una matriz de números complejos a la entrada de la función. La parte real representa una señal discreta arbitraria, con muestras a intervalos regulares. La parte imaginaria contiene ceros. El número de muestras en la señal debe ser igual a una potencia de dos. Si su señal es más corta, rellénela con ceros hasta un múltiplo de 2: 256, 512, 1024, etc. Cuanto más larga sea la señal, mayor será la resolución de frecuencia del espectro calculado.
Código para calcular la transformada rápida directa de Fourier en VB.NET(giro alrededor) """3 Inverso discreto rápido Transformada de Fourier
La transformada discreta inversa de Fourier (IDFT), una de las etapas de cálculo, incluye una DFT directa sobre una matriz de números complejos, donde la parte imaginaria es la inversión con respecto al eje X de la parte imaginaria del espectro.
Código para calcular la transformada rápida inversa de Fourier en VB.NET(giro alrededor) """Y, por supuesto, describiremos el método utilizado, que verifica el número de elementos de la matriz pasada:
"""
4 Comprobando hacia adelante y hacia atrás Transformada de Fourier
Ahora comprobemos que nuestras funciones funcionan. Para hacer esto, pasemos una señal arbitraria a través del mecanismo de transformada directa de Fourier y luego "ensamblemos" nuevamente usando la transformada inversa de Fourier. La señal reconstruida debería prácticamente coincidir con la original. Los errores de redondeo que ocurren cuando se trabaja con números en una computadora ocurren, por lo que las señales no serán completamente idénticas, pero su desviación entre sí debería ser insignificante.
Por ejemplo, tomemos la función seno como señal fuente y generemos datos con una longitud de 128 muestras como esta:
Dim cn(127) As ComplexNumber For i As Integer = 0 To cn.Length - 1 cn(i) = New ComplexNumber(Math.Sin(i * 3 * Math.PI / 180)) Siguiente
Obtenemos esta señal:
Aquí, el eje X es el número de muestras en el dominio del tiempo y el eje Y es la amplitud. Tenga en cuenta que la señal consta únicamente de partes reales y la parte imaginaria en todo el segmento es igual a "0".
Ahora pasemos esta señal a la entrada de la función FFT(). Usando las matrices de números complejos obtenidas durante la transformada directa de Fourier, construiremos dos gráficas: las partes real (Re) e imaginaria (Im) del espectro:
Aquí a lo largo del eje X están las lecturas en dominio de la frecuencia, a lo largo del eje Y - amplitud. Para obtener los valores de frecuencia reales es necesario calcularlos, teniendo en cuenta que el "0" del eje Y corresponde a la frecuencia cero, el máximo del eje Y corresponde a la frecuencia de muestreo.
Transferiremos el espectro de la señal resultante a la función de transformada de Fourier inversa IFFT(). Obtengamos una matriz de números complejos, donde la parte real contendrá la señal reconstruida:
Como puede ver, la señal reconstruida repite completamente la original.
Es conveniente analizar muchas señales descomponiéndolas en sinusoides (armónicos). Hay varias razones para esto. Por ejemplo, el oído humano funciona de forma similar. Descompone el sonido en vibraciones individuales de diferentes frecuencias. Además, se puede demostrar que las sinusoides son " funciones propias"sistemas lineales (ya que pasan a través de sistemas lineales, sin cambiar la forma, pero solo puede cambiar la fase y la amplitud). Otra razón es que el teorema de Kotelnikov se formula en términos del espectro de la señal.
La transformada de Fourier es la descomposición de funciones en sinusoides (en adelante también llamaremos funciones cosenos sinusoides, ya que se diferencian de las sinusoides "reales" sólo en fase). Existen varios tipos de transformada de Fourier.
1. No periódico señal continua se puede expandir a una integral de Fourier.
2. Una señal continua periódica se puede expandir a una serie infinita de Fourier.
3. Una señal discreta no periódica se puede expandir a una integral de Fourier.
4. Una señal discreta periódica se puede expandir a una serie finita de Fourier.
Una computadora sólo puede trabajar con una cantidad limitada de datos, por lo tanto, en realidad sólo puede calcular el último tipo de transformada de Fourier. Echemos un vistazo más de cerca.
DFT complejo
Hasta ahora hemos considerado las DFT a partir de señales reales. Generalicemos ahora la DFT al caso de señales complejas. Sea x[n], n=0,…,N-1 - la señal compleja original que consta de N números complejos. Denotemos X[k], k=0,…N-1 - su espectro complejo, que también consta de N números complejos. Entonces las siguientes fórmulas para directo y transformaciones inversas Fourier:
Si descomponemos una señal real en un espectro usando estas fórmulas, entonces los primeros N/2+1 coeficientes complejos del espectro coincidirán con el espectro de la DFT real "habitual", presentada en forma "compleja", y los coeficientes restantes será su reflexión simétrica con respecto a la mitad de la frecuencia de muestreo. Para coeficientes cosenos la reflexión es par y para coeficientes senos es impar.
DFT 2D
Para imágenes que son una señal bidimensional, el espectro también es una señal bidimensional. Las funciones básicas de la transformada de Fourier tienen la forma:
Además, las fases también pueden ser diferentes. En la imagen, cada una de estas funciones básicas representa una onda de una determinada frecuencia, una determinada orientación y una determinada fase.
Aquí N 1 xN 2 es el tamaño de la señal original, que también es el tamaño del espectro. k 1 y k 2 son los números de las funciones básicas (los números de los coeficientes de la DFT bidimensional en los que se encuentran estas funciones). Dado que el tamaño del espectro igual al tamaño señal fuente, entonces k 1 = 0,…,N 1 -1; k 2 = 0,…,norte 2 -1.
n 1 y n 2 son argumentos variables de las funciones básicas. Dado que el dominio de definición de las funciones base coincide con el dominio de definición de la señal, entonces n 1 = 0,...,N 1 -1; norte 2 = 0,…, norte 2 -1.
DFT 2D (en forma compleja) está determinado las siguientes fórmulas(aquí x es la señal original y X es su espectro):
El cálculo directo de una DFT bidimensional utilizando las fórmulas anteriores requiere enormes costos computacionales. Sin embargo, se puede demostrar que la DFT bidimensional tiene la propiedad de separabilidad, es decir se puede calcular secuencialmente a partir de dos dimensiones.
Para calcular una DFT bidimensional, basta con calcular las DFT complejas unidimensionales de todas las filas de la imagen y luego calcular las DFT complejas unidimensionales de todas las columnas de la "imagen" resultante.
En este caso, los resultados de todas las DFT complejas unidimensionales deben escribirse en lugar de los datos originales de estas DFT. Por ejemplo, al calcular el DFT unidimensional de la primera fila de una imagen, debe escribir el resultado DFT en la primera fila de esta imagen (tiene el mismo tamaño). Para hacer esto, necesita almacenar cada "píxel" como un número complejo.
De este modo, algoritmo eficiente Calcular la DFT de una imagen consiste en calcular las FFT unidimensionales primero de todas las filas y luego de todas las columnas de la imagen.
Dejar F(X 1 , X 2) – una función de dos variables. Por analogía con la transformada de Fourier unidimensional, podemos introducir una transformada de Fourier bidimensional:
La función para valores fijos de ω 1, ω 2 describe onda plana en el avión X 1 , X 2 (Figura 19.1).
Las cantidades ω 1, ω 2 tienen el significado de frecuencias espaciales y dimensión. milímetros−1, y la función F(ω 1, ω 2) determina el espectro de frecuencias espaciales. Una lente esférica es capaz de calcular el espectro de una señal óptica (Figura 19.2). En la Figura 19.2 se introducen las siguientes notaciones: φ - longitud focal,
Figura 19.1 - Para determinar frecuencias espaciales
La transformada de Fourier bidimensional tiene todas las propiedades de la transformada unidimensional; además, observamos dos propiedades adicionales, cuya prueba se desprende fácilmente de la definición de la transformada de Fourier bidimensional.
Figura 19.2 – Cálculo del espectro de una señal óptica utilizando
lente esférica
Factorización. Si se factoriza una señal bidimensional,
entonces su espectro también se factoriza:
Simetría radial . Si la señal bidimensional es radialmente simétrica, es decir
¿Dónde está la función de Bessel de orden cero? La fórmula que define la relación entre una señal bidimensional radialmente simétrica y su espectro espacial se llama transformada de Hankel.
TEMA 20. Transformada discreta de Fourier. Filtro de paso bajo
La transformada de Fourier discreta (DFT) bidimensional directa transforma una imagen dada una sistema coordinado (x,y), en una transformación de imagen discreta bidimensional especificada en un sistema de coordenadas de frecuencia ( u,v):
La transformada discreta inversa de Fourier (IDFT) tiene la forma:
Se puede observar que la DFT es transformación compleja. El módulo de esta transformación representa la amplitud del espectro de la imagen y se calcula como la raíz cuadrada de la suma de los cuadrados de las partes real e imaginaria de la DFT. La fase (ángulo de cambio de fase) se define como el arco tangente de la relación entre la parte imaginaria del DFT y la parte real. Espectro energético igual al cuadrado amplitud del espectro, o la suma de los cuadrados de las partes imaginaria y real del espectro.
Teorema de convolución
Según el teorema de convolución, la convolución de dos funciones en el dominio espacial se puede obtener mediante la ODFT del producto de su DFT, es decir
El filtrado en el dominio de la frecuencia le permite utilizar la DFT de la imagen para seleccionar la respuesta de frecuencia del filtro que proporciona la transformación de imagen necesaria. Veamos las características de frecuencia de los filtros más comunes.
En ingeniería de radio se utiliza a menudo el concepto de convolución de dos señales. Por ejemplo, la señal a la salida de una red de cuatro puertos se puede encontrar convolucionando la señal de entrada y la respuesta al impulso de la red de cuatro puertos. Dado que se consideraron señales discretas y digitales, definimos el concepto convolución para señales discretas , o convolución discreta.
Que haya una señal discreta. x D (t), que consiste en norte cuenta x k, y una señal discreta y d (G), que consta de norte cuenta Reino Unido, Entonces convolución discreta estas dos señales se llaman señal zA(t), para cual
Las señales discretas se han generalizado en la creación de sistemas de modulación de impulsos.
En el caso más simple, el dispositivo de muestreo es una cascada cerrada (llave) que se abre por un tiempo. t y con el período A (Fig. 4.7).
Arroz. 4.
El intervalo de muestreo A puede ser constante (muestreo uniforme) o variable (muestreo adaptativo). La forma más común de discretización es la uniforme, que se basa en el teorema de Kotelnikov.
Modulador de pulso - Este es un dispositivo con dos entradas, una de las cuales se suministra Señal analoga, y el segundo recibe pulsos de sincronización cortos con un período de repetición A. En este caso, en el momento en que llega el pulso de sincronización, se mide el valor instantáneo de la señal hp(g). Aparece una secuencia de pulsos en la salida del modulador, cada uno de los cuales tiene un área proporcional al valor de referencia correspondiente de la señal analógica (Fig. 4.7).
Señal Hmpn ( t) en la salida del modulador de pulso se llama secuencia de pulsos modulada(PMI). Matemáticamente, el MIP se escribe de la siguiente manera:
A Densidad espectral MIP expresado a través de densidad espectral señal analógica de la siguiente manera:
El modelo de señal discreta supone que se pueden obtener valores de muestra de una señal analógica en un número ilimitado de puntos en el eje del tiempo. En la práctica, el procesamiento siempre se realiza en un intervalo de tiempo finito.
Consideremos las características de la representación espectral de una señal discreta, definida en un intervalo por sus propias lecturas. x 0 ,x x ,...,x N _ x . numero completo cuenta norte-t/ A.
La técnica para estudiar tales señales discretas es que la muestra resultante de valores de referencia se repite mentalmente. número infinito una vez. Como resultado, la señal se vuelve periódica (Fig. 4.8).
Al hacer coincidir dicha señal modelo matemático, puede utilizar la expansión de la serie de Fourier y encontrar los coeficientes de amplitud correspondientes. La combinación de estos coeficientes forma el espectro de una señal periódica discreta.
Arroz. 4.8.
Escribamos el modelo de una señal periódica limitada en forma de secuencia de pulsos delta:
Expandamos la señal Xmip (0 en una serie de Fourier:
¿Es esto un cambio de variables? = f / A. Finalmente obtenemos
Esta fórmula determina la secuencia de coeficientes que forman transformada discreta de Fourier (DFT) de la señal bajo consideración.
DFT tiene las siguientes propiedades:
1. DFT es una transformación lineal, es decir, si zk = axk + /? Reino Unido, Eso
C "Z P ~ ^ C X p R Su p .
2. Número de coeficientes diferentes Cq,Ci,...,C n _i es igual al número norte cuenta para el período, con norte = norte coeficiente C N= C 0 .
3. C 0 es el valor promedio de todas las lecturas C 0 = - ^x A.
norte a=o
- 4. Si N- número par, Eso Con N = -^(-1) k x k.
- 7 ^ ?=o
- 5. Si las lecturas x k - numeros reales Y norte es un número par, entonces C norte = C * norte, / = 0; L/7 2-1.
- -+yo - -i
- 6. Si yk=xk+m, m = l;JV-l,A C, t =C, * e ~ j2rrkm,N .
- 2 tf-l
- 7. Si z k= -> T0 C z k = C X k C y k
yo/yo=0
DFT se utiliza para calcular los espectros de funciones especificadas mediante tablas o gráficos, procesar datos experimentales, encontrar la señal en la salida de un filtro discreto, etc.
Si se basa en lecturas x 0 ,x l ,...,x norte _ l Los coeficientes DFT se encuentran para alguna señal. C 0 ,Ci,... 9 C n/2 , luego usándolos puedes reconstruir una señal analógica con un espectro limitado x(t). La serie de Fourier de dicha señal tiene la forma (incluso para NORTE)
donde |Q| - módulo de coeficientes DFT; =arg - ángulo de fase (argumento)
Coeficientes DFT. Primera frecuencia armónica: f= -/ en = - = -/i- impar norte el último término de la fórmula (4.17) es igual a:
Para calcular muestras discretas x k En base a los coeficientes DFT disponibles, existe la siguiente fórmula:
Esta fórmula se llama transformada de Fourier discreta inversa (IDFT).
