Na matemática, a transformada discreta de Fourier sobre um anel generaliza a transformada discreta de Fourier (TDF), de uma função cujos valores são números complexos, para uma cujos valores se dão sobre um anel arbitrário.

Definição Seja um anel, um inteiro e uma raiz principal n -ésima da unidade, definida por: Martin Fürer, "Faster Integer Multiplication", STOC 2007 Proceedings, pp. 57–66. Section 2: The Discrete Fourier Transform.

A Transformada Discreta de Fourier é uma operação que mapeia uma n-tupla (énupla) de elementos de para outra n -tupla de elementos de com respeito a seguinte fórmula:

Por convenção, a n-tupla é dita estar no domínio do tempo onde o índice é chamado de tempo . Já a n-tupla é dita estar no domínio da frequência onde o índice é chamado de frequência . Outra nomenclatura usual para é espectro de . Essa terminologia tem como origem as aplicações das transformadas de Fourier no processamento de sinais .

Se é um domínio integral (que inclui Corpos ), basta escolher como uma raiz primitiva n- ésima da unidade, para satisfazer a condição ( ). Em outras palavras, é suficiente que: Martin Fürer, "Faster Integer Multiplication", STOC 2007 Proceedings, pp. 57–66. Section 2: The Discrete Fourier Transform.

para

Outra simples hipótese se aplica no caso em que n é da forma . Neste caso, ( ) pode ser substituído por .

Inverso O inverso da transformada discreta de Fourier é dada por:

onde é o inverso multiplicativo de em (realçamos que se esse inverso não existir, a TDF não pode ser invertida).

Formulação matricial Como a transformada discreta de Fourier é um operador linear sob uma n-tupla (um vetor no ), ela pode ser descrita pela multiplicação de matrizes . Nessa notação matricial, a transformada é expressa da seguinte forma:

De forma similar, a matriz para a transformada inversa de Fourier é

Formulação polinomial Identificando uma -tupla com um polinômio da forma

Obtemos que a transformada ( ) é da forma:

Ou seja, isso significa que é o valor do polinômio para , em outras palavras,

Portanto, a transformada de Fourier pode ser vista pela valuação de polinômios cujos coeficientes estão no domínio do tempo e os valores estão no domínio da frequência. Aqui é importante que o polinômio seja avaliado nas raízes -ésimas da unidade, que são exatamente as potências de .

De modo análogo, a definição da transformada inversa de Fourier ( ) pode ser escrita usando:

Em síntese, resumimos isso do seguinte jeito: Os valores de em são os coeficientes de . Enquanto os valores de em são os coeficientes de , a menos de um fator escalar e reordenação.R. Lidl and G. Pilz. Applied Abstract Algebra, 2nd edition. Wiley, 1999, pp. 217–219.

Casos especiais

Números complexos Se é o corpo dos números complexos, então as -ésimas raízes primitivas da unidade podem ser serão nossos . Neste caso, produz-se a fórmula usual para a transformada discreta complexa de Fourier :

Sobre os números complexos, frequentemente normaliza-se as fórmulas para a TDF e a TDF inversa usando o fator escalar em ambas as fórmulas, em vez de na fórmula para o TDF e na fórmula para a TDF inversa. Essa normalização, é feita para tornar a matriz TDF unitária. Observe que não se realiza essa normalização no caso geral, pois não faz sentido em um anel arbitrário.

Corpos finitos Se é um corpo finito, onde é uma potência de um número primo, então a existência de uma raiz primitiva implica automaticamente que divide . Isso segue do Teorema de Lagrange que tem como corolário que ordem multiplicativa de cada elemento deve dividir o tamanho do grupo multiplicativo , que é . Isto, em particular, garante que é invertível, de modo que a notação em ( ) faz sentido.

Uma aplicação da transformada discreta de Fourier sobre é a simplificação dos códigos Reed-Solomon aos códigos BCH dentro da teoria da codificação . Tal transformação pode ser realizada mais eficientemente utilizando certos algoritmos rápidos, por exemplo, a transformada rápida ciclotômica de Fourier .

Formulação polinomial sem raiz n-ésima Suponha que . Primeiro consideremos o caso em que .

Já que buscamosque não haja raíz -ésima raiz da unidade em , então . Assim, vendo a transformada de Fourier como um isomorfismo para alguns polinômios , de acordo com o teorema de Maschke . O mapa é dado pelo teorema do resto chinês, e o inverso pela aplicação da identidade de Bézout para polinômios.

Além disso, , é um produto de polinômios ciclotômicos. Onde, a fatoração de em equivale a fatorar o ideal primo em , onde é uma -ésima raiz primitiva da unidade. Obtendo assim, polinômios de grau onde e é a ordem de .

Novamente, podemos estender um corpo finito base para com o objetivo de encontrarmos uma raiz primitiva, ou seja, queremos construir um corpo de divisão para . Nessa extensão, obtemos , para um elemento tal que dado um polinômio , para cada .

No caso de , podemos definir novamente um -isomorfismo linear como anteriormente, da seguinte forma: Observamos que onde e . Então, aplicamos a fatoração efetuada no caso anterior a , e obtendo a decomposição . Porém, os módulos que aparecem agora são indecomponíveis em vez de irredutíveis.

Transformada de Teoria dos Números A transformada de Teoria dos Números (TTN) é obtida pela especialização da transformada discreta de Fourier para , os inteiros módulo um primo . Este é um corpo finito, e raízes primitivas -ésimas da unidade existem sempre que divide , então temos para um inteiro positivo . Especificamente, deixe ser uma -ésima raiz primitiva da unidade, então uma -ésima raiz primitiva da unidade pode ser encontrado calculando .

e.g. para , temos , uma -ésima raíz primitiva da unidade

quando , temos e a forma matricial fica

A TTN pode ter significado no anel , mesmo quando o módulo não é primo, desde que exista uma raiz principal de ordem . Alguns casos especiais da TTN, ocorrem para certos , como a Transformada de Números de Fermat ( ), usada pelo algoritmo de Schönhage–Strassen, ou a Transformada de Números de Mersenne ( ) que usa um módulo composto.

Em geral, se , então pode-se encontrar uma -ésima raíz da unidade mod encontrando uma ráiz primitiva mod , que depende de satisfazer . Então se para cada , onde é a função totiente de Euler, somos capaz de produzir uma tupla , tal que, a pré-imagem de , dada pelo teorema do resto chinês, é uma -ésima raiz da unidade de modo que . Garantindo que a condição de soma para raízes principais ( ) seja satisfeita.

Ver também

Transformada de Fourier Transformada discreta de Fourier (complexa) Transformada de Fourier de tempo discreto Convolução

Referências

Categoria:Análise de Fourier