Filtraggio inverso...

[lupo grigio]

Ragazzi
vedo con piacere che avete subito dimostrato interesse per la crittografia e ciò è buona cosa. E’ opportuno però ricordare che questo spazio è dedicato in generale alla Matematica discreta e non solamente alla crittografia. Così ho pensato bene di inaugurarlo con un quesito che con la crittografia non ha nulla a che fare ma che rientra nel tema generale…

Supponiamo di avere lo schema seguente…



La black box sia un sistema tempo-discreto lineare invariante e casuale caratterizzato da una risposta impulsiva $h(n)$. In tal caso la relazione ingresso uscita è data da…

$y(n)= sum_(i=0)^(+oo) h_i*x(n-i)$ (1)

Supponiamo di conoscere $h(n)$ e $y(n)$, di non conoscere l’ingresso $ x(n)$ e volerlo valutare. Un problema del genere è chiamato in letteratura filtraggio inverso. Due quesiti assai semplici:

a) è sempre possibile date $y(n)$ e $h(n)$ trovare la $x(n)$?…
b) nei casi in cui è possibile come si procede?…

cordiali saluti

lupo grigio



an old wolf may lose his teeth, but never his nature

[TomSawyer]

Non vorrei aver frainteso (ma mi sa di sì, perché non conosco questi argomenti), ma a me sa tanto di formula di inversione di Moebius (la terza, per essere precisi).

Cioè, ponendo $f(i*n)=h_ix(n-i)$, si ha $y(n)=\sum_{i=0}^(+oo)f(i*n)$. E la $f(n)$ si ricava dalla formula di inversione $f(n)=\sum_{i=1}^(+oo)\mu(n)y(nx)$, sempre se $\sum_{m,n}|f(mnx)|$ converge.. Solo che la terza formula di inversione vale a partire da $i=1$, quindi può essere che mi sbagli.

[lupo grigio]

Diciamo che una strada abbastanza ‘diretta’ [che può essere anche la citata ‘formula di Moebius’…] consiste in questo. Dato che è…

$y(n)= sum_(i=0)^(+oo) h_i*x(n-i)$ (1)

… se per ipotesi è $h_0ne0$ si può procedere così…

$y(0)=h_0*x(0)$ -> $x(0)=(y(0))/h_0$

$y(1)=h_0*x(1)+h_1*x(0)$ -> $x(1) = (y(1)-h_1*x(0))/h_0$

…

$y(k)= sum_(i=0)^k h_i*x(k-i)$ -> $x(k)=1/h_0*(y(k)-sum_(i=1)^k h_i*x(k-i))$ (2)

E’ così?…

cordiali saluti

lupo grigio



An old wolf may lose his teeth, but never his nature

[luca.barletta]

... lineare invariante e casuale caratterizzato ...

causale?

Diciamo che una strada

…

$y(k)= sum_(i=0)^k h_i*x(k-i)$ -> $x(k)=1/h_0*(y(k)-sum_(i=1)^k h_i*x(k-i))$ (2)

E’ così?…

sì, diciamo che grazie alla causalità dobbiamo risolvere un sistema triangolare.

[lupo grigio]

Mi fa piacere aver ricevuto l’avvallo al mio 'calcolo', per la verità alquanto semplice. Operando in questo modo vi è però un problema. Supponiamo che il sistema lineare invariante e causale [ …] abbia una risposta all’impulso finita [ossia un FIR…], diciamo di lunghezza $N$. In tal caso per $k>N-1$ la formula diviene…

$x(k)= 1/h_0*(y(k) – sum_(i=1)^(N-1) h_i*x(k-i))$ (1)

In termini di z-trasformata la (1) si scrive…

$X(z)= 1/h_0* (Y(z))/(D(z))$ (2)

... con…

$D(z)= 1+sum_(i=1)^(N-1) h_i/h_0*z^(-i)$ (3)

Ora perché la risposta non diverga è necessario che il polinomio $D(z)$ abbia radici tutte all’interno del cerchio unitario. Questo è garantito in ogni caso?…

cordiali saluti

lupo grigio



An old wolf may lose his teeth, but never his nature

[luca.barletta]

è garantito se H(z) è a fase minima (a meno di errori da parte mia)

[lupo grigio]

