Notation:
$\mathcal F\left\{a\right\}$ denotes applying the discrete forward Fourier transform to the histogram $a$. Similarly for $\mathcal F^{-1}\left\{a\right\}$ and the discrete inverse Fourier transform.
Capitals represent the discrete fast Fourier transform of the lower-case counterpart, e.g. $A = \mathcal F\left\{a\right\}$.
The convolution of two histograms $f$ and $g$ is denoted $f\star g$.
Say I have histograms $a$ and $b$ with $a=[1,2,3]$ and $b=[4,5,6]$ (the heights) and the edges given by $e=[0,1,2,3]$. I.e. For the histogram $a$, there is one entry in the interval $[0,1)$, two entries in the interval $[1,2)$, and three entries in the interval $[2,3]$.
In order to perform a linear convolution as opposed to circular, $a$ must be padded such that len($a$) = len($a$) $+$ len($b$) $-1$. Similarly for $b$.
The convolution theorem states: $$\mathcal F\left\{a\star b\right\} = \mathcal F\left\{a\right\} \cdot \mathcal F\left\{b\right\}$$
So if $c = a\star b$ and $d = \mathcal F^{-1}\left\{A\cdot B\right\}$, then $c = d$.
On performing the Fourier convolution of the $a$ and $b$ mentioned above, I obtain a result if $d = [4,13,28,27,18]$.
My questions:
- Where does $c$ sit in terms of bins?
- Do I need to expand the bin edges, $e$, in some way?
- In which direction should I expand them?
- Should the extra bins have the same width as the originals (in this case, $1$)?
Intuition tells me that there should be an extra bin on either side of $e$, of the same width.
Furthermore, if I was to crop $c$ such that it has the same length as the unpadded kernel or the signal, where would I make the cut? Is this even possible?
