Sign up ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
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. – Dilip Sarwate May 5 at 19:57

1 Answer 1

up vote 2 down vote accepted

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.

share|improve this answer
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? – Ovomaltine May 6 at 5:40
See the example in block diagram in Wikipedia at – kodlu May 6 at 6:30

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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