Forma a traliccio per filtri FIR e IIR
Riccardo Bernardini
8 giugno 2010
Sommario
Alcune brevi note sulla forma a traliccio.
Indice
1 Introduzione
1
2 Un modello fisico
2.1 Forme alternative per il “blocchetto di scambio”
2.1.1 Forma a tre prodotti . . . . . . . . . .
2.1.2 Blocchetto di rotazione . . . . . . . . .
2.1.3 Forma a farfalla . . . . . . . . . . . . .
2.2 Riassunto . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2
. 5
. 7
. 7
. 8
. 10
3 Funzione di trasferimento
10
4 Struttura per filtri FIR
12
1 Introduzione
Come noto, il generico filtro a tempo discreto rappresentato da un’equazione alle differenze del tipo
N
M
y(n) =
∑
m=1
am y(n − m) + ∑ bk x(n − k)
(1)
k=0
può essere implementato usando strutture diverse (per es. forma diretta, forma in cascata, forma in
parallalo, . . . ) ognuna delle quali è più o meno adatta a certi contesti applicativi. Molte delle possibili
strutture per filtri a tempo discreto discendono da proprietà algebriche; per esempi, la forma in cascata
viene ottenuta fattorizzando la funzione di trasferimento in fattori di grado due, mentre la forma in parallelo viene dedotta dalla scomposizione in fratti semplici. Un’importante eccezione a questa “regola”
è rappresentata dalla forma a traliccio, molto usata in alcuni contesti applicativi quali la codifica della
voce. Lo scopo di queste brevi note è di introdurre le nozioni di base riguardo la forma a traliccio.
1
A0
A1
A2
A3
A4
A5
A6
Figura 1:
2 Un modello fisico
Il modo più semplice di introdurre la forma a traliccio per filtri a soli poli (ossia, con funzione di trasferimento 1/A(z), dove A(z) è un polinomio) è di basarsi su di un modello fisico di un “tubo acustico.” La
Fig. 1 mostra la sezione di un “tubo” composto da diversi segmenti di sezione variabile (per semplicità,
i vari segmenti sono supposti di uguale lunghezza). Sia Ak la larghezza del k-simo segmento. Il fatto
che il tubo in Fig. 1 sia chiuso ad un’estremità ed aperto all’altra può essere rappresentato introducendo
una sezione iniziale di larghezza A0 = 0 (estremità chiusa) ed una sezione finale di larghezza A6 = ∞
(estremità aperta). Il nostro scopo è studiare la “risposta in frequenza” del tubo di Fig. 1.
Commento 2.1
Si osservi come un sistema della forma mostrata in Fig. 1 sia sufficientemente generale da poter rappresentare
qualsiasi “strumento a fiato,” incluso la generazione della voce umana.
Per studiare il comportamento del sistema di Fig. 1, supponiamo che ci siano due onde: una che
viaggia da sinistra a destra e l’altra da destra a sinistra. Concentriamoci per un momento sull’onda che
viaggia da sinistra a destra (indicata con xd in Fig. 2). Fintanto che l’onda viaggia in un segmento (tra
An e An+1 in Fig. 2) non subisce alcun cambiamento e la propagazione nel segmento corrisponde ad
un ritardo di ∆t = v/L, dove v è la velocità dell’onda e L la lunghezza del segmento. Nel momento in
2
L
(1+a d ) xd
xd
ad x d
An
An+1
arxr
(1+a r )x r
ad
An+1−A n
xr
ar
An+1+A n
An−A n+1
An+1+A n
−a d
Figura 2:
cui l’onda arriva all’interfaccia col segmento successivo avviene una parziale riflessione dell’onda. Più
precisamente, definendo
A − An
ad := n+1
(2)
An+1 + An
si può dimostrare che un’onda di ampiezza (1 + ad )xd si propaga dal segmento n al segmento n + 1 e
un’onda di ampiezza ad xd si riflette e torna indietro.
In maniera perfettamente analoga, possiamo dire che un’onda che muove da destra a sinistra (xr in
Fig. 2) genera un’onda riflessa di ampiezza ar xr e un’onda diretta di ampiezza (1 + ar )xr , dove
ar :=
An − An+1
= −ad
An+1 + An
(3)
Si osservi che poiché le due onde “vedono” la stessa discontinuità, ma da “lati” diversi, i due coefficienti
(2) e (3) differiscono unicamente per il segno.
Commento 2.2
Ci sono un paio di osservazioni interessanti da fare sui coefficienti (2) e (3). La prima osservazione è che
3
An
An+1
τ
1+a
a
τ
−a
τ
τ
1−a
Figura 3:
dipendono unicamente dal rapporto delle due sezioni An e An+1 ; infatti, detto ρ = An+1 /An è immediato
dimostrare che
ρ −1
ad = −ar =
(4)
ρ +1
Una seconda osservazione riguarda i casi estremi An+1 = 0 (tubo chiuso) e An+1 = ∞ (tubo aperto). Nel
primo caso si ha
−An
= −1
(5)
ad =
An
da cui ne deduciamo che non c’è onda diretta (1 − 1 = 0) e che l’onda viene totalmente riflessa con segno
cambiato. Nel caso An+1 = ∞ si ha
x − An
=1
(6)
ad = lim
x→∞ x + An
da cui deduciamo che l’onda si propaga nello spazio aperto con ampiezza doppia e torna indietro senza
cambiamento di segno.
Il pezzo di tubo di Fig. 2 può quindi essere rappresentato dal grafo di flusso di Fig. 3 dove la linea
superiore (blu) rappresenta la perturbazione da sinistra a destra, la linea inferiore (magenta) la perturbazione da destra a sinistra e i rami etichettati con τ rappresentano il ritardo di ∆t = v/L relativo alla
propagazione all’interno di un segmento.
Siamo ora pronti per analizzare nel dettaglio un tubo a più sezioni del tipo mostrato in Fig. 1. Più in
particolare, considereremo il sistema mostrato in Fig. 4, formato da quattro segmenti, aperto a destra ed
infinito a sinistra. Il “filtro” di Fig. 4 ha un ingresso (il segnale x(t) “iniettato” sul confine A1 –A2 ) e due
uscite: il segnale y(t) che esce nello spazio aperto all’estremità destra ed il segnale w(t) che si propaga
“eternamente” verso sinistra. Si noti che nessun segnale entra dall’estremità destra del tubo.
4
x(t)
y(t)
w(t)
A1
A3
A2
1+a2
x
a2
1+a2
τ
−a2
w
1−a2
a2
τ
1+a2
τ
−a2
1−a2
A4
a2
τ
τ
2
y
−a2
1−a2
τ
Figura 4:
Commento 2.3
La scelta di avere il tubo semi-inifinito a sinistra è dovuta al fatto che cosı̀ w(t) non torna più indietro e
l’analisi diventa un po’ più semplice.
Lo schema di Fig. 4 può essere rappresentato in maniera più semplice come in Fig. 5a, dove i blocchi
segnati con la × rappresentano i “blocchetti di scambio” mostrati in Fig. 4.
Per arrivare alla forma a traliccio per filtri IIR è conveniente semplificare un po’ la Fig. 5a. Il primo
passo verso una forma semplificata sarà l’eliminazione di metà elementi di ritardo. Tale eliminazione
è possibile osservando che il grafo racchiuso nella linea a tratto-e-punto in Fig. 5a è un filtro. Poiché
un filtro è tempo-invariante, possiamo spostare il ritardo presente all’ingresso del filtro sulle due uscite
del filtro stesso, ottenendo cosı̀ lo schema di Fig. 5b. Iterando tale costruzione per tutti i ritardi della
linea superiore, otteniamo lo schema di Fig. 5c, equivalente allo schema di Fig. 5a, ma con i ritardi solo
nella linea inferiore. Infine, come ulteriore passo di semplificazione, deriviamo lo schema di Fig. 5d
campionando lo schema in Fig. 5c con un passo di campionamento pari a 2∆t, sı̀ che il ritardo associato
a τ 2 (pari proprio a 2∆t) si trasformi in un ritardo unitario (indicato con z−1 in Fig. 5c). Si osservi che
in Fig. 5d abbiamo eliminato il ritardo τ 3 presente sull’uscita del filtro in Fig. 5c poiché tale ritardo
aggiuntivo non cambia qualitativamente il comportamento del filtro.
2.1
Forme alternative per il “blocchetto di scambio”
Per arrivare alla forma “canonica” della struttura a traliccio è conveniente esprimere il blocchetto di
scambio in forma diversa. Esistono diversi modi di scrivere il blocchetto di scambio, ognuno con le
proprie caratteristiche.
5
x
τ
τ
τ
τ
w
a1
y
τ
τ
a2
a3
Filtro
(a)
x
τ
τ
τ2
w
a1
τ
τ
y
τ3
y
τ
a2
a3
(b)
x
τ2
w
a1
τ2
a2
τ2
a3
(c)
x
y
z −1
w
a1
z −1
a2
z −1
a3
(d)
Figura 5:
6
x
y
1+a 1
a1
−a1
z −1
w
1−a 1
z −1
a2
z −1
a3
(a)
x
a1
y
1+a 1
y
1+a 1
y
−a1
z −1
w
1+a 1
2
z −1
a2
z −1
a3
1−a 1
(b)
x
cos( θ n )
cos( θ n )
z −1
w
2
z −1
a2
z −1
a3
sin( θ n )
(c)
x
cos( θ n )
cos( θ n )
z −1
w
2
z −1
a2
z −1
a3
sin( θ n )
(d)
Figura 6:
2.1.1 Forma a tre prodotti
Per determinare la prima forma alternativa osserviamo la figura Fig. 6a che riproduce lo schema di
Fig. 5d, ma mostrando esplicitamente la struttura del primo blocco di scambio. Sfruttiamo la linearità
del blocco evidenziato con linea tratto-e-punto spostando il prodotto per 1 + a1 dall’ingresso del blocco
alle due uscite. Otteniamo cosı̀ lo schema di Fig. 6b in cui lo “scambiatore a quattro prodotti” è stato
sostituito da uno “scambiatore a tre prodotti,” più un prodotto aggiuntivo spostato sull’uscita del filtro.
Iterando il procedimento appena visto per tutti i blocchetti dello schema si ottiene uno schema equivalente, ma con un costo computazionale (in termini di numero di prodotti) pari a circa i 3/4 del costo
dello schema iniziale.
2.1.2 Blocchetto di rotazione
Per ottenere la seconda forma, osserviamo che poiché ρ = An+1 /An ≥ 0, si ha
ρ −1
≤1
|an | = ρ +1
7
(7)
iu
sin( θ 1)
cos( θ 1)
od
ou
cos( θ 1)
sin( θ 1)
id
Figura 7:
da cui deduciamo che possiamo sempre scrivere a1 = cos θ1 per un qualche θ1 , da cui 1 − a21 = sin2 θ1 .
Lo schema di Fig. 6b può quindi essere ridisegnato come in Fig. 6c che ha un moltiplicatore sin2 θ1 sul
ramo inferiore dello scambiatore. Se sin θ1 6= 0 (ossia, se a1 6= ±1), possiamo riportare un fattore sin θ1
sul ramo superiore, dividendo l’uscita principale per sin θ1 , ottenendo cosı̀ lo schema di Fig. 6d.
Se chiamiamo iu e id i due ingressi dello scambiatore e ou e ud le due uscite (vedi Fig. 7), possiamo
scrivere
sin θ1 − cos θ1
iu
ou
(8)
=
id
od
cos θ1 sin θ1
da cui vediamo che il vettore delle uscite dello scambiatore lo si ottiene applicando una rotazione di θ1 al
vettore degli ingressi, da cui deduciamo che il blocco di scambio nella forma Fig. 6d conserva l’energia
totale dell’ingresso (intesa come somma delle norme quadratiche degli ingressi).
2.1.3 Forma a farfalla
La “forma a farfalla” è forse la forma più comunemente usata per il blocco di scambio.
• Per derivare la forma a farfalla, partiamo dalla forma a tre moltiplicatori mostrata in Fig. 8a e
scomponiamo il ramo moltiplicato per 1 − a2 come parallelo di un ramo unitario ed uno moltiplicato per −a2 , ottenendo cosı̀ lo schema di Fig. 8b.
• Il prodotto per −a2 può essere scritto come un prodotto per −a seguito da un prodotto per a,
poiché anche il ramo sulla destra è moltiplicato per −a, possiamo eseguire il prodotto per −a una
volta sola come mostrato nello schema di Fig. 8c.
• Nello schema di Fig. 8c ci sono due rami moltiplicati per a che entrano nel nodo in basso a destra.
Possiamo risparmiare un prodotto eseguendo prima la somma e poi moltiplicando per a, come
mostrato in Fig. 8d.
• Le uscite dei nodi 1 e 2 (segnati con cerchio a tratto continuo) in Fig. 8d sono necessariamente
uguali poiché ricevono in ingresso i segnali che escono dai noti α e β (cerchi con linea a tratti).
Possiamo quindi risparmiare una somma eliminando il nodo 2 e prelevando a valle del nodo 1
l’ingresso per il ramo con moltiplicatore a. Il risultato è lo schema mostrato in Fig. 8e.
8
a
−a
1−a 2
(a)
a
−a
−a 2
(b)
a
a
−a
(c)
1
a
−a
2
(d)
−a
a
(e)
Figura 8: Derivazione della forma a farfalla.
9
x
y
−a
a
z −1
w
Figura 9:
La forma a farfalla è particolarmente interessante, se non altro per il suo ridotto costo computazionale
di due somme e due prodotti.
2.2
Riassunto
3 Funzione di trasferimento
Caso con solo blocco Per avere un’idea di quale possa essere la funzione di trasferimento di una
struttura a traliccio, cominciamo considerando la struttura con un solo blocco mostrata in Fig. 9. Il
legame tra le trasformate zeta di x (ingresso), y (uscita primaria) e w (uscita secondaria) è
Y (z) = X(z) − az−1Y (z)
−1
W (z) = (a + z )Y (z)
(9a)
(9b)
Dalla (9a) possiamo ricavare
Y (z) =
1
1
X(z) =
X(z)
−1
1 + az
A1 (z)
(10)
dove abbiamo definito
A1 (z) = 1 + az−1
(11)
La (10) usata nella (9b) ci permette di scrivere
W (z) =
z−1 A1 (z−1 )
a + z−1
X(z)
=
X(z)
1 + az−1
A1 (z)
(12)
Si osservi che il filtro associata all’uscita principale è un filtro IIR a soli poli e che il filtro corrispondente
all’uscita secondaria è un passatutto.
Caso generale Per ricavare la funzione di trasferimento nel caso generale, proviamo a dimostrare una
versione generalizzata del risultato ottenuto per un solo blocco.
Proprietà 1. La funzione di trasferimento principale associata ad una struttura a traliccio con N blocchi
è una funzione a soli poli 1/AN (z) dove AN (z) è un polinomio di grado N in z−1 . La funzione di
trasferimento secondaria associata alla stessa struttura è z−N AN (z−1 )/AN (z).
10
u
x
y
−a
A N (z)
a
z −1
w
v
Figura 10:
Dimostrazione. La prova procede per induzione. Il caso N = 1 è stato dimostrato più sopra, per cui
supponiamo il risultato vero per N e dimostriamolo per N − 1. Consideriamo la figura Fig. 10. Per
ipotesi induttiva abbiamo
Y (z) = U(z)
1
AN (z)
(13a)
V (z) = U(z)
z−N AN (z−1 )
AN (z)
(13b)
Gli ingressi e le uscite del blocchetto a farfalla sono invece legati dalle equazioni
U(z) = X(z) − az−1V (z)
(14a)
−1
2
−1
W (z) = aU(z) + z V (z) = aX(z) + (1 − a )z V (z)
(14b)
Usando la (13b) nella (14a) possiamo scrivere
U(z) = X(z) −U(z)
az−N−1 AN (z−1 )
AN (z)
(15)
da cui
az−N−1 AN (z−1 )
X(z) = U(z) 1 +
AN (z)
A (z) + az−N−1 AN (z−1 )
= U(z) N
AN (z)
(16)
che permette di ricavare U(z) in funzione di X(z)
U(z) =
AN (z)
X(z)
AN (z) + az−N−1 AN (z−1 )
(17)
che usata nella (13a) permette di determinare la funzione di trasferimento primaria del sistema di Fig. 10
Y (z) =
1
AN
(z) + az−N−1 A
N (z
−1 )
X(z)
(18)
Il filtro primario del sistema di Fig. 10 è quindi un filtro a soli poli con denominatore
AN+1 (z) := AN (z) + az−N−1 AN (z−1 )
11
(19)
Per ricavare la funzione di trasferimento secondaria dobbiamo ricavare W (z) in funzione di X(z) e a tal
fine usiamo la (13b) nella (14b) ottenendo
"
#
z−(N+1) AN (z−1 )
W (z) = U(z) a +
AN (z)
= U(z)
aAN (z) + z−(N+1) AN (z−1 )
AN (z)
aA (z) + z−(N+1) AN (z−1 )
AN (z)
= X(z) N
AN (z)
AN (z) + az−N−1 AN (z−1 )
=
(20)
aAN (z) + z−(N+1) AN (z−1 )
X(z)
AN (z) + az−N−1 AN (z−1 )
Per completare la dimostrazione resta da verificare che il numeratore dell’ultimo termine di (20) è
z−(N+1) AN+1 (z−1 ). La verifica è immediata
z−(N+1) AN+1 (z−1 ) = z−(N+1) AN (z−1 ) + azN+1 AN (z)
= z−(N+1) AN (z−1 ) + aAN (z)
(21)
4 Struttura per filtri FIR
Poiché un filtro FIR è il filtro inverso di un filtro a soli poli, per ricavare la struttura a traliccio per filtri
FIR, cerchiamo di invertire la struttura a traliccio per filtri IIR a soli poli. Il punto di partenza sarà il
seguente lemma.
Lemma 1. La struttura di Fig. 11a è equivalente alla struttura di Fig. 11b con
D(z) =
a +C(z)
1 + aC(z)
(22)
Dimostrazione. È sufficiente scrivere le equazioni che legano i segnali di Fig. 11a.
U(z) = X(z) − aV (z)
(23a)
V (z) = C(z)U(z)
(23b)
W (z) = aU(z) +V (z)
(23c)
Y (z) = U(z) + aV (z)
(23d)
R(z) = aU(z) +V (z)
(23e)
• Usando la (23a) nella (23d) si deduce Y (z) = X(z)
• Confrontando la (23c) con la (23e) si deduce W (z) = R(z)
• Infine, dalla (23a) e (23b) deduciamo
U(z) = X(z) − aC(z)V (z)
12
(24)
u
x
y
y
x
a
−a
C(z)
w
D(z)
a
a
r
v
(a)
w
r
(b)
Figura 11:
da cui
U(z) = X(z)
1
1 + aC(z)
(25)
che usata nella (23c) con la (23b) ci permette di dedurre
W (z) = aU(z) +V (z)
= (a +C(z))U(z)
a +C(z)
X(z) = D(z)X(z)
=
1 + aC(z)
Riferimenti bibliografici
13
(26)