Transformada de Walsh

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.

Definició

Sia G un grup abelià finit d'ordre g i d'exponent una potència n-èsima d'un nombre primer p, F_pⁿ el cos finit de cardinal p ⁿ, χ un caràcter amb valors en F_pⁿ i f una funció de G en F_pⁿ.

• La transformada de Walsh és una funció, escrita sovint ${\displaystyle {\widehat {f}}}$ del conjunt dels caràcters de G en el cos F_pⁿ definida per:

${\displaystyle {\widehat {f}}(\chi )\ ={\frac {1}{g}}\sum _{s\in G}f(s)\chi ^{-1}(s)}$

Anàlisi harmònica sobre un grup abelià finit

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:

${\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.

Cas d'un espai vectorial finit

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

${\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 ${\displaystyle p=\xi n+1\,}$, où ${\displaystyle \xi \,}$ On ${\displaystyle \xi \,}$ pot ser qualsevol nombre enter positiu.

El nombre ${\displaystyle e^{-{\frac {2\pi i}{n}}}\,}$ se substitueix per un nombre ${\displaystyle \omega ^{\xi }\,}$ on ${\displaystyle \omega \,}$ èr una « arrel primitiva » de p, un nombre tal que el nombre enter positiu més petit ${\displaystyle \alpha \,}$ on ${\displaystyle \omega ^{\alpha }=1\,}$ és ${\displaystyle \alpha =p-1\,}$. Hi hauria d'haver una quantitat ${\displaystyle \omega \,}$ que compleix aquesta condició. Els dos nombres ${\displaystyle e^{-{\frac {2\pi i}{n}}}\,}$ i ${\displaystyle \omega ^{\xi }\,}$ elevat a la potència 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

${\displaystyle f(x)_{j}=\sum _{k=0}^{n-1}x_{k}(\omega ^{\xi })^{jk}\mod p\quad \quad j=0,\dots ,n-1}$

Context

La transformació teòrica inversa de nombre ve donada per

${\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}$

${\displaystyle \omega ^{(p-1-\xi )}=\omega ^{-\xi }\,}$, la inversa de ${\displaystyle \omega ^{\xi }\,}$, et ${\displaystyle n^{p-2}=n^{-1}\,}$, la inversa de n. (mòdul p)

El contrari és verdader, ja que ${\displaystyle \sum _{k=0}^{n-1}z^{k}}$ és n per a z=1 i 0 per a tots els altres z on ${\displaystyle z^{n}=1\,}$. Una demostracio és

${\displaystyle z\left(\sum _{k=0}^{n-1}z^{k}\right)+1=\sum _{k=0}^{n}z^{k}}$

${\displaystyle z\sum _{k=0}^{n-1}z^{k}=\sum _{k=0}^{n-1}z^{k}}$ (restant ${\displaystyle z^{n}=1\,}$)

${\displaystyle z=1\,}$ si ${\displaystyle \sum _{k=0}^{n-1}z^{k}\neq 0}$ (dividint els dos costats)

Si z=1 llavors es veu de forma trivial que ${\displaystyle \sum _{k=0}^{n-1}z^{k}=\sum _{k=0}^{n-1}1=n}$. Si ${\displaystyle z\neq 1\,}$ llavors el costat dret ha de ser fals per evitar una contradicció.

Per completar la demostració, es pren la transformada inversa de a transformació.

${\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}$

${\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}$

${\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}$

${\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}$ (puisque ${\displaystyle \omega ^{\xi }=1\,}$)

${\displaystyle f^{-1}(f(x))_{h}=n^{p-2}x_{h}n\mod p}$

${\displaystyle f^{-1}(f(x))_{h}=x_{h}\mod p}$

Vegeu també

• convolució
• algorisme de multiplicació

Enllaços externs

• S'explica el mateix que aquí) (anglès)