A Transformada Discreta do Seno em um Corpo Finito

A Transformada Discreta do Seno em um Corpo Finito R. M. Campello de Souza H. M. de Oliveira

M. M. Campello de Souza M. M. Vasconcelos

Depto de Eletrˆ onica e Sistemas, CTG, UFPE. 50670-901, Recife, PE E-mails: (ricardo,hmo,marciam)@ufpe.br, [email protected]

Resumo

tley de corpo finito (THCF), foi introduzida em [4]. Aplica¸c˜oes da THCF incluem o projeto de sisteUma nova transformada, a transformada discreta mas de multiplexa¸c˜ao digital, de sistemas de acesso do seno sobre um corpo finito (TDSCF) ´e introdu- m´ ultiplo e de seq¨ uˆencias multin´ıveis para espalhazida. O n´ ucleo da TDSCF ´e a fun¸c˜ ao trigonom´etrica mento espectral [5, 6]. Recentemente, a vers˜ao de seno definida sobre um corpo finito. A TDSCF corpo finito da TDC, foi introduzida [8]. Essas tem comprimentos que s˜ ao divisores de (p + 1)/2. transformadas s˜ao exemplos de transformadas diUm caso especial ´e a TDSCF de Mersenne, definida gitais. quando p ´e um primo de Mersenne. Essa classe de Neste trabalho, uma nova transformada digital, TDSCFs tem comprimentos que s˜ ao potˆencias de a transformada discreta do seno em um corpo fi2 e podem ser computadas por algoritmos FFT de nito (TDSCF), ´e introduzida. A partir de uma tribase 2. gonometria para corpos finitos introduzida recentemente [4], a fun¸c˜ao trigonom´etrica seno sobre um corpo finito ´e usada para construir a TDSCF. Na 1 Introdu¸ c˜ ao se¸c˜ao 2 alguns fundamentos matem´aticos s˜ao apresentados, que incluem a fun¸c˜ao seno e a constru¸c˜ao Transformadas discretas definidas sobre estruturas de n´ umeros complexos em um corpo finito. Uma finitas ou infinitas tem muitas aplica¸c˜ oes em Ennova propriedade dessas fun¸c˜oes ´e introduzida, a genharia. Dentre as v´ arias transformadas discretas qual leva `a defini¸c˜ao da TDSCF na se¸c˜ao 3. A definidas sobre os reais ou complexos, a transforexistˆencia da TDSCF inversa ´e demonstrada e almada discreta de Fourier (TDF) e as transformaguns exemplos s˜ao apresentados. A se¸c˜ao 4 cont´em das discretas do cosseno (TDC) e do seno (TDS) as conclus˜oes do trabalho. tem desempenhado um papel importante em Engenharia El´etrica. A TDC e a TDS tem recebido muita aten¸c˜ ao devido ao seu uso em sistemas de coFundamentos Matem´ aticos difica¸c˜ao por transformadas. Em particular, a DST 2 ´e o fundamento da t´ecnica de codifica¸c˜ ao de bloco umeros recursiva e tem sido usada na implementa¸c˜ao r´apida 2.1 O Corpo Finito dos N´ Complexos de transformadas ortogonais para codifica¸c˜ao [1, 2]. Embora discretizadas no dom´ınio da vari´avel indec˜ ao 1 GI(p) , {a + jb, a, b ∈ GF(p)}, p um pendente, estas transformadas tem coeficientes que Defini¸ primo ´ ımpar tal que j 2 ≡ −1 (mod p) n˜ ao ´e um pertencem a um estrutura infinita. Portanto, elas res´ ıduo quadr´ a tico em GF(p) (i.e., p ≡ 3 (mod 4)), podem ser vistas como um tipo de “transformada ´ e o conjunto dos inteiros gaussianos sobre GF(p). anal´ogica”. Por outro lado, transformadas definidas sobre estruturas finitas, al´em de discretizadas no dom´ınio da vari´ avel independente, tem seus coe- Da defini¸c˜ao acima, todo elemento de GI(p) pode ficientes definidos sobre um alfabeto finito e podem ser representado na forma a + jb e ´e denominado n´ umero complexo de corpo finito. ser vistas como “transformadas digitais”. A An´alise de Fourier pode ser aplicada para trac˜ ao 2 O conjunto unimodular de GI(p) ´e o tar sinais definidos sobre corpos finitos, por meio da Defini¸ conjunto de elementos ζ = (a + jb) ∈ GI(p), tais transformada de Fourier de corpo finito (TFCF), 2 2 que a + b ≡ 1 (mod p). Os elementos ζ s˜ ao deintroduzida por Pollard e aplicada para compunominados elementos unimodulares. tar convolu¸c˜ oes discretas usando aritm´etica modular [3]. Uma vers˜ ao de corpo finito da transformada discreta de Hartley, a transformada de Har- Esse conjunto ´e um grupo c´ıclico de ordem p + 1 [9].

2.2

Trigonometria em Corpos Fini- A seq¨uˆencia g tem comprimento 2N e os coeficientes de sua TFCF s˜ao [3]: tos

Esta se¸c˜ao introduz algumas fun¸c˜ oes trigonom´etricas sobre corpos finitos, as quais tem propriedades semelhantes ` aquelas das fun¸c˜oes trigonom´etricas definidas sobre os reais [10].

