基于Android系统的傅立叶变换

开篇：润墨网以专业的文秘视角，为您筛选了一篇基于Android系统的傅立叶变换范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：傅立叶变换在通信、光学、天文方面都有着极其广泛的应用。基于PC平台的研究已经相当成熟，具有较多的工具和库可以使用（如，MATLAB和FFTW开源库）。但是在嵌入式系统上却很难找到相关的库和分析工具，在android系统上更是如此。然而音频分析和游戏开发等领域傅立叶变换有着不可或缺的作用，所以在嵌入式系统上实现快速高效的傅立叶变换有着实际的应用意义。

关键词：傅立叶变换；Android；音频分析

中图分类号：TP301 文献标识码：A文章编号：1007-9599 (2011) 09-0000-03

Fourier Transform Based on Android System

Gu Qiwei

(School of Computer Engineering and Science Shanghai University,Shanghai200072,China)

Abstract:Fourier transform in the communications,optics,astronomy have a very wide range of applications.PC-based research is already quite mature,with more tools and libraries can be used(eg,MATLAB and open source library FFTW).But in the embedded system is difficult to find the relevant libraries and analysis tools,especially in the Android system.However,audio analysis and Fourier transform the field of game development has an indispensable role,so in the embedded systems to achieve fast and efficient application Fourier transform has a real meaning.

Keywords:Fourier transform;Android;Audio analysis

傅立叶变换在科学计算中有着极其重要的意义，因为Android系统开放的SDK是基于JAVA语言实现的，如果想通过SDK实现其算法在性能上由于JAVA语言自身的特性很难达到较高的效率。如何解决在Android系统上实现高性能的傅立叶变换是本文要着手解决的问题。

一、离散傅立叶分析

随着计算机技术的发展与完善。科学研究和工程计算中的很多问题跟计算机已经密不可分了。计算机的一个典型特征是离散化，而傅立叶变换的本质是一个积分计算，体现为连续化特征[2]。同时在实际应用中信号都是离散化采样得到的（例如来自CD的信号），为了能够有效利用计算机实现傅立叶变换的需求，需要对傅立叶级数实现高效、高精度的离散化，为此提出了离散化傅立叶变换（DFT）的概念。由1.3式可得傅立叶变换的离散形式：

……（2.1）

令 可得2.1式的矩阵形式：

……（2.2）

其中， ， ，

根据2.2式，程序不难实现，下面给出代码：

DFT（input）

for k

for j

wjk=cos（2*PI/n*k*j）+sin（2*PI/n*k*j）i；

Output+=input[j]*wjk

将2.1式分为奇、偶两部分则可得到下式：

，其中

令， ， ，，将其代入上式可得：

……（2.3）

上式用矩阵的形式可写成 ， 和 分别表示偶数序列和奇数序列的傅立叶变换。根据以下性质：

（1） 和 是以N为周期的序列。

（2） 。

可将2.3式表示成：

……（2.4）

由2.2式可知，离散傅立叶变换需要与矩阵 相乘，所以2.2式的时间复杂度为 。而2.4式中 和 的时间复杂度均为 ，所以2.4式的时间复杂度为 。由此可见2.4式的算法要比2.2式计算次数少了一半。如果对 和 做同样的分解，便可将计算量继续减半。如此迭代便得到了快速傅立叶算法[3]，最终的时间复杂度为 。

下面以序列 为例推导整个快速傅立叶变换过程。

首先根据2.4式将2.2式的傅立叶变换序列分成奇、偶两部分。

再经过若干次分解，便可得到最终形式：

……（2.5）

从最终的结果来看地，其中大部分复数运算都被 替代，这无疑大大降低了计算的复杂度。下面给出算法实现：

FFT（input，output）

1.If length[input]=1

2.output=input

3.For i

4.even=input[2*i]

5.odd=input[2*i+1]

6.FFT（even，evenout）

7.FFT（even，oddout）

8.for j

9.wjk=cos（2*PI/n*k*j）+sin（2*PI/n*k*j）i；

10.output=evenout[j]+wjk*oddout[j]

11.output=evenout[j]-wjk*oddout[j]

上面1-2行是迭代退出条件，3-5行将输入数据分成奇、偶两组，6-7行分别对分了组的数据迭代计算，8-11行是利用2.4式对数据进行处理。

二、基于Android系统程序实现

基于Android系统的程序编写，现有两种方法：一种是基于上层SDK（Software Development Kit）框架的JAVA语言开发，另一种是基于底层NDK（Native Development Kit）环境的C/C++开发。一般来说开发程序的UI和简单的逻辑用SDK来开发具有简单快捷的优点，但是那些对速度和内存要求较高的算法实现通过NDK来实现可以得到较高性能。这主要是从JAVA和C/C++语言的特点来考虑的，一般来说JAVA的运行效率要比C/C++低2-10倍[4]，特别是具有大量浮点运算的程序。如何同时得到JAVA语言的便捷和C/C++的高效，JNI（Java Native Interface）是关键。通过JNI，JAVA程序可以调用C/C++实现的接口方法。

