12

There is probably a bit of a misconception here. In many application the signal is runnning all the time or is VERY long: modem, audio stream, video etc. In this case you can't really define the "length" of the signal. The relevant metric is here "number of operations per input sample" not the "total number of operations". If ...


10

Is there any trade-off in numerical precision or speed? Yes. For delays that are integer multiples of the sampling period method 1 is far superior: it's computationally efficient, it's bit-exact, it's easy to implement and it's almost fool proof. Method 2 is computationally expensive, you need to pick an FFT length (which is not trivial) it's subject to ...


6

Your problem comes about because you're pondering the convolution of a signal by itself: $$g(x) = f(x) * f(x)$$ So, yes, if you had a block diagram where you collect f(x) from the æther and then somehow magically convolve it by itself (which can't be done physically because it would require time-reversing $f(x)$, which requires looking into the future), then ...


5

Yes, that's correct. The impulse response of a cascade of two systems is the convolution of the individual Impulses responses. Convolution is commutative, so it doesn't matter in which order you convolve. Impulse responses are ONLY defined for linear time invariant systems, so this will work for systems like equalizers or filters but NOT for things like ...


5

The OP says that sequences $x = [x(0), …, x(N_x-1)]$ and $h = [h(0), …, h(N_h-1)]$ (are) of different finite lengths $N_x$ and $N_h$ respectively He does not claim that $x$ and $h$ are finite-length segments of possibly longer (maybe even infinitely longer) sequences, and so the standard assumption is that finite length means what it says. In particular, $...


4

Apart from the formulae, let us go back to their actual meaning, and how they are derived. Talking about convolution: this operation is inherent to Linear-Time-Invariant (LTI) systems. In other words: if you want to analyse a system that is linear, and time-invariant, or you want to apply a processing or a filter that does not vary in time or space then ...


4

For two non-zero sequences $x_n$ and $h_n$ given that their convolution is zero, At least one of them must be infinite length.


4

Because the impulse response completely characterizes an LTI system. The reason is an arbitrary input $x(t)$ can be written as an infinite sum of time shifted and scaled Delta functions: $$x(t) = \int_{-\infty}^{+\infty}x(\tau)\delta(t-\tau)d\tau$$ or alternatively, using the convolution operator, $$x(t) = x(t)*\delta(t)$$ Properties of linearity and time ...


4

I did it for the DCT-I and DCT-II. At first I thought it is about circular convolution, but it is not. After desperate attempts to do it by myself I found this article: https://dr.ntu.edu.sg/bitstream/10356/94137/1/Convolution%20Using%20Discrete%20Sine%20and%20Cosine%20Transforms.pdf. In this paper there is a derivation of circular convolution using DTT's, ...


4

The answer is simple, the Sobel Filter is a composition of Lows Pass Filter (LPF) and High Pass Filter (HPF). The composition is done by convolution. Now, indeed the LPF presented above $ {\left[ 1, 2, 1 \right]}^{T} $ has amplification in the DC value (Its sum is 4 so the amplification is 4). Yet it is convolved with an HPF filter which rejects the DC ...


4