Gk =

2N −1 X

gi ζ ki =

N −1 X

i=0

fi ζ ki −

i=0

2N −1 X

f2N −1−i ζ ki ,

i=N

(1) 0 ≤ k ≤ 2N − 1, onde ζ ´e um elemento de ordem Defini¸ c˜ ao 3 Seja ζ um elemento n˜ ao nulo de 2N de GI(p). Observe que, devido `a anti-simetria GI(p), p ≡ 3 (mod 4). As fun¸c˜ oes kusada na defini¸c˜ao de g, o coeficiente Go ´e nulo. trigonom´etricas k-cos e k-sen de ∠(ζ i ) (o arco do Mudando, no segundo somat´orio, 2N − 1 − i por i, elemento ζ i ) sobre GI(p), s˜ ao 1 torna-se cosk (∠ζ i ) =

1 ki (ζ + ζ −ki ) 2

Gk =

N −1 X

fi ζ

i=0

e

1 senk (∠ζ ) = (ζ ki − ζ −ki ), j2 i

ki

−

N −1 X

fi ζ k(−1−i) ,

i=0

ou seja,

i, k = 0, 1, ..., N −1, onde ζ tem ordem N e N |(p2 − 1).

Gk =

N −1 X

fi [ζ ki − ζ (−k−ki) ].

i=0

Numa nota¸c˜ ao mais simples, considerando ζ fixo, as Evidenciando o termo ζ −k/2 , tem-se fun¸c˜oes k-trigonom´etricas s˜ ao denotadas por cosk (i) N −1 X e senk (i). A proposi¸c˜ ao 1, indicada a seguir, decorre G = fi ζ −k/2 [ζ k/2 ζ ki − ζ −k/2 ζ −ki ], k diretamente da defini¸c˜ ao 3. i=0

ou

Proposi¸ c˜ ao 1 A fun¸c˜ ao senk (i) satisfaz: i i) senN ( 2i+1 2 ) = (−1) .

Gk = ζ −k/2

2i+1 ii) senN −k ( 2i+1 2 ) = senk ( 2 ).

N −1 X

fi [ζ k(2i+1)/2 − ζ −k(2i+1)/2 ],

i=0

de modo que, da defini¸c˜ao 3, A TDS usual ´e constru´ıda por um processo que N −1 envolve a duplica¸c˜ ao da seq¨ uˆencia f [n] de compriX −k/2 G = ζ fi 2jsenk [(2i + 1)/2], (2) mento N , cuja TDS se quer definir, seguida pela k i=0 computa¸c˜ao da TDF dessa seq¨ uˆencia de comprimento 2N , o que requer que se use um n´ ucleo de 0 ≤ k ≤ 2N − 1. Os N coeficientes Sk da TDSCF ordem 2N [11]. s˜ao extra´ıdos da seq¨ uˆencia (Gk ) de comprimento 2N e s˜ao definidos por

3

A Transformada Discreta do Seno em um Corpo Finito

De forma an´ aloga ` a transformada discreta do seno definida sobre os reais, a constru¸c˜ ao da TDSCF S = (Sk ) de uma seq¨ uˆencia f = (fi ), i = 0, ....., N − 1 de elementos de GF(p), faz uso da seq¨ uˆencia auxiliar g = (gi ), i = 0, ...., 2N −1, de elementos gi ∈ GF(p), definidos por  fi , 0≤i≤N −1  gi , fi −f2N −1−i =  −f2N −1−i , N ≤ i ≤ 2N − 1

 Sk =

