Trasformata di Fourier discreta

[Nukles]

Ragazzi non capisco nulla di questo argomento... mi sapete indicare qualche sito, appunti ecc ecc che mi permettano di capirlo meglio?

Poi contate anche che la mia mente è già al mare...

[kaioh]

tiè, il primo link che mi trova google
http://astronomy.swin.edu.au/~pbourke/analysis/dft/

altri link
http://www.google.it/search?hl=it&q=...nsform&spell=1

[r_howie]

Vedi anche Wikipedia e i lucidi di questo corso.

Aggiungo un po' di chiacchiere sperando di non confondere le idee.

La DFT è importante perché è calcolabile tramite un algoritmo facile ed efficiente (Fast Fourier Transform). In generale, calcolare una DFT significa calcolare N coefficienti X[k] (con k = 0,...,N-1), il che ha complessità O(N^2). Se però N è una potenza di 2, allora ci riduciamo a dover calcolare una FFT, con complessità soltanto N*log2(N). Questo ha un impatto notevole nei "grossi" calcoli numerici: per esempio se N = 256, una FFT ci costa solo 2k operazioni contro le 64k della DFT vera e propria.

Non solo: se il segnale x[n] da trasformare -oltre a essere necessariamente finito- è pure a valori reali, allora i coefficienti della DFT da calcolare godono di una simmetria coniugata: X[N-k] = X[k]* dove l'asterisco indica il complesso coniugato.

Esercizio di esempio: calcolare la DFT di lunghezza N = 8 del segnale discreto x[n] che vale 1 per n = 0 o 1.

Per prima cosa operiamo un "zero padding" al segnale x[n], dicendo che esso vale 0 per 2 <= n <= 7 (in questo modo N diventa una potenza di 2, ci conviene). Poi applichiamo la definizione di DFT con la sua sommatoria e il suo esponenziale complesso, che qui non scrivo perché non dubito che tu la studierai benissimo e avrai fior di libri davanti. Ottieniamo:

X[k] = (1/8) * (1 + exp(-j*2*pi*(k/8))) = (1/8) * (1 + cos(k*pi/4) - j*sin(k*pi/4))

X[0] = (1/8) * (1 + 1 - 0) = 1/4

X[1] = (1/8) * (1 + exp(-j*pi/4)) = (1/8) * (1 + 1/sqrt(2) - j/sqrt(2))

X[2] = (1/8) * (1 + exp(-j*pi/2)) = (1/8) * (1 - j)

X[3] = (1/8) * (1 + exp(-j*3*pi/4)) = (1/8) * (1 - 1/sqrt(2) - j/sqrt(2))

X[4] = (1/8) * (1 + exp(-j*pi)) = (1/8) * (1 - 1) = 0

Gli altri coefficienti ce li abbiamo gratis in virtù della simmetria coniugata:

X[5] = X[8-5]* = X[3]*

X[6] = X[2]*

X[7] = X[1]*

Graficando il modulo quadro |X[k]|^2 in funzione di k, il segnale risulta essere passa-basso.

[Nukles]

uao... grazie mille per le dritte! Cercherò di capirle bene... anche perchè suppongo servano a Teoria Dei Segnali... vero?

Ma, in parole povere, che cosa è la Trasformata Di Fourier Discreta? Io nn riesco a capirla bene perchè proprio non comprendo il concetto...

All'università ce l'hanno propinata dopo due settimane in cui abbiamo parlato solo di equazioni differenziali e di teoremi sulle eq diff... ora ci hanno propinato questa trasformata in matematica dicendo che era una cosa difficile da capire anche per i matematici... e infatti nn ci ho capito nulla!

Mi potreste spiegare in parole poverissime e spicce che cosa è? Di cosa si tratta? Ho capito che è una funzione... ma associa cosa a che cosa?

Thanx

[r_howie]

Originariamente inviato da Nukles