Certo... ma in tal caso alle ipotesi fatte in precedenza occorre aggiungere la condizione che $H(z)$ sia a 'fase minima'... e se non è così che si fà?...

cordiali saluti

lupo grigio



An old wolf may lose his teeth, but never his nature

[luca.barletta]

Siamo passati da $Y(z)=H(z)X(z)$ a $X(z)=H^(-1)(z)Y(z)$. Poli e zeri si scambiano passando da $H$ a $H^(-1)$ (in questo caso H è soli zeri essendo FIR), e se H non è a fase minima, $H^(-1)$ è instabile.

[lupo grigio]

Una delle applicazioni che ha mostrato la grande potenza degli algoritmi di signal processing è legata al mondo della musica. Tutti sappiamo che un brano musicale registrato in una ambiente soggetto a ‘riverberi’ [tipicamente una chiesa o un teatro non progettato in maniera ‘idonea’ allo scopo…] è in alcuni casi assai ‘sgradevole’ da sentire. In particolare in certe posizioni certe ‘note’ risultano praticamente non udibili in quanto il ‘segnale principale’ e i riverberi si sommano in opposizione di fase autocancellandosi. Una maniera intelligente di porre rimedio a questo consiste nel costruire un ‘modello’ dell’ambiente in cui il brano musicale è stato registrato secondo lo schema già visto…



Qui $x(n)$ rappresenta il brano musicale ‘incorrotto’, $y(n)$ il brano musicale soggetto ai riverberi e $h(n)$ la ‘risposta all’impulso’ dell’ambiente di registrazione. Passando alle traformate se $H(z)$ è invertibile sarà…

$X(z)= Y(z)*H^(-1)(z)$ (1)

… e il gioco è fatto. In altre parole se si conosce $h(n)$ e si ha la registrazione $y(n)$, $x(n)$ può essere ottenuta dalla convoluzione di $y(n)$ con la ‘sequenza inversa’ di $h(n)$. Negli anni ’70 ha destato un certo ‘scalpore’ la ‘riedizione’ di alcune incisioni discografiche di Caruso registrate in analogico negli anni ’20 e ‘riproposte’ cinquant’anni dopo debitamente ‘ripulite’. Da allora è divenuta pratica ‘standard’ quella di caratterizzare la ‘firma’ $h(n)$ di un ambiente registrazione allo scopo di applicare sempre tale tecnica…

Come abbiamo visto condizione necessaria perché $h(n)$ sia ‘invertibile’ è che sia a fase minima. Che significa?… Significa che se scriviamo…

$H(z)= h_0*(N(z))/(D(z))$ (2)

... il polinomio $N(z)$ deve avere tutte le radici in modulo minori di 1, ossia stare [sul piano delle $z$…] entro il cerchio con centro l’origine e raggio uguale ad 1. In tal caso è assicurato che il ‘filtro inverso’…

$H^(-1) (z)= 1/h_0 * (D(z))/(N(z))$ (3)

... è stabile. Facciamo un paio di esempi. Supponiamo da prima che la nostra ‘stanza’ abbia risposta…

$y(n)= x(n)+1/2*x(n-4)$ (4)

… cui corrisponde…

$H_1(z)= 1+1/2*z^(-4)$ (5)

Supponiamo poi che un’altra ‘stanza’ abbia risposta…

$y(n)=x(n)+2*x(n-4)$ (6)

… cui corriponde…

$H_2(z)=1+2*z^(-4)$ (7)

Nella figura che segue…



… sono riportate in rosso le radici di $H_1$ e in azzurro le radici di $H_2$. Per quanto detto prima $H_1$ è ‘invertibile’ mentre $H_2$ non lo è. La domanda ora è questa: se la stanza di registrazione è caratterizzata da una risposta simile ad $H_2$ dobbiamo ‘rassegnarci’ ad ascoltare musica ‘cattiva’ o possiamo tentare di fare qualche cosa?…

cordiali saluti

lupo grigio



An old wolf may lose his teeth, but never his nature

[luca.barletta]

si potrebbe dare in pasto a $H_2^(-1)$ la sequenza ${y_(-n)}$ invece che ${y_n}$, rinunciando così a sistemi in tempo reale (a patto di introdurre un ritardo dovuto alla memorizzazione di ${y_n}$)