DokuWiki

You've loaded an old revision of the document! If you save it, you will create a new version with this data.

======= ELEN90058 - Signal Processing =======
{{tag>notes unimelb electrical_engineering math}}
====== Introduction ======

Signals are used all over. When signals are read, they tend to be sampled as digital processing is easier than analogue, so processing the signal treats it as a discrete time function. In sampling, noise can be inferred onto the signal, distorting it randomly. The aim of signal processing is to remove the noise and recreate the original signal. This can be done by applying filters, such as a moving average. Filters that are linear time invariant map sinusoids to sinusoids, and as such can be effective in removing added noise. A sinusoid in continuous time is of the form: $$x(t)=A\cos(2\pi ft)+B\sin(2\pi ft)=\alpha\cos(2\pi ft+\theta)$$ The constants $A,B,f,\alpha,\theta$ are unique. When sampled into discrete time, we get: $$x[k]=A\cos(2\pi fk)+B\sin(2\pi fk)$$ This is not unique as the frequency can always be shifted by an integer amount to provide the same sinusoid. This means we can always find a frequency between 0 and 1 for a given sinusoid.

===== Signals and systems =====

A system is a thing that takes a signal as an input and produces a signal at the output. A signal is a doubly infinite sequence of numbers. We write a system as: $$y-L\{x\}$$ where L is some mathematical rule expressing each $y[k]$ as a function of $\dotsb,x[-2],x[-1],x[0],x[1],x[2],\dotsb$. We tend to define systems in terms of mathematical rules, as it makes them simpler to work with and means we don't need to enumerate all the values of the transformation. The definition can be finite or infinite. A linear system is one where: $$L\{ax+by\}=aL\{x\}+bL\{y\}$$ for all possible inputs $x$ and $y$ and scalars $a$ and $b$. For systems with infinite impulse responses, we need to be careful not to provide input for which the output is undefined. To prove a system is linear, you need to prove it passes additivity and multiplicativity. To prove a system is nonlinear, you need to provide a signal for which it fails linearity. A system is time-invariant if the only effect of shifting the input in time is that the output is shifted by the same amount of time. First we define a system $y=L\{x\}$, then we define $v=L\{u\}$ where $u[k]=x[k-d]$. The system is time-invariant if $v[k]=y[y-d]$. While we work with real valued functions, it can be easier to express them as complex functions. $$y[k]=A*e^{j2\pi fk}$$

===== Signal processing hardware =====

In digital signal processing, we can use an FPGA, DSP, CPU or ASIC, and they all have their own strengths and weaknesses. The choice of which to use depends on the project requirements, costs, speeds, etc. Traditionally FPGAs are more energy efficient but have higher development costs, but now there are better tools making development faster. A DSP is a specialised CPU, both having a fetch-execute cycle and have interrupts. A DSP is a specialised CPU designed for signal processing. DSPs can have execution time determined beforehand and are designed for high-throughput. As a result DSPs are designed for real-time signal processing, high-throughput applications, but are not as general purpose.

===== LTI frequency responses =====

If a complex exponential (sinusoid) is fed into a LTI system, a complex exponential comes out also. It can, however, be scaled. The coefficient of the exponential is the frequency response, $H(\omega)$, where $\omega$ is the input frequency. As the frequency response is complex, it can be useful to plot its magnitude and phase. If our frequency response is periodic with period $2\pi$, the filter alters the magnitude and phase of $e^{j(\omega+2\pi)k}$ the same as $e^{j\omega k}$. This is because they are the same signals due to aliasing, which is sampling to remove high-frequency behaviour. We can use the frequency response to characterise the system and determine what will happen to a given signal passed through. A spectral null is when the frequency response is equal to 0, meaning that a sinusoid passing in produces no output.

===== Fourier transform =====

