Segnali Discreti - Dipartimento di Ingegneria Informatica e delle

UNIVERSITA’ DEGLI STUDI DI CATANIA
Facoltà di Ingegneria
Corso di Laurea in Ingegneria Telematica
Elaborazione di Segnali
Multimediali
=
Elaborazione Numerica dei Segnali
+
Comunicazioni Multimediali
Elaborazione numerica dei segnali
(Digital Signal Processing, DSP)
Tecniche e algoritmi per l’analisi, la
trasformazione, la sintesi di segnali digitali
elaborati attraverso circuiti elettronici digitali
programmabili (microprocessori, DSP) il cui
funzionamento è regolato da un
programma
x [n]
DSP
y [n]
(Digital Signal Processor)
• Algoritmi sempre più sofisticati
• Flessibilità
• DSP sempre più potenti e a basso costo
Campi applicativi dell’elaborazione
numerica dei segnali
• Analysis
• Synthesis
• Source Coding
• Recognition
• Modulation
• Filtering
• Regeneration
• Detection
• Identification
• Measurement
Comunicazioni Multimediali
Sistemi interattivi che utilizzano
contemporaneamente diversi mezzi di
comunicazione come:
• testo
• grafica
• video
• suono
Esempio: lavoro di gruppo a distanza in
cui ognuno ha la possibilità di:
• interagire con i propri gli interlocutori avendo a
disposizione un collegamento video
• sentire la loro voce
• condividere una tavola grafica
Corso
Elaborazione di Segnali Multimediali
Docente
F. Beritelli
Programma Segnali a tempo discreto (Lezioni: 5 ORE)
Conversione D/A e metodi di interpolazione. Teoremi sulla trasformata di
Fourier di segnali discreti. Analisi di Fourier di sequenze periodiche (DFT).
Algoritmi veloci di trasformata discreta di Fourier (FFT).
Sistemi a tempo discreto (Lezioni:14 ORE; Esercitazioni: 10 ORE)
Caratterizzazione dei sistemi a tempo discreto. Proprietà. Sistemi lineari e
stazionari. Risposta in frequenza. Interpolazione e decimazione di una
sequenza numerica. La trasformata Z. Proprietà della trasformata Z. Sistemi a
tempo discreto regolati da equazioni alle differenze. Risposta impulsiva.
Funzione di trasferimento. Filtri FIR e IIR. Progettazione di filtri numerici.
Tecniche di elaborazione del segnale vocale (Lezioni: 10 ORE;
Laboratorio: 5 ORE)
Caratteristiche del segnale vocale. Quantizzazione adattativa (APCM).
Predizione lineare. Codifica differenziale ed adattativa (DPCM, ADPCM).
Codifica di analisi per sintesi (RPE, MPE, CELP). Codifica della voce a bit-rate
variabile. Standard di codifica per sistemi radiomobili GSM e UMTS. Tecniche
di sintesi e riconoscimento della voce.
Tecniche di elaborazione del segnale video (Lezioni:8 ORE; Laboratorio: 5
ORE )
Caratteristiche del segnale video. Quantizzazione vettoriale. Codifica di
immagini fisse JPEG: modalità di funzionamento, codifica DCT, ricostruzione
dell’immagine. Codifica differenziale intracampo ed intercampo. Standard
H.261 e H.263 per videoconferenza. Standard MPEG. Compensazione del
movimento. Comunicazioni multimediali interattive in tempo reale su reti a
pacchetto: telefonia su IP e videoconferenza.
Tecniche di pattern recognition (Lezioni: 3 ORE)
Architettura di un sistema di pattern recognition. Ottimizzazione dei parametri:
analisi della correlazione, criterio di Fisher, criterio di separabilità di Fukunaga,
analisi delle componenti principali, metodi ricerca del sottoinsieme ottimo.
Metodi di classificazione: classificatore di Bayes, classificazione Nearest
Neighbour, classificatore lineare di Fisher, classificazione basata su tecniche
di Soft Computing.
Modalità
d’esame
Esame orale preceduto da una prova scritta o, in alternativa, da due/tre
prove scritte intermedie.
Elaborazione numerica
x(t)
–3T –2T –T
x[n]
T 2T 3T
t
–3 –2 –1
x(t)
1 2
3
n
x[n]
t=nT
x(t)
x[n]
A/D
DSP
D/A
xˆ (t)
x[n]
–3 –2 –1
y(t)
y[n]
1 2
x[n]
3
n
–3T –2T –T
xˆ (t)
T 2T 3T
t
Esempi di segnali tempo discreto
notevoli (1/2)
1) sequenza gradino unitario:
1
u[n] = 
0
u[n]
n≥0
n<0
1
–4 –3 –2 –1
2) sequenza esponenziale unilatera:
x[n]
x[n ] = a u[n]
n
1 n = 0
δ[ n] = 
 0 altrimenti
