Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fourier expansion of boolean functions

  1. Mar 4, 2014 #1
    Any boolean function on n variables can be thought of as a function

    [tex]f : \mathbb{Z}_2^n \rightarrow \mathbb{Z}_2[/tex]

    which can be written as

    [tex]f(x) = \sum_{s \in \mathbb{Z}_2^n} \hat{f}(s) \prod_{i : x_i = 1} (-1)^{x_i}[/tex]


    [tex]\hat{f}(s) = \mathbb{E}_t \left[ f(t) \prod_{i : s_i = 1} (-1)^{t_i} \right][/tex]

    This is the Fourier expansion of a boolean function. But this uses the group [itex]\mathbb{Z}_2^n[/itex]. Why not use [itex]\mathbb{Z}_{2^n}[/itex]? Characters of the latter would be nice looking roots of unity on the complex circle, instead of points on an [itex]n[/itex]-cube.

    EDIT: You know what, nevermind. I don't even understand my own question anymore.
    Last edited: Mar 4, 2014
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you offer guidance or do you also need help?
Draft saved Draft deleted

Similar Threads - Fourier expansion boolean Date
I Fourier series of Dirac comb, complex VS real approaches Thursday at 3:38 PM
I [Signal and system] Function with fourier series a[k] = 1 Dec 13, 2017
I Frequency contributions Nov 26, 2017
Insights Further Sums Found Through Fourier Series - Comments Sep 28, 2017
Lissajous curves Oct 13, 2014