That's an application of Parseval's (Plancherel's) Theorem: $$\int_{-\infty}^{\infty}f(t)g^*(t)dt=\frac{1}{2\pi}\int_{-\infty}^{\infty}F(\omega)G^*(\omega)d\omega\tag{1}$$ where $F(\omega)$ and $G(\omega)$ are the Fourier transforms of $f(t)$ and $g(t)$, respectively. I've used $^*$ to denote complex conjugation.


4

I think you need to refine your definitions. The computational complexity for an $n$-element convolution on $m$ points of data is $\mathcal{O}(n\cdot m)$. Your $\mathcal{O}(n)$ only applies for each output sample. The computational complexity for an $n$-element FFT is, indeed $\mathcal{O}(n \log n)$. But it coughs up $n$ points. The savings in using the ...


4

You may solve it by 3 steps: Show yourself that a Cyclic Convolution with a vector $ \boldsymbol{e}_{i}^{N} $ is a Cyclic Shift Operator $ {T}_{i - 1} \left( \cdot \right) $. Where $ \boldsymbol{e}_{i}^{N} $ is defined as a vector of length $ N $ which all its elements is zero but the $ i $- th element which is 1. Decompose $ \phi $ into $ 3 $ vectors of ...


4

Convolution of an input signal with a fixed impulse response is a linear operation. However, if the input-output relation of a system is $$y(t)=(x*x)(t)\tag{1}$$ then the system is non-linear, which is straightforward to show. Similarly, any convolution with a kernel that depends on the input signal is a non-linear operation. On the other hand, a system with ...


4

At the risk of blowing my own trumpet and that of my co-author, Bob Williamson, there is also this paper which shows the equivalence of three techniques referred to in the FIR link in Ben's answer and also referred to in the paper linked to from Hilmar's answer. The two results that are of particular interest are Proposition's 2 and 3 of the paper, ...


3

Let's assume you have 2 signals: vX and vY. So: clear(); numSamplesX = length(vX); numSamplesY = length(vY); numSamplesConv = numSamplesX + numSamplesY - 1; vTimeDomainConv = conv(vX, vY); vFrequencyDomainConv = ifft(fft(vX, numSamplesConv) .* fft(vY, numSamplesConv), 'symmetric'); max(abs(vTimeDomainConv - vFrequencyDomainConv)) %<! Should be < ...


3

and how to avoid it? Address the NaN in your input data. Don't "fix", "paper over it" or "replace by 0". Find the root cause for the NaN, understand what's happening and take meaningful corrective action. NaN means your input data is bad. Doing anything with bad data is pointless since your output will be bad. Doing cosmetic adjustment just so the code ...


3

Convolving with Matched Filter is same as cross-correlation. Suppose say your known signal is $x[n]$ for $0 \le n \le N-1$. The matched filter is $$ h[n] = x^*[N-n] $$ where $*$ denotes conjugate (considering a generic complex signal). You can drop the conjugate for real signals. The convolution with matched filtering operation is $$ y[p] = \sum x[l]h[p-...


3

Let $x$ and $y$ be signals of $N$ samples each, numbered as $x(0),\ldots,x(N-1)$. Then their DFTs are $X$ and $Y$, which also have $N$ entries each: \begin{eqnarray} X(k) &=& \sum_{n=0}^{N-1}x(n)e^{-2\pi i kn/N},\\ Y(k) &=& \sum_{m=0}^{N-1}y(m)e^{-2\pi i k m/N}, \end{eqnarray} where the indices run from $0$ to $N-1$. The $k^{\textrm{th}}$ ...


3

I have no access to your audio files so I've downloaded: IR from here (mono/r1_omni.wav) - it's a really long one Anechoic recording from here (operatic-voice/mono/singing.wav) Resampled voice signals: Final convolved signal: As for your questions: 1. As you did the plot of IR in logarithmic scale it's clearly visible that towards its end there is ...


3

Let's follow the math from incubation to delivery. It begins with psi, a rescaled morlet2 (as shown previously) at a scale $a=64$, and $\sigma=5$: $$ \psi = \psi_{\sigma}(t/a) = e^{j\sigma (t/a)} e^{-(t/a)^2/2} \tag{2} $$ gets integrated and L1-normalized: -- (see caveat2 below) $$ \psi = \psi_{\text{int}}(t) = \frac{1}{a} \int \psi_{\sigma}(t/a)\ dt \tag{3} ...


3

Just do it the hard way by writing out the individual formulas for the general convolution sum \begin{align} y[n] &= \sum_{k=-\infty}^\infty a[k]b[n-k]\\ &= \sum_{k=0}^\infty a[k]b[n-k] &\scriptstyle{\text{because }a[k]=0~\text{whenever } k < 0,}\\ &= \sum_{k=0}^n a[k]b[n-k] &\scriptstyle{\text{because }b[n-k]=0~\text{whenever } k > ...


3

It's quite straightforward to give an exact formulation for the convolution of two finite-length sequences, such that the indices never exceed the allowed index range for both sequences. If $N_x$ and $N_h$ are the lengths of the two sequences $x[n]$ and $h[n]$, respectively, and both sequences start at index $0$, the index $k$ in the convolution sum $$(x\...


3

As Hilmar pointed out, for delays that are integer multiples of the sampling period, method 1 is far superior. Also, Method 1 is more suitable for real-time operations as you don't need to buffer the data to perform the FFT. For delays that are non-integer multiples of the sampling period you can adapt method 1 by using an FIR or IIR filter using Lagrange ...


2

It is a little late, but i'm also working on convolution reverb at the moment. If it is still of interest, you can use my code. Simply call the function convolution_reverb and pass the paths to the two audio files (audio and impulse response, both need to be .wav files), as well as the name for the result file to be created. import numpy as np from wave ...


2

http://r0k.us/graphics/kodak/ does link to Kodak PhotoCD contents with 2048x3072 images. It is not what is called "raw" as those are using 4:2:0 subsampling (so not lossless at all) and xvYCC transfer function (almost like BT.709 gamma). Those were indeed produced by scanning KODACOLOR Gold 100 (35 mm) film and some other types of 35 mm, all types ...


2

I found an implementation of STFT based on conv1d in pytorch here: https://github.com/huyanxin/phasen/blob/master/model/conv_stft.py edit: Actually, the phasen repository took the STFT code from https://github.com/pseeth/torch-stft edit2: Asteroid has an alternative implementation of STFT and iSTFT: https://github.com/mpariente/asteroid/


2

I compared 3 implementations for Linear Convolution of 1D signals: Direct - Using MATLAB's conv() funciton. Overlap and Save - Implemented in MATLAB with tuned loop to prevent allocation and optimal choice of the DFT window. Frequency Domain - Using MATLAB' fft() and proper padding to implement Linear Convolution using Circular Convolution. For various ...


2

After playing with the notebook for a while, I figured out the following: The result from scipy is shifted by one pixel in each axis (probably due to its definition of the "same" mode). Or, alternatively, both the analytic result and pyfftw results are shifted the opposite way. After working around that, the result is exactly (within error) the same as the ...


Only top voted, non community-wiki answers of a minimum length are eligible