0<a<1
1
–4 –3 –2 –1
3) sequenza δ o impulsiva:
1 2 3 4 5
δ[n]
1
–4 –3 –2 –1
1 2 3 4
Relazione tra u[n] e δ[n]:
u[n] =
n
1 2 3 4
n
∑δ [i ]
i =−∞
quindi u[n] è la sequenza somma della sequenza δ[n].
n
n
Esempi di segnali tempo discreto
notevoli (2/2)
4) sequenza impulso rettangolare causale di durata N :
x[n ] = u[n] − u[n − N ]
x[n]
u[n]
1
1
•••
0
1
N–1 N
n
0
1
N–1
n
-u[n-N]
5) oscillazione complessa discreta alla frequenza
normalizzata Fo:
x[n] = exp( j2πF0 n)
6) differenza all’indietro del primo ordine o incremento:
δ[ n] = u[n ]− u[n − 1]
Trasformata di Fourier di una
sequenza x(n) aperiodica (1/5)
x[n] ⇔ X ( f )
Trasformata:
∞
∆
X ( f ) = ∑ x[n] e
− j 2πnfT
n= −∞
= F [x [n]]
eq. di analisi
è una funzione periodica in ambito frequenziale di un
periodo pari alla frequenza di campionamento fc=1/T:
1

X (f ) = X f + 

T
Antitrasformata:
x[n ] = T
1 2T
j 2πnfT
e
df
X
f
(
)
∫
eq. di sintesi
−1 2T
Anche per la trasformata di una sequenza è comunque
d’uso introdurre lo spettro di ampiezza A ( f ) =| X ( f ) |
e lo spettro di fase θ ( f ) = ∠X ( f )
Trasformata di Fourier di una
sequenza x(n) aperiodica (2/5)
Una condizione sufficiente per l’esistenza della
trasformata è l’assoluta sommabilità della sequenza, cioè
la condizione
∞
∑ x[n] < +∞
n =−∞
Infatti, essendo
X (f ) =
∞
∑ x[n] e
− j2πnfT
∞
≤
∑ x[n]
n = −∞
n = −∞
si ha di conseguenza la convergenza della serie per tutti i
valori della frequenza.
1) Trasformata di Fourier della sequenza δ[n]:
δ[n] ⇔ ∆( f ) =
∞
∑ δ [n] e
− j 2πnfT
=1
n = −∞
La trasformata è quindi una funzione periodica di periodo
1/T che, in ciascun periodo, assume un valore costante e
pari a 1.
∆(f)
δ[n]
1
1
–4 –3 –2 –1
1 2 3 4
n
–1/2T
1/2T
f
Trasformata di Fourier di una
sequenza x(n) aperiodica (3/5)
2) Trasformata di Fourier dell’impulso rettangolare discreto di
durata N
x[n ] = u[n] − u[n − N ]
1− e − j2πNfT
e − jπNfT e jπNfT − e − jπNfT
− jπ ( N −1 ) fT sin(NπfT )
X (f ) =
e
=
=
j fT
j fT
j fT
e− π
e π − e− π
sin(πfT )
1 − e − j 2πfT
Lo spettro di ampiezza è allora
X (f ) =
sin(NπfT )
sin (πfT )
L’andamento dello spettro di ampiezza in vicinanza di f=0
ricorda quello di una funzione
N sinc(NfT)
Inoltre, restringendoci all’intervallo “base”
si annulla per le frequenze
fk =
k
NT
f ∈ [−1 2T,1 2T ]
k = ±1, ± 2, K, ± N 2
, esso
Trasformata di Fourier di una
sequenza x(n) aperiodica (4/5)
e assume per il valore massimo per f=0 dato da
X (0 ) = lim X ( f ) = N
f →0
12
10
N=10
8
6
4
2
0
-1.00
-0.75
-0.50
-0.25
0.00
0.25
0.50
0.75
1.00
0.75
1.00
Frequenza normalizzata, fT
180
135
N=10
90
45
0
-45
-90
-135
-180
-1.00
-0.75
-0.50
-0.25
0.00
0.25
Frequenza normalizzata, fT
0.50
Trasformata di Fourier di una
sequenza x(n) aperiodica (5/5)
3) Trasformata di Fourier della sequenza esponenziale discreto:
X (f ) =
x[n ] = a u[n]
n
1
| X ( f ) |=
1+ a2 − 2 a cos(2πfT )
1
− j2 πfT
1− a e
| a |< 1
2.50
2.00
a=0.5
1.50
1.00
,
a=0.1
0.50
0.00
-0.5
-0.4
-0.3
-0.2
-0.1
0.0
0.1
0.2
0.3
0.4
0.5
Frequenza normalizzata, fT
 a sin (2πfT ) 
