Hi guys these questions are from my homework. I am not asking you to solve my homework. Instead, i just need some help in getting started. Please list down some steps as I am very lost. Also, if you have any books/materials to let me read about Fourier transform respective to coding theory please let me know. Thanks.
1) Show $x^d$ has a five valued spectrum on $F(2^n)$ when $d=(2^{2s}+1)/(2^s+1)$
$n$ is odd, $\gcd(s,n)=1$
2) Find the weights in the code generated by $$ \left(\begin{array}{ccc} \cdots& x&\cdots\\ \cdots&x^{2^s+1}&\cdots\\ \cdots&x^{2^{2s}+1}&\cdots\end{array}\right). $$
Thank you very much!
A sketch for part 1. Let $F$ be the field of $2^n$ elements. We have $|F^*|=2^n-1$. You assumptions imply that $\gcd(n,2s)=1$ and a standard argument then shows that also $\gcd(2^n-1,2^{2s}-1)=2^{\gcd(n,2s)}-1=1$. Hence also $\gcd(2^s+1,2^n-1)=1$. Therefore $2^s+1$ has an inverse $b$ modulo $2^n-1$. This is a relief, because otherwise raising an element of $F$ to power $d=(2^{2s}+1)/(2^s+1)$ does not make sense, because $2^s+1$ is not a factor of $2^{2s}+1$. Now there is a well-defined function $f:F\to F$ given by $$ f(x)=x^d=x^{b(2^{2s}+1)}. $$ We are to calculate its Walsh-Hadamard transform, i.e. we need to say something about the possible values of the character sums $$ S(a)=\sum_{x\in F}e(f(x)+ax), $$ where $a\in F$ is a constant, and $e:F\to \{\pm1\}$ is the additive character $e(x)=(-1)^{tr(x)}$. Here $tr:F\to GF(2)$ is the trace to the prime field. The character property means that $e(x+y)=e(x)e(y)$ for all $x,y\in F$.
Because $\gcd(2^s+1,2^n-1)=1$, the mapping $y\mapsto y^{2^s+1}$ is a permutation of $F$. Therefore we can make the substitution $x=y^{2^s+1}$. The sums can thus be rewritten to read $$ S(a)=\sum_{y\in F}e(y^{2^{2s}+1}+a y^{2^s+1}). $$ Then we do a standard trick and start manipulating $S(a)^2$: $$ S(a)^2=\sum_{y\in F}\sum_{x\in F} e(y^{2^{2s}+1}+ay^{2^s+1}+x^{2^{2s}+1}+ax^{2^s+1})\\ $$ Let us first substitute $y=z+x$. As the pair $(x,z)$ ranges over $F^2$ so does $(x,y)$. Furthermore $$ y^{2^s+1}=(x+z)^{2^s+1}=(x+z)(x+z)^{2^s}=(x+z)(x^{2^s}+z^{2^s}) $$ by applying standard properties of the Frobenius automorphism, and similarly $$ y^{2^{2s}+1}=(x+z)(x^{2^{2s}}+z^{2^{2s}}). $$ Substituting these turns the sum into $$ \begin{aligned} S(a)^2&=\sum_{z\in F}\sum_{x\in F} e((z+x)^{2^{2s}+1}+a(z+x)^{2^s+1}+x^{2^{2s}+1}+ax^{2^s+1})\\ &=\sum_{z\in F}\sum_{x\in F}e\left(z^{2^{2s}+1}+az^{2^s+1} +\left[x^{2^{2s}}z+xz^{2^{2s}}+a(x^{2^s}z+xz^{2^s})\right]\right)\\ &=\sum_{z\in F}e(z^{2^{2s}+1}+az^{2^s+1})\sum_{x\in F} e\left(\left[x^{2^{2s}}z+xz^{2^{2s}}+a(x^{2^s}z+xz^{2^s})\right]\right). \end{aligned} $$ Next we look at the inner sum. We observe that in all the terms $x$ is raised to a power of two. By applying the rule $e(x)=e(x^{2^j})$, which is valid for all natural numbers $j$, we can turn the inner sum, denote it by $I(a)$ to $$ I(a)=\sum_{x\in F}e\left(x^{2^{2s}}[z+z^{2^{4s}}+a^{2^s}z^{2^s}+a^{2^{2s}}z^{2^{3s}}]\right). $$ Here the factor in square brackets does not depend on the inner summation variable, so we can treat it as a constant. There the inner sum is equal to zero unless that bracketed quantity $$ L_a(z)=z+z^{2^{4s}}+a^{2^s}z^{2^s}+a^{2^{2s}}z^{2^{3s}} $$ is zero, in which case the inner sum is equal to $2^n$. We need a handle on how often this will happen.
Let $K$ be an algebraic closure of $F$, and let $E$ be the (unique) subfield of $K$ of cardinality $2^s$. Let us view $L_a$ as a mapping from $K$ to $K$. Because only power of $2^s$ occur as exponents of $z$, we see that $L_a$ is an $E$-linear mapping. Therefore its kernel (in $K$) is a 4-dimensional subspace over $E$, because all of its zeros are simple, so the number of zeros in $K$ is clearly $2^{4s}$. Because $E$ and $F$ are linearly disjoint, the kernel intersects $F$ at a subspace of dimension $\le 4$ over the prime field.
At this point we know that the number of $z\in F$ such that $L_a(z)=0$ is either $1,2,4,8$ or $16$. To narrow this further down we need to observe that the same calculations shows that $\ker L_a\cap F$ is the radical of symmetric (and symplectic) bilinear form $$ B(x,y)=tr(y^{2^{2s}+1}+ay^{2^s+1}+x^{2^{2s}+1}+ax^{2^s+1}).$$ Because $\dim F=n$ is odd, we know from the theory of symplectic forms that the dimension of the kernel is also odd. Therefore the cardinality $N(a):=|\ker L_a\cap F|$ is either 2 or 8 according to whether the radical has dimension 1 or 3.
Repeating the earlier calculation shows that $S(a)^2$ is either zero or equal to $N(a)|F|$. This, at long last, shows that the Walsh-Hadamard transform is at most 5-valued.