Transformada de Walsh

De Viquipèdia
Dreceres ràpides: navegació, cerca

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 de 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ó[modifica | modifica el codi]

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

  • La transformada de Walsh és una funció, escrita sovint \widehat f del conjunt dels caràcters de G en el cos Fpn definida per:
\widehat f (\chi) \ = \frac 1g \sum_{s \in G} f(s)\chi^{-1}(s)

Anàlisi harmònica sobre un grup abelià finit[modifica | modifica el codi]

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:

\forall f,h \in \mathbb F_{p^n}^G <f|h>=\frac 1g \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[modifica | modifica el codi]

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

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

f(x)_j=\sum_{k=0}^{n-1}x_k(\omega^\xi)^{jk}\mod p\quad\quad j=0,\dots,n-1

Context[modifica | modifica el codi]

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

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
\omega^{(p-1-\xi)} = \omega^{-\xi}\,, la inversa de \omega^{\xi}\,, et n^{p-2} = n^{-1}\,, la inversa de n. (mòdul p)

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

z\left(\sum_{k=0}^{n-1}z^k\right)+1=\sum_{k=0}^nz^k
z\sum_{k=0}^{n-1}z^k=\sum_{k=0}^{n-1}z^k (restant z^n = 1\,)
z=1\, si \sum_{k=0}^{n-1}z^k\ne 0 (dividint els dos costats)

Si z=1 llavors es veu de forma trivial que \sum_{k=0}^{n-1}z^k=\sum_{k=0}^{n-1}1=n. Si z \ne 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ó.

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}\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}\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}\sum_{k=0}^{n-1}x_k\left\{\begin{matrix}n,&k=h\\0,&k\ne h\end{matrix}\right\}\mod p (puisque \omega^{\xi} = 1\,)
f^{-1}(f(x))_h=n^{p-2}x_hn\mod p
f^{-1}(f(x))_h=x_h\mod p

Vegeu també[modifica | modifica el codi]

Enllaços externs[modifica | modifica el codi]