Hi guys can anyone tell me how to apply Fourier transform in the context of coding theory? ie. how to find the weights of the code, show that the function has a five valued spectrum/transform etc. It will be good if you will be able to show me some notes on how to do it and an explanation of how.

It is so difficult to find any notes of Fourier transform and how it relates to weight analysis. I am really desperate and i really need help in understanding this topic!! Thank you very much in advance guys!

  • $\begingroup$ This is a relatively broad subject. Have you studied the Handbook of Coding Theory? Your university library should have a copy. IIRC the chapters on "Number theory and codes" and "Sequences" have a lot of related material, and introduce many of the basic tricks. All assuming that you are relatively conversant with finite fields. If not, take a look at Lidl & Niederreiter. At least for the theory of symmetric/symplectic bilinear forms over fields of characteristic two. $\endgroup$ Apr 14 '13 at 19:27

This is a broad subject, but I describe some basic ideas.

Let $V$ be an $m$-dimensional vector space over the binary field $\mathbb{F}_2$. We often but not always identify $V$ with the extension field $\mathbb{F}_{q},q=2^m$.

Consider any function $f$ from $V$ to $\mathbb{F_2}$. By fixing an ordering of elements of $V$, say $V=\{x_1,x_2,\ldots,x_q\}$, we can identify $f$ with the vector $c_f=(f(x_1),f(x_2),\ldots,f(x_q))\in\mathbb{F}_2^q$. In other words, if we let $f$ range over a linear space of functions, the vectors $c_f$ will range over the words of a binary linear code of length $q$.

How do we compute weights of those codewords? To that end we use (looks somewhat silly at this point, but bear with me) the function $e:x\mapsto (-1)^x$ from $\mathbb{F}_2$ to real numbers. Here $e(0)=1$ and $e(1)=-1$, so if the weight of the word $c_f$ is $w$, we get that the exponential sum $$ S(f):=\sum_{x\in V}e(f(x))=\sum_{x\in V}(-1)^{f(x)}=q-2w. $$ In other words, if we know the sum $S(f)$ we can calculate $w$ and vice versa.

The Walsh-Hadamard transforms enter the scene because many interesting codes contain the set $$L(V)=\{c_\lambda\in\mathbb{F}_2^q\mid \lambda:V\to\mathbb{F_2}\ \text{linear}\}$$ as a subspace. If you add to the set $L(V)$ their bitwise complements, i.e. extend the set of linear functions to the set of affine functions, you get the so called first order Reed-Muller code, which you have surely heard about. Given any function $f:V\to\mathbb{F}_2$, the Walsh-Hadamard transform calculates all the sums of the form $$ S(f+\lambda):=\sum_{x\in V}(-1)^{f(x)+\lambda(x)}, $$ where $\lambda$ ranges over all the linear functions from $V$ to $\mathbb{F}_2$. This means that the Walsh-Hadamard transform gives us the weights of all the codewords in the coset $c_f+L(V)$.

In typical applications of this idea the functions $f$ are restricted to be of the form $f(x)=tr(a x^d)$, where $a$ can be an arbitrary element of $\mathbb{F_q}$, and the exponent $d$ is fixed. Here we definitely identified $V$ with $\mathbb{F}_q$ for otherwise the exponentiation $x^d$ does not make sense.

When $d$ is the sum of two powers of two, the trace transforms $f$ to a symmetric bilinear form on $V$. And that is how the theory of symmetric bilinear forms on vector spaces over $\mathbb{F}_2$ enters the picture.


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.