uao... grazie mille per le dritte! Cercherò di capirle bene... anche perchè suppongo servano a Teoria Dei Segnali... vero?

Prego. Io parlavo di teoria dei segnali. Tu che esame stai studiando, e per quale corso di laurea?

Originariamente inviato da Nukles

Ma, in parole povere, che cosa è la Trasformata Di Fourier Discreta? Io nn riesco a capirla bene perchè proprio non comprendo il concetto...

Originariamente inviato da Nukles

Ho capito che è una funzione... ma associa cosa a che cosa?

La tua domanda è equivalente a chiedere a cosa serve la derivata, oppure l'elevamento a potenza. Per la stretta sopravvivenza, a niente; per le scienze, invece, sono tutti strumenti di calcolo quantitativi e quasi sempre necessari per studiare cose che altrimenti non si potrebbero studiare.

Comunque, hai letto la prima riga del link di Wikipedia? E per leggere intendo fermarsi a riflettere sul significato delle parole, quando con gli occhi scorri i caratteri e mentalmente senti i suoni... Mi sembra abbastanza chiaro.

Data una successione numerica discreta che io ho chiamato x[n], quindi per esempio un segnale discreto oppure uno continuo che è stato quantizzato, la DFT rappresenta o se preferisci trasporta tale successione in un altro spazio. Sicuramente un libro lo dice in modo più elegante e convincente di me.

[Nukles]

Originariamente inviato da r_howie

Prego. Io parlavo di teoria dei segnali. Tu che esame stai studiando, e per quale corso di laurea?

La tua domanda è equivalente a chiedere a cosa serve la derivata, oppure l'elevamento a potenza. Per la stretta sopravvivenza, a niente; per le scienze, invece, sono tutti strumenti di calcolo quantitativi e quasi sempre necessari per studiare cose che altrimenti non si potrebbero studiare.

Comunque, hai letto la prima riga del link di Wikipedia? E per leggere intendo fermarsi a riflettere sul significato delle parole, quando con gli occhi scorri i caratteri e mentalmente senti i suoni... Mi sembra abbastanza chiaro.

Data una successione numerica discreta che io ho chiamato x[n], quindi per esempio un segnale discreto oppure uno continuo che è stato quantizzato, la DFT rappresenta o se preferisci trasporta tale successione in un altro spazio. Sicuramente un libro lo dice in modo più elegante e convincente di me.

Ho letto la prima parte di Wikipedia e mi pare di aver capito che la trasformata di Fourier non è altro che una funzione che associa a una serie di n numeri appartenenti allo spazio vettoriale C con n, associa una nuova serie sempre in C con n definita attraverso la formula



Lo stiamo facendo in Calcolo Avanzato, dunque in matematica... calcola che il professore l'ha fatto in due lezioni da 1 ora e mezza, parlando anche di convoluzione e robe varie...

...ma io non ci ho capito nulla principalmente perchè fino al giorno prima s'era parlato di equazioni differenziali con il docente titolare, che aveva appunto lasciato all'assistente un certo "nuovo argomento", appunto la trasformata di Fourier discreta... conta anche le lacune dovute ai docenti stupidi di Calcolo I e II su cui è meglio non proferir parola (altrimenti finiremmo in improperi), capirai che passare all'algebra lineare dopo il calcolo differenziali mi ha fatto sentire un po' spaesato...

[r_howie]

Originariamente inviato da Nukles

Ho letto la prima parte di Wikipedia e mi pare di aver capito che la trasformata di Fourier non è altro che una funzione che associa a una serie di n numeri appartenenti allo spazio vettoriale C con n, associa una nuova serie sempre in C con n definita attraverso la formula



Lo stiamo facendo in Calcolo Avanzato, dunque in matematica... calcola che il professore l'ha fatto in due lezioni da 1 ora e mezza, parlando anche di convoluzione e robe varie...

