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.

Transformades de Fourier
Transformada de Fourier continua
Sèrie de Fourier
Transformada Discreta de Fourier
Transformada de Fourier en Temps Discret
Transformada de Fourier sobre cossos finits
Anàlisi de Fourier
Transformades relacionades

DefinicióModifica

Sia G un grup abelià finit d'ordre g i d'exponent una potència n-èsima 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   del conjunt dels caràcters de G en el cos Fpn definida per:
 

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

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:

 

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 finitModifica

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

 

La transformació teòrica de nombre opera sobre una successió de n nombres, mòdul un nombre primer p de la forma  , où   On   pot ser qualsevol nombre enter positiu.

El nombre   se substitueix per un nombre   on   èr una « arrel primitiva » de p, un nombre tal que el nombre enter positiu més petit   on   és  . Hi hauria d'haver una quantitat   que compleix aquesta condició. Els dos nombres   i   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

 

ContextModifica

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

 
 , la inversa de  , et  , la inversa de n. (mòdul p)

El contrari és verdader, ja que   és n per a z=1 i 0 per a tots els altres z on  . Una demostracio és

 
  (restant  )
  si   (dividint els dos costats)

Si z=1 llavors es veu de forma trivial que  . Si   llavors el costat dret ha de ser fals per evitar una contradicció.

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

 
 
 
  (puisque  )
 
 

Vegeu tambéModifica

Enllaços externsModifica