∠X ( f ) = arctg
 1 − a cos(2πfT )
90
a=0.5
45
0
a=0.1
-45
-90
-0.5
-0.4
-0.3
-0.2
-0.1
0.0
0.1
0.2
Frequenza normalizzata, fT
0.3
0.4
0.5
Teoremi sulla Trasformata di
Fourier di una sequenza (1/2)
Teorema di linearità:
x[n ] = a x1 [n] + b x2 [n]
X ( f ) = a X1 ( f ) + b X 2 ( f )
Teorema del ritardo:
x[n − k ] ⇔ X ( f ) e − j2πkfT
Teorema della modulazione:
x[n ] e
j 2 π nf0 T
⇔ X ( f − f0 )
Teorema del prodotto:
p[n] = x[n ] y[n] ⇔ P ( f ) = T
1 2T
∫ X (ν )Y ( f − ν )dν
−1 2T
Teoremi sulla Trasformata di
Fourier di una sequenza (2/2)
Teorema della somma di convoluzione:
z[n] = x[n]⊗ y[n ]=
∆
+∞
+∞
k = −∞
k =−∞
∑ x[k ] y[n − k ] = ∑ y[k ] x[n − k ]
z[n] = x[ n] ⊗ y[n ] ⇔ Y ( f ) X ( f ) = Z ( f )
Teorema dell’incremento:
∆x[n ]=∆ x[n] − x [n − 1]
Operatore incremento
−
∆x[n ] ⇔ X ( f ) − X ( f ) e
j 2 π fT
−
= X ( f ) (1− e
j 2 π fT
)
Teorema della sequenza somma:
y[n]=
∆
n
∑ x[k ]
Sequenza somma
k =−∞
X (f )
Y (f ) =
− j2πfT
1− e
purchè
X (0) =
∞
∑ x[n ] = 0
n =−∞
Condizione di Nyquist
Segnale nel tempo Trasformata di Fourier
x(t)
x[n]
X(f)
X (f )
1 ∞ 
k
X ( f ) = ∑ X f − 
T k = −∞ 
T
La trasformata di Fourier di una sequenza ottenuta per
campionamento si ricava come periodicizzazione della
trasformata del segnale analogico di partenza, con un
periodo di ripetizione in frequenza pari alla frequenza di
campionamento fc = 1 / T
Fissata la banda del segnale B, la frequenza di
campionamento deve essere scelta in modo che
valga la condizione
fc =
1
≥ 2B
T
Condizione di Nyquist
condizione che garantisce assenza di aliasing.
Esempio di Campionamento con e
senza Aliasing
1.25
Trasformata del segnale
analogico x(t)
1.00
0.75
0.50
0.25
0.00
-B
-0.25
-3.0
-2.0
-1.0
B
0.0
1.0
2.0
3.0
Frequenza normalizzata, f/B
1.25
Trasformata del
segnale digitale
x[n] (fc>2B)
1/T=2.5B
1.00
0.75
0.50
0.25
0.00
-B
-0.25
-3.0
-2.5
-2.0
-1.5
-1.0
-0.5
B
0.0
0.5
1.0
1.5
2.0
2.5
3.0
Frequenza normalizzata, fT
1.25
Trasformata del segnale
digitale x[n] in presenza
di “aliasing” (fc<2B)
1/T=1.25B
1.00
0.75
0.50
0.25
0.00
-B
-0.25
-3.0
-2.0
-1.0
B
0.0
1.0
Frequenza normalizzata, fT
2.0
3.0
Filtro Anti-Aliasing e Teorema del
Campionamento
Filtro Anti-Aliasing
H(f)
x(t)
1
ξ(t)
ξ[n]
A/D
y[n]
DSP
y(t)
D/A
B' f
Teorema del campionamento (C. Shannon): Un
segnale il cui spettro è limitato nella banda B può
essere ricostruito esattamente a partire dai propri
campioni, purché la frequenza di campionamento
non sia inferiore a 2B.
Altri esempi di trasformata di
Fourier di sequenze digitali
1) Trasformata di Fourier della sequenza costante:
1 ∞ 
k
X ( f ) = ∑ δ  f − 
T k = −∞
T
x[n] = 1
X(f)
x[n]
1/T
1
n
-1/T
−
1
2T
1
2T
1/T
f
2) Trasformata di Fourier del coseno e del seno:
x[n] = cos(2πnf0 T )
y[n] = sin(2πnf 0 T)
1
1
δ ( f − | f0 |1/ T ) +
δ ( f + | f0 |1/ T )
2T
2T
1
1
Y (f) =
δ ( f − | f0 |1/ T ) −
δ( f + | f 0 |1 / T )
2 jT
2jT
X(f )=
ove ci siamo limitati a considerare l’intervallo “base”
1
1
della trasformata, − 2 T ≤ f ≤ 2T senza esplicitamente
indicare la periodicizzazione
Trasformata discreta di Fourier
(DFT) di una sequenza periodica
Sequenza periodica di periodo No:
x[n ] = x[n + N0 ]
x[n ] =
N 0 −1
∑X
k= 0
1
Xk =
N0
k
e
2πkn
j
N0
∞
∑X
x (t ) =
k
k
N 0 −1
∑ x[n] e
2πkn
−j
N0
n= 0
e
j
2πkt
T0
= −∞
T0 2
2πkt
1
−j
Xk =
x (t ) e T0 dt
∫
T0 − T 2
0
Per i segnali periodici a tempo continuo la
rappresentazione mediante serie di Fourier comporta
una somma infinita di termini; nel caso di sequenze
periodiche, invece, la rappresentazione mediante
antitrasformata discreta consiste in una somma con un
numero finito di addendi. Infatti la trasformata di una
sequenza periodica di periodo No è essa stessa
periodica con il medesimo periodo.
X k + N0
1
=
N0
1
=
N0
N 0 −1
N 0 −1
∑ x[n] e
−j
2π (k + N 0 )n
N0
n =0
2 πkn
∑ x[n ] e − j N = Xk
0
n =0
1
=
N0
N 0 −1
∑ x[n] e
n =0
−j
2π kn
N0
e−
j2 πn
=
Una sequenza periodica quindi può essere
rappresentata mediante uno sviluppo del tutto
analogo alla serie di Fourier per i segnali periodici a
tempo continuo, chiamato serie discreta o
antitrasformata discreta di Fourier:
La sequenza dei coefficienti discreti di Fourier è
comunemente chiamata trasformata discreta di
Fourier o DFT (Discrete Fourier Transform) della
sequenza periodica data.
Periodicizzazione di una sequenza
x(n) aperiodica
Analogico
y(t ) =
Digitale
+∞
∑ x (t − mT )
0
m =−∞
1  k 

