傅里叶转换(FT)，C语言实现

绝地灬酷狼 2022-11-27 07:06 92阅读 0赞

最近在看傅里叶转换(FT)和快速傅里叶转换(FFT)，感觉很难，包括号称“小学生都能看懂的快速傅里叶转换”，也是一样晦涩难懂，当然，这不排除现在的小学生智力都很强，而我的智商已经在走下坡路了。言归正传，我也来实现一下傅里叶转换(FT)，下一节再实现快速傅里叶转换(FFT)。

傅里叶转换是非常有用的一个算法，在声学、信号处理等领域有广泛的应用，例如核磁共振得到的数据是很难看出特征的，用傅里叶转换之后，就很容易看出谱图的特征。两个多项式的乘法也称之为“卷积”，“卷积”操作是AI中非常常见且重要的操作，傅里叶转换也可以用于两个多项式的乘法。傅里叶转换的时间复杂度是O(N2)，快速傅里叶转换的时间复杂度为O(N \* logN)。这两者的差距就相当于冒泡排序和快速排序的差别，所以我们很有必要学习一下这两种转换。在这里，我们就用两个多项式的乘法为例介绍傅里叶转换。

## 傅里叶转换 (FT) ##

有三个数a, b, c。其中a = 111, b = 11111，c = a \* b，我们很容易用计算器求出c = 1233321。但是如果a和b都是非常大的数，例如都有100位，我们就没办法用计算器求解了。如果用C语言的编程，则会超出范围。  
int a = 1111111111111111111111111111111111111111111; //假设有100位  
int b = 1111111111111111111111111111111111111111111; //假设有100位  
int c = a \* b;

对于这样的问题，我们该怎么办呢？这就要用到傅里叶转换了：用数组arr1存放a中的每一位数据；用数组arr2存放b中的每一位数据。然后让arr1中的每一个元素与arr2中的每一个元素相乘，并累加。代码如下：

#include<stdio.h>
    #include<stdlib.h>
    
    int * arr;
    
    //傅里叶转换，时间复杂度为O(N * M) 
    void ft(int * arr1, int * arr2, int n, int m) 
    {
        
    	int a = 0;
    	int b = 0;
    	
        for(int i = 0; i < n; i++)
    	{
        
    		for(int j = 0; j < m; j++)
    		{
        
    			//因为这里用到了+=，所以数组arr一定要先进行初始化
    			arr[i + j] += arr1[i] * arr2[j];
    		}
        }
    }
    
    void show(int * arr, int size) //显示arr数组中的数据 
    {
        
    	for(int i = 0; i < size; i++)
    	{
        
    		printf("%d, ", arr[i]);
    	}
    	printf("\r\n");
    }
    
    void initArr(int * arr, int size) //数组arr一定要先进行初始化 
    {
        
    	for(int i = 0; i< size; i++)	
    	{
        
    		arr[i] = 0;
    	}
    }
    
    int main()
    {
        
    	int n = 3; //数组arr1的长度为3 
    	int m = 5; //数组arr2的长度为5
    	
    	//获取空间之后，一定要赋值 (初始化)
    	int * arr1 = (int *)(malloc(n * sizeof(int)));
    	int * arr2 = (int *)(malloc(m * sizeof(int)));
    	arr = (int *)(malloc((n + m - 1) * sizeof(int)));  
    	
    	//初始化 
        arr1[0] = 1; arr1[1] = 1; arr1[2] = 1; 
        arr2[0] = 1; arr2[1] = 1; arr2[2] = 1; arr2[3] = 1; arr2[4] = 1; 
        initArr(arr, n + m - 1); //初始化 
        
    	ft(arr1, arr2, n, m); //傅里叶转换 
    	show(arr, n + m - 1); //arr1有n个元素，arr2有m个元素，则arr有n + m - 1个元素 
    	
    	free(arr1); //回收指针
    	free(arr2);
    	free(arr);
    	printf("Hello\r\n");
    	
        return 0;
    }

运行结果：

![在这里插入图片描述][20200814093815115.png_pic_center]

所以最终结果是1 + 2 \* 10 + 3 \* 100 + 3 \* 1000 + 3 \* 10000 + 2 \* 100000 + 1 \* 1000000 = 1233321。这就是原始的傅里叶转换。思路很清晰，代码实现也很简单。但是时间复杂度很高，为O(N2)，正是因为时间复杂度很高，所以在出现快速傅里叶转换之前，傅里叶转换的应用得不到推广。下一节，我们来实现一下快速傅里叶转换 (FFT)。

注：  
1、一般情况下，最大可接受的算法的时间复杂度为O(N \* N)。比它小一级的时间复杂度为O(N \* logN)。这两者之间有巨大的鸿沟，如果能跨越，则性能会有质的飞跃。例如对于几万个数据的傅里叶变换，处理一次需要30秒。但是如果用快速傅里叶转换，可能只需要几十毫秒，基本上做到了即时转换。

[20200814093815115.png_pic_center]: /images/20221124/e2130d9dafdb4d6a821cb0030cc40301.png