−jζ k/2 Gk , 1 ≤ k ≤ N, , 0, caso contr´ario

(3)

2fi senk [(2i + 1)/2], 1 ≤ k ≤ N.

(4)

isto ´e,

Sk =

N −1 X i=0

A express˜ao acima define a TDSCF direta da seq¨ uˆencia f . .

3.1

A TDSCF Inversa

Os coeficientes Sk da TDSCF s˜ ao obtidos a par- Para inverter a express˜ao 4 e obter a TDSCF intir da TFCF G = (Gk ) de g, conforme ilustrado a versa, faz-se uso do lema 1 a seguir. seguir e descrito nesta se¸c˜ ao: Lema 1 Os coeficientes Gk em 2 satisfazem N

(fi )

→

2N

T F CF

2N

(gi )

←→

(Gk )

N

→

(sk )

i) Gk = −ζ k G2N −k , 0 ≤ k ≤ 2N − 1.

ii) Gk = jζ −k/2 S2N −k , N ≤ k ≤ 2N − 1. N −1 2N −1 i X Prova: j hX −k(2i+1)/2 Sk ζ + Sk ζ −(2N −k)/2 ζ −(2N −k)i . i) Mudando k por 2N −k em 2 e usando a proposi¸c˜ao gi = 2N k=1 k=N 1 (ii) (note que como ζ tem ordem 2N , ent˜ao ζ N = −1), obtem-se: isto ´e,

G2N −k = −ζ k/2

N −1 X

fi 2jsenk [(2i + 1)/2].

gi =

i=0

N −1 i X j h −SN j(−1)i + Sk (ζ −k(2i+1)/2 −ζ k(2i+1)/2 ) . 2N k=1

Por´em de 2, isso ´e o mesmo que Da defini¸c˜ao 3, resulta G2N −k = −ζ −k Gk gi =

N −1  2i + 1 i X SN 1h (−1)i . + Sk senk N 2 2

e o resultado segue. k=1 ii) Fazendo 2N − k = r, o intervalo N ≤ k ≤ 2N − 1 torna-se 1 ≤ r ≤ N e assim vale a express˜ao 3, isto e portanto, da proposi¸c˜ao 1 (i), os coeficientes fi da ´e, TDSCF inversa de S s˜ao dados por Sr = −jζ r/2 Gr , fi =

de modo que

N −1  2i + 1  1 X , ρk Sk senk N 2

(5)

k=1

G2N −k = jζ −(2N −k)/2 S2N −k .

1 2, k = N . 1, k 6= N As express˜oes 4 e 5 definem o par transformado da TDSCF, denotado por



0 ≤ i ≤ N − 1, onde ρk = Usando o resultado (i) anterior, pode-se escrever −ζ k Gk = −jζ k/2 S2N −k ,

f = (fi ) ←→ S = (Sk ).

ou seja, Gk = jζ −k/2 S2N −k , e a prova est´ a completa.

Exemplo 1: Considerando p = 11, o elemento ζ = (3 + j5) ∈ GI(11) tem ordem p + 1 = 12 e ´e um elemento gerador do grupo unimodular de GI(7). Nessa estrutura, um par TDSCF de comprimento  (p + 1)/2 = 6 ´e

De posse do lema 1, ´e poss´ıvel expressar fi em fun¸c˜ao de Sk e obter a rela¸c˜ ao que corresponde `a TDSCF inversa. Da TFCF inversa de G, tem-se 2N −1 1 X Gk ζ −ki , gi = 2N k=0

0 ≤ i ≤ 2N − 1, sendo que  gi , 0 ≤ i ≤ 2N − 1 fi = . 0, caso contr´ ario

f = (1, 2, 3, 4, 5, 6) ←→ S = (j4, 1, j10, 2, j6, 6) As matrizes de transforma¸c˜ao direta e dadas por  j2 j3 j5 j5 j3  10 9 10 1 2   j3 j3 j8 j8 j3 Mk,i =   5 0 6 5 0   j5 j8 j2 j2 j8 9 2 9 2 9

inversa, s˜ao

j2 1 j3 6 j5 2



10 1 10 1 10 1



      

Expandindo o somat´ orio acima, pode-se escrever N −1 2N −1 i X 1 hX −ki gi = Gk ζ + Gk ζ −ki . 2N k=0

e

k=N

Usando 3 e o lema 1, e considerando que G0 = 0, tem-se gi =

N −1 2N −1 i X 1 h X −k/2 jζ Sk ζ −ki + jζ −k/2 S2N −k ζ −ki . 2N 3.2 k=1

k=N

 −1 Mk,i

   =   

j2 j3 j5 j5 j3 j2

10 9 10 1 2 1

j3 j3 j8 j8 j3 j3

5 0 6 5 0 6

j5 j8 j2 j2 j8 j5

      

As Matrizes de Transforma¸ c˜ ao

Mudando 2N − k por k no segundo somat´orio, leva As express˜oes 4 e 5, repetidas a seguir, definem o a par transformado da TDSCF (fi ) ←→ (Sk ):

fun¸c˜ao k-sen, um tal elemento ´e sempre real (∈ GF(p)) ou imagin´ario (da forma jb). Portanto, a 1 ≤ k ≤ N, complexidade computacional envolvida no c´alculo da transformada ´e essencialmente a mesma de uma P  N fi = N1 k=1 ρk Sk senk ( 2i+1 2 ), 0 ≤ i ≤ N − 1 transformada que assume valores apenas em GF(p). (6) Al´em disso, transformadas reais podem ser facil 1 2 , k = N . Devido ` onde ρk = a forma das ex- mente constru´ıdas, considerando-se a proposi¸c˜ao 2 1, k 6= N a seguir [12]. press˜oes em 6, as matrizes de transforma¸c˜ao direta e inversa, de elementos dados por mk,i = Proposi¸ c˜ ao 2 Se ζ = a+jb ´e um elemento unimoρk [2senk (2i+1)/2] e m−1 k,i = [ N senk (2i+1)/2], respec- dular, ent˜ ao a fun¸c˜ ao senk (i) assume apenas valores tivamente, apresentam uma rela¸c˜ ao simples e dada em GF(p), para quaisquer i, k. uma destas matrizes ´e poss´ıvel obter a outra diretamente por inspe¸c˜ ao. No exemplo, tem-se Portanto, se ζ ´e um elemento unimodular cuja ra´ız  quadrada λ tamb´em ´e unimodular, ent˜ao a matriz 6mk,i , k = N m−1 = . de transforma¸c˜ao so ter´a elementos pertencentes a k,i mk,i , k 6= N GF(p) e a TDSCF ´e real nesse caso. Entretanto, sendo λ um elemento gerador do grupo unimodu3.3 A TDSCF de Mersenne lar, sua ordem ´e (p + 1), de modo que ζ ter´a ordem Uma importante subclasse de transformadas deri- (p + 1)/2, o que implica em uma TDSCF de comvadas da TDSCF, ´e a das TDSCF de Mersenne, primento N = (p + 1)/4. Uma tal transformada ´e as quais s˜ao definidas sobre GF(p) quando p ´e um mostrada no exemplo 2 a seguir. primo de Mersenne, isto ´e, p = 2s − 1. Nesse caso, o comprimento N da transformada ´e um divisor de 2s−1 , o que a torna uma ferramenta atrativa Exemplo 2: Considerando p = 31, um primo uma vez que algoritmos r´ apidos de base 2 podem de Mersenne, o elemento ζ = (7 + j13) ∈ GI(31) ser usados na sua computa¸c˜ ao. A tabela 1 a se- tem ordem (p + 1)/2 = 16 e pode ser usado para guir apresenta valores de parˆ ametros envolvidos na definir uma TDSCF de Mersenne de comprimento constru¸c˜ao de algumas TDSCF. (p + 1)/4 = 8. Um par dessa transformada ´e  PN −1  Sk = i=0 2fi senk ( 2i+1 2 ),

