Dft E Prodotto di convoluzione tra vettori
Il cerchietto con la x , rappresenta il prodotto di convoluzione , $F_N[f] $ e $F_N[g] $ rappresentano le dft f e g che sono vettori. $ . \star $ è il prodotto componente per componente di due vettori. Adesso la mia domanda è : sto provando a sperimentare la prima delle due proprietà con Matlab , ma non mi riesce . qualcuno sa aiutarmi?
La proprietà dice che la dft del prodotto componente per componente dei vettori f e g , è uguale al prodotto di convoluzione tra la dft(f) e la dft(g).
Risposte
ragazzi qualcuno mi aiuta?
Ti aiuto volentieri ma non ho ben capito la tua richiesta/problema. 
praticamente se faccio il prodotto componente per componente di due vettori e ne calcolo la dft, allora il vettore risultante è uguale al vettore ottenuto dal prodotto di convoluzione delle dft dei singoli vettori, $F_N[f.\starg]=F_N[f]\otimesF_N[g] $. Non riesco a far valere questa proprietà utilizzando degli esempi concreti
Possiamo vedere un caso semplice, non so quanto sia utile...
$x1 = [1 ,1, 1, 1] \Rightarrow X1 = [1, 0, 0, 0]$
$x2 = [1,2,3,2] \Rightarrow X2 = [8, -2,0,-2]$
In maiuscolo denoto le trasformate discrete di Fourier.
Il prodotto componente per componente tra i vettori $x1$ ed $x2$:
$x = [1,2,3,2] \Rightarrow X = [8,-2,0,-2]$
La convoluzione circolare delle trasformate è chiaramente uguale ad $X$, che appunto rispetta la proprietà.
Bene. Ora vediamo dove invece potresti sbagliarti o confonderti... Sei sicuro di utilizzare la convoluzione ciclica? La DFT opera su successioni periodiche/periodicizzate. Sei sicuro che i tuoi risultati non siano inesatti solo per alcune costanti di normalizzazione? Ad esempio, invece di ottenere $X = [8, -2, 0, -2]$ ottieni $X = [32, -8, 0,-8]$ ... Spesso la DFT viene normalizzata con la costante $1/N$ con $N$ numero degli elementi del vettore: questa costante va ovviamente considerata anche nelle definizioni delle sue proprietà e di conseguenza nella proprietà di convoluzione ciclica.
$x1 = [1 ,1, 1, 1] \Rightarrow X1 = [1, 0, 0, 0]$
$x2 = [1,2,3,2] \Rightarrow X2 = [8, -2,0,-2]$
In maiuscolo denoto le trasformate discrete di Fourier.
Il prodotto componente per componente tra i vettori $x1$ ed $x2$:
$x = [1,2,3,2] \Rightarrow X = [8,-2,0,-2]$
La convoluzione circolare delle trasformate è chiaramente uguale ad $X$, che appunto rispetta la proprietà.
Bene. Ora vediamo dove invece potresti sbagliarti o confonderti... Sei sicuro di utilizzare la convoluzione ciclica? La DFT opera su successioni periodiche/periodicizzate. Sei sicuro che i tuoi risultati non siano inesatti solo per alcune costanti di normalizzazione? Ad esempio, invece di ottenere $X = [8, -2, 0, -2]$ ottieni $X = [32, -8, 0,-8]$ ... Spesso la DFT viene normalizzata con la costante $1/N$ con $N$ numero degli elementi del vettore: questa costante va ovviamente considerata anche nelle definizioni delle sue proprietà e di conseguenza nella proprietà di convoluzione ciclica.
dft(x1)=[4 0 0 0] perchè ti viene [1 0 0 0]?
COMUNQUE SI !! mi viene [32 -8 0 8 0 0 0] perchè? grazie
Non capisco questa cosad ella normalizzazione perchè si fa!
COMUNQUE SI !! mi viene [32 -8 0 8 0 0 0] perchè? grazie
Non capisco questa cosad ella normalizzazione perchè si fa!
Proprio perché ho utilizzato una DFT normalizzata, con una costante $1/N$ di normalizzazione a moltiplicare.
Dunque invece di ottenere [4 0 0 0] ottengo 1/4 * [4 0 0 0].
Invero molti libri definiscono la DFT non normalizzata, salvo poi compensare la trasformata inversa con la costante $1/N$. La normalizzazione si fa per un motivo ben visibile anche dalla stessa definizione di DFT, dalla formula:
$DFT(x)_n = \sum_{k=0}^{N-1} x_k e^{2pikn/N}$
Prendi, ad esempio:
$DFT(x)_0 = \sum_{k=0}^{N-1} x_k$
Chiaramente stai gonfiando di $N$ il vettore risultante, diviene $N$ volte più grande.
Perché proprio così? Mah... sono convenzioni. Invero, senza una normalizzazione adatta, $N$ DFT di fila producono un ingigantimento del vettore finale di $N^N$ rispetto quello iniziale: questo potrebbe causare spiacevoli problemi nell'applicazione numerica. Teoricamente, il miglior compromesso risiede nel stabilire una costante di normalizzazione $1/sqrt(N)$ sia per DFT che per IDFT: in questo modo la trasformata e l'inversa sono unitarie e non si ha nessun tipo di ingigantimento/ridimensione. Nell'applicazione si preferisce comunque tenere le costanti $1$ ed $1/N$. (quando la DFT viene definita con costante $1/N$ la sua inversa ha costante $1$ e viceversa...)
Dunque invece di ottenere [4 0 0 0] ottengo 1/4 * [4 0 0 0].
Invero molti libri definiscono la DFT non normalizzata, salvo poi compensare la trasformata inversa con la costante $1/N$. La normalizzazione si fa per un motivo ben visibile anche dalla stessa definizione di DFT, dalla formula:
$DFT(x)_n = \sum_{k=0}^{N-1} x_k e^{2pikn/N}$
Prendi, ad esempio:
$DFT(x)_0 = \sum_{k=0}^{N-1} x_k$
Chiaramente stai gonfiando di $N$ il vettore risultante, diviene $N$ volte più grande.
Perché proprio così? Mah... sono convenzioni. Invero, senza una normalizzazione adatta, $N$ DFT di fila producono un ingigantimento del vettore finale di $N^N$ rispetto quello iniziale: questo potrebbe causare spiacevoli problemi nell'applicazione numerica. Teoricamente, il miglior compromesso risiede nel stabilire una costante di normalizzazione $1/sqrt(N)$ sia per DFT che per IDFT: in questo modo la trasformata e l'inversa sono unitarie e non si ha nessun tipo di ingigantimento/ridimensione. Nell'applicazione si preferisce comunque tenere le costanti $1$ ed $1/N$. (quando la DFT viene definita con costante $1/N$ la sua inversa ha costante $1$ e viceversa...)
"pasqualinux":
dft(x1)=[4 0 0 0] perchè ti viene [1 0 0 0]?
COMUNQUE SI !! mi viene [32 -8 0 8 0 0 0] perchè? grazie
In questo caso hai usato la convoluzione lineare. Sbagli. Sei stato fortunato perché - con i vettori scelti - la convoluzione lineare è identica a quella ciclica... Ma non e' assolutamente una regola: solitamente si creano degli artefatti di periodicizzazione (Aliasing). In questo caso non ci sono perché il primo vettore ha abbastanza zeri da far sì che la convoluzione circolare non abbracci gli elementi finali con gli iniziali. Ma qui il discorso si apre...
IMPORTANTE: la convoluzione deve essere CICLICA e risultare di $N$ elementi; non di $2N-1$ elementi, come una lineare.
nelle slide c'è scritto che la convoluzione fornisc un vettore di 2n-1 elementi quindi suppongo che la proprietà faccia riferimento alla convoluzione lineare. In effetti nelle slide parla semplicemente di convoluzione e non specifica ne lineare ne ciclica. Adesso guardando la formula nella slide di che convoluzione si tratta?
Se parliamo di DFT, questa opera su successioni periodiche: la loro convoluzione si definisce come quella che hai postato tu in alto.
"Hadronen":
Se parliamo di DFT, questa opera su successioni periodiche
che significa ?
Quella che ho definito sopra è lineare o circolare?
"pasqualinux":
[quote="Hadronen"]Se parliamo di DFT, questa opera su successioni periodiche
che significa ?
Quella che ho definito sopra è lineare o circolare?[/quote]
Ma sopra dove? Nell'immagine? È circolare.
ok , ma quella circolare restituisce un vettore di $2n-1$ componenti?
cosa intendi che la DFT opera su successioni periodiche?
cosa intendi che la DFT opera su successioni periodiche?
"pasqualinux":
ok , ma quella circolare restituisce un vettore di $2n-1$ componenti?
cosa intendi che la DFT opera su successioni periodiche?
No. La convoluzione ciclica restituisce al massimo $N$ componenti con $N$ lunghezza dei vettori in convoluzione.
La DFT, Trasformata Discreta di Fourier, è definita SOLO per successioni periodiche. Dunque per operare una DFT su un certa successione, sequenza, quest'ultima dev'essere periodica.
ma successioni numeriche periodiche? la dft numericamente è un prodotto matrice vettore. non riesco ancora a capire cosa intendi che opera su successioni periodiche. cioè io posso creare un qualsiasi vettore e applicarne la dft non capisco tu cosa intendi !
Quindi per effettuare il prodotto di due numeri naturali con la convoluzione devo usare la convoluzione lineare?
Com'è definita la convoluzione lineare tra vettori? su internet non riesco a trovarla.
Inoltre nella formula che ho pubblicato k varia da 0 a n-1 e anche j , solo che j risulta fissato ad ogni ciclo quindi $w_(j-k)$ avrebbe indice negativo, per opportuni valori! è sbagliata la formula?
Questa è la definizione che ho della dft, non so quell' $n$ nella tua definizione cosa indica .
Infine non ho capito , in quanto non mi trovo con la tua definizione di dft, il discorso di gonfiamento del vettore
anche supponendo che il mio k sia il tuo n, ma non capisco lla notazione $DFT(x)_0 $ cosa significa!
Grazie in anticipo
Quindi per effettuare il prodotto di due numeri naturali con la convoluzione devo usare la convoluzione lineare?
Com'è definita la convoluzione lineare tra vettori? su internet non riesco a trovarla.
Inoltre nella formula che ho pubblicato k varia da 0 a n-1 e anche j , solo che j risulta fissato ad ogni ciclo quindi $w_(j-k)$ avrebbe indice negativo, per opportuni valori! è sbagliata la formula?
Questa è la definizione che ho della dft, non so quell' $n$ nella tua definizione cosa indica .
Infine non ho capito , in quanto non mi trovo con la tua definizione di dft, il discorso di gonfiamento del vettore
"Hadronen":
La normalizzazione si fa per un motivo ben visibile anche dalla stessa definizione di DFT, dalla formula:
$DFT(x)_n = \sum_{k=0}^{N-1} x_k e^{2pikn/N}$
Prendi, ad esempio:
$DFT(x)_0 = \sum_{k=0}^{N-1} x_k$
anche supponendo che il mio k sia il tuo n, ma non capisco lla notazione $DFT(x)_0 $ cosa significa!
Grazie in anticipo
"pasqualinux":
ma successioni numeriche periodiche? la dft numericamente è un prodotto matrice vettore. non riesco ancora a capire cosa intendi che opera su successioni periodiche. cioè io posso creare un qualsiasi vettore e applicarne la dft non capisco tu cosa intendi !
Quindi per effettuare il prodotto di due numeri naturali con la convoluzione devo usare la convoluzione lineare?
Com'è definita la convoluzione lineare tra vettori? su internet non riesco a trovarla.
Inoltre nella formula che ho pubblicato k varia da 0 a n-1 e anche j , solo che j risulta fissato ad ogni ciclo quindi $w_(j-k)$ avrebbe indice negativo, per opportuni valori! è sbagliata la formula?
Se hai studiato un po' di analisi armonica dovresti sapere che la trasformata di una funzione periodica è una successione di impulsi. Dunque, se tu vuoi successioni (quindi funzioni discrete) la cui trasformata è ancora discreta, allora, per la stessa ragione di prima, queste successioni devono essere periodiche.
Chiaro che tu puoi prendere qualsiasi vettore.
Se con vettore indichi una successione finita (ad esempio A = [1 1 0 0]) allora certo che è possibile.
Ma e' impossibile eseguire una DFT del segnale $x[n] = x$ , $-infty < n < infty$ (bisettrice discreta, chiaramente non periodica)... Qual'è lo $0$ di partenza, qual'è l'$N-1$ di chiusura? Puoi solamente eseguire una DFT di una porzione del segnale $x[n]$, che automaticamente, ti restituisce la Trasformata di Fourier della stessa porzione di segnale PERIODICIZZATA.
Dunque, ad esempio...
Preso $X$ = [-3 -2 -1 0 1 2 3] la sua DFT è la Trasformata di Fourier del segnale $X_p$ = [... -3 -2 -1 0 1 2 3 -3 -2 -1 0 1 2 3 ...].
La formula è corretta, come anche la mia. $j$, $n$, $k$, chiamali come vuoi. Sono indici...
... quel $j-k$ indica una riflessione di uno dei due vettori in convoluzione. Su http://it.wikipedia.org/wiki/Convoluzione c'è tutto.
Purtroppo i grafici in movimento che sono lì non fanno capire molto bene il capovolgimento/riflessione del vettore in movimento. (una funzione caratteristica (onda quadra) riflessa è identica a sé stessa non riflessa)
si ma gli indici diventano negativi nella sommatoria del primo post? e non ho capito il discorso sul gonfiamento del vettore e cosa significa $Dft(x)_0$
Mi daresti un link con le formule di convoluzione ciclica e lineare di vettori o magari una definizione. Non riesco a trovare nulla ci sono quasi sempre integrali e strane formule.
se usi i vettori $f=[1 ,2, 3, 4] $ e $g=[5, 6 ,7, 8]$ la proprietà non vale !
Mi daresti un link con le formule di convoluzione ciclica e lineare di vettori o magari una definizione. Non riesco a trovare nulla ci sono quasi sempre integrali e strane formule.
"Hadronen":
Possiamo vedere un caso semplice, non so quanto sia utile...
$x1 = [1 ,1, 1, 1] \Rightarrow X1 = [1, 0, 0, 0]$
$x2 = [1,2,3,2] \Rightarrow X2 = [8, -2,0,-2]$
In maiuscolo denoto le trasformate discrete di Fourier.
Il prodotto componente per componente tra i vettori $x1$ ed $x2$:
$x = [1,2,3,2] \Rightarrow X = [8,-2,0,-2]$
La convoluzione circolare delle trasformate è chiaramente uguale ad $X$, che appunto rispetta la proprietà.
se usi i vettori $f=[1 ,2, 3, 4] $ e $g=[5, 6 ,7, 8]$ la proprietà non vale !
"pasqualinux":
si ma gli indici diventano negativi nella sommatoria del primo post? e non ho capito il discorso sul gonfiamento del vettore e cosa significa $Dft(x)_0$
Mi daresti un link con le formule di convoluzione ciclica e lineare di vettori o magari una definizione. Non riesco a trovare nulla ci sono quasi sempre integrali e strane formule.
[quote="Hadronen"]Possiamo vedere un caso semplice, non so quanto sia utile...
$x1 = [1 ,1, 1, 1] \Rightarrow X1 = [1, 0, 0, 0]$
$x2 = [1,2,3,2] \Rightarrow X2 = [8, -2,0,-2]$
In maiuscolo denoto le trasformate discrete di Fourier.
Il prodotto componente per componente tra i vettori $x1$ ed $x2$:
$x = [1,2,3,2] \Rightarrow X = [8,-2,0,-2]$
La convoluzione circolare delle trasformate è chiaramente uguale ad $X$, che appunto rispetta la proprietà.
se usi i vettori $f=[1 ,2, 3, 4] $ e $g=[5, 6 ,7, 8]$ la proprietà non vale ![/quote]
Se ti sembra strana la definizione di Convoluzione, credo che dovresti (ri)vederti buona parte dei programmi di Analisi...
Funziona per ogni vettore. Vuoi che non funzioni una delle proprietà base della DFT...? Boh.
Ti scrivo un programma in codice MATLAB (mi sembra che avevi accennato al suo utilizzo) così fai un po' (infinite) prove...
clear all close all % Numero di Elementi Vettori x1 ed x2 N = 4 % Definisco Vettori x1 = [1 2 3 4]; x2 = [5 6 7 8]; % DFT di x1 ed x2 (Divido per N per NORMALIZZARE!) X1 = fft(x1)/N; X2 = fft(x2)/N; % Prodotto di x1 per x2 y1 = x1.*x2; % DFT Prodotto Y1 = fft(y1)/N % Convoluzione Ciclica DFT Y2 = cconv(X1,X2,N)
non e colpa mia la prof ci da la conv come function!! forse e per questo che nn funziona!! praticamente descrivendo le proprieta della dft a un certo punto esce quella del prodotto di convoluzione che non abbiamo mai studiato e non sappiamo cosa sia . ci dice solo che serve per il prodotto di numero naturali e polinomi non cidice se e ciclico o lineare niente niente niente
addirittura dice il vettore risultante ha lunghezza 2n-1 ma non ho capito adesso se vale per la ciclica o per la lineare
mi fate un po di chiarezza please!!
addirittura dice il vettore risultante ha lunghezza 2n-1 ma non ho capito adesso se vale per la ciclica o per la lineare
mi fate un po di chiarezza please!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo