Consider these two signals:
a = [1 1 0 0 0 0 0 0]
b = [1 0 1 0 0 0 0 0]
their convolution is
c = a * b = [1 1 1 1 0 0 0 0]
I am trying to obtain b
by using complex division to divide the discrete Fourier transform of c
by the discrete Fourier transform of a
. I am aware that in general, there may not be a solution when attempting deconvolution in this way, due to division by zero issues etc. -- however, I want to understand why this doesn't work in this specific case.
The discrete Fourier transforms of all three signals are:
F(a) = [
2 (0)
1.707 - 0.707 i
1 - i
0.293 - 0.707 i
0 (N/2)
0.293 + 0.707 i
1 + i
1.707 + 0.707 i
]
F(b) = [
2 (0)
1 - i
0
1 + i
2 (N/2)
1 - i
0
1 + i
]
F(c) = [
4 (0)
1 - 2.414 i
0
1 - 0.414 i
0 (N/2)
1 + 0.414 i
0
1 + 2.414 i
]
The zero-th entry (marked (0)
) is the sum of the number of 1 values in the signal, equal to $\Sigma_{i = 0}^7k_i$ for each kernel $k \, \epsilon \{a, b, c\}$; the value of the $N/2$-th entry (marked (N/2)
) is equal to $\Sigma_{i = 0}^7k_i(-1)^i$.
The problem arises when F(c)
is divided by F(a)
at the $N/2$-th entry: this is 0/0
, which is undefined, or is sometimes defined as evaluating to 1. However, the correct result for the complete division $F^{-1}(F(c) / F(b)) = F(a)$ can only be obtained if this instance of 0/0
in the $N/2$-th position evaluates to the value 2, not 1, since the $N/2$-th entry of F(b)
is 2. Other than this value at the $N/2$-th position, all entries of F(b)
can be recovered correctly by simply dividing entries in F(c)
by the corresponding entry in F(a)
, using complex division.
Why is the N/2
-th entry of the Fourier transform problematic in this way? Is there a robust way to derive what the correct result should be for the division of Fourier transforms at the N/2
-th position? Or is this simply due to the fact that the value 2 is lost due to multiplication by 0 in the pointwise multiplication $F(a) . F(b)$?
Does this problem affect other components of the Fourier transform? Or is it only possible for this to happen at the N/2
th position, which will be real-valued and may be zero?
Are there other gotchas to dividing signals in the Fourier domain in this way, or does this only happen in cases where there are zeroes in the Fourier domain of one of the factors?