OK (facoltà di matematica, se ho capito bene?). Io ho avuto la fortuna di avere una docente di teoria dei segnali molto chiara, perciò studiare la materia non mi è costato fatica.

Tu chiami la DFT una funzione, il che è giustissimo. Io preferisco chiamarla operatore, ma le due cose non sono in contraddizione... semplicemente il secondo è un caso particolare della prima.

In passato, funzione aveva un significato più ristretto di oggi e indicava un'applicazione R->R, C->R, R^n ->R o quant'altro. Invece oggi la parola funzione include tutto: una qualsiasi applicazione da un insieme a un insieme, il che è un concetto così ampio e generico che di più non si può.

Questo perché con la nascita degli spazi di funzioni, sono "nati" i funzionali (applicazioni da uno spazio di funzioni a un numero. Esempio: l'integrale definito da a a b di una funzione) e gli operatori (applicazioni da uno spazio di funzioni a un altro spazio di funzioni, magari anche lo stesso. Esempio: l'operazione di derivata oppure la stessa trasformata di Fourier).

[Nukles]

No, niente Matematica! Vade retro!

Ingegneria Elettronica!

Matematica è troppo teorica... preferisco applicarle le cose, per questo forse la trasformata ancora non la digerisco: non ho ancora trovato applicazioni...

[Banus]

Originariamente inviato da Nukles

Ingegneria Elettronica!

Allora le trasformate le devi conoscere a memoria

