{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "nbsphinx": "hidden"
   },
   "source": [
    "# Realization of Non-Recursive Filters\n",
    "\n",
    "*This jupyter notebook is part of a [collection of notebooks](../index.ipynb) on various topics of Digital Signal Processing. Please direct questions and suggestions to [Sascha.Spors@uni-rostock.de](mailto:Sascha.Spors@uni-rostock.de).*"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Introduction\n",
    "\n",
    "Computing the output $y[k] = \\mathcal{H} \\{ x[k] \\}$ of a [linear time-invariant](https://en.wikipedia.org/wiki/LTI_system_theory) (LTI) system is of central importance in digital signal processing. This is often referred to as [*filtering*](https://en.wikipedia.org/wiki/Digital_filter) of the input signal $x[k]$. The methods for this purpose are typically classified into\n",
    "\n",
    "* non-recursive and\n",
    "* recursive\n",
    "\n",
    "techniques. This section focuses on the realization of non-recursive filters."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Non-Recursive Filters\n",
    "\n",
    "An LTI system can be characterized completely by its impulse response $h[k]$ \n",
    "\n",
    "![Linear time-invariant system](LTI_system_td.png)\n",
    "\n",
    "The output signal $y[k]$ is given by (linear) convolution of the input signal $x[k]$ with the impulse response $h[k]$\n",
    "\n",
    "\\begin{equation}\n",
    "y[k] = x[k] * h[k] = \\sum_{\\kappa = -\\infty}^{\\infty} x[\\kappa] \\; h[k-\\kappa]\n",
    "\\end{equation}\n",
    "\n",
    "Two aspects of this representation become evident when inspecting above equation:\n",
    "\n",
    "1. The output signal $y[k]$ is a linear combination of the input signal $x[k]$. There is no feedback of the output signal of past time-instants. Therefore, such filters are termed as *non-recursive* filters.\n",
    "\n",
    "2. In order to compute the output signal at one particular time-instant $k$, the input signal needs to be known for all past and future time-instants.\n",
    "\n",
    "The second aspect prohibits a practical realization. In order to be able to realize a non-recursive filter by convolution, the output at time-instant $k$ should only depend on the input signal $x[k]$ up to time-index $k$\n",
    "\n",
    "\\begin{equation}\n",
    "y[k] = \\sum_{\\kappa = -\\infty}^{k} x[\\kappa] \\; h[k-\\kappa]\n",
    "\\end{equation}\n",
    "\n",
    "This is the case when the impulse response is causal, hence when $h[k] = 0$ for $k<0$. However, this still requires knowledge of the input signal for all past time-instants. If we further assume that the input signal is causal, $x[k] = 0$ for $k<0$, we get\n",
    "\n",
    "\\begin{equation}\n",
    "y[k] = \\sum_{\\kappa = 0}^{k} x[\\kappa] \\; h[k-\\kappa]\n",
    "\\end{equation}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Finite Impulse Response\n",
    "\n",
    "Many practical systems have an impulse response of finite length $N$ or can be approximated by an impulse response of finite length\n",
    "\n",
    "\\begin{equation}\n",
    "h_N[k] = \\begin{cases} h[k] & \\text{ for } 0 \\leq k < N \\\\ 0 & \\text{ otherwise} \\end{cases}\n",
    "\\end{equation}\n",
    "\n",
    "Such an impulse response is denoted as [*finite impulse response*](https://en.wikipedia.org/wiki/Finite_impulse_response) (FIR). Introducing $h_N[k]$ into above sum and rearranging terms yields\n",
    "\n",
    "\\begin{equation}\n",
    "y[k] = \\sum_{\\kappa = 0}^{k} x[\\kappa] \\; h_N[k-\\kappa] = \\sum_{\\kappa = 0}^{N-1} h_N[\\kappa] \\; x[k-\\kappa]\n",
    "\\end{equation}\n",
    "\n",
    "Hence for a causal input signal $x[k]$ and a FIR the output of the system can be computed by a finite number of operations. \n",
    "\n",
    "The evaluation of the convolution for a FIR of length $N$ requires $N$ multiplications and $N-1$ additions per time index $k$. For the real-time convolution of an audio signal with a sampling rate of $f_\\text{S} = 48$ kHz with a FIR of length $N = 48000$ we have to compute around $2 \\times 2.3 \\cdot 10^9$ numerical operations per second. This is a considerable numerical complexity, especially on embedded or mobile platforms. Therefore, various techniques have been developed to lower the computational complexity."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "nbsphinx": "hidden"
   },
   "source": [
    "**Copyright**\n",
    "\n",
    "This notebook is provided as [Open Educational Resource](https://en.wikipedia.org/wiki/Open_educational_resources). Feel free to use the notebook for your own purposes. The text is licensed under [Creative Commons Attribution 4.0](https://creativecommons.org/licenses/by/4.0/), the code of the IPython examples under the [MIT license](https://opensource.org/licenses/MIT). Please attribute the work as follows: *Sascha Spors, Digital Signal Processing - Lecture notes featuring computational examples*."
   ]
  }
 ],
 "metadata": {
  "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.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}