En matemàtiques , i més precisament en anàlisi harmònica la transformada de Walsh és l'equivalent de la Transformada discreta de Fourier quan es treballa sobre un cos finit d'aritmètica modular en comptes de sobre nombres complexos .
Es fa servir en teoria de la informació tant en codis lineals com en criptografia .
Sia G un grup abelià finit d'ordre g i d'exponent una potència n -èsima d'un nombre primer p , F pn el cos finit de cardinal p n , χ un caràcter amb valors en F pn i f una funció de G en F pn .
La transformada de Walsh és una funció, escrita sovint
f
^
{\displaystyle {\widehat {f}}}
G en el cos F pn definida per:
f
^
(
χ
)
=
1
g
∑
s
∈
G
f
(
s
)
χ
−
1
(
s
)
{\displaystyle {\widehat {f}}(\chi )\ ={\frac {1}{g}}\sum _{s\in G}f(s)\chi ^{-1}(s)}
[ modifica ] El context és idèntic al de l'anàlisi harmònic clàssic d'un grup abelià finit. La forma bilineal associada a l'àlgebra del grup és la següent:
∀
f
,
h
∈
F
p
n
G
<
f
|
h
>=
1
g
∑
s
∈
G
f
(
s
)
−
1
.
h
(
s
)
{\displaystyle \forall f,h\in \mathbb {F} _{p^{n}}^{G}<f|h>={\frac {1}{g}}\sum _{s\in G}f(s)^{-1}.\,h(s)\;}
Aquí s'aplica el conjunt dels resultats de la teoria de l'anàlisi harmònic, així es disposa de la igualtat de Parseval , del teorema de Plancherel , d'un producte de convolució , de la dualitat de Pontryagin o fins i tot de la fórmula de sumatori de Poisson .
[ modifica ] Hi ha un cas particular, aquell en què el grup G és el grup additiu d'un espai vectorial finit. En aquest cas particular G és un cos.
La transformada discreta de Fourier ve donada per
f
j
=
∑
k
=
0
n
−
1
x
k
(
e
−
2
π
i
n
)
j
k
j
=
0
,
…
,
n
−
1
{\displaystyle f_{j}=\sum _{k=0}^{n-1}x_{k}\left(e^{-{\frac {2\pi i}{n}}}\right)^{jk}\quad \quad j=0,\dots ,n-1}
La transformació teòrica de nombre opera sobre una successió de n nombres, mòdul un nombre primer p de la forma
p
=
ξ
n
+
1
{\displaystyle p=\xi n+1\,}
ξ
{\displaystyle \xi \,}
ξ
{\displaystyle \xi \,}
El nombre
e
−
2
π
i
n
{\displaystyle e^{-{\frac {2\pi i}{n}}}\,}
ω
ξ
{\displaystyle \omega ^{\xi }\,}
ω
{\displaystyle \omega \,}
arrel primitiva » de p , un nombre tal que el nombre enter positiu més petit
α
{\displaystyle \alpha \,}
ω
α
=
1
{\displaystyle \omega ^{\alpha }=1\,}
α
=
p
−
1
{\displaystyle \alpha =p-1\,}
ω
{\displaystyle \omega \,}
e
−
2
π
i
n
{\displaystyle e^{-{\frac {2\pi i}{n}}}\,}
ω
ξ
{\displaystyle \omega ^{\xi }\,}
n són iguals a 1 (mòdul p), totes les potències potències inferiors diferents de 1.
La transformació teòrica de nombre ve donada per
f
(
x
)
j
=
∑
k
=
0
n
−
1
x
k
(
ω
ξ
)
j
k
mod
p
j
=
0
,
…
,
n
−
1
{\displaystyle f(x)_{j}=\sum _{k=0}^{n-1}x_{k}(\omega ^{\xi })^{jk}\mod p\quad \quad j=0,\dots ,n-1}
La transformació teòrica inversa de nombre ve donada per
f
−
1
(
x
)
h
=
n
p
−
2
∑
j
=
0
n
−
1
x
j
(
ω
p
−
1
−
ξ
)
h
j
mod
p
h
=
0
,
…
,
n
−
1
{\displaystyle f^{-1}(x)_{h}=n^{p-2}\sum _{j=0}^{n-1}x_{j}(\omega ^{p-1-\xi })^{hj}\mod p\quad \quad h=0,\dots ,n-1}
ω
(
p
−
1
−
ξ
)
=
ω
−
ξ
{\displaystyle \omega ^{(p-1-\xi )}=\omega ^{-\xi }\,}
ω
ξ
{\displaystyle \omega ^{\xi }\,}
n
p
−
2
=
n
−
1
{\displaystyle n^{p-2}=n^{-1}\,}
n . (mòdul p)El contrari és verdader, ja que
∑
k
=
0
n
−
1
z
k
{\displaystyle \sum _{k=0}^{n-1}z^{k}}
n per a z=1 i 0 per a tots els altres z on
z
n
=
1
{\displaystyle z^{n}=1\,}
z
(
∑
k
=
0
n
−
1
z
k
)
+
1
=
∑
k
=
0
n
z
k
{\displaystyle z\left(\sum _{k=0}^{n-1}z^{k}\right)+1=\sum _{k=0}^{n}z^{k}}
z
∑
k
=
0
n
−
1
z
k
=
∑
k
=
0
n
−
1
z
k
{\displaystyle z\sum _{k=0}^{n-1}z^{k}=\sum _{k=0}^{n-1}z^{k}}
z
n
=
1
{\displaystyle z^{n}=1\,}
z
=
1
{\displaystyle z=1\,}
∑
k
=
0
n
−
1
z
k
≠
0
{\displaystyle \sum _{k=0}^{n-1}z^{k}\neq 0}
Si z =1 llavors es veu de forma trivial que
∑
k
=
0
n
−
1
z
k
=
∑
k
=
0
n
−
1
1
=
n
{\displaystyle \sum _{k=0}^{n-1}z^{k}=\sum _{k=0}^{n-1}1=n}
z
≠
1
{\displaystyle z\neq 1\,}
Per completar la demostració, es pren la transformada inversa de a transformació.
f
−
1
(
f
(
x
)
)
h
=
n
p
−
2
∑
j
=
0
n
−
1
(
∑
k
=
0
n
−
1
x
k
(
ω
ξ
)
j
k
)
(
ω
p
−
1
−
ξ
)
h
j
mod
p
{\displaystyle f^{-1}(f(x))_{h}=n^{p-2}\sum _{j=0}^{n-1}\left(\sum _{k=0}^{n-1}x_{k}\left(\omega ^{\xi }\right)^{jk}\right)(\omega ^{p-1-\xi })^{hj}\mod p}
f
−
1
(
f
(
x
)
)
h
=
n
p
−
2
∑
j
=
0
n
−
1
∑
k
=
0
n
−
1
x
k
(
ω
ξ
)
j
k
−
h
j
mod
p
{\displaystyle f^{-1}(f(x))_{h}=n^{p-2}\sum _{j=0}^{n-1}\sum _{k=0}^{n-1}x_{k}(\omega ^{\xi })^{jk-hj}\mod p}
f
−
1
(
f
(
x
)
)
h
=
n
p
−
2
∑
k
=
0
n
−
1
x
k
∑
j
=
0
n
−
1
(
ω
ξ
(
k
−
h
)
)
j
mod
p
{\displaystyle f^{-1}(f(x))_{h}=n^{p-2}\sum _{k=0}^{n-1}x_{k}\sum _{j=0}^{n-1}(\omega ^{\xi (k-h)})^{j}\mod p}
f
−
1
(
f
(
x
)
)
h
=
n
p
−
2
∑
k
=
0
n
−
1
x
k
{
n
,
k
=
h
0
,
k
≠
h
}
mod
p
{\displaystyle f^{-1}(f(x))_{h}=n^{p-2}\sum _{k=0}^{n-1}x_{k}\left\{{\begin{matrix}n,&k=h\\0,&k\neq h\end{matrix}}\right\}\mod p}
ω
ξ
=
1
{\displaystyle \omega ^{\xi }=1\,}
f
−
1
(
f
(
x
)
)
h
=
n
p
−
2
x
h
n
mod
p
{\displaystyle f^{-1}(f(x))_{h}=n^{p-2}x_{h}n\mod p}
f
−
1
(
f
(
x
)
)
h
=
x
h
mod
p
{\displaystyle f^{-1}(f(x))_{h}=x_{h}\mod p}