f Tabela 1: Parˆ ametros da Transformada Discreta do (1, 2, 3, 4, 5, 6, 7, 8) Seno em alguns corpos finitos: p, comprimento N , elemento unimodular ζ usado na fun¸c˜ ao k-sen(.) e e suas matrizes de a sua ordem no campo de extens˜ ao GF(p2 ). por  GF(p) N ζ Ord(ζ) 9 11 7* 4 2+j2 8  26 17  11 6 3+j5 12  11 4  19 5 17+j4 10  23 23  M = k,i 23 12 4+j10 24  21 9  31* 8 7+j13 16  17 5  31* 16 2+j11 32  4 10 47 24 4+j19 48 29 2 71 36 8+j24 72 e 79 40 2+j32 80  103 52 2+j10 104 18 21 127* 64 2+j39 128  22 3  151 76 2+j65 152  11 3  167 84 4+j73 168  8 21 −1 Mk,i =  191 96 6+j27 192  8 10  199 100 2+j14 200  11 28   22 28 * TDSCF de Mersenne. 18 10

S (2, 28, 27, 2, 23, 10, 20, 8)

←→

transforma¸c˜ao reais s˜ao dadas

21 17 9 8 27 5 11 29

4 26 10 8 11 17 22 2

4 5 10 23 11 14 22 29

21 14 9 23 27 26 11 2

 11 9 14 5   4 11   8 8   9 21   26 14   10 4  29 2

22 8 18 20 20 18 8 22

15 15 16 16 15 15 16 16

11 18 23 22 22 23 18 11

3 10 10 3 28 21 21 28

 8 29 20 2   22 29   13 2  . 13 29   22 2   20 29  8 2

No exemplo 1, o vetor transformado tem componentes em GI(p). Entretanto, como os elemen- 4 Conclus˜ oes e Sugest˜ oes tos da matriz de transforma¸c˜ ao s˜ ao obtidos por potˆencias da ra´ız quadrada de um elemento uni- Nesse trabalho uma nova transformada foi introdumodular, devido ao fator (1/j2) na defini¸c˜ao da zida, a transformada discreta do seno sobre GF(p)

