{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# MAC0317/MAC5920\n",
    "## Introdução ao Processamento de Sinais Digitais\n",
    "## Seção 7.3: O Banco de Filtros Geral de 1 Estágio e 2 Canais"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Seção 7.3.1: Formulação para filtros FIR arbitrários\n",
    "\n",
    "Tudo o que foi desenvolvido na seção 7.2 pode ser generalizado para uma coleção bastante geral de pares de filtro $l_a,l_s$ (passa-baixas de análise e de síntese) e $h_a,h_s$ (passa-altas de análise e de síntese), desde que determinados cuidados sejam tomados para garantir que *nenhuma informação é perdida no processo* (garantindo com isso que *a reconstrução do sinal original seja perfeita*)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "O objetivo será preservar a estrutura geral da transformada, ou seja, a etapa de análise consiste em\n",
    "\n",
    "> 1. Filtrar: $l_a*x$ e $h_a*x$;\n",
    "> 2. Subamostrar: $X_l=D(l_a*x)$ e $X_h=D(h_a*x)$;\n",
    "> 3. Combinar os resultados: $X=(X_l,X_h)$;\n",
    "\n",
    "enquanto a etapa de síntese consiste em\n",
    "\n",
    "> 1. Superamostrar: computar $U(X_l)$ e $U(X_h)$;\n",
    "> 2. Filtrar: $v_l=l_s*U(X_l)$ e $v_h=h_s*U(X_h)$;\n",
    "> 3. Combinar os resultados: $x=v_l+v_h$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Observação 7.2\n",
    "\n",
    "O esquema descrito acima é chamado de *banco de filtros em dois canais* porque os sinais são separados em duas componentes, processadas paralelamente por dois filtros com características espectrais diferentes (um passa-baixas e um passa-altas).\n",
    "\n",
    "*Bancos de filtros em $M$ canais* funcionam de maneira análoga, porém o sinal de entrada é filtrado paralelamente por $M$ filtros, dando origem a $M$ componentes $X_1,X_2,\\ldots,X_M$ que capturariam faixas de frequência distintas. Os sinais filtrados são geralmente subamostrados numa relação de $M:1$, a fim de eliminar as redundâncias.\n",
    "\n",
    "A teoria que trata do desenho de bancos de filtros de $M$ canais a fim de garantir reconstrução perfeita é chamada de *codificação sub-banda* (*subband coding*) e foge ao escopo desse curso."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Reconstrução perfeita (definição 7.3)\n",
    "\n",
    "Dado um banco de filtros $\\{l_a,h_a,l_s,h_s\\}$ que define o par de transformações $x\\mapsto X=(X_l,X_h)=(D(l_a*x),D(h_a*x))$ (análise) e $X\\mapsto l_s*U(X_l)+h_s*U(X_h)$ (síntese), dizemos que o banco de filtros possui *reconstrução perfeita* se a equação de síntese é a inversa da equação de análise, ou seja, se\n",
    "\n",
    "$$x = l_s*U(D(l_a*x))+h_s*U(D(h_a*x))$$\n",
    "\n",
    "para qualquer sinal $x$. Um banco de filtros com reconstrução perfeita também é chamado de *biortogonal*."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Ocasionalmente consideraremos também filtros cuja reconstrução ocorre com um certo atraso, como é o caso do banco de Haar com filtros causais. Nesse caso, a condição de reconstrução perfeita equivale a existir algum $m\\in\\mathbb{Z}$ tal que\n",
    "\n",
    "$$S^m(x) = l_s*U(D(l_a*x))+h_s*U(D(h_a*x))$$\n",
    "\n",
    "para qualquer sinal $x$, onde $S$ é o operador de atraso definido na seção 7.2 (e $S^m$ é sua aplicação repetida $m$ vezes, ou seja, um atraso de $m$ amostras)."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Desenho de bancos de filtros\n",
    "\n",
    "A equação de reconstrução perfeita não ajuda muito na construção de bancos de filtros em geral, já que equivale a um sistema de infinitas equações (lembre-se que os sinais estão em $L^2(\\mathbb{Z})$) e envolve produtos de coeficientes dos filtros de análise e síntese.\n",
    "\n",
    "Em alguns casos muito particulares, como quando os filtros de análise já são conhecidos, é possível desenvolver essas equações para construir os filtros correspondentes de síntese, como veremos no exemplo a seguir."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Exemplo 7.3\n",
    "\n",
    "Considere que usaremos os filtros de análise de Haar ($(l_a)_0=(l_a)_1=\\frac{1}{2}$ e $(h_a)_0=-(h_a)_1=\\frac{1}{2}$, com todos os demais coeficientes nulos), e desejamos encontrar filtros de síntese (supondo desconhecidos) que satisfaçam a equação de reconstrução perfeita sem atraso\n",
    "\n",
    "$$x = l_s*U(D(l_a*x))+h_s*U(D(h_a*x)),$$\n",
    "\n",
    "que pode ser escrita em função de cada amostra do sinal $x$ como\n",
    "\n",
    "$$x_n = (l_s*U(D(l_a*x)))_n+(h_s*U(D(h_a*x)))_n.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Lembrando que $(l_a*x)_n=\\frac{1}{2}(x_n+x_{n-1})$ e $(h_a*x)_n=\\frac{1}{2}(x_n-x_{n-1})$, e que $U(D(y))_n=\\left\\{\\begin{array}{ll}y_n,&\\mbox{se $n$ é par,}\\\\0,&\\mbox{se $n$ é ímpar,}\\end{array}\\right.$, podemos re-escrever a equação de reconstrução perfeita como\n",
    "\n",
    "$$\\begin{array}{ll}\n",
    "x_n&=\\displaystyle\\frac{1}{2}\\sum_{k\\ \\small\\mbox{par}}(x_k+x_{k-1})(l_s)_{n-k}+(x_k-x_{k-1})(h_s)_{n-k}\\\\\n",
    "&=\\displaystyle\\frac{1}{2}\\sum_{k\\ \\small\\mbox{par}}x_k\\left[(l_s)_{n-k}+(h_s)_{n-k}\\right]+x_{k-1}\\left[(l_s)_{n-k}-(h_s)_{n-k}\\right],\\end{array}$$\n",
    "\n",
    "e ela precisa valer para qualquer sinal $x\\in L^2(\\mathbb{Z})$."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Considere o sinal de entrada $x=\\delta$ dado por $x_0=1$ e $x_k=0,\\ \\forall k\\neq 0$. Então a equação anterior \n",
    "\n",
    "$$\\begin{array}{ll}\n",
    "x_n&=\\displaystyle\\frac{1}{2}\\sum_{k\\ \\small\\mbox{par}}x_k\\left[(l_s)_{n-k}+(h_s)_{n-k}\\right]+x_{k-1}\\left[(l_s)_{n-k}-(h_s)_{n-k}\\right]\\\\\n",
    "&=\\displaystyle\\frac{1}{2}x_0\\left[(l_s)_{n-0}+(h_s)_{n-0}\\right]\\quad\\quad\\mbox{(sobra apenas $k=0$ na $\\sum$)}\\end{array}$$\n",
    "\n",
    "se reduz a\n",
    "\n",
    "$$(l_s)_{n}+(h_s)_{n}=\\left\\{\\begin{array}{ll}2,&n=0,\\\\0,&n\\neq 0.\\end{array}\\right.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Considere agora o sinal de entrada $x=S(\\delta)$ dado por $x_1=1$ e $x_k=0,\\ \\forall k\\neq 1$. Então a equação anterior \n",
    "\n",
    "$$\\begin{array}{ll}\n",
    "x_n&=\\displaystyle\\frac{1}{2}\\sum_{k\\ \\small\\mbox{par}}x_k\\left[(l_s)_{n-k}+(h_s)_{n-k}\\right]+x_{k-1}\\left[(l_s)_{n-k}-(h_s)_{n-k}\\right]\\\\\n",
    "&=\\displaystyle\\frac{1}{2}x_1\\left[(l_s)_{n-2}-(h_s)_{n-2}\\right]\\quad\\quad\\mbox{(sobra apenas $k=2$ na $\\sum$)}\\end{array}$$\n",
    "\n",
    "se reduz a\n",
    "\n",
    "$$(l_s)_{n-2}-(h_s)_{n-2}=\\left\\{\\begin{array}{ll}2,&n=1,\\\\0,&n\\neq 1,\\end{array}\\right.$$\n",
    "\n",
    "ou equivalentemente\n",
    "\n",
    "$$(l_s)_{n}-(h_s)_{n}=\\left\\{\\begin{array}{ll}2,&n=-1,\\\\0,&n\\neq -1,\\end{array}\\right.$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Juntando as duas condições\n",
    "\n",
    "$$(l_s)_{n}+(h_s)_{n}=\\left\\{\\begin{array}{ll}2,&n=0,\\\\0,&n\\neq 0.\\end{array}\\right.\\quad\\quad\\quad(l_s)_{n}-(h_s)_{n}=\\left\\{\\begin{array}{ll}2,&n=-1,\\\\0,&n\\neq -1,\\end{array}\\right.$$\n",
    "\n",
    "podemos concluir para $n=0$ que $(l_s)_0=(h_s)_0=1$ e para $n=-1$ que $(l_s)_{-1}=-(h_s)_{-1}=1$, ao passo que para $n\\neq 0,-1$ concluímos que $(l_s)_n=(h_s)_n=0$.\n",
    "\n",
    "Isso mostra que os filtros $l_s=(\\ldots,0,1,\\overbrace{1}^{\\small n=0},0,\\ldots)$ e $h_s=(\\ldots,0,-1,\\overbrace{1}^{\\small n=0},0,\\ldots)$, que já sabíamos obedecer a condição de reconstrução perfeita, são na realidade **os únicos filtros de síntese** compatíveis com o par de filtros de análise $(l_a,h_a)$ correspondentes ao filtro da média e da diferença."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Exemplo 7.4\n",
    "\n",
    "Um outro conjunto de filtros biortogonais que estudaremos são os filtros **Le Gall 5/3**:\n",
    "\n",
    "$$\\begin{array}{lcc}\n",
    "l_a&=&(\\ldots,0,-\\frac{1}{8},\\frac{1}{4},\\overbrace{\\frac{3}{4}}^{\\small n=0},\\frac{1}{4},-\\frac{1}{8},0,\\ldots)\\\\\n",
    "h_a&=&(\\ldots,0,-\\frac{1}{2},1,-\\frac{1}{2},0,\\ldots)\\\\\n",
    "l_s&=&(\\ldots,0,\\frac{1}{2},1,\\frac{1}{2},0,\\ldots)\\\\\n",
    "h_s&=&(\\ldots,0,-\\frac{1}{8},-\\frac{1}{4},\\frac{3}{4},-\\frac{1}{4},-\\frac{1}{8},0,\\ldots)\n",
    "\\end{array}$$\n",
    "\n",
    "Observe como os coeficientes dos filtros parecem estar relacionados: $l_a$ possui \"quase\" os mesmos coeficientes que $h_s$, e o mesmo ocorre com $h_a$ e $l_s$. Os detalhes da construção desse banco de filtros serão apresentados na seção 7.7."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "### Seção 7.3.3: Bancos de filtro ortogonais\n",
    "\n",
    "Existem infinitos bancos de filtro que satisfazem a equação de reconstrução perfeita, por isso é interessante considerar condições que restrinjam as escolhas possíveis para o desenho de filtros. Uma dessas condições é considerar conhecidos os filtros de análise, como fizemos no exemplo 7.3. Outra possibilidade é criar vínculos entre os coeficientes dos filtros de análise e de síntese, como aqueles vistos no banco de filtros Le Gall 5/3, ou nos próprios filtros de Haar, que satisfazem\n",
    "\n",
    "$$(l_s)_k = 2(l_a)_{-k}\\quad\\quad\\mbox{e}\\quad\\quad(h_s)_k = 2(h_a)_{-k}.$$\n",
    "\n",
    "Esse é um tipo de situação muito comum, e geralmente é possível eliminar a constante $C=2$ na condição acima através de uma mudança de escala adequada. Nesse caso, buscaremos filtros que satisfazem\n",
    "\n",
    "$$(l_s)_k = (l_a)_{-k}\\quad\\quad\\mbox{e}\\quad\\quad(h_s)_k = (h_a)_{-k}.$$\n",
    "\n",
    "Bancos de filtros que satisfazem essa condição são chamados de ortogonais, por razões que ficarão claras na seção 7.5."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "### Exemplo 7.5\n",
    "\n",
    "O banco de filtros de Haar, que satisfaz a condição\n",
    "\n",
    "$$(l_s)_k = 2(l_a)_{-k}\\quad\\quad\\mbox{e}\\quad\\quad(h_s)_k = 2(h_a)_{-k}.$$\n",
    "\n",
    "pode facilmente satisfazer a condição de ortogonalidade fatorando-se a constante $2=\\sqrt{2}\\sqrt{2}$ e passando um dos termos para o outro lado:\n",
    "\n",
    "$$\\frac{1}{\\sqrt{2}}(l_s)_k = \\sqrt{2}(l_a)_{-k}\\quad\\quad\\mbox{e}\\quad\\quad\\frac{1}{\\sqrt{2}}(h_s)_k = \\sqrt{2}(h_a)_{-k}.$$\n",
    "\n",
    "Essa fatoração não afeta a condição de reconstrução perfeita porque todas as operações envolvidas são lineares e os fatores novos se cancelam:\n",
    "\n",
    "$$x = \\frac{1}{\\sqrt{2}}l_s*U(D(\\sqrt{2}l_a*x))+\\frac{1}{\\sqrt{2}}h_s*U(D(\\sqrt{2}h_a*x)).$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "subslide"
    }
   },
   "source": [
    "Assim, definindo-se\n",
    "\n",
    "$$\\begin{array}{lllrcccl}\n",
    "\\tilde{l}_a&=\\sqrt{2}(l_a)&=&(\\ldots,0,&0,&\\overbrace{\\frac{\\sqrt{2}}{2}}^{\\small n=0},&\\frac{\\sqrt{2}}{2},&0,\\ldots)\\\\\n",
    "\\tilde{l}_s&=\\frac{1}{\\sqrt{2}}(l_s)&=&(\\ldots,0,&\\frac{\\sqrt{2}}{2},&\\frac{\\sqrt{2}}{2},&0,&0,\\ldots)\\\\\n",
    "\\tilde{h}_a&=\\sqrt{2}(h_a)&=&(\\ldots,0,&0,&\\frac{\\sqrt{2}}{2},&-\\frac{\\sqrt{2}}{2},&0,\\ldots)\\\\\n",
    "\\tilde{h}_s&=\\frac{1}{\\sqrt{2}}(h_s)&=&(\\ldots,0,&-\\frac{\\sqrt{2}}{2},&\\frac{\\sqrt{2}}{2},&0,&0,\\ldots),\n",
    "\\end{array}$$\n",
    "\n",
    "teremos um banco de filtros com reconstrução perfeita que satisfaz\n",
    "\n",
    "$$(\\tilde{l}_s)_k = (\\tilde{l}_a)_{-k}\\quad\\quad\\mbox{e}\\quad\\quad(\\tilde{h}_s)_k = (\\tilde{h}_a)_{-k}.$$"
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.11"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}