Yk = X
T0  T0 
y[n] =
+∞
∑ x [n − mN ]
0
m = −∞
1
1  k 

Yk =
X( f ) f = k =
X
N0
N0  N0 T 
N0 T
Complessità di calcolo della
trasformata discreta di Fourier (1/3)
(DFT, Discrete Fourier Transform)
Si consideri la trasformata di una sequenza x[n] periodica
di periodo No:
Trasformata:
1
Xk =
N0
N 0 −1
∑ x[n] e
2πkn
−j
N0
n= 0
2π (N 0 −1)k
2πk
2π 2 k
1 
−j0
−j
−j
−j

=
N0
 x[0] ⋅ e + x[1] ⋅ e N 0 + x [2] ⋅ e N 0 + ... + x[N0 − 1]⋅ e

N0
Antitrasformata:
x[n] = X 0 ⋅ e + X1 ⋅ e
j0
2 n
j π
N0
+ X2 ⋅ e
2 2n
j π
N0
+ ... + X N 0 −1 ⋅ e
j
2 π (N 0 −1)n
N0
Se x[n] è una sequenza di valori complessi e si trascura
il prodotto per il termine 1/No possiamo dire che la
complessità di calcolo tra trasformata e antitrasformata è
la stessa.
Supponendo che i fattori esponenziali complessi che
figurano nelle espressioni sopra siano precalcolati, cioè
già disponibili in memoria, per calcolare il k-esimo
coefficiente Xk sono necessarie No moltiplicazioni
complesse e No-1 addizioni complesse.
Complessità di calcolo della DFT
(2/3)
________________________________________
Considerando che
1 moltiplicazione complessa = 4 moltiplicazioni reali + 2
addizioni reali
1 addizione complessa=2 addizioni reali
________________________________________
N0
quindi, sono
coefficiente:
necessarie
per
ogni
k-esimo
6No+2(No-1)=8No-2 operazioni
il numero complessivo di operazioni da compiere
per calcolare la trasformata discreta di Fourier
(TDF) di una sequenza periodica di periodo No è:
NTDF (N0 ) = (8N 0 − 2) N 0 = 8N0 − 2N0 ≅ 8N 0
2
2
Possiamo notare che la complessità di calcolo (o
computazionale) della trasformata discreta è di tipo
quadratico nell’ordine No di trasformazione.
Complessità di calcolo della DFT
(3/3)
_______________________________________
ESEMPIO:
Microelaboratore con Fclock=100 MHz
(cioè 100 milioni di operazioni al secondo)
Sequenza x[n] di periodo No=210=1024
________________________________________
il tempo necessario per effettuare il calcolo della
DFT è pari a:
TN0 = NTOT fclock ≅ 8⋅ 220 ⋅10 −8 ≅ 8 ⋅10 6 ⋅10 −8 = 80 ms
Supponiamo adesso che la sequenza venga
generata campionando un segnale analogico x(t)
a frequenza fc=1/Tc. Per poter operare in tempo
reale si deve utilizzare una frequenza di
campionamento tale che
fc ≤
N0 1024
3 = 12.8 kHz
TN0 80 ⋅10 −
Ricordando la condizione di Nyquist, questo
risultato rappresenta un vincolo sulla banda B del
segnale da elaborare.
Fast Fourier Transform (FFT) (1/3)
L’algoritmo veloce di calcolo della trasformata
discreta consente un deciso miglioramento della
velocità di elaborazione. Sfruttando particolari
simmetrie insite nei fattori esponenziali complessi
della trasformata stessa si può infatti ridurre la
complessità computazionale.
L’algoritmo di FFT fu pubblicato nel 1965 da
Cooley e Tukey; a questa data si fa risalire la
nascita della moderna elaborazione numerica dei
segnali.
Supponiamo di avere No=2M
Xk =
N 0 2−1
∑
x [2m ] e
−j
2 π ( 2m) k
N0
+
N 0 2 −1
m =0
m= 0
Pk
644
47
444
8
N 0 2 −1
= ∑ x[2m ] e
m =0
−j
∑
2 πkm
N0 2
+e
π
− j2 k
N0
x[2m + 1] e
−j
2 π ( 2m +1) k
N0
Dk
64447
4448
N 0 2−1
⋅ ∑ x[2m + 1] e
m=0
−j
2 πkm
N0 2
k = 0,K, N0 − 1
la trasformata di ordine No è espressa come
combinazione lineare di due trasformate di ordine
No/2.
Fast Fourier Transform (FFT) (2/3)
Il numero di operazioni NFFT(No) necessario a
calcolare la trasformata di ordine No secondo
questo nuovo criterio può allora essere espresso
in maniera ugualmente ricorsiva sulla base di
questa scomposizione:
NFFT (N0 ) = N FFT
 N0 
 N0 
