Register to reply 
Fourier expansion of boolean functions 
Share this thread: 
#1
Mar414, 09:05 PM

P: 993

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] where [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. 


Register to reply 
Related Discussions  
When to use fourier integral instead of fourier series expansion  Classical Physics  2  
Boolean functions  General Math  13  
Logic circuits for boolean functions  Engineering, Comp Sci, & Technology Homework  7  
One wayness of boolean functions  General Math  4  
Boolean Functions  General Math  8 