(a TDSCF), uma vers˜ ao de corpo finito da bem cocasting, pp. 291-303, Eds. P. Farrell, M. Darnhecida transformada discreta do seno definida sonell and B. Honary, Research Studies Press / bre o corpo dos n´ umeros reais. Inicialmente, foram John Wiley, 2000. apresentados alguns fundamentos matem´aticos que levam `a constru¸c˜ ao das fun¸c˜ oes k-trigonom´etricas [8] M. M. Campello de Souza, H. M. de Oliveira, R. M. Campello de Souza e M. M. Vasconcelos, sobre um corpo finito. Para derivar a TDSCF da A Transformada Discreta do Cosseno em um seq¨ uˆencia f de comprimento N , adotou-se, em um Corpo Finito, Anais do XX Simp´ osio Brasicorpo finito, o procedimento cl´ assico de relacionar leiro de Telecomunica¸ c o ˜ es, Rio de Janeiro, RJ, f com uma nova seq¨ uˆencia, g, de comprimento 2N . outubro 2003. A TDSCF S de f foi ent˜ ao obtida da transformada de Fourier de corpo finito G de g. Por meio das [9] D. Silva, R. M. Campello de Souza, H. M. de rela¸c˜oes estabelecidas entre G e S, estabeleceu-se Oliveira, L. B. E. Palma e M. M. Campello de a f´ormula de invers˜ ao da transformada. A TDSCF Souza, A Transformada Num´erica de Hartley e tem comprimentos divisores de (p + 1), onde Grupos de Inteiros Gaussianos, Revista da Sop ≡ 3 (mod 4), sendo poss´ıvel a constru¸c˜ao da ciedade Brasileira de Telecomunica¸c˜ oes, CamTDSCF de Mersenne, que apresenta comprimentos pinas, SP, v.17, No.1, pp. 48-57, junho 2002. cujos valores s˜ ao potˆencias de 2. A TDSCF introduzida nesse trabalho corres- [10] A. N. Kauffman, A Transformada de Hartley ponde a vers˜ ao anti-sim´etrica par. Sua vers˜ao biem um Corpo Finito e Aplica¸c˜oes, Disserta¸c˜ ao dimensional pode ser constru´ıda por um procedide Mestrado, Departamento de Eletrˆonica e mento semelhante ao introduzido nesse trabalho. Sistemas, UFPE, 1999. Considerando a existˆencia de defini¸c˜ oes alternativas para a TDS usual, vers˜ oes de corpo finito dessas [11] J. S. Lim, Two-Dimensional Signal and Image Processing, Prentice-Hall, 1990. alternativas e poss´ıveis aplica¸c˜ oes para a transformada discreta do seno de corpo finito est˜ao sendo [12] R. M. Campello de Souza, H. M. de Oliveira, investigadas. L.B Esp´ınola e M. M. Campello de Souza, Transformadas Num´ericas de Hartley, Anais do XVIII Simp´ osio Brasileiro de TelecomuReferˆ encias nica¸c˜ oes, pp. 357 - 366, Gramado, RS, setembro 2000. [1] A. K. Jain, Fundamentals of Digital Image Processing, Prentice-Hall, 1989. [2] H. S. Malvar, Signal Processing with Lapped Transforms, Artech, 1992. [3] J. M. Pollard, The Fast Fourier Transform in a Finite Field, Math. Comput., vol. 25, No. 114, pp. 365-374, Apr. 1971. [4] R. M. Campello de Souza, H. M. de Oliveira and A. N. Kauffman, Trigonometry in Finite Fields and a New Hartley Transform, Proceedings of the 1998 IEEE International Symposium on Information Theory, p. 293, Cambridge, MA, Aug. 1998. [5] H. M. de Oliveira, R. M. Campello de Souza and A. N. Kauffman, Efficient Multiplex for Band-Limited Channels, Proceedings of the Workshop on Coding and Cryptography - WCC ’99, pp. 235 - 241, Paris, Jan. 1999. [6] J. P. C. L. Miranda, H. M. de Oliveira, On Galois-Division Multiple Access Systems: Figures of Merit and Performance Evaluation,. Anais do 19o Simp´ osio Brasileiro de Telecomunica¸c˜ oes, Fortaleza CE, agosto 2001. [7] H. M. de Oliveira, R. M. Campello de Souza, Orthogonal Multilevel Spreading Sequence Design, in Coding, Communications and Broad-