1

In doing some FFT's defined over prime number finite fields, I notice that the Parseval relations on conservation of sum of squares no longer seems to hold on each side of the FT. Curious about what it is in the usual Fourier Transformation with complex roots of unity, that makes the Parseval relations hold there, but does not happen with finite number field roots of unity?

dbm
  • 11
  • Just to make sure we are on the same page, can you give an example of what you mean? The usual Parseval identity depends on taking squared absolute values, i.e. multiplying complex numbers with their conjugates. What would be the finite field counterpart of either absolute value or *complex conjugate? It may be possible to cook up something... – Jyrki Lahtonen Aug 10 '16 at 11:43
  • I was comparing, after the way we do in physics, the sum of squared input values against the sum of squared output values, with arithmetic over the field. These two quantities are not equal to each other. – dbm Aug 11 '16 at 16:21
  • However, I found some papers describing that the Plancherel Theorem, of which the Parseval Theorem is a special sub-case, do indeed hold trivially. All you need to do is use the sum of x multiplied by y-bar. What is "bar" in a field with no complex values? Why it is the Characteristic of the group. What is the Characteristic? We aren't going to tell you. And we won't ever tell you what "bar" means. But as a hint, the Characteristic has the property that its negative is the same as its multiplicative inverse. – dbm Aug 11 '16 at 16:25
  • AHA! So that property is exactly the case for my 2^N roots of unity, used as the modulus of my FFT. And then looking at each row of the FFT operator array, I see that they are orthogonal to each other - hint: basis vectors, and upon substituting the multiplicative inverse for every element of any row, I remain orthogonal to other rows but can form a dot product against the original row and receive a constant value. Hence "bar" must be that replacing of row elements by the multiplicative inverses, and the Characteristic must be those basis vectors, i.e., row tuples. – dbm Aug 11 '16 at 16:28
  • As for absolute value... I have been able to visualize analogies to the physical real world by plotting field values normalized by "q", and where I take the min(x, q-x) as the absolute value measure. In other words, treat field numbers the same way we do with 2s complement arithmetic, treating low values as positive and high values as negative. Do that and the output of FFT's look very similar to those from the Complex domain over Reals. – dbm Aug 11 '16 at 16:34
  • So to summarize, you have to treat input and output values from the FFT differently in the finite field domain. On input side you form sum of squared input values. On output side you form sum of conjugate squared basis vectors. Conjugation as described above by replacing basis elements by their multiplicative inverses. Doing that makes the Plancherel Theorem trivially true (modulo normalizations). – dbm Aug 11 '16 at 16:43

0 Answers0