La trasformata di Fourier esprime la funzione in un altro modo (usa un'altra base per rappresentarla, in termini di spazi vettoriali). Invece di dire quanto vale punto per punto, la si immagina come la somma di infiniti termini oscillanti (prova a sviluppare l'esponenziale dell'antitrasformata ). Se la funzione è discreta (f(n)) e limitata allora la formula della trasformata di Fourier si riduce alla formula della DFT (giocando sulle frequenze di campionamento, ci vogliono un po' di calcoli per spiegarlo).
In gergo si dice che la trasformata di Fourier porta la funzione dal dominio del tempo al dominio della frequenza. E' utile per capire come le frequenze di un certo segnale siano modificate da un determinato sistema dinamico (in gergo filtro). I filtri degli apparecchi elettronici sono progettati con l'aiuto della trasformata di Fourier (anche se con l'avvento del digitale ci sono metodi più sofisticati ).
Inoltre una variante della DFT, chiamata DCT, è usata negli algoritmi JPEG, MPEG, DIVX e in molti altri formati lossy, sfruttando il fatto che l'occhio umano è meno sensibile alle alte frequenze (= piccoli dettagli) dell'immagine.

[sgksgk]

Originariamente inviato da r_howie

Se però N è una potenza di 2, allora ci riduciamo a dover calcolare una FFT, con complessità soltanto N*log2(N). Questo ha un impatto notevole nei "grossi" calcoli numerici: per esempio se N = 256, una FFT ci costa solo 2k operazioni contro le 64k della DFT vera e propria.

Una pignoleria,è solo una precisazione.
Dipende comunque dall'algoritmo uttilizzato nello specifico,dietro al nome FFT.
Nel caso di FFT Radice 2 nella frequenza oppure FFT Radice 2 nel tempo il "costo" è di (N/2)*log2(N) moltiplicazioni complesse.
Se tuttavia togliamo le moltiplicazioni al primo stadio (in quanto si tratta di moltiplicazioni per 1) oppure all'ultimo stadio nel caso di FFT Radice 2 nel tempo,allora le moltiplicazioni complesse diventano (N/2)*log(N/2).
Tuttavia implementare il tutto in un programma significherebbe utilizzare istruzioni di selezione che sarebbero comunque onerose.
Quindi si fa quasi sempre riferimento a (N/2)*log2(N) per semplicità.
Quindi nel caso di N=256 verrebbe 1024 moltiplicazioni complesse.
Per calcolare comunque la complessità ancora più in dettaglio uno potrebbe considerare anche le somme complesse e poi riportarsi in moltiplicazioni reali e somme reali (che è quello che si fa,ad esempio per riportarsi da moltiplicazioni complesse a quelle reali si moltiplica per 4 : difatti (a+ib)(c+id) sono 4 moltiplicazioni reali dove a,b,c,d appartengono ad R,quindi nel caso di FFT Radice 2 nella frequenza o nel tempo verrebbero 2N*log2(N) moltiplicazioni reali).

Esistono comunque altri algoritmi ad esempio FFT Radice 4 (il vincolo è che N deve essere una potenza di 4).

[r_howie]

Grazie per la precisazione, sgksgk! Non sapevo.

[Nukles]

Originariamente inviato da Banus

Allora le trasformate le devi conoscere a memoria

Parlare di matematica senza che intervenga Banus (mister "Analisi III così per sport anche se non serviva"), sarebbe come aspettarsi che qua su non si parli di amore senza che intervengano Nicky o Crissina...

Oggi, a mente più fresca di ieri, riesco a comprenderla meglio, anche se mi ci vorrà ancora un po' per capirla, dato che mi devo concentrare oggi sui circuiti e su altre cose di Elettromagnetismo...

...per cambiare proprio argomento, sto vivendo una crisi... anche se ho passato 8 esami su 9 (l'ultimo che non ho passato non lo prendete in considerazione...) e ho una media del 25 (anche se un 21 è da non prendere in considerazione...), che non è poi così male, sono in crisi perchè mi prende la solita crisi d'identità dello studente... "Ho fatto la scelta giusta?" ecc ecc, solo perchè magari di primo impatto non si capisce bene un argomento... oggi questa crisi forse c'è di meno, e le cose le capisco un po' meglio...

...vabbè va, se avete da aggiungere altro fate pure!

[Nukles]

-

[Banus]

Originariamente inviato da Nukles

Parlare di matematica senza che intervenga Banus (mister "Analisi III così per sport anche se non serviva"), sarebbe come aspettarsi che qua su non si parli di amore senza che intervengano Nicky o Crissina...

mi sono già fatto questa fama?
Meglio le trasformate comunque che Eclipse e Java, è tutto il pomeriggio che mi sto rompendo la testa

[Goldrake_xyz]

Originariamente inviato da Nukles

Ragazzi non capisco nulla di questo argomento... mi sapete indicare qualche sito, appunti ecc ecc che mi permettano di capirlo meglio?

Poi contate anche che la mia mente è già al mare...

anche questo :
http://mathworld.wolfram.com/Discret...Transform.html

FFT, ecc. ecc.

Tchuss_

[Goldrake_xyz]

Originariamente inviato da Nukles

...ma io non ci ho capito nulla principalmente perchè fino al giorno prima s'era parlato di equazioni differenziali con il docente titolare, che aveva appunto lasciato all'assistente un certo "nuovo argomento", appunto la trasformata di Fourier discreta... conta anche le lacune dovute ai docenti stupidi di Calcolo I e II su cui è meglio non proferir parola (altrimenti finiremmo in improperi), capirai che passare all'algebra lineare dopo il calcolo differenziali mi ha fatto sentire un po' spaesato...

Ok, ti dico alcuni segreti, ma non dirli a nessuno !

Per prendere quasi tutti 30 + o - lode,
Il trucco è studiare la lezione prima che il professore la spiega...
Oppure avere la fortuna di essere figli o parenti di prof. che insegnano all' università ...

Piccola guida
I prof. di ingegneria e materie affini si possono dividere in queste categorie :
A) Quelli che devono far lezione e non nè hanno voglia, spiegano
l'argomento saltando molti passaggi e copiano dagli appunti.
Risultato : Chi l'ha studiata prima forse capirà qualcosa, gli altri si attaccano ...
B) Gli improvvisatori, che avendo un 'autostima di sè molto grande,
iniziano a spiegare e (purtroppo) a fare dimostrazioni sul momento.
Risultato : impasticciano dimostrazioni iperboliche che talvolta
non capiscono neanche loro..
C) Quelli che hanno la lezione già preparata e vanno avanti in stile
mitragliatore a raffica libera.
Risultato : hai un pacco di appunti, la mano che ti fà male, e non hai capito nulla !

