ΕΠΕΞΕΡΓΑΣΙΑ ΣΗΜΑΤΩΝ (ECE-Y523)

The Fast Fourier Transform is used everywhere but it has a fascinating origin story that could have ended the nuclear arms race.

Discrete convolutions, from probability, to image processing and FFTs.

Εκτός των άλλων και μια εξαιρετική παρουσίαση της συνέλιξης απ' ευθείας ή μέσω του DFT και του FFT.

In this video, we take a look at one of the most beautiful algorithms ever created: the Fast Fourier Transform (FFT). This is a tricky algorithm to understand so we take a look at it in a context that we are all familiar with: polynomial multiplication. You will see how the core ideas of the FFT can be "discovered" through asking the right questions. The key insights that are presented in this video is that polynomial multiplication can be improved significantly by multiplying polynomials in a special value representation. The challenge that presents itself is the problem of converting a polynomial from a standard coefficient representation to value representation. We see that the FFT is an incredibly efficient recursive algorithm that performs this task, and we also discover that a slightly tweaked FFT (Inverse FFT) can also solve the reverse problem of interpolation. If this video doesn't blow your mind, I don't know what will.

0:00 Introduction

2:19 Polynomial Multiplication

3:36 Polynomial Representation

6:06 Value Representation Advantages

7:07 Polynomial Multiplication Flowchart

8:04 Polynomial Evaluation

13:49 Which Evaluation Points?

16:30 Why Nth Roots of Unity?

18:28 FFT Implementation

22:47 Interpolation and Inverse FFT

26:49 Recap

By Artem Kirsanov

Wavelet transform is an invaluable tool in signal processing, which has applications in a variety of fields - from hydrodynamics to neuroscience. This revolutionary method allows us to uncover structures, which are present in the signal but are hidden behind the noise. The key feature of wavelet transform is that it performs function decomposition in both time and frequency domains.

OUTLINE: 00:00 Introduction 01:55 Time and frequency domains 03:27 Fourier Transform 05:08 Limitations of Fourier 08:45 Wavelets - localized functions 10:34 Mathematical requirements for wavelets 12:17 Real Morlet wavelet 13:02 Wavelet transform overview 14:08 Mother wavelet modifications 15:46 Computing local similarity 18:08 Dot product of functions? 21:07 Convolution 24:55 Complex numbers 27:56 Wavelet scalogram 30:46 Uncertainty & Heisenberg boxes 33:16 Recap and conclusion