Relazione russa

quantizzatore.pdf

quantizzatore.tex

\documentclass{article}

\usepackage{pgfplots,mathtools,commath}
\usepackage[russian,english,italian]{babel}
\usepackage[utf8]{inputenc}
\usepackage{hyperref}
\usetikzlibrary{calc}
\pgfplotsset{compat=1.6}

\pgfplotsset{soldot/.style={color=blue,only marks,mark=*}} \pgfplotsset{holdot/.style={color=blue,fill=white,only marks,mark=*}}

\title{Quantizzatore ad autoapprendimento}
\author{Enrico Odetti \and Andrea Odetti\footnote{per la versione \LaTeX{} Febbraio 2016}}
\date{Dicembre 1967}
\begin{document}
\maketitle

Come noto un quantizzatore \`e un sistema dinamico senza memoria che trasforma un segnale analogico variabile d'ingresso in un segnale d'uscita discreto o digitale.
Il diagramma pi\`u comune di un quantizzatore si presenta con gradini orizzontali (Fig. \ref{fig:1}).
Il numero dei gradini  N pu\`o essere illimitato (quantizzatore senza saturazione).

Se N \`e limitato, come nel caso pi\`u comune, si definisce allora quantizzatore con saturazione.
Nel caso pi\`u comune si definiscono solo l'altezza e la larghezza dei gradini (quantizzatore uniforme).
Molto pi\`u interessante \`e quando l'altezza e la larghezza dei gradini sono una funzione del segnale d'ingresso o di una sua caratteristica statistica (quantizzatore non uniforme).

In questo lavoro studiamo un quantizzatore non uniforme con saturazione a cui applichiamo la funzione di autoapprendimeto per ottimizzarne il comportamento.

\begin{figure}[h]
  \centering
  \begin{tikzpicture}
    \begin{axis}[
        xtick={-2.5,-1.5,-0.5,0.5,1.5,2.5},
        xticklabels={},
        xlabel=$S_{\text{in}}$,
        xmin=-2.5, xmax=2.5,
        yticklabels={},
        ytick={-2,-1,0,1,2},
        ylabel=$S_{\text{out}}$,
        ymin=-4, ymax=4,
        axis x line = center,
        axis y line = center]
      \addplot+[jump mark left,very thick] coordinates {
        (-2.5,-2) (-1.5,-1) (-0.5,0) (0.5,1) (1.5,2) (2.6,3)
      }
      node[pos=0.05,black]{$1$}
      node[pos=0.25,black]{$2$}
      node[pos=0.45,black]{$3$}
      node[pos=0.65,black]{$i$}
      node[pos=0.85,black]{$N$}
      ;
    \end{axis}
  \end{tikzpicture}
  \caption{Diagramma di un quantizzatore uniforme.}
  \label{fig:1}
\end{figure}

\begin{figure}[h]
  \centering
  \begin{tikzpicture}[node distance=2.5cm,auto]
    \node (a) {$S_{\text{in}}$};
    \node [draw, fill=blue!20, minimum size=3em, right of=a] (b) {quantizzatore};
    \node [right of=b] (c) {$S_{\text{out}}$};
    \path[->,thick] (a) edge (b);
    \path[->,thick] (b) edge (c);
  \end{tikzpicture}
\end{figure}

% asse x ingresso In, asse y uscita Out

Per $N$ gradini il processo di quantizzazione \`e completamente definito se ai punti $x_i$ e $x_{i+1}$ di ciascun intervallo corrisponde un unico livello o gradino $y_i$ (Fig. \ref{fig:2}).
% ----------

Per la migliore determinazione delle grandezze $x_i$ e $y_i$ introduciamo la misura di distribuzione $D$, per tutto il quantizzatore, come speranza matematica di una opportuna funzione $f$ differenza tra il segnale d'ingresso e quello di uscita.
\begin{align}
  D = M \{ f(S_{\text{in}} - S_{\text{out}}) \}
\end{align}

Se la distribuzione di densit\`a della probabilit\`a di errore $(S_{\text{in}} - S_{\text{out}})$ \`e uguale alla densit\`a di distribuzione $p(x)$ del segnale d'ingresso, possiamo scrivere
\begin{align}
  D = \sum_{i=1}^N \int_{x_i}^{x_{i+1}} f(x - y_i) p(x) \dif x \label{eq:2}
\end{align}
dove $x_1 = -\infty, x_{N+1} = \infty$ e $x$ \`e il segnale di entrata.

I migliori valori $x_i$ e $y_i$ devono minimizzare $D$
\begin{align}
  \min_{x_i, y_i} D \rightarrow x_i^*,y_i^*
\end{align}

Nel caso la densit\`a di distribuzione sia conosciuta in anticipo, il problema pu\`o essere considerato risolto. Se invece per quanto possibile non \`e nota, diviene allora complicata e complessa da calcolare. Nel secondo caso quando la funzione distribuzione $p(x)$ non \`e nota, possiamo utilizzare un procedimento di auto-sintonia (quantizzatore ad autoapprendimento).

Supponiamo che le grandezze $x_i$ e $y_i$ possano assumere qualunque valore iniziale e che i valori successivi siano
\begin{align*}
  x_i[0] \quad i = 2,\dots,N \\
  y_i[0] \quad i = 1,\dots,N
\end{align*}

\begin{figure}[h]
  \centering
  \begin{tikzpicture}
    \begin{axis}[
        xtick={-2.6,-1.2,-0.6,0.7,1.1,2.5},
        xticklabels={$x_1=-\infty$, $x_2$, $x_i$, $x_{i+1}$, $x_N$, $x_{N+1}=\infty$},
        xmin=-2.6, xmax=2.5,
        ytick={-2.2,-0.9,0.1,1,2.2},
        yticklabels={$y_1$,$y_2$,,$y_{N-1}$,$y_N$},
        ymin=-3, ymax=3,
        axis x line = center,
        axis y line = center]
      \addplot+[jump mark left, very thick] coordinates {
        (-2.6,-2.2) (-1.2,-0.9) (-0.6,0.1) (0.7,1) (1.1,2.2) (2.6,3)
      };
    \end{axis}
  \end{tikzpicture}
  \caption{Diagramma di un quantizzatore non uniforme.}
  \label{fig:2}
\end{figure}
Un quantizzatore con sintonizzatore si realizza con un dispositivo speciale, che chiamiamo \emph{adattatore} (Fig. \ref{fig:3}). L'adattatore, per passi successivi, calcola i valori $x_i$ e $y_i$ per cui si ottengono i valori ottimali $x_i^*$ e $y_i^*$.

Supponiamo che le variazioni si effettuino in modo discreto nel tempo, in tal modo possiamo scrivere la corrispondenza tra ingresso e uscita come segue
\begin{align}
\begin{rcases*}
x[n] \\
x_i[n-1],y_i[n-1]
\end{rcases*} \rightarrow x_i[n], y_i[n] \label{eq:4}
\end{align}

In questo lavoro si stabilisce la corrispondenza ingresso-uscita dell'adattatore (\ref{eq:4}) formalmente con i principi dell'approssimazione stocastica. Come noto il metodo dell'approssimazione stocastica permette di trovare i valori estremi del funzionale (\ref{eq:2}) quando la conoscenza a priori della densit\`a di distribuzione $p(x)$ soddisfa qualche condizione che inizialmente non conosciamo.
Per minimizzare $D$ per $N$ costante differenziamo per $x_i$ e $y_i$ e imponiamo che il risultato abbia valore nullo
\begin{align}
  \frac{\partial D}{\partial x_i} & = f(x_i -y_{i-1}) p(x_i) - f(x_i -y_i) p(x_i) = 0 & i = 2,\dots,N  \label{eq:5} \\
  \frac{\partial D}{\partial y_i} & = - \int_{x_i}^{x_{i+1}} f(x - y_i) p(x) \dif x = 0 & i = 1,\dots,N \label{eq:6}
\end{align}

Dalla (\ref{eq:5}) otteniamo (quando $p(x_i) \neq 0$)
\begin{align}
  f(x_i - y_{i-1}) & = f(x_i - y_i) \label{eq:7} \\
  i & = 2,\dots,N \nonumber
\end{align}

\`E evidente che l'ultima soluzione non dipende da $p(x)$ al contrario della soluzione (\ref{eq:6}). Considerando la soluzione (\ref{eq:7}), la condizione di minimo pu\`o essere scritta come segue
\begin{align}
\begin{dcases*}
  f(x_i - y_{i-1}) = f(x_i - y_i) \\
  \min_{y_i} D
\end{dcases*} \rightarrow x_i^*,y_i^* \label{eq:8}
\end{align}
dove adesso il minimo \`e ricercato solo per $y_i$ ($i=1,\dots\,N$). La soluzione (\ref{eq:7}) si presenta come una condizione supplementare.

\begin{figure}[h]
  \centering
  \begin{tikzpicture}
    \node (a) {$S_{\text{in}}$};
    \node [inner sep=0,minimum size=0,right of=a, node distance=2cm] (k) {};
    \node [draw, fill=blue!20, minimum size=3em, right of=k, node distance=3cm] (b) {quantizzatore};
    \node [draw, fill=blue!20, minimum size=3em, below of=b, node distance=2.8cm] (c) {adattatore};
    \node [right of=b,node distance=5cm] (d) {$S_{\text{out}}$};

    \coordinate (c0) at ($(c.west) +(0,-0.2)$);
    \coordinate (c1) at ($(c.west) +(0,0.2)$);
    \coordinate (b1) at ($(b.south) +(-0.7,0)$);
    \coordinate (b2) at ($(b.south) +(+0.7,0)$);

    \draw[fill] (k) circle (0.05);

    \path[->,thick] (a) edge (b);
    \draw[->,thick] (k) |- node[near end,below] {$x[n]$} (c0);
    \draw[->,thick] (b1) -- +(0,-0.6) -- +(-1.5,-0.6) node[below right] {$\begin{array}{c}x_i[n-1] \\ y_i[n-1]\end{array}$} -- +(-1.5,-1.5) |- (c1);
    \draw[<-,thick] (b2) -- +(0,-0.6) -- +(1.5,-0.6) node[below left] {$\begin{array}{c}x_i[n] \\ y_i[n]\end{array}$} -- +(1.5,-1.5) |- (c);
    \path[->,thick] (b) edge (d);

    \draw[dashed,thick] (1,-3.8) rectangle (9,1);
  \end{tikzpicture}
  \caption{Struttura di un quantizzatore ad autoapprendimento.}
  \label{fig:3}
\end{figure}
Supponendo che ci sia solo un sistema risolutivo (\ref{eq:8}) possiamo trovarlo con il metodo dell'approssimazione stocastica.

Indichiamo
\begin{align}
  \overline{c} = \left [
    \begin{array}{c}
      y_1 \\ y_2 \\ \vdots \\ y_N
    \end{array}
    \right ]
\end{align}

Per cui
\begin{align}
  \min_{\overline{c}} D(\overline{c}) = \min_{\overline{c}} M_x \left \{ f(\overline{c}, x) \right \} \rightarrow \overline{c}^*
\end{align}

Non scriviamo una nuova condizione (\ref{eq:7}), in rapporto a quelle supposte, poich\'e si realizzano sempre. $\overline{c}^*$ deve risolvere la seguente equazione
\begin{align}
  \Delta D (\overline{c}) = M_x \left \{ \nabla_{\overline{c}} f(\overline{c}, x) \right \} = 0
\end{align}

Possiamo risolvere l'equazione precedente con il seguente algoritmo di approssimazione stocastica
\begin{align}
  \overline{c}[n] = \overline{c}[n-1] - \gamma[n] \nabla_{\overline{c}} f(x[n], \overline{c}[n-1]) \label{eq:12}
\end{align}
dove $\gamma[n]$ \`e una successione di valori favorevoli, tali per cui
\begin{align}
  \sum_{n=1}^\infty \gamma[n] = \infty \quad \sum_{n=1}^\infty \gamma^2[n] < \infty
\end{align}

In tal modo affinch\'e di fatto siano determinati $x_i$ e $y_i$ poniamo $f(\bullet)$ nella forma di una funzione quadratica. Dopo aver calcolato $\nabla_{\overline{c}} f$ otteniamo
\begin{align}
  \frac{\partial f}{\partial y_i} = -2(x-y_i) \varepsilon_{x_i,x_{i+1}}(x) \quad i=1,\dots,N
\end{align}
dove
\begin{align*}
  \varepsilon_{x_i,x_{i+1}}(x) =
  \begin{dcases*}
    1 & $x_i \le x < x_{i+1}$ \\
    0 & altrove
  \end{dcases*}
\end{align*}

Adesso possiamo scrivere dettagliatamente l'algoritmo (\ref{eq:12}) prendendo in considerazione la condizione (\ref{eq:7})
\begin{align}
  f(x_i - y_{i-1}) & = f(x_i - y_i) \nonumber \\
  (x_i - y_{i-1})^2 & = (x_i - y_i)^2 \\
  x_i & = \frac{y_i + y_{i-1}}{2} \nonumber \\
    i & = 2,\dots,N \nonumber
\end{align}
oppure
\begin{align}
  \tag{$12'$}
  \begin{dcases*}
    x_2[n] = \frac{y_1[n] + y_2[n]}{2} \\
    \dots \\
    x_N[n] = \frac{y_{N-1}[n] + y_N[n]}{2} \\
    \left [
      \begin{array}{c}
        y_1[n] \\ \vdots \\ y_N[n]
      \end{array}
      \right ] =
    \left [
      \begin{array}{c}
        y_1[n - 1] \\ \vdots \\ y_N[n - 1]
      \end{array}
      \right ] + 2 \gamma[n]
    \left [
      \begin{array}{c}
        (x[n] - y_1[n - 1]) \varepsilon_{x_1,x_2[n-1]}(x[n])  \\ \vdots \\ (x[n] - y_N[n - 1]) \varepsilon_{x_N[n-1],x_{N+1}}(x[n])
      \end{array}
      \right ]
  \end{dcases*} \label{eq:12i}
\end{align}
dove sempre $x_1=-\infty$, $x_{N+1}=\infty$.

Come noto da $\gamma[n]$ dipende la convergenza, come anche la velocit\`a del processo di convergenza dell'autoapprendimento.

Per questo affinch\'e di fatto sia definita una unica funzione $\gamma[n]$, impostiamo una condizione supplementare cos\`i che il processo iterattivo converga nel modo migliore.

Il criterio di scelta della qualit\`a dell'algoritmo si determina come segue: il funzionale $D(\overline{c}) = M_x \{ (S_{\text{in}} - S_{\text{out}})^2 \}$ si imposta empiricamente
\begin{align}
  V_e^2[n] = \frac{1}{n}  \sum_{m=1}^n \sum_{i=1}^N (x[m] - y_i[n])^2 \varepsilon_{x_i[n-1],x_{i+1}[n-1]}(x[m]) \label{eq:16}
\end{align}
otteniamo
\begin{align}
  \min_{\gamma[n]} V_e^2[n] & \rightarrow \gamma^*[n]
\end{align}
cio\`e
\begin{align}
  \frac{\dif V_e^2[n]}{\dif \gamma[n]} & = 0 \label{eq:18}
\end{align}

Sostituendo nella (\ref{eq:16}) $y_i[n]$, nell'algoritmo (\ref{eq:12i}), otteniamo
\begin{align*}
  \begin{split}
    V_e^2[n] = \frac{1}{n} \sum_{m=1}^n \sum_{i=1}^N \left ( x[m] - \left (y_i[n-1] + 2 \gamma [n] \left (x[n] - y_i[n-1] \right ) \varepsilon_{x_i[n-1],x_{i+1}[n-1]}(x[n]) \right ) \right ) ^2 \\
    \times \varepsilon_{x_i[n-1],x_{i+1}[n-1]}(x[m])
    \end{split}
\end{align*}

Di conseguenza l'equazione (\ref{eq:18}) diventa
\begin{align}
  \tag{$18'$}
  \begin{split}
    \frac{\dif V_e^2[n]}{\dif \gamma [n]} = - \frac{2}{n} \sum_{m=1}^n \sum_{i=1}^N \left ( x[m] - \left ( y_i[n-1] + 2 \gamma [n] \left (x[n] - y_i[n-1] \right ) \right ) \right ) \times \\
    \left (x[n] - y_i[n-1] \right ) \varepsilon_{x_i[n-1],x_{i+1}[n-1]}(x[n]) \varepsilon_{x_i[n-1],x_{i+1}[n-1]}(x[m]) = 0
  \end{split} \label{eq:18i}
\end{align}

Nella (\ref{eq:18i}) $\varepsilon(x[n])$ garantiscono l'esistenza di un solo valore sommatoria $\sum_{i=1}^N$.
Con questo si completa l'equazione
\begin{align}
  \sum_{m=1}^n \left ( x[m] - \left (y_{\underline{i}}[n-1] + 2 \gamma [n] \left (x[n] - y_{\underline{i}}[n-1] \right ) \right ) \right ) \left (x[n] - y_{\underline{i}}[n-1] \right ) & = 0
\end{align}
oppure
\begin{align}
  \sum_{m=1}^n \left ( x[m] - \left (y_{\underline{i}}[n-1] + 2 \gamma [n] \left (x[n] - y_{\underline{i}}[n-1] \right ) \right ) \right ) & = 0 \nonumber
\end{align}
dove $\underline{i}$ sono determinati dalla condizione
\begin{align}
  \varepsilon_{x_{\underline{i}}[n-1],x_{\underline{i}+1}[n-1]}(x[n]) \neq 0
\end{align}
da cui otteniamo il valore ottimale per $\gamma[n]$
\begin{align}
  \gamma^*[n] = \frac{\frac{1}{n^*} \sum_{m=1}^n x[m] - y_{\underline{i}}[n-1]}{2 (x[n] - y_{\underline{i}}[n-1])}
\end{align}
dove la sommatoria dei valori $x[m]$, che appartengono all'intervallo $x_{\underline{i}}[n-1], x_{\underline{i}+1}[n+1]$ per i quali, per ogni $\varepsilon_{x_{\underline{i}}[n-1],x_{\underline{i}+1}[n-1]}(x[m]) \neq 0$ e $n^*$ \`e il numero di questi valori.

Se introduciamo $\gamma^*[n]$ nell'algoritmo, otteniamo
\begin{align}
  y_i = \frac{1}{n^*} \sum_{m=1}^n x[m]
\end{align}

Questa equazione mostra che per ogni passo i valori $y_i^*$ tendono a eguagliare il valore medio di tutti gli $x[m]$, che appartengono all'intervallo $x_i[n-1], x_{\underline{i}+1}[n-1]$ al passo precedente.

Al termine di questo lavoro\footnote{Questo lavoro costituisce la tesi di fine corso, giugno 1967, di uno stage presso l'Istituto di Energetica di Mosca MEI (\url{http://www.mpei.ru}), annesso al Politecnico.} desidero ringraziare caldamente il prof. Yakov Zalmanovitch Tsypkin\footnote{In Memoria di Yakov Zalmanovitch Tsypkin: A Life in Feedback Control, \url{http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=664147}} per il grande aiuto e appoggio datomi per la sua stesura.

\begin{thebibliography}{9}

  \begin{otherlanguage*}{russian}

  \bibitem{doc1}
    Цыпкин Я. З.,
    Адаптация, обучение и самообучение в автоматических системах,
    Автоматика и телемеханика, 1, 1966.

  \bibitem{doc2}
    Joel Max,
    Quantizing for minimum distorsion,
    IRE Transactions on Information Theory,
    Vol. 6 marzo 1960, N. 1.

  \bibitem{doc3}
    Кошелев В. Н.,
    Квантование с минимальной энтропией,
    Проблемы передачи информации АН СССР, выпуск 14, 1963.

  \bibitem{doc4}
    Солодов А. В.,
    Теориа информации и ее применение к задачам автоматического уравления и контроля,
    Изд-во Наука, Москва, 1967.

  \bibitem{doc5}
    Tou J.,
    Optimum design of digital control systems,
    Academic Press, 1963.

  \end{otherlanguage*}

\end{thebibliography}

\end{document}