#!/usr/bin/env python
# coding: utf-8

# # Realization of Non-Recursive Filters
# 
# *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).*

# ## Introduction
# 
# 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
# 
# * non-recursive and
# * recursive
# 
# techniques. This section focuses on the realization of non-recursive filters.

# ### Non-Recursive Filters
# 
# An LTI system can be characterized completely by its impulse response $h[k]$ 
# 
# ![Linear time-invariant system](LTI_system_td.png)
# 
# The output signal $y[k]$ is given by (linear) convolution of the input signal $x[k]$ with the impulse response $h[k]$
# 
# \begin{equation}
# y[k] = x[k] * h[k] = \sum_{\kappa = -\infty}^{\infty} x[\kappa] \; h[k-\kappa]
# \end{equation}
# 
# Two aspects of this representation become evident when inspecting above equation:
# 
# 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.
# 
# 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.
# 
# 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$
# 
# \begin{equation}
# y[k] = \sum_{\kappa = -\infty}^{k} x[\kappa] \; h[k-\kappa]
# \end{equation}
# 
# 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
# 
# \begin{equation}
# y[k] = \sum_{\kappa = 0}^{k} x[\kappa] \; h[k-\kappa]
# \end{equation}

# ### Finite Impulse Response
# 
# Many practical systems have an impulse response of finite length $N$ or can be approximated by an impulse response of finite length
# 
# \begin{equation}
# h_N[k] = \begin{cases} h[k] & \text{ for } 0 \leq k < N \\ 0 & \text{ otherwise} \end{cases}
# \end{equation}
# 
# 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
# 
# \begin{equation}
# y[k] = \sum_{\kappa = 0}^{k} x[\kappa] \; h_N[k-\kappa] = \sum_{\kappa = 0}^{N-1} h_N[\kappa] \; x[k-\kappa]
# \end{equation}
# 
# 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. 
# 
# 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.

# **Copyright**
# 
# 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*.