I'm currently dealing on the so called “Walsh Function” (WF) that is written like: $$f^W(a)=\sum_{x\in{F^n_2}}(-1)^{f(x)+(a,x)}$$ What I know is that this function is used to approximate an arbitrary function like $f: F^n_2 \to F_2$ and that the $a$ in the upper function is the so called Walsh Coefficient.

But whats in detail about the WF? What can I do with it exactly? How do the elements in the set of the WF look like? As far as I know is this set called the Walsh Spectrum!? How can an arbitrary function be approximated by the WF?

And what exactly is the the Walsh Transformation (WT). I know there is a method to conduct the WT, the so called Fast-Fourier-Transformation. Why do I do a WT?

  • 1
    $\begingroup$ There is some stuff on this over on dsp.SE (search for Hadamard also, not just for Walsh) that might get you some of the information that you seek. $\endgroup$ May 5 '15 at 19:57

The function $L_a(x)=\langle a,x\rangle=a_1 x_1+\cdots+a_n x_n$ is a linear multivariate function of $(x_1,\ldots,x_n)$.

The function $$f(x)+\langle a,x\rangle=f(x_1,\ldots,x_n)+a_1 x_1+\cdots+a_n x_n$$ equals $0$ mod 2 if $f(x)=\langle a,x\rangle$ and $1$ mod 2 otherwise.

The sum $$ \hat{f}(a)=\sum_{(x_1,\ldots,x_n) \in \mathbb{F}_2^n} (-1)^{f(x)+\langle a,x\rangle}, $$ is equal to $2^n-2 d_H(f,L_a)$ and computes the correlation between the function $f$ and the linear function $L_a$. Here $d_H(f,L_a)$ is the Hamming distance between those two functions as $x$ varies over $\mathbb{F}_2^n.$ Each one of these $2^n$ correlations (for different $a$) can be obtained by a matrix multiplication.

Since the mapping is invertible, a $2^n\times 2^n$ Hadamard matrix appears as below: $$\left[(-1)^{\langle a,x \rangle}\right]$$ where $a$ indexes rows and $x$ indexes the columns in the standard order.

Due to the kronecker structure of the Hadamard matrix, a fast transform and inverse transform exist. The functions that have the maximum hadamard coefficient $\hat{f}(a)$ minimized are called bent functions and are important in coding theory and cryptography. By Parseval's relation, $$\sum_{a \in \mathbb{F}_2^n} |\hat{f}(a)|^2 =2^{2n},$$ and bent functions have $|\hat{f}(a)|=2^{n/2}.$ Note $f(0)=0$ means a function is balanced, bent functions are not.

  • $\begingroup$ Thank you very much, that gives me some insight. One more question: As far as I understand for every $\langle a,x\rangle$ exists the Walsh Coefficient $\hat{f}(a)$ where are some of the WC are maximum. I know that those WC can be found for each $a$ by the Fast-Fourier-Transformation. Can you tell how this method basically works? $\endgroup$
    – Ovomaltine
    May 6 '15 at 5:40
  • $\begingroup$ See the example in block diagram in Wikipedia at en.wikipedia.org/wiki/Fast_Walsh%E2%80%93Hadamard_transform $\endgroup$
    – kodlu
    May 6 '15 at 6:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.