Good Luck !

[misterx]

Originariamente inviato da r_howie

Vedi anche Wikipedia e i lucidi di questo corso.

Aggiungo un po' di chiacchiere sperando di non confondere le idee.

La DFT è importante perché è calcolabile tramite un algoritmo facile ed efficiente (Fast Fourier Transform). In generale, calcolare una DFT significa calcolare N coefficienti X[k] (con k = 0,...,N-1), il che ha complessità O(N^2). Se però N è una potenza di 2, allora ci riduciamo a dover calcolare una FFT, con complessità soltanto N*log2(N). Questo ha un impatto notevole nei "grossi" calcoli numerici: per esempio se N = 256, una FFT ci costa solo 2k operazioni contro le 64k della DFT vera e propria.

Non solo: se il segnale x[n] da trasformare -oltre a essere necessariamente finito- è pure a valori reali, allora i coefficienti della DFT da calcolare godono di una simmetria coniugata: X[N-k] = X[k]* dove l'asterisco indica il complesso coniugato.

Esercizio di esempio: calcolare la DFT di lunghezza N = 8 del segnale discreto x[n] che vale 1 per n = 0 o 1.

Per prima cosa operiamo un "zero padding" al segnale x[n], dicendo che esso vale 0 per 2 <= n <= 7 (in questo modo N diventa una potenza di 2, ci conviene). Poi applichiamo la definizione di DFT con la sua sommatoria e il suo esponenziale complesso, che qui non scrivo perché non dubito che tu la studierai benissimo e avrai fior di libri davanti. Ottieniamo:

X[k] = (1/8) * (1 + exp(-j*2*pi*(k/8))) = (1/8) * (1 + cos(k*pi/4) - j*sin(k*pi/4))

X[0] = (1/8) * (1 + 1 - 0) = 1/4

X[1] = (1/8) * (1 + exp(-j*pi/4)) = (1/8) * (1 + 1/sqrt(2) - j/sqrt(2))

X[2] = (1/8) * (1 + exp(-j*pi/2)) = (1/8) * (1 - j)

X[3] = (1/8) * (1 + exp(-j*3*pi/4)) = (1/8) * (1 - 1/sqrt(2) - j/sqrt(2))

X[4] = (1/8) * (1 + exp(-j*pi)) = (1/8) * (1 - 1) = 0

Gli altri coefficienti ce li abbiamo gratis in virtù della simmetria coniugata:

X[5] = X[8-5]* = X[3]*

X[6] = X[2]*

X[7] = X[1]*

Graficando il modulo quadro |X[k]|^2 in funzione di k, il segnale risulta essere passa-basso.

non ci ho capito quasi niente

[gabi.2437]

s cerchi un'applicazione della FFT, dai un'occhiata al progetto SETI@Home, la applica per distinguere i segnali ricevuti.

[hibone]

Originariamente inviato da misterx

non ci ho capito quasi niente

cercati dei lucidi di comunicazioni elettriche ci sono dei testi sul web

[misterx]

Originariamente inviato da hibone

cercati dei lucidi di comunicazioni elettriche ci sono dei testi sul web

ho una lista di valori in excel coi quali sto cercando di capirci qualcosa. Tali valori se rappresentati su un grafico originano un'onda complessa; ora, prendendo spunto dall'esempio qui postato, volevo vedere se coi dati che ho a disposizione si riusciva a determinare i valori che rappresentano la sinusoide di base ma......nisba

Mi sa che sono ancora lontano dall'obbiettivo