MIT desenvolve algoritmo FFT 10 vezes mais rápido

Foto Ilustração

Ao ser calculado mais rapidamente, permite que as CPUs ocupem menos tempo, e possam passar 10X mais tempo em modos de stand by algo que nos dispositivos móveis como os smartphones corresponde a manutenção da autonomia.




A Transformada de Fourier permite decompor um sinal complexo nas suas componentes e amplitudes. Com esta função, podemos pegar, por exemplo, numa onda sonora e descobrir quais as suas frequências fundamentais, mas tem o inconveniente de ser uma função computacionalmente intensiva, razão pela qual se fala da "Fast" Fourier Transform (FFT) uma variação que permite o seu cálculo de forma muito mais rápido e possibilita que suas aplicações estendem-se pelas mais diversas áreas: Física, Teoria dos números, Análise combinatória, Processamento de sinal, Processamento de imagem, Teoria das probabilidades, Estatística, Criptografia, Acústica, etc.

Como a FFT, o novo algoritmo opera em sinais digitais. Um sinal digital é apenas uma série de números — discretas amostras de um sinal analógico, tais como o som de um instrumento musical. A FFT leva um sinal digital que contém um certo número de amostras e manifesta a ele como a soma ponderada de um número equivalente de frequências.

O que os professores Katabi e Piotr Indyk, do Laboratório de Inteligência Artifical e Ciência da Computação (CSAIL) do MIT, descobriram é que na verdade 57 dessas frequências podem ser completamente ignoradas sem perdas significativas de qualidade - o que aumenta em pelo menos 10 vezes a velocidade do novo algoritmo.

O seu desenvolvimento contou com a ajuda dos alunos Eric Price e Haitham Hassanieh e consiste de uma nova ideia em relação ao método atual: dividir e mensurar o sinal em camadas mais estreitas de banda, de modo que cada camada contenha apenas uma única frequência com ‘peso’ de marcação significativo e seja assim considerada, descartando-se as demais.

Conforme descrito no paper, esta nova abordagem pode proporcionar o desenvolvimento de aplicações em tecnologias de comunicação, como a 4G, mais eficientes, o paper encontra-se disponível em http://arxiv.org/abs/1201.2501v1 e apresentado no Association for Computing Machinery's Symposium on Discrete Algorithms - SODA.

Referência:
Massachusetts Institute of Technology. "Faster-than-fast Fourier transform." ScienceDaily, 18 Jan. 2012. Web. 23 Jan. 2012.