N
6N 2N
 2  + FFT  2  + 0 + 0
avendo tenuto conto del fatto che, per ogni valore
di k, è necessario moltiplicare
per un
esponenziale
complesso
(precalcolato,
6
operazioni reali) e quindi effettuare la somma con
(2 operazioni reali). Questo procedimento di
scomposizione può essere poi ripetuto in modo
ricorsivo ottenendo:
NFFT (N0 ) = 6N0 + 8N 0 log2 N0 ≅ 8N0 log 2 N0
Il rapporto tra il numero di operazioni necessarie
nei due casi è pari a:
NTDF (N 0 )
8N 0 2
N0
=
=
NFFT (N 0 ) 8N0 log 2 N0 log2 N0
Fast Fourier Transform (FFT) (3/3)
Con riferimento all’esempio precedente, se si usa
il medesimo elaboratore per calcolare una FFT di
ordine 1024, si otterrà un tempo di calcolo
inferiore a quello prima calcolato del fattore
N0 / log 2 N 0 = 1024 /10 ≅ 100
________________________________________
Come già detto, gli stessi algoritmi utilizzati per il
calcolo veloce della trasformata discreta possono
essere anche utilizzati per il calcolo della
antitrasformata,
poiché
le
relazioni
di
trasformazione e di antitrasformazione sono
formalmente identiche, a parte l’inessenziale
costante moltiplicativa, e l’altrettanto ininfluente
segno dell’argomento degli esponenziali.
Analisi spettrale di una sequenza
x[n] aperiodica basata su FFT (1/4)
Si desidera effettuare l’analisi spettrale di una
data sequenza aperiodica x[n] attraverso il calcolo
della relativa trasformata di Fourier:
X (f ) =
+∞
∑ x[n] e
− j 2 πnfT
n = −∞
Problema: nelle applicazioni reali non si hanno a
disposizione tutti i valori della sequenza x[n], ma
solo i valori in un intervallo finito, diciamo [0, N-1].
Inoltre, ad esempio nel caso di una sequenza
vocale, in base al valore di N si parla di analisi
spettrale a breve (NT=10÷30 ms) o lungo termine
(NT=qualche minuto).
Vedremo che non è possibile calcolare la
trasformata per gli infiniti valori della variabile f in
un periodo, ad es. nell’intervallo [0,1/T], ma ci si
accontenterà di ottenere il valore della trasformata
per un numero finito di punti normalmente
equispaziati nell’intervallo [0, 1/T].
Immaginiamo dunque di periodicizzare
sequenza data con periodo No=N:
y[n] =
+∞
∑ x [n − mN]
m = −∞
la
Analisi spettrale di una sequenza
x[n] aperiodica basata su FFT (2/4)
Dalla relazione di campionamento in frequenza si
ha:
1  k 
Yk =
X

