0
$\begingroup$

Continuing the discussion from Convolution kernel in Bluestein's algorithm it has a very specific signature of the kernel

[conj(W), zeros(1, L-2*N+1), conj( W(N:-1:2) )];

for the fast-convolution.

There W is the chirp specific to Bluestein's algorithm

If not W would such a signature applicable for any general data?

I personally have one problem where the output length after the convolution must be same as the input vector length.

$\endgroup$

3 Answers 3

1
$\begingroup$

enter image description here

Perhaps I am over-complicating the things here. If I visualize the convolution it boils to very simple.

S = [1 2 3];
T = [2 0 0];

G = ifft( fft(S).*fft(T) )

and if I extand to $\ell=4$ samples then

L = 4

S = [1 2 3 1 2 3 1 2 3 1 2 3];
T = [2 0 0 2 0 0 2 0 0 2 0 0];

G = ifft( fft(S).*fft(T) ) / L

I may think this is the solution.

$\endgroup$
6
  • 1
    $\begingroup$ What if T has more than 1 non-zero value? Were you concerned with computing a linear convolution as this would just be circular as done, and therefore would repeat periodically as you show with the scale correction. I added to my answer to tie it back to Bluestein's in case that is helpful and importantly to note exactly what is needed there in terms of the linear convolution, and over what range of samples, and what portion of that linear convolution is needed. $\endgroup$ Apr 3, 2022 at 21:12
  • $\begingroup$ It would be interesting if T is vector with a more one non-zero values. But the current is described as above. $\endgroup$
    – jomegaA
    Apr 4, 2022 at 6:49
  • $\begingroup$ I see, you mean to say what you are currently trying to compute has just one non-zero value (so the result after zero padding the one value to match the first sequence also results in linear convolution since there are no non-zero values that overlap in this case) $\endgroup$ Apr 4, 2022 at 19:30
  • 1
    $\begingroup$ Note the key point from Bluestein’a algo vs convolution in general is that we require convolving with the negative index samples of the chirp which are non-zero, and for this a linear convolution is required and then we only need the N sample results of this associated with index at time or n=0. This is not necessarily the general case for the linear convolution between any two sequences. (and specific to Bluetein’s chip the negative index samples were equal to the positive index samples which also isn’t generally the case. $\endgroup$ Apr 4, 2022 at 19:34
  • 1
    $\begingroup$ Say there are m and n groups. Each group contains a vector of $3\times\ell$ samples since each sample is a 3d-vector. The transfer between groups m and n is a vector of $\ell$ samples. Initially I failed to this see as convolution problem. Once I realized, then I need a vector of $3\times\ell$ after the transfer and there started all the miss-directions and miss-understandings. $\endgroup$
    – jomegaA
    Apr 5, 2022 at 7:03
1
$\begingroup$

To answer the question: No it will not be the same in general form.

What is general form is for the second half of the vector to represent the time reversed samples for the function used so that the result is identical to linear convolution with no time offset or delay (so a non-causal operation that we do with post processing).

Such for any general time domain waveform with $N$ samples given by $[x[0], x[1], \ldots x[N-1]]$ where x[0] represents the sample at time in samples at $n=0$, for a “zero-phase” linear convolution we would perform the convolution with the $2N-1$ samples given by $[x[-N+1], x[-N+2], \ldots x[-1], x[0], x[1], \ldots x[N-1]$.

Notice how for the case of $W[n]= e^{2\pi n^2/N}$ specifically, the first half of the above is simply $W$ in reverse order, but generally this is not the case (when used in a transform where the resulting transform is real, we would use the time reversed complex conjugate, and when the result complex it can be completely independent and should be computed directly for the negative indexes).

Next an $N$ length output was used and for the Bluestein Algorithm specifically it is the last $N$ samples of the linear convolution, associated with $n=0$.

When this same convolution is done using FFT’s for the fast convolution technique the form given by the OP results and it will be the first $N$ samples of the result that would match the last $N$ samples of the linear convolution of computed directly. This is how the output samples match the input samples (a subset of the samples is selected) and how to set up the array in general form.

To answer the question as to how to do the convolution in general form with $N$ samples out for $N$ samples in, we must first clarify if a circular or linear convolution is desired. If circular convolution is desired, then the fast convolution will return $N$ samples for $N$ samples in (of each waveform). If a linear convolution is desired, this is done with zero padding as detailed in the referenced posts below, and here we note that the result of linear convolution of two waveforms will be $M+N-1$ samples long when one of the waveforms has $M$ samples and the other has $N$ samples. Therefore we need to specify which $N$ samples of the output we wish to have.

Further details relating to Bluestein's Algorithm


With that said we can see how this applies specifically to what motivated this question, further detailed here and here- notably the derivation of using FFT's with efficient power of 2 lengths to compute prime-length DFT's via Bluestein's Algorithm. The second link details specifically step by step how the Algorithm is computed, but note for here that a linear convolution of an $N$ sample sequence $y[n]$ with a chirp signal given as $h^{-1}[n] = W_N^{-n^2/2}[n]$, notably defined for $n$ with negative index values from -$N+1$ to $N-1$. The inverse is not important to this explanation, so I will further simplify by using $g[n]= h^{-1}[n]$. Further, for this chirp signal specifically (and not universally to any signal), $g[-n] = g[n]$. Given this, the graphic below represents the linear convolution specified, shown with arbitrary waveforms but notably to depict that $g[n]$ is defined for $n=-N+1\ldots N-1$ and zero elsewhere, and has symmetry about $n=0$ but $y[n]$ is defined for $n=0 \ldots N-1$:

depiction of linear convolution needed

The linear convolution result of the above would have a first non-zero value at $n=-N+1$ and would continue for a total $3N-2$ samples. However, it is only the $N$ samples starting at $n=0$ that are needed for Bluestein's Algorithm (see the referenced post detailing why). Thus if we were to do the linear convolution directly, it would be formed as follows using $g[n]$ as the $N$ samples from $n=0 \ldots N-1$ and equal to conj(W) used by the OP:

result = xcorr(y, [g(N:-1:2), g]);

The first sample of this result corresponds to $n=N+1$, we would would extract the $N$ sample sequence starting with the Nth sample:

result(N:2*N-1)

The above operations are in the derivation of Bluestein's Algorithm and notably showing how a DFT of a sequence can be computed by multiplying with a chirp, convolving that product with the inverse of the chirp (including the negative index values as explained here) and then multiplying the proper $N$ samples of that result with the chirp. Where the question and concern with "zero padding" comes up is in using the FFT for "fast convolution" and for that I reference the first post specifically, where in my answer, I detail how padding in the center of the sequence when doing a DFT or inverse DFT is necessary to achieve the same linear convolution result. Specifically the following would give us identical results to the $N$ samples needed as done above, out to any length FFT (and for this reason specifically, the algorithm is attractive as we can use power of 2 length FFT's which are very efficient).

result = ifft(fft([g, zeros(1, L-2*N+1), g(N:-1:2)]) * fft(y));
result(1:N)
$\endgroup$
9
  • $\begingroup$ A small typo in $e^{2\pi n^2/N}$ a brace instead of parenthesis. $\endgroup$
    – jomegaA
    Apr 3, 2022 at 16:53
  • $\begingroup$ This sentance...where x[0] represents the sample at time in samples at n=0, for a “zero-phase”...is not clear for me. $\endgroup$
    – jomegaA
    Apr 3, 2022 at 16:54
  • $\begingroup$ So to convolve $\hat{k}$ samples of $x$ to $\hat{k}$ sample of $t$, where each of $x[\hat{k}]$ is $\left( (\hat{k}_{1_x},\,\hat{k}_{1_y},\,\hat{k}_{1_z}),\dots\right)$ and each of $t[\hat{k}]$ is $\left(\hat{k}_{1},\,\hat{k}_{2},\dots\right)$. How can I setup the kernel so that my output $y[\hat{k}]=\left( (\hat{k}_{1_x},\,\hat{k}_{1_y},\,\hat{k}_{1_z}),\dots\right)$ $\endgroup$
    – jomegaA
    Apr 3, 2022 at 17:11
  • 1
    $\begingroup$ @jomegaA let me remove the zero phase reference: it makes sense for those familiar with “zero-phase” filters where you convolve with the forward filter coefficients and then again with the reverse filter for no delay (when post processing)— but distracting to explain that here. I will read you last comment when I am not on my phone (it isn’t rendering so hard for me to read) $\endgroup$ Apr 3, 2022 at 17:18
  • 1
    $\begingroup$ A good example that makes it clear for me at least is to consider a real signal in time is complex conjugate symmetric in frequency. Similarly a complex conjugate symmetric sequence in time (negative index samples are the complex conjugate of the positive index samples) will be real in frequency and thus every sample has a phase equal to zero (this is what I meant by zero phase). We cannot assume that will always be the case, it must be specified as such. $\endgroup$ Apr 3, 2022 at 17:30
0
$\begingroup$

"Convolution" ...

comes in two major 'flavors':

  1. impulse response: output of a (LTI) system in response to an input

    • always yields len(out) > len(in) (for len(h) > 1), namely, len(out) == len(in) + len(h) - 1.
    • "kernel at x[i]" means kernel starts at x[i] (see further in answer)
  2. correlation, i.e. cross-correlation / template matching: measuring similarity of input with the convolution kernel

    • flexible, but we usually do len(out) == len(in).
    • "kernel at x[i]" means kernel is centered at x[i]

I will explain padding for #2, but everything can be translated to 1 from the bullet points.

Padding

The basic idea is, "left shall not draw from right". That is, the convolution kernel, $h$, when at one edge of $x$, is not present at the other edge. Suppose

$$ x = [1, 2, 3], h = [5, -1, 6] $$

"$h$ is at $x[n_0]$" means $h$ is centered there ("kernel at").

No padding, $h$ at $x[0]$:

[1,  2,  3]
[-1, 6,  5]

Here, $h$'s left, which is $5$, draws from $x$'s right, which is $3$. Similar story when $h$ is at $x[-1]$. (Note, $h$'s left "wraps" around to right because FFT convolution is circular)

Sufficient zero padding, $h$ at $x[0]$:

[0,  1,  2,  3,  0]
[5, -1,  6,  0,  0]

Here, $h$'s left, which is $5$, is at $0$, which doesn't touch $x[-1]$, which is $3$.

Visualized:

Blue = $x$, green = $h$, red = boundaries of $x$ (i.e. unpadded region of $x$). $h$ can be anything here, I picked boxcar for clarity. What matters is, when it's at $x[0]$, its left is zero at $x[-1]$, and when it's at $x[-1]$, and vice versa.

Input size == output size just means we only keep results of convolution where $h$ is at $x$, rather than at padded $x$. There's no restriction on $x$ or $h$ (though the quality of our results can surely vary, e.g. if $h$ is much longer than $x$).

How to

This MATLAB guide demonstrates linear convolution, i.e. #1. It right-pads both the input and the kernel, meaning the kernel isn't centered, and we also unpad to len(out) > len(in). With a few tweaks as per bullets, we can convert this code to #2 - as in Bluestein's algorithm.

Finally, a caveat: any non-zero padding requires double the length of zero padding (because then "left" and "right" include the padded portions).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.