实现JNI调用需要完成以下几个步骤[5]：

1. 定义JAVA接口方法。

2. 通过JAVA自带的工具"javah"生成C/C++头文件。

3. 实现C/C++文件方法，并编译成动态库。

4. JAVA程序加载生成的动态库。

5. 定义接口对象，调用其定义的方法。

其中需要指出的是JAVA与C/C++之间参数的传递。虽然现在关于JNI方面的文献已经很多，但是大多数都缺乏对数组类型参数传进、传出的介绍，而这在实际应用中是非常重要的，例如在我们的程序中由于JAVA缺少复数类型的定义，我们需要自己定义复数类型并将它以数组的形式传递给C/C++程序，程序不仅要实现数组类型参数的传递，还要实现自定义类型数组参数的传递。

为了获得传进来的自定义数组对象的内容我们需要以下几个步骤：

1. 通过Find Class和Get Field ID得到数组对象的类型定义和对象中字段的类型定义。

2. 通过Get Object Array Element得到数组元素对象。

3. 通过Get XXX Field得到最终元素的数据，XXX为JNI定义的内置类型如Double，Float等。

创建返回自定义数组对象的内容我们也需要以下几个步骤：

1.通过Find Class和Get Field ID得到数组对象的类型定义和对象中字段的类型定义。

2.通过Get Method ID查找到默认构造函数。

3.通过New Object方法和上面找到的默认构造函数生成数组的默认值。

4.用New Object Array创建数组。

5.再用New Object和Set XXX Field创建数组元素对象，并设定值。

6.最后通过Set Object Array Element将元素赋给返回数组。

如果是PC环境下这样调用就已经足够了，得是在实际开发中我们会发现当传递的数组过大时程序会异常的缓慢甚至崩溃。原因是当我们调用Get Object Array Element或New Object方法时C/C++将会为程序分配内存空间，如果是在PC环境下，JAVA虚拟机的垃圾回收机制会在适当的时候释放这些分配的内存，但在嵌入式系统中内存资源一般都很有限，JAVA虚拟机来不及回收内存，程序就已经耗尽内存。所以我们需要调用Delete Local Ref方法，手动删除我们分配的内存。

三、实验结果

MATLAB是矩阵实验室（Matrix Laboratory）的简称，是美国Math Works公司出品的商业数学软件，用于算法开发、数据可视化、数据分析以及数值计算的高级技术计算语言和交互式环境，它的计算结果具有很高的权威性。Mat lab提供了fft函数，下面我们将利用MATLAB的计算结果验证我们程序计算的准确性。

我们以计算图4.1中8个序列的FFT为例，分别验证算法的正确性。

图4.1.输入序列 图4.2.MATLAB的FFT计算结果

图4.3JAVA实现DFT图4.4 NDK实现DFT 图4.5NDK实现FFT

图4.2是用MATLAB计算得到的FFT结果，图4.3是直接调用通过JAVA实现的DFT算法，图4.4是通过NDK调用C++实现的DFT算法，图4.4是通过NDK调用C++实现的FFT算法，从图4.2、4.3、4.4、4.5可以看出数据结果基本一致，虽有误差但是相差很小，这主要是由于精度的不同导致的。从图4.3、4.4、4.5的用时对比我们还可以看出通过NDK实现的算法的耗时要比直接用JAVA实现的算法均缩短了接近一倍，而FFT的算法又比DFT算法耗费更少的时间，而且这种差距随着计算序列的增加而显著增加，表格4.1是三种算法计算256个序列时在不同设备上耗时情况。

JAVA DFT NDK DFT NDK FFT

SDK虚拟机 36844 2064 145

三星Nexus S 632 218 41

摩托罗拉Xoom 447 108 16

表格4.1.傅立叶实现耗时比较

从表格4.1对比中我们可以看出通过NDK实现要比直接用JAVA实现性能提高的3~15倍以上，而同样是NDK实现FFT又比DFT提高了4-15倍以上，通过NDK的FFT优化性能比直接调用SDK提升了两个数量级，而随着计算量的增加性能的提升将更加明显。

四、结束语

本文不仅阐述了傅立叶变换和快速傅立叶变换的原理还给出了其在Android平台上的算法实现。最后还通过实验验证和对比了在Android系统上实现傅立叶变换算法的准确性并通过NDK实现的方式提升了算法的性能，这将给在Android上基于傅立叶变换的程序应用带来方便。