Uma nota sobre transformada de fourier sobre anéis
finitos e aplicações
Antonio Aparecido de Andrade
Depto de Matemática - Ibilce - Unesp - São José do Rio Preto - SP
Sejam Zq [x] o anel de polinômios na variável x sobre o anel local Zq , onde q é potência de
um número primo p, e f (x) um polinômio de grau h irredutı́vel sobre Zp e consequentemente
também é irredutı́vel sobre Z . Seja R = Zq [x] o anel quociente das classes de restos dos
q
<f (x)>
polinômios sobre Zq módulo o polinômio f (x). Temos que R é um anel comutativo com
elemento identidade e é chamado uma extensão de Galois de grau h de Zq . O grupo
multiplicativo R∗ , das unidades do anel R, possui um único subgrupo cı́clico de ordem
n = ph − 1 (McDonald, 1974), o qual denotaremos por Gn .
A transformada de Fourier discreta de um vetor v = (v0 , v1 , · · · , vn−1 ), cujos elementos são
Pn−1 −j2πik
k=
números complexos, é um vetor V = (V0 , V1 , · · · , Vn−1 ) dado por Vk = i=0
e n vi ,
−j2π
2
0, 1, · · · , n − 1, onde j = −1. O elemento e n é uma raiz complexa n-ésima da unidade.
Em um anel finito, um elemento α de ordem n é uma raiz n-ésima da unidade. Fazendo
−j2π
uma analogia entre e n e α temos a seguinte definição.
Definition 1 Seja v = (v0 , v1 , · · · , vn−1 ) um vetor sobre o anel Zq , onde n divide s,
e seja α um elemento de Gs de ordem n. O vetor V = (V0 , V1 , · · · , Vn−1 ), onde
P
ij
j = 0, 1, · · · , n − 1, é chamado de transformada de Fourier do vetor v.
Vj = n−1
i=0 α vi ,
O ı́ndice discreto i é definido como tempo e v como função domı́nio do tempo ou sinal.
Também definimos o ı́ndice discreto j como a frequência e V como a função domı́nio da
frequência ou espectro. Qualquer fator de n pode ser usado como o comprimento de uma
transformada de Fourier, mas os valores mais importantes são os de comprimento n, e neste
caso, α é um gerador do grupo Gn . Em constraste com os números complexos, não existe a
transformada de Fourier de qualquer comprimento porque não existem elementos de qualquer
ordem. Representando o vetor v através do polinômio v(x) = v0 + v1 x + · · · + vn−1 xn−1 ,
obtemos, pela aplicação da transformada de Fourier, o polinômio V(x) = V0 + V1 x + · · · +
Vn−1 xn−1 , chamado polinômio espectro ou polinômio associado de v(x).
Após darmos algumas propriedades da transformada de Fourier, passamos a um método de
decodificação de códigos BCH sobre anéis finitos envolvendo a transformada de Fourier. Para
isso, seja C um código BCH sobre Zq com capacidade de correção de até t erros, onde a distância
mı́nima é maior ou igual a 2t + 1. Seja c = (c0 , c1 , · · · , cn−1 ) uma palavra código transmitida
através do canal, e que o mesmo introduza o vetor erro e = (e0 , e1 , · · · , en−1 ). Deste modo, o
vetor recebido é dado por v = c + e, onde v = (v0 , v1 , · · · , vn−1 ), e suas componentes são dadas
por vk = ck + ek para k = 0, 1, · · · , n − 1. O processo consiste dos seguintes passos: 1) cálculo
da sı́ndromes; 2) cálculo do polinômio localizador de erros; 3) cálculo da função domı́nio de
freqüência V = C + E; e 4) calculo da transformada inversa de Fourier de C.
1