N0  N0 T 
k = 0,1, K, N − 1
Poiché y[n] è una sequenza periodica, possiamo
calcolarne la trasformata discreta di Fourier Yk per
k=0, ..,N-1, mediante un algoritmo veloce.
Pertanto dalla relazione precedente si ricava:
X
 k 
N Yk
 NT  =
k = 0,1, K, N − 1
Siamo cioè riusciti a calcolare la trasformata di
Fourier X(f) in N punti, e precisamente per le N
frequenze equispaziate nell’intervallo [0,1/T]:
fk =
k
NT
k = 0,1, K, N − 1
La distanza tra una frequenza e la successiva è
pari a ∆=1/NT e quindi la risoluzione in frequenza
è pari a 1/∆=NT.
Analisi spettrale di una sequenza
x[n] aperiodica basata su FFT (3/4)
ESEMPIO
Calcoliamo lo spettro della sequenza aperiodica
x[n] di figura. Essa ha durata finita e pari a N=3.
x[n]
1
0.5
1
–1
2
n
3
Effettuando una periodicizzazione si ottiene la
sequenza periodica y[n] di periodo N=3:
y[n]
1
0.5
•••
•••
–1
1 2 3
n
Analisi spettrale di una sequenza
x[n] aperiodica basata su FFT (4/4)
La trasformata di Fourier
originaria è:
della sequenza
X ( f ) = x [0] + x[1] e− j 2πfT + x[2 ] e − j 2π 2 fT = e − j 2πfT [1 + cos(2πfT )]
il cui generico periodo [0, 1/T] è rappresentato
nella seguente figura:
2.5
2.0
_
|X(f)|
1.5
1.0
0.5
_
|3 Y k |
0.0
1/3T
2/3T
1/T
Frequenza
Utilizzando il metodo appena descritto, si usa una
trasformata discreta di ordine 3 e si ricavano i 3
“campioni” della trasformata per le frequenze:
f k = 0,1 3T , 2 3T
Zero-padding o riempimento
con zeri (1/2)
Per migliorare la risoluzione o accuratezza della
trasformata di Fourier di una sequenza finita di
valori, è possibile usare per il parametro No un
valore maggiore della durata della sequenza N. In
particolare, aggiungendo No-N zeri si ottiene una
sequenza di periodo No che nel periodo base vale:
 x[n] 0 ≤ n ≤ N − 1