Because it is easy to work with complex exponentials, we want to represent an input signal as a sum of complex exponentials. If the input is already a sum, the work is already done, however we cannot represent every signal as a sum of finite exponentials. Se we use an infinite number of complex exponentials. $$x[k]=\frac{1}{2\pi}\int_{-\pi}^\pi X(\omega)e^{j\omega j}d\omega$$ The $X(\omega)$ term is found using the discrete-time Fourier transform (DTFT): $$X(\omega)=\sum_{k=-\infty}^{\infty}x[k]e^{-j\omega k}$$ We note that $X(\omega)$ is periodic with period $2\pi$. With the transform of the function, we can get the transform of the output from the product of the input and frequency response. $$y[k]=\frac{1}{2\pi}\int_{-\pi}^\pi X(\omega)H(\omega)e^{j\omega k}d\omega$$ $$Y(\omega)=X(\omega)H(\omega)$$ We can recover $x[k]$ with the inverse DTFT: $$x[k]=\frac{1}{2\pi}\int_{-\pi}^\pi X(\omega)e^{j\omega k}d\omega$$ The inverse transform of the frequency response gives the impulse response: $$h=\text{InvDTFT}\{H\}$$ This is the output when $x=\delta$. We can find the output signal from with the impulse response with convolution: $$y[k]=x\star h=\sum_{k'=-\infty}^\infty x[k']h[k-k']$$ The Fourier transform turns convolution into multiplication. We define the transform of the complex exponential as a shifted delta function: $$\text{DTFT}\{e^{j\omega'k}\}=\delta(\omega-\omega')$$

====== Filter design ======

In designing a filter, we chose a frequency response $H(\omega)$, and design hardware to implement it. An ideal low-pass filter allows small frequencies to pass through unattentuated and blocks all high frequencies. The transition is called the cut off frequency. $$H_{LP}(\omega)=\begin{cases}1,&|\omega|<\omega_c\\\frac{1}{2},&|\omega|=\omega_c\\0,&\omega_c<|\omega|\leq\pi\end{cases}$$ $$h_{LP}[k]=\begin{cases}\frac{\sin(\omega_ck)}{\pi k},&k\neq 0\\\frac{\omega_c}{\pi},&k=0\end{cases}$$ Trouble in designing a filter comes from incomplete access to the signal (the signal is still arriving in the future). Filter design is about approximating the ideal characteristics so the implementation becomes practical.

A system whose output at time k depends only on inputs at times before k is causal. If the output depends on times after k the system is anti-causal. A system that is not causal is non-causal or acausal. All natural systems are causal as we are not able to see into the future.

Real filters have a cutoff as they do not work across an infinite range of filters. The cutoff causes fringing, called the Gibbs phenomenon.

====== Sample rate ======

Choosing a sample rate can have run on effects, so is a non-trivial task. If we sample a 3kHz tone at 48kHz, we get a samples sinusoid of 1/16 Hz. If we sample at 96 kHz, the sampled signal is 1/32 Hz. The sampled frequency is dependent on the sample rate and is called the normalised frequency. Every normalised frequency lies between 0 and 1/2, with the angular frequency between 0 and $\pi$. We chose complex exponential frequencies to lie between -1/2 and 1/2, which we can find equivalent signals with trigonometric transformations. If the normalised frequency is outside the range of 0 to 1/2, we can subtract 1 until it lies in the range. As an alternative we can treat the time index as related to amounts of time and work with the real frequency, but it turns out being easier to use normalised frequency. When processing real world signals, real-valued signals are the norm. It can be useful to use complex-valued signals sometimes though, such as in wireless communication networks. Because the sample rate determines the normalised to real frequency relationship, we need to store it in order to decode the signal properly. When processing the sampled signals, we need to adjust the cutoff frequencies to work with the normalised frequencies.

The ideal ADC converter implements $x[k]=x(kT)$, but a DAC is a bit more complex. Because the ADC implements a many to one mapping, the DAC is unable to perfectly invert it. This inability is due to high frequency signals being aliased to lower signals, e.g. a 2 and 10 kHz signal being the same at 8 kHz sample rate. As such an ideal DAC will interpolate $y[k]$ by the unique sinusoid $y(t)$ with a frequency between 0 Hz and half the sample rate. As such, the sample rate should be chosen to be above double the highest frequency. The ideal DAC is linear, and produces $y(t)=e^{j2\pi t}$ when given $y[k]=e^{j2\pi k}$ and $|f|\leq\frac{1}{2}$. That is, the DAC produces the lowest frequency output for the given data points. The ideal DAC must observe the whole input sequence, so we can never implement an ideal DAC. Mathematically, a DAC with an arbitrary sample rate can be constructed from a DAC with a sample rate of 1 Hz by altering the time base.

The Nyquist Rate is the minimum sampling rate needed to preserve the signal after sampling and reconstruction. It is equal to double the highest frequency present in the signal, although we tend to sample higher to keep with error. In reality a large number of sampling frequencies are used depending on the use case. Lower sample rates can be useful when dealing with data limits and higher sample rates can be useful when dealing with jitter and technical faults from the ADC.

Changing the sample rate can produce a new signal. Increasing the sample rate is upsampling and decreasing the sample rate is downsampling. Changing the sample rate by an integer amount allows us to change by a rational factor of the original rate. Downsampling by a factor of N means we set $x_2[k]=x_1[kN]$. This cause the DTFT to become: $$X_2(\omega)=\frac{1}{N}\sum_{n=0}^{N-1}X_1(\frac{\omega-2\pi n}{N})$$ If we apply this to a signal with high frequencies, we can see aliasing corrupt our signal. In upsampling, the Nyquist criterion is automatically fulfilled. The new signal is the following, given we have a low-pass filter ($H_{LP}(\omega)$) with an angular cutoff of $\pi/N$: $$X_2(\omega)=NH_{LP}(\omega)X_1(N\omega)$$ While downsampling can be performed online, an ideal upsampler cannot due to the low pass filter. Also, upsampling and DAC is a similar operation.

To up-sample by an integer amount, we add zeros in between the existing values. we then apply a low pass filter to the modified signal. The stage of inserting the 0s is called expansion, the application of the LPF and the scaling is called interpolation. As such the LPF used can be called an interpolation filter. We can use a finite response filter (FIR) easily. We can also use a recursive filter (Infinite Impulse Response, IIR): $$y[k]=\sum_{m=1}^M\alpha_my[k-m]x[k]$$ We can also chain an IIR filter with a FIR filter. As an ideal LPF cant be implemented, we need to trade off speed and accuracy in our filter design.

The DTFT of the product of two signals is the convolution of their DTFTs. $$DTFT\{w[k]\sin(2\pi k/16)\}=DTFT\{w[k]\}\star DTFT\{\sin(2\pi k/16)\}$$ $$(W\star X)(\omega)=\frac{1}{2\pi}\int_{-\pi}^\pi W(\nu)X(\omega-\nu)d\nu$$ The convolution is restricted, becoming a circular convolution. The convolution causes a smoothing effect to the signal. When sampling over a finite region of time, we are multiplying by a square wave, causing a sinc function in the DTFT. Taking more cycles uses a longer rectangular pulse, causing a narrower sinc function and thus less distortion in the DTFT. Changing the windowing function from a rectangular pulse to something else can make the found DTFT nicer, removing the convolved sinc function.

====== Block based processing ======

Filters can need past information about the input signal, so we need to store parts of the signal. The input signal can be arbitrarily large, making it impractical to store all of it. As a result we store blocks of the signal and continuously shift the amount stored so that we only store the parts that we need. This is done in C with global, static variables or structs. In object oriented languages like C++ and MATLAB, we do with objects. The objects store a buffer of the past signal, and have a step function to apply to each block. This step and store is done while there is an input signal, with the incoming signal being moved into the buffer replacing the old stored signal.

====== ARMA filter ======

An ARMA filter is an Auto-Regressive Moving Average filter. AR is IIR filter, MA is FIR. Moving average filters can have spectral nulls, and need many terms to have sharp spectral peaks. Auto-Regressive filters are of the form: $$y[k]=\alpha_1y[k-1]+...+\alpha_Ny[k-N]+x[k]$$ This is a difference equation and can be studied with a generating function.

===== Fibonacci Sequence =====

The Fibonacci numbers are defined by the difference equation: $$F_n=F_{n-1}+F_{n-2}$$ We initialise it as $F_n=0,\forall n$. As computing it is expensive, we want a function to find the nth number non recursively. We want to associate the generating function with the formal power series: $$g(x)=\sum_{n=0}^\infty F_nx^n=F_0+F_1x+F_2x^2+F_3x^3+...$$ If we can find another expression for $g(x)$, we may be able to use that expression to find the coefficients of $g(x)$, being the values of $F_n$. We can write: $$g(x)=x+\sum_{n=2}^\infty f_nx^n=x+\sum_{n=2}^\infty F_{n-1}x^n+\sum_{n=2}^\infty F_{n-2}x^n=x+xg(x)+x^2g(x)$$ $$g(x)=\frac{x}{1-x-x^2}$$ If we can write $(1-x-x^2)^{-1}$ as a power series of x, we are set. Note that $(1-x)-1=1+x+x2=x3+…$, suggesting to use a partial fraction expansion. $$g(x)=\frac{-x}{(x+\lambda_-)(x+\lambda_+)}=\frac{A}{x+\lambda_-}+\frac{B}{x+\lambda_+},\lambda=\frac{1\pm\sqrt{5}}{2}$$ $$g(x)=\frac{1}{\sqrt{5}}\left(\frac{\lambda_-}{x+\lambda_-}-\frac{\lambda_+}{x+\lambda_+}\right)$$ We use the identity $\frac{-\alpha^{-1}}{x-\alpha^{-1}}=\frac{1}{1-\alpha x}=\sum_{n=0}^\infty\alpha^nx^n$ to find: $$\frac{\lambda_-}{x+\lambda_-}=\sum_{n=0}^\infty\lambda_+^nx^n,\frac{\lambda_+}{x+\lambda_+}=\sum_{n=0}^\infty\lambda_-^nx^n$$ So we get: $$f(x)=\sum_{n=0}^\infty\frac{1}{\sqrt{5}}(\lambda_+^n-\lambda_-^n)x^n$$ Giving the final answer as: $$F_n=\frac{1}{\sqrt{5}}(\lambda_+^n-\lambda_-^n)$$

==== Faster method ====

We will guess the solutions are of the form $F_n=\lambda^n$. $$\lambda^n=\lambda^{n-1}+\lambda^{n-2}$$ $$\lambda^2=\lambda+1$$ Solving this gives two solutions: $\lambda=\frac{1\pm\sqrt{5}}{2}$, which direct substitution shows are solutions. Linearity implies $F_n=\alpha\lambda_-^n+\beta\lambda_+^n$ is also a solution. Given initial values, we can fix $\alpha$ and $\beta$.

===== AR(1) systems =====

A recursive system with a singular input is an AR(1) system, e.g.: $$y[k]=\alpha y[k-1]+x[k]$$ It can be applied recursively given an initial condition. A homogeneous solution is one where $x[k]=0,\forall k$. Solutions to the equation are the sum of a particular solution and a solution to the homogeneous equation (due to linearity). These can be calculated forward and backward in time, which can cause problems in the math.

We create some generating functions: $$X(z)=\sum_{k=-\infty}^\infty x[k]z^{-k}$$ This is a double-sided power series, which can be problematic. $z^{-1}$ is called the unit delay operator, because: $$Y(z)=z^{-1}X(x)\implies y[k]=x[k-1]$$ These generating functions are the z-transform. When we take the z-transform, we can lose some solutions. This is because a formal double sided power series doesn't exist, so we use a formal Laurent series (which can only have a finite number of non-zero $x[k],k<0$). Because we want to work with doubly infinite sequences, we must treat $\sum_{k=-\infty}^\infty x[k]z^{-k}$ as a genuine function. This means we define a region of convergence for z, wherein the sequence is absolutely summable. The sequence is absolutely summable is when: $$\sum_{k=-\infty}^\infty |x[k]z^{-k}|<\infty$$ This is dependent on $|z|$. The ROC is an annular region of the form $\{z\in\mathbb{C}|r_-<|z|<r_+\}$ or $|z|<r_+$. The initial solutions bind the possible solutions, as the z-transform finds stable solutions.

===== Z transform =====

The one sided Z transform can find all solutions in the future, so it is useful for real-world systems. The double sided transform works with our earlier study of LTI systems, looking at all values of k to find the frequency response. The Z transform fails to find the infinite number of solutions to the double sided case, it finds the ones we care about for finding the frequency response.

For a given system where we want to find all possible future outputs, the standard Z transform gives us one solution at most. The other solutions are found by solving the homogeneous problem, but the Z transformed solution gives the trivial solution $Y(z)=0$. Hence we need the one sided Z transform. Generating functions work for one sided problems, as problems arose when working with the double sided transform. This works for all future equations values but misses some of the current, which can be rectified by specifying initial conditions. The number of initial conditions is equal to the rank of the AR system (AR(1) needs 1, AR(3) needs 3).

For the double sided transform, there is no place to specify initial conditions. While this would mean we can find all solutions, we can only find all solutions to convergent power series. The transform can have zeros, where the solution is always zero, and poles, where the solution is undefined. The solution is found in the region of convergence by partial fraction expansion. We can expand the fractions as Taylor series in $z$ or $z^{-1}$ to get the solutions. The solutions result when the regions of convergence for each fraction overlap. The solution in $z$ is causal and the solution in $z^{-1}$ is anticausal. A representation of the series is unique for a ROC.

Please fill all the letters into the box to prove you're human. P V B H R Please keep this field empty:

Edit summary

Note: By editing this page you agree to license your content under the following license: CC Attribution-Noncommercial-Share Alike 4.0 International