y[n] = 
N ≤ n ≤ N0 − 1
0
La nuova risoluzione in frequenza è pari a NoT
avendo ancora una volta:
 k 
 = N0 Yk
X
 N0 T 
k = 0,1, K, N0 − 1
Se si fa crescere il valore del parametro No, ossia
si aggiungono molti campioni nulli aumentando
l’ordine della FFT, si aumenta la risoluzione
dell’analisi spettrale della sequenza x[n] aperiodica
e di durata finita originaria.
Zero-padding o riempimento
con zeri (2/2)
ESEMPIO
Ripetiamo il calcolo dell’esempio precedente,
stavolta però con zero-padding fino a No=8,
ovvero aggiungendo 5 valori nulli alla sequenza
originaria:
y[n]
1
0.5
•••
•••
–8 –7 –6
1 2
8 9 10
2.5
2.0
1.5
_
|X(f)|
1.0
_
|8Yk|
0.5
0.0
0.000
0.125
0.250
0.375
0.500
0.625
0.750
Frequenza normalizzata, fT
0.875
1.000
n
Convoluzione veloce basata su FFT
Si considerino due sequenze aperiodiche (per
semplicità causali) a durata finita pari a N.
La convoluzione (lineare) tra le due sequenze per
definizione è data da:
z[n] = x[n]⊗ y[n ] =
+∞
N −1
m =−∞
m= 0
∑ x[m] y[n − m] = ∑ x[m] y[n − m]
Si dimostra che la complessità della convoluzione
di sequenze di durata N calcolata secondo la
definizione è:
N (N) = 2N 2 − 2N + 1 ≅ 2N 2
conv
Una procedura alternativa, basata su FFT, per il
calcolo della convoluzione è la seguente:
Si dimostra che, in questo caso, la complessità è:
Nconv,FFT (N) ≅ 12 N0 / 2 log 2 (N0 / 2) ≅ 12N log 2 (N)
che per N>32 è inferiore al caso precedente.
Riassunto caratteristiche dei
segnali tempo-frequenza
Tempo
Frequenza
x(t)
•••
Xk
•••
t
k
Segnale
aa tempo
continuo
periodico
Segnale
a tempo
continuo
periodico
Segnale
tempo
continuo
periodico
Spettro discreto aperiodico
X(f)
x(t)
t
Segnale a tempo continuo aperiodico
f
Spettro continuo aperiodico
x[n]
X(f)
•••
n
Segnale a tempo discreto aperiodico
f
Spettro continuo periodico
x[n]
•••
•••
Xk
•••
n
Segnale a tempo discreto periodico
•••
•